Publication Type

Journal Article

Version

acceptedVersion

Publication Date

7-2023

Abstract

We consider a dynamic pickup and delivery problem (DPDP) where loading and unloading operations must follow a last in first out (LIFO) sequence. A fleet of vehicles will pick up orders in pickup points and deliver them to destinations. The objective is to minimize the total over-time (that is the amount of time that exceeds the committed delivery time) and total travel distance. Given the dynamics of orders and vehicles, this paper proposes a hierarchical optimization approach based on multiple intuitive yet often-neglected strategies, namely what we term as the urgent strategy, hitchhike strategy and packing-bags strategy. These multiple strategies can dynamically adapt to dispatch orders to vehicles according to the status of orders and by considering the travel distance and overtime. To account for the LIFO constraints, block-based operators are designed to schedule the delivery routes, thereby enhancing the search efficiency. The result on real-world instances shows that our proposed hierarchical optimization approach outperforms the current practice and the winning approach in an international competition. Finally, the insights gained from generated instances shows the hierarchical optimization approach has broader applicability.

Keywords

Dynamic pickup and delivery problem, Last in first out, Order dispatching strategy, Neighborhood search

Discipline

Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Optimization

Publication

Transportation Research Part E: Logistics and Transportation Review

Volume

175

First Page

1

Last Page

19

ISSN

1366-5545

Identifier

10.1016/j.tre.2023.103131

Publisher

Elsevier

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1016/j.tre.2023.103131

Download

Share

COinS