Get Complete Project Material File(s) Now! »

## Analysis of the formulations

The size of the formulation (GTDSPP) depends on several factors. Clearly, the size of the graph G plays a most important role, because some variables and constraints are defined for each node and arc that appear in the network. In the case of piecewise linear cost functions, the total number of breakpoints in the network is also important, as extra variables and constraints have to be added for each one of these breakpoints. If we assume that c(i, j, τi) is nonlinear, as is the case if we use the summation of Gaussiansmodel proposed in Section 1.2.2, then solution algorithms for MINLPs (23; 131; 132) typically add extra variables, depending on the expression of the cost function c. It is likely that, for a road network with millions of nodes and arcs, the resulting formulation (GTDSPP) would have several millions or billions of variables and constraints. Therefore, there is no hope of solving it to optimality with existing exact algorithms within the short time slots allowed by real-time applications. However, this formulation may be useful for practical purposes as a mean to study networks which are difficult to treat with Dijkstra’s algorithm, such as non-FIFO networks or networks with general nonlinear time-dependent costs, possibly restricting the size of the analyzed graph. Thismay allowto underline the differences between FIFOand non-FIFOscenarios, aswell as understandingwhichmodels aremore meaningful froma user point of view. We recall that at the beginning of this thesis it was not clear whether the real-world time-dependent data would satisfy the FIFO property or not, and it was not clear if it would be highly nonlinear or it could be modeled with piecewise linear functions. This is because data gathering andmanipulation was still in progress. Therefore, we wanted to have the possibility of studying general non-FIFO networks as a mean to verify the quality of the solutions found by simplifications of the problem. To do so, we investigated efficient algorithms to quickly find good (hopefully, optimal) solutions to both MILPs and MINLPs.

### Hierarchical speedup techniques for static road networks

Many hierarchical speedup techniques have been developed for the SPP on static graphs. The main idea is to preconstruct a graph hierarchy where each level is smaller then the previous one, i.e. it has fewer nodes; shortest paths queries start at the bottom level and are then carried out exploring the hierarchy levels in ascending order, so that most of the search is carried out on the topmost level. Since the number of nodes at each level shrinks rapidly as we progress upwards into the hierarchy, the total number of explored nodes is considerably smaller than in a plain appplication of Dijkstra’s algorithm (see Figure 1.3). Due to the inherent bidirectional nature of these algorithms, these approaches only work on static graphs.

#### Drawbacks of guarantee regions

The most evident drawback of the algorithm presented in this section is that we must use a very large approximation constant K in order to achieve a significant speedup during the computations. We have seen that in practice the solution quality does not deteriorate as much as K would allow, but from an industrial point of view an approximation guarantee ≥ 3 is not appealing. There is one additional major drawback, which is difficult to overcome: the space consumption to store guarantee regions is very large. Associating bit flags to each node is very expensive: elementary calculations show that, for a graph with 18M nodes such as the European road network (Section 5.1), 8GB ofmemory would allow only ≈ 60 clusters in the graph covering. In this case, each cluster would be very large, hence performance would significantly decrease. More efficient methods for identifying nodes belonging to a guarantee region could be devised, but, as discussed in Section 2.4.1, one has to be careful not to introduce too many false positives. In the end, we decided to try a different approach, in which the set of nodes to be explored is not predetermined and stored in memory, but is computed “on-the-fly” for each shortest path query. This way, there is no additional space consumption for the storage of guarantee regions.

**Dynamic cost updates**

Up to now, time-dependent routing algorithms assumed complete knowledge of the time-dependent cost functions on arcs. However, since the speed profiles onwhich these functions are based are generated using historical data gathered from sensors (or cams), it is reasonable to assume that also real-time traffic information is available through these sensors. Moreover, other technologies exist to be aware of traffic jams even without having access to real-time speed information (e.g., TMC1). In the end, a procedure to update the time-dependent cost functions depending on real-time traffic information would be desirable for practical applications.

The input required by the TDALT algorithm (Section 3.1) consists of the graph G with the associated arc cost functions and the distances to and from landmarks. As landmark distances are computed using the lower bounding function λ, it is clear that the preprocessing information, i.e. landmark distances, remain valid as long as λ = c, that is, λ bounds c frombelow. On road networks,

computing a lower bounding function which is necessarily valid can be easily done: it suffices to divide the length of the road segment that an arc represents by the maximum speed allowed on that type of road. Thus, as long as λ = c, the time-dependent cost functions can be updated with no additional required effort.

**Table of contents :**

**1 Introduction **

1.1 Motivation

1.2 Definitions and Notation

1.2.1 The FIFO property

1.2.2 Choice of the cost functions

1.3 Mathematical Programming Formulations for the TDSPP

1.3.1 Definition ofmathematical program

1.3.2 Formulation of the TDSPP

1.3.3 Analysis of the formulations

1.4 RelatedWork

1.4.1 Early history

1.4.2 Dijkstra’s algorithm

1.4.3 Label-correcting algorithm

1.4.4 Hierarchical speedup techniques for static road networks .

1.4.4.1 Highway Hierarchies

1.4.4.2 Dynamic Node Routing

1.4.4.3 Contraction Hierarchies

1.4.5 Goal-directed search: A∗

1.4.5.1 The ALT algorithm

1.4.6 The SHARC algorithm

1.5 Contributions

1.6 Overview

I CombinatorialMethods

**2 Guarantee Regions **

2.1 Definitions andmain ideas

2.2 Computing the node sets

2.3 Query algorithm

2.4 Implementation

2.4.1 Storing node sets

2.4.2 Computational analysis

2.4.3 Drawbacks of guarantee regions

**3 Bidirectional A∗ Search on Time-Dependent Graphs **

3.1 Algorithmdescription

3.2 Correctness

3.3 Improvements

3.4 Dynamic cost updates

**4 Core Routing on Time-Dependent Graphs **

4.1 Algorithmdescription

4.2 Practical issues

4.2.1 Proxy nodes

4.2.2 Contraction

4.2.3 Outputting shortest paths

4.3 Dynamic cost updates

4.3.1 Analysis of the general case

4.3.2 Increases in breakpoint values

4.3.3 A realistic scenario

4.4 Multilevel Hierarchy

**5 Computational Experiments **

5.1 Input data

5.1.1 Time-dependent arcs

5.2 Contraction rates

5.3 RandomQueries

5.3.1 Local Queries

5.4 Dynamic Updates

6 A Real-World Application

6.1 Description of the existing architecture

6.2 Description of the proposed architecture

6.2.1 Load balancing and fault tolerance

6.3 Updating the cost function coefficients

II Mathematical Formulation BasedMethods

**7 Improved Strategies for Branching on General Disjunctions **

7.1 Preliminaries and notation

7.2 A quadratic optimization approach

7.2.1 The importance of the normof λ

7.2.2 Choosing the set Rk

7.2.3 The depth of the cut is not always a goodmeasure

7.3 A MILP formulation to generate split disjunctions

7.3.1 Generating a pool of split disjunctions

7.4 Computational experiments: quadratic approach

7.4.1 Comparison of the differentmethods

7.4.2 Combination of severalmethods

7.5 Computational experiments: MILP formulation

**8 A Good Recipe for SolvingMINLPs **

8.1 The basic ingredients

8.1.1 Variable neighbourhood search

8.1.2 Local branching

8.1.3 Branch-and-bound for cMINLPs

8.1.4 Sequential quadratic programming

8.2 The RECIPE algorithm

8.2.1 Hyperrectangular neighbourhood structure

8.3 Computational results

8.3.1 MINLPLib

8.3.2 Optimality

8.3.3 Reliability

8.3.4 Speed

**9 Computational Experiments on the TDSPP **

9.1 Input data

9.2 Numerical experiments with the linear formulation

9.2.1 Formulation

9.2.2 Computational results

9.3 Numerical experiments with the nonlinear formulation

9.3.1 Formulation

9.3.2 Modifications to RECIPE

9.3.3 Computational results

III Conclusions and Bibliography

**10 Summary and Future Research **

10.1 Summary

10.2 Future research

**References**