VOCAL 2024
Abstract Submission

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

Invited abstract in session TD-4: Application of integer programming, stream contributed papers.

Thursday, 14:45 - 16:15
Room: C105

Authors (first author is the speaker)

1. Markó Horváth
Research Laboratory on Engineering & Management Intelligence, HUN-REN Institute for Computer Science and Control
2. Tamas Kis
Institute for Computer Science and Control
3. Péter Györgyi
Institute for Computer Science and Control

Abstract

In this talk, we consider a dynamic pickup and delivery problem with several practical restrictions, such as last-in-first-out order (LIFO) loading rule and docking constraints.
Briefly stated, there is a homogeneous fleet of vehicles to serve pickup-and-delivery requests.
Loading orders has to respect the vehicles' capacity limit, while unloading orders has to follow the LIFO rule.
The factories have a limited number of docking ports for loading and unloading, which may force the vehicles to wait.
The goal is to satisfy all the requests such that a combination of tardiness penalties and traveling costs is minimized.
The problem is dynamic in the sense, that the orders are not known in advance, but arrive online, and at certain time points there is an opportunity to make decisions, i.e., to re-plan routes, reflecting on the new information.
We propose a cost function approximation method for the problem.
At each decision point, we solve the corresponding problem with a perturbed objective function to make solutions flexible for possible future changes.
These problems are solved with a variable neighborhood search, for which we apply two existing local search operators, and we also introduce a new one.
Our computational experiments show that our solution procedure significantly outperforms the existing methods for the problem on a widely used benchmark dataset.

This work was supported by grant TKP2021-NKTA-01, and by the János Bolyai Research Scholarship.

Keywords

Status: accepted

Back to the list of papers