The Vehicle Routing Problem with Release and Due Dates

Benjamin C. Shelbourne (), Maria Battarra () and Chris N. Potts ()
Additional contact information
Benjamin C. Shelbourne: Mathematical Sciences, University of Southampton, Highfield, Southampton SO17 1BJ, United Kingdom
Maria Battarra: School of Management, University of Bath, Bath BA2 7AY, United Kingdom
Chris N. Potts: Mathematical Sciences, University of Southampton, Highfield, Southampton SO17 1BJ, United Kingdom

INFORMS Journal on Computing, 2017, vol. 29, issue 4, 705-723

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

Keywords: vehicle routing and scheduling; weighted tardiness; release dates; path relinking; hybrid population-based metaheuristics (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2017.0756 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:29:y:2017:i:4:p:705-723

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().