Real-life vehicle routing with time windows for visual attractiveness and operational robustness

Hollis, B. L. and Green, P. J. (2012) Real-life vehicle routing with time windows for visual attractiveness and operational robustness. Asia-Pacific Journal of Operational Research, 29 4: 1250017.1-1250017.29. doi:10.1142/S0217595912500170


Author Hollis, B. L.
Green, P. J.
Title Real-life vehicle routing with time windows for visual attractiveness and operational robustness
Journal name Asia-Pacific Journal of Operational Research   Check publisher's open access policy
ISSN 0217-5959
Publication date 2012-08
Sub-type Article (original research)
DOI 10.1142/S0217595912500170
Volume 29
Issue 4
Start page 1250017.1
End page 1250017.29
Total pages 29
Place of publication Singapore
Publisher World Scientific Publishing Co.
Collection year 2013
Language eng
Formatted abstract
This paper describes an algorithm for producing visually attractive and operationally robust solutions to a real-life vehicle routing problem with time windows. Visually attractive and operationally robust solutions are usually synonymous with compact, nonoverlapping routes with little or no intra-route cross over. The visual attractiveness of routes, for practical routing applications, is often of paramount importance.

We present a two phase solution approach. The first phase is inspired by the sequential insertion algorithm of Solomon (1987) and includes a range of novel enhancements to ensure visually attractive solutions are produced in the face of a range of nonstandard real-life constraints: A constrained and heterogeneous vehicle fleet; tight time windows and banned delivery windows; multiple route capacity measures; driver breaks; minimum route volumes; vehicle-location compatibility rules; nonreturn to base routes; peak hour traveling times; vehicle type dependent service times; and replenishment back at the depot. The second phase is based on the guided local search algorithm of Kilby et al. (1999). It uses an augmented objective function designed to seek solutions which strike a balance between minimizing traditional cost measures, whilst maximizing the visual attractiveness of the solution.

Our two phase solution approach is particularly adept at producing solutions that both aggressively minimize the total number of routes, a feature that we believe has been missing in algorithms presented in equivalent literature, as well as minimizing traditional cost measures whilst delivering a very high degree of visual attractiveness.

The algorithm presented has been successfully implemented and deployed for the real-life, daily beverage distribution problem of Schweppes Australia Pty. Ltd. for a range of capital cities throughout Australia.
Keyword Vehicle routing with time windows
Construction heuristics
Meta heuristics
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ
Additional Notes Article # 1250017

Document type: Journal Article
Sub-type: Article (original research)
Collections: School of Mathematics and Physics
Official 2013 Collection
School of Physical Sciences Publications
 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 2 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 3 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Thu, 15 Nov 2012, 15:13:14 EST by System User on behalf of School of Mathematics & Physics