A lexicographic-based two-stage algorithm for vehicle routing problem with simultaneous pickup–delivery and time window. (October 2020)

• Record Type: Journal Article
• Authors: Shi, Yong; Zhou, Yanjie; Boudouh, Toufik; Grunder, Olivier
• Is Part Of: Engineering applications of artificial intelligence. Volume 95(2020)
• Publication Date: 2020-10
• Subjects: Simultaneous pickup–delivery problem -- Time window -- Tabu search -- Variable neighborhood search -- Vehicle routing problem -- Two-stage algorithm -- Learning-based approach; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2020.103901
• Languages: English
• ISSNs: 0952-1976

Abstract

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. Highlights: A vehicle routing problem with simultaneous pickup–delivery and time windows is considered. The studied problem is computationally challenging due to its NP-hard nature. A lexicographic-based two-stage algorithm is proposed. The performance of the proposed algorithm is verified by test and comparison.