A lexicographic-based two-stage algorithm for vehicle routing problem with simultaneous pickup–delivery and time window

• DOI: 10.1016/j.engappai.2020.103901
• Publication Date: 2020-08-28T11:10:21Z
• Authors: Yong Shi; Yanjie Zhou; Toufik Boudouh; Olivier Grunder
• Keywords: [SDV.SA]Life Sciences [q-bio]/Agricultural sciences; 0211 other engineering and technologies; Two-stage algorithm; 02 engineering and technology; 650; Tabu search; 004; Simultaneous pickup-delivery problem; Learning-based approach; Vehicle routing problem; Time window; [MATH]Mathematics [math]; Variable neighborhood search

Abstract 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.