JOPT2025

HEC Montreal, 12 — 14 May 2025

JOPT2025

HEC Montreal, 12 — 14 May 2025

Schedule Authors My Schedule

Vehicle Routing I

May 12, 2025 10:30 AM – 12:10 PM

Location: Raymond Chabot Grant Thornton (Yellow)

Chaired by Claudio Contardo

4 Presentations

  • 10:30 AM - 10:55 AM

    Diversification Strategies in Deep Reinforcement Learning for Multi-Commodity Pickup and Delivery Problem

    • King Tong Wong, presenter, University of Edinburgh Business School
    • Tsung-Sheng Chang, Department of Transportation & Logistics Management, National Yang Ming Chiao Tung University
    • Jamal Ouenniche, University of Edinburgh Business School

    Pickup and delivery problems are challenging due to their NP-hard nature. This research focuses on the multi-commodity one-to-one single capacitated vehicle pickup and delivery problem (1-1 m-SCVPDP). After presenting a typical mathematical programming formulation of the 1-1 m-SCVPDP, we introduce Deep Reinforcement Learning (DRL) reformulation of the problem. Then, we present our DRL algorithm with a key innovation consisting of the introduction of a new multi-start diversification mechanism and new intensification-diversification strategies. These strategies are crucial for balancing exploration and exploitation, ensuring high training quality and efficiency. Our empirical experiments show that our methodology generates optimal solutions quicker than traditional exact solvers for smaller instances and demonstrate the generalization capabilities of our methodology across various problem sizes and characteristics. Furthermore, we equip our methodology with an incremental training mechanism to further enhance its adaptability and efficiency. This research demonstrates the value of employing DRL to solve the 1-1 m-SCVPDP and offers valuable insights for future research and practical applications in transportation and logistics.

  • 10:55 AM - 11:20 AM

    Team orienteering with pick-up and delivery, products incompatibilities and pre-assigned customers

    • Maryam Darvish, Université Laval
    • Simona Mancini, presenter, University of Palermo

    In this work we address the context of less-than-truckload carriers who are available for performing additional pick-up and delivery tasks during their route. Products may become to different categories, which can be incompatible among each others, such as diary and cleaning products. In this case they cannot be simultaneously loaded on the same vehicle. However, they can be carried by the same vehicle in different parts of the route.
    We propose a system in which a centralized platform receive information about pick-up and delivery requests and about available carriers, and decide the assignment of requests to carriers considering that the profit earned for each fulfilled request depends on the category of the product and on the quantity requested. No profit is earned for unfulfilled requests. Furthermore, the company has to pay drivers a compensation depending on the detour, from their original path, required to fulfill all the requests assigned to them. Therefore, the net profit earned by the platform, for a specific request, is assignment-dependent.
    The goal is to maximize the total revenue for the company, given by the earned profit minus the compensation paid to the drivers, obtained by respecting vehicle capacity and incompatibility constraints.
    We provide a MIP formulation for the problem, able to solve small instances, and an efficient and effective matheuristic for larger instances. Moreover, we present several managerial insights.

  • 11:20 AM - 11:45 AM

    Vehicle Routing Problem for a City Logistics Orchestrator

    • Burak Koksal, presenter, Université de Lorraine
    • Nicolas Jozefowiez, Université de Lorraine
    • Ayse Akbalik, Université de Lorraine
    • Simon Belieres, Toulouse Business School

    In this study, we address a planning problem in the context of city logistics and motivated by a collaboration with an industrial partner. Specifically, we consider a logistics service provider that serves as an orchestrator, acting as an interface between retailers and freight transporters. The mission of that orchestrator involves coordinating, managing, and optimizing the city logistics system while ensuring that the principles and agreements established by collaboration among participants are maintained. Notably, the orchestrator does not own any courier but instead hires couriers to the transporters through long-term contracts, i.e., dedicated couriers, or short-term contracts, i.e., external couriers, so as to satisfy customer demands. The problem under study is an extension of the Vehicle Routing Problem (VRP) with a nonlinear objective function and is thus not directly amenable to the current VRP-solvers.

  • 11:45 AM - 12:10 PM

    An unified class of multi-vehicle covering tour problems with time windows

    • Marilène Cherkesly, ESG UQÀM
    • Claudio Contardo, presenter, Concordia University
    • Caroline Rocha, Ivado Labs

    We consider the problem of servicing a set of customer locations by means of two types of services: direct services fulfilled by transporting the freight by a fleet of vehicles to the customer locations directly; and indirect services by dropping the freight at intermediate locations for later pickup. We consider multiple attributes for this problem leading to different variants: time windows at the customer locations that must be respected when the service provided is direct, but which may or may not be respected when the service provided is indirect; coverage radii that restrict the distance between customers and their associated drop-off locations when the service provided is indirect; coverage capacity that restricts the maximum storage capacity when nodes act as drop-off locations; assignment costs associated with the pickup at the drop-off locations; covering constraints to model situations where covering nodes comes at no cost and without resource consumptions associated; and the possibility of having optional drop-off locations, this is nodes that do not require service but that may help at fulfilling service at other locations via an indirect service. We unify the multiple problem variants resulting from combining these attributes within a single mathematical model, and propose a branch-cut-and-price algorithm for its resolution. Our modeling framework includes the classical multi-vehicle covering tour problem (mCTP) as a particular case. By means of a thorough computational campaign we assess the performance of our modeling and algorithmic framework, and present a sensitivity analysis to derive managerial insights.

Back