A branch-price-and-cut algorithm for the vehicle routing problem with release and due dates. (January 2021)

• Record Type: Journal Article
• Authors: Yang, Weibo; Ke, Liangjun; Wang, David Z.W.; Lam, Jasmine Siu Lee
• Is Part Of: Transportation research. Volume 145(2021)
• Publication Date: 2021-01
• Subjects: Vehicle routing -- Release and due dates -- Branch-price-and-cut -- Bidirectional labeling algorithm; Logistics -- Periodicals; Transportation -- Periodicals; 388.011
• DOI: 10.1016/j.tre.2020.102167
• Languages: English
• ISSNs: 1366-5545

Abstract

Highlights: A branch-price-and-cut algorithm is developed to exactly solve the VRPRD. An effective bidirectional labeling algorithm is proposed for the pricing problem. Extensive computational experiments are conducted to evaluate the performance of the proposed algorithm. The test instances and computational results are provided for future researchers of the problem. Abstract: In this paper, we investigate the vehicle routing problem with release and due dates (VRPRD), which is a new variant of vehicle routing problem (VRP). In the problem, the order required by a customer is available for delivery later than its release date. A penalty cost, called tardiness cost, will be imposed if a customer is served after its due date. The objective of the VRPRD is to minimize the total routing and weighted tardiness costs. To address the problem, we develop an exact branch-price-and-cut algorithm based on the set-partitioning formulation. An effective bidirectional labeling algorithm is proposed to deal with the pricing problem. Numerical studies have verified that the proposed algorithm can obtain the exact optimal solutions for more than 75 % of benchmark instances within approximately six minutes on average.