[hulp] Aanpassing shortest path (dijkstra) algoritme

[iLaurens]

Hallo, ik hoop hier programmeurs en operationele research fanatisten te vinden die me kunnen helpen met mijn probleem!

Voor een opdracht is het de bedoeling dat ik een aanpassing maak op een shortest path probleem. Ik zal allereerst uitleggen wat de situatie is.
Ik heb een directed graph G=(V,E) waarin V de set met vertices is (plaatsen) en E de set met edges (verbindingen tussen plaatsen). De afstanden tussen de plaatsen zijn bekend. Ik moet proberen om met zo min mogelijk kilometers een pakket te bezorgen van x naar y. Echter de situatie is iets anders.

Er zijn een beperkt aantal trucks en ze zijn al gepositioneerd. Een truck heeft een licentie om maar in 2 van te voor gespecificeerde landen te mogen rijden. Plaatsen zijn dus ook gekoppeld aan een land, en je hebt dus bijvoorbeeld 2 trucks nodig als je van Amsterdam naar Praag wilt. (truck1: Amsterdam > Berlijn, truck2: Berlijn > praag). Maar bij het berekenen van de kortste route moet er rekening mee gehouden worden met het plaatsen van de trucks! Dus als in Berlijn truck2 nog niet klaar stond, dan komt daar de afstand van het brengen van truck2 naar Berlijn bij.

Weet iemand misschien hoe ik een shortest-path algoritme zo kan aanpassen dat die een kortste route berekend die ook rekening houd met de (ver)plaatsing van de trucks?

[Gomez12]

Simpel : verleng de paden met de rijafstand van de lege truck (even aangenomen dat het enkel eenmalig is, moet het continue gebeuren dan heb je nog tal van andere factoren die gaan meespelen ( bijv tijd van de dag, rustpauzes chauffeurs, werktijden chauffeurs, maximale rijtijden chauffeurs, tijdsspecifieke paden etc. etc.))

[iLaurens]

Dat heb ik inderdaad ook overwogen, echter zit er een probleem daarin;
Stel je kan van A naar B, en van B naar C. Stel dat je zegt dat truck2 naar B moet reizen, hoe tel je dat daar dan bij op? En stel dat je een truck hebt die gewoon van A, via B naar C kan? Dan krijg je wel de extra kilometers van die verplaatste truck richting B, maar dan gebruik je die truck niet eens!
Bovendien kan je de truck op meerdere manieren plaatsen naar verschillende plekken. Dus van te voor weet je nog niet welke truck je waar heen stuurt...

[Gomez12]

A->B+truck->B->C is pad 1.
A->B->C is pad 2.

Je mogelijke truckverplaatsingen genereren enkel maar meer paden (met andere lengtes), de hoeveelheid paden moet geen echte invloed hebben op je shortest-path berekening...

Daarom zeg ik ook als het eenmalig is, als het enkel voor school is etc. etc. In de praktijk werkt het niet zo simplistisch (je mogelijke paden blaast gigantisch op en je hebt nog 1000'en randvoorwaarden waar je rekening mee moet houden (een chauffeur die 8 uur per dag mag rijden is waardeloos als die 6 uur moet rijden naar locatie dan 1 uur pakketje wegbrengt en dan de volgende dag weer 6 uur bezig is met terugrijden))

In wezen is het probleem net zo moeilijk als dat er randvoorwaarden zijn, in jouw TS zijn de randvoorwaarden simpel dus volstaat ook supersimpele oplossing

[Vaan Banaan]

nvm

[ Voor 104% gewijzigd door Vaan Banaan op 22-11-2012 00:58 . Reden: Het gaat om de minimale totale afstand van de trucks, niet over de kortste levertijd. ]

[D-Raven]

Met het risico dat ik ergens overheen kijk (ik heb de TS snel even gescanned )
Je moet gebruik gaan maken van je forward costs.
Dus hoeveel kost het om van A naar B te gaan? Afhankelijk van je graaf is dit A -> B = bv 1 want geen andere vrachtwagen komt hieraan te pas.

Maar als je dan van B naar C gaat kost het niet 1 maar +1 dus 2, want: 1 punt voor de standaard cost om van B -> C te gaan, maar +1 omdat er nog een andere vrachtwagen naartoe moet.

Tenminste ik ga ervanuit dat je weet waar de vrachtwagens nu staan?
In dat geval doe je een preprocessing over de waardes in je graaf, waarbij je je forward costs aanpast. Op deze manier reflecteerd je graaf de aanwezigheid van vrachtwagens, maar hoef je je search algoritme verder niet aan te passen.

Versimpeling van je domein is dit.

[Vaan Banaan]

code:

    Plaatsen     start
t1: A, B, C        C
t2: A, B, D        D

Pakket: D->A

    A
   ^ ^
10/   \4
 /  4  \
B ----->C t1
^ <----
|    3
| 3
|
D t2

  naar A  B  C  D          naar  A  B  C  D
t1 van                   t2 van
  A    0                   A     0
  B    8  0  4             B    10  0
  C    4  3  0             C
  D                        D    13  3     0

• Zoek de eerste de beste truck die bij het pakket kan komen
In dit geval is dat t2(D)->D, toevallig staat die al op de goede plek, Cost=0
• Dan de plaatsen zoeken waar de truck heen kan rijden:
t2(D)->A is gelijk de eindbestemming, Cost=13

t2(D)->B is niet de eindbestemming, Cost=3
• Opnieuw van alle overige trucks kijken die bij B kunnen komen
Alleen t1 blijft in dit voorbeeld over, Cost = 3 + t1(C)->B = 3 + 3 = 6
• En weer kijken waar die heen kan rijden
Aangezien er verder geen trucks rijden, hoeft alleen naar t1(B)->A gekeken te worden of hier een waarde staat.
t1(B)->A = 8 dus de Cost = 6 + 8 = 14

t2(D)->A = 13 is dus de route met de minste kilometers

[ Voor 181% gewijzigd door Vaan Banaan op 22-11-2012 01:31 ]

[bwerg]

D-Raven schreef op dinsdag 20 november 2012 @ 08:39:
Versimpeling van je domein is dit.

Dit kan inderdaad, omdat elke truck maar in 2 landen mag rijden. Na elke route móet je dus van truck wisselen, als je een pakketje van A->B hebt gebracht, en je wil daarna van B->C dan zul je sowieso een andere truck naar B moeten halen, die vervolgens A->B aflegt. Dus totale kosten voor A->B zijn d(A,B) + d( waarbij d( de kosten zijn om de truck naar B te halen (en eventueel tel je ook de kosten op om de truck weer terug te brengen naar home-base, als dat moet). Zelfde geldt ook voor de truck A->B, als die in het begin nog niet bij A is. Die kosten kun je dus gewoon vervangen zodat je een nieuwe graaf krijgt.

[Vaan Banaan]

Ik kaap het topic misschien, maar ik vind dit wel een leuk onderwerp en de TS reageert niet meer.

code:

Truck Plaatsen     start
t1:   A, B, C        C
t2:   A, B, D        D

Pakket: D->A

    A
   ^ ^
10/   \4
 /  3  \
B ----->C t1
^ <----
|    2
| 3
|
D t2

Ik snap het versimpelen van de graaf niet, of eigenlijk wat bwerg en DeathRaven bedoelen
De kortste route is in dit geval:
t2: D->B = 3
t1: C -> B -> C -> A = 9
Cost = 3 + 9 = 12
Door het heen weer rijden van t1 snap ik niet hoe ik de forward costs in die graaf kan toevoegen en hem kan versimpelen (van domein)
Kan iemand mij dit duidelijk maken?

[bwerg]

Jouw situatie is iets moeilijker dan die van de TS. De TS heeft het over dat elke truck maar in twee landen mag rijden, dus maar op één lijn (en ik nam aan dat er maar één punt per land was). Als je die edge wil gebruiken zul je dus de bijbehorende truck moeten oproepen, dus per lijn kun je de bijbehorende kosten voor die truck er van tevoren bij optellen (als er meerdere trucks per lijn zijn dan neem je natuurlijk altijd de goedkoopste).

Als een truck meerdere landen in kan dan kan je de situatie niet versimpelen naar een graaf waar je op de 'normale' manier de kosten aan kan berekenen. Je kan een truck dan door meerdere landen (A -> B -> C) heen laten rijden om geen extra trucks op te hoeven halen (voor bijv. B -> C), maar die overgeslagen trucks zul je misschien wel nodig hebben als je vanuit een ander punt komt (D -> B -> C). Je kunt de kosten voor B -> C dus niet eenduidig voorspellen zonder de hele route in acht te nemen.

Wil je er leuke dingetjes mee doen, dan werkt de versimpeling ook al snel niet meer. Bijvoorbeeld meerdere pakketjes, waarbij een truck bijvoorbeeld op de heenweg pakketje 1 doet en op de terugweg pakketje 2 om efficiënter te werkt te gaan.