본문 바로가기

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

저자

  1. Shi, Yong제1저자UMR SADAPT, INRAE, University of Paris-Saclay, 16 rue claude bertand, Paris, 75005, France
  2. 주염걸교신저자Department of Industrial Engineering, Pusan National University, Busan, 46241, Republic of Korea.
  3. Boudouh, ToufikICB UMR 6303, CNRS, Univ. Bourgogne Franche-Comt, UTBM, rue de Leupe, Sevenans, 90400, France
  4. 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