[Grafen] Efficiënt zoeken

[Verwijderd]

Ik zit met een opdracht voor school waarbij ik de werking van een taxibedrijf van een bepaalde dag moet simuleren. De volgende gegevens zijn op voorhand gegeven:

• Aantal beschikbare taxi's die klaarstaan aan het bedrijf.
• Aantal klanten met als info: plaats om ze op te pikken, plaats om ze af te zetten, periode van de dag waartussen ze opgehaald willen worden (uitgedrukt in minuten. Bv. 600 - 660 wil zeggen "tussen 10u en 11u 's ochtends")
• Een graf die de stad voorstelt waarin het taxibedrijf opereert. Op de nodes staan (mogelijk) klanten te wachten en de edges zijn gewogen (gewicht = tijd in minuten die nodig is om van node A naar node B te gaan via de edge)

Bedoeling is om met zo weinig mogelijk taxi's, zoveel mogelijk klanten op hun bestemming te krijgen in 1 dag tijd. Dit alles moet in Prolog geprogrammeerd worden.

Op dit moment heb ik al 2 oplossingsmethode's geprobeerd:

1. Een grote loop waarin ik een teller bijhoud die het aantal verstreken minuten voorstelt. Bij elke iteratie vindt dan een bepaalde minuut van de dag plaats. In elke iteratie doe ik 2 stappen namelijk de volgende: ik kijk of ik taxi's kan sturen naar klanten om ze op tijd op te halen en ik beweeg de reeds vertrokken taxi's vooruit. Telkens als een klant afgezet wordt, kijk ik of er op de huidige locatie een andere klant staat die opgepikt kan worden en deze vervoer ik dan. Staat er geen andere klant, stuur ik de taxi terug naar het bedrijf om dan klaar te staan voor een mogelijk volgende klant.
2. De andere methode die ik al heb is het uitplannen van de dag per taxi. Ik neem per iteratie in een loop een taxi en begin dan met een klant op te halen die vroeg opgehaald wil worden. Nadat deze klant opgehaald en weer afgezet is, kijk ik welk de meest dichtsbijzijnde klant is om deze dan te gaan ophalen. Hierdoor kan de taxi zo meerdere klanten na mekaar vervoeren zonder steeds terug te keren naar het bedrijf.

Op dit moment is methode 1 de snelste methode (gemiddeld tussen 30seconden en 1 minuut) omdat de enige grote berekeningen die uitgevoerd worden, het berekenen van de routes is (van het startpunt van de taxi naar de klant, van startpunt van de klant naar zijn eindpunt en het terugkeren van de taxi naar het bedrijf). Het berekenen van route's doe ik in een eigen implementatie van A* dus dat zit wel goed. Het zorgt ervoor dat ik zo'n 55% van mijn klanten kan vervoeren binnen de tijdsgrenzen wat helaas niet goed genoeg is. Bedoeling is dat we natuurlijk zoveel mogelijk klanten kunnen bedienen.

Methode 2 is het traagste (half uur tot zelfs een uur) omdat hij telkens bij het afzetten van een klant, alle andere klanten overweegt om naartoe te rijden. Ik dacht dat dit een beter resultaat zou geven qua hoeveelheid vervoerde klanten maar helaas kom ik tot de conclusie dat slechts 40% van de klanten nu vervoerd worden.

Nu heb ik wel al beetje gegoogle'd voor het zoeken in graffen maar ofwel kom ik dan op dingen uit zoals het kortste pad berekenen (wat ik al heb) ofwel zaken die niet altijd toepasbaar zijn omdat Prolog met lijsten werkt (wat zoals we allemaal weten, niet echt goed is worst-case gezien).

Heeft er iemand misschien ideëen voor goede algoritmes die ik kan gebruiken? Of bepaalde optimalisaties die ik kan doorvoeren om beter te kunnen zoeken in de graf? Een (kleine) duw in de goede richting (zoekwoorden voor in Google die ik over het hoofd zie of namen van algoritmes) wordt zeer geapprecieerd!

PS: ik weet dat tijd niet echt een goede meetmethode is voor goede code maar ik moet dit in een demo kunnen tonen met een maximumduur

[Boudewijn]

Je bent bekend met het algoritme van Dijkstra?

offtopic:
In nl is het graaf, en niet graf.

[Boss]

In plaats van per minuut kan je wellicht ook met een event-list werken, dan hoef je de minuten dat er niets wordt gedaan ook niets door te rekenen. Als een taxi vertrekt dan zet je in de event-list een event op het moment van aankomst. De event-list houd je gesorteerd op tijd. Zo kan je steeds het eerstvolgende event doorrekenen. Zeker omdat de edges de tijd weergeven die de taxi nodig heeft ben je zo veel sneller uit dan wanneer je gaat simuleren dat de taxi minuut voor minuut verder komt.

[Verwijderd]

Boudewijn schreef op dinsdag 27 december 2011 @ 21:16:
Je bent bekend met het algoritme van Dijkstra?

offtopic:
In nl is het graaf, en niet graf.

Jazeker, dat was mijn eerste algoritme voor het zoeken naar het kortste pad maar heb het dan omgevormd naar A*. Doel je erop dat ik Dijkstra moet gebruiken om de volgende klant te zoeken?

Boss schreef op dinsdag 27 december 2011 @ 21:18:
In plaats van per minuut kan je wellicht ook met een event-list werken, dan hoef je de minuten dat er niets wordt gedaan ook niets door te rekenen. Als een taxi vertrekt dan zet je in de event-list een event op het moment van aankomst. De event-list houd je gesorteerd op tijd. Zo kan je steeds het eerstvolgende event doorrekenen. Zeker omdat de edges de tijd weergeven die de taxi nodig heeft ben je zo veel sneller uit dan wanneer je gaat simuleren dat de taxi minuut voor minuut verder komt.

Had ik nog niet eens aan gedacht. Maar waarom zou dit dan beter zijn? Ik zie wel in dat het een aantal onnodige iteraties vermijd maar dit gaat mijn percentage van gediende klanten toch niet verhogen?

[pedorus]

Verwijderd schreef op dinsdag 27 december 2011 @ 21:37:
Jazeker, dat was mijn eerste algoritme voor het zoeken naar het kortste pad maar heb het dan omgevormd naar A*. Doel je erop dat ik Dijkstra moet gebruiken om de volgende klant te zoeken?

Dijkstra berekend het kortste pad (zeg van de taxiplaats) naar alle omliggende punten (potentiële nieuwe klant). Waarom zou A* een optimalisatie zijn?

Had ik nog niet eens aan gedacht. Maar waarom zou dit dan beter zijn? Ik zie wel in dat het een aantal onnodige iteraties vermijd maar dit gaat mijn percentage van gediende klanten toch niet verhogen?

Je zou 'per minuut' kunnen zien als een "calendar queue", veel efficiënter gaat het denk ik niet worden. Ik snap enkel niet waarom je tussenstappen zou hanteren voor de taxi's, dus blijkbaar doe je toch iets anders

Is het nu de bedoeling om een simulatie te maken, of is het de bedoeling om een zo efficiënt mogelijk algoritme te maken? Bij het laatste: Gezien dit planningsprobleem waarschijnlijk snel uit de hand loopt (over hoeveel taxi's/klanten hebben we het?) zou ik kijken naar dingen als hybrid genetic algoritms. Bij kleine aantallen is exact oplossen een mogelijkheid, desnoods brute-force

[Boudewijn]

pedorus schreef op dinsdag 27 december 2011 @ 22:50:

Dijkstra berekend het kortste pad (zeg van de taxiplaats) naar alle omliggende punten (potentiële nieuwe klant). Waarom zou A* een optimalisatie zijn?

Wellicht sneller, maar ik ken A* niet. Punt is dat ik hier maar 1 algoritme in gedachten kreeg... Dijkstra .

. Bij kleine aantallen is exact oplossen een mogelijkheid, desnoods brute-force

Bij schoolopdrachten is dat meestal niet de bedoeling . Iig als je >6.0 wil.

[pedorus]

Boudewijn schreef op dinsdag 27 december 2011 @ 22:56:
Wellicht sneller, maar ik ken A* niet. Punt is dat ik hier maar 1 algoritme in gedachten kreeg... Dijkstra .

A* houdt rekening met de minimale mogelijke reistijd vanaf een punt naar het eindpunt. Oninteressante punten worden zo niet onderzocht, maar dit werkt natuurlijk maar met 1 punt.

Bij schoolopdrachten is dat meestal niet de bedoeling . Iig als je >6.0 wil.

Brute-forcen is hier nog niet eens zo simpel. Noem het "backtracking" of "dynamic programming" en je krijgt hoger dan een 6 Opstapjes wellicht om naar branch&bound te gaan.

Ik denk dat Wikipedia een aardig overzicht geeft voor TS van dit soort trefwoorden.

[Verwijderd]

pedorus schreef op dinsdag 27 december 2011 @ 22:50:
[...]

Dijkstra berekend het kortste pad (zeg van de taxiplaats) naar alle omliggende punten (potentiële nieuwe klant). Waarom zou A* een optimalisatie zijn?

[...]

Doordat A* met een heuristiek werkt, kan ik veel sneller zoeken naar het kortste pad. Bepaalde paden hadden met Dijkstra een half uur aan berekentijd nodig, A* was al in 2 seconden klaar met een kortste pad.

pedorus schreef op dinsdag 27 december 2011 @ 22:50:
Is het nu de bedoeling om een simulatie te maken, of is het de bedoeling om een zo efficiënt mogelijk algoritme te maken? Bij het laatste: Gezien dit planningsprobleem waarschijnlijk snel uit de hand loopt (over hoeveel taxi's/klanten hebben we het?) zou ik kijken naar dingen als hybrid genetic algoritms. Bij kleine aantallen is exact oplossen een mogelijkheid, desnoods brute-force

Het is de bedoeling een simulatie te maken waarbij we eender welke algoritmes zelf mogen implementeren die een resultaat opleveren binnen 10 minuten (waarbij liefst zoveel mogelijk klanten geholpen zijn). Het is de bedoeling om ons eens goed met Prolog te laten werken. De dataset is fixed qua aantallen (125 taxi's, 500 klanten, graf heeft 2500 nodes en 2500 edges).
Brute-force is natuurlijk een oplossing maar als ik zie hoe traag oplossingsmethode 2 gaat (wat nog niet eens alles berekent zoals bij een brute-force), dan is dat zeker geen optie. Het moet in 10 minuten tijd resultaat kunnen geven en mijn 2e oplossingsmethode doet er al meer dan een uur over. Sowieso verwachten ze wel wat meer dan brute-forcen van iemand die een master opleiding gestart is

pedorus schreef op dinsdag 27 december 2011 @ 23:23:
Ik denk dat Wikipedia een aardig overzicht geeft voor TS van dit soort trefwoorden.

Ik zal eens in mijn oude cursussen Algoritmen En Datastructuren duiken (de hoofdstukken over grafen waren niet mijn beste onderdelen van die cursussen) en die link eens doorlezen, mss ben ik hier wel iets over het hoofd aan het zien (projecten die af moeten tijdens de blok, het zijn lange dagen tegenwoordig )

[pedorus]

Verwijderd schreef op dinsdag 27 december 2011 @ 23:40:
Doordat A* met een heuristiek werkt, kan ik veel sneller zoeken naar het kortste pad. Bepaalde paden hadden met Dijkstra een half uur aan berekentijd nodig, A* was al in 2 seconden klaar met een kortste pad.

Dat lijkt me een hele brakke implementatie van Dijkstra. Heel Nederland doorrekenen met Dijkstra is een kwestie van seconden (mits er voldoende werkgeheugen is). Je A*-implementatie met een 0-heuristiek (wat exact hetzelfde is als Dijkstra) zal het vast beter doen...

Het is de bedoeling om ons eens goed met Prolog te laten werken. De dataset is fixed qua aantallen (125 taxi's, 500 klanten, graf heeft 2500 nodes en 2500 edges).

Neem aan dat 2500 maximaal is? Je zou toch wel wat rondjes verwachten in zo'n graAf.

Sowieso verwachten ze wel wat meer dan brute-forcen van iemand die een master opleiding gestart is

Iemand die dit in deze tijd kan brute-forcen binnen de gestelde tijd verdient een 10. Dat is namelijk een hele brute tool

Ik zal eens in mijn oude cursussen Algoritmen En Datastructuren duiken (de hoofdstukken over grafen waren niet mijn beste onderdelen van die cursussen) en die link eens doorlezen, mss ben ik hier wel iets over het hoofd aan het zien (projecten die af moeten tijdens de blok, het zijn lange dagen tegenwoordig )

Helaas, is er is geen eenvoudige oplossing voor dit probleem. Iets met NP enzo.

[GlowMouse]

Het lijkt een beetje op Clarke & Wright's Savings Algorithm (wat geen optimale oplossing geeft), maar dan net iets lastiger nog ivm ophaaltijden. Je kunt een bepaalde oplossing nog proberen met local search icm simulated annealing proberen te verbeteren.

[Verwijderd]

pedorus schreef op woensdag 28 december 2011 @ 00:24:
[...]

Dat lijkt me een hele brakke implementatie van Dijkstra. Heel Nederland doorrekenen met Dijkstra is een kwestie van seconden (mits er voldoende werkgeheugen is). Je A*-implementatie met een 0-heuristiek (wat exact hetzelfde is als Dijkstra) zal het vast beter doen...

[...]

Ja ik stond er zelf beetje van te kijken hoe traag die Dijkstra implementatie ging, niet echt wat ik verwacht had. Lag het aan mijn implementatie of misschien Prolog die nogal slecht met geheugen overweg gaat, ik weet het niet. Ik blijf lekker met die A* werken nu deze het snelste is

Neem aan dat 2500 maximaal is? Je zou toch wel wat rondjes verwachten in zo'n graAf.

Ja normaalgezien moeten we de boel kunnen presenteren met de dataset die ze gegeven hebben dus kan ik wel uitgaan van maximaal 2500 enzo. En ik blijf maar fouten maken met het woord "graaf"

GlowMouse schreef op woensdag 28 december 2011 @ 00:29:
Het lijkt een beetje op Clarke & Wright's Savings Algorithm (wat geen optimale oplossing geeft), maar dan net iets lastiger nog ivm ophaaltijden. Je kunt een bepaalde oplossing nog proberen met local search icm simulated annealing proberen te verbeteren.

Had nog nooit van Clarke&Wright's Savings Algorithm gehoord maar na het lezen van een pdf erover lijkt het daar idd wel op. Als ik iets kan doen met de ophaaltijden die meetellen als gewicht van een klant, kan ik er wel iets mee aanvangen. Een dag bestaat toch maximaal uit 1440 minuten, dat is dan de "maximumlading" van een taxi. Moet ik alleen nog zien hoe ik dan rekening ga houden met de ophaaltijden en de afstanden van startpunt naar klant, tussen 2 klanten en van klant naar eindpunt.

[pedorus]

Verwijderd schreef op woensdag 28 december 2011 @ 09:04:
Ja ik stond er zelf beetje van te kijken hoe traag die Dijkstra implementatie ging, niet echt wat ik verwacht had. Lag het aan mijn implementatie of misschien Prolog die nogal slecht met geheugen overweg gaat, ik weet het niet. Ik blijf lekker met die A* werken nu deze het snelste is

2 seconden is nog steeds vrij veel. Overigens zou je in dit geval ook prima Floyd-Warshall of Johnson kunnen gebruiken, 2500 punten is binnen een halve minuut ook wel klaar, en dan is dit deelprobleem uit de weg. Hou je nog 9 minuten over voor de rest.

Had nog nooit van Clarke&Wright's Savings Algorithm gehoord maar na het lezen van een pdf erover lijkt het daar idd wel op. Als ik iets kan doen met de ophaaltijden die meetellen als gewicht van een klant, kan ik er wel iets mee aanvangen. Een dag bestaat toch maximaal uit 1440 minuten, dat is dan de "maximumlading" van een taxi. Moet ik alleen nog zien hoe ik dan rekening ga houden met de ophaaltijden en de afstanden van startpunt naar klant, tussen 2 klanten en van klant naar eindpunt.

Ik vrees dat ophaaltijd hier zodanig belangrijk is, en dat pickup & delivery ook een zodanige factor is, dat C&W niet bruikbaar is. Je kunt beter kijken naar oplossingen voor het k-taxi problem. Je huidige oplossing 1 gebruiken als startpunt voor het genoemde simulated annealing lijkt me ook prima, enkel terugsturen naar het bedrijf lijkt me wat onhandig...

Overigens, zit je met 1 persoon/groep in de taxi of met meer? Is het geheel on-line of weet je alle ritjes van te voren?

[Verwijderd]

pedorus schreef op woensdag 28 december 2011 @ 12:56:
2 seconden is nog steeds vrij veel. Overigens zou je in dit geval ook prima Floyd-Warshall of Johnson kunnen gebruiken, 2500 punten is binnen een halve minuut ook wel klaar, en dan is dit deelprobleem uit de weg. Hou je nog 9 minuten over voor de rest.

Thanks voor de tips.

Ik vrees dat ophaaltijd hier zodanig belangrijk is, en dat pickup & delivery ook een zodanige factor is, dat C&W niet bruikbaar is. Je kunt beter kijken naar oplossingen voor het k-taxi problem. Je huidige oplossing 1 gebruiken als startpunt voor het genoemde simulated annealing lijkt me ook prima, enkel terugsturen naar het bedrijf lijkt me wat onhandig...

Overigens, zit je met 1 persoon/groep in de taxi of met meer? Is het geheel on-line of weet je alle ritjes van te voren?

Nog nooit van het k-taxi probleem gehoord, zal ik eens wat over lezen. Ja het terugsturen gebeurt nogal naïef eigenlijk. Nu zat ik te denken om in plaats van enkel te kijken of er op de huidige node (waar je zojuist iemand afgezet hebt) een nieuwe klant staat, om ook de directe buren van de node in overweging te nemen, eventueel zelfs met het even laten wachten van de taxi (met een treshold dan van bijvoorbeeld 15 minuten).

Nu zijn er situatie's dat een taxi 's ochtends vertrekt, 's middags terugkeert en daarna nog terug vertrekt om 's nachts terug te keren. Die rit terug en weer heen kan die dan evengoed spenderen aan het vervoeren van een taxi.

Er mogen trouwens ook meerdere personen in een taxi (max. 4) en de klanten zijn altijd op hun eentje. Zo heb ik het al ingebouwd dat hij op de weg tussen beginplaats en eindbestemming van een klant kijkt of hij een andere klant ook kan oppikken die ook naar dezelfde eindbestemming moet (wat helaas in de gegeven dataset maar in 1 van de 500 gevallen zo is).

[RobIII]

Verwijderd schreef op woensdag 28 december 2011 @ 14:47:
(met een treshold dan van bijvoorbeeld 15 minuten)

Waarom een hardcoded threshold? Kijk hoe lang de rit naar HQ duurt en zoek ritten die binnen die tijd in je omgeving moeten starten; wanneer die tijd (+ de rit ernaartoe) korter is is het onzin om naar HQ te rijden (tenzij je verplichtte pauzes en CAO geneuzel in de berekening wil opnemen ). En als je dan toch naar HQ zou rijden maar vervolgens weer tijd verliest omdat je vanuit HQ moet vertrekken i.p.v. de huidige locatie ben je ook niet erg efficiënt bezig volgens mij

[pkuppens]

Ik snap dat iedereen in grafen algoritmes denk, maar is dit niet scheduling?

De taxi's zijn machines, en de ritten zijn jobs.
Ok, je zult misschien wat aan de jobs moeten rekenen, om op de goede beginplek te komen.

Verder moet je wel in het kader van Prolog proberen te denken.
En laten zien dat je alle definities en operaties een beetje doorhebt, en wat de toepassingen zijn.

[Verwijderd]

RobIII schreef op woensdag 28 december 2011 @ 15:06:
[...]

Waarom een hardcoded threshold? Kijk hoe lang de rit naar HQ duurt en zoek ritten die binnen die tijd in je omgeving moeten starten; wanneer die tijd (+ de rit ernaartoe) korter is is het onzin om naar HQ te rijden (tenzij je verplichtte pauzes en CAO geneuzel in de berekening wil opnemen ). En als je dan toch naar HQ zou rijden maar vervolgens weer tijd verliest omdat je vanuit HQ moet vertrekken i.p.v. de huidige locatie ben je ook niet erg efficiënt bezig volgens mij

Goed punt van die threshold

pkuppens schreef op woensdag 28 december 2011 @ 15:17:
Ik snap dat iedereen in grafen algoritmes denk, maar is dit niet scheduling?

De taxi's zijn machines, en de ritten zijn jobs.
Ok, je zult misschien wat aan de jobs moeten rekenen, om op de goede beginplek te komen.

Ik had helemaal nog niet stilgestaan bij scheduling. Graafalgoritmes gebruiken leek mij het meest logische

[IceM]

Is het de bedoeling dat je alle taxis telkens terug laat gaan naar het startpunt? Als je de taxis laat staan op hun laatste afleverplek krijg je veel meer spreiding en dan zul je kortere paden vinden naar je klanten.

[Verwijderd]

Taxis moeten enkel op het einde van de dag terugkeren. Nadat ze een klant hebben afgeleverd mogen ze in feite doen wat ze willen als de dag nog niet voorbij is. Het is dus zeker mogelijk om ze een tijd te laten staan om later weer klanten op te pikken die dichtbij zijn.

[djluc]

Dat is leuke kansberekening, waat laat je de taxi wachten, wat heeft de meeste kans op passanten, wat zijn de kosten om daar te staan, hoe vaak haal je iemand op in die omgeving?

[Verwijderd]

pkuppens schreef op woensdag 28 december 2011 @ 15:17:
Ik snap dat iedereen in grafen algoritmes denk, maar is dit niet scheduling?

Dat was mijn eerste gedachte bij het lezen van de opdracht omschrijving. De graaf komt er natuurlijk wel bij kijken bij de bepaling van de jobtijd.

Ik ben benieuwd hoe een simpel algoritme als het volgende het doet:

1. Spring naar de vroegste starttijd voor een nog niet geplande rit, berken rittijd en assign een taxi, registreer waar deze eindigt en hoe laat (Berekening van twee ritten tijd om er te komen, tijd van de rit).
2. spring naar de volgende starttijd en bepaal of al ingezette taxi op tijd klaar zijn om die af te handelen, zo ja zet degene in die er het snelste is (taxi's blijven op eindpunt staan) enzo nee, zet een nieuwe in als nog beschikbaar. Registreer eindpunt en eindtijd van de rit. (berekening van 1 rit per 1 ingezette taxi en 1 rit voor n nog niet ingezette taxis, plus 1 rit voor de rit als er een taxi voor beschikbaar is)
3. Spring naar 2. totdat alle ritten assigned zijn.


Stap twee kan je sneller maken door de eerste ingezette taxi te nemen die op tijd in het interval bij de rit kan zijn in plaats van de snelste.

De oplossing zal vast niet optimaal zijn, maar ik zie niet zo snel hoe je met minder reisduur berekeningen uitkomt. (Aan de anderekant is het ook 14 jaar geleden dat ik me met dit soort problemen bezig hield )