EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

325. An Enhanced Dynamic Discretization Discovery Algorithm for the Continuous-Time Service Network Design Problem

Invited abstract in session TD-58: MILPs for Vehicle Routing 1, stream VeRoLog - Vehicle Routing and Logistics.

Tuesday, 14:30-16:00
Room: S07 (building: 101)

Authors (first author is the speaker)

1. Roberto Baldacci
College of Science and Engineering, Hamad Bin Khalifa University
2. Shengnan Shu
The Hong Kong Polytechnic University
3. Zhou Xu
Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University

Abstract

Service Network Design Problems (SNDPs) are prevalent in the freight industry, holding significant practical value in their solutions. While the classic SNDP is often defined on a planning horizon discretized into a finite number of integral time units, the Continuous-Time Service Network Design Problem (CTSNDP) operates on a continuous-time planning horizon to avoid errors from discretization. Existing algorithms for CTSNDP and its variants primarily adopt a Dynamic Discretization Discovery (DDD) solution framework. This framework iteratively refines a finite set of integral time units, constructs a partially time-expanded network based on the discretization, and leverages the network to derive relaxations and feasible solutions for the problem. However, DDD algorithms face limitations in computational performance, especially when handling instances characterized by a high-cost ratio of vehicle-based costs over flow-based costs and high time flexibility. Consequently, a substantial portion of these instances remains unsolved. In this study, we enhance the DDD method for CTSNDP by introducing a new initial discretization, a novel exact method for deriving upper-bound solutions, and an improved refinement strategy. The computational study demonstrates that, with these innovative components, the enhanced DDD algorithm exhibits exceptional performance.

Keywords

Status: accepted

Back to the list of papers