A cost function approximation method for dynamic vehicle routing with docking and LIFO constraints

Horváth, Markó and Kis, Tamás and Györgyi, Péter (2025) A cost function approximation method for dynamic vehicle routing with docking and LIFO constraints. MULTIMODAL TRANSPORTATION, 4 (1). No. 100194.

Preview

Text 03_horvath2025cost_offprint.pdf - Published Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (1MB) | Preview

Abstract

In this paper, we study a dynamic pickup and delivery problem with docking constraints. There is a homogeneous fleet of vehicles to serve pickup-and-delivery requests at given locations. The vehicles can be loaded up to their capacity, while unloading has to follow the last-in-first-out (LIFO) rule. The locations have a limited number of docking ports for loading and unloading, which may force the vehicles to wait. The problem is dynamic since the transportation requests arrive real-time, over the day. Accordingly, the routes of the vehicles are to be determined dynamically. The goal is to satisfy all the requests such that a combination of tardiness penalties and traveling costs is minimized. We propose a cost function approximation based solution method. In each decision epoch, we solve the respective optimization problem with a perturbed objective function to ensure the solutions remain adaptable to accommodate new requests. We penalize waiting times and idle vehicles. We propose a variable neighborhood search based method for solving the optimization problems, and we apply two existing local search operators, and we also introduce a new one. We evaluate our method using a widely adopted benchmark dataset, and the results demonstrate that our approach significantly surpasses the current state-of-the-art methods.

Actions (login required)

Edit Item