4 Presentations

• 
  01:30 PM - 01:55 PM

  An efficient ruin-and-recreate heuristic for the time-dependent shortest path and vehicle routing problem

  • Rodrigo Ramalho, presenter, Universidade Federal da Paraíba, CIRRELT
  • Anand Subramanian, Universidade Federal da Paraíba (UFPB - Brazil)
  • Jacques Renaud, Université Laval, CIRRELT
  • Leandro C. Coelho, Université Laval

  In urban logistics, customers are spread across a geographical region that typically yields a dense graph. Travel times between customers are not constant and may vary throughout the day as traffic and congestion evolve. Indeed, at an urban level, different paths can be used to link two points, and different paths can be optimal at different times of the day. In the Time-Dependent Shortest Path and Vehicle Routing Problem (TDSPVRP), we consider several time intervals with different congestion levels. The goal is to design least-cost routes to serve customers with capacitated vehicles where the travel times between two customers are determined by solving a time-dependent shortest path (TD-SP). This work suggests a new metaheuristic approach for the TDSPVRP based on the ruin and recreate operator Slack Induction by String Removals (SISRs). Moreover, this work proposes an efficient strategy to evaluate and store time intervals where we can avoid recomputing TD-SPs. We analyze the impact of such strategy on the algorithm’s efficiency with respect to the size of the instance and runtime. The proposed algorithm was tested on real-world benchmark instances, and the results show that the method was capable of improving several best-known solutions within very competitive times.
• 
  01:55 PM - 02:20 PM

  Multi-depot arc routing models: An application in national road network sweeping

  • Omar Foutlane, presenter,
  • Amina Lamghari, Université du Québec à Trois-Rivières
  • Jean-François Audy, Université du Québec à Trois-Rivières

  We address a street sweeping problem that
  belongs to the class of multi-depot vehicle routing problems. A fleet
  of vehicles (sweepers, water and dump trucks) starts a shift from a
  depot, sweeps a set of the required arcs, and returns at the end of
  each shift to the nearest depot. A shift should start from the ending
  depot of the previous one. In addition, a constraint related to
  another practical aspect imposes that highways must be swept during
  the night for safety and traffic considerations. The goal is to find a
  schedule (shifts) that minimizes sweeping costs and satisfies work regulations
  constraints. This problem and its specifications are inspired by a
  real-world application. We formulate the problem as a mixed integer
  linear programming (MILP) model, introduce strategies to solve it
  efficiently, and discuss preliminary results obtained on a real case
  study in Quebec, Canada.
• 
  02:20 PM - 02:45 PM

  Service Time Window Design in Routing Optimization under Uncertainty

  • Davod Hosseini, presenter, Sobey School of Business, Saint Mary's University
  • Borzou Rostami, Alberta School of Business, University of Alberta
  • Mojtaba Araghi, Lazaridis School of Business and Economics, Wilfrid Laurier University

  We propose a new routing optimization approach where a service provider aims to design service time windows to visit a set of customers within a given time budget in a network with stochastic and possibly correlated travel times. To construct the service time window for each customer, we introduce two criteria to address the length of the time window and the risk of violating it. The service provider can allocate different penalties indicating risk preferences/tolerance to each of these criteria, resulting in various routes and time windows with different levels of service guarantee. We provide two modeling frameworks based on stochastic and distributionally robust optimization to handle uncertainty in travel times. In each setting, we derive closed-form solutions for the optimal time windows that are functions of the service provider's risk preference on both criteria. Moreover, we develop two decomposition-based algorithms to find the exact optimal routing and time window assignment solutions in dense networks. We show the efficacy of our proposed models on a rich collection of instances derived from some well-known datasets in the literature. Our computational experiments also demonstrate the efficiency of our proposed algorithms in improving the performance of a state-of-the-art commercial solver.
• 
  02:45 PM - 03:10 PM

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

  • Bahman Bornay, presenter, Polytechnique Montreal, CIRREL, CTTT

  The classical Pickup and Delivery Problem with Time Windows (PDPTW) is typically formulated on a complete customer-based graph, where links between vertices represent the shortest paths between each pair of customers. However, in reality, the speed on links changes over time, leading to multiple shortest paths within various intervals throughout the day. Moreover, in the current competitive market, carrier companies may need to provide customers with options to choose from among multiple potential pickup and delivery locations, each with its own time windows and constraints. In this context, we introduce a new class of problems, called the Generalized Dial-A-Ride Problem (GDARP), which assumes a set of potential pickup and delivery locations for each transit request. We present a Mixed-Integer Programming (MIP) model and formulate the scheduling problem for each vehicle as a Dynamic Programming (DP) problem, which is solved to optimality. Furthermore, we propose a hybrid metaheuristic algorithm that combines DP with a search algorithm to find high-quality solutions. We conduct experiments on real road networks with time-dependent travel times and show that our proposed algorithm is efficient and outperforms existing methods. Our work fills a gap in the rich vehicle routing problem literature by explicitly investigating the combination of multiple pickup and dropoff locations, time windows, and time-dependent travel times.