PTV Group - Logistics Forum

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.

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

• 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

Furthermore there are three major categories of constraints I'd like to mention - they all appear in the context of orders and resources:

• 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)

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.

• v2.27 : monetary cost optimization in xTour was available as experimental feature
• v2.28 : monetary cost optimization in xTour was available as released
• v2.29 : monetary cost optimization in xTour was still available but announced to be discopntinued with v2.30