ABSTRACT. Solving the TSP is a challenge that has been addressed by most exact and heuristic solving methods. In constraint programming, the most efficient model is based on a Lagrangian relaxation, more precisely the 1-tree relaxation. We show how to model this Lagrangian relaxation efficiently in constraint programming and the associated filtering algorithms. Then, we introduce filtering algorithms based on the graph. First, the k-cutset constraint imposes that any solution contains a strictly positive and even number of elements in each cutset. Then, the mandatory Hamiltonian path constraint is based on the local search k-opt algorithm. If a path of mandatory edges is not optimal (i.e. it exists a k-opt), then it cannot belong to any optimal solution. An experimental part will show that these algorithms allow to speed up by an order of magnitude the solving times. Finally, we show the limits of the current model and the remaining challenges.

ABSTRACT. Finding provably optimal solutions for vehicle routing problems requires the use of strong relaxations of the problem. These relaxations can provide dual bounds for integer programming solvers or improve constraint propagation for constraint programming solvers. We discuss the use of decision diagrams for developing scalable relaxations for vehicle routing problems. We start with the decision diagram representation for the traveling salesperson problem (TSP) with variants including time windows and time-dependent travel times. We show how this relaxation can be strengthened by adding a Lagrangian relaxation. Next we discuss more general vehicle routing problems for which we allow the relaxed decision diagram to represent multiple routes simultaneously. The resulting dual bound can be strengthened via the process of column elimination, which iteratively removes infeasible routes from the diagram. The computational experiments demonstrate that decision diagram relaxations are competitive with or outperform the state-of-the-art on several classes of vehicle routing.

ABSTRACT. Computing a route is a fundamental problem in our society. The shortest path problem has been studied for many years and is one of the best-known problems in graph theory and operations research. A variant of this problem exists for public transit networks, with the need to modify the algorithms to take into account the temporality of public transit. Many algorithms exist, but new algorithms must be created because the needs of the users are changing. Nowadays with smartphones being everywhere, travelers want a fast and almost personalized response to a public transit request. Which can be quite complex especially in large and dense metropolitan networks. We highlight recent solutions from our company and the wider research field. One solution is a multi-objective algorithm, which uses precomputation to decrease the response time. This algorithm is based on a goal-directed search, so for a route between Nice and Cannes, the routes passing through Menton will be discarded. Using a multi-objective algorithm, multiple results will be outputted, however, only the criteria defined in the objective function will be used. Most users have specific preferences that are impossible to represent using an objective function, that is why other methods have been developed. One of those solutions is the application of the k shortest path problem to public transit networks, which enumerates the shortest paths between a starting point and an ending point. Their application to public transit networks provides with a very fast response time a large number of potentially interesting results.

ABSTRACT. In early 2022, Google launched a service called Cloud Fleet Routing that solves rich vehicle routing problems. Our customers' problems are very diverse: constraints such as driver breaks or maximum driving time, ill-defined goals such as route balancing, coming in all kinds of sizes. In this talk, we overview both the IT part i.e. how the service works, and OR part, i.e. the kinds of problems users want to solve. We present the expectations users have and how we help them use the service. We also highlight the differences between academic and industrial routing problems in terms of solution quality and solving time.

ABSTRACT. Data uncertainty is a common feature in practical transportation settings, exemplified by unknown travel times in vehicle routing problems, network disruptions in supply chains, and non-deterministic demands in location-based models. One of the key challenges in designing prescriptive tools in this context involves striking a balance between the representation of uncertainty and the tractability of the resulting optimization problems. In this master class, we will tackle this issue from a risk-hedging perspective, exploring routing and location models that impose safe probabilistic guarantees. These include chance-constrained methods, risk constraints such as conditional value-at-risk (CVaR) inequalities, network-based approximations, and connections with (distributionally) robust approaches. We will present examples to illustrate the trade-offs between conservatism and tractability, highlighting the challenges and opportunities in this field.