Tour Optimization a la PTV

This forum deals with any kind of trip optimization whether it is automatic planning or manual dispatching, refering to transport orders or service planning.
Post Reply
User avatar
Bernd Welter
Site Admin
Posts: 2564
Joined: Mon Apr 14, 2014 10:28 am
Contact:

Tour Optimization a la PTV

Post by Bernd Welter »

Hi there,

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:
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.
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 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.
Feedback is welcome!

Bernd
Bernd Welter
Technical Partner Manager Developer Components
PTV Logistics - Germany

Bernd at... The Forum,LinkedIn, Youtube, StackOverflow
I like the smell of PTV Developer in the morning... :twisted:
User avatar
Bernd Welter
Site Admin
Posts: 2564
Joined: Mon Apr 14, 2014 10:28 am
Contact:

Re: Tour Optimization a la PTV

Post by Bernd Welter »

since 2.23 we offer a switch called "minimizeNumberOfTours". Under some circumstances it might be meaningful to ignore the number of tours.
Bernd Welter
Technical Partner Manager Developer Components
PTV Logistics - Germany

Bernd at... The Forum,LinkedIn, Youtube, StackOverflow
I like the smell of PTV Developer in the morning... :twisted:
User avatar
Bernd Welter
Site Admin
Posts: 2564
Joined: Mon Apr 14, 2014 10:28 am
Contact:

Re: Tour Optimization a la PTV

Post by Bernd Welter »

since v2.25 we offer "considerOrderPriorities": each order gets a priority and we ensure displacerd that orders with higher prios are not displaced by low prio orders.
Bernd Welter
Technical Partner Manager Developer Components
PTV Logistics - Germany

Bernd at... The Forum,LinkedIn, Youtube, StackOverflow
I like the smell of PTV Developer in the morning... :twisted:
Post Reply