Summary: 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 M. M. Solomon [Oper. Res. 35, 254–262 (1987; Zbl 0625.90047)] 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 Ph. Kilby, P. Prosser and P. Shaw [in: Meta-heuristics. Advances and trends in local search paradigms for optimization. 2nd Meta-Heuristics international conference (MIC-97), Sophia-Antipolis, France, July 21-24, 1997. Dordrecht: Kluwer Academic Publishers. 473–486 (1999; Zbl 0985.90019)]. 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.