Traffic Engineering (TE) represents one of the most essential tools in modern telecommunication networks. The rapid growth of exchanged traffic has required tackling a known NP-hard problem called the Multi-Commodity Flow problem (MCF). Many studies in the literature have already considered different variants of this problem. In this paper, we propose a new way to use a double Dantzig-Wolfe decomposition formulation to improve the quality of the linear relaxation. We apply our method on the classical multi-commodity flow problem where the throughput acceptance is first maximized and then the routing cost is minimized. We provide a computational experiment and conduct an in-depth analysis of the algorithm based on realistic instances.

Demand-Responsive Transport (DRT) has grown over the last decade as an ecological solution to both metropolitan and suburban areas. It provides a more efficient public transport service in metropolitan areas and satisfies the mobility needs in sparse and heterogeneous suburban areas. Traditionally, DRT operators build the plannings of their drivers by relying on myopic insertion heuristics that do not take into account the dynamic nature of such a service. We thus investigate in this work the potential of a Demand Prediction Framework used specifically to build more flexible routes within a Dynamic Dial-a-Ride Problem (DaRP) solver. We show how to obtain a Machine Learning forecasting model that is explicitly designed for optimization purposes. The prediction task is further complicated by the fact that the historical dataset is significantly sparse. We finally show how the predicted travel requests can be integrated within an optimization scheme in order to compute better plannings at the start of the day. Numerical results support the fact that, despite the data sparsity challenge as well as the optimization-driven constraints that result from the DaRP model, such a look-ahead approach can improve up to 3.5% the average insertion rate of an actual DRT service.

We study the family of problems of partitioning and covering a graph into/with a minimum number of relaxed cliques. Relaxed cliques are subsets of vertices of a graph for which a clique-defining property—for example, the degree of the vertices, the distance between the vertices, the density of the edges, or the connectivity between the vertices—is relaxed. These graph partitioning and covering problems have important applications in many areas such as social network analysis, biology, and disease-spread prevention. We propose a unified framework based on branch-and-price techniques to compute optimal decompositions. For this purpose, new, effective pricing algorithms are developed, and new branching schemes are invented. In extensive computational studies, we compare several algorithmic designs, such as structure-preserving versus dichotomous branching, and their interplay with different pricing algorithms. The final chosen branch-and-price setup produces results that demonstrate the effectiveness of all components of the newly developed framework and the validity of our approach when applied to social network instances.

International audience

This paper deals with the multiple vehicle balancing problem (MVBP). Given a fleet of vehicles of limited capacity, a set of vertices with initial and target inventory levels and a distribution network, the MVBP requires to design a set of routes along with pickup and delivery operations such that inventory is redistributed among the vertices without exceeding capacities, and routing costs are minimized. The MVBP is NP‐hard, generalizing several problems in transportation, and arising in bike‐sharing systems. Using theoretical properties of the problem, we propose an integer linear programming formulation and introduce strengthening valid inequalities. Lower bounds are computed by column generation embedding an ad‐hoc pricing algorithm, while upper bounds are obtained by a memetic algorithm that separate routing from pickup and delivery operations. We combine these bounding routines in both exact and matheuristic algorithms, obtaining proven optimal solutions for MVBP instances with up to 25 stations.

Caio Corro, Joseph Le Roux, Mathieu Lacroix, Antoine Rozenknop, Roberto Wolfler Calvo. Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2016.

Shortest paths on road networks can be efficiently calculated using Dijkstra's algorithm (D). In addition to roads, multi-modal transportation networks include public transportation, bicycle lanes, etc. For paths on this type of network, further constraints, e.g., preferences in using certain modes of transportation, may arise. The regular language constrained shortest path problem deals with this kind of problem. It uses a regular language to model the constraints. The problem can be solved efficiently by using a generalization of Dijkstra's algorithm (D_RegLC). In this paper we propose an adaption of the speed-up technique uniALT, in order to accelerate D_RegLC. We call our algorithm SDALT. We provide experimental results on a realistic multi-modal public transportation network including time-dependent cost functions on arcs. The experiments show that our algorithm performs well, with speed-ups of a factor 2 to 20.

The paper presents a new approach to solve the unate covering problem based on exploitation of information provided by Lagrangean relaxation. In particular, main advantages of the proposed heuristic algorithm are the effective choice of elements to be included in the solution, cost-related reductions of the problem, and a good lower bound on the optimum. The results support the effectiveness of this approach: on a wide set of benchmark problems, the algorithm nearly always hits the optimum and in most cases proves it to be such. On the problems whose optimum is actually unknown, the best known result is strongly improved.

The classical solving approach for two-level logic minimisation reduces the problem to a special case of unate covering and attacks the latter with a (possibly limited) branch-and-bound algorithm. We adopt this approach, but we propose a constructive heuristic algorithm that combines the use of Binary Decision Diagrams (BDDs) with the Lagrangian relaxation. This technique permits us to achieve an effective choice of the elements to include in the solution, as well as cost-related reductions of the problem and a good lower bound on the optimum. The results support the effectiveness of this approach: on a wide set of benchmark problems, the algorithm nearly always hits the optimum, and in most cases proves it to be so. On the problems whose optimum is actually unknown, the best known result is strongly improved.