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.
A branch-price-and-cut algorithm for the vehicle routing problem with release and due dates
2020-11-08
Article (Journal)
Electronic Resource
English
A Branch-and-Price Algorithm for the Multidepot Vehicle Routing Problem with Interdepot Routes
Online Contents | 2014
|A Branch-Cut-and-Price Algorithm for the Energy Minimization Vehicle Routing Problem
Online Contents | 2016
|A Branch-Cut-and-Price Algorithm for the Energy Minimization Vehicle Routing Problem
British Library Online Contents | 2016
|