Tutorial: Solving Real-World Vehicle Routing Problems

Tutorial on Solving Real-World Vehicle Routing Problems

Speaker: Phil Kilby and Charles Gretton

Slides Part 1

Slides Part 2


In this tutorial we look at a method for solving real-world vehicle routing problems. We present a Constraint Programming model of VRPs that is able to represent a wide variety of real-world transport scenarios. We then look at a meta-heuristic based on Ropke and Pisinger's Large Neighbourhood Search that can be used to find good solutions to that model. We demonstrate why that LNS procedure is a "natural fit" for use in a Constraint Programming setting.

The end of the tutorial examines a number of "soft constraints" or "penalties", that can be used to represent user preferences in routing problems. We show how concepts such as "visual appeal" and "balanced routes" can be represented using augmented objective functions, and how the LNS solution procedure performs in optimizing both classical and augmented objectives.

Phil Kilby

Dr Phil Kilby [BSc and PhD from The University of Queensland, Australia] is a Principal Research Scientist within the NICTA Optimisation Research Group. Phil has extensive experience in transportation science, operations research and computer science. Phil has previously held leadership positions within the Commonwealth Scientific and Industrial Research Organisation (CSIRO) in Australia. His career has also seen him employed on research and industrial projects at The University of Strathclyde in the United Kingdom, at OPCOM PTY LTD and at QUF Industries LTD. Phil has experience in many transportation optimisation applications, ranging from viniculture to defence logistics. Phil is the principle developer of the multi-award winning transport optimisation system called Indigo.