MB4 - Tournées de véhicule / Vehicle Routing 2

We address Single and Multi-depot roll-on roll-off vehicle routing problem for construction waste collection. We construct a specialized graph incorporating facility selection, client request types, and vehicle feasible operations. We propose a MILP formulation and apply it to an industrial case study. 

A classical approach for solving the Vehicle Routing Problem with Time Windows (VRPTW) relies on the column generation algorithm. This method typically involves solving the linear relaxation of a master problem, followed by a branch-and-price (BP) scheme to determine an integer solution. An alternative to BP consists of enumerating a set of new columns with a positive reduced cost lower than a gap γ, defined as the difference between the lower bound from the relaxation and a known upper bound. The Restricted Master Problem (RMP) is then enriched with these columns and solved as a mixed integer linear program (MILP). The efficiency of this approach depends heavily on the quality and the number of enumerated columns.

In this article, we present a machine learning-based approach that leverages statistical features extracted both locally, to characterize each post-enumerated column individually, and contextually, to capture interactions between the enumerated columns and those originating from the RMP relaxation. This model aims to identify and prioritize the selection of a subset of promising columns from the post-column generation enumeration.

The performance of our approach is evaluated on Solomon-type instances and compared against the exact post-enumeration method as well as the Top-K heuristic strategy based on reduced costs. Experimental results confirm that machine learning effectively captures the problem's structure to identify high-potential columns, offering significant gains in algorithmic efficiency. Finally, we demonstrate the robustness of these models through their ability to generalize to larger and out-of-distribution instances.

The vehicle routing problem with stochastic demands is a combinatorial optimization problem that arises in industrial applications such as waste management and facility replenishment. In these applications, one could aim at using a specific number of vehicles to better align with available resources, thereby including a fixed-fleet constraint in the problem. Standard column generation heuristics, that are usually efficient in this context, struggle to handle this additional constraint and cannot quickly produce good feasible solutions, mainly because the labeling algorithm used during the pricing becomes inefficient. We introduce a hybrid pricing heuristic that generates columns by combining a greedy component aiming for a quick generation of good columns, a reinforcement learning module to compute critical routes disregarded by the greedy construction, and a tabu search procedure to explore the search space around the generated routes. We embed our method within an existing restricted master heuristic framework: we first perform a column generation phase using our pricing heuristic to quickly generate a set of high-quality columns, which we then complete with a greedy randomized adaptive search procedure. The resulting restricted master problem is then solved as a mixed-integer program. We evaluate our approach on 40 benchmark instances with up to 60 customers and achieve an average optimality gap of 1% within a 5-minute total computation time. Our matheuristic also provides more best average solution cost and optimal solutions than the competing heuristics considered.

Keywords: vehicle routing, stochastic demands, restricted master heuristic, pricing heuristics, reinforcement learning

The Time-Dependent Traveling Salesman Problem with Time Windows (TD-TSPTW) poses a significant challenge in combinatorial optimization, primarily because incorporating real-world traffic conditions means path costs are no longer constant nor additive. This presentation introduces the application of the Peel and Bound (PnB) algorithm using Decision Diagrams (DD) to solve the TD-TSPTW. Traditional Branch and Bound approaches suffer from redundant computations by rebuilding the enumeration tree at each branch. In contrast, the PnB algorithm extracts and refines subgraphs directly from a shared DD, avoiding repeated work. We will detail the adaptation of PnB to handle dynamic time-dependent costs, highlighting the use of minimum guaranteed costs to maintain admissible lower bounds. Furthermore, we will explore massive arc filtering via time windows and Latest Departure Time , alongside iterative bound tightening techniques to guarantee optimality.