The Vehicle Routing Problem with Release and Due Dates

Autor: Chris N. Potts, Maria Battarra, Benjamin C. Shelbourne
Rok vydání: 2017
Předmět:
Zdroj: Shelbourne, B, Battarra, M & Potts, C N 2017, ' The Vehicle Routing Problem with Release and Due Dates ', INFORMS Journal on Computing, vol. 29, no. 4, pp. 705-723 . https://doi.org/10.1287/ijoc.2017.0756
ISSN: 1526-5528
1091-9856
DOI: 10.1287/ijoc.2017.0756
Popis: A novel extension of the classical vehicle routing and scheduling problems is introduced that integrates aspects of machine scheduling into vehicle routing. Associated with each customer order is a release date that defines the earliest time that the order is available to leave the depot for delivery and a due date that indicates the time by which the order should ideally be delivered to the customer. The objective is to minimize a convex combination of the operational costs and customer service level, represented by the total distance traveled and the total weighted tardiness of delivery, respectively. A path-relinking algorithm (PRA) is proposed to address the problem, and a variety of benchmark instances are generated to evaluate its performance. The PRA exploits the efficiency and aggressive improvement of neighborhood search but relies on a new path-relinking procedure and advanced population management strategies to navigate the search space effectively. To provide a comparator algorithm to the PRA, we embed the neighborhood search into a standard iterated local search algorithm (ILS). Extensive computational experiments on the benchmark instances show that the newly defined features have a significant and varied impact on the problem, and the performance of the PRA dominates that of the ILS algorithm. The online supplement is available at https://doi.org/10.1287/ijoc.2017.0756 .
Databáze: OpenAIRE
Externí odkaz: