TLHSA and SACA: two heuristic algorithms for two variant VRP models

Xuhong Cai, Li Jiang, Songhu Guo, Hejiao Huang () and Hongwei Du
Additional contact information
Xuhong Cai: Harbin Institute of Technology (Shenzhen)
Li Jiang: Harbin Institute of Technology (Shenzhen)
Songhu Guo: Harbin Institute of Technology (Shenzhen)
Hejiao Huang: Harbin Institute of Technology (Shenzhen)
Hongwei Du: Harbin Institute of Technology (Shenzhen)

Journal of Combinatorial Optimization, 2022, vol. 44, issue 4, No 43, 2996-3022

Abstract: Abstract Vehicle routing problem (VRP) is a classical combinatorial optimization problem. Under this problem, we focus on two variant models which better capture the real-world scenes: multiple-orders pickup and delivery problem with time-bound window (MOPDPTW) and dynamic vehicle routing problem with time window (DVRPTW). To tackle MOPDPTW, a two-layers heuristic search algorithm is proposed. The inner layer of proposed algorithm searches possible solutions in global and sends them to the outer layer to find local optimal solution. In order to solve DVRPTW, a general dynamical algorithm framework is designed to tackle the dynamic nature of the problem. Then based on ant colony algorithm, we propose several effective strategies called pheromone preserving mechanism, pheromone updating based on important solution components and parameter self-adaptive adjustment, aiming to improve the solution construction process by ants. We validate our two algorithms on different standard benchmarks and the results indicate that our proposed algorithms are competitive and effective compared with the state-of-the-art approaches.

Keywords: MOPDPTW; DVRPTW; Two-layers heuristic search; Dynamical algorithm framework; Pheromone updating (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00831-0 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:jcomop:v:44:y:2022:i:4:d:10.1007_s10878-021-00831-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00831-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

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