some days ago I've been asked for a generic statement about PTV's understanding of tour optimization. Difficult to say but here are my 2 cents:
Furthermore the following statement gives you a description of what tour optimization means from a more functional point of view. I am aware that this is very rough but this is by design: if you want to understand tour optimization in detail you need to check the technical posts and the documentation:In the past tour optimization was often based on a combination of construction and a post processing. This is no longer state-of-the-art:
In the recent years the evaluation of finetuned neighborhoods seem to provide better results (even within less computation time). Mechanisms such as local searches and large neighborhoods have become standard.
Such algorithms apply various heuristics which are combined in an adaptive and carefully orchestrated manner: Relocate, Swap, 2Opt, 2Opt*, 3Opt, OrOpt, Ejection Chain…
Therefore “standard processes” have been replaced by “standard frameworks”. PTV introduced it’s own framework which can be seen as an Adaptive Large Neighborhood Search procedure: incredibly fast - extremely efficient – and defining the new state-of-the-art.
We implemented those techniques in C++ to make them most performant.
All these approaches include exact mechanisms (e.g. dynamic programming) for sub-tasks such as the calculation of time profile. And we even use parallel programming when it is applicable.
Feedback is welcome!In basic tour optimization the following objects have to be considered:
- a set of geo-referenced tasks/orders you want to fullfill (e.g. deliveries to specific customers, repair services or sales visits)
- a set of ressources that are available to fullfil the tasks (Vehicles and Drivers)
- a set of depots and vehicle locations
- a set of planning constraints that have to be considered (e.g. maximum driving periods, official break- and rest rules, ...)
- as an optional element you could provide a pre-planned tour structure
Now the main objective for the optimization engine is to create a plan structure that mentions
Furthermore there are three major categories of constraints I'd like to mention - they all appear in the context of orders and resources:
- who takes care of what and in what sequence...: so the engine decides both about assignments of tasks to orders and about proper sequences considering all the given constraints. What distances and arrival times do apply at the stops?
- There's also a priority of several KPIs we apply for the optimization:
- Schedule as many orders as possible
- use fewest number of ressources as possible
- find compact tours (reduce both distance and time)
- let the tours terminate as early as possible
- let the tours start as late as possible
Based on this definition we can handle simple sequencing of a single truck and also complete tour optimization. This applies both on green field and on given structures and finally you can use this as a 100% automated batch but also within a semi manual / interactive user application.
- time windows such as opening intervals (orders) and operating intervals (drivers/vehicles)
- quantities such as freight volumes (orders) and loading capacities (vehicles)
- skills/equipment such as required equipment (orders) and available equipment (drivers/vehicles)
Bernd
