Cynthia Andréa

Santos

Olivier Peton

Bernard Grabot

Louis F Gouveia

Amadeu Almeida Coco

Omar Jaafor

Alexandre Xavier Martins

Celso Sakuraba

Elyn Solano

D Especially

Véronique Bernadette Andre

Keywords: ACO Ant Colony Optimization, AOF Aggregate Objective Function BRKGA Biased Random Key Genetic Algorithm, DFS Depth-First Search, EA Evolutionary Algorithm, GA Genetic Algorithm, GIS Geographical Information System, GRASP Greedy Randomized Adaptive Search Procedures, GUI Graphical User Interface, HCI Human Computer Interaction, HV Hypervolume, ILS Iterated Local Search, LS Local Search, MOEA Multi-Objective Evolutionary Algorithm, MOGA Multi-Objective Genetic Algorithm, MRND Multidirectional Road dominated Sorting Genetic Algorithm ODS Optimal traffic Deviation System, OSM OpenStreetMap, RKGA Random Key Genetic Algorithm, RND Road Network problem with Disruptions and connecting requirements, SCC Strongly Connected Components, SNOP Strong Network Orientation Problem, SPP Shortest Path Problem URND Unidirectional Road

and Christophe DUHAMEL, not only for their marvelous guidance to my research with immense intelligence and patience, but also for their companionship every time I got difficulties and for teaching me the philosophy of life. During these years of study, I

Chapter 1 Introduction

The steady growth of population in urban areas has a strong impact on the basic infrastructures of transportation networks, which are often close to saturation due to their limited capacity. Today, the urban population is already higher than the rural population around the world, but the concentration of population in urban areas is still increasing. The 2014 revision of the World Urbanization Prospects of the United Nations indicates that by 2050, the urban population will account for nearly 66% of total population (6.3 over 9.5 billion of people). This implies an increase of urban traffic flows. Hence, managing the daily traffic is an important and challenging issue, especially in rush hours. Expanding the networks by constructing new routes can be a solution, but it cannot be indefinitely carried out since geographical resources are often scarce, particularly in conurbations.

In recent years, serious modifications in the environment have been observed with significant ecological impacts, such as high concentrations of harmful particles in the air and reduction of agricultural areas resulting in less physical space available for production and livestock. In addition, maintaining urban network infrastructures requires increasing financial input. In this context, one of society's major challenges is to well manage urban transportation network infrastructures in a way to provide support for multiple daily trips for different purposes.

Paris is an example of a city with a high population density. It stands as a reference in the world due to its rich public transportation offer. In spite of that, Paris still needs further improvements in order to handle the traffic better in rush hours, with obvious difficulties for implementing solutions. Thus, several cities are instead trying to reduce the vehicle traffic flow, for instance by setting tolls, prohibited periods, motivating the use of bicycles, stimulating pedestrian habits and public transportation. Even planned cities face problems to managing their urban transportation network. For instance, Brasília, the planned capital of Brazil, was designed for 500 000 inhabitants and it was supposed to allow an easy traffic flow without signal settings. However, 50 years later, this city contains about 2 million inhabitants and is known for its chaotic rush hour traffic. On an even larger scale, Beijing, the capital of China, has one of the largest and the most complicated urban transportation networks in the country, with 21.5 million citizens and about 5.5 million vehicles. As the political and economic center of China, Beijing also welcomes a large number of tourists every year, as well as many international conferences and visits. Although scalability and flexibility were considered in its road and highway design, the fast-growing demands of travel are leading to unbearable congestion, especially in rush hours and on the concentric rings of in-city highways. The geographical configuration can also be a complicating factor. Nice (France) and Rio de Janeiro (Brazil), settled between mountains and beaches, are examples where the geography is a barrier to managing the traffic.

The situation becomes even more complex whenever disruptions (blockages) occur on the road network, either predictable (road works, maintenance, social events, etc.) or not (accidents, bad weather conditions, disasters, etc.). Disruptions can block a number of road sections, thus reducing the traffic capacity and pass-rate in involved areas. They may also break travel paths between some locations on the network (loss of strong connectivity).

Besides, they always generate more congestion, noise and air pollution. Although blockages disrupt a lot the urban road networks, they are usually not properly addressed from a global point of view in most of the cities, especially in medium-large ones. Therefore, innovating approaches should be studied so as to maintain a good level of network services.

Under this background, this thesis comprises two major goals. The one consists of an academic study on Road Network problem with Disruptions and connecting requirements (RND) and the other is dedicated to the software engineering (design and development) of Optimal traffic Deviation System (ODS). The investigation of RND is divided into two specific problems depending on the network structure: the Unidirectional Road Network problem with Disruptions and connecting requirements (URND) and the Multidirectional Road Network problem with Disruptions and connecting requirements (MRND). URND aims at addressing the problem in simpler downtown networks, where streets are likely one-way and simple digraphs can be used as an adequate modeling tool. On the other hand, MRND is designed to address the problem on general transportation networks by using multigraphs (i.e. graphs that can have multiple arcs between pairs of nodes), because streets can be two-way and can have multiple lanes. These two problems are formulated using a multi-flow mathematical model where the decision criteria involve the total travel distance between all pairs of nodes and the number of arc reversals. Reversing the direction of a road segment (an arc reversal) is thus allowed to restore the strong connectivity of the network when needed.

Moreover, two heuristic methods, a Biased Random Key Genetic Algorithm (BRKGA) and an Iterated Local Search (ILS), are proposed with specific adaptations to these two problems for both two objectives. The bi-objective versions of these two metaheuristics are also addressed and analyzed by comparing with an -constraint method and a Non-dominated Sorting Genetic Algorithm II (NSGA-II) in terms of the quality of Pareto fronts.

As an application of the research part, we develop the ODS to provide solutions for decision-makers in order to efficiently manage traffic flows and prevent any inaccessible locations on the network whenever disruptions occur. ODS is planned to be a Decision Support System to manage, schedule and compute deviations (alternate paths) to bypass the blocked routes on a road network. It is also a collaborative project with industry, academic researchers and the traffic control center of city Troyes in France. The industrial partner is a Chinese R&D company, Beijing YuanZhiTianCheng Technology Co. Ltd., and the academic researchers are from the University of Technology of Troyes (Troyes, France) and the Clermont-Auvergne University (Clermont-Ferrand, France). The Traffic Regulation Center of Troyes (Troyes, France) is also involved to provide data, support the development and to test the first deployments of the system, via the regional Innov'Action project "AGIR" (système d'Aide à la décision pour la Gestion d'Interruptions Routières) held by region Champagne-Ardenne (France). The major goal of this project is to run the developed application in a real context and to perform knowledge transfer from academies to the industry.

The core of ODS is a network solver to compute deviations for blocking events. A number of constraints have been identified, but only the most important ones are taken into account in this work which is supposed to be the first stage of the entire collaborative project AGIR.

The first constraint is the strong connectivity of the network and the second one is the traffic load associated to the given disruption. For the former, it is obviously necessary to keep at least one path between all pairs of network points. Thus, the network solver first checks if a disruption breaks the strong connectivity. In such a case, it sends a warning and it proposes deviations using some arc reversals to restore it. For the latter constraint, it tries to avoid as much congestion as possible caused by redirecting a large traffic flow disrupted by a blockage to a route with a smaller traffic load capacity. Yet it can be the only solution in some situations. Hence, the solver does not block the computation of deviations but alerts instead the network manager that the capacity of the deviation may be insufficient. ODS also combines a Geographical Information System (GIS) based on "OpenStreetMap (OSM)" with the solver to obtain the network information from the targeted urban area, to display the computed solutions and to interact with the traffic manager. The roads are classified in several types which can be used to deduce the traffic load capacity by [START_REF] Zilske | OpenStreetMap for traffic simulation[END_REF].

Other identified constraints and requirements are planned to be fulfilled gradually in future stages. For instance, an accident can interrupt a route for a few hours, while tubing maintenance can take days or weeks. Thus, handling disruptions should be scheduled according to the importance and the emergency. In scientific terms, scheduling a set of deviations belongs to the NP-hard class of problems, while the real context raises some more difficulties, like dealing with large amount of data, sophisticated algorithms and integration of complex systems, among others. In addition, cars, buses and trucks have different sizes and functions, implying that a deviation adapted for one type of vehicle could not be used for others. A typical example is trucks employed for merchandise transportation whose weight can exceed the allowed capacity of a street. Another example is a deviation set for cars that cannot be used for long buses due to limitation in its turning radius. Furthermore, the alternating traffic can also be a good solution for some disruptions, but it is not yet evident to determine in which cases it could be applied, especially in narrow streets.

The deviations, apart from manually-designed ones, are computed according to one or more optimization criteria. The following objectives are considered: the bypass distance; the expected duration of travel among pairs of origins and destinations; the number of allowed modifications on the route directions; the number of signal settings and congestion. Such objectives can be handled individually, in priority order or even in a multi-criteria schema.

In a real urban context, several predictable and unpredictable disruptions may be considered per time period, which could generate conflicting decisions if addressed individually. Thus, a global vision of the network over time is necessary. ODS is being developed to support all of the mentioned requirements which have been defined together with the partners working in a real context. Its general goal is to manage and schedule deviations over time and it is expected to be integrated into the traffic control center of Troyes by 2018. A functional prototype has been first designed to validate the idea and workflow. The system in production is then developed for a professional use. Major features are mostly accomplished while fine tuning and optimization are still required in order to deliver progressively the final software. Currently, a number of modules are already working: (i) an interactive customized GIS based on the network of Troyes; (ii) a Graphical User Interface (GUI); (iii) computing deviations for a given blockage minimizing either the travel distance, the number of employed road segments or the number of traffic signals;

Document structure

This document is globally organized around these two parts, i.e. the scientific part and the application one. The current chapter ends with the Section 1.2 listing the publications produced during this thesis and the conferences attended. Contributions ordered by chapters are as follows.

Chapter 2 gives a bibliographical survey in three related research fields: the graph theory, the Network Design Problem (NDP) as well as its applications in specific contexts, and algorithms. Basis of graph's strong connectivity has been investigated in previous works, either for simple graphs or for multigraphs. The orientation problem respecting strong connectivity was mentioned in some studies as well, referred as Strong Network Orientation Problem (SNOP). It is highly related to the class of RND. The arc reversal is another feature of RND, which is considered in some investigations. Besides, inspiration from NDP's point of view is also an important gateway to single-and bi-objective RND, especially in terms of mathematical models and frameworks for assignment problems, traffic signal location problems and toll setting problems. There are also many studies of NDP applied on real transportation networks.

Mathematical formulations are detailed in Chapter 3. Notations used in mathematical definitions are presented first in Section 3.1. In Section 3.2, RND is precisely defined based on the graph theory. Depending on the network structure, two problems are defined: the URND and the MRND. They rely on different underlying graphs, the one on simple graphs and the other on multigraphs. Section 3.3 gives the model of URND while Section 3.4 addresses the formulation for MRND. Specification of MRND model is also described by proposing the 2-directed multigraph and indexing multiple lanes. Experiments using the commercial solver CPLEX and their numerical results are developed in Section 3.5.

In Chapter 4, two approximate methods are proposed, a BRKGA and an ILS. Extending the Depth-First Search (DFS) on graphs, an random orientation algorithm is developed.

It has been integrated in the two heuristics. Section 4.2 presents the two heuristics in their single-objective version. The basic principles of BRKGA are explained, such as the random keys, decoding, elitism, etc., as well as the adaptation introduced so as to handle both URND and MRND. The section also gives the details of ILS, including the constructive heuristic, local search operators and shaking. The bi-objective versions of these two methods are addressed in Section 4.3, especially the adaptations for constructing Pareto fronts. In addition, a NSGA-II method is adapted to bi-URND and bi-MRND since it is one of the most efficient method to compute approximate Pareto fronts. It will be used to measure the performance of our two dedicated metaheuristics. An exact method, the -constraint method, is also developed in this section in order to analyze the bi-objective performance of the heuristics. Results of experiments on the two methods for both single-and bi-objective versions are presented in Section 4.4. For the former, a comparison is done with the results obtained using the proposed mathematical formulations. For the latter, the heuristic results are compared with the ones from the bi-objective -constraint method.

Chapter 5 is dedicated to the application in real context: the ODS. Its description is divided into three parts. The first corresponds to the requirements analysis; the second presents the architecture of the system, i.e. the Human Computer Interaction (HCI), the database and the network solver; the third raises a number of known gaps in terms of technology. Screenshots are given in order to illustrate the system's look-and-feel and the usage of the system is explained by scenarios.

Finally, Chapter 6 concludes this thesis with a summary of contributions and proposals of future works.

List of publications

Works of this thesis are progressively carried out to publications listed below. Especially, the software development of ODS belongs to the project TOAST (Tactical Optimization Strategies to Adapt Urban Transportation Networks), one of the laureates of the Prix Européen d'Innovation Le Monde -Smart Cities 2017. As an innovation idea, ODS participates as well to the TRAVISION 2016 student contest and overall ranked 13 th out of 107 submissions from Europe.

Submitted articles

• Yipeng Huang, Andréa Cynthia Santos, Christophe Duhamel, Model and methods to address urban road network problems with disruptions. Submitted to International Transactions in Operational Research (to appear). 2018.

• Yipeng Huang, Andréa Cynthia Santos, Christophe Duhamel, Bi-objective methods for road networks problems with disruptions. Submitted to Annals of Operations Research (to appear). 2018.

International conference with indexed acts

• Yipeng Huang, Andréa Cynthia Santos, Christophe Duhamel, Methods for solving road network problems with disruptions. Electronic Notes in Discrete Mathematics, Volume 64. pp. 175-184, 2018. • Yipeng Huang, Andréa Cynthia Santos, Christophe Duhamel, A bi-objective model to address disruptions on unidirectional road networks, in: Proceedings of the 8th IFAC Conference on Manufacturing Modelling, Management and Control (MIM2016), 12 (49), pp. 1620-1625, Troyes, France, 2016.

International conference with extended abstracts

• Yipeng Huang, Andréa Cynthia Santos, Christophe Duhamel, Heuristiques pour le problème de reconfiguration des réseaux urbains suite à des interruptions routières, in:

Actes du 19ème congrès de la société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF). 2p. Lorient, France, 2018.

• Yipeng Huang, Andréa Cynthia Santos, Christophe Duhamel, Disruptions management in multidirectional road networks, in: Proceedings of the 9th Triennial Symposium on Transportation Analysis (TRISTAN16), 4p. Oranjestad, Aruba, 2016. Chapter 2

International conference abstracts

State of the art

Road networks have been intensively investigated in various domain over years. This chapter is dedicated to the literature review closely related to the problems addressed in this thesis in terms of graph theory, network design and real applications. According to the definition of RND, the strong connectivity and the arc reversal are two relevant graph features. Theoretical studies have been carried out on the SNOP, which are reviewed in Section 2.1. In terms of applications, NDP is also strongly related to RND. Therefore, other related contributions are surveyed in Section 2.2.

Related researches on graph theory

In the field of graph theory, there are several relevant topics for RND, such as the strong connectivity, orientation problem and reversal of arc direction. In the seminal work of [START_REF] Robbins | A theorem on graphs, with an application to a problem on traffic control[END_REF], the theorem stating the condition for a simple graph to admit a strong orientation is first presented. Motivated by the traffic control problem for modern cities, an orientable graph is defined as a graph which admits strong orientations. The orientability of a graph refers to the fact that, if any of its edges can be safely removed without breaking its connectedness, there will exist a strong orientation of the graph. Besides, an edge whose removal makes the resulting graph no longer connected corresponds to a bridge of the graph. Thus, only bridgeless graphs admit strong orientations. This theorem is commonly considered as the first key-stone for the strong orientation problem which has been studying since last decades. Furthermore, multiple orientations can exist on an orientable graph but there should be metrics by which the orientations can be compared. To this extent, [START_REF] Chvátal | Distances in orientations of graphs[END_REF] propose a thorough study on the distance metric for strong orientations, which was not taken into account in earlier literature and which can be problematic when converting a two-way network into a one-way network since some original paths may involve longer detours. A lower-bound, which is still the best one till now, is proposed for the radius of orientations and a classification of orientation problems with different distance constraints is presented. By limiting the radius (resp. diameter) of strong orientation on a given undirected graph, the authors prove that the problem becomes very difficult to solve and belongs to the class of NP-hard problems. Also inspired by [START_REF] Robbins | A theorem on graphs, with an application to a problem on traffic control[END_REF], [START_REF] Boesch | Robbins's Theorem for Mixed Multigraphs[END_REF] extend the strong orientation problem to mixed multigraphs. The term "mixed" specifically indicates that undirected edges and directed arcs can co-exist on the given graph. Thus, a network containing both one-way and two-way streets can be modeled (an initial strong orientation exists). Strictly speaking, it also differs from multigraphs, consisting only of undirected edges, and multidigraphs, including only directed arcs. Turning a mixed multigraph into a multigraph simply involves undirecting all arcs. The authors propose and prove that a strong orientation of a mixed multigraph exists iff there is no bridges on its undirected multigraph. In a real context, this corresponds to a road segment whose orientation cannot be changed since it would leave some locations unreachable and isolated on the network. [START_REF] Chung | Strongly connected orientations of mixed multigraphs[END_REF] is another extension of [START_REF] Robbins | A theorem on graphs, with an application to a problem on traffic control[END_REF] combining the study of [START_REF] Chvátal | Distances in orientations of graphs[END_REF] on distance and the study of [START_REF] Boesch | Robbins's Theorem for Mixed Multigraphs[END_REF] on mixed multigraphs. The major contributions are adapting the orientation radius lower-bound of [START_REF] Boesch | Robbins's Theorem for Mixed Multigraphs[END_REF] on mixed multigraphs and proposing a linear-time algorithm to check the orientability of a given graph. Authors prove two Lemmas following the conditions of the orientability proposed by [START_REF] Boesch | Robbins's Theorem for Mixed Multigraphs[END_REF]. The first states that orienting an undirected edge following the direction of the cycle it belongs to does not violate the orientability of the given graph. The second shows that there should be at least one outgoing directed arc and one incoming directed arc between any two connected components. Based on these Lemmas, the orientability check algorithm is designed by: (i) extending a DFS [START_REF] Tarjan | Depth-First Search and Linear Graph Algorithms[END_REF]) to orient the given graph and (ii) reachability checks on all vertices. Note that this algorithm is an adaptation of Tarjan's Strongly Connected Components Algorithm developed in [START_REF] Tarjan | Depth-First Search and Linear Graph Algorithms[END_REF]. Besides, using a DFS algorithm to orient simple graphs is also proposed by [START_REF] Roberts | Graph theory and its applications to problems of society[END_REF].

A recent work by [START_REF] Conte | Directing Road Networks by Listing Strong Orientations[END_REF] can be noticed as it has a considerable correlation to RND. It proposes an algorithm for enumerating all strong orientations in O(m) amortized time each for a given mixed multigraph with respectively m edges. Authors defined a specific graph transformation technique by merging a directed cycle to an auxiliary node such that undirected self-loops are formed. A strong orientation of the rest of the graph can be extended by assigning a direction to each self-loop to obtain a strong orientation of the entire graph.

Chapter 2. State of the art Next, following the theorems of [START_REF] Robbins | A theorem on graphs, with an application to a problem on traffic control[END_REF] and [START_REF] Boesch | Robbins's Theorem for Mixed Multigraphs[END_REF], the one-way cut and forcing cut are defined depending on the status of an eventual bridge (whether or not directed towards the component such that the resulting graph is not strongly connected). By making use of the linear time algorithm of [START_REF] Italiano | Finding strong bridges and strong articulation points in linear time[END_REF] for finding strong bridges, the algorithm proposed in this work orients all these bridges in a way that the rest of the graph is orientable. Then, the algorithm recurs with removal of an arbitrary edge and outputs every strong orientation found during the procedure.

The question of reversing the orientation of an arc has been investigated in graph theory, mainly to investigate the impact on some graph invariants. For instance, Ádám (1963) introduced a conjecture on the existence of an arc whose reversal decreases the number of elementary cycles in a digraph by at least one cycle. The conjecture has been validated on some class of graphs, for example, digraphs containing a 2-arc cycle. However, counterexamples are also found on some classes of graphs, by [START_REF] Jirásek | On a certain class of multidigraphs, for which reversal of no arc decreases the number of their cycles[END_REF][START_REF] Thomassen | Counterexamples to Ádám's conjecture on arc reversals in directed graphs[END_REF] and [START_REF] Jirásek | Arc reversal in nonhamiltonian circulant oriented graphs[END_REF]. According to these works, the conjecture remains open on simple digraphs. More recently, [START_REF] Bogdanowicz | On arc reversal in balanced digraphs[END_REF] shows that the reversal of any arc in a balanced directed loopless multigraph decreases the number of non-necessarily elementary cycles.

The impact of network disruptions on the Shortest Path Problem (SPP) in terms of travel time is addressed by [START_REF] Sever | Dynamic shortest path problems: Hybrid routing policies considering network disruptions[END_REF]. Each arc is associated with a disruption probability.

Thus the disruption state of each vulnerable arc is modeled by a random variable. A generic framework is proposed using a dynamic programming approach to evaluate both online and offline routing policies. In this Markov decision process, online information on disruption states is available or not. This investigation provides valuable insights for RND, even if our problem is more oriented towards a deterministic context in which disruptions are pre-defined in advance.

Network design and applications

As a problem based on the reorganization of urban road networks, RND is highly related to NDP. Studies are thus reviewed in this section in theoretical and application's points of view.

Theoretical studies and surveys

The work of [START_REF] Magnanti | Network Design and Transportation Planning: Models and Algorithms[END_REF] is considered as a key entry point to the NDP. A three-level classification of NDP is proposed: strategic, tactical and operational, which correspond respectively to investment decision-making (i.e. road construction or expansion), link modification (especially orientation problems) and facility location problems Urban transportation road network problem (like traffic signal setting). Authors give a survey on many network design models specialized in various problems, either discrete or continuous. A generic model is developed to cover most of discrete network design problems with some specializations and variations. Optimization-based methods for solving NDP are also mentioned, such as Benders Decomposition, Branch and Bound and Linear Programming. Complexity, limitation in computations and heuristics for solving NDP are also presented, stating that medium-sized networks (50 nodes and 150 arcs) can be efficiently solved at that time by current heuristics.

Nevertheless, handling larger instances still requires improvements on the proposed methods. [START_REF] Boyce | A discrete transportation network design problem with combined trip distribution and assignment[END_REF] The Generalized NDP is formally defined and investigated by [START_REF] Feremans | Generalized network design problems[END_REF], describing the generalization of NDP by vertex clustering and the optimization-based solution by an optimal subgraph subject to a set of constraints. Authors consider that a graph is divided into several groups of vertices denoted "clusters". According to their statement, problems can be divided into spanning problems whose feasible solutions should cover all vertex subsets and non-spanning problems whose solutions do not involve all clusters of vertices. Complexity of different example problems are listed, showing that the generalization makes these problems harder than their classical versions in most of the cases. Authors then survey some previously studied generalized graph problems which can prove the concept of the Generalized NDP, such as the generalized minimum spanning tree problem (by [START_REF] Myung | On the generalized minimum spanning tree problem[END_REF]), the generalized traveling salesman problem (by [START_REF] Henry-Labordere | The record balancing problem: A dynamic programming solution of a generalized traveling salesman problem[END_REF], [START_REF] Saskena | Mathematical model of scheduling clients through welfare agencies[END_REF] and [START_REF] Srivastava | Generalized traveling salesman problem through n sets of nodes[END_REF]) and the generalized shortest path problem (by [START_REF] Li | The shortest path with at most l nodes in each of the series/parallel clusters[END_REF]).

More reviews on theoretical network design can be found in [START_REF] Fernandez | Equilibrium predictions in transportation markets: The state of the art[END_REF], [START_REF] Boyce | Urban transportation network-equilibrium and design models: recent achievements and future prospects[END_REF] and [START_REF] Friesz | Transportation network equilibrium, design and aggregation: Key developments and research opportunities[END_REF], including models, methods and case studies for network equilibrium, design or aggregation problems. Furthermore, diving deeper in the context of urban transportation system, readers are referred to [START_REF] Cascetta | Transportation Systems Engineering: Theory and Methods[END_REF] SNOP [START_REF] Santos | Heuristics for setting directions in urban networks[END_REF]) is a problem highly related to RND. It aims at setting a strong orientation to an undirected graph G 0 = (V, E). That is to say assigning a direction for every undirected edge e ∈ E such that the resulting digraph should be strongly connected. The total distance of a given set of origin-destination trips (R =

{(o 1 , d 1 ), (o 2 , d 2 ), . . . , (o n , d n )}|(o n , d n ) ∈ V × V, 1 ≤ n ≤ |V |) is minimized. Differing from
SNOP, RND searches for re-orienting a given oriented digraph (the original network) in which a set of blocked arcs are removed, such that the graph remains strongly connected. If an arc is oriented in the opposite direction of the original one, it is considered as a reversal. [START_REF] Miandoabchi | Optimizing reserve capacity of urban road networks in a discrete Network Design Problem[END_REF] study the lane allocation problem, considering the reserve capacity concept (ability to allow additional flow). They propose a bi-level model following the widely-used framework of [START_REF] Yang | Models and algorithms for road network design: a review and some new developments[END_REF], in order to solve the lane addition and orientation problem with reserve capacity. In particular, lane allocation was considered in two variations according to the layout symmetry constraint on both sides of a two-way road.

Applications and case studies on NDP

Two metaheuristics have been proposed: a Hybrid Genetic Algorithm and an Evolutionary Simulated Annealing. Experiments using several fictive networks indicate that the first one has a better performance. Some works handle NDP in real contexts in different levels. For instance, [START_REF] Cantarella | Heuristics for urban road network design: Lane layout and signal settings[END_REF] investigate methods to deal with the UTNDP addressing the network topology and the signal settings, in order to reorganize the traffic. The signal settings are modeled using the Urban transportation road network problem Method of Successive Averages on the Flow Averaging which had been proposed by [START_REF] Powell | The Convergence of Equilibrium Algorithms with Predetermined Step Sizes[END_REF]. The authors propose heuristics, metaheuristics and hybrid methods: two Hill Climbing methods, a Genetic Algorithm (GA), a Simulated Annealing and a Tabu Search (TS). The first hybrid method combines the GA and the TS, while the second couples the The authors propose a metaheuristic based on the Scatter Search of [START_REF] Glover | Scatter Search[END_REF],

where the assignment problem is solved by the Ant Colony Optimization method of [START_REF] Dorigo | Ant Colony Optimization[END_REF]. Computational experiments are done with 8,700 km of the Campania regional road network composed of 262 road nodes, 764 road links.

It is important to mention that the works of [START_REF] Cantarella | Heuristics for urban road network design: Lane layout and signal settings[END_REF] and [START_REF] Gallo | A Meta-heuristic Algorithm for Solving the Road Network Design Problem in Regional Contexts[END_REF] deal with long-term issues of NDP. Thus, in this thesis, relevant contributions consist of handling both short-term and long-term decisions to improve urban network infrastructures.

Especially, the core of ODS is able to manage disruptions for both short-and long-term purposes with the orientation problem in multigraphs. To the best of our knowledge, this problem has not been investigated in the literature either in theoretical and practical issues, or in the real context. The aforementioned theoretical and practical works will provide an initial base to build our methods for RND and to develop ODS. Finally, Section 3.5 shows computational experiments of the aforementioned formulations and provides analysis of their numerical results.

Notations

Notations used in this chapter as well as in the rest of this document are explained in this section. Especially, different types of graph are presented.

Let G 0 = (V, E) be an undirected connected loopless graph with V the set of vertices and E the collection of edges. An unweighted edge is denoted by a pair of vertices i, j where i, j ∈ V × V such that i, j = j, i. In addition, a weighted edge is an edge (i, j) with a cost assigned denoted by γ ij .

In addition, let G 1 = (N 1 , A 1 ) be a connected simple digraph. N 1 is the set of nodes and A 1 is the set of distinct arcs. An arc has an orientation denoted by an ordered pair (i, j) where i, j ∈ N 1 × N 1 , i.e. (i, j) = (j, i). Note that any arc a ∈ A 1 is unique. Similarly to the definition of a weighted edge, the arc (i, j) can also be associated with a cost γ ij . Suppose B 1 ⊂ A 1 be a set of disruptions containing arcs that can no longer be used for routing. H 1 = (N 1 , A 1 ) is the underlying graph of G 1 on which blocked arcs are removed,

thus A 1 = A 1 \ B 1 .
Moreover, let G 2 = (N 2 , A 2 ) be a directed connected multigraph with N 2 the set of nodes and A 2 the collection of arcs. As mentioned previously, there can be more than one arc between a pair of nodes in a multigraph. Thus, an arc a ∈ A 2 does not have to be unique. Therefore, arcs between the same pair of node i, j ∈ N 2 × N 2 should be associated with an index k ∈ N so as to be distinct from each other. Then, the representation of an arc becomes (i, j, k). Likely to the aforementioned set of blockages

B 1 , B 2 ⊂ A 2 is the collection of disruptions on G 2 . H 2 = (N 2 , A 2 ) is then defined as the underlying graph of G 2 that excludes blocked arcs b ∈ B, i.e. A 2 = A 2 \ B.

Road networks problems with disruptions and connecting requirements

First, it is important to highlight the relation between the situation in practice and its modeling by means of graph theory. For instance, a road network must have a path allowing the access to any point of the networks. In graph theory, this characteristic relies on the so-called connectedness property for undirected graphs and the strong connectivity property for directed graphs. Moreover, changing the orientation of a lane corresponds to modifying the orientation of the corresponding arc, named here an arc reversal. One may note that arc reversals are likely to disturb users habits. That is why one of the objectives focused in this thesis is to minimize the number of arc reversals. As a consequence, as few modifications as possible are done on the network such that the strong connectivity is guaranteed. Last but not least, a disruption on the road networks is defined as an unavailable edge in undirected graphs or as an unavailable arc on digraphs. Other specific solutions could also be taken into account such as alternated traffic, lanes reduction and transforming a two-way street into two one-way lanes as it have been done in the "Quai du Comte Henri" in Troyes. These could be possible extensions to our work.

Roads (road segments) and crossroads (intersections) are the two topological components of a transportation network, which correspond respectively to edges and vertices in graph theory. Thus, modeling networks by graphs has been an obvious and efficient approach.

However, roads can be either one-way or two-way, which should be represented differently on graphs in such a way that one-way streets are modeled by directed arcs and two-way streets are displayed by undirected edges. Moreover, a two-way street can even have multiple lanes in both directions and it does not seem evident if such a street is represented by an undirected edge. That is the reason why directed multigraphs are involved. Unlike simple graphs which can have at most one edge (arc) between a pair of vertices, there might be more Chapter 3. Formal definitions and mathematical formulations than one edge (arc) between two nodes so as to represent lanes of a road. The connecting requirement means the graph has to be strongly connected, i.e., there exists at least one path between every pair of Origin-Destination (O-D) nodes. Since disruptions are treated as arcs removed from the given graph, they can potentially break the strong connectivity.

The main goal of RND is to find orientations of given networks in order for the networks to remain strongly connected in case of disruptions. Two objectives are considered as measures of orientations: (i) minimizing the total travel distance (c 1 ) and (ii) minimizing the number of arc reversals (c 2 ). To restore strong connectivity broken by disruptions, the direction of every arc is allowed to be reversed. However, an arc reversal may involve a lot of operational forces such as setting notice panels and keeping network users informed. It also perturbs drivers' habits which may further cause congestion in concerned areas and even more disruptions.

Thus, it should be applied only when necessary and minimizing arc reversals is justified as mentioned at the beginning of this section.

Depending on the type of networks addressed, either unidirectional or multidirectional, two problems (URND and MRND) are then proposed and defined in the following two sections with their bi-objective versions being respectively bi-URND and bi-MRND.

Unidirectional road networks problems

URND particularly addresses historical downtown networks where roads are often one-way due to limited width. This is the case of the city center of Troyes and many other French cities. Layouts are often fixed in order to lead traffic flows in designed paths.

However, finding bypasses is almost impossible without modifying the configuration of the network since blocking a one-way street can make some destinations unreachable, which must be avoided for network users. Furthermore, if a non-informed driver just arrives in front of a blocked road, he is willing to find a detour. But he cannot simply take a U-turn to get back to the previously passed intersection and should sometimes perform a long trip over a certain area. This increases the travel cost of some network users and often leads to traffic difficulties. Hence, managing disruptions can be very complicated from a network manager's point of view. The previously defined graph G 1 is used to model URND with nodes representing road intersections and arcs standing for road segments. Setting strong orientation minimizing all distances on undirected graphs is an NP-hard problem, formally proved by [START_REF] Burkard | Minimum-cost strong network orientation problems: Classification, complexity, and algorithms[END_REF]. In addition, the problem with the number of reversals minimization is polynomial [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]. Consequently, URND is NP-hard with c 1 objective and it is polynomial with c 2 objective. Thus, NP-hardness can be deduced for the bi-objective version, bi-URND. with nine nodes 0, 1, 2, 3, 4, 5, 6, 7, 8 and one blocked arc (4, 5). Suppose G 1 models this network with the blockage illustrated in Figure 3. 1-(a). It is no longer strongly connected due to the blocked arc.

Given G 1 = (V 1 , A 1 ), let P = {(o, d)|o, d ∈ V 1 , o = d} be the set of all O-D pairs in G 1 and
let the B 1 be the list of the p blocked arcs (disruptions). All arcs (i, j) ∈ B are preprocessed and removed from G 1 , leading to the modified graph H 1 = (N 1 , A 1 ), as described in Section 3.1. Since the strong connectivity is the major concern in URND, it is ensured by forcing a unit flow for each O-D pair (o, d) ∈ P . The direction of arcs in A 1 are allowed to be reversed.

The two criteria to be minimized for a solution s are the total distance c 1 (s) and the number of reversed arcs c 2 (s).

The decision variables x ij ∈ {0, 1} is used to represent the reversal state of the arc (i, j) ∈ A 1 . If it is reversed, x ij = 1; x ij = 0 otherwise. The flow of the path from o to d on the arc (i, j) is modeled by variables f od ij ∈ R, taking its reversal state into account. For instance, assuming (i, j) is used to send flow from o to d, f od ij > 0 if the arc keeps its original direction and f od ij < 0 if the arc is reversed. Variables y od ij ≥ 0 keep the amount of flow from o to d going through the arc (i, j) independently of its orientation.

Proposition 3.1. The variables f od ij as defined above are valid for the flow conservation constraints in URND.

The proposed mathematical model is then as follows:

min c 1 = (o,d)∈P (i,j)∈A 1 γ ij y od ij (3.1) min c 2 = (i,j)∈A 1 x ij s.t. (3.2) l:(l,o)∈A 1 f od lo - l:(o,l)∈A 1 f od ol = -1 ∀(o, d) ∈ P (3.3) l:(l,i)∈A 1 f od li - l:(i,l)∈A 1 f od il = 0 ∀(o, d) ∈ P , ∀i / ∈ {o, d} (3.4) -y od ij ≤ f od ij ≤ y od ij ∀(o, d) ∈ P , ∀(i, j) ∈ A 1 (3.5) -x ij ≤ f od ij ≤ 1 -x ij ∀(o, d) ∈ P , ∀(i, j) ∈ A 1 (3.6) x ij ≤ (o,d)∈P y od ij ∀(i, j) ∈ A 1 (3.7) x ij ∈ {0, 1} ∀(i, j) ∈ A 1 (3.8) f od ij ∈ R ∀(o, d) ∈ P , ∀(i, j) ∈ A 1 (3.9) y od ij ≥ 0 ∀(o, d) ∈ P , ∀(i, j) ∈ A 1 (3.10)
The first objective function (3.1) aims at minimizing the total travel cost and the second objective function (3.2) minimizes the number of arc reversals. Constraints (3.3) and (3.4) are the flow conservation constraints using variables f od ij . Inequalities (3.5) link variables f od ij with variables y od ij in order to set the amount of flow. Constraints (3.6) link f od ij with x ij for f od ij variables to take arcs' orientation into account. In addition, arcs not carrying flows do not need to be reversed, as set in constraints (3.7). Moreover, variables are defined from (3.8) to (3.10). Besides, this model contains (2

× |P | + 1) × |A 1 | variables and (|P | 2 + (4 × |A 1 | -1) × |P | + 2 × |A 1 |) constraints.
Note that, according to a recent improvement of the model, the relation among the variables x ij , f od ij and y od ij can be enhanced by the constraints (3.11). It can be linearized into the inequalities (3.12) along with the constraints (3.5). The constraints (3.6) can thus be replaced by this definition. (i, j) ∈ A 1 without any flow, i.e. arcs not used in the path from 4 to 1. The difference between f and y only occurs for the flow on the arc (5, 4) in the solution with arc reversal: f 4,1 5,4 = -1 while y 4,1 5,4 = 1. Another simpler model can also be defined with only 2 sets of variables. It relies on the graph G 1 = (N 1 , A 1 ) with N 1 = N 1 and A 1 = A 1 ∪ A 1 , i.e. the set of all possible arc orientations. The set of arc reversals is extended to A 1 : x ij ∈ {0, 1}∀(i, j) ∈ A 1 . The variables f od ij ≥ 0 store the flow on the arc (i, j) ∈ A 1 from the origin o to the destination d. Then, the alternate model is as follows:

f od ij = f od ij × (1 -2x ij ) ∀(o, d) ∈ P , ∀(i, j) ∈ A 1 (3.11) -2x ij + y od ij ≤ f od ij ≤ 2 -2x ij -y od ij ∀(o, d) ∈ P , ∀(i, j) ∈ A 1 (3.
min c 1 = (o,d)∈P (i,j)∈A 1 γ ij f od ij (3.13) min c 2 = (i,j)∈A 1 x ij s.t. (3.14) l:(l,i)∈A 1 f od li - l:(i,l)∈A 1 f od il =        -1 if i = o 1 if i = d 0 otherwise        ∀(o, d) ∈ P (3.15) f od ij ≤ 1 -x ij ∀(o, d) ∈ P , ∀(i, j) ∈ A 1 (3.16) x ij + x ji = 1 ∀(i, j) ∈ A 1 (3.17) x ij ∈ {0, 1} ∀(i, j) ∈ A 1 (3.18) f od ij ≥ 0 ∀(o, d) ∈ P , ∀(i, j) ∈ A 1 (3.19)

Multidirectional road networks problems

MRND is a more general problem that addresses road networks closer to real situations where one-way and two-way streets coexist. Layouts can be diverse and there can also exist one-way streets with multiple lanes in one direction. The strong connectivity is easier to ensure in MRND than in URND since two-way streets can be used as a bi-directional bridge to connect two strongly connected components. Let the aforementioned multigraph G 2 = (N 2 , A 2 ) be used in the MRND model. Especially, the collection of arcs A 2 can contain multiple arcs corresponding to lanes of two-way streets. One-way streets can still belong to G 2 , which means that an arc a = (n 3 , n 4 ) (a ∈ A , (n 3 , n 4 ) ∈ N 2 × N 2 ) can also be the unique instance between the nodes n 3 and n 4 . Similar to the complexity of URND (resp. bi-URND) presented in the previous section, MRND with c 1 objective is NP-hard while it is polynomial for c 2 . Therefore, bi-MRND is NP-hard as well.

Illustrative orientations are given in Figure 3.5. The network contains nine nodes {0, 1, 2, 3, 4, 5, 6, 7, 8} and a single disruption (4, 1). Suppose G 2 models this network with the disruption as depicted in Figure 3.5-(a). The URND formulation is generalized to handle multigraphs. A graph reduction is first proposed to simplify multigraphs to 2-directed multigraphs defined as follows: Consequently, the following property holds for MRND.

Property 3.1. Any instance of MRND can be represented by a 2-directed multigraph.

Given two nodes i, j

∈ N 2 ×N 2 in the multigraph G 2 = (N 2 , A 2 ), assume [l 1 , l 2 ] ∈ N + ×N +
be the pair of two respective numbers of arcs in the two directions i → j and j → i. The combination [1,0] respects the definition of a 2-directed multigraph since there is a single arc (i, j, 0). On the other hand, [0, 1] is also valid. Any [l, 0] with l > 1 can be reduced to [2, 0] with two arcs: (i, j, 0) and (i, j, 1). Symmetrically, any [0, l] with l > 1 can be reduced to [0, 2] with two arcs (j, i, 0) and (j, i, 1). More generally, a pair {i, j} with [l 1 , l 2 ] where l 1 > 1 and l 2 > 1 can be reduced to [1,1] with an arc (i, j, 0) and another arc (j, i, 0). These reductions do not impact the computation of c 1 criterion. They also support the optimal values for the c 2 criterion.

Thus, G 2 can be reduced to a 2-directed multigraph and possible values for indices k of an arc (i, j, k) ∈ A 2 can be restricted to 2, i.e. k ∈ {0, 1}. Extended to the model in Section 3.3, decision variables are additionally indexed on k, i.e. x ijk ∈ {0, 1} for the reversal state of an arc (i, j, k), f od ijk ∈ R for the flow passed on the arc (i, j, k) on the path from o to d and y od ij ≥ 0 for the absolute amount of flow related to f . Proposition 3.2. The variables f od ijk are valid for the flow conservation constraints in MRND.

Figures 3.6 and 3.7 depict the reduction cases described above. In the former, every graph in columns "a" and "b" can be reduced to the ones in cells "1-a" and "1-b", respectively.

In the latter, reductions can be made from right to left in every row and from bottom to top in every column, and every graph can be reduced to the one in the cell "1-c". Note that these figures illustrate only graphs with up to 3 arcs in a direction. Graphs with more than 3 arcs in one direction between a pair of nodes also admit underlying reduced 2-directed multigraphs.

a b 1 The proposed formulation for MRND is then as follows:

0 1 0 0 1 0 2 0 1 1 0 0 1 0 1 3 0 1 2 1 0 0 1 0 1 2
min c 1 = (o,d)∈P (i,j,k)∈A 2 γ ijk y od ijk (3.20) min c 2 = (i,j,k)∈A 2 x ijk s.t. (3.21) l:(l,o,k)∈A 2 f od lok - l:(o,l,k)∈A 2 f od olk = -1 ∀(o, d) ∈ P (3.22) l:(l,i,k)∈A 2 f od lik - l:(i,l,k)∈A 2 f od ilk = 0 ∀(o, d) ∈ P , ∀i / ∈ {o, d} (3.23) -y od ijk ≤ f od ijk ≤ y od ijk ∀(o, d) ∈ P , ∀(i, j, k) ∈ A 2 (3.24) -x ijk ≤ f od ijk ≤ 1 -x ijk ∀(o, d) ∈ P , ∀(i, j, k) ∈ A 2 (3.25) x ijk ≤ (o,d)∈P y od ijk ∀(i, j, k) ∈ A (3.26) x ijk ∈ {0, 1} ∀(i, j, k) ∈ A (3.27) f od ijk ∈ R ∀(o, d) ∈ P , ∀(i, j, k) ∈ A 2 (3.28) y od ijk ≥ 0 ∀(o, d) ∈ P , ∀(i, j, k) ∈ A 2 (3.29)
The two objective c

(|P | 2 + (4 × |A 2 | -1) × |P | + 2 × |A 2 |) constraints.

Computational experiments and numerical results

Two major goals of the computational experiments on the mathematical models are the following: (i) to know their computational performance and limits; (ii) to identify the gaps to find optimal solutions, for instance, in terms of linear relaxation and how the branch-and-cut tree progresses towards the optimal solution proof. Some mathematical models lead to a very fast computation but they visit a significant number of nodes in the Branch-and-Bound (B&B) tree, while others require only a few nodes to be visited in the B&B tree in spite of a high running time. According to [START_REF] Gouveia | Network flow models for designing diameter-constrained minimum-spanning and Steiner trees[END_REF], multiflow models result generally in good linear relaxation. However, the combinatorial aspects as well as the number of variables and constraints do not allow solving very large instances.

Another relevant point concerns the objective functions. Two criteria are considered, but at this point each one is optimized independently of the other, following a single-objective approach. The bi-objective optimization is also considered but it will be presented later on in this manuscript.

Small-and medium-sized graphs with grid-based layout have been generated as instances for testing the proposed mathematical model, including 14 simple graphs and 24 2-directed multigraphs. All arc costs are set to 1. Disruptions are randomly generated, but a control procedure is also involved in order to guarantee that, when these disruptions are removed from an instance, the resulting graph is still orientable. For multigraph instances, multiple arcs are randomly added so as to stay within the 2-directed multigraph context. Instance characteristics are presented in Tables 3.1 and 3.2 for simple graph instances and multigraph instances, respectively. In these tables, instances are classified into small-sized instances (3x3 and 4x4) and medium-sized instances (5x5 and 6x6), reported respectively in the column "Group". All instance names are reported in column "Name". Columns "n", "m" and "p"

represent respectively the number of nodes, arcs and disruptions. In addition, the column "M %" reports the percentage of multiple arcs in multigraphs, as additional information in Results are reported in Tables 3.3 and 3.4 for URND and MRND, respectively. In both two tables, instance names, c 1 value, c 2 value, CPLEX processing time in seconds, linear relaxation value and relative gap are presented by columns "Instance", "c 1 ", "c 2 ", "t(s)", "LR" and "Gap(%)". Depending on the optimization objective (either c 1 or c 2 ), the columns marked with "*" report the optimal value (i.e. "c 1 *" or "c 2 *", resp.).

For URND, an optimal value of c 1 sometimes implies a significant number of arc reversals. This is undesirable, even unpractical in the real context, because it involves a lot of changes in the network infrastructure as well as an unaffordable user experience for drivers ( for instance the impact on driving habits which may cause troubles and congestion in the areas impacted by reversals). To the opposite, c 2 minimization restricts the number of necessary reversals while the total travel distance of the whole network is left free. This can also be problematic on a real unidirectional network since drivers should sometimes make much longer trips than before to reach their destinations. Traffic loads may also increase on some important paths. Results also indicate that c 1 minimization tends to be very time-consuming when instance becomes larger since the model uses two sets of 4-dimension variables. This can be justified by the sharp growth of the computational time and the globally high value of are given for these instances). However, c 2 minimization is relatively easier for CPLEX. The processing time increases mildly and all 6x6-* instances can be solved to optimality in a reasonable amount of time. On an instance, CPLEX generally uses less time when more disruptions happen. One possible reason may be that blocked arcs are removed from the given instance before the computation. In other words, there are less arcs to handle.

Regarding MRND, according to the results, it seems that CPLEX solves such problem faster than URND. In addition, respecting our generated instance, the more multiple arcs an instance has, the less time CPLEX uses to solve MRND on it. Based on our proposition Chapter 4

Methods for solving single-and bi-objective URND and MRND

In this chapter, the proposed single-and bi-objective methods are presented. First of all, a DFS-based orientation algorithm is proposed and described in Section 4.1. It is used respectively as the decoding method and the constructive heuristic in BRKGA and ILS. Then, Section 4.2 presents the two approximate methods, BRKGA and ILS, for solving single-objective URND and MRND. In Section 4.3, an -constraint exact method is proposed to compute the Pareto-optimal fronts for bi-URND and bi-MRND, followed by bi-objective versions of BRKGA and ILS. Since these two proposed metaheuristics have been basically designed for single-objective optimization, an additional NSGA-II algorithm is also implemented, used as a reference method for bi-objective heuristic optimization. It is presented in Subsection 4.3.4. Finally, experiments on all these methods and their numerical results are shown in Section 4.4.

An orientation algorithm

Given an existing road network in which every link is available for carrying traffic flows, it is by definition strongly connected since every location should be accessible from any other location. However, as described in Chapter 1, disruptions on links can disable some arcs, hence probably turn some locations isolated, i.e. the road network may not be strongly connected anymore. This is the reason why a strong orientation algorithm should be developed on an already oriented network in order to set another orientation that makes the given network strongly connected.

In the case of URND, [START_REF] Roberts | Graph theory and its applications to problems of society[END_REF] proposed an algorithm to build a strong orientation on a simple connected non-oriented graph G 0 = (V, E). It uses the algorithm DFS [START_REF] Cormen | Introduction to Algorithms[END_REF]) to visit the vertices in V through edges in E. Thus, an edge can be oriented during this process. Assume two vertices i, j ∈ N × N and an edge e = (i, j) ∈ E. Suppose the algorithm tries to visit j from i through e. Then, e is oriented from i to j. In this way, every edge in E is oriented and an orientation of G 0 is thus constructed.

Proposition 4.1. The orientation constructed by applying the algorithm proposed by [START_REF] Roberts | Graph theory and its applications to problems of society[END_REF] on a simple connected undirected bridgeless graph (orientable simple graph) is strongly connected.

Readers are referred to [START_REF] Roberts | Discrete Mathematical Models, with Applications to Social, Biological, and Environmental Problems[END_REF] for the proof.

The extension of this algorithm is proposed in this work. First, it is adapted to 2-directed multigraphs for MRND. Second, the algorithm is parameterized in order to provide different strong orientations depending on the parameter.

For MRND, there can be several edges between a pair of vertices on the underlying undirected multigraph of an instance. However, DFS can visit a vertex only one time. We relax this constraint in such a way that a vertex can always be visited until all its related edges are oriented.

Proposition 4.2. By using the relaxed visit mechanism, all the edges of a connected undirected bridgeless multigraph (orientable multigraph) are oriented.

Proof. Given a connected non-oriented graph, the DFS browses all the vertices. By definition, it ends with a final backtrack to the root vertex. Besides, the backtrack in our DFS-based algorithm only occurs when all the edges related to a vertex is oriented. If a non-oriented edge e still exists while the final backtrack, the scan of non-oriented edges on the two ends of e is not completed and the backtrack should not have been triggered. This leads to a contradiction.

Proposition 4.3. By using the relaxed visit mechanism, the resulting orientation on a connected undirected bridgeless multigraph (orientable multigraph) is strongly connected.

Proof. Suppose the underlying simple graph of the given multigraph. It is strongly oriented by the algorithm. When constructing the orientation for the multigraph, the order of visits through its edges is not changed and these edges are oriented in the same way as the underlying graph. Thus, the resulting orientation is strongly connected.

This algorithm is determinist. Given a graph and a root vertex, it generates only one strong orientation. By running the algorithm with each n vertex of the graph as root, we can hence construct at most n strong orientations, whereas some of them might be identical.

However, the DFS can provide more possibilities. In fact, the order of selecting adjacent vertices to visit from the current vertex does not impact the strong connectivity of the resulting orientation, while different orders result in different configurations of the edges.

Thus, varying this order increases the possibility to build different strong orientations.

In this work, the variation of the order is introduced by giving a weight to every vertex.

When scanning from a current vertex, its available adjacent vertices (through a non-oriented edge) are sorted in descending order according to their weights. In this way, a different vector of weights might result in a different strong orientation. This also allows to have a randomized algorithm, if every weight is randomly generated with respect to a certain distribution

U [0,1] .
Property 4.1. Introducing this variation of the selecting order is valid for URND and MRND.

Thus, we obtain the final algorithm detailed in Algorithm 4.1. As for the input arguments, it requires an undirected graph G (either simple for URND or multiple for MRND), a vector of vertex weights W and a root vertex u. Note that any vertex can be used as root. Here, the vertex with the highest weight is considered as the root vertex for the first call of the algorithm. As described in the previous paragraphs, the selecting order is defined by sorting the adjacent vertices in lines 1-2. Then, following this order, lines 3-8 examine every neighbor As a consequence, this algorithm, even randomized by the random weights, may not cover the entire solution space. Thus, it could not generate the optimal solution for certain instances.

[0.9] [0.7] [0.3] [0.5] [0.2] [0.8] [0.6] [0.1] 0 1 2 3 4 5 6 7 8 [0.1] [0.9] [0.6] [0.4] [0.8] [0.7] [0.5] [0.2] [0.3]
However, this issue can be overcome by applying a Local Search (LS).

This algorithm is used as a basic component in our proposed BRKGA and ILS. It is used as the decoding procedure and the constructive heuristic, respectively. Further details are explained in following sections in this chapter.

Single-objective optimization

Heuristics are a very classic way to quickly compute solutions for combinatorial optimization problems. The possible loss of optimality and the fact that poor or even infeasible solutions may be produced are compensated by the short CPU time consumed, whereas sometimes near-optimal solutions can also be found. The main drawback of heuristics is often the poor quality of the produced solution. Thus, LS procedures are designed to improve a given solution by iteratively performing modifications improving its quality, until no more improvement can be done. In addition, metaheuristics extend the LS principle by providing global guidance.

Given an initial solution s, a LS is a method for iteratively improving s by performing local changes. It stops whenever s cannot be improved anymore. Thus, s has become a local optimum s * . Usually, a LS relies on one or several move operators, which define neighborhoods of the current solution,

N i (s), i = 1, 2, • • • , k (k is specified according to the needs).
A neighborhood is the set of all solutions that can be obtained from s by performing a kind of moves. Since a LS is dependent to the input solution and on the moves, the quality of the output solution s * can be poor. Thus, the community tries to optimize the use of the LS in order to enhance it performance to solve complex problems. An intuitive approach is to embed a LS into a multi-start method that calls the LS on a number of randomly generated starting solutions (random restart), for instance Greedy Randomized Adaptive Search Procedures (GRASP). In this way, the output solutions can be diverse and the one with the best fitness can be chosen as the final output solution. Furthermore, memory structures can be integrated in the procedure so as to bias the search towards poorly explored regions or regions of interest, for instance TS and Ant Colony Optimization (ACO).

Embedding LS into global guidance mechanisms leads to the metaheuristics.

A metaheuristic is often a high level coordinator for a set of simple heuristics. It organizes the way these algorithms are called, along with some procedures to overcome their drawbacks, such as the restart, multistart, randomization and shaking procedures. Key metaheuristics include Simulated Annealing [START_REF] Kirkpatrick | Optimization by simulated annealing: Quantitative studies[END_REF]), GRASP (Feo &[START_REF] Feo | A probabilistic heuristic for a computationally difficult set covering problem[END_REF]Feo &[START_REF] Feo | Greedy Randomized Adaptive Search Procedures[END_REF]), Tabu Search [START_REF] Glover | Tabu Search -Part I[END_REF] and [START_REF] Glover | Tabu Search -Part II[END_REF]), Variable Neighborhood

Search [START_REF] Mladenović | Variable neighborhood search[END_REF]), Iterated Local Search [START_REF] Lourenço | Iterated Local Search[END_REF]), etc.

Population-based metaheuristics are also widely used, such as Scatter Search [START_REF] Glover | Heuristics for integer programming using surrogate constraints[END_REF]), Genetic Algorithm [START_REF] Goldberg | Genetic Algorithms in Search, Optimization and Machine Learning[END_REF]) and ACO [START_REF] Dorigo | Ant Colony Optimization[END_REF]).

In order to simplify the presentation of heuristic methods, we first present methods for single-objective RND first and then we show their adaptations to bi-objective optimization.

Two proposed metaheuristics, a BRKGA and an ILS are studied respectively in Subsections 4.2.1 and 4.2.2. In both subsections, a brief state-of-the-art is first presented for the respective method, followed by the adaptation to the context of both single-objective URND and MRND.

BRKGA

GA [START_REF] Goldberg | Genetic Algorithms in Search, Optimization and Machine Learning[END_REF]) is an evolutionary algorithm that works on a population of individuals. Each individual is represented by a sequence of n genes, called a chromosome, for which a fitness value can be evaluated. A so-called generation consists of the creation of a new population by crossover and mutation operators. After a given number of generations, GA selects the fittest individual as the output of the algorithm following the specification of the given problem. At each generation, GA makes its population evolved by randomly selecting and combining individuals in order to generate new individuals called offsprings.

Two individuals are selected as parents denoted A and B. This selection can follow a specific strategy, for instance, an individual with a better fitness is more probable to be selected.

Then, the gene i ∈ [1, n] of their child chromosome is copied arbitrarily from the gene i of either A or B. This procedure is called a crossover. Hence, new children compose the new population to make up the next generation. In addition, a random mutation is another fundamental component of a GA. It is applied to escape local optima and hence improve the diversity of the algorithm. Unlike the crossover, the mutation takes only one chromosome and changes its genes such that it may become different. Note that the mutation does not always take place. A probability can be given in order to decide whether a mutation happens or not in each generation.

One may note that some components of GA are general while others are problem-specific.

For example, problems with different objective functions often have different ways to evaluate an individual, but the crossover always follows a common mechanism. A large part of the specification comes from different encodings, which are the way to represent an individual over different problems and implementations. Thus, using random keys as a common representation of an individual has been proposed by [START_REF] Bean | Genetic Algorithms and Random Keys for Sequencing and Optimization[END_REF]. This leads to a GA with random keys, referred as a Random Key Genetic Algorithm (RKGA). Such an approach is very generic and it can be applied to handle different combinatorial optimization problems.

In a RKGA, every gene of a chromosome is a random key, i.e. a real value in the interval [0,1]. Depending on the specification of the given problem, a vector of random keys should be decoded into a feasible solution by calling a deterministic algorithm, i.e. a decoder, which includes also the logic to evaluate the fitness of the solution. In this way, the problem-specific part is totally isolated. The RKGA can hence be reused in different problems. This only requires an effort to implement specific decoders.

Regarding the classic mechanisms of the evolution, a RKGA keeps the principles of the crossover and the mutation with a slight difference to classical GAs. First, the elitism is applied in a RKGA. Depending on the fitness of the individuals, the population is divided into a small group of elite individuals with a better fitness, and a larger group of the other individuals who are less fit (called non-elites). All elite individuals of a generation are copied without any modification to the next generation. Note that newly created individuals may have better fitness than these copied elites. Therefore, a RKGA sorts the population to recompute the elite set before going to the next generation. Second, the mutation is no longer directly applied on individuals. When creating a new population, a given number of new individuals, called mutants, are introduced. Finally, besides the unchanged elites and the mutants, the crossover is used to generate only the remainder of the new population and the parents are randomly selected from the current population.

BRKGA has been proposed by [START_REF] Gonçalves | Biased random-key genetic algorithms for combinatorial optimization[END_REF] and [START_REF] Resende | Biased random-key genetic algorithms with applications in telecommunications[END_REF]. It is another GA-based framework that extends RKGA. It inherits the major features of RKGA such as the random keys, the elitist population and the mechanism of mutants. The term "biased" refers to the crossover operator. In a BRKGA, to generate an offspring, a parent is always selected from the elite group and the other parent comes from the non-elite group. Moreover, during the crossover, the child has a higher probability to inherit a gene from the elite parent. In this way, the population tends to keep the characteristics from fittest parents over generations. In [START_REF] Gonçalves | Biased random-key genetic algorithms for combinatorial optimization[END_REF], the authors show that a BRKGA converges much better than a classical GA without loss of diversity. Two reverse e back to its initial direction

ILS

In the context of optimizing the use of a LS, [START_REF] Lourenço | Iterated Local Search[END_REF] first formally defined the ILS which follows the guideline of a random shaking (biased sampling) better than a random restart (random sampling). The main purpose is to take a single input solution and repeat a LS for a certain number of iterations. This high-level procedure coordinates several operators and the LS in order to obtain a solution of a better fitness than the one given by running the LS itself for a single time. According to the authors, ILS is divided into four major independent components: the generation of an initial solution, the LS, the acceptance criterion and the perturbation (shaking). The initial solution is often generated by a constructive heuristic. Its quality can be mediocre so that the algorithm tries to improve it.

The LS then combines several operators that push the current solution to its neighborhoods so as to find other solutions which might better fit. In the end of the LS, the solution is stable in a local optimum and cannot be further improved. Thus, the LS is trapped into the local optima. A perturbation procedure is then applied at each iteration, trying to generate a close-enough neighbor solution such that calling the LS on it will lead to an exploration of new regions of the solution space. Before passing to a next iteration, the incumbent solution is evaluated by an acceptance criterion which decides whether it will be used as the new input to the next iteration or not. In most applications, the acceptance criterion is defined by the improvement on the objective function. This means if the current solution has a better fitness, it will replace the input solution and be passed to the next iteration. The authors claim that the choice of the criterion is important and other conditions may also have a good performance.

Applications of ILS on different optimization problems are presented in Lourenço et al.

ILS applied to URND and MRND

In our single-objective ILS intended to address URND and MRND, the DFS-based orientation algorithm is used as the constructive heuristic to generate the initial solution as shown in Algorithm 4.5. To comply to its input requirements, the set of weights is randomly generated in the similar way of BRKGA. Then, the graph's orientation is removed by simply making all its directed arcs undirected. Finally, the resulting undirected graph is strongly oriented by applying the strong orientation algorithm. Thus, the initial solution is feasible by construction.

As for the LS, a Variable Neighborhood Descent (VND) from [START_REF] Mladenović | Variable neighborhood search[END_REF] is used. Given a predefined set of neighborhood structures g ← N 1 (g)

{N i , i = 1, 2, • • • , l}
3:
if fitness(g ) < fitness(g) then 4:

g ← g 5: else 6: g ← N 2 (g) 7:
if fitness(g ) < fitness(g) then 8:

g ← g 9:

else 10:

g ← N 3 (g) 11:
if fitness(g ) < fitness(g) then The second shaking changes completely the current orientation of the graph by reversing all arcs direction, which helps to escape local optima. In order to determine which perturbation should be used in an iteration of the ILS, two thresholds on the number of iterations without improvement are defined to divide the ILS into three stages. A specific perturbation is hence associated with each stage. According to calibrations, the partition is as follows: let i be the current number of iteration without improvement on the incumbent solution and p be the max number of iterations without improvement allowed, such that 0 ≤ i ≤ p and the ILS stops if i = p; the random restart takes effect when 0 ≤ i ≤ p/3; the first shaking is applied when p/3 ≤ i ≤ 2p/3; in the last iterations (2p/3 < i < p), the second shaking is used.

Algorithm 4.7 RestartOrShake(g, i, p)

Input: g = G = (N,

Bi-objective optimization

Many real-world operations research problems cannot be handled by optimizing a single objective. This is especially the case in decision making systems where many criteria are often considered simultaneously. That is why multiobjective optimization is widely addressed in the literature. Reviews and surveys can be found in [START_REF] Chankong | Multiobjective Decision Making: Theory and Methodology[END_REF] Variables: g,g : temporary graph i: current number of iteration without improvement

1: i ← 0 2: g ← Construct(G) 3: g ← VND(g) 4: while i < p do 5:
g ← RestartOrShake(g, i, p)

6: g ← VND(g ) 7:
if fitness(g ) < fitness(g) then 8:

g ← g 9: i ← 0 10: else 11: i ← i + 1 12:
end if 13: end while 14: return fitness(g) optimum since the objectives are often in conflict. An optimal solution for one of the objectives may have a poor quality for other objectives. Furthermore, many solutions that are optimal for different single objectives can be found, but it is hard to say that one is better or worse than another from a general viewpoint. Thus, solving a multiobjective optimization problem is more about finding a set of solutions. The concept has first been proposed by [START_REF] Pareto | Manuale di economia politica. Piccola biblioteca scientifica[END_REF] and the solution set is named as the Pareto-optimal set or Pareto front.

In the literature, solutions on a Pareto front are said to be "noninferior", "nondominated" or "Pareto-optimal". The relation of dominance is well formulated in many studies. For instance, in bi-URND and bi-MRND, given two solutions s 1 and s 2 ,

s 1 dominates s 2 either if (i) f c 1 (s 1 ) < f c 1 (s 2 ) and f c 2 (s 1 ) ≤ f c 2 (s 2 ) or if (ii) f c 1 (s 1 ) ≤ f c 1 (s 2 ) and f c 2 (s 1 ) < f c 2 (s 2 ).
If such a s 1 does not exist, s 2 is nondominated.

Determinist methods for solving multiobjective optimization problems are also well studied, such as the weighting method [START_REF] Zadeh | Optimality and non-scalar-valued performance criteria[END_REF]) and the -constraint method [START_REF] Haimes | On a bicriterion formulation of the problems of integrated system identification and system optimization[END_REF] and [START_REF] Chankong | Multiobjective Decision Making: Theory and Methodology[END_REF]). However, it is often very expensive to find all nondominated solutions of a given problem, especially with a large number of criteria.

Even identifying whether a solution belongs to the Pareto-optimal set is NP-hard. Hence, heuristics should be investigated in order to find good quality Pareto front in a reasonable time. Among others, Evolutionary Algorithm (EA) are intuitive for multiobjective purposes because they rely on populations, similar to finding a set of solutions. Important reviews and investigations are referred to [START_REF] Kalyanmoy | Multi-Objective Optimization Using Evolutionary Algorithms[END_REF] and [START_REF] Zitzler | Multiobjective optimization using evolutionary algorithms -A comparative case study[END_REF].

An -constraint method for bi-URND and bi-MRND

The bi-objective version for URND and MRND models, resp. bi-URND and bi-MRND, are solved to optimality by means of the -constraint method. It is based on the enumeration strategy proposed by [START_REF] Haimes | On a bicriterion formulation of the problems of integrated system identification and system optimization[END_REF]. This method is especially intuitive whenever at least one of the objective functions take values on Z. As a consequence, its value may be turned into a constraint of the problem while the other ones are optimized. This means the (i,j)∈A 1

x ij ≤ κ (4.1)
Every integer value κ ∈ c 2 , c 2 can be investigated using the -constraint method since

c 2 (x) ∈ N.
The same approach is applied for bi-MRND, whereas the objective function (3.21) is turned into the following constraint: 2 ) = c 2 (s 2 ) and c 1 (s * 2 ) ≤ c 1 (s 2 ), is found. Details of this adapted method can be found in Algorithm 4.9.

(i,j,k)∈A 2 x ijk ≤ κ (4.2)

Bi-objective BRKGA adaptation for bi-URND and bi-MRND

BRKGA is originally designed for single-objective combinatorial optimization. Adaptations need to be done for solving bi-URND and bi-MRND. To do so, a solution pool is created in the proposed BRKGA to store solutions. To construct a Pareto front for a given instance, two single-objective BRKGA optimizations are done for the respective c 1 and c 2 objectives.

All solutions found during these two processes are stored in the pool, including intermediate solutions obtained in the repairing procedure mentioned in Subsection 4.2.1. After the two independent minimization procedures, a dominance check is done using all solutions in the pool. Those not dominated by any other are inserted into the Pareto front returned as the result of the bi-criteria optimization. Thus, our BRKGA for the bi-objective version of the problems consists in two calls of the BRKGA, including in each call the predefined number of generations, followed by a merge and a filter on the two sets of solutions.

* c 1 = (c * 1 , c 2 ) ← optimize G for c 1 objective 2: s * c 2 = (c 1 , c * 2 ) ← optimize G for c 2 objective 3: f ← {s * c 1 , s * c 2 } 4: p ← (c * 1 , c 2 ) 5: while c 2 (p) > c * 2 do 6: c 2 ← c 2 (p) 7: p ← min{c 1 (p)|c 2 (p) ≤ c 2 -, p ∈ P } 8:
f ← f ∪ {p} 9: end while 10: return f

Bi-objective ILS adaptation for bi-URND and bi-MRND

Similar to BRKGA, ILS was not originally designed for multi-objective optimization.

In order to deal with both bi-URND and bi-MRND, an Aggregate Objective Function (AOF) of c 1 and c 2 objectives is used in the proposed ILS as presented in Equation (4.3).

Given a solution for URND or MRND, the objective values of c 1 and c 2 are evaluated and normalized by f c 1 (s) and f c 2 (s), respectively. Given a varying parameter α ∈ [0, 1], they are aggregated into one objective value f α (s), which can be used as the evaluation criterion in the components of our ILS. The AOF replaces the evaluation evaluation not only in a bi-criteria optimization, but also when solving single-objective URND and MRND. Running the ILS for several times with different α give a set of nondominated solutions, hence defining an approximation of the Pareto-optimal front. Besides, calling the ILS with α = 1, the objective value of c 2 is ignored and the c 1 objective is minimized; to optimize the c 2 objective, it is

sufficient to set α = 0. min s∈S f α (s) = αf c 1 (s) + (1 -α)f c 2 (s) ∀α ∈ [0, 1] (4.3)
Thus, similar to BRKGA, the bi-objective adaptation of ILS consist in running ILS several times and merging/filtering the sets of solutions.

NSGA-II

EA have been proved to be efficient for solving combinatorial optimization problems.

A (1994). [START_REF] Goldberg | Genetic Algorithms in Search, Optimization and Machine Learning[END_REF] suggests the nondominated sorting based on the ranking mechanism can be integrated in a GA for a multi-objective optimization. At each generation, a nondominance check is first performed on all individuals according to their objective values.

The individuals nondominated by the remainding individuals of the current population are assigned to the current rank (starting from 1) and removed from the current population.

Then, the rest of the population is scanned for another nondominance check. By repeating the process of nondominance check, rank assignment and individual removal, the sorting terminates when all solutions are given a rank.

The Non-dominated Sorting Genetic Algorithm (NSGA) has been hence proposed by [START_REF] Srinivas | Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms[END_REF] (1984). By using a performance measure defined by [START_REF] Deb | Genetic Algorithms in Multimodal Function Optimization[END_REF] for evaluating the distribution of a Pareto front, authors claim that the NSGA performs generally better than the VEGA, except several cases where the sharing parameter is not well set.

However, drawbacks of NSGA have been identified by the community, including the high complexity due to the implementation of the nondominated sorting, the lack of an elitist mechanism and the dependence on the sharing parameter. In [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF], these disadvantages are well explained and an enhanced approach is proposed, named NSGA-II.

This improved method integrates a fast nondominated sorting with a lower complexity. The main idea is, for every solution, to memorize the number of solutions dominating it and to store all the solutions dominated by it. The time complexity is proved to be O(M N 2 ) where M is the number of objectives and N is the population size, but this new approach requires a slightly higher storage space of O(N 2 ). NSGA-II also replaces the sharing function by a crowded-comparison operator which guarantees a good solution distribution on the Pareto front as well. Instead of sharing the fitness, a crowding distance is computed for every solution to indicate whether it is located in a crowded region of the current rank or not.

The selection of the GA is then guided by comparing the crowding distances in a way that solutions in less crowded areas are preferred. In the literature, NSGA-II is compared to other two MOEA on four different problems and it has generally a better performance.

Computational experiments and numerical results

Four computational experiments have been performed using the proposed metaheuristics so as to test their performance in terms of the quality of the solutions and the processing

Parameter tuning

A tuning phase is essential before getting into the experiments in order to figure out good settings for the proposed metaheuristics. In every calibration experiment, the worst, the best and the average solution values and average running time in seconds are used as performance indicators. Table 4.3 reports all parameters tested in the calibration experiments. For each method and each configuration, one parameter varies and the others were fixed. In BRKGA,

the key parameters to be tuned are the seed of the random number generator (SD B ), the multiplier of the number of nodes (R B ) used to deduce the population size, the maximal number of generations (I B ) and the number of generations without profit (J B ). In ILS, the tuning is performed on the seed of the random generator (SD I ) and the number of iterations without profit (J I ). Note that, since ILS relies on α variation for bi-objective optimization, the pace of variation (∆ I ) needs also to be tuned. In NSGA-II, the settings concern the seed of the random number generator (SD N ), the multiplier of the number of nodes (R N ) used to deduce the population size, the maximal number of generations (I N ), the probability of Tests are launched on a set of samples chosen from the generated instances detailed previously, including 6 instances: 3x3-b1, 4x4-b2, 5x5-b4, 3x3-b2-25, 4x4-b1-75 and 5x5-b1-50. The strategy for testing a parameter is similar to a unidimensional optimization, that is varying one parameter at a time among several predefined possible values with other parameters fixed. Then, the value with better results are used to fix this parameter and the process is repeated on another parameter until a so far best settings is determined. In this study, 3 possible values are chosen for every parameter reported in that are related to multigraph instances referred in Tables 3.2 and 4.2 (also with the number of nodes less thant 50). In order to compare the results in an intuitive way, the numerical results for solving URND and MRND models on CPLEX solver are copied from respective tables reported in Section 3.5, keeping the defined notation of columns. In addition, for both heuristics (BRKGA and ILS), columns "c 1 ", "c 2 " and "t(s)" provide respectively the total Instance Settings SD I = 2,J I = 6 SD I = 4,J I = 6 SD I = 8,J I = 6 due to the memory limit, whereas the two metaheuristics could finish the computation on all the instances. We can observe that, in c 1 optimization, BRKGA found better solutions than ILS on 3 out of 4 instances and ILS performs better on the other instance. When minimizing c 2 , the two methods resulted in similar objective values for 3 out of 4 instances, while ILS found a solution with a better c 2 value than BRKGA in the other instance.

c 1 * c 2 t(s) δ c1 % c 1 * c 2 t(s) δ c1 % c 1 * c 2 t(s) δ c1 % 3x3-
As for time consumption, BRKGA and ILS have a much better performance than CPLEX in the harder problem c 1 . CPLEX optimizes c 2 much more quickly than c 1 since the former is a polynomial problem while the latter is NP-hard. It can even solve instances with up to 36 nodes (6x6 instances) when minimizing c 2 while c 1 cannot be optimized in 2h limit.

Comparing the two heuristics, the running time is generally in the same scale with a slight difference in some instances. ILS is less time-consuming than BRKGA in c 1 minimization on a number of instances and it is not too sensitive to instance size. This is due to the fact that ILS addresses only one solution per iteration. However, BRKGA solved the problems for c 2 globally faster than ILS (see Table 4.8), because the local search operators in ILS tend to reverse arcs' direction, which is hard to control and does not comply with the arc reversals minimization. Thus, a post-processing is added to ILS in order to reverse back some reversed arcs and to reduce the value of c 2 for URND. Tests were also carried out using the strategy of the time-to-target plot (tttplot), proposed by [START_REF] Aiex | Probability Distribution of Solution Time in GRASP: An Experimental Investigation[END_REF] and [START_REF] Aiex | TTT plots: a perl program to create time-to-target plots[END_REF], in order to compare the robustness of the proposed metaheuristics. The idea of tttplots is to compare the ability of the methods to obtain a certain target value following 200 runs with different random seeds. In addition, the selected target value should not be too easy nor too difficult to reach. Thus, the selection of target values is done so as to allow conclusions in these experiments. Here, for each instance (Table 3.1 for URND and 3.2 for MRND), we fixed a small deviation from the optimum value to obtain the target values. The axes x and y indicate respectively the running time and the probability to reach the target value. For each method, the more the curve is straight, the higher probability the method has to reach rapidly the target value. Example plots obtained by minimizing c 1 objective for URND are illustrated in Figure 4.8. The instances from Table 3 the same number of nodes, it seems that the problems are getting easier for CPLEX since it tends to set the bi-direction configuration for two arcs between a pair of nodes. However, the more multiple arcs an instance has, the higher the time consumed by the two heuristics.

They seem to be sensitive to the increase of the arc number. There is little gap between BRKGA and ILS in terms of computational time in c 1 minimization, but ILS is slightly more time-consuming than BRKGA when minimizing c 2 on most of the instances. The tttplots presented in Figure 4.9 illustrate the behavior of the two metaheuristics for MRND. Instances from Table 3.2 are used in these experiments. Results indicate that, on most of the instances, BRKGA performs better than ILS, while ILS leads BRKGA slightly on a few instances, for instance as shown in Figure 4.9-(c).

Tables 4.11 and 4.12 refer to the instances from Table 4.1 with the number of nodes greater than 50 (8x8, 9x9, 10x10, 11x11 and 12x12 instances). Moreover, Tables 4.13 and4.14 refer to the instances from Table 4.2 with the number of nodes greater than 50 (8x8 and 9x9 instances). These instances cannot be solved by CPLEX due to memory issues.

Hence, experiments were done using BRKGA and ILS. Results of c 1 optimization for URND reported in Table 4.11 indicate that ILS performs much better than BRKGA in terms of solution quality, since BRKGA found lower or identical objective values than ILS on only 4 out of 20 instances, whereas the processing time is very similar for both methods. When minimizing c 2 , much more time is elapsed by ILS to find better or equal objective values than BRKGA on 12 out of 20 instances, as presented in Table 4.12. In addition, ILS has also a better solutions quality than BRKGA on multigraph instances, but its time consumption is even higher, either for optimizing c 1 or c 2 . Details are referred to Tables 4.13 and 4.14.

In general, ILS performs better on most of the instances, while BRKGA takes the lead on a few instances for c 2 objective or for MRND.

Bi-objective optimization

As previously claimed, BRKGA and ILS were not initially designed for multi-objective Tables 4.15 and 4.16 report respectively the results of bi-URND and bi-MRND obtained on the instances with up to 25 nodes from Tables 3.1 and 3.2. Aside from the notations defined in previous tables, the columns "Q", "HV " and "SP " present respectively the number of solutions, the HV, a well-known performance measure for Pareto front approximation

Zitzler & Thiele (1998) (the higher the better), and the spacing proposed by [START_REF] Veldhuizen | On measuring multiobjective evolutionary algorithm performance[END_REF] and [START_REF] Zitzler | Performance assessment of multiobjective optimizers: an analysis and review[END_REF] (the lower the better) which allows to analyze the distribution of the given Pareto front. However, due to the memory limit, the -constraint method cannot handle instances larger than 5x5. Thus, for every instance with the number of nodes greater than 25, nondominated solutions among the solutions found by the three metaheuristics are grouped to construct a set of Best Known Solutions (BKS), denoted "BKS" in Tables 4.17 for bi-URND on 3x3, 4x4 and 5x5 instances. This is confirmed by the tiny optimality gap on HV (comparing with the Pareto-optimal fronts constructed by the -constraint method) on 9 out of 10 instances. The spacing values seem also reasonable for a non-evolutionary metaheuristic without any functions that ensure the solutions distribution. Since a linear aggregation of the two objective functions is applied in ILS, most of its solutions found on the fronts are supported, whereas a few non-supported solutions can also be reported thanks to the post-processing integrated in the method. For the other two metaheuristics, BRKGA and NSGA-II, they can construct Pareto fronts with more solutions than ILS because of the use of populations, especially on 5x5 instances. The quality of their fronts are also good but they are slightly worse than ILS in general. Moreover, NSGA-II allows to construct Pareto fronts with a very well spread on these instances. Starting from 6x6 instances, the -constraint method ran out of time due to too many variables and constraints in the mathematical model. All three metaheuristics can approximate the Pareto-optimal fronts in a reasonable amount of time. Figure 4.10 illustrates the Pareto fronts found by these four methods on the 5x5 instance with 1 disruption, respectively.

Moreover, Table 4.16 reports the results for bi-MRND on 3x3, 4x4 and 5x5 instances, all Regarding the bi-URND on 6x6, 7x7 and 8x8 instances, results of the three metaheuristics are shown in Table 4.17. BRKGA and NSGA-II have a globally similar performance comparing to BKS. They can find good quality fronts with a large quantity of solutions.

Besides, the spread performance of these two methods are very well and generally better than ILS. In particular, NSGA-II consumes less time than the other two methods. On the other hand, the Pareto fronts found by ILS are very close to BKS on these instances but with minor gaps in terms of solution numbers. However, for bi-MRND with results reported in Table 4.18, ILS starts to struggle when the problem size is getting larger, particularly on the 8 instances of 8x8. Sometimes, it spends more than two hours to construct a Pareto front while BRKGA and NSGA-II can finish most of the tasks in less than one hour. In terms of the front quality, ILS still has a significant lead in front of the other two metaheuristics. a very comparable quality of fronts to BKS. However, the drawback of a high running time is getting more significant, compared to the other two metaheuristics. BRKGA has a good performance on several instances such as 6x6-b1-100, 6x6-b2-100 and 7x7-b2-100. This particularly refers to the instances with a high percentage of multiple arcs. NSGA-II still runs with a stable performance by finding good quality Pareto fronts in a very short time.

By extending its processing duration, there may be ample room for improvement. By testing the proposed methods on this kind of large generated instances, it can hence be expected that real (small or medium scale) networks can be handled to address both bi-URND and bi-MRND. In terms of the solutions distribution, BRKGA had better spacing on 19 out of 24 instances than ILS and NSGA-II, while ILS also found 3 fronts out of 24 instances that are better distributed than the other two methods. NSGA-II performs surprisingly worse than BRKGA and ILS using this metric on these instances. Figure 4.13 illustrates the fronts found by the three methods on the 8x8 instance with 100% multi-arcs and 1 disruption.

An application to a real urban network

In order to take a step into the real context of urban network management, we also extracted real geographical data (from OSM) for the urban network of Troyes1 . Several instances are then created onto this basis that can hence be tested by the proposed metaheuristics for both (bi-)URND and (bi-)MRND. Disruptions are selected on a random basis but also in a way to ensure that the resulting graph allows strong orientations to be computed, i.e. does not have bridges. We consider that there is a travel demand for every O-D pair. Thus, there should be a path between every pair of nodes. Experiments were performed on the same machine described at the beginning of this section.

The original dataset from OSM consists of 4261 nodes and 614 ways including redundant The metaheuristics constructed high quality fronts. Among them, BRKGA has the best performance. However, unlike the behavior observed on the results for bi-MRND instances, nodes and 40 arcs. For MRND, its limit is around 36 nodes and 120 arcs. On the other hand, the metaheuristics are able to solve instances with more nodes and arcs. Comparing to BRKGA, ILS seems more robust for both URND and MRND, even when the number of disruptions increases.

Conclusion

As for bi-objective optimization, computational tests are performed on grid instances with up to 64 nodes and 112 arcs for bi-URND and up to 64 nodes and 224 arcs for bi-MRND.

The four methods are also applied on instances built from the real road network of Troyes.

Results show that ILS is able to produce high quality Pareto fronts in both bi-URND and bi-MRND. In addition, it is less dependent on the network configuration, either the topology Chapter 5

Application : Optimal traffic Deviation System

Urban traffic management is a complicated issue in the real world due to the growing demand of travels and the insufficient capacity of networks, as stated earlier in this document.

When disruptions happen on a critical link of a road network, it is important for traffic manager to react rapidly and adequately in order to maintain the circulation functionning, which may impact concerned areas. Based on the road network of Troyes city in France, there are over 8000 planned disruptions in 2014, nearly 22 per day. Managing this network is even more difficult because the downtown city is a historical center where roads have a low capacity and are almost one-way. A great challenge is to choose alternate paths for every disruption. Since drivers willing to pass a disrupted road are sent to another road which has its original traffic load. Thus, a bad choice may cause congestion or an uncomfortable experience of the drivers. Therefore, ODS is designed to help the decision-making of traffic managers from different viewpoints and in a short time. Under the meta-project TOAST, A functional prototype is firstly designed to justify the idea and workflow and the system in production is then developed oriented to professional uses. Major features are mostly accomplished while fine tuning and maintenance are still required in order to deliver progressively the real product. As the main functionality of ODS, the deviations are computed according to one or more optimization criteria. The following objectives are focused: the bypass distance, the number of road sections and the number of traffic signals.

These objectives are handled individually. A multi-criteria schema can also be imagined, whereas it is not the priority in this stage. Currently, a number of modules are already working: (i) an interactive customized GIS based on the network of Troyes; (ii) a GUI;

(iii) computing deviations for a given blockage minimizing either the travel distance, the number of employed road segments or the number of traffic signals; (iv) network information administration and adjustment, especially the positions of traffic signals and traffic calming features; and (v) monthly monitoring of disruptions.

Requirements analysis

As a decision-support system, ODS is supposed to help decision makers (probably a hierarchy team with leaders, managers and operators, etc.) in daily tasks of disruptions management. Its key feature is the automatic computation of deviations while users can always get involved by manually create and edit deviations. The system is able to retrieve the planned blocking events from the given databases of a city hall, while unpredictable disruptions such as traffic accidents can also be manually added to the system. Moreover, information is presented to users in an intuitive way, including the blocking events, deviations and network elements, such that a user can really focus on different aspect of making the decision instead of searching different information everywhere in the system. Regarding the engineering, ODS is developed and maintained under several mature application standards in the Web context following the Scrum for the agile software development.

Functional requirements

The functional requirements of ODS concern mostly the features proposed to users for managing blocking events as well as the network information. They may involve every layer in the software design: the presentation to end users, application and services, business logic and data persistence. The end users of ODS are decision makers in general, referred as "USER" in this report. Moreover, there may be different user roles, such as traffic engineers (non-administrator) and administrator. They have specific needs when using ODS. Hence, the requirements are also addressed from their viewpoints. Considering the background of the collaborations and to concentrate on the key features of ODS, several requirements are based on the existing services of the road network of Troyes.

• ODS must be able to connect to the disruption databases of the city hall of Troyes, to retrieve the information of blocking events and corresponding contacts (such as a road maintenance company, a removers firm, the organization of a parade, etc.).

• ODS must be able to store and update the data gotten from the disruption database.

• ODS must be able to visualize disruptions and deviations on an intuitive map of the road network of Troyes.

• USER must be able to create unpredictable disruptions by offering its label, starting and ending dates, a contact (if exists) and the blocked road segments.

• USER must be able to edit a disruption by modifying its contact and ending date (i.e. to extend its duration).

• USER must be able to launch an automatic computation of deviations for every disruption.

• USER must be able to edit a deviation by changing its path.

• USER must be able to create deviations for a disruption by indicating detour paths.

• Non-administrator USER must be able to select deviation(s) for a disruption and submit to administrator.

• Administrator USER must be able to validate or reject the deviation selection for a disruption.

• ODS must be able to consider the strong connectivity of the network impacted by disruptions and to propose adapted solutions for different types of vehicle: car and truck (bus is another type but it is not considered at this moment due to possible complex changes of bus stops).

• ODS can propose deviations with insufficient capacity, but a warning must be highlighted to USER.

• ODS must be able to compute optimal deviations with respect to several criteria: the minimization of the distance, the number of segments and the number of traffic signals (more criteria are also identified and planned for future stages).

• ODS must be able to classify disruptions according to their status: (i) not handled, (ii) handled but not yet validated, (iii) handled but rejected and (iv) validated.

• Within a calendar, ODS must be able to illustrated the unhandled disruptions according to their starting dates, so that USER shall able to have a vision of the tasks.

• ODS must be able to retrieve and store the network information from OpenStreetMap, such as the locations of traffic signals, stop signs and speed reducers.

• USER must be able to monitor the locations of traffic signals, stop signs and speed reducers.

• USER must be able to add to or remove from ODS a traffic signal, a stop sign or a speed reducer by offering the location on the map.

• ODS must be able to perform a qualitative analysis of deviations according to the network information, for instance in terms of air pollution, noise or driving experience.

• ODS should store user activity data and perform statistical analysis (probably by some machine learning approaches) in order to enhance the strategies for computing deviations.

• ODS should connect to the database of Gertrude's system, deployed in the traffic control center of Troyes, in order to obtain real-time traffic flow data. In the case of addressing unpredictable disruptions, these data are especially important so as to take into account the real-time network status.

Nonfunctional requirements

The analysis of nonfunctional requirements is mainly divided into five parts: the usability, reliability, performance, supportability and interfaces. The main purpose is to clarify the needs of the User Experience (UX) and different aspects in the development, deployment and maintenance of ODS.

Usability

• ODS must be able to synchronize regularly the newly created blocking events from remote databases.

• USER must be able to synchronize the newly created disruptions on demand.

• ODS must be able to indicate the starting and ending point of deviations, with respective brief descriptions of the paths.

• ODS must be able to show all the performance values, either quantitative or qualitative, of each deviation, in order that USER has an intuitive vision.

• ODS must be able to warn whenever a deviation has an insufficient capacity.

• Administrator USER must be able to compare selected deviations for a disruption in an intuitive way, for instance a polar graph that combines the performance values of every deviations.

• USER must be able to switch the look-and-feel of the map between a "day" theme and a "night" theme, like what does a GPS navigation device.

• ODS must provide a user manual.

Reliability

• Automatic unit tests must be carried out for the components of the computing core of ODS with a code coverage ≥ 80%.

• Automatic integration tests must be carried out for the modules of Web services of ODS.

Performance

• Data synchronization must not block the main process of ODS.

• Automatic deviation computation must be performed in a reasonable time.

• Web client of ODS should be responsive to different size of viewport.

• USER must have a smooth loading view whenever a relatively long procedure is executed.

Supportability

• Web client of ODS must support modern browsers (of recent versions) as many as possible.

• Web services of ODS must be independent to operating systems and able to deploy on any platform with a Docker container support.

Interfaces

• ODS must have an independent module of data access able to make connections to different heterogeneous databases or services of traffic information.

• Web services of ODS must be able to support mobile applications under authorization.

ODS architecture

Architecture is the high level coordination of every single part of the system, which shows clearly the goals of the system and provides guidelines to the implementation. On one hand, it should classify the modules considering the current requirements such that the features are divided into small parts of functionality instead of being centralized in some domains. This decentralization is already a mature concept in software engineering that helps to simplify the software development and maintenance as well as the project management. On the other hand, the architecture of a software should also anticipate the potential extensions in the future. In practice, choosing a balanced vision is always challenging. If the architecture includes too many needs that are not important at the beginning of the design, it will make the implementation much more complicated because one should consider a lot when developing a small function and cannot focus on key elements. In turn, it is hard to apply any concept of agile project management because every development cycle would take a long time and any delivery cannot be ensured. It is called an over-design or over-engineering. If the future updates are not well foreseen in the architecture, problems may arise when adding new features since there might be some concerned functionality which would have been but was not extracted to an independent component or module. This will surely increase the amount of work and may involve an additional refactoring which is often difficult and expensive.

The architecture of ODS concentrates on the major features that can prove its concept and provides (at this moment) the extensibility only on computing solvers and data sources. ODS is divided into four layers. The presentation layer comprises generally, just as its name implies, all the modules concerning the User Interface (UI) where ODS interacts with the end users. The logic layer consists of different deviation computing cores. It is related to the presentation layer via Web services in the service layer to collect required data from user, to performance the computation and to return the results shown to user. Data modules are classified in the data access layer. They are in charge of collecting data inside or outside ODS, converting the data when needed, storing the data and abstracting the fundamental data manipulations such as to create, read, update and delete (CRUD) data. This layer may provide data supports to the solvers for computation or directly to the UI for visualization via Web services.

Beyond these four layers of functional modules, there are three supplementary elements: the activity metadata is composed mainly by the log across the four basic layers for debugging and tuning uses; the security configuration protects the Web services and confidential data from being abused; the tests ensures the functioning of the modules of ODS which play a In addition, the architecture of ODS considers the connection to heterogeneous systems, which are mostly drivers data sources at this first stage of design. As described previously, ODS needs network data from OpenStreetMap and disruption data from the databases of Troyes's city hall. To complete the geographical data, especially the data of addresses, it is also possible to integrate the databases of IGN (Institut National de l'information Géographique et forestière or Information Grandeur Nature), a hyper organization of geographical information of France. Moreover, the qualitative analysis of deviations may require additional information, for instance, the emission of carbon dioxide of vehicles according to the type (vehicle producer and engine model), the distribution and usage of different types of vehicles in the city, etc.

Note that implementation details are not presented in the architecture, which will be described in the next three subsections regarding the human-computer interaction, database and computing core. Technologies and practices applied in the development will be discussed.

Human Computer Interactions

HCI investigates in general the way that people exchange information with artifacts on computers in order to collect required information from users for some computational purposes and to show the results back to users. From a software's point of view, HCI is mainly represented by UI and UX. The former is a concrete field about what and how things are presented to users, while the latter focuses on making UI intuitive and facilitating the usage of the product. All the concerns should concentrate on making the software simple to use so that users can easily understand what is proposed to solve their problems.

As for ODS, its end users are mostly urban traffic managers, who are supposed to have a professional background of the road network and disruption management while probably being confused by theory of graph and algorithms to compute alternate paths, to check the strong connectivity or to calculate the CO 2 emission. Thus, UI developers should centralize most of the input and output operations on a map view such that users can have a clear vision on their problems and the proposed solutions. There are four major aspects to address HCI of ODS:

1. General layout and feature organization: to study and propose the appropriate workflow.

2. Cartography: to integrate an interactive view of OSM.

3. UI element: to design the logo, icon set, color scheme and fonts. 4. Visualization: to carry out the methods for showing information such as disruptions, deviations and traffic elements.

General layout

According to the requirements related to the interaction between users and ODS, a preliminary study is done by designing some conceptual screens of the GUI on mockups.

It is proposed to a few target users in PC-Régulation of Troyes helping to validate the general layout regarding their antecedent workflow of disruption management. As the base of HCI which should be respected during implementation, the mockups are also confirmed by concerning actors of ODS comprising the developers team and the project supervisors.

Figure 5.2 is the designed home page of ODS, on which four major activities are classified: to create deviations, to supervise disruptions and their deviations, to configuer the application (settings) and to consult the user manual. A sidebar of shortcuts is also considered and settled on the left of the screen. As a UX consideration, it can be folded up Figure 5.2: Mockup of home screen with organization of major activities to save the space for the activity view and allows from deep inside an activity to navigate to another activity. Moreover, a block of summaries is also planned on bottom right of this main screen, in order for multiple users to have a quick preview of actions performed by colleagues and of urgent disruptions requiring to be handled rapidly.

Besides, the general layout of deviation management screen is also proposed, as shown in Figure 5.3. The main feature is the map view with markers indicating the locations of the ongoing blocking events which have already been handled with validated deviations. There is also a list of details to the right with, for each disruption, the street name it concerns and a brief summary of its deviations. Details are shown when selecting a disruption either from the map or from the list.

Cartography

As the most important component of ODS, the cartography is used to exchange a large amount of information with users related to disruptions, deviations and network elements.

It is associated with not only a map view on UI, but also the underlying network data for computational purposes. The current cartography solution in ODS is based on OSM since it is an open source GIS having a stable database with public access and a integration-friendly ecosystem. It also serves a Web application with a number of features such as searching a place and routing between several locations. In this application, the map tiles technology Earth can be divided into small images of a high resolution that can be loaded in parallel.

Besides, only necessary tiles are loaded depending on the current view spot of the user and on the level of zoom in order to avoid wasting time and memory. Furthermore, it is possible to generate our own tiles using the Python library MBUtil by providing decoration scripts in CartoCSS on Shapefiles of network information. These tiles can hence be distributed within ODS for all types of uses. However, unlike the other famous GIS Google Maps, OSM does not have an official support for a ready-to-use map component (Web and mobile widgets are available for Google Maps). To integrate a map view similar to the application, one can use the third-party Javascript library called Leaflet.js which support the dynamic loading of map tiles. The design of the first ODS logo, as shown in Figure 5.6, is inspired by traffic cones which are often placed in the area of blocking road works. The main illustration is a closed line draws the stroke of a traffic cone, which can also represent a blocked street to the left and its deviation to the right (which tends sometimes to be complicated with many curves in downtown cities).

The color scheme (see Figure 5.7) is established with a special care to avoid conflicting with the themes of the cartography. Also with an additional consideration, two free fonts (see Figure 5.8), OpenSans and Vollkorn are selected mainly for their elegance and adaptability across platforms.

Visualization

The visualization is an efficient tool in HCI. The principle is to present information on the GUI in a simple and intuitive way so that users can understand what is requested and what is responded by the software. In a complex system, the visualization is not an easy task since there is often a huge amount of data to be shown at a time.

With the aforementioned technologies of the cartography, the map view of ODS is able to highlight paths with custom decorations, such as the color, the line style and the line width.

Figure 5.9 illustrates the screen visualizing a deviation of a blockage. The track of the disruption is drawn by dotted lines in red color. The path of the deviation is presented with green lines and two markers to indicate its starting and ending intersections. Text description is also available for every deviation route. In addition, all deviations for the current blockage is listed below the map view with of each a summary of performance criteria: the dedicated vehicle type, whether it has an insufficient capacity, the distance, the number of intersections and the number of traffic signals. Switching deviations in this list triggers rendering of its path on the map.

As determined in the requirement analysis, the administrator should validate deviations selected by agents of traffic management. This feature also involves the visualization since users need to compare relevant deviations for decision making. According to the current criteria taken into account: the distance, the number of intersections and the number of traffic signals, a radar chart in three scales is presented in such a way that the pros and cons of every deviation can be intuitively perceived, as shown in Figure 5.10. Moreover, a score between (0, 1) is calculated for each deviation by aggregating the three normalized objective values. It can also be a comparison measure of the global performance of each deviation. The visualization concerns the network elements as well, especially for showing the traffic signals, the stop signs and the speed bumps. Originally, these objects are used for qualitative analysis of deviations. Meanwhile, since the information of locations are collected from OSM, some locations may be incorrect or even missing. Thus, network managers are also involved not only to have a global vision of the locations but also to maintain the data. They can add or delete a traffic element just by clicks on the interactive map.

Database

The goal of ODS database is to store the network information, the disruptions and the computational results (deviations). Since some of these data are obtained from heterogeneous systems, their structure should be adapted especially for the uses in the computing core.

The geographical network data of Troyes are collected from OSM. They are stored in the database for the visualization use in HCI. Furthermore, OSM also provides additional network information, such as street names, the speed limit and traffic signals, which are useful for ODS. However, the data objects "Node" and "Way" cannot be directly converted into graph structures for computing purposes. Hence, a pre-processing module has been developed in order to cut ways into arcs and merge transitive nodes. Then, the resulting data are stored separately.

Since ODS is connected to the database GEODP of the Troyes city hall, the disruption data can be obtained. In this database, the geographical information is not specified for disruptions. Instead, the impacted area is represented by addresses. Thus, ODS needs to identify the geolocation of every disruption in order to fit computational requirements. To do so, another module is developed using the Jaro-Winkler distance [START_REF] Winkler | String Comparator Metrics and Enhanced Decision Rules in the Fellegi-Sunter Model of Record Linkage[END_REF]) to analyze the text similarity [START_REF] Gomaa | A survey of text similarity approaches[END_REF]) between the addresses and street names in the data from OSM.

With the analysis and specifications, the structure of ODS database is conceived as illustrated in Figure 5.12. The diagram is constructed using the classical entity-relationship model. Objects are classified into three domains: Figure 5.12: ODS database schema Another long term issue is the data update from heterogeneous systems. Updating disruptions from the database of GEODP is not too problematic because the major change of the database is adding new disruptions and a regular polling from ODS can accomplish the task. However, since OSM is open source, contributions from its community may change the network. Especially when a node is deleted, it is not very obvious to adapt our database.

Till the moment of redaction, the problem is yet left to be handled and searching an update solution is still in progress.

Computing core

The computing core of ODS supports the major functionality for proposing deviations to decision makers. By the aforementioned system architecture, it consists of various solvers and belongs to the business layer. The major component is the network solver which receives disruptions information and returns several deviations combining the context of the given network. It is designed with a loose external coupling to other modules of ODS, especially in the routines for the deviation computation. Required data are always passed through public interfaces and the calculation works on any formatted data. Thus, the solver is highly reusable when the network context changes and its side effect to other features of ODS is minimized.

Given the graph modeling the concerned network and disruptions information, the network solver applies the algorithms studied in the scientific part of this thesis. They are adapted to the optimization objectives defined for ODS: the detour distance, the number of sections used in the deviation and the number of traffic signals. Hence, the algorithms use different arc costs corresponding to these criteria. Moreover, for each disruption, an origin node and a destination node are also given to the network solver in order to simplify the calculation. Besides, specific constraints for different vehicle types should be taken into account by the solver, for instance the height, the weight and the angle of turning.

Variations and extensions of the algorithms are thus considered, whereas their application is still in progress.

By the way, a multi-layer graph model can also be applied to handle the specific arc constraints of distinct vehicle types. A dedicated subgraph can be created for each vehicle type with only the arcs that it is allowed. Hence, algorithms can use different layers of the graph to calculate deviations destined to different vehicle types. However, there are several problems left to be addressed for this idea, for instance the storage and subgraphs identification. Therefore, this feature is still conceptional.

The concepts explained in this subsection mainly concern the network solver for the deviation computation. Other solvers are also planned to be developed and to be integrated gradually in the computing core as plug-ins or post-processing modules, for instance the solver to compute pollution indicators for a given deviation. As the system grows, there is a strong possibility that the requirements change. The architecture will hence evolve in order to adapt to the needs, especially on the business layer.

Addressing technological gaps

One major technical challenge concerning the ODS system is to obtain accurate traffic data, especially to reproduce the real flow of vehicles. With the technological evolution since last decades, sensors become the most important weapon to collect real-time information from a city, especially on an urban road network. However, those data may not be available in every network. In fact, some cities have a lot of modern sensors that can cover almost every single intersection of the network. They allows not only to count the number of vehicles on different road sections by different timescale, but also to track the path of every vehicle or to deduce the congestion level at any given intersection, as it is the case in Beijing, China.

Another example is Lyon, France, with a large number of sensors for vehicle counting, weather detection and pollution measurement. Troyes also possesses its own digital sensor network for traffic control purposes, but it covers only some of the critical intersections of the downtown city and it is not possible to access any traffic data of suburbs that contains important links as well. This is due to financial or environmental limits (insufficient investment or lack of public area). Thus, constraints and criteria based on real flow models are difficult to integrate in ODS for this moment.

Another issue is the consideration of the public infrastructure. There are many blockages in critical bi-direction road sections where detouring the traffic can be very complicated and can change driver experience a lot. According to the workflow of the manual design of deviations, alternating traffic is often a solution facing this situation. Usually, it is employed when one direction is completely blocked and drivers in the two directions share the other direction left open. In the original idea before the development of ODS, it is planned to be taken into account to propose deviations. However, it is yet difficult for the network solver to determine whether alternating traffic can be applied and to choose the positions to place temporary signals. Furthermore, disruptions can impact the public transport system on urban transportation networks such as bus and tram. Sometimes, bus lines have to be periodically modified. In this case, deviation managers should work with public transport engineers in order to figure out the modified routes and the places of additional bus stops to deploy. The implementation of such a process automated by ODS needs also a great effort, since it requires investigations on the modeling, algorithms and infrastructural information systems.

Last but not least, there is an important technological gap concerns the congestion. Some studies have tried to anticipate congestion by using prediction based models, the traffic simulation, mathematical equilibrium strategies, etc. (Institut national de la statistique et des études économiques (France) & Berthier (1998) and [START_REF] Buisson | Comprendre le trafic routier. Méthodes et calculs[END_REF]). However, the congestion is still a phenomenon for further researches since some obvious solutions can produce even more congestion. We can mention the paradox of [START_REF] Braess | Über ein Paradoxon aus der Verkehrsplanung[END_REF] in which a route is added to a network infrastructure and it generates more congestion, instead of improving the traffic. For now, we are planning to bypass this drawback by doing simulations of traffic flow to take into account different scenarios.

Chapter 6

Concluding remarks and future works

In the context of disruption management, we investigate the reconfiguration of urban road networks as the first part of this thesis. With the development of urban areas all over the world, this problem becomes critical since there are growing concerns in various domains, for instance the increasing traffic load facing the insufficient network capacity. The situation is more complex when there are disruptions on the network. They often interrupt the traffic at a certain level or even break the paths between some locations. Modification of the network layout by reversing arc directions is hence taken into account in this work as the breakthrough to the problem, since it may overcome the issue of broken paths and eventually reduce travel costs of drivers. Therefore, RND is properly defined based on the reversals of the road direction to rearrange a given transportation network. Depending on network properties, it is divided into two problems. URND handles particularly one-way road networks which is often the case in historical centers, and MRND can treats general networks mixing one-way and two-way streets. With respect to the concerned criteria, the total distance of all O-D pairs and the number of arc reversals, both single-and bi-objective optimization are considered (resp. bi-URND and bi-MRND).

This thesis involves many related fields of research such as the graph theory in terms of orientation, the arc reversals and the NDP, for which relevant studies have been carried out for decades resulting in the respective theories and methods. Using graphs to model road network, bi-objective mathematical formulations are developed as the starting point to address these two problems by introducing the constraints of disruptions and reversals to classical multi-flow based models. In addition, 2-directed multigraph is introduced as an efficient way to simplify the multigraphs in bi-MRND. By applying an -constraint method, these models are able to handle the problems in bi-objective version. Next, two metaheuristics, a BRKGA and an ILS are proposed to handle single-objective URND and MRND together with a DFS-based orientation heuristic. Following their functionality, they can find high quality solutions in a very short time. Adaptations are then introduced in both methods in order to address bi-URND and bi-MRND. Moreover, a classical bi-objective framework NSGA-II is also used with respect to the specifications of bi-URND and bi-MRND.

Experiments were performed using simulated and realistic instances in order to validate the models and the proposed metaheuristics. Numerical results indicate that the models are able to solve the problems (using the commercial solver CPLEX) on small sized instances and on a few medium sized instances with up to 36 nodes and 60 arcs, whereas it is difficult for them to confront with larger instances. The metaheuristics have generally good performance and they can handle large instances with up to (not limited) 144 nodes and 264 arcs in URND, and with up to (not limited) 81 nodes and 288 arcs in MRND. According to the numerical results, ILS performs globally better than BRKGA for URND, whereas BRKGA works better than ILS for MRND. Moreover, an encouraging result was obtained with the ILS adapted for bi-URND and bi-MRND, since it performs better than the well known bi-objective metaheuristic NSGA-II. Thus, this idea could be applied for other problems in order to check if such results also verify. A number of possibilities are opened for future works. Firstly, a polynomial time algorithm to minimize the number of arc reversals is still an open issue. Finding such an algorithm may help to handle bi-URND and bi-MRND faster. Then, there is still room to improve the performance of the metaheuristics, especially on the computation time of ILS. Also, the solution quality of BRKGA and NSGA-II might be enhanced by allowing more generations, while it involves much deeper tuning. In addition, more realistic constraints and criteria are being studied for the application on general networks, such as the traffic capacity, multi-modal flows and the scheduling of planned disruptions, in order to better approximate the real contexts of RND problems. As for ODS, feature tests should be organized in the traffic control center of Troyes, in order to validate the functionality of its first version. Several aspects can also be considered in the future, such as to develop other algorithms with different criteria (travel time, gaz emission, etc.), to integrate more data sources, to address real-time traffic load and to explore a machine learning procedure taking into account the activities of traffic managers, so as to improve the computation of deviations.

Liste des contributions

Les publications réalisée au cours de la thèse sont listées ci-dessous. En particulier, ODS a été classé 13 ème parmi 107 projets européens dans la compétition étudiante de TRAVISION 2016. De plus, le projet TOAST a été classé à la seconde place du Prix Européen d'Innovation Smart Cities 2017.

• Yipeng Huang, Andréa Cynthia Santos, Christophe Duhamel, Model and methods to address road network problems with disruptions and an application to urban contexts.

Submitted to an international journal with impact factor. 2018.

Congrès internationaux avec actes indexés

(i) f c 1 (s 1 ) < f c 1 (s 2 ) et f c 2 (s 1 ) ≤ f c 2 (s 2 ); (ii) f c 1 (s 1 ) ≤ f c 1 (s 2 ) et f c 2 (s 1 ) < f c 2 (s 2 ).

Méthode -constraint

La méthode -constraint est une méthode exacte pour construire le front de Pareto optimal, proposée par [START_REF] Haimes | On a bicriterion formulation of the problems of integrated system identification and system optimization[END_REF]. Elle s'applique particulièrement bien aux problèmes dont au moins un des critères est défini sur Z. Pour l'optimisation bi-critère, le principe est de transformer un critère entier en une contrainte tout en optimisant l'autre objectif. Progressivement, cette contrainte est modifiée par une solution trouvée et l'optimisation continue jusqu'au moment où toutes les solutions possibles ont été générées.

Le front de Pareto se construit ainsi par l'identification itérative de ces solutions.

Pour bi-URND et bi-MRND, l'objectif c 2 prend des valeurs entières non-négatives. Il peut ainsi être transformé en une contrainte :

(i,j)∈A

x ij ≤ κ.

(A.11) D'où, κ prend initialement la valeur c 2 de la solution optimale pour la minimisation de c 1 .

La contrainte s'actualise par la nouvelle solution calculée et ainsi de suite.

  (iv) network information administration and adjustment, especially the positions of traffic signals and traffic calming features; and (v) monthly monitoring of disruptions classified in three categories: (a) disruptions to handle, (b) deviations decided but not yet validated and (c) deviations validated.

•

  Yipeng Huang, Andréa Cynthia Santos, Christophe Duhamel, Managing disruptions in urban road networks for real contexts, in: 6th INFORMS Transportation Science and Logistics Society Workshop, Hong Kong, China, 2018. • Yipeng Huang, Andréa Cynthia Santos, Christophe Duhamel, Managing predictable and unpredictable disruptions on road networks, in: Int'l Conference on Intelligent Transportation Engineering and Smart City (ITESC 2017), Guilin, China, 2017. • Yipeng Huang, Andréa Cynthia Santos, Christophe Duhamel, Heuristics for the bi-objective Unidirectional Road Network Design Problem with Disruptions, in: Annual workshop of the EURO working group on Vehicle Routing and Logistics optimization (VeRoLog), p140. Nantes, France, 2016.

•

  Yipeng Huang, Andréa Cynthia Santos, Christophe Duhamel, Optimal traffic Deviation System. TRAVISIONS (Academic Student Competition), 23, Varsovie, Pologne, 2016.

  investigate a Discrete NDP minimizing total travel cost with respect to a given budget for network changes, especially operations concerning the capacity. Authors emphasize the use of discrete functions that appropriately satisfy transportation network design. Formulations are separately given for the objective function, the trip distribution problem and the assignment problem. Several problems combining the aforementioned formulations are presented. Moreover, computational results obtained by experiments of a simple 10-node network are shown and perspectives on a number of open questions are given for further studies. Yang & Bell (1998) study a generic bi-level framework for modeling transportation planning and investment decision-making problems under a transportation network management system. Authors consider the NDP on an economic aspect, especially budget constraints on financial resources (investment). The goal of the lower level is to carry out the network flow pattern holding the equilibrium between traffic flow and the level of service of the network (demand-performance equilibrium) influenced by a given investment. It is passed as a decision variable to the upper-level model. Authors review some equilibrium models such as User Equilibrium and the logit-based Stochastic User Equilibrium. For the upper-level, the profit from investment is maximized in terms of social welfare for transport planners. It can handle different types of decision variables, either discrete, continuous or mixed.

  and Farahani et al. (2013) for a summary of several mathematical models, such as traffic assignment to transportation networks, supply design models and transportation systems engineering for planning and evaluation. In this context, problems can be specialized in Urban Transportation Network Design Problem, a refined term interpreting transportation planning decision-making problems when traffic demand grows, by applying network changes and facility location setting under some given constraints. Other terms include Road Network Design Problem and (Public) Transit Network Design Problem.

  TS and a Path Relinking procedure. Experiments are done with real networks of three small Italian towns: Villa San Giovanni with 45 km, 88 nodes and 225 arcs; Melito Porto Salvo with 23 km, 96 nodes and 189 arcs; and Barcellona Pozzo di Gotto with 81 km, 176 nodes and 510 arcs. Gallo et al. (2012) study the problem of improving the network infrastructure considering the investment cost in order to increase the flow capacity and the free-flow speed.

  chapter, mathematical formulations are presented for RND. First, the notations used in definitions and models are listed and explained in Section 3.1. Details and common definitions of RND are given in Section 3.2. Then in Sections 3.3 and 3.4, URND and MRND are formally defined and formulated by bi-objective mathematical models with respective examples illustrating several key concepts. Particularly, the latter section includes also the definition of the 2-directed multigraph, a specific multigraph used in MRND formulations.

Figure 3 .

 3 Figure 3.1 depicts an example of different orientations on an unidirectional road network

Figure 3 . 1 :

 31 Figure 3.1: An example network with one blockage addressed by URND

Figure 3 . 3 : 1 (Figure 3 . 4 :

 33134 Figure 3.2: Modeling a deviation.

  Figure 3.5-(d).

Figure 3 . 5 :

 35 Figure 3.5: An example network with one blockage addressed by MRND

Figure

  Figure 3.6: 2-directed multigraphs reductions: 1 direction

1

 1 and c 2 are defined by (3.20) and (3.21). The flow conservation constraints are formulated in (3.22) and (3.23). In addition, inequalities (3.24) and (3.25) model the relations between f and y and between x and f . Reversals of unused arcs are still forbidden as in the constraints (3.26). Finally, definition of variables are formulated in (3.27), (3.28) and (3.29). Moreover, this model consists of (2 × |P | + 1) × |A 2 | variables and

of 2 -

 2 directed multigraph, this is probably because 2 arcs (at most) between a pair of nodes o and d can be turned into bi-directional (a 1 = (o, d) and a 2 = (d, o)) that simplifies the paths from o to d and from d to o, while in URND, an arc a 0 = (o, d) cannot be served in the path from d to o. The same situation can also be found in c 2 minimization, that, comparing to URND, CPLEX uses less time to solve multigraphs. Besides, the number of disruptions does not seem to have a significant impact on the objective values and the processing time.

v

  of u and propagate a visit to v if the edge(u, v) is not yet oriented, see the line 4. More precisely, the line 5 sets the orientation for the edge (u, v) and the line 6 recursively calls the strong orientation algorithm with v as the new root vertex.

Figure 4 . 1 :

 41 Figure 4.1: Examples of the strong orientation algorithm

  Figure 4.3: Orientation impossible to generate

  RKGA are then compared to a BRKGA by using time-to-target plots and the latter shows a better performance. Parameter settings are also addressed by a set of experiments carried out on variations of the population size, the partition of elite individuals, the number of mutants and the elite inheritance probability. As a consequence, recommendations for the parameters configuration are given. Applications of BRKGA to telecommunication problems are presented in[START_REF] Gonçalves | Biased random-key genetic algorithms for combinatorial optimization[END_REF] and[START_REF] Resende | Biased random-key genetic algorithms with applications in telecommunications[END_REF]. For each problem, authors give a brief definition, the way a solution is encoded by random keys, the heuristic in the decoder and several numerical results. Particularly, it is shown that a BRKGA can combines a LS in the decoder in order to improve solutions quality.[START_REF] Stefanello | On the minimization of traffic congestion in road networks with tolls[END_REF] propose using a BRKGA on toll setting problem for minimizing the traffic congestion. It aims at assigning tolls to critical streets and deciding their tariffs. The main goal is to reduce the Urban transportation road network problem congestion and better distribute the traffic, since drivers tend to choose alternate routes in order to avoid paying tolls. Authors propose mathematical formulations and a BRKGA to solve the problem. Numerical results of experiments on the models as well as the BRKGA are shown and it is stated that the BRKGA produces high quality solutions.4.2.1.1 BRKGA applied to URND and MRNDFor the problems in this thesis, the randomized strong orientation algorithm (Algorithm 4.1) can be used as a decoder, since the vector of weights can be interpreted as a vector of random keys. Thus, a BRKGA is developed taking this algorithm as the basis of the decoding heuristic for both URND and MRND. A solution is an oriented graph (respectively G 1 and G 2 ) encoded in the BRKGA with random keys representing the weights on each vertex. Using the Algorithm 4.1 and set the vertex of highest random key as the input root vertex u, a chromosome of random keys is decoded into a solution. Then, depending on the optimization objective, the solution fitness is evaluated. An adapted Dijkstra's shortest paths algorithm[START_REF] Dijkstra | A Note on Two Problems in Connexion with Graphs[END_REF]) on all vertices is used for c 1 objective. The c 2 objective is evaluated by counting the number of arcs whose directions are reversed comparing to the initial graph. This decoding procedure is detailed in Algorithm 4.2. Algorithm 4.2 Decode(G, c) Input: G = (N, A): graph (simple or multiple) with initial orientation c: a chromosome with random keys Output: fitness of the orientation decoded from c Variables: g: temporary graph 1: g ← removeOrientation(G) 2: u ← index of the highest random key in c 3: StrongOrient(g,c,u) 4: f ← fitness(g) 5: return fSince the chromosomes depend on random keys and are independent to the initial orientation of the given graph, the solutions decoded can show a large difference in the configuration. It has been observed that the resulting graphs often have a lot of arc reversals, which is not suitable when minimizing the c 2 objective in neither URND nor MRND. Thus, a repairing procedure is added to the decoding method, especially for c 2 . It aims at reducing as much as possible the arc reversals. According to the guideline of a BRKGA, a solution should always be feasible. Therefore, this procedure also ensures that the resulting graph is strongly connected by using Tarjan's Strongly Connected Components (SCC) algorithm proposed in[START_REF] Tarjan | Depth-First Search and Linear Graph Algorithms[END_REF]. Modifications on Algorithm 4.2 result the Algorithm 4.3 when optimizing the c 2 objective. Since the complexity of the Tarjan's algorithm is O(|N |+|A|) for a given graph G = (N, A), the procedure in Lines 4-10 has a complexity of O(|N |×|A|+|A| 2 ) in the worst case where all arcs a ∈ A are reversed. Algorithm 4.3 Decode Repair c 2 (G, c) Input: G = (N, A): graph (simple or multiple) with initial orientation c: a chromosome with random keys Output: fitness of the orientation decoded from c Variables: g: temporary graph 1: g ← removeOrientation(G) 2: u ← index of the highest random key in c 3: StrongOrient(g,c,u) 4: for each reversed arc e in g do 5:

  end forreturn fitness(g) With the proposed solution encoding and decoding, BRKGA can be used to solve both URND and MRND. This requires a graph with the initial orientation, the size of the population and the number of wanted generations. The graph can be either G 1 or G 2 , for URND and MRND, respectively. Algorithm 4.4 presents the process for solving an instance of the problems. The population is initialized with the given number of chromosomes in Line 1. Then, the population is evolved for the given number of generations in Lines 2-13. In each generation, the BRKGA decodes every chromosome in the population by the respective algorithm (Algorithm 4.2). Next, Lines 6-12 is the evolution procedure which is common for either URND and MRND. The BRKGA sorts the chromosomes by their fitness, partitions the population into an elite group and a non-elite group, initializes a new population, copies the elite chromosomes into the new population, generate mutants for the new population and generate offsprings of the current population to make up entirely the new population for the next generation. At the end of all generations, the best fitness is returned as the near-optimal solution found, shown in Line 14. Algorithm 4.4 BRKGA(G, p, n) Input: G = (N, A): graph (simple or multiple) with initial orientation p: population size n: number of generations Output: fitness of G with incumbent near-optimal orientation Variables: P : population P : temporary population c: a chromosome

  (2003) as well as in[START_REF] Lourenço | Iterated Local Search: Framework and Applications[END_REF], such as the Traveling Salesman Problem, the Quadratic Assignment Problem, Vehicle Routing Problems, scheduling problems and the MAX-SAT problem. It is claimed that, depending on the given problem, sophisticated components of a ILS and problem-specific fine tuning are necessary to reach a better performance.

Figure 4 Figure 4

 44 Figure 4.5. A move in N 3 reverses one arc, see Figure 4.6. The strong connectivity is ensured by moves in N 1 , while it is not in N 2 and N 3 . Hence Tarjan's Algorithm for SCC is used

Figure 4

 4 Figure 4.6: N 3 move at arc (1, 2)

  4: end ifAccording to the architecture given by[START_REF] Lourenço | Iterated Local Search[END_REF] and[START_REF] Lourenço | Iterated Local Search: Framework and Applications[END_REF], the dedicated components are coordinated in the proposed ILS given by Algorithm 4.8. Line 1 initializes the counter of iterations without improvement. The initial solution is generated and then optimized by a LS in Lines 2-3. Next, Lines 4-13 repeats the procedure of the perturbation (Line 5), the LS (Line 6) and the acceptance criterion (Lines 7-12) under the stopping condition depending on the number of iterations without improvement specified in Line 4. Since the acceptance follows a greedy criterion, the incumbent solution is the one with the best fitness returned as the output of the metaheuristic in Line 14.

  [START_REF] Chinchuluu | A survey of recent developments in multiobjective optimization[END_REF],[START_REF] Ehrgott | A survey and annotated bibliography of multiobjective combinatorial optimization[END_REF],[START_REF] Zopounidis | Handbook of Multicriteria Analysis[END_REF] and[START_REF] Zhou | Multiobjective evolutionary algorithms: A survey of the state of the art[END_REF].In most of the multiobjective optimization problems, a single solution is not a global Algorithm 4.8 ILS(G, p) Input: G = (N, A): multigraph with initial orientation p: max number of iteration without improvement Output: fitness of G with incumbent near-optimal orientation

  search space is constrained by successively optimizing one of the objectives and considering the new solution value as a new bound. The procedure stops when the sub-problem becomes infeasible. Examples of applications for the -constraint method are found in Bérubé et al. (2009) and De Sousa et al. (2015). In the case of bi-URND, in order to compute the Pareto-optimal front F, its extreme points Z 1 and Z 2 are first computed by optimizing the single objectives (3.1) and (3.2) respectively, within a mixed integer linear programming by CPLEX. The values c 2 = c 2 and c 2 = c 2 of arc reversals in respectively Z 1 and Z 2 define the interval of variation on c 2 for solutions in F. Since c 2 ∈ N, F can be computed by solving the modified problem M (κ) in which objective function (3.2) is turned into a constraint c 2 (x) ≤ κ, i.e.

Figure 4 .

 4 Figure 4.7 illustrates the schema of -constraint method applied on bi-URND and bi-MRND. The extreme points s 1 and s 2 are computed by optimizing respectively c 1 and

  Algorithm 4.9 -constraint(G, ) Input: G = (N, A): graph (simple or multiple) with initial orientation : step of constraint variation Output: Pareto-optimal front of G 1: s

  number of implementations and sophisticated adaptions are widely applied in different research areas. Since multi-objective optimization problems arise over the years, extension of EAs to Multi-Objective Evolutionary Algorithm (MOEA) gains researchers' attention and efforts have been given such as in[START_REF] Kalyanmoy | Multi-Objective Optimization Using Evolutionary Algorithms[END_REF] and[START_REF] Zitzler | Multiobjective optimization using evolutionary algorithms -A comparative case study[END_REF]. In particular, Multi-Objective Genetic Algorithm (MOGA) is well studied in[START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF],[START_REF] Fonseca | Genetic Algorithms for Multiobjective Optimization: FormulationDiscussion and Generalization[END_REF],[START_REF] Horn | A niched Pareto genetic algorithm for multiobjective optimization[END_REF],[START_REF] Santos | Modeling and solving the bi-objective minimum diameter-cost spanning tree problem[END_REF] andSrinivas & Deb

  by using the ranking mechanism. In addition, a sharing method with a niche formation technique is applied in order to maintain the diversity of the population and the distribution of nondominated solutions. The other mechanisms of the metaheuristic follow the guideline of a classical GA, such as the crossover and the mutation. Regarding simulation experiments, three test problems are solved by the proposed NSGA and a Vector Evaluated Genetic Algorithm (VEGA), another MOGA developed in the thesis of Schaffer

4. 3

 3 .4.1 NSGA-II applied to bi-URND and bi-MRND Since the proposed BRKGA and ILS are adapted to the bi-objective optimization, it is valuable to compare them with a metaheuristic especially designed for multiobjective purposes. Thus, the NSGA-II is also developed. It applies a generic fast nondominated sort with a ranking calculation, a crowded-comparison operator with a crowding distance calculation, the classical crossover and a bitwise mutation. However, by carring out some preliminary experiments, the strong orientation algorithm proposed in Section 4.1 seemed not fit for NSGA-II. A different chromosome encoding has been hence designed. It also takes a set of random weights w ∈ [0, 1] as input but they are associated with arcs. If an arc possesses a weight w < 0.5, it is oriented from the vertex with a lower label to the other end and vice versa. Readers are referred to Algorithm 4.10 for details. This procedure has a lower computational complexity of O(m) (m is the number of arcs), but the orientation it proposes cannot be guaranteed to be strongly connected. In such a case, some shortest paths do not exist and a high-enough cost is used instead. This corresponds to a partial penalization of an infeasible solution. Nonetheless, according to the results of a testing implementation, every orientation is kept in the final population of the NSGA-II as it contributes to the performance of the final Pareto front.

  time. In the first experiment, parameter tuning has been carried out for the proposed metaheuristics, BRKGA, ILS and NSGA-II. The second experiment consists of the single-objective optimization on the generated instances. The small-and medium-sized instances, referred respectively in Tables3.1 and 3.2, are solved by BRKGA and ILS so as to analyze their quality of solutions comparing to the optima from CPLEX. Two additional sets of medium-and large-sized instances (presented in Tables 4.1 and 4.2) that CPLEX cannot solve in a reasonable amount of time or memory. Tests on these larger instances are done Algorithm 4.10 ArcOrient(G, W ) Input: G = (V, E): undirected graph (simple or multiple) W : arcs weight Output: G with an orientation 1:for each e = (u, v) ∈ E such that u < v do for only using the proposed metaheuristics. Third, the bi-objective optimization by the proposed methods has been tested on some of the generated instances. The last experiment aims at solving instances extracted from the real road network of Troyes, which is further explained in Subsection 4.4.4. Note that the machine used for running all experiments is the same one previously described in Section 3.5. The -constraint method is coded and compiled in Java version 1.7 using the "IBM ILOG CPLEX Concert" API library. All the metaheuristics are coded inC++ and compiled by Visual C++ version 11.0 (in "Visual Studio 2012").

  cN ) and the probability of mutation (ρ mN ).

  Tables 4.7 and 4.8 present respectively the results for the URND minimizing c 1 and c 2 on instances from Tables 3.1 and 4.1, with the number of nodes less than 50. In the following, results for the MRND minimizing c 1 and c 2 are listed respectively in Tables 4.9 and 4.10

  Figure 4.9: Time-to-target plots of BRKGA and ILS for MRND c 1 objective

  optimization. Experiments are hence necessary to validate the adaptations to these methods by comparing their performance for computing Pareto fronts with the classical multi-objective frameworks, -constraint method and NSGA-II. Due to the long running time of these method on large instances, only the instances from 3x3 to 8x8 are tested in this work. In order to analyze the quality of Pareto fronts produced by the proposed methods, three performance metrics are used. The first metric is the number of Pareto solutions in the first front. The second metric is the hypervolume (Zitzler & Thiele (1998)) that represents the size of the area dominated by the given front in the solution space. The last one is the spacing (Veldhuizen & Lamont (2000) and Zitzler et al. (2003)) which allows to analyze the distribution of the given Pareto front.

  and 4.18. It can hence be used as the basis for the relative comparison of their performance. Readers are referred to Appendices C and D for more figures of Pareto

Figure 4

 4 Figure 4.10: Pareto fronts on 5x5-b1 (bi-URND)

Figure 4

 4 Figure 4.11: Pareto fronts on 5x5-b2-100 (bi-MRND)

Figure 4 .

 4 Figure 4.12 illustrates the Pareto fronts constructed by the three metaheuristics on the 8x8 instance with 6 disruptions.For bi-MRND with respect to results in Table4.18, ILS continues to perform well with

Figure 4 .

 4 Figure 4.12: Pareto fronts on 8x8-b6 (bi-URND)

Figure

  Figure 4.13: Pareto fronts on 8x8-b1-75 (bi-URND)

  BRKGA does not ensure a good spread of the fronts on these real instances. ILS got high quality Pareto fronts in terms of both hypervolume and spacing within a much shorter time than 5x5 bi-MRND instances. As for the Pareto fronts produced by NSGA-II, they are generally worse than bi-BRKGA and bi-ILS in terms of the hypervolume, whereas the quality of solutions distribution is leading. On the instances with 58 nodes with results reported in Table4.25, ILS still has a good solutions quality along with a huge time consumption. It can find Pareto fronts very close to the best known fronts combining the solutions found by all the metaheuristics. In addition, BRKGA dominates the other two metaheuristics on the Pareto fronts spread and it performs generally better than NSGA-II in terms of HV. Since NSGA-II uses much less time than the other two methods, it should be tested in the future whether its performance can be enhanced by running a longer time. Example of combined Pareto fronts can be found in Figures 4.17

  and 4.18 for troyes-v24-b2 and troyes-v58-b6 instances, respectively. Readers are also referred to Appendices C and D for more images.

Figure 4 .

 4 Figure 4.18: Pareto fronts for the troyes-v58-b6 instance

  the design and development of the first ODS prototype are launched in 2014 thanks to the collaboration with PC-Régulation of Troyes. The corresponding work in Subsection 1.2.5 is ranked 13 th out of 107 projects in TRA-Vision 2016 Student competition. By a financial support from the Innov'Action project "AGIR", the further research and development have been carried out.

Figure 5 .

 5 Figure 5.1 illustrates the design of the entire system.

Figure 5 . 1 :

 51 Figure 5.1: System architecture of ODS

Figure 5 . 3 :

 53 Figure 5.3: Mockup of deviation management with a map view and list of blocking events

Figure 5

 5 Figure 5.5: Example of map tiles with map projection and tile coordinates 1

Figure 5 . 7 :

 57 Figure 5.7: Palette of colors used in ODS

Figure 5

 5 Figure 5.9: An example of deviations visualization on the map view

  Figure 5.11 is a screenshot of the way the traffic signals are visualized on the map view.

Figure 5 .

 5 Figure 5.11: Visualization of traffic signals on the map view

  Besides, the methods studied in this work are tested on instances generated from the real urban network of Troyes, France. Graphs are extracted from the geographical data on which random disruptions are added. Specific techniques are used to restrict the size of the graphs that are grouped into three levels: (i) 24 nodes and 43 arcs; (ii) 58 nodes and 155 arcs; (iii) 102 nodes and 193 arcs. The smallest instances can be solved by CPLEX for MRND and by -constraint method for bi-MRND, while the metaheuristics are run on larger instances. The methods are able to solve all these instances and their behaviors are quite similar comparing to the results obtained from the constructed instances.The second part of this work consists of the design and development of ODS, a decision-support system that helps to compute alternate paths for disruptions and to manage the concerned road network. In the background of the collaboration with the traffic control department of Troyes city hall, the requirements of ODS as well as its architecture are determined and validated in order to guide the following development. The major features of ODS comprise the visualization of disruptions on a map view, the computation of deviations and the management of network elements such as the traffic signals, the stop signs and the speed reducers. The development of the software are divided into three phases concerning the HCI for interacting with users, the database for integrating information and the computing core for calculating deviations according to various constraints and criteria. During the thesis, my contribution to ODS relied on the design of the software architecture and the development of the computing core. Furthermore, the first version of the final product is released that combines the most important functionality and optimization criteria, for Chapter 6. Concluding remarks and future works instance, minimizing the detouring distance, the number of sections and the number of traffic signals. Other elements are planned to be integrated progressively in ODS in future stages of development.

  des graphes simples pouvant couvrir les cas des centres-villes historiques. De son côté, MRND utilise une modélisation des réseaux par multigraphes dans lesquels des rues à double sens peuvent être définies. Les modèles mathématiques sont proposés pour ces deux problèmes en se basant sur le modèle de multi-flot. Ensuite, deux métaheuristiques sont développées pour l'optimisation mono-objectif, un « Biased Random Key Genetic Algorithm » (BRKGA) et un « Iterated Local Search » (ILS). Des adaptations sont réalisées pour ces deux méthodes afin de pouvoir traiter les deux problèmes en bi-objectif (respectivement bi-URND et bi-MRND). Une méthode exacte multi-objectif « -constraint method » et une métaheuristique multi-objectif « Non-dominated Sorting Genetic Algorithm II » (NSGA-II) sont également développées. L'analyse de la performance des méthodes est basée sur la comparaison des résultats numériques provenant des expérimentations. La partie applicative de cette thèse est consacrée à la conception et au développement du logiciel « Optimal traffic Deviation System » (ODS), un système d'aide à la décision pour gérer des arrêtés et calculer automatiquement des déviations correspondantes. À l'aide d'une représentation graphique de la cartographie, des arrêtés et déviations peuvent être visualisés. De plus, les resources de différents composants sont gérées par la base de données. Celle-ci relie des systèmes hétérogènes comme OpenStreetMap et GEODP, contenant des informations géographiques et les enregistrements des arrêtés municipaux. Plusieurs contraintes et critères d'optimisation sont pris en compte par les algorithmes dédiés permettant de calculer des déviations. Ce travail s'inscrit dans le cadre du projet TOAST (Tactical Optimization Strategies to Adapt Urban Transportation Networks), en collaboration avec le PC-Régulation de trafic de la Ville de Troyes et l'entreprise de R&D Beijing YuanZhiTianCheng Co. Ltd. Il fait partie aussi du projet AGIR (système d'Aide à la décision pour la Gestion d'Interruptions Routières), porté par le PC-Régulation de Troyes et financé par la région Champagne-Ardenne. Ce projet a pour but de réaliser ODS et de tester son fonctionnement dans un contexte réel. Structure du document À la fin du chapitre d'introduction se trouve une liste des contributions réalisées au cours des années de doctorat. Le reste du document s'organise en quatre partie : la revue de littérature sur les travaux liés au RND, la définition et modélisation de bi-URND et bi-MRND, les méthodes pour résoudre les problèmes et la réalisation d'ODS. Les points clés de chaque chapitre sont soulignés ci-dessous : le chapitre 2 présente la bibliographie en relation avec deux domaines de recherche : la théorie des graphes et la conception de réseau (Network Design Problem (NDP)). Les études qui nous intéressent le plus concernent l'orientation des graphes, le renversement d'arcs ainsi que les modèles, méthodes et applications dans le contexte des réseaux routiers. Elles sont essentielles non seulement pour la recherche sur RND mais également pour la conception des méthodes de résolution dans ODS. Bi-URND et bi-MRND sont formellement définis dans le chapitre 3 avec leur modélisation par graphe. Les modèles reposent sur la notion classique de multi-flot. De plus, nous définissons un multigraphe particulier, le 2-directed multigraph, afin de réduire les multigraphes généraux en graphes contenant au plus deux arcs entre chaque paire de sommets. Pour tester la pertinence des modèles, des instances abstraites sont générées et les expérimentations reposent sur le solver commercial CPLEX. Ensuite, des métaheuristiques sont proposées pour pouvoir traiter des instances de taille plus grande, que les modèles n'arrivent pas à résoudre. Tout d'abord, nous adaptons l'algorithme de parcours en profondeur (Depth-First Search (DFS)) pour proposer une heuristique d'orientation des graphes. Elle est modifiée pour pouvoir générer davantage de solutions initiales différentes. Elle est ensuite utilisée dans les deux métaheuristiques BRKGA et ILS initialement conçues pour l'optimisation mono-objectif. Leur principe est expliqué ainsi que les adaptations apportées pour pouvoir passer en version bi-objectif. Toujours dans le cas de l'optimisation bi-critère, sont proposées une méthode exacte utilisant -constraint et la métaheuristique NSGA-II, très utilisée dans la recherche opérationnelle multi-critère. La discussion se termine par les résultats numériques des expérimentations sur plusieurs ensembles d'instances de tailles différentes, y compris des données provenant du réseau de transport de Troyes. Le dernier chapitre du mémoire consiste en la présentation détaillée d'ODS, depuis la phase de conception jusqu'au développement. Suite à l'analyse des besoins établie au début du projet et validée par l'ensemble des acteurs, l'architecture du système est décrite. Cette dernière est ensuite analysée d'une manière plus technique, notamment l'Interface Homme-Machine (IHM), la base de données et le moteur de calcul. Toutefois, il existe encore de nombreux problèmes techniques dont la solution restent à être définie de façon précise. Finalement, ce mémoire se conclut par des remarques et des discussions sur tous ces sujets concernés, ainsi que des perspectives pour des travaux dans le futur.

  déviations pour chaque arrêté ayant lieu au centre-ville historique, dans lequel il existe de nombreuses rues à sens-unique. Dans ce contexte, la collaboration avec le Poste Central de Régulation de trafic de Troyes Champagne Métropole a été établie pour développer ODS, un système d'aide à la décision pour gérer les arrêtés et proposer le calcul des déviations adaptées à chaque catégorie de véhicule. Ce projet a été réalisé dans le cadre du projet TOAST avec un support de financement par le projet Innov'Action AGIR de la région Champagne-Ardenne. La fonctionnalité principale d'ODS est de calculer les déviations sur la base de l'optimisation d'un seul critère. Pour le moment, 3 critères d'optimisation sont intégrés dans le système de production: la distance du détour, le nombre de segments empruntés et le nombre de feux tricolores rencontrés. D'autres objectifs ont aussi été prévus, telles que le nombre de changements de suns de circulation à effectuer. Notons que cette dernière dépend des opérations de renversement et de mise en double sens des arcs, qui sont en cours de réalisation. De plus, le calcul multi-objectif sera aussi pris en compte dans le futur. Pour l'instant, un module de visualisation multi-critère est déjà implanté.Analyse des besoinsDans le cadre de la conception du système, l'analyse des besoins est d'abord réalisée en considérant des flux de travail des utilisateurs et des aspects pratiques du développement. Dans ce cadre, un cahier des charges complet a été établi pour diriger la mise en place du système et le suivi de l'avancement. Les principes sont expliqués dans le reste de cette des fonctions, en considérant l'intégration des systèmes hétérogènes comme la base de données des arrêtés. Elle est illustrée dans la Figure A.2. La couche de présentation est destinée particulièrement aux utilisateur. Elle contient tous les modules sur l'Interface Homme-Machine (IHM). La couche de services sert à établir le lien entre l'IHM interagissant avec les utilisateurs et le calcul en arrière-plan d'ODS. Elle consiste surtout en des Web services interfaçables par la couche de présentation. En effet, il est possible de changer l'IHM du système sans toucher aux autres parties. Ensuite, la couche logique est surtout composée des moteurs de calcul pour la proposition des déviations. Il y a en particulier le solver pour calculer des chemins des déviation, mais il peut y avoir aussi d'autres moteurs pour évaluer les déviations selon des critères spéciaux, tels que la pollution de l'air, la pollution sonore, la satisfaction des usagers, etc. La dernière couche est prévue pour la manipulation des données ainsi que la connexion directe avec des bases de données hétérogènes. En dessous de ces couches modulaires, nous avons aussi conçu des composantes globales permettant de réaliser la journalisation, d'assurer la sécurité et de faciliter la maintenance d'ODS.

Figure A. 2 :

 2 Figure A.2: System architecture of ODS

  Figure C.2: Pareto fronts of -constraint method, BRKGA, ILS and NSGA-II on the instance 5x5-b2

Table 3

 3

	.2. Experiments are designed to solve all the generated instances within the proposed
	models for URND and MRND by the commercial solver CPLEX 12.6. They are done on a
	machine with an Intel CORE i7-4710MQ at 2.50 GHz, with 4 cores (8 threads) and 16 GB
	RAM under Windows.

Table 3

 3

	.2: Characteristics of generated
	multigraphs

Table 3

 3

.4: CPLEX results of small and medium multigraph instances (MRND)

  Table 4.3. B I B J B SD I J I ∆ I SD N R N I N ρ cN ρ mN Table 4.3: Predefined possible values of the parameters For example, Table 4.5 presents the preliminary results obtained by tuning the parameter SD I in ILS for c 1 objective. The additional column "δ c 1 %" represents the margins of the objective values comparing to the global optima computed by CPLEX (cf. Section 3.5).The other parameter J I is fixed and SD I is varied among the predefined values. Generally, the performance of ILS is better when setting SD I = 4 in terms of the processing time and the secondary value c 2 . Another example is given on the tuning of R B I B J B SD I J I ∆ I SD N R N I N ρ cN ρ mN

	BRKGA		ILS		NSGAII
	SD B R 0 1.25 50	6	2 6 0.075	2 1.25 50 0.3 0.03
	2 1.45 100 12	4 12	0.1	4 1.45 100 0.6	0.1
	8 1.75 150 24	8 24 0.15	8 1.75 150 0.9	0.3
	0 1.45 100 12	4 12 0.1	2 1.75 100 0.3 0.03
	Table 4.4: Chosen parameter values
	4.4.2 Results for single-objective URND and MRND

B in BRKGA for bi-objective optimization, as shown in Table

4

.6. The column "δ HV %" compares the resulting Hypervolume (HV)

[START_REF] Zitzler | Multiobjective optimization using evolutionary algorithms -A comparative case study[END_REF]

) to the exact Pareto-optimal fronts computed by -constraint method. The value 1.45 for R B saves the computational time in general, without losing too much quality of the fronts. After the calibration, the sets of parameter values in Table

4

.4 are chosen for the following experiments in this work. Other numerical results in this experiment can be found in Appendix B.

BRKGA ILS NSGAII

SD B R

  Table4.6: Results of bi-objective BRKGA parameter tuning on R B , with other parameters fixed: SD B = 2, I B = 100 and J B = 12 travel distance, the number of reversals and the processing time in seconds. Furthermore, columns "c 1 *" and "c 2 *" rely on optimum values for c 1 and c 2 objective function, respectively.Results in Tables 4.7 and 4.8 indicate that ILS performs generally better than BRKGA.On 4x4 and 5x5 instances, ILS found 9 out of 10 global optima when minimizing c 1 (in Table4.7) and 10 out of 10 global optima when minimizing c 2 (in Table4.8); in the same time, BRKGA found 7 out of 10 global optima when minimizing c 1 (in Table4.7) and 8 out of 10 global optima when minimizing c 2 (in Table4.8). On 6x6 instances, CPLEX solved only 1 out of 4 instances in the time limit when minimizing c 1 and both BRKGA and ILS are able

	Instance	c 1 * c 2	CPLEX t(s)	LR Gap(%)		BRKGA c 1 * c 2	t(s)	ILS c 1 * c 2	t(s)
		3x3-b1		246 2	0.27 212		13.82		246 2 0.18	246 2 0.15
	b1	246 3x3-b2	2 0.14 284 2	0 0.16 264	246	7.04	2	0.14 284 2 0.18 0	246 284 2 0.09 2 0.13	0
	4x4-b2	968 4x4-b1	17 0.60 912 22	0 22.40 786	968	17 13.82	0.52 912 3 0.82 0	968 912 1 0.47 17 0.67	0
	5x5-b4	3032 4x4-b2	13 3.86 968 5	0 11.34 836 3032	13 13.64	2.67 968 5 1.17 0	3032 968 17 0.56 13 4.29	0
	3x3-b2-25 4x4-b4 250	7 0.15 1392 8	0 3.99 1216	250	7 12.64 1392 8 0.60 1392 8 0.42 0.14 0 250 2 0.14	0
	4x4-b1-75 4x4-b6 716	8 1.61 1304 7	0 1.72 1088	716	16.56	7	1.22 1388 6 0.58 1304 7 0.28 0 716 7 1.28	0
	5x5-b1-50 5x5-b1 2296	15 7.65 2638 14 414.62 2292 0 2296	15 13.12	4.10 2668 23 2.42 2638 25 4.16 0 2296 22 4.81	0
	Best	246 5x5-b2	2 0.14 2748 16 373.96 2404 0	246	2 12.52 2748 16 2.64 0.14 0	246 2758 11 2.28 2 0.125	0
	Worst	3032 5x5-b4	17 7.647 3032 23 182.74 2636 0 3032	17 4.103 13.06 3032 23 2.68 3032 13 2.82 0 3032 22 4.805	0
	Average 1251.33 10.33 2.34 0.00 1251.33 10.17 5x5-b6 3116 4 253.86 2672 14.25	1.46 0.00 1251.33 10.50 3140 28 3.35 3116 4 1.64 1.89 0.00
		6x6-b1 ≤ 6250	-	7200 5506		11.90		6244 22 8.60	6394 36 8.57
		Table 4.5: Results of single-objective ILS parameter tuning on SD I 6x6-b2 ≤ 6554 -7200 5632 14.07 6356 32 7.70 6470 24 7.71
		6x6-b4 ≤ 6820	-	7200 5956		12.67		6780 35 10.94	6854 9 8.34
		6x6-b6		7006 35 3894.85 6394		Settings 8.74 7006 19 7.29 7006 35 6.14
	Instance 7x7-b1		R B = 1.25					R B = 1.45 13282 30 37.32 13344 43 49.90 R B = 1.75
	3x3-b1	Q 2 0.00 HV 7x7-b2 7x7-b4	t(s) δ HV % 0.98 0 Out of memory	Q 2	HV 0.00		t(s) δ HV % 1.25 0 13592 35 33.10 13688 29 23.68 Q HV t(s) δ HV % 2 0 1.19 0 14206 49 31.64 14214 30 24.80
	4x4-b2	7x7-b6	4 0.50	4.98	0		4	0.50		9.07 14824 45 24.54 14494 50 34.29 0 4 0.495 10.36	0
	5x5-b4			9 0.81 47.41	10		9	0.82		28.34	9	10 0.754 51.18	8
	3x3-b2-25		1 0.00	0.91	0		1	0.00		1.05	0	1	0	1.28	0
	4x4-b1-75		8 0.65	5.62	0		8	0.65		6.80	1	8 0.647	8.14	1
	5x5-b1-50	15 0.72 31.23	10	14	0.73		39.05	11	14 0.756 43.32	6
	Best		15	0 0.905	0	14	0		1.046	0	14	0 1.185	0
	Worst			1 0.805 47.408 0.104		1 0.818 39.047 0.109	1 0.756 51.184 0.075
	Average 6.50 0.45 15.19	0.03 6.33	0.45		14.26	0.03 6.50 0.44 19.25	0.02

to find the global optimum. When minimizing c 2 , CPLEX can easily solve all four instances of 6x6 to optimality and the two heuristics are also able to find the global optima. As for the instances of 7x7, it is not even possible to read the LP files for neither c 1 nor c 2 objective Table

4

.7: c 1 minimization for URND (I)

Table 4 .

 4 10: c 2 minimization for MRND (I) minimizing c 1 . It solves to optimality all 32 instances solvable by CPLEX when minimizing c 2 . BRKGA performs better for c 1 , finding 27 out of 28 global optima. It is a little bit worse for c 2 , finding 30 out of 32 global optima. With the growth of multiple arcs on instances with

	.1 are used in these expriments. Results indicate that ILS seems to performs globally better
	than BRKGA for URND as it reach target values quicker.

Figure 4.8: Time-to-target plots of BRKGA and ILS for URND c 1 objective

Table 4 .

 4 Table 4.18, ILS continues to perform well with 17: Performance comparison of Pareto fronts for bi-URND (II))

	Instance	BKS Q HV Q	BRKGA HV SP t(s) Q	HV	ILS	SP t(s) Q	NSGA-II HV SP t(s)
	6x6-b1 12 0.88 17 0.82 2.59 716 10 0.88 0.18 133 11 0.78 2.30 161
	6x6-b2 15 0.78 17 0.68 1.21 485 13 0.76 2.12 126 14 0.62 3.16 161
	6x6-b4	9 0.77 10 0.70 0.67 332	6 0.77 1.47 119	9 0.76 0.67 144
	6x6-b6 10 0.72 10 0.48 1.65 438	8 0.68 1.26	88	5 0.67 0.11 137
	7x7-b1 15 0.78 16 0.61 1.09 1369 11 0.74 2.30 703	8 0.74 0.82 368
	7x7-b2 19 0.83 17 0.76 1.75 1276 14 0.83 1.98 739 20 0.58 1.82 367
	7x7-b4	7 0.91 13 0.75 4.13 1100	7 0.91 1.50 587 15 0.83 0.80 346
	7x7-b6 14 0.87 24 0.74 3.56 1179	9 0.85 6.05 701 13 0.72 3.70 362
	8x8-b1 17 0.94 33 0.87 2.40 4556 15 0.93 3.80 2158 23 0.82 4.63 732
	8x8-b2 15 0.92 22 0.88 1.76 3474 10 0.86 5.61 2024 28 0.87 1.97 716
	8x8-b4 18 0.93 26 0.84 1.26 4894 17 0.91 3.45 1898 21 0.83 1.79 677
	8x8-b6 18 0.94 26 0.85 3.96 2840 17 0.94 1.20 1727 32 0.80 1.22 655

Table 4

 4

	Instance	BKS Q HV Q HV BRKGA SP t(s) Q	HV	ILS SP	NSGA-II t(s) Q HV SP t(s)
	6x6-b1-25 16 0.84 18 0.80 0.54 591 12 0.83 4.08	224 21 0.82 0.79
	6x6-b1-50 15 0.85 22 0.80 0.35 551 11 0.84 0.94	374 21 0.75 1.85
	6x6-b1-75 19 0.83 29 0.74 0.35 632 16 0.82 2.19	518 28 0.75 1.12
	6x6-b1-100 29 0.84 35 0.81 0.17 518 14 0.83 2.52	586 35 0.75 2.54
	6x6-b2-25 17 0.89 19 0.85 1.94 874 16 0.89 1.32	219 20 0.79 4.05
	6x6-b2-50 18 0.72 28 0.62 0.18 678 12 0.70 2.32	391 24 0.65 0.50
	6x6-b2-75 26 0.79 34 0.74 0.19 512 22 0.78 1.08	594 32 0.72 0.95
	6x6-b2-100 24 0.81 39 0.77 0.17 512 11 0.79 3.65	542 40 0.75 0.80
	7x7-b1-25 22 0.87 31 0.78 1.14 1837 21 0.86 3.82 1725 24 0.73 2.05
	7x7-b1-50 24 0.90 38 0.84 1.08 1105 22 0.89 4.98 2205 35 0.81 2.32
	7x7-b1-75 32 0.90 50 0.84 0.53 1276 22 0.89 8.65 3604 37 0.82 1.75
	7x7-b1-100 39 0.88 54 0.82 0.30 671 20 0.87 5.62 3884 41 0.77 2.60
	7x7-b2-25 19 0.84 26 0.67 1.93 1683 17 0.84 1.40 1442 27 0.67 1.59
	7x7-b2-50 17 0.87 38 0.79 1.59 1119 16 0.87 2.34 3036 35 0.78 1.56
	7x7-b2-75 24 0.92 46 0.85 0.55 1817 21 0.91 2.23 3741 35 0.83 1.47
	7x7-b2-100 31 0.90 52 0.86 0.70 635 18 0.89 3.70 4243 33 0.79 2.61
	8x8-b1-25 15 0.91 31 0.71 3.17 5029 14 0.90 4.29 4199 22 0.68 4.56
	8x8-b1-50 26 0.89 40 0.75 3.96 5143 23 0.88 5.75 8196 35 0.77 2.29
	8x8-b1-75 30 0.90 61 0.79 0.67 8000 29 0.90 2.12 9476 31 0.74 2.86
	8x8-b1-100 37 0.88 75 0.81 0.19 1989 22 0.87 4.81 12378 48 0.72 2.69
	8x8-b2-25 19 0.85 35 0.67 2.77 3772 16 0.84 2.63 3959 25 0.71 3.76
	8x8-b2-50 24 0.92 43 0.81 1.98 2974 23 0.92 5.42 9468 36 0.74 3.23
	8x8-b2-75 40 0.90 55 0.82 1.38 5823 33 0.90 9.37 11697 44 0.77 3.36
	8x8-b2-100 33 0.92 69 0.85 0.35 1761 19 0.92 5.74 10958 41 0.77 2.83

.18: Performance comparison of Pareto fronts for bi-MRND (II))

Table 4 .

 4 19: Characteristics of Troyes network based instances is described in 4.4.2. First, CPLEX, BRKGA and ILS are used to solve the small instances of troyes-v24. Tables 4.20 and 4.21 contain the results obtained. CPLEX is still able to handle these instances for minimizing both c 1 and c 2 . When minimizing c 1 , BRKGA is a bit faster than ILS in terms of computational time, but the quality of solutions is slightly worse since only 2 out of 4 global optima are found whereas ILS finds all the four. As for c 2 terms of the solution quality in c 1 optimization, whereas BRKGA can find the same objective values as ILS on 7 out of 8 instances when minimizing c 2 .

	minimization, both BRKGA and ILS can find all 4 global optima in a reasonable amount of
	time. However, ILS runs much longer than either CPLEX or BRKGA. Second, since CPLEX

cannot handle the larger instances of troyes-v58 and troyes-v102 (respectively larger than the generated 7x7 and 10x10 instances), only the two proposed metaheuristics are tested with results reported in Tables 4.22 and 4.23. While consuming much more time, ILS leads BRKGA in instances of troyes-v24 while the larger instances are tested only by the metaheuristics. Table

4

.24 shows the comparison of the bi-objective optimization performance of the four methods. The exact method consumes a relatively longer time compared to the similar

Table 4 .

 4 23: c 2 minimization on troyes-v58 and troyes-v102 instances instance set of 5x5 multigraphs. The reason might be that the real networks are more complex than the generated ones with real arc distances though the network size stays small.

  Under the single-objective context (URND and MRND) with respect to c 1 and c 2 criteria,

		Instance			-constraint Q HV SP	t(s) Q	BRKGA HV SP		t(s) Q	HV	ILS SP	t(s) Q	NSGA HV
	troyes-v24-b1		8 0.86 0.36 108.48	9 0.85 4.81 81.66 6 0.85 0.83 68.05	8 0.86 0
	troyes-v24-b2 11 0.86 0.34 263.28 12 0.85 1.49 99.65 7 0.84 0.79 61.07 13 0.78 0
	troyes-v24-b4		7 0.88 0.35		99.86	8 0.87 2.21 97.15 7 0.86 0.48 51.73 13 0.66 0
	troyes-v24-b6		9 0.86 0.47 290.96	9 0.83 2.17 51.33 8 0.85 0.56 45.76	8 0.84 0
		Table 4.24: Performance comparison of Pareto fronts on troyes-v24 instances
		Instance		BKS Q HV Q HV BRKGA SP t(s) Q		HV	ILS	NSGA-II SP t(s) Q HV SP t(s)
	troyes-v58-b1 17 0.90 15 0.77 1.04 2230 17 0.90 1.10 4754 21 0.50 7.35 1183
	troyes-v58-b2 16 0.94 19 0.84 1.14 1553 15 0.94 20.29 3413 27 0.61 8.21 1205
	troyes-v58-b4 17 0.88 14 0.76 2.00 2525 15 0.88 2.22 3696 13 0.40 8.08 1155
	troyes-v58-b6 20 0.91 24 0.81 0.76 2730 19 0.91 1.08 3121 26 0.48 5.18 1138
		Table 4.25: Performance comparison of Pareto fronts on troyes-v58 instances
		260000 270000 280000							ε-constraint BRKGA ILS NSGA-II				2.22x10 6 2.24x10 6 2.26x10 6								BRKGA ILS NSGA-II
	Distance	240000 250000												Distance	2.16x10 6 2.18x10 6 2.2x10 6
		230000													2.14x10 6
		220000													2.12x10 6
		210000	0	2	4	6	8	10	12	14	16	18	20		2.1x10 6	0	10	20	30	40	50	60	70	80	90 100
							Nb. reversals											Nb. reversals
		Figure 4.17: Pareto fronts for the
			troyes-v24-b2 instance

numerical experiments are performed on a set of generated instances up to 144 nodes and 264 arcs for URND and up to 81 nodes and 288 arcs for MRND. Methods are also applied on instances extracted from the real network of the French Troyes city, Troyes, with 58 nodes

  'orientation de graphes, notamment celui de[START_REF] Tarjan | Depth-First Search and Linear Graph Algorithms[END_REF],de Roberts (1978) etde Chung et al. (1985). Des algorithmes en temps linéaire sont proposés pour fortement orienter soit des graphes simples soit des multigraphes mixtes. Généralement, ils s'attachent à l'algorithme de DFS et de recherche de composantes fortement connexes, qui sont centraux dans le domaine. En particulier,[START_REF] Conte | Directing Road Networks by Listing Strong Orientations[END_REF] propose un algorithme pour énumérer toutes les orientations fortement connexes d'un multigraphe mixte de m arcs et arêtes en temps amorti de O(m) pour le passage d'une orientation à la suivante. L'idée basique est de trouver des ponts dans des sous-graphes ainsi qu'une direction pour chacun respectant la forte connexité du graphe. Par ailleurs, les auteurs utilisent une technique spéciale basée sur des boucles pour transformer efficacement d'une orientation en une autre. L'utilisation du renversement d'arcs est en fait relativement peu étudiée. Il y a cependant des travaux essentiels comme la conjecture de Ádám (1963) sur l'existance d'un arc dont le renversement réduit le nombre de cycles élémentaires dans une graphe simple orienté. ∈ N 2 × N 2 sont indexés avec un entier k ∈ N. La représentation d'un arc devient donc(i, j, k) ∈ A 2 . Similaire à la réduction de G 1 à H 1 , H 2 = (N 2 , A 2 ) est le sous-graphe de G 2 avec A 2 = A 2 \ B, i.e.après avoir retiré les arcs bloqués. Il est important d'abord de souligner la modélisation d'un réseau de transport par graphe. Dans un réseau routier, il existe au moins un chemin entre toute paire de points. Cette propriété correspond à la connexité d'un graphe non-orienté et à la forte connexité d'un graphe orienté. De plus, la rue (un tronçon) et l'intersection sont les deux éléments topologiques essentiels dans un réseau de transport. On peut les représenter par un sommet (noeud) et une arête (un arc) dans un graphe. Néanmoins, une rue peut avoir plusieurs voies et sa circulation peut être à sens unique ou à double sens. L'utilisation du multigraphe est donc naturelle pour bien distinguer le sens et les voies. Les expérimentations de ces modèles sont ensuite effectuées. Le but est de tester leur fonctionnement, de connaître leurs limites et d'identifier les marges en termes de relaxation linéaire pour trouver des solutions optimales. Les deux objectifs sont testés indépendemment dans cette partie alors que l'optimisation bi-objectif est traitée plus tard dans ce mémoire. Les instances de petite et moyenne taille ont été générées pour les tests. Ce sont des graphes en grille pour lesquels tous les arcs ont un coût de 1. Les arcs bloqués sont sélectionnés de façon aléatoire, en garantissant cependant que les graphes résultants sont toujours orientables. Selon le type d'instances, 14 graphes simples et 24 multigraphes 2-orientés sont créés. Pour URND, le modèle rencontre des difficultés sur l'objectif c 1 . Ceci est confirmé par des marges assez grandes au niveau de la relaxation linéaire. Aussi, le temps de calcul croît rapidement avec l'augmentation de taille d'instance et CPLEX n'arrive pas à résoudre 3 parmi 4 instances avec 36 noeuds et 60 arcs dans une limite de 2 heures. En revanche, la minimisation du nombre d'arcs renversés ne pose pas de problème pour le modèle. Les marges sont faibles et le temps d'exécution est raisonnable. Pour MRND, les résultats sont favorables pour c 1 et c 2 sauf que la résolution de certaines instances moyennes "6x6" est limitée par un blocage lié à la taille des programmes linéaires mixtes générés. Il doit être décodé pour obtenir une solution selon les spécifications du problème. Ensuite, selon l'évaluation des solutions, la population des individus est ainsi divisée en deux groupes: l'un des élites avec des meilleures performances et le reste composé des non-élites. Au passage d'une génération à une autre, les solutions élites sont toujours gardées. De plus, pour générer de nouveaux individus, le croisement se fait toujours avec un chromosome dans les élites et un autre dans les non-élites. C'est le principe de l'évolution biaisée. De plus, en comparant l'orientation de la solution avec l'orientation initiale du graphe, le nombre d'arcs renversés peut être compté (objectif c 2 ). Cependant, d'après des tests préliminaires, BRKGA a tendance à trouver des solutions qui renversent de nombreux arcs, ce qui n'est pas désirable dans la gestion réelle des réseaux. De ce fait, un post-processing est intégré dans le décodage des chromosomes pour essayer d'annuler des arcs renversés tout en garantissant que l'orientation résultante soit fortement connexe. En revanche, dans le cadre d'optimisation multi-objectif, la résolution d'un problème s'effectue par la recherche d'un ensemble de solutions telles que aucune n'est dominée par une autre. En empruntant la notion de dominance de Pareto (Pareto (1906)), cet ensemble est appelé front de Pareto et les solutions sont dites Pareto-optimales. En considérant les objectifs c 1 et c 2 pour bi-URND et bi-MRND, une solution s 2 est dominée par s 1 si une des deux conditions suivantes est remplie:

	BRKGA
	BRKGA est une métaheuristique proposée par Gonçalves & Resende (2011) et Resende
	(2012). C'est une variant de l'Algorithme Génétique, lequel repose sur l'évolution d'une
	population d'individus. La particularité de cette métaheuristique est surtout l'encodage
	Définitions de RND, d'URND et de MRND générique des chromosomes, l'utilisation de l'élitisme, le biais et l'ajout des mutants.
	Premièrement, chaque individu est encodé par un vecteur de clés aléatoires dans l'intervalle
	[0, 1].
	• Yipeng Huang, Andréa Cynthia Santos, Christophe Duhamel, Methods for solving road
	network problems with disruptions. Electronic Notes in Discrete Mathematics, Volume
	64, pp. 175-184, 2018.
	• Yipeng Huang, Andréa Cynthia Santos, Christophe Duhamel, A bi-objective model to
	address disruptions on unidirectional road networks, in: Proceedings of the 8th IFAC
	Conference on Manufacturing Modelling, Management and Control (MIM2016), 12 49,
	pp. 1620-1625, Troyes, France, 2016.
	Congrès internationaux avec résumés étendus
	• Yipeng Huang, Andréa Cynthia Santos, Christophe Duhamel, Disruptions management Chapitre 4 -Méthodes pour résoudre URND et MRND
	in multidirectional road networks, in: Proceedings of the 9th Triennial Symposium on en mono-et bi-objectif
	Transportation Analysis (TRISTAN16), 4p. Oranjestad, Aruba, 2016. Le chapitre est dédié aux méthodes exactes et approchées proposées pour résoudre URND
	et MRND en mono-et bi-objectif.
	Tout d'abord, nous présentons une heuristique d'orientation des graphes reposant sur
	l'algorithme DFS. L'utilisation du DFS pour orienter des graphes a été proposée initialement
	Boyce & Janson (1980) se consacre spécialement au NDP discret en minimisant le coût par Roberts (1978) et l'algorithme conçu dans cette thèse est une extension de son idée. À
	total de déplacement, ce qui est en relation avec l'un des objectifs de RND. Les modèles partir d'un sommet de départ, le parcours en profondeur a pour but de visiter tous les
	mathématiques sont proposés avec des expérimentations effectuées sur une instances de sommets en utilisant les relations d'adjacence. Chaque sommet visité est marqué comme
	Congrès internationaux avec communications orales • Yipeng Huang, Andréa Cynthia Santos, Christophe Duhamel, Heuristics for the bi-objective Unidirectional Road Network Design Problem with Disruptions, in: Annual 10 sommets. De plus, Yang & Bell (1998) étudie un modèle générique à deux niveaux pouvant couvrir de nombreux problèmes de prise de décision dans le contexte de NDP. Il peut surtout être appliqué pour des problèmes considérant la planification soumise à des "trouvé" et un sommet dont tous les voisins sont visités est marqué comme "complètement G 1 obtenu par suppression des arcs bloqués. Nous proposons alors le modèle mathématique visité". Une visite signifie la propagation d'un sommet i à un sommet voisin j en passant pour URND ci-dessous: par l'arête (i, j). Cette dernière peut alors être orientée selon le sens de la visite. De plus,
	budgets d'investissement. Ensuite, Feremans et al. (2003) étudie une généralisation de NDP un sommet est marqué comme complètement visité si toutes les arêtes liées sont orientées. workshop of the EURO working group on Vehicle Routing and Logistics optimization en utilisant le regroupement des sommets afin de classifier des problèmes spécifiques en min c 1 = γ ij y od ij (A.1) Un sommet déjà visité peut être visité de nouveau, tant qu'il n'est pas complètement visité. (VeRoLog), p140. Nantes, France, 2016. deux catégories: des problèmes de couverture dont les solutions utilisent tous les groupes (o,d)∈P (i,j)∈A 1 Cependant, au lieu de terminer quand tous les sommets sont complètement visités, comme
	min c 2 =	x ij	s.t.	(A.2)
	(i,j)∈A 1

• Yipeng Huang, Andréa Cynthia Santos, Christophe Duhamel, Heuristiques pour le problème de reconfiguration des réseaux urbains suite à des interruptions routières, in:

Actes du 19ème congrès de la société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF). 2p. Lorient, France, 2018.

• Yipeng Huang, Andréa Cynthia Santos, Christophe Duhamel, Managing predictable and unpredictable disruptions on road networks, in: Int'l Conference on Intelligent Transportation Engineering and Smart City

(ITESC 2017), Guilin, China, 2017. d

Néanmoins, plusieurs contre-exemples sur des graphes particuliers sont trouvés par

[START_REF] Jirásek | On a certain class of multidigraphs, for which reversal of no arc decreases the number of their cycles[END_REF]

,

[START_REF] Thomassen | Counterexamples to Ádám's conjecture on arc reversals in directed graphs[END_REF][START_REF] Jirásek | Arc reversal in nonhamiltonian circulant oriented graphs[END_REF]

. Récemment, l'étude de

[START_REF] Bogdanowicz | On arc reversal in balanced digraphs[END_REF]

indique que, dans un multigraphe équilibré, orienté et sans boucles, n'importe quel arc renversé engendre la diminution des cycles élémentaires non-nécessaires.

Au niveau de NDP, l'étude

[START_REF] Magnanti | Network Design and Transportation Planning: Models and Algorithms[END_REF]

est considérée comme un point d'entrée dans le domaine. Elle propose une classification du problème en trois niveaux: stratégique, tactique et opérationel, ce qui correspondent aux différents points de vue pour la prise de décision. Les auteurs révisent aussi des problèmes divers selon le type de contraintes, avec un modèle générique proposé pour le NDP discret. Ensuite, les méthodes d'optimisation sont aussi détaillées en indiquant que les heuristiques de l'époque sont capables de traiter des instances dont la taille monte jusqu'à 50 sommets et 150 arcs.

de sommets et des problèmes opposés, de non-couverture. Des exemples généralisant les problèmes connus sont présentés. D'autres travaux sur le NDP tels que

[START_REF] Fernandez | Equilibrium predictions in transportation markets: The state of the art[END_REF]

,

[START_REF] Boyce | Urban transportation network-equilibrium and design models: recent achievements and future prospects[END_REF]

,

[START_REF] Friesz | Transportation network equilibrium, design and aggregation: Key developments and research opportunities[END_REF]

,

[START_REF] Cascetta | Transportation Systems Engineering: Theory and Methods[END_REF]

et Farahani et al. (2013), dans lesquelles deux noeuds i, j L'objectif de RND est de trouver une orientation pour un réseau de transport en assurant qu'il soit fortement connexe, en prenant les interruptions en compte. Deux critères de minimisation sont pris en compte: (i) la distance totale entre toute paire de noeuds (c 1 ) et (ii) le nombre d'arcs renversés (c 2 ). Le renversement d'arcs est admis comme une opération pour restorer la forte connexité (le cas échéant) et éventuellement réduire la distance totale. URND s'adresse aux réseaux des rues lorsqu'elles sont seulement à sens unique. C'est souvent le cas dans un centre-ville ou dans un centre historique, où la gestion pratique des interruptions peut rencontrer des difficultés. Un tronçon bloqué peut impacter plusieurs autres axes puisqu'il faut souvent emprunter un chemin de déviation beaucoup plus long que celui prévu. En prenant le graphe simple G 1 pour modéliser URND, l'objectif c 1 est prouvé NP-difficile dans Burkard et al. (1999). La minimisation de c 2 est-elle polynomiale d'après Bang-Jensen & Gutin (2008). Par conséquent, bi-URND est NP-difficile. Supposons l'ensemble des paires origine-destination (paires O-D) P = {(o, d)|o, d ∈ V 1 , o = d} et l'ensemble B 1 des p arcs bloqués. Comme indiqué précédent, H 1 est le sous-graphe de dans DFS original, la condition d'arrêt de notre algorithme est que toutes les arêtes soient orientées. La complexité reste donc O(n + m) où les nombres de sommets et d'arêtes sont n et m respectivement. Par ailleurs, pour piloter les sens de visite, l'heuristique admet un Finalement, BRKGA n'applique pas une vraie mutation comme dans les implémentations classiques de l'Algorithme Génétique. À la place, à la fin de chaque génération, une partie de la nouvelle population est composée par des chromosomes arbitraires appelés mutants. Notons que toutes les opérations dans BRKGA sont indépendantes du problème donné, sauf la partie pour décoder des chromosomes en solutions spécifiques. Ainsi, c'est une métaheuristique assez générique pouvant être appliquée dans des domaines de recherche divers. Des applications spécifiques sont détaillées notamment dans Stefanello et al. (2017). Avec l'heuristique d'orientation des graphes présentée précédemment, il est possible de considérer le vecteur des clés aléatoires comme un vecteur des poids associés aux noeuds d'un graphe. Ainsi, un chromosome de BRKGA peut être décodé en une orientation d'un graphe donné. Ensuite, pour évaluer la valeur c 1 , nous appliquons l'algorithme de Dijkstra (Dijkstra (1959)), adapté pour calculer la somme des distances des plus courts chemins entre chaque paire de noeud. ILS L'idée d'une recherche locale (Local Search) est de prendre une seule solution initiale et d'examiner ses voisins définis par des changements spécifiques. Souvent dans le cadre d'une approche gloutonne, la procédure sélectionne une des voisins améliorant, se déplace optimales.

  ainsi que leur évaluation. Pour un graphe de m arcs, chaque chromosome de notre NSGA-II est composé de m gènes booléens (allèle ∈ {0, 1}), chacun indiquant l'état de renversement d'un arc par rapport à son état initial dans le graphe entré. Par conséquent, une Le but des expérimentations sur les métaheuristiques proposées est de tester leur performance en termes de qualité des solutions et de temps d'exécution. Les aspects mono-et bi-objectif de URND et MRND sont analysés. En plus des instances traitées par les modèles via CPLEX, nous avons généré d'autres instances de taille plus grande, surtout pour les métaheuristiques. Également, un ensemble d'instances construites à partir du réseau routier de la ville de Troyes est proposé afin d'étudier le comportement des méthodes sur la résolution des problèmes proches de la réalité. dans l'optimisation de c 2 . Le comportement de ces deux méthodes est similaire sur les instances réelles. ILS est globalement plus performante que BRKGA au niveau de la qualité avec un temps de calcul beaucoup plus haut. Un extrait des résultats numériques est présenté dans la Table A.1. De plus, la performance de NSGA-II est aussi bonne pour bi-URND que pour bi-MRND. Pour les instances que la méthode -constraint ne peut pas traiter, les solutions non-dominées trouvées par l'ensemble des trois méthodes sont combinées pour simuler un front de Pareto optimal, noté BKS (Best Known Solutions). Ceci est surtout fait pour construire une base de comparaison pour l'analyse. Sur ces instances, ILS a la meilleure performance parmi les trois métaheuristiques. Les fronts qu'elle retourne sont très proches de BKS dans la plupart des cas. Des exemples se trouvent dans Table A.2. La gestion du trafic urbain est très compliquée dans le monde réel, souvent à cause d'une capacité du réseau insuffisante qui ne correspond pas à la demande du déplacement Table A.2: Exemple des résultats de l'optimisation bi-objectif des habitants. La situation devient encore plus complexe quand certains axes critiques sont perturbés par des interruptions routières. Par exemple, dans le réseau de transport de la ville de Troyes, il y a eu environ 8000 arrêtés municipaux en 2014, gérés manuellement par des ingénieurs de trafic urbain, soit 22 problèmes par jour. Un des défis est de trouver des

	Instance	-constraint Q HV	BRKGA t(s) Q HV	t(s) Q	ILS HV	NSGA-II t(s) Q HV	t(s)
	5x5-b1	15 0.89 3769.28 12 0.80 87.32	9 0.87 42.28 11 0.80 62.21
	5x5-b2	13 0.90 1835.61 13 0.87 87.99	7 0.88 30.45 11 0.90 64.15
	orientation décodée peut être non fortement connexe mais elle sera pénalisée. D'après les tests 6x6-b1 12 0.88 (BKS) 17 0.82 716 10 0.88 133 11 0.78 161
	préliminaires, toutes les solutions sont gardées, mais les solutions infaisables receveront une pénalisation par l'évaluation. Elles seront donc moins favorisées par rapport aux solutions fortement connexes. 6x6-b6 7006 35 3894.85 6394 8.74 7006 19 7.29 7006 35 6.14 Résultats numériques Instance CPLEX BRKGA 6x6-b2 15 0.78 (BKS) 17 0.68 485 13 0.76 126 14 0.62 161 ILS c 1 * c 2 t(s) LR Gap(%) c 1 * c 2 t(s) c 1 * c 2 8x8-b1 17 0.94 (BKS) 33 0.87 4556 15 0.93 2158 23 0.82 732 t(s) 5x5-b4 3032 23 182.74 2636 13.06 3032 23 2.68 3032 13 8x8-b2 15 0.92 (BKS) 22 0.88 3474 10 0.86 2024 28 0.87 716 2.82 5x5-b6 3116 4 253.86 2672 14.25 3140 28 3.35 3116 4 troyes-v58-b1 1 7 0.90 (BKS) 15 0.77 2230 17 0.90 4754 21 0.50 1183 1.64 6x6-b4 ≤ 6820 -7200 5956 12.67 6780 35 10.94 6854 9 8.34 troyes-v58-b2 16 0.94 (BKS) 19 0.84 1553 15 0.94 3413 27 0.61 1205
	12x12-b4 12x12-b6	LP read OOM		188164 122 2989.76 195228 126 791.19	187690 111 1527.31 188124 116 1613.10
	troyes-v102-b4 troyes-v102-b6	LP read OOM	6718200 75 594.92 6601810 39 948.22 6895030 45 499.74 6643740 51 694.14
	parmi trois valeurs choisies à priori. De plus, chaque test est lancé 10 fois pour obtenir des
	Adaptation BRKGA au bi-objectif pour bi-URND et bi-MRND valeurs objectif moyennes.
	Pour URND et MRND mono-objectif, BRKGA et ILS traitent d'abord les instances
	BRKGA n'est initialement pas une méthode d'optimisation multi-objectif. résolues par CPLEX, puis les instances plus grandes. Les résultats sur les petites instances Des
	adaptations sont donc nécessaires afin qu'elle puisse fournir des fronts de Pareto indiquent que ILS a une meilleure performance que BRKGA en trouvant 9 optima sur
	pour bi-URND et bi-MRND. Pour ce faire, un pool de solutions est intégré dans la 10 instances pour c 1 et 10/10 pour c 2 . Avec un niveau similaire de temps de calcul,
	métaheuristique. Il sert à stocker toutes les solutions non-dominées par les autres solutions BRKGA trouve l'optimum pour 7 instances parmi 10 pour c 1 et 8/10 pour c 2 . Au niveau Chapitre 5 -Application: Optimal traffic Deviation
	courantes. La résolution consiste en deux procédures d'optimisation indépendantes, pour des grandes instances, les deux métaheuristiques peuvent trouver des solutions dans un System

c 1 puis c 2 . Au cours de chaque optimisation, on essaie d'insérer toutes les solutions dans le pool, en vérifiant la dominance. Finalement, les solutions du le pool sont triées et constituent comme un front de Pareto appoché. solutions Comme chaque métaheuristique est dépendante d'un certain nombre de paramètres, une phase de calibration est réalisée pour trouver de bonnes configurations. Dans BRKGA, les paramètres importants sont la racine aléatoire, le ratio entre la taille de population et le nombre de noeuds du graphe entré, le nombre maximal de générations et le nombre de générations sans amélioration. Dans ILS, la calibration est faite sur la racine aléatoire et le nombre d'itérations sans amélioration. Dans NSGA-II, le paramétrage s'effectue sur la racine aléatoire, le ratio entre la taille de population et le nombre d'arcs du graphe entré, le nombre maximal de générations, la probabilité de croisement et la probabilité de mutation. Sur un échantillon d'instances représentatives prédéfini, chaque paramètre de chaque méthode varie temps assez raisonable sur les instances avec jusqu'à 144 noeuds et 264 arcs. La qualité des solutions trouvées par ILS est généralement meilleure que celle de BRKGA. Cependant, le temps d'exécution d'ILS s'éleve plus rapidement avec l'augmentation de la taille d'instance, particulièrement Table A.1: Exemple des résultats de l'optimisation mono-objectif sur c 1 Pour bi-URND et bi-MRND, la notion d'hypervolume (Zitzler & Thiele (1998)) est empruntée pour mesurer la performance des métaheuristiques. La méthode exacte -constraint peut trouver les fronts de Pareto optimaux pour les petites instances de bi-URND jusqu'à 25 noeuds et 40 arcs. Pour les petites instances de bi-MRND, elle peut aller jusqu'à 25 noeuds et 80 arcs. Les trois méthodes approchées sont capables de trouver des fronts approximatifs. En général, BRKGA a une performance légèrement pire que les deux autres méthodes sur les instances de bi-URND alors qu'elle fonctionne très bien sur les instances de bi-MRND. De son côté, ILS trouve des fronts proches des optima pour bi-URND, mais elle rencontre des difficultés pour bi-MRND.

Table B .

 B Table B.2: Preliminary results of single-objective BRKGA parameter tuning on R brkga , with other parameters fixed: SD brkga = 2, I brkga = 100 and J brkga = 12 Table B.3: Preliminary results of single-objective BRKGA parameter tuning on I brkga , with other parameters fixed: SD brkga = 2, R brkga = 1.45 and J brkga = 12 Table B.4: Preliminary results of single-objective BRKGA parameter tuning on J brkga , with other parameters fixed: SD brkga = 2, R brkga = 1.45 and I brkga = 100 Instance Settings SD ils = 4,J ils = 6 SD ils = 4,J ils = 12 SD ils = 4,J ils = 24 Table B.5: Preliminary results of single-objective ILS parameter tuning on J ils Table B.6: Preliminary results of bi-objective BRKGA parameter tuning on SD brkga , with other parameters fixed: R brkga = 1.45, I brkga = 100 and J brkga = 12 Table B.7: Preliminary results of bi-objective BRKGA parameter tuning on I brkga , with other parameters fixed: SD brkga = 2, R brkga = 1.45 and J brkga = 12 Table B.8: Preliminary results of bi-objective BRKGA parameter tuning on I brkga , with other parameters fixed: SD brkga = 2, R brkga = 1.45 and I brkga = 100 9: Preliminary results of NSGA-II parameter tuning on SD nsgaii , with other parameters fixed: R nsgaii = 1.45, I nsgaii = 100, ρ c = 0.3 and ρ m = 0.03

											Settings Settings Settings Settings
	Instance Instance Instance Instance		R brkga = 1.25 J brkga = 6 SD brkga = 0 R nsgaii = 1.25					R brkga = 1.45 J brkga = 12 SD brkga = 2 R nsgaii = 1.45		R brkga = 1.75 J brkga = 24 SD brkga = 8 R nsgaii = 1.75
		Q Q	c 1 * c 1 * HV HV	c 2 c 2	t(s) δ ( c 1 )% t(s) δ ( c 1 )% t(s) δ ( HV )% t(s) δ ( HV )%	Q Q	c 1 * c 1 * HV HV	c 2 c 2	t(s) δ ( c 1 )% t(s) δ ( c 1 )% t(s) δ ( HV )% t(s) δ ( HV )%	c 1 * c 1 * Q Q	c 2 c 2 HV HV	t(s) δ ( c 1 )% t(s) δ ( c 1 )% t(s) δ ( HV )% t(s) δ ( HV )%
	3x3-b1 3x3-b1 3x3-b1 3x3-b1	246 246 2 0.00 2 0	2 0.125 2 0.078 1.34 4.90	0 0 0 0	246 246 2 0.00 2 0	2 0.188 2 0.188 1.25 6.76	0 0 0 0	246 246 2 2	0 0	2 0.172 2 0.296 0.86 6.91	0 0 0
	4x4-b2 4x4-b2 4x4-b2 4x4-b2	968 988 4 0.495 13.20 17 0.499 8 0.312 4 0.50 14.59	0 2 0 0	988 988 4 0.495 3 0.34 17.90 8 0.681 8 0.681 9.07	2 2 0 32	988 988 4 0.495 3 0.495 22.15 8 0.780 8 1.154 8.47	2 2 0
	5x5-b4 5x5-b4 5x5-b4 5x5-b4	3032 3032 7 0.802 46.37 23 2.184 23 1.482 5 0.70 38.11	0 0 11 14	3032 3032 9 0.818 28.34 23 2.618 23 2.618 8 0.76 45.51	0 0 9 7	3058 3032 8 0.83 27.82 22 3.697 23 3.915 5 0.831 58.77	1 0 8
	3x3-b2-25 3x3-b2-25 3x3-b2-25 3x3-b2-25	250 250 1 0.00 1 0	2 0.140 2 0.093 1.13 6.55	0 0 0 0	250 250 1 0.00 1 0	2 0.204 2 0.204 1.05 7.16	0 0 0 0	250 250 1 1	0 0	2 0.187 2 0.343 1.08 8.49	0 0 0
	4x4-b1-75 4x4-b1-75 4x4-b1-75 4x4-b1-75	716 716 8 0.647 8 0.74 33.63 7 0.734 7 0.484 7.11	0 0 1 5	716 716 8 0.647 8 0.65 41.45 7 1.001 7 1.001 6.80	0 0 1 0	716 716 8 0.647 8 0.638 53.81 7 1.060 7 1.653 6.66	0 0 1
	5x5-b1-50 5x5-b1-50 5x5-b1-50 5x5-b1-50	2296 2296 14 0.726 37.67 15 1.982 16 1.263 13 0.74 75.55	0 0 10 2	2296 2296 14 0.727 39.05 16 2.719 16 2.719 13 0.75 91.20	0 0 11 0	2296 2296 17 0.74 39.83 16 2.776 15 4.414 15 0.786 121.15	0 0 9
	Best Best Best Best	14 13	246 246	2 0.125 2 0.078 0 1.131 0 4.899	0 0 0 0	14 13	246 246	2 0.188 2 0.188 0 1.046 0 6.761	0 0 0 0	246 246 17 15	2 0.172 2 0.296 0 0.858 0 6.911	0 0 0
	Worst Worst Worst Worst	3032 3032 1 0.802 46.368 23 2.184 23 1.482 1 0.741 75.551	0 2 11 14	3032 3032 1 0.818 39.047 23 2.719 23 2.719 1 0.761 91.197	2 2 11 32	3058 3032 1 0.83 39.826 22 3.697 23 4.414 1 0.831 121.15	2 2 9
	Average 1251.33 11.00 0.94 Average 1254.67 9.67 0.62 Average 6.00 0.45 17.80 Average 5.50 0.45 28.89	0 1254.67 9.67 1.235 0 1254.67 9.67 1.235 4 6.33 0.45 14.26 3 5.83 0.42 35.00	0 1259.00 9.50 1.445 0 1254.67 9.50 1.963 3 6.67 0.45 14.12 6 5.67 0.46 45.21	0 0 3
											Settings Settings Settings
	Instance Instance Instance			I brkga = 50 I brkga = 50 SD nsgaii = 2					I brkga = 100 I brkga = 100 SD nsgaii = 4		I brkga = 150 I brkga = 150 SD nsgaii = 8
		Q Q	c 1 * HV HV	c 2	t(s) δ ( c 1 )% t(s) δ ( HV )% t(s) δ ( HV )%	Q Q	c 1 *	HV HV	c 2	t(s) δ ( c 1 )% t(s) δ ( HV )% t(s) δ ( HV )%	c 1 * Q Q	c 2 HV HV	t(s) δ ( c 1 )% t(s) δ ( HV )% t(s) δ ( HV )%
	3x3-b1 3x3-b1 3x3-b1	2 2	246 c 1 *	0 0	2 0.171 c 2 t(s) δ ( c 1 )% 0 1.11 0 6.76 0	2 2	246 c 1 *		0 0	2 0.188 c 2 t(s) δ ( c 1 )% 0 1.15 0 5.82 0	246 c 1 * 2 2	0 0	2 0.192 c 2 t(s) δ ( c 1 )% 0 1.16 0 5.69
	4x4-b2 3x3-b1 4x4-b2 4x4-b2	988 246 4 0.495 3 0.339 17.90 8 0.577 2 0.14 8.13	2 0 0 32	988 246 4 0.495 4 0.495 18.53 8 0.681 2 0.23 8.07	2 0 0 0	988 246 4 0.495 2 0.295 18.17 8 0.787 2 0.44 8.14	2	0 0
	5x5-b4 4x4-b2 5x5-b4 5x5-b4	3032 968 9 0.818 28.00 23 2.278 17 0.52 8 0.761 45.51	0 0 9 7	3032 968 9 0.818 27.64 23 2.418 17 1.55 7 0.781 46.60	0 0 9 4	3032 968 9 0.818 27.94 23 2.646 5 2.15 6 0.783 44.34	0	0 9
	3x3-b2-25 5x5-b4 3x3-b2-25 3x3-b2-25	250 3032 1 1	0 0	2 0.171 13 2.67 1.04 7.16	0 0 0 0	250 3032 1 1		0 0	2 0.204 13 3.82 1.05 7.74	0 0 0 0	250 3032 1 1	0 0	2 0.287 13 6.18 1.05 7.39	0	0 0
	4x4-b1-75 3x3-b2-25 4x4-b1-75 4x4-b1-75	716 250 8 0.647 8 0.651 41.45 7 0.889 7 0.14 6.65	0 0 1 0	716 250 8 0.647 8 0.8 42.34 7 1.001 7 0.25 6.70	0 0 1 8	716 250 8 0.647 10 0.727 40.95 7 1.058 7 0.44 6.72	0	0 1
	5x5-b1-50 4x4-b1-75 5x5-b1-50 5x5-b1-50	2296 716 14 0.727 38.91 16 2.403 7 1.22 13 0.753 91.20	0 0 11 0	2296 716 14 0.727 38.06 16 2.519 7 2.28 13 0.835 93.34	0 0 11 8	2296 716 14 0.727 39.06 16 2.793 7 3.57 15 0.827 94.32	0 11 0
	Best 5x5-b1-50 Best Best	246 2296 14 13	2 0.171 15 4.10 0 1.044 0 6.761	0 0 0 0	246 2296 14 13		2 0.188 15 6.97 0 1.046 0 5.819	0 0 0 0	246 2296 14 15	2 0.192 15 14.76 0 1.045 0 5.694	0	0 0
	Worst Best Worst Worst	3032 246 1 0.818 38.907 23 2.403 2 0.14 1 0.761 91.197	2 0 11 32	3032 246 1 0.818 38.057 23 2.519 2 0.234 1 0.835 93.335	2 0 11 8	3032 246 1 0.818 39.063 23 2.793 2 0.437 1 0.827 94.318	2 11 0
	Average 1254.67 9.67 1.08 Worst 3032 17 4.103 Average 6.33 0.45 13.97 Average 5.83 0.42 35.00	0 1254.67 9.67 1.169 0 3032 17 6.973 3 6.33 0.45 13.78 6 5.83 0.49 35.73	0 1254.67 9.67 1.294 0 3032 15 14.758 3 6.33 0.45 14.01 3 6.00 0.44 35.14	0	0 3
	Average 1251.33 10.17 1.46	0 1251.33 10.17 2.52	0 1251.33 8.17	4.59	0

Table B .

 B 10: Preliminary results of NSGA-II parameter tuning on R nsgaii , with other parameters fixed: SD nsgaii = 2, I nsgaii = 100, ρ c = 0.3 and ρ m = 0.03

								Settings
	Instance		I nsgaii = 50			I nsgaii = 100			I nsgaii = 150
		Q	HV	t(s) δ ( HV )%	Q	HV	t(s) δ ( HV )%	Q	HV	t(s) δ ( HV )%
	3x3-b1	2	0	3.43	0	2	0	6.91	0	2	0	11.08
	4x4-b2	3 0.495 10.75	0	3 0.495 22.15	0	4 0.495	33.63
	5x5-b4	6 0.794 27.41	3	5 0.831 58.77	8	10 0.81	86.18
	3x3-b2-25	1	0	4.26	0	1	0	8.49	0	1	0	12.79
	4x4-b1-75	9 0.707 26.30	9	8 0.638 53.81	2	8 0.651	81.17
	5x5-b1-50	18 0.835 61.65	8	15 0.786 121.15	7	12 0.731 182.32
	Best	18	0 3.432	0	15	0 6.911	0	12	0 11.076
	Worst	1 0.835 61.652	9	1 0.831 121.15	8	1 0.81 182.318
	Average 6.50 0.47 22.30	3 5.67 0.46 45.21	3 6.17 0.45	67.86

Table B .

 B 11: Preliminary results of NSGA-II parameter tuning on I nsgaii , with other

A medium city in France with about 61,000 inhabitants in

Credit to MSDN with origin at https://msdn.microsoft.com/en-us/library/bb259689.aspx

Contents

List of Figures

List of Tables

the three metaheuristics have some issues on particular instances. It is clear that ILS has a relatively mediocre performance on 3x3 and 4x4 instances. Since there are usually a very small number of solutions on the Pareto-optimal fronts, the loss of one or two nondominated

Appendices

Appendix A

Résumé étendu en français

Problèmes du réseau de transport urbain:

modèles, méthodes et application Chapitre 1 -Introduction L'augmentation de la population dans des zones urbaines a un fort impact sur les infrastructures de réseaux de transport, qui risquent souvent d'être saturées. Ceci implique aussi une croissance importante du flux de trafic urbain. Or, les réseaux routiers ne peuvent pas être étendus indéfiniment. L'influence de la concentration de population devient de plus en plus problématique et la situation devient encore plus compliquée lorsqu'il y a des interruptions sur des axes, telles que des arrêtés municipaux ou des accidents de véhicules.

Ces interruptions perturbent la circulation dans les secteurs concernés, voire cassent des chemins entre certains points.

Pour une arête pondérée, un coût γ ij est associé.

G 1 = (N 1 , A 1 ) est un graphe simple connexe orienté avec l'ensemble des noeuds N 1 et l'ensemble des arcs A 1 . Un arc non pondéré est représenté par une paire de noeuds (i, j) où

Enfin, un multigraphe connexe orienté est défini par G 2 = (N 2 , A 2 ) pour lequel les ensembles de noeuds et de multi-arcs sont dénotés N 2 et A 2 . Par définition, un multigraphe peut admettre plusieurs arcs entre chaque paire de noeuds. Ainsi, les arcs multiples entre