We present the approach we designed to tackle and win the 2025 Graph Drawing Challenge on minimizing the k-planarity of graphs. Our method employs a multi-stage heuristic centered around two Simulated Annealing (SA) algorithms: the first aims to reduce the total number of crossings, while the second improves the k-value. To obtain a good initial solution, we first applied tools from the OGDF library, which helped reduce crossings. The challenge consisted of nine instances to optimize. Our approach achieved the best results on eight out of nine instances - sharing the top score twice with other teams and ranking first alone in six cases.

Wireless Sensor Networks (WSNs) represent a key component in smart building systems. An efficient WSN deployment involves selecting the most appropriate positions within the building to place sensors in order to maximize coverage and minimize the deployment cost. This paper proposes a novel approach called the Hybrid Binary Grey Wolf Optimiser (HBGWO) to automate the WSN deployment in indoor environments. The proposed approach integrates the Building Information Modeling (BIM) database to accurately model the physical layout and structural characteristics of the deployment area. Furthermore, a Steiner Tree-based heuristic has been developed to reduce the number of active sensors while preserving the network coverage. Experimental results demonstrate the efficiency and superiority of the HBGWO approach compared to existing methods in literature in terms of network coverage and deployment cost under the connectivity constraint.

The wireless sensor deployment problem is one of the major issues in wireless sensor networks (WSNs). It involves designing the optimal network topology within the deployment area in order to maximize network coverage and lifetime and minimize cost and energy consumption under the connectivity constraint. The WSN deployment problem is a challenging NP-hard combinatorial optimization problem due to a number of factors, including the size and the type of the deployment area, the number of obstacles, and the number of objectives to optimize. Consequently, metaheuristics are assumed to be the most efficient methods to compute the deployment scheme in a reasonable amount of time. In this paper, several well-known metaheuristics have been tested on the problem of WSN deployment in indoor environments. The problem has been formulated as a constrained single objective optimization problem, and the performance of the selected algorithms has been evaluated through experimentation on a set of ten representative indoor architectural scenarios with varying dimensions and obstacles.

Several studies have shown that the layout of an area's infrastructure has a strong impact on the mobility of the mobile network users. Each district in a city has one or more different type of activity areas. Depending on the type of activity areas that a district covers, several profiles emerge. These profiles are closely linked to the impact a district can have on LTE users mobility. In the current work, we propose a first approach to determine the profile of a district in a territory. The territory under study is the city of Lomé, the data used for this analysis come from the geographical data of the OSM database. An alternative approach is proposed that, in the case of missing data, determines the profile of a new district from knowledge built from other districts in the same study area. To validate the proposed approach, evaluations were conducted considering several types of distance (Mahalanobis distance, Euclidian distance,…). It appears that with the K-NN algorithm, using manhattan distance, we have 61 % accuracy in determining the profile of a new district based on the nearest district's profiles.

Wireless sensor network connectivity is a crucial parameter since it keeps the network operative. Network connectivity may be lost due to a variety of factors, such as energy depletion and sensor node failure. Therefore, the network will be partitioned into a set of disjoint sets, resulting in a loss of data collected by isolated sets. In this paper, we address the problem of connectivity repair for stationary sensor networks (WSNs) in case of multiple disjoint partitions. We propose two heuristics based on Dijkstra algorithm and minimum Steiner tree respectively, to deploy the minimum number of additional nodes while preserving the initial topology. For the two heuristics, a procedure is executed in the first stage to merge disjoint sets having a shared zone in their neighboring deployment zones to reduce the complexity of the solution. The first heuristic is adapted to free-obstacle areas and areas with few obstacles. It connects the less distant segments using Dijkstra algorithm. The second heuristic is rather appropriate for areas with opaque obstacles. Simulation experiments validate the effectiveness of the proposed methods compared to existing approaches.

International audience

Let G be a graph, for which each vertex is assigned one of k colors in {1, ..., k}. A legal coloring requires that two adjacent vertices have two different colors. The minimum sum coloring problem (MSCP) consists of finding such a legal coloring with the smallest sum value, knowing that to each color is assigned an integer value from 1 to k. This paper presents a new memetic approach for this NP-hard problem. The proposed hybrid algorithm is based on a very small population, composed of only two individuals. Thanks to this small population, no selection operator needs to be defined, nor any replacement strategy. In order to prevent a premature convergence of the algorithm, alternative mechanisms are introduced based on an elitist approach. The local search introduced in the population based algorithm is split in two phases. The first one is based on the well known TabuCol algorithm and aims to reduce the number of conflicting vertices. The second one, which is used to improve the total sum value, implements an efficient 2-move local operator. The proposed approach was successfully applied on many graphs from the reference COLORS02 and DIMACS benchmarks. It allowed to achieve most of the best known results, and to overpass the best known results for 15 challenging graphs.

In this study, we proposed a deep learning model to infer the daily individual mobility pattern from static census data. Our work was inspired by Google Brain team work on machine learning system to automatically produce captions that accurately describe images using recurrent encoder-decoder model. They also use a convolutional neural network to exploit the strong spatially local correlation present in their structured data i.e., images. Unfortunately, survey data are generally heterogeneous with unknown local structure. Thus we have adapted their model using instead an appropriate mixed-variate version of restricted Boltzmann machine (MVRBM). This leads to estimation of daily regular mobility displacements in the form of variable length sequence given input individual attributes. The prime strength of our approach is that the resulting mobility flows inherit all the attributes contained in the input census which are typically missing in portable digital media data. Moreover, the model makes use of land use and point of interest data. optimized in this way, the model is scalable to apply to other places conditioned with censuses availability. Finally, it has been validated and showed its efficiency in a real context.

With the rapid growth of cell phone networks during the last decades, call detail records (CDR) have been used as approximate indicators for large scale studies on human and urban mobility. Although coarse and limited, CDR are a real marker of human presence. In this paper, we use more than 800 million CDR to identify weekly patterns of human mobility through mobile phone data. Our methodology is based on the classification of individuals into six distinct presence profiles where we focus on the inherent temporal and geographical characteristics of each profile within a territory. Then, we use an event-based algorithm to cluster individuals and we identify 12 weekly patterns. We leverage these results to analyze population estimates adjustment processes and as a result, we propose new indicators to characterize the dynamics of a territory. Our model has been applied to real data coming from more than 1.6 million individuals and demonstrates its relevance. The product of our work can be used by local authorities for human mobility analysis and urban planning.

Optimization problems are often compared to mountain climbing. In particular, the classical Hill Climber is a so used local search. In this paper we propose to explore further the analogy with climbing a mountain, not alone as it is generally the case but in rope team. Indeed, for difficult problems a single climber (heuristic) can easily be trapped into a local optimum. This situation can be compared to a crevasse which the heuristic can not escape from. In this paper we propose the Rope Team heuristic dealing with several elementary memetic heuristics which corresponds to climbers. The leader of the rope team bring with him at least one other climber, linked by a rope, in order to help him to escape from a local optimum. This approach has been successfully applied to one of the most studied combinatorial problem: the Graph Coloring Problem. The advantage of this approach is twofold: on one hand, it is able to find the best known solution for most of the difficult graphs coming from the DIMACS benchmark; on the other hand, all climbers can be considered simultaneously, allowing parallelization of the algorithm. Among the significant results of this work we can notice 3 well-studied graphs, DSJC500.5 colored with 47 colors, DSJC1000.5 with 82 colors and flat1000_76_0 with 81 colors.

the human mobility is always organized nowadays in a multimodal context. However, the transport system has become more complex. For the sake of helping passengers, building Advanced Travelers Information Systems (ATIS) has therefore become a certain need. Since passengers tend to consider several other criteria than the travel time, an efficient routing system should incorporate a multi-objective analysis. Besides, the transport system may behave in an uncertain manner. Integrating uncertainty into routing algorithms may thus provide more robust itineraries. The main objective of this paper is to propose a Memetic Algorithm (MA) in which a Genetic Algorithm (GA) is combined with a Hill Climbing (HC) local search in order to solve the multicriteria shortest path problem in stochastic multimodal networks. As transport modes, railway, bus, tram and metro are considered. As optimization criteria, stochastic travel time, number of changes and walking time are taken into account. Experimental results have been assessed by solving real life itinerary problems defined on the transport network of the city of Paris and its suburbs. Results indicate that unlike classical deterministic algorithms and pure GA and HC, the proposed MA is efficient enough to be integrated within real world journey-planning systems.

Device-to-Device (D2D) is a promising technique for the future mobile networks and the resource allocation is one of the most crucial problems for its application. In order to efficiently allocate radio resource, the D2D network is organized with clusters such that the adjacent devices are assembled as an one-hop cluster. The cluster resource assignment problem is formulated as a dynamic graph coloring problem, and a graph coloring algorithm is designed from the graph structure point of view. This algorithm is able to allocate radio resource to clusters while they are dynamically generated and deleted. The numerical analysis results show that our algorithm has good performance in resource utilization, runtime and scalability.

Spatial and temporal decomposition of aggregated mobility flows is nowadays a commonly addressed issue, but a trip-purpose decomposition of mobility flows is a more challenging topic, which requires more sensitive analysis such as heterogeneous data fusion. In this paper, we study the relation between land use and mobility purposes. We propose a model that dynamically decomposes mobility flows into six mobility purposes. To this end, we use a national transportation database that surveyed more than 35,000 individuals and a national ground description database that identifies six distinct ground types. Based on these two types of data, we dynamically solve several overdetermined systems of linear equations from a training set and we infer the travel purposes. Our experimental results demonstrate that our model effectively predicts the purposes of mobility from the land use. Furthermore, our model shows great results compared with a reference supervised learning decomposition.