A lexicographic-based two-stage algorithm for vehicle routing problem with simultaneous pickup-delivery and time window
- 문서 유형
- 연구출판물 · 학술지 논문
- 등재
- SCIEScopus
- 저널 순위
- JCR Q1Scopus Q1
- 피인용
- Web of Science 40Scopus 52
- FWCI (Scopus)
- 0
- JCR IF
- JCR 2019 4.201
- ISSN
- 0952-1976
저자
- Shi, Yong제1저자UMR SADAPT, INRAE, University of Paris-Saclay, 16 rue claude bertand, Paris, 75005, France
- 주염걸교신저자Department of Industrial Engineering, Pusan National University, Busan, 46241, Republic of Korea.
- Boudouh, ToufikICB UMR 6303, CNRS, Univ. Bourgogne Franche-Comt, UTBM, rue de Leupe, Sevenans, 90400, France
- Grunder, OlivierNanomedicine Lab, Univ. Bourgogne Franche-Comté, UTBM, rue mieg, Belfort, 90010, France.
초록
Vehicle routing problem with simultaneous pickup-delivery and time window (VRPSPDTW) is computationally challenging as it generalizes the classical and NP-hard vehicle routing problem. According to the state-of-the-art, VRPSPDTW usually has two hierarchical optimization objectives: a primary objective of minimizing the number of vehicles (NV) and a secondary objective of reducing the transportation distance (TD). Given the existing research and our trial results, we find that the optimization of TD is not necessarily a promotion for reducing NV. In this paper, an effective learning-based two-stage algorithm, which has never been studied before, is proposed to solve the VRPSPDTW. In the first stage, a modified variable neighborhood search with a learning-based objective function is proposed to minimize the primary objective with retaining the potential structures. In the second stage, a bi-structure based tabu search (BSTS) is designed to optimize the primary and secondary objectives further. The experimental results on 93 benchmark instances demonstrate that the proposed algorithm performs remarkably well both in terms of computational efficiency and solution quality. In particular, the proposed two-stage algorithm improve several best known solutions (either a better NV or a better TD when NV are the same) from the state-of-the-art. To our knowledge, this is the first learning-based two-stage algorithm for solving VRPSPDTW reaching such a performance. Finally, we empirically analyze several critical components of the algorithm to highlight their impacts on the performance of the proposed algorithm.
키워드
Simultaneous pickup-delivery problemTime windowTabu searchVariable neighborhood searchVehicle routing problemTwo-stage algorithmLearning-based approachPARTICLE SWARM OPTIMIZATIONLARGE NEIGHBORHOOD SEARCHTABU SEARCHLOCAL SEARCHSCHEDULING PROBLEMUP PROBLEMLOCATIONHEURISTICSTRAVELSimultaneous pickup–delivery problem
식별자
- Scopus EID
- 2-s2.0-85089922056
- WoS UID
- 000569874100020



로그인
연구물 목록으로