2022 Optimization Days
HEC Montréal, Québec, Canada, 16 — 18 May 2022
TB11 - Vehicle routing and scheduling IV
May 17, 2022 03:30 PM – 05:10 PM
Location: EY (blue)
Chaired by Tayeb Mhamedi
4 Presentations
-
03:30 PM - 03:55 PM
A vehicle routing problem with workload balancing for home delivery of COVID-19 tests
The COVID-19 pandemic forced an unexpected demand on laboratories for home delivery test services (i.e., RT-PCR tests) used for the virus diagnosis. People who are required to obtain a negative test result for certain activities usually prefer to request in-home tests to reduce the risk of getting infected. Due to the limited capacity of laboratories, they must manage their resources to meet demands while reducing their transportation costs. We present a vehicle routing problem that helps laboratories in managing their testers while considering patients’ time windows and employees' workload balance. In this problem, testers’ workload balancing is defined based on the number of visited customers to reduce testers’ exposure to infected patients. A mixed-integer formulation is proposed to solve the problem for small instances, and an ALNS metaheuristic algorithm is applied for solving the problem for real-world data.
-
03:55 PM - 04:20 PM
The Two-Echelon Location-Routing Problem under Stochastic and Correlated Demands
We study the Two-Echelon Location-Routing Problem with Stochastic and Correlated Demands (2E-LRPSCD). The system topology is composed of sets of platforms, satellites (or intermediate facilities), and customer zones. The system requires the routing of vehicles on each echelon to deliver freight from platforms to customer zones, through satellite facilities. Location decisions on platforms are not considered, but satellite locations must be defined. In this context, we investigate the influence of correlated uncertain non-substitutable customer zone demands on the design of freight delivery systems. To gain insight into the importance of correlations, we use different scenario sets representing different correlation matrices to study the effect of correlations on the optimal solution. We introduce the problem setting and present a two-stage stochastic formulation for the 2E-LRPSCD, where the first-stage decisions concern the distribution network design before the realization of the random demands, and the second-stage comprises the routing decisions for both echelons considering the demand realization. A progressive hedging-based heuristic framework is also proposed for the 2E-LRPSCD introducing series of novel strategies to accelerate the consensus among the non-scenario dependent decisions. Extensive computational experiments are performed to study the efficiency of the proposed formulations and the solution framework for the 2E-LRPSCD.
-
04:20 PM - 04:45 PM
Multi-attribute Two-echelon Location Routing Problem: Formulation and Dynamic Discretization Discovery Approach
We address the Two-Echelon Multi-Attribute Location-Routing Problem with fleet Synchronization at intermediate facilities (2E-MALRPS), where location and routing decisions are to be taken on both echelons under tight synchronization constraints. Prompted, in particular, by applications to the strategic and tactical planning of City Logistics systems, the problem setting includes time-dependent origin-destination demand, time windows, limited storage capacity at intermediate facilities, and synchronization at these facilities of the fleets operating on different echelons. Our study aims to deepen the understanding of the effects of the integrated treatment of diverse attributes on both location and routing decisions, under the presence of tight synchronization constraints and timing features. We introduce a mixed-integer programming formulation for the 2E-MALRPS defined on a time-space network. An exact solution framework for the 2E-MALRPS based on a dynamic discretization scheme is also proposed to address the scalability issues provoked by the time-space formulation. In the computational study, we analyze the cost sensitivity, the infrastructure usage, and the importance of fleet synchronization under time-sensitive distribution systems to derive managerial insights. Preliminary results show the efficiency of the proposed solution method, as well as the benefits to City Logistics networks of integrating multiples attributes into a single formulation.
-
04:45 PM - 05:10 PM
Branch-price-and-cut algorithms for the single and multi-commodity two-echelon vehicle routing problem with time windows
In this presentation, we address the two-echelon vehicle routing problem with time windows (2E-VRPTW) and an extension of the problem when considering multiple commodities (MC-2E-VRPTW). For both problems, first-echelon routes handle transportation of goods from depots to satellites while second-echelon routes, departing from satellites, ensure that goods are being shipped to customers within their allowed time windows. In the 2E-VRPTW, goods available at different depots correspond to a single commodity. Moreover, freight distributed by a second-echelon route must be supplied from exactly one first echelon route. In the MC-2E-VRPTW, each customer's demand is solely available at a specific depot and is supplied by a single first-echelon vehicle. We propose tailored branch-price-and-cut algorithms for both problems. We report computational results obtained on instances from the literature with up to 100 customers and 5 satellites that we are able to solve to optimality.