A hybrid heuristic algorithm for urban distribution with simultaneous pickup-delivery and time window

Fagui Liu, Lvshengbiao Wang, Mengke Gui (), Yang Zhang (), Yulin Lan, Chengqi Lai and Boyuan Zhu
Additional contact information
Fagui Liu: South China University of Technology
Lvshengbiao Wang: South China University of Technology
Mengke Gui: South China University of Technology
Yang Zhang: South China University of Technology
Yulin Lan: South China University of Technology
Chengqi Lai: South China University of Technology
Boyuan Zhu: South China University of Technology

Journal of Heuristics, 2023, vol. 29, issue 2, No 3, 269-311

Abstract: Abstract With the continuous development of urban distribution services, customers have increasingly strict requirements for the delivery time windows. Therefore it is necessary to study the vehicle routing problem with simultaneous pickup-delivery and time windows (VRPSPDTW) in urban distribution. However, as one of the most important classification of the much anticipated reverse logistics, the VRPSPDTW problem has not received much attention, and lacks an efficient and simple implementation. Our method combines the enhanced Late Acceptance Hill Climbing algorithm (enhanced LAHC) to ensure the diversity of solutions and the Multi-armed Bandit Algorithm (MAB) to choose a neighborhood structure which has the best performance. In order to enhance its search ability at a later stage, a perturbation strategy is designed to effectively prevent premature convergence. To our best knowledge, the proposed h_LAHC (hybrid LAHC) algorithm is applied to the VRPSPDTW for the first time. We provide abundant experiments were conducted on 93 benchmark instances, and the results demonstrated that our algorithm can achieve better, totally equal or approximately equal results in 97.85%, 56.99% and 73.12% instances compared with the latest three mainstream algorithms respectively. In particular, the proposed algorithm has a prominent performance in scenarios with relatively narrow time windows. Moreover, we conduct an empirical analysis on critical components of the algorithm to highlight their impact on the performance of the proposed algorithm.

Keywords: Scheduling; Vehicle routing problem with time windows; Simultaneous pickup-delivery; Adaptive memory; Late acceptance hill climbing algorithm (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-023-09510-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:29:y:2023:i:2:d:10.1007_s10732-023-09510-1

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-023-09510-1

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().