Traveling Salesman Problem (2.0)

[Ypho]

Disclaimer: Dit is een hele lap tekst, onderaan staat een TL;DR als je meer info wilt voordat je gaat lezen

Ik ben bezig met een nieuw systeem waarmee een planning gemaakt kan worden voor klantbezoeken. Deze planning heeft enkele honderden locaties (verdeeld over meerdere klanten, dus ik praat in "locaties") die bezocht moeten worden.

In totaal zijn er 5 medewerkers in dienst die dagelijks op de weg zitten om deze locaties te bezoeken. Er moet rekening gehouden worden met verschillende werktijden (tijd die iemand bezig is) per locatie, maar ook met bepaalde openingsdagen in de week of locaties waar bepaalde medewerkers niet mogen komen.

Informatie:

• 4-5 Medewerkers, in de zomermaanden iemand extra
• Enkele honderden locaties per maand die bezocht moeten worden, verdeeld over heel Nederland
• Op sommige locaties mag een medewerker niet komen (er zijn een aantal locaties waar bv alleen een projectleider mag komen)
• Locaties kunnen bepaalde dagen in de week gesloten zijn (zelfs bepaalde dagdelen!)
• Locaties kunnen op gesloten zijn in een bepaalde periode (bv winter of vakanties)
• Bij de meeste locaties zijn de medewerkers ongeveer 15-20 minuten bezig, met uitzonderingen richting de 30+ minuten
• Een medewerker werkt 8 uur per dag
• Beginpunt van een dag is huisadres van een medewerker, of adres van kantoor
• Eindpunt op een dag kan verschillen

NB:

1. Vooraf is bekend welke locaties bezocht moeten worden in een maand
2. Of een medewerker toegang heeft, of wanneer een locatie gesloten is, wordt vooraf ingesteld
3. De totale werktijd die een medewerker nodig heeft per locatie, wordt vooraf berekend
4. Start- en eindpunt van een route (kantoor, huisadres, lab etc) is vooraf bekend

Het probleem
Iedere maand (rond de 15e) moet de planning voor de volgende maand gemaakt worden. Hier moeten alle locaties verdeeld worden over de week (ma-vr) bij de verschillende medewerkers. Hierbij moet rekening worden gehouden efficiëntie (zo min mogelijk kilometers) en de informatie hierboven.

Dit is een bekend probleem (Traveling Salesman Probleem, Wikipedia), maar omdat hier wat extra haken en ogen aanzitten, ben ik benieuwd naar jullie ideeën.

Op dit moment zit ik nog in de fase om alles uit te denken, en heb dus nog niets geprogrammeerd. Uiteindelijk moet dit in een PHP webapplicatie gebruikt worden, het moet dus in PHP geprogrammeerd worden.

Huidige situatie:
De vorige planning heb ik ook gemaakt, maar deze wordt handmatig gevuld. Iedere maand is er een soort "verkenner" waarin alle afspraken staan van de betreffende maand. Deze zijn grotendeels onderverdeeld in "routes", die nu handmatig worden gemaakt. Een route wordt in de planning gezet, en bevat meestal 10-15 locaties bij elkaar in de buurt. Dit werkt redelijk, maar omdat sommige klanten bijvoorbeeld maar één keer per jaar worden bezocht, en andere twee keer per maand, blijven er altijd een hoop afspraken in de verkenner die los gepland moeten worden (dit kan op dezelfde dag als een tocht, maar gaat niet via de tocht zelf).

Tevens gebeurt het regelmatig dat locaties een dag niet kunnen, en daarmee dus een deel van de tocht verplaatst moet worden (zie informatie). Ook komen er regelmatig nieuwe locaties (en dus afspraken) bij (al dan niet ad hoc), of gaan deze weg. Nu gebeurt het ook regelmatig dat medewerker soms op een dag naar een locatie moeten die een week eerder op de route lag, dus dit zijn verspilde kilometers.

Vooraf staan dus alle afspraken in een tabel. In deze tabel staat de informatie van de afspraak, de medewerker, datum, status en wat meer info (niet belangrijk voor deze casus). Als de afspraak nog niet gepland is, is de datum de eerste van de maand, en de status 0 (niet gepland). Zodra een afspraak gepland is, wordt de status > 0 (afhankelijk van het type "Voorlopig gepland", of "Gepland").

Mijn idee:
Het idee van "tochten" wat er nu is (gegroepeerd), is niet verkeerd, alleen moet dit dus automatisch gaan gebeuren. Ik zat zelf te denken aan het groeperen op basis van postcodegebieden. Dit is vrij efficiënt ingedeeld in Nederland.

Stel dan ik even Noord-Holland-Noord pak, postcodegebied 17XX. Het idee wat ik zou hebben is om hier alle locaties te verdelen in verschillende "groepen" met een maximale werkdag van: 8 uur - reistijd van startpunt naar postcodegebied - reistijd van postcodegebied naar eindpunt. Via de Google API zijn er mogelijkheden om deze reistijden te berekenen, maar dit zou bijvoorbeeld ook kunnen op basis van een postcodetabel (indien beschikbaar).

Nu is dit stap 1. Want als ik een aantal locaties op één dag heb gepland, komt stap 2. Hoe bereken ik op die dag de meest efficiënte route. Ik kan natuurlijk alle routes gaan uitstippelen, maar met 15 locaties is dat 15! (faculteit) (uitgaande van "brute force", dat is onmogelijk om te doen (vindt Google ook niet leuk). Het makkelijkste hier lijkt mij het sorteren op postcodes, dus bijvoorbeeld alle 1785 na elkaar (Den Helder), en daarna pas 1791 (Texel).

Maar dan komt de derde stap. Hoe ga ik bijvoorbeeld de beste route berekenen voor alle adressen met dezelfde postcode-cijfers, bijvoorbeeld van de 15 locaties op een dag zitten er 5 in Den Helder (1785). Uiteraard kan ik dit ook sorteren (1785AA t/m 1785ZZ), maar soms kom je een stad binnenrijden bij 1785RT en moet je bij 1785FF de stad uit naar Texel.

Stap 2 en 3 gaan wellicht iets te ver. Als ik al een indeling heb kunnen maken zou dat al mooi zijn.

Alternatief voor stap 2/3 2: Een dag opdelen kan ook via het "Nearest-neighbour" principe. We hebben een vast startpunt (huisadres of kantoor), en we kijken welke locatie daar het dichtste bij ligt, vanaf dat punt kijken we welke daar het dichtste bij ligt, etc. Dit zou kunnen werken, maar is ook niet altijd optimaal.

Dit betreft één route, maar het kan zijn dat een bepaald gebied (Amsterdam bijvoorbeeld), veel bezoeklocaties hebben. Dit moet over meerdere dagen verdeeld worden, dus stap 1-3 moet dus op meerdere dagen worden gedaan.

Wellicht sla ik iets te ver in door, maar ik ben benieuwd wat jullie voor ideeën hebben hierin.

Groeperen:
Bovenstaand is mijn idee betreffende het "verdelen" van de locaties in meerdere groepen, maar we zitten natuurlijk ook nog met de overige punten. Mag een medewerker wel/niet op een locatie komen. Zijn bepaalde locaties op één dag in de week dicht of een deel van de maand op vakantie?

Mijn idee hierin zou zijn om éérst alle locaties die problematisch zijn (die niet iedere dag voor iedere medewerker beschikbaar zijn) te plannen, en hieromheen verder te plannen. Bij gemiddeld 20 werkdagen per maand en 4 man personeel heb ik 80 dagen per maand om deze in te plannen.

Als ik dit combineer, kan ik denk ik het beste groepen met locaties laten berekenen als volgt:
|-------------------------
| GROEP 1
|-------------------------
|Beperkingen:
|- Alleen medewerker X
|- Niet op dinsdag
|-------------------------
|- Locatie 1
|- Locatie 2
|- Locatie n
|-------------------------

Op deze manier kan ik per maand dus zo'n 80-100 groepen maken (uitgaande van 20 dagen 4-5 man personeel waarvan een aantal dagen ziekte of voor overhead).

Uiteindelijk is dit niet zo zeer één Traveling Salesman-problem, maar vele kleintjes. Nu is de aanpak hierin hetzelfde, maar het lijkt me verstandig om eerst eens te gaan uitdenken hoe ik alles efficiënt ga verdelen over 4 medewerkers en 20 werkdagen voordat ik me bezig ga houden met de routes per dag.

Ergo:
- Ik zoek geen hulp bij het maken van code, dit lukt me wel (denk ik). Ik ben vooral benieuwd naar jullie ideeën. Zit ik zelf de goede kant op te denken, vergeet ik dingen etc. Tips zijn welkom!
- De route moet zo optimaal mogelijk zijn, maar het hoeft niet "perfect" te zijn. Al wordt er maar 5-10% bespaard op het aantal kilometers is dit al prima! Het zou al mooi zijn als ik goed kan groeperen, de optimale route op een dag kan een medewerker zelf ook zelf wel inschatten.

TL;DR: Ik zoek een oplossing voor het Traveling Salesman probleem, alleen gaat het niet om meerdere locaties op één dag bij één medewerker, maar om enkele honderden locaties verdeeld over de maand over meedere medewerkers.

Mochten jullie tips hebben, meer informatie willen, of verduidelijking van mijn kant laat het maar even weten.

[ Voor 3% gewijzigd door Ypho op 18-12-2013 09:09 ]

[Coca-Cola]

Niet helemaal doorgelezen, maar op het eerste gezicht lijkt dit op hetzelfde probleem wat bv scholen hebben om roosters te maken en daar zijn mooie oplossing voor die gebruik maken van (google maar eens op 'genetic algorithm time table' of 'evolutionary agorithm time table').

[pedorus]

Ik zou me afvragen of je dit zelf moet gaan programmeren. Volgens mij is dit een standaard-probleem dat al is opgelost, en gaat het veel tijd kosten om dit efficiënt op te lossen en in een gebruikersvriendelijk stukje software te krijgen. Dus [google=field service planning] geeft als eerste hit http://www.ortec.nl/oplos...ele_service_planning.aspx en een hele bunch aan anderen.

Als het hobbymatig of studiematig is, dan kunnen we het ook wel over algoritmes gaan hebben, maar voor een echt bedrijf zou ik denken dat bestaande software dit beter kan. Ik weet niet wat zoiets precies kost, maar ik denk dat de kans groot is dat je met brandstof-/tijdkosten de softwarekosten er uit haalt.

Qua taal lijkt php mij ook niet zo handig in dit verband, aangezien het vaak ook op evaluatiesnelheid aankomt. Dus ik zou meer aan iets als Java, c# of c++ denken, in ieder geval voor het stukje dat de daadwerkelijke optimalisatie doet.

10-15 plekken optimaal in een route zetten, gegeven dat je een afstandentabel hebt, is niet zo heel moeilijk. Met iets als simulated annealing kan dit bijvoorbeeld ('s nachts) prima berekend worden, met een zeer grote kans op de optimale route. Openstreetmap heeft eventueel gratis map-data.

[Ypho]

@pedorus: Ortec heb ik inderdaad ook gezien, maar die voldoet niet aan de "eisen" die we hebben helaas (met name rekening houden met welke medewerkers wel/niet ergens mogen komen)

10-15 plekken optimaal maken is op zich ook geen probleem. Dit kan bijvoorbeeld al geautomatiseerd worden met RouteXL. Maar in eerste instantie moeten 400 locaties eerst optimaal verdeeld worden (qua afstand) over 5 medewerkers en 20 werkdagen per maand. Daarna pas per dag een route, maar dat wordt fase 2. Een medewerker zit op een kaartje waar hij moet zijn, dan kan hij/zij zelf vooralsnog wel bepalen wat een goede route is.

Qua taal ben ik niet echt afhankelijk, maar de applicatie waar de planning in staat is gemaakt in PHP. Het plan-gebeuren hoeft niet persé PHP te zijn, maar heel veel andere programmeertalen spreek ik niet

[ Voor 14% gewijzigd door Ypho op 18-12-2013 14:45 ]

[pedorus]

Ypho schreef op woensdag 18 december 2013 @ 14:44:
@pedorus: Ortec heb ik inderdaad ook gezien, maar die voldoet niet aan de "eisen" die we hebben helaas (met name rekening houden met welke medewerkers wel/niet ergens mogen komen)

Dit lijkt me eigenlijk een standaardrequirement van zo'n pakket, ik neem aan dat in zo'n pakket medewerkers bepaalde skills kunnen hebben en dat een klant bepaalde skills vereist, lijkt me zeer normaal. Je hebt nu de requirements toch al vrij duidelijk uitgeschreven, dus ik zou ze gewoon op de mail zetten, dan zie je vanzelf wel of ze het kunnen.

Maar in eerste instantie moeten 400 locaties eerst optimaal verdeeld worden (qua afstand) over 5 medewerkers en 20 werkdagen per maand. Daarna pas per dag een route, maar dat wordt fase 2.

De optimale verdeling zal natuurlijk wel afhangen van mogelijke routes. Ik kan me zo voorstellen dat je in een heuristiek begint met moeilijk te plannen locaties (weinig vrijheden) en dan bij de initiële routes andere locaties probeert toe te voegen.

Het plan-gebeuren hoeft niet persé PHP te zijn, maar heel veel andere programmeertalen spreek ik niet

Och, een nieuwe programmeertaal leren is over het algemeen niet zo moeilijk. Een goede heuristiek ontwikkelen voor een NP-compleet probleem, en een gebruikersvriendelijke interface, tsja, dat is een heel ander verhaal... In een bestaand pakket zitten waarschijnlijk vele manjaren aan werk.