4 Presentations

• 
  03:40 PM - 04:05 PM

  Generic approach to solve vehicle routing problems with synchronized visits

  • Ala-Eddine Yahiaoui, presenter, Université Laval

  Keywords : vehicle routing problem, synchronization, post-optimization, set covering formulation, cutting plane, separation procedure.
  Set covering formulations has been extensively used as a post-optimization phase when solving vehicle routing problems. The basic idea is to store the set of routes generated by heuristics and meta-heuristics during an initial phase, then perform a route-recombination phase to find the set of routes yielding the best feasible solution. This solution approach has proven its effectiveness on many variants of VRP.
  However, the application of such approach on variants of VRP with synchronized visits has been scarcely explored. This is mainly due to the fact that combining routes with interdependencies may incur delays on some visits. These delays may cause some time windows violations in the subsequent visits. Moreover, combining several routes may also result in a solution with cross-synchronization issue.
  To overcome these issues when applying set covering formulations on VRPs with synchronized visits, we propose an iterative cutting plane approach with efficient cut generation procedures that produces purely combinatorial inequalities associated with minimal/irreducible subset of incompatible routes in the solution found by a basic set covering formulations. Those cuts are added to the basic formulation and solved again. This iterative process is carried out until a feasible solution for the original problem is found. We highlight the performance of our approach by showing preliminary results using benchmark instances from the literature.
• 
  04:05 PM - 04:30 PM

  A Pickup and Delivery Problem with Multiple Time Windows and Resource Constraints

  • Mohammad Moshref-Javadi, presenter, University of Illinois at Urbana-Champaign
  • Ahmad Hemmati, University of Bergen
  • Preben Johannessen, University of Bergen

  This paper proposes an efficient Adaptive Large Neighborhood Search (ALNS) algorithm for a pickup and delivery problem with multiple time windows. This problem aims to schedule routes of vehicles to pick up orders from suppliers and deliver them to factory locations. The problem considers various new constraints, such as a non-conventional cost structure and dock constraints at factories. The problem is formulated as a mathematical model. The proposed algorithm incorporates several heuristics to effectively search the solution space. The algorithm is evaluated on several problem instances created based on a case study from a major manufacturer in Europe. The numerical results show the effectiveness and consistency of the algorithm in obtaining promising solutions to the problem.
• 
  04:30 PM - 04:55 PM

  Compact Formulations for the Robust Vehicle Routing Problem with Time Windows under Demand and Travel Time Uncertainty

  • Rafael Ajudarte de Campos, presenter, Department of Operations and Decision Systems, Université Laval
  • Pedro Munari, Department of Production Engineering, Federal University of São Carlos, Brazil
  • Leandro C. Coelho, Université Laval

  We provide new compact formulations for the robust vehicle routing problem with time windows (RVRPTW) under cardinality- and knapsack-constrained demand and travel time uncertainty. Particularly, we propose the first compact model that addresses the RVRPTW under travel time uncertainty considering the knapsack uncertainty set. Our models use different types of constraints to control time propagation based on the well-known Miller-Tucker-Zemlin and single commodity flow constraints. The latter has not been explored even for the deterministic variant of the problem, so we first state them explicitly. We also design tailored branch-and-cut algorithms based on the proposed formulations, which rely on a dynamic programming algorithm to verify if a solution is robust feasible with respect to demand and time, and use specific as well as standard separation methods found in the literature. We present detailed computational results on RVRPTW instances, compare the performance of our models and algorithms, and evaluate the impact and advantages of implementing each studied uncertainty set.
• 
  04:55 PM - 05:20 PM

  Tri-level heuristic to solve large-scale vehicle routing problem

  • Abdelhakim Abdellaoui, Polytechnique Montréal
  • Issmail El Hallaoui, GERAD, Polytechnique Montréal
  • Loubna Benabbou, UQAR
  • Abdelhakim Abdellaoui, presenter, Polytechnique Montréal

  Efficient vehicle routing is a critical challenge for delivery management companies. This paper proposes an improved approach for solving real-world and large-scale vehicle routing problem (VRP) using an adapted clustering heuristic. Our proposed framework consists of three stages. At the first level, a constrained clustering algorithm generates feasible clusters of customers. This stage is endowed with three enhancement tools to achieve near-optimal clusters, namely: a multi-start procedure for initial centroids, a customer assignment coefficient, and a self-adjustment mechanism for choosing the number of clusters. At the second level, a traveling salesman problem (TSP) solver is employed to optimize the order of customers within each cluster. Finally, at the third level, we introduce a re-optimization process that utilizes a splitting and relinking procedure, which calls upon solving a linear and integer programming model to further improve the obtained routes. This novel approach diverges from the classical cluster-first, route-second methods and provides near-optimal results regarding the objective function and the computational time, as evidenced by experiments conducted on well-known benchmark instances. Moreover, we validate the effectiveness of our approach through experimentation on real-world and large-scale instances provided by an industrial partner. These experiments demonstrate significant results in terms of solution quality and computational efficiency, offering important advancements in solving VRP for practical applications.