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.

Tour Optimization a la PTV

Postby Bernd Welter » Tue Aug 13, 2019 3:41 pm

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.

Feedback is welcome!

Bernd Welter
Senior Technical Consultant Developer Components
PTV GROUP - Germany

Bernd at Youtube
User avatar
Bernd Welter
Site Admin
Posts: 1479
Joined: Mon Apr 14, 2014 10:28 am

Return to PTV xTourServer