4 présentations

• 
  10h30 - 10h55

  Consistent Vehicle Routing Problem with Simultaneous Delivery and Pick-up and Time Windows

  • Diego Bravo, prés., Universidad Católica del Norte
  • Hernán Lespay, Universidad Católica del Norte

  This work proposes a Mixed-Integer Linear Programming (MILP) formulation for the Consistent Vehicle Routing Problem with Simultaneous Delivery and Pick-up and Time Windows (ConVRPSDPTW) for multi-periods. Besides standard VRPTW constraints, ConVRPSDPTW determines an efficient set of routes, where each customer has both a delivery and a pick-up demand to be satisfied, simultaneously. Moreover, the routes are constrained by vehicle capacity, time windows, and service consistency, meaning assigning each set of customers just one driver to fulfill their orders during the whole planning horizon and making it impossible to decompose the model into several independent one-period problems. The model is employed to minimize operational costs: number of vehicles and total travel time. The computational experiments were executed utilizing benchmark instances constructed from Solomon’s VRPTW instances and were solved by a commercial solver.

• 
  10h55 - 11h20

  Deep Reinforcement Learning for One-to-One Single Vehicle Pickup and Delivery Problems

  • King-Tong Wong, prés., University of Edinburgh Business School
  • Tsung-Sheng Chang, National YangMing ChiaoTung University
  • Jamal Ouenniche, University of Edinburgh Business School
  • Joosung Lee, Sungkyunkwan University

  This paper proposes new Deep Reinforcement Learning (DRL) methods to address the Single Vehicle Routing Problem with Pickups and Deliveries (SVRPPD). The SVRPPD is a challenging combinatorial optimization problem with significant real-world applications. Its typical mathematical formulation and existing solution methods are presented. The basics of Reinforcement Learning (RL) and Deep Learning are then introduced, and the SVRPPD is reformulated as a RL problem. Several DRL algorithms including new proposals are discussed and their performance is compared to an exact solution provided by Gurobi. This research potential contributions include employing DRL to solve SVRPPD and comparing various DRL algorithms including new proposals, providing insights for future research and practical applications in transportation and logistics optimization.

• 
  11h20 - 11h45

  Generalized Dial-A-Ride Problem on Road Networks with Time-dependent Travel Times

  • Bahman Bornay, prés., Polytechnique Montreal, CIRRELT
  • Michel Gendreau, Polytechnique Montréal
  • Bernard Gendron, Université de Montréal, CIRRELT

  Classical Dial-a-Ride problem (DARP) is typically formulated on a complete customer-based graph, where vertices represent customer locations and arcs denote the shortest path between them. Further, a unique pair of pickup and dropoff (PD) nodes is associated with each request. We argue that these models might not be responsive to the contemporary transportation needs, hence leading to suboptimal solutions. First, in reality, an actual road network connects customer locations, where the speed on links changes over time, resulting in multiple shortest paths within various intervals throughout the day. Moreover, in modern logistics, flexibility is no longer a feature but a necessity. To be competitive in today’s market, carrier companies and on-demand transit providers may need to offer clients a selection of potential pickup and dropoff locations, each with its own time windows, based on availability and constraints. Despite this, the rich vehicle routing problem body of knowledge does not entail any article which explicitly investigates the combination of the aforementioned aspects. Hence, we formally introduce a new class of DARP with added layers of complexity described earlier, termed Generalized Dial-A-Ride Problem (GDARP). This model assumes a set of potential pickup and dropoff locations for each transit request, studied on real road networks with time-dependent travel times (TD-GDARPRN). We present a Mixed-Integer Programming (MIP) model and formulate the scheduling problem for each vehicle as a Dynamic Programming (DP) problem. To solve the DP to optimality, we propose two algorithms: one employing forward propagation linearly, and the other utilizing a binary tree data structure in both recursive and iterative methods. Solving the DP for each route yields an optimal solution to the NP-Hard, Optimal Start Time Problem (OSTP). Additionally, we present an efficient DP-embedded hybrid adaptive large neighbourhood search (ALNS) metaheuristic that generates high-quality solutions.

• 
  11h45 - 12h10

  Branch-and-price-and-cut algorithm for a practical dial-a-ride problem

  • Mohammad Karimi, prés., Polytechnique Montréal - CIRRELT
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Michel Gendreau, Polytechnique Montréal

  The Dial-a-Ride Problem (DARP) involves designing vehicle routes and schedules for customers with specified pickup and delivery requests between their origins and destinations. The objective is to minimize the cost of vehicle routes while adhering to constraints such as vehicle capacity, time windows, and maximum ride time. This paper proposes a branch-and-price-and-cut (B&P&C) algorithm to address a variant of DARP where both customers and the vehicle fleet are heterogeneous, alongside practical constraints like budget, breaks with different configurations, and maximum run duration. The algorithm employs a column generation approach at each node in the branching tree, decomposing the problem into a master problem and subproblems. Exact and heuristic versions of the labeling algorithm are developed to efficiently handle these subproblems. The effectiveness of the algorithm is assessed through a real-world case study involving 849 heterogeneous passengers and over 70 available vehicles, represented as contracts with varying cost structures. Notably, this instance marks the largest problem size addressed using an exact B&P&C algorithm to our knowledge. Results demonstrate that the proposed algorithm achieves highly competitive solution quality.