Back to search

University of Southampton

The vehicle routing problem with release and due dates: formulations, heuristics and lower bounds

Abstract

dc:description.abstract

A novel extension of the classical vehicle routing and scheduling problem is proposed that integrates aspects of machine scheduling into vehicle routing. Associated to each customer 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 minimise a convex combination of the operational costs and customer service level, measured as total distance travelled and total weighted tardiness, respectively. A formal definition of the problem is presented, and a variety of benchmark instances are generated to analyse the problem experimentally, and evaluate the performance of any solution approaches developed. Both experimental and theoretical contributions are made in this thesis, and these arise from the development of mixed integer linear programming(MIP) formulations, efficient heuristics, and a Dantzig-Wolfe decomposition and associated column generation algorithm. <br/><br/>The MIP formulations extend commodity flow formulations of the capacitated vehicle routing problem, and are generally related by aggregation or disaggregation of the variables. Although a set of constraints is presented that is only valid form-commodity flow formulations. A path-relinking algorithm (PRA) is proposed that exploits the efficiency and aggressive improvement of neighbourhood 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 neighbourhood search into a standard iterated local search algorithm. The Dantzig-Wolfe decomposition of the problem yields a traditional set-partitioning formulation, where the pricing problem (PP) is an elementary shortest path problem with resource constraints and weighted tardiness. Two dynamic programming (DP) formulations of the PP are presented, modelling the weighted tardiness of customers in a path as a pointwise function of the release dates, or decomposing the states over the release dates. The CG algorithm relies on a multi-phase pricing algorithm that utilises DP heuristics, and a decremental state-space relaxation algorithm that solves an ng-route relaxation at each iteration.<br/><br/>Extensive computational experiments on the benchmark instances show that the newly defined features have a significant and varied impact on the problem. As a result, finding tight lower bounds and eventually optimal solutions is highly complex, but tight upper bounds can be found efficiently using advanced heuristics.

Degree

thesis:*
Name dc:type.qualificationname
Ph.D.
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Southampton
Year dc:date.issued
2016

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Shelbourne, Benjamin
Advisors dc:contributor.advisor
  • Potts, Chris
  • Battarra, Maria

Rights

Language dc:language
English, eng

Chain of custody

source
Harvested from
University of Southampton
Base URL
eprints.soton.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Shelbourne, Benjamin. The vehicle routing problem with release and due dates: formulations, heuristics and lower bounds. doctoral thesis, University of Southampton, 2016.