[Routing] Routing algorithms - proposed workaround for Stefan

Marcus Wolschon Marcus at Wolschon.biz
Mon Sep 22 07:55:14 BST 2008



On Sun, 21 Sep 2008 22:33:16 +0200, "Nic Roets" <nroets at gmail.com> wrote:
> Well take any traveling salesman problem : You are given a graph and
> required to find the shortest path from A to B that visits at all the
> nodes
> in the 'cities' subset at least once. Now  create a new graph by adding
> node
> C and an edge BC. Now you choose your metric to be the length of each
> edge,
> except for BC. The metric for BC is 0 if the route travel included visits
> to
> all the cities, and very large (sum of all edges / infinite) otherwise.
> Now
> you have Stefan's problem. So finding an efficient solution for the
> general
> case looks very unlikely.

Yes, any TS-problem is none to be hard
but I don't think you can reduce Stefan's metric-issue to an traveling-saleman
-problem because the nodes to visit are not none a-priori.

  The problem:

He has a metric(startNode,EndNode,WayID) that depends on the time you arrive
at startNode and thus on the sum of the metrics of the segments forming the
most optimal path to startNode (this is not the backtrack from startNode to the
node where your routing started at the time metric() is evaluated).

 Proposed workaround for stefan:

Of cause you can do this by invoking dikjstra recursively inside the metric()
-function and cache any matric already calculated but that would yield exponential
runtime.
I think the best way to go here is to use only an aproximation of the time like
hour%2 or a heuristic like AirDistance(globalStartNode, startNode) * AverageSpeed
inside the metric-function. That could be done in contant time.

>From an earlier mail in german:

> Stefan Pflumm schrieb:
>> Hallo Marcus,
>>
>> Ich arbeite gerade an einer Diplomarbeit zur Erfassung von
>> Fahrzeiten mit Hilfe von GPS-Tracks. Die Fahrzeiten werden für ein
>> Straßensegment (der Weg zwischen zwei Abbiegemöglichkeiten)
>> gespeichert. Zusätzlich möchte ich ein dynamisches Routing
>> ermöglichen, d.h. die getCost-Methode
>> soll abhängig von der Ankunftszeit an diesem Straßensegment die
>> Fahrdauer zwischen den vorhandenen Daten berechnen.


Marcus





More information about the Routing mailing list