3 Presentations

• 
  10:30 AM - 10:55 AM

  A branch-price-and-cut algorithm for the multi-commodity two-echelon vehicle routing problem with time windows

  • Tayeb Mhamedi, presenter, Polytechnique Montréal
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Marilène Cherkesly, ESG UQÀM

  In this presentation, we address the multi-commodity two-echelon vehicle routing problem with time windows (MC-2E-VRPTW). In the MC-2E-VRPTW, first-echelon routes handle transportation of goods from depots to intermediate facilities (satellites) while second-echelon routes, departing from satellites, ensure that goods are being shipped to customers within their allowed time windows. Each customer's demand is available at a specific depot and is supplied by a single first-echelon vehicle. First, we propose a branch-price-and-cut algorithm to solve the MC-2E-VRPTW within which first-echelon routes are enumerated a priori while second-echelon routes are generated using column generation. To generate second-echelon routes, we consider one pricing problem per satellite that is solved by means of an ad hoc labeling algorithm that keeps track of the first-echelon routes used to supply the (partial) second-echelon routes considered. Second, we make use of effective deep dual-optimal inequalities to speed up the column generation process and apply known valid inequalities to strengthen the lower bounds. Finally, we report computational results obtained on instances from the literature with up to 100 customers and 3 satellites that we are able to solve to optimality.
• 
  10:55 AM - 11:20 AM

  A Framework for Efficient Vehicle Routing Problem Heuristics

  • Francesco Cavaliere, presenter, University of Bologna

  Vehicle Routing Problems (VRPs) are a class of combinatorial optimization problems with a wide range of applications. In the past decades, numerous heuristic and exact approaches have been proposed to solve various VRP variants. However, developing a unifying framework for VRP heuristics is complex due to the balance required between the generality of the approach and the specificity in exploiting problem characteristics. A successful framework proposed by Vidal et al. (2014) separated generic and variant-specific components of the algorithm. This separation helped to achieve a good compromise between efficiency and generality. However, the wide adoption of such a framework has been limited, possibly due to the absence of a public library to aid researchers with new heuristics ideas and techniques. The proposed project aims to extend this framework further, to generalize it to other classes of constraints and objective functions regarding inter-routes dependencies. The project will also study and develop a taxonomy of VRP constraints and apply the unifying approach to the algorithmic counterpart, presenting a framework able to help the development of meta-heuristics for a large class of VRPs.
• 
  11:20 AM - 11:45 AM

  Solution approaches for the Timber Transport Vehicle Routing Problem with Queuing considerations

  • Ala-Eddine Yahiaoui, presenter, Université Laval
  • Mikael Rönnqvist, Université Laval
  • Jean-François Audy, Université du Québec à Trois-Rivières

  The integration of queuing into the Timber Transport Vehicle Routing Problem (TTVRP) is an important topic. In addition to accurately estimate transportation costs and routing times, it also allows efficient scheduling of loading and unloading operations in harvest areas and sawmills.
  We propose several crafted algorithms to solve the TTVRPQ. The first is a rolling-horizon based heuristic inspired by a well-known method called ASICAM. The second is a Large Neighborhood Search (LNS) meta-heuristic, with adapted removal and repair heuristics. Finally, we propose a math-heuristic approach based on column generation, which aims to further improve the best solution obtained by the rolling horizon heuristic and the LNS. This hybrid approach starts from a pool of columns generated by either the rolling horizon heuristic or the LNS and attempts to generate new columns with negative reduced costs. The key feature of the math-heuristic is the incorporation of several pricing heuristics with polynomial (linear) complexity responsible of astutely finding new improving columns.
  To assess the performance of these solution approaches, we have generated new benchmark instances for the TTVRPQ based on real-life data provided by FORAC partners. We compared the results of both heuristic approaches, and we investigated the contribution of the column generation approach.