4 Presentations

• 
  03:50 PM - 04:15 PM

  New Optimality Cuts for the Traveling Salesman Problem with Generalized Latency

  • Joaquim Jusseau, presenter, École de technologie supérieure
  • Fausto Errico, École de technologie supérieure

  In this presentation we focus on the Traveling Salesman Problem with Generalized Latency (TSP-GL), which is a variant of the TSP that finds application in the context of Semi-Flexible transit Systems (STSs). STSs combine the advantages of traditional transit systems, such as buses or trains with predefined routes and schedules, with flexible transit systems, such as ridesharing services or taxis, which adapt their routes in real time based on demand. The goal of these systems is to optimize operational efficiency while improving passenger comfort and satisfaction.
  With respect to the classical TSP, the TSP-GL not only incorporates the traditional tour cost, but also a latency component, which can be interpreted as the average passengers' travel time. The resulting problem is very challenging, and state-of-the-art methods can only solve relatively small problem instances.
  In this presentation, we introduce a solution approach based on Benders decomposition and a new set optimality cuts exploiting the problem’s integer structure. Computational results show the effectiveness of our algorithm when compared to benchmark methods from the literature.

• 
  04:15 PM - 04:40 PM

  Generalized Route Scheduling Problem on Road Networks with Time-dependent Travel Times

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

  Route scheduling is a key challenge in transportation and logistics, traditionally addressed through static models such as VRPTW, PDPTW, and DARP on customer-based graphs. Yet modern applications demand routing on real road networks with time-dependent travel times and flexible pickup and delivery options, introducing significant modeling and computational challenges. We introduce the Generalized Route Scheduling Problem with Time-dependent Travel Times on road networks (GRSP-TD), which unifies a broad class of scheduling problems under realistic network conditions. Our formulation models time-dependent travel times on actual road networks and incorporates a route sequence that includes a depot, clustered pickup and delivery locations, and a return to the depot---thereby capturing time-dependent VRPTW, PDPTW, and DARP as special cases. To address GRSP-TD, we develop novel dynamic programming algorithms based on linear forward and binary tree propagation. These algorithms also optimally solve the NP-hard Optimal Start Time Problem (OSTP). In addition, we introduce efficient screening, feasibility-checking, and lower-bounding procedures to discard non-promising solutions, enhancing the approach's integration into metaheuristics and exact decomposition methods such as column generation. This framework offers a robust and scalable solution for modern routing challenges on real road networks, directly addressing the evolving needs of transportation systems.

• 
  04:40 PM - 05:05 PM

  Solving a real-world Multi Trips Multi Depots Multi Products Petrol Replenishment problem with time windows and a heterogeneous fleet of tank-trucks

  • Ayoub Insa Correa, presenter, Université de Thies, Sénégal
  • André LANGEVIN, CIRRELT, Polytechnique Montréal

  In this paper, we address a real-world replenishments scheduling problem of a network of petrol stations with two types of gasoline by a heterogeneous fleet of tank-trucks from five depots. To solve this complex problem, we propose a graph and a related mathematical model integrating a heterogeneous fleet assignment, compartmented truck loading (stowage) with scheduling and capacitated vehicle routing with time windows and no split delivery. We tested our model on 90 instances based on real world weekly replenishment orders. Even though this exact approach is turned into a good heuristic method by setting a short solution time limit, the results obtained are very satisfactory as several optimal solutions are reached. Our approach is also promising in terms of convergence, scalability and potential for decomposition.

• 
  05:05 PM - 05:30 PM

  A Branch-and-Price algorithm for the traveling salesman problem with release dates

  • Joseph Robitaille, presenter, Université Laval
  • Jean-François Côté, Université Laval
  • Jacques Renaud, Université Laval, CIRRELT

  In the traveling salesman problem with release dates (TSP-rd), the delivery goods are not necessarily available at the beginning of the time horizon. Instead, each customer's merchandise comes with a release date, which determines the moment it becomes available at the depot. The delivery paths of a single vehicle visiting all customers must be planned with this information. Waiting times may be used to allow the goods to become available at the depot, adding a new layer of optimization to the standard traveling salesman problem. There is only a limited amount of research in the literature, which motivates the need for a more efficient approach in determining optimal solutions. To reduce this gap, we propose two formulations. The first one takes advantage of symmetries found in the problem; paths visiting most subsets of customers are replicable at different periods in the time horizon. The second one is a set-partitioning formulation allowing us to use a Branch-and-Price (B&P) algorithm. Various strategies are used to boost the effectiveness of the B&P algorithm, which performs better than the asymmetric formulation and better than the latest approaches from the literature across all benchmark instances. These intuitive strategies are easily replicable to other B&P algorithms, which may grant insights to the audience.