UNIVERSITEIT GENT FACULTEIT ECONOMIE EN BEDRIJFSKUNDE ACADEMIEJAAR 2008 – 2009
Optimalisatie van de logistieke processen van de bennewagens in ArcelorMittal Gent
Masterproef voorgedragen tot het bekomen van de graad van Master in de Toegepaste Economische Wetenschappen: Handelsingenieur
Liselotte Loosveldt onder leiding van Prof. dr. ir. Birger Raa
UNIVERSITEIT GENT FACULTEIT ECONOMIE EN BEDRIJFSKUNDE ACADEMIEJAAR 2008 – 2009
Optimalisatie van de logistieke processen van de bennewagens in ArcelorMittal Gent
Masterproef voorgedragen tot het bekomen van de graad van Master in de Toegepaste Economische Wetenschappen: Handelsingenieur
Liselotte Loosveldt onder leiding van Prof. dr. ir. Birger Raa
PERMISSION Ondergetekende verklaart dat de inhoud van deze masterproef mag geraadpleegd en/of gereproduceerd worden, mits bronvermelding. Liselotte Loosveldt
WOORD VOORAF Na anderhalf jaar is het moment gekomen om de laatste hand te leggen aan deze masterproef. Van deze gelegenheid wil ik dan ook gebruik maken om een aantal mensen te bedanken. In de eerste plaats wil ik mijn promotor, Prof. dr. ir. Birger Raa bedanken voor de goede begeleiding en het waardevolle advies die me steeds weer op het goede pad zetten. Daarnaast ben ik ook alle medewerkers van de afdeling ‘Recylage en Baanvervoer’ van ArcelorMittal Gent zeer dankbaar. Zij stonden ten allen tijde klaar om mijn vragen te beantwoorden en te helpen bij de dataverzameling. Ook mijn familie verdient een woordje van dank. In het bijzonder wil ik mijn ouders bedanken voor hun steun en hulp bij het nalezen en ook mijn broer voor zijn helpende hand tijdens het programmeren. Tenslotte wil ik ook mijn vrienden bedanken voor de nuttige tips en het delen van hun ervaringen met de masterproef. Liselotte Loosveldt, mei 2009
I
INHOUDSOPGAVE 1
INLEIDING .............................................................................................................................. 1
2
HET VEHICLE ROUTING PROBLEM ........................................................................................... 3
2.1
HET KLASSIEKE VRP EN BASISVARIANTEN .................................................................................................. 3
2.2
OPTIMALISATIETECHNIEKEN .................................................................................................................... 5
2.2.1
Heuristieken ................................................................................................................................. 6
2.2.2
Metaheuristieken ....................................................................................................................... 10
2.3
HET ROLLON - ROLLOFF VEHICLE ROUTING PROBLEM ............................................................................... 12
2.3.1
Het RRVRP door Bodin et al. (2000) ........................................................................................... 13
2.3.2
Vergelijking met andere werken ................................................................................................ 15
3
CASE ARCELORMITTAL GENT ................................................................................................ 16
3.1
BEDRIJFSVOORSTELLING ....................................................................................................................... 16
3.1.1
Kort overzicht ............................................................................................................................. 16
3.1.2
De afdeling ‘Recyclage en Baanvervoer’ (RBV) .......................................................................... 18
3.2
HET BENNEWAGENTRANSPORT: AS-IS ................................................................................................... 19
3.3
PROBLEEMSTELLING EN OPLOSSINGSMETHODIEK ...................................................................................... 20
3.4
DATAVERZAMELING ............................................................................................................................. 22
3.5
DEEL 1: ROUTEPLANNING..................................................................................................................... 23
3.5.1
Verklaring begrippen .................................................................................................................. 24
3.5.2
Mathematisch model ................................................................................................................. 25
3.5.3
Heuristische Benadering ............................................................................................................ 29 3.5.3.1
Constructie van de initiële oplossing: ‘cheapest insertion’ heuristiek ............................ 30
3.5.3.2
‘Improvement’ heuristiek: swap ..................................................................................... 32
3.5.3.3
‘Improvement’ heuristiek: relocate ................................................................................ 33
3.5.3.4
Variable Neighborhood Search (VNS)............................................................................. 34
3.5.4
Implementatie ............................................................................................................................ 35
3.5.5
Resultaten .................................................................................................................................. 36 3.5.5.1
Output routeplanning en vergelijking met de realiteit ................................................... 37
3.5.5.2 Scenario-analyse: Performantie van de routeplanning bij een hogere frequentie van de aanvragen ........................................................................................................................ 40
II
3.6
DEEL 2: LOCATIE NIEUWE WEEGBRUG .................................................................................................... 41
3.6.1
Probleemstelling......................................................................................................................... 42
3.6.2
Oplossingsmethodiek ................................................................................................................. 43
3.6.3
Implementatie ............................................................................................................................ 45
3.6.4
Resultaten .................................................................................................................................. 46
3.7
CONCLUSIES EN VERDER ONDERZOEK ...................................................................................................... 48
4
ALGEMEEN BESLUIT.............................................................................................................. 50
5
LIJST VAN GERAADPLEEGDE WERKEN .................................................................................... VI
6
BIJLAGEN ............................................................................................................................ VIII
6.1
BIJLAGE A – ORGANOGRAM ARCELORMITTAL GENT................................................................................ VIII
6.2
BIJLAGE B – SITUERING VAN DE WEEGBRUGGEN OP HET GRONDPLAN ........................................................... IX
6.3
BIJLAGE C – OVERZICHT BINNENGEKOMEN AANVRAGEN PER SHIFT ................................................................ X
6.4
BIJLAGE D – OVERZICHT RITTEN PER CHAUFFEUR PER SHIFT ......................................................................... XI
6.5
BIJLAGE E – BESCHRIJVING VAN DE DATABASE “INVENTARIS_BENNES_THESIS”.............................................. XII
III
LIJST VAN FIGUREN Figuur 2-1: De basisvarianten van het VRP en hun relaties ......................................................................... 5 Figuur 2-2: Savings heuristic. ........................................................................................................................ 7 Figuur 2-3: Nearest insertion heuristiek. ..................................................................................................... 7 Figuur 2-4: ‘2-opt’ methode. ........................................................................................................................ 8 Figuur 2-5: ‘Or-opt’ methode. ...................................................................................................................... 8 Figuur 2-6: ‘String relocation’. ...................................................................................................................... 9 Figuur 2-7: ‘String exchange’. ....................................................................................................................... 9 Figuur 2-8: Local Search en Guided Local Search ....................................................................................... 11 Figuur 2-9: De vier trip types van Bodin et al. ............................................................................................ 14 Figuur 3-1: Grondplan ArcelorMittal Gent ................................................................................................. 18 Figuur 3-2: Bennewagen ............................................................................................................................ 19 Figuur 3-3: Tabellen en relaties van database “Inventaris_bennes_thesis” .............................................. 23 Figuur 3-4: Schematische voorstelling van een trip ................................................................................... 24 Figuur 3-5: Schematische voorstelling van een oplossing van de routeplanning met drie routes ............ 25 Figuur 3-6: Class diagram van de routeplanning ........................................................................................ 35 Figuur 3-7: Situering van het overgrote deel van de oorsprongen en bestemmingen op het grondplan van ArcelorMittal Gent ............................................................................................................................... 42 Figuur 3-8: Class diagram van het project ‘Nieuwe weegbrug’ ................................................................. 46 Figuur 3-9: Resultaten van het programma, getest op de referentieperiode april 2008 .......................... 47
IV
LIJST VAN TABELLEN Tabel 3-1: Gemiddelde duur van de basiselementen van de servicetijd ................................................... 28 Tabel 3-2: Output van de automatische routeplanning ............................................................................. 38 Tabel 3-3: Vergelijking automatische en manuele planning voor shift 1 ................................................... 40 Tabel 3-4: Output van de automatische routeplanning bij hogere frequentie van de trips ...................... 41
V
1 INLEIDING De staalsector, en in het bijzonder een geïntegreerd staalbedrijf zoals ArcelorMittal Gent, steunt op tal van verschillende activiteiten. Deze activiteiten moeten dagelijks op elkaar afgestemd worden om de productie van staal zo efficiënt mogelijk te laten verlopen. In de loop der jaren werden voor de meeste afdelingen binnen ArcelorMittal Gent beslissingsondersteunende instrumenten ontwikkeld in het kader van efficiëntieverhoging en kostenreductie. Doch een aantal processen, voornamelijk behorend tot de randactiviteiten van de productie, zijn nog steeds voor verbetering vatbaar. Deze masterproef zal één van deze activiteiten, namelijk het bennewagentransport, van naderbij bekijken. Het
doel van deze masterproef is
tweevoudig. Enerzijds
zal geprobeerd worden een
beslissingsondersteunend instrument te ontwikkelen om de logistieke processen van het bennewagentransport te optimaliseren. De bennewagens worden ingezet om op verschillende plaatsen op het bedrijfsterrein afvalmateriaal op te halen. Om de kosten te minimaliseren is het cruciaal de ritten van deze bennewagens efficiënt te plannen. Dit planningsprobleem is een reële toepassing van het Vehicle Routing Problem (VRP). Het VRP werd reeds door vele operationeel onderzoekers grondig bestudeerd en beschreven. Het tweede doel van de masterproef is dan ook een studie te maken van de belangrijkste werken inzake het VRP en zijn meer complexe varianten. Een aantal belangrijke beperkingen moeten in acht worden genomen. Ten eerste is het onmogelijk om een volledige beschrijving te geven van alle varianten van het VRP en de talrijke oplossingsmethoden ervoor. De literatuurstudie beperkt zich tot een overzicht van de varianten en heuristieken die het meest van toepassing zijn op het planningsprobleem in ArcelorMittal Gent. Ten tweede zou het een leugen zijn te beweren dat het ontwikkelde model de werkelijkheid perfect reflecteert. Een aantal vereenvoudigingen zijn onvermijdelijk. Onverwachte gebeurtenissen die in realiteit vaak voorkomen, zoals files of defecte wagens, alsook het real-time karakter van de planning van het bennewagentransport zijn elementen die het modelleren bemoeilijken. Vooraleer de masterproef aangevat wordt, is een opmerking in verband met het taalaspect noodzakelijk. Daar het VRP hoofdzakelijk in het Engels bestudeerd wordt, is het niet altijd mogelijk om bepaalde begrippen naar het Nederlands te vertalen. Deze begrippen zullen daarom in hun oorspronkelijke taal gebruikt worden. De masterproef is als volgt opgebouwd. In hoofdstuk 2 wordt de bestaande literatuur van het VRP bestudeerd, alsook de belangrijkste heuristieken en metaheuristieken. Daarna wordt in hoofdstuk 3 de case over het bennewagentransport in ArcelorMittal Gent aangevat. Na een korte voorstelling van het bedrijf en de huidige organisatie van het bennewagentransport, wordt het onderzoeksprobleem 1
geformuleerd. De oplossing van de case bestaat vervolgens uit twee delen. Allereerst wordt een programma ontwikkeld om de planning van het bennewagentransport op automatische wijze te laten verlopen. In tweede instantie wordt op basis van dit beslissingsondersteunend instrument nagegaan of het mogelijk is een efficiëntieverhoging te realiseren door middel van een wijziging in de infrastructuur.
2
2 HET VEHICLE ROUTING PROBLEM Het Vehicle Routing Problem (VRP) werd in 1959 geïntroduceerd door Dantzig en Ramser in het werk ‘The
truck
dispatching
problem’.
De
auteurs
beschreven
als
eerste
een mathematisch
programmeringsprobleem voor de levering van brandstof aan tankstations en gebruikten daarvoor een algoritmische benadering. Vandaag behoort het VRP tot de meest bestudeerde problemen in het domein van het operationeel onderzoek. Dit enerzijds omwille van zijn complexiteit en anderzijds door zijn brede toepasbaarheid. Het VRP wordt immers in zeer uiteenlopende aspecten van het dagelijkse leven gebruikt: afvalophaling, distributie van goederen, transport van gehandicapte personen, routeplanning van schoolbussen, enz.. Volgens Toth en Vigo (2002) zorgt het gebruik van gecomputeriseerde procedures in de distributie van goederen voor substantiële besparingen (van 5% tot 20%) in de globale transportkosten. Aangezien de transportkosten een aanzienlijk deel van de totale kost van een product vertegenwoordigen, hebben deze besparingen een significante invloed op ons economisch systeem, hetgeen duidt op de belangrijke rol van de studie van het VRP. Het VRP is een lineair programmeringsprobleem en is van combinatorische aard. Deze combinatorisch complexe problemen worden ook NP-hard genoemd. De inspanning nodig om NP-harde problemen op te lossen stijgt exponentieel met de grootte van het probleem. Dit heeft tot gevolg dat het quasi onmogelijk is om dé exacte oplossing te bekomen. Enkel voor kleinschalige problemen kan in een aanvaardbare tijdsspanne een optimale oplossing gevonden worden. In plaats daarvan streven operationeel onderzoekers naar het bereiken van de best mogelijke oplossing met behulp van heuristische procedures. Er zijn reeds verschillende optimalisatietechnieken, zowel exact als heuristisch, voorhanden om het VRP op te lossen, maar vooraleer overgegaan wordt tot een bespreking van deze technieken, is het nuttig het VRP en zijn varianten even kort voor te stellen.
2.1 HET KLASSIEKE VRP EN BASISVARIANTEN Het klassieke VRP, ook het Capacitated VRP (CVRP) genoemd, bestaat uit het bepalen van een set van routes voor een vloot van voertuigen zodat aan alle eisen van een vooropgesteld aantal klanten wordt voldaan en dit met minimale kosten. Elke route wordt uitgevoerd door één enkel voertuig. Het aantal beschikbare voertuigen kan gegeven zijn of gebruikt worden als beslissingsvariabele. Een aantal beperkingen moet daarbij gerespecteerd worden:
3
•
Elke route begint en eindigt in een centraal depot,
•
elke klant moet exact één keer bediend worden door exact één voertuig,
•
de totale vraag van de klanten op een route mag de capaciteit van het voertuig niet overschrijden,
•
de totale duur van een route mag een bepaalde limiet niet overschrijden (dit komt in de meeste gevallen overeen met de duur van de shift).
Deze lijst van beperkingen is in geen geval exhaustief. Er kunnen steeds bijkomende beperkingen geformuleerd worden, zoals bijvoorbeeld het opleggen van de volgorde waarin klanten bediend moeten worden. Deze bijkomende beperkingen liggen aan de basis van de verschillende varianten op het klassieke VRP. Het hoofddoel van het VRP is gericht op het minimaliseren van de totale kosten. Vaak komt dit neer op het minimaliseren van de transportkosten, bepaald door de totale afgelegde afstand en de vaste kosten voor het gebruik van de voertuigen. In bepaalde problemen worden echter ook nog andere objectieven vooropgesteld, zoals het minimaliseren van het aantal voertuigen die nodig zijn om de klanten te bedienen of het minimaliseren van de ‘penalty’ kosten die voortvloeien uit de bediening. ‘Penalty’ kosten kunnen bijvoorbeeld toegekend worden omwille van vertraagde bediening, overuren, enz.. Een laatste vaak voorkomend doel is het balanceren van de verschillende routes. Hiervoor kunnen een aantal criteria vooropgesteld worden zoals de reistijd of de lading van de voertuigen. Een VRP wordt geformuleerd aan de hand van een graaf G = (V,A). V = {0,…,n} stelt daarbij de vertex set voor en A = {(i,j): i,j V, i ≠ j} de arc set. Vertices i = 1,…,n komen overeen met de klanten en vertex 0 stelt het depot voor. Naargelang het een symmetrisch of asymmetrisch VRP betreft, wordt respectievelijk een niet-gerichte of gerichte graaf gebruikt. In een niet-gerichte graaf wordt in plaats van de arc set A een edge set E gebruikt voor de verbindingen tussen de vertices. Aan elke arc of edge (i,j) wordt een niet-negatieve kost cij toegekend. Deze kost vertegenwoordigt de reiskost nodig om een voertuig van vertex i naar vertex j te verplaatsen en is over het algemeen evenredig met de lengte van (i,j). Als G een niet-gerichte graaf is, is de kostenmatrix c, en dus ook de afstandsmatrix, symmetrisch. Er geldt dus dat cij = cji voor elke (i,j) E. Zoals reeds vermeld bestaan er verschillende varianten op het klassieke VRP, en dit naargelang de beperkingen die opgelegd worden. Zo spreekt men van een Distance-Constrained VRP (DCVRP) als de lengte van de routes een bepaalde limiet niet mag overschrijden. Het VRP with Time Windows (VRPTW) ontstaat als de klanten binnen een bepaalde periode van de dag, het time window, bediend moeten worden. Het VRP with Pickup and Delivery (VRPPD) wordt gekenmerkt door een aantal pickup en 4
delivery points. Voertuigen vervoeren mensen of goederen van de pickup points naar de delivery points en moeten dus een bepaalde volgorde respecteren. Een delivery point kan nooit bediend worden vóór het bijhorende pickup point. De routes bestaan bijgevolg uit een aaneenschakeling van pickup en delivery points. In het VRP with backhauls (VRPB) worden de klanten in twee subgroepen opgedeeld. De eerste groep bevat de ‘linehaul’-klanten waaraan een bepaalde hoeveelheid van een product moet worden geleverd. De tweede groep bestaat uit de ‘backhaul’-klanten waarbij een hoeveelheid van een product moet opgehaald worden. Er wordt opgelegd dat de ‘backhaul’-klanten pas bediend kunnen worden na alle ‘linehaul’-klanten. Deze basisvarianten kunnen nog verder gecombineerd worden zodat er in werkelijkheid een veel groter aantal verschillende Vehicle Routing Problems bestaat dan theoretisch beschreven. Zo kunnen het VRPB en het VRPTW gecombineerd worden tot het VRPBTW, dit is het VRP with Backhauls and Time Windows. Onderstaande figuur geeft een overzicht van de basisvarianten van het VRP en de relaties tussen deze varianten. CVRP
Route length
Backhauling
DCVRP
Mixed Service Time Windows
VRPB
VRPTW
VRPBTW
VRPPD
VRPPDTW
Figuur 2-1: De basisvarianten van het VRP en hun relaties (Toth & Vigo, 2002, p. 6)
Voor een uitgebreide bespreking van de basisvarianten van het VRP, zie Toth & Vigo (2002). Het VRP with Time Windows wordt ook in het werk van Bräysy (2001) uitgebreid behandeld.
2.2 OPTIMALISATIETECHNIEKEN Het VRP is een hard combinatorisch optimalisatieprobleem en dat maakt het zeer moeilijk het optimum te bereiken. Exacte algoritmen, zoals het ‘branch-and-bound’ of het ‘branch-and-cut’ algoritme, slagen er niet in problemen met meer dan 50 klanten consistent op te lossen (Cordeau, Gendreau, Laporte, Potvin & Semet, 2002). Omwille van de beperkte mogelijkheden van deze exacte algoritmen, worden in praktijk
meestal
heuristieken
en
metaheuristieken
gebruikt.
Echter,
ook
bij
deze
optimalisatietechnieken moet een trade-off gemaakt worden tussen een kwalitatief hoogstaande
5
oplossing en een snelle berekening. Hoe hoger de vereiste graad van optimaliteit, hoe meer rekentijd het algoritme vraagt van de computer. Zowel de klassieke heuristieken als de metaheuristieken zoeken naar de optimale oplossing door stap voor stap de oplossingsruimte te verkennen. Er wordt vertrokken van een initiële oplossing en door middel van kleine aanpassingen wordt gepoogd een betere oplossing te vinden. Dit proces wordt steeds herhaald tot een bepaald stopcriterium bereikt is. De belangrijkste heuristieken en metaheuristieken worden hierna kort voorgesteld. Voor een gedetailleerde bespreking, zie Toth & Vigo (2002).
2.2.1 HEURISTIEKEN Het overgrote deel van de klassieke heuristieken werd ontwikkeld tussen 1960 en 1990 (Toth & Vigo, 2002). De meeste constructie- en ‘improvement’ heuristieken die vandaag in gebruik zijn behoren tot deze klasse. Klassieke heuristieken voeren een relatief beperkte verkenning van de oplossingenruimte uit. Daardoor worden ze gekenmerkt door eenvoud en snelheid. Ze slagen erin zeer lage rekentijden te bereiken. Een andere reden voor de populariteit van de heuristieken is de brede toepasbaarheid in reële situaties. Ze kunnen makkelijk aangepast worden om een diversiteit aan beperkingen in rekening te brengen. De kwaliteit van de oplossingen is over het algemeen goed, maar toch minder accuraat dan de oplossingen bekomen door de metaheuristieken. De klassieke heuristieken worden over het algemeen ingedeeld in drie categorieën: de constructieve heuristieken, de ‘two-phase’ heuristieken en de ‘improvement’ heuristieken. De constructieve heuristieken bouwen stap voor stap een toelaatbare oplossing op, maar bevatten niet noodzakelijk een ‘improvement’ fase. Een voorbeeld van deze categorie is de bekende ‘Clarke and Wright savings heuristic’. Het basisprincipe waarop deze heuristiek steunt is het laten samensmelten van bestaande routes op basis van een ‘savings’ criterium. In eerste instantie worden n routes geconstrueerd voor de klanten i = 1,…,n. Elke route bevat bijgevolg slechts één klant. Daarna worden bij elke iteratie twee routes samengesmolten tot één nieuwe route, waarbij telkens gekozen wordt voor die routes die de grootste besparing of ‘saving’ opleveren. De ‘saving’ sij bij het samenvoegen van de routes (0,i,0) en (0,j,0) wordt als volgt berekend: ij i0 0j ij
6
Onderstaande figuur geeft één iteratie weer van de ‘savings’ heuristiek. De routes in de linkse figuur worden samengevoegd door klant j na klant i toe te voegen in één route. De bijhorende saving wordt onmiddellijk duidelijk uit de verandering van de pijlen.
j
i
j
i
Figuur 2-2: Savings heuristic. (Bräysy, 2001, p.24)
Er bestaan twee versies van deze heuristiek, een parallelle en een sequentiële. De parallelle versie levert duidelijk betere resultaten op (Toth & Vigo, 2002, p.111). Een tweede klasse van constructieve heuristieken zijn de ‘insertion’ heuristieken. Deze zijn gebaseerd op een ander basisprincipe. In plaats van verschillende routes te combineren wordt in dit soort heuristieken stap voor stap een vertex toegevoegd aan een route op basis van een ‘insertion’ kost. Naargelang het criterium dat gebruikt wordt om een vertex toe te voegen spreekt men van een ‘nearest insertion’, ‘farthest insertion’ of ‘cheapest insertion’. Net als bij de ‘savings’ heuristiek bestaat hiervan een sequentiële en parallelle variant. In de parallelle variant worden verschillende routes tegelijk geïnitialiseerd. De parallelle ‘insertion’ overtreft de sequentiële variant in kwaliteit en rekentijd maar stelt bijkomende moeilijkheden op vlak van het bepalen van het aantal initiële routes en de set van ‘root’ klanten. In onderstaande figuur wordt een ‘sequential nearest insertion’ voorgesteld. In de linkse figuur bevinden enkel klant i en klant j zich reeds op de route. In elke fase wordt die klant toegevoegd die de waarde van de doelfunctie het minst doet stijgen. In dit voorbeeld wordt klant a geselecteerd omdat deze de totale afstand van de huidige route minder doet stijgen dan klant b of c. c i
c j
b
i
j
b a
a
Figuur 2-3: Nearest insertion heuristiek. Klant a wordt toegevoegd aan de bestaande route met klanten i en j. (Bräysy, 2001, p.27)
7
De ‘two-phase’ heuristieken kunnen opgedeeld wordt in 2 grote subcategorieën, maar zoals de naam al aangeeft wordt het probleem telkens opgedeeld in twee componenten. De eerste subcategorie wordt de ‘cluster-first, route-second’ categorie genoemd. Hierbij worden de klanten in een eerste fase gebundeld in clusters en voor elk van deze clusters wordt in de tweede fase een route gepland. Verschillende bekende algoritmes, zoals het ‘sweep algorithm’ en het ‘Fisher and Jaikumar algorithm’ behoren tot deze categorie. Ook de omgekeerde situatie is mogelijk waarbij eerst een grote TSP (Traveling Salesman Problem) route geconstrueerd wordt, die daarna in een tweede fase opgedeeld wordt in kleinere, toelaatbare routes. Deze subcategorie is gekend als de ‘route-first, cluster-second’ methode. De ‘improvement’ heuristieken of ‘local search’ heuristieken tenslotte proberen een toelaatbare initiële oplossing te verbeteren door het verplaatsen van vertices of strings van vertices binnenin of tussen routes. Men spreekt van een ‘first improvement’ of ‘first accept’ procedure wanneer de eerst voorkomende verbetering geïmplementeerd wordt en van een ‘best improvement’ of ‘best accept’ procedure als de volledige ‘neighborhood’ geëxploreerd wordt om de beste verbetering te identificeren. De ‘neighborhood’ van een oplossing bestaat uit de set van alle oplossingen die door middel van een aantal elementaire bewegingen kunnen bereikt worden vanuit de huidige oplossing. Verbeteringen binnenin één route zijn in de meeste gevallen gebaseerd op het ‘λ-opt’ of ‘Or-opt’ principe. De ‘λ-opt’ methode verwijdert λ edges uit de route en herverbindt deze edges op alle mogelijke manieren. De ‘Oropt’ methode verwijdert een string van vertices en voegt die terug toe op een andere locatie. Onderstaande figuren tonen duidelijk het verschil tussen de λ-opt en Or-opt methodes. i
j
j+1
i+1
i
j
j+1
i+1
Figuur 2-4: ‘2-opt’ methode. De edges (i, i+1) en (j, j+1) zijn vervangen door de edges (i,j) en (i+1, j+1). (Bräysy, 2001, p.31)
i-1
i+1
i+1
i
i
j+1
i-1
j
j+1
j
Figuur 2-5: ‘Or-opt’ methode. Klant i krijgt een nieuwe locatie tussen klant j en j+1. (Bräysy, 2001, p.34)
8
Behalve veranderingen binnenin één route kunnen (strings van) vertices ook verplaatst worden tussen twee routes. Verschillende auteurs hebben in de loop der jaren onderzoek gedaan naar deze ‘between route exchanges’. Van Breedam bijvoorbeeld beschrijft vier improvement procedures: ‘string cross’, ‘string exchange’, ‘string relocation’ en ‘string mix’. In onderstaande figuren worden respectievelijk de ‘string relocation’ en ‘string exchange’ voorgesteld. i-1
i+1
i-1
i+1
i
i
j
j+1
j
j+1
Figuur 2-6: ‘String relocation’. In dit geval bestaat de string slechts uit één vertex i. Vertex i krijgt een nieuwe locatie in een andere route. (Bräysy, 2001, p.36)
i-1
i+1
i+1
i-1
j
j
i j-1
i j+1
j-1
j+1
Figuur 2-7: ‘String exchange’. Ook hier bestaat de string uit één vertex. Vertices i en j worden verwisseld van plaats. (Bräysy, 2001, p.37)
Een typische ‘local search’ procedure, gebaseerd op ‘best improvement’, kan als volgt beschreven worden (Bräysy, 2001, p.31): Stap 1: Start met een initiële oplossing en beschouw deze als de huidige oplossing. Stap 2: Genereer alle oplossingen in de ‘neighborhood’ van de huidige oplossing door het uitvoeren van één of meerdere elementaire bewegingen (‘λ-opt’, ‘Or-opt’, ‘string exchange’, ‘string relocation’, enz.). Stap 3: Selecteer de beste oplossing uit de ‘neighborhood’ en definieer deze oplossing als de nieuwe huidige oplossing. Stap 4: Ga terug naar stap 2.
9
In werkelijkheid is het onderscheid tussen constructie- en ‘improvement’ heuristieken echter niet altijd duidelijk omdat de meeste constructieheuristieken één of meerdere ‘improvement’ stappen incorporeren.
2.2.2 METAHEURISTIEKEN De relatief lage kwaliteit van de oplossingen bekomen door middel van klassieke heuristieken, vormde de aanzet tot het zoeken naar alternatieven. Vanaf de jaren 1990 is het meeste onderzoek dan ook gericht op de zogenaamde metaheuristieken (Toth & Vigo, 2002). Metaheuristieken slagen erin oplossingen van hoge kwaliteit te behalen door een diepere verkenning van de oplossingenruimte. In tegenstelling tot de klassieke ‘improvement’ heuristieken stoppen de metaheuristieken niet op een lokaal optimum. Ze benaderen door middel van een gerichte zoekstrategie, namelijk door het tijdelijk aanvaarden van oplossingen die de waarde van de doelfunctie verslechteren, het globale optimum. Metaheuristieken worden dan ook vaak ‘global improvement’ heuristieken genoemd. Het grootste nadeel van metaheuristieken is dat de hogere kwaliteit gepaard gaat met een stijgende rekentijd, dit omdat er geen stopconditie gedefinieerd wordt. Hoe langer de rekentijd, hoe hoger de waarschijnlijkheid dat de oplossing dicht bij het globale optimum ligt. Metaheuristieken kunnen onderverdeeld worden in twee klassen: ‘local search’ metaheuristieken en ‘population search’ metaheuristieken. De eerste klasse is gebaseerd op het principe van ‘local search’, waarbij door een intensieve verkenning van de ‘neighborhood’ van de huidige oplossing een nieuwe oplossing wordt gezocht. Deze metaheuristieken zijn in principe geavanceerde versies van de klassieke ‘improvement’ heuristieken. Simulated Annealing, Deterministic Annealing en Tabu Search zijn drie metaheuristieken die tot deze klasse behoren. De tweede klasse is gebaseerd op het principe van ‘population search’. Deze metaheuristieken vertrekken van meerdere oplossingen tegelijk, in tegenstelling tot de ‘local search’ metaheuristieken die op elk moment slechts één oplossing beschouwen. Bij ‘population search’ wordt een verzameling van goede ‘parent’ oplossingen bijgehouden en gecombineerd zodat nog betere nakomelingen geproduceerd worden. De populatie van oplossingen evolueert dus van de ene generatie naar de volgende volgens principes die in de natuur teruggevonden worden, namelijk selectie, combinatie (of crossover) en mutatie. Genetic Algorithms, Ant Systems en Neural Networks behoren tot deze klasse. Omdat Tabu Search van alle metaheuristische optimalisatietechnieken de beste resultaten levert voor het VRP (Toth & Vigo, 2002; Cordeau et al., 2002), wordt deze metaheuristiek hierna iets meer in detail behandeld. 10
Tabu Search is, zoals reeds vermeld, een metaheuristische ‘local search’ strategie, geïntroduceerd door Fred Glover in 1986. Tijdens elke iteratie wordt de beste oplossing uit de ‘neighborhood’ van de huidige oplossing geselecteerd als de nieuwe huidige oplossing. Oplossingen die de waarde van de doelfunctie doen stijgen worden daarbij ook toegelaten, dit om te ontsnappen aan een lokaal optimum. Typisch aan Tabu Search is het gebruik van speciale geheugenstructuren om de ‘neighborhood’ van de huidige oplossing aan te passen en het zoeken te organiseren. Oplossingen die recent bezocht werden, worden in een korte termijn geheugen, de ‘tabu list’, opgeslagen en worden taboe. Dit wil zeggen dat deze oplossingen gedurende een bepaald aantal iteraties (overeenstemmend met de lengte van de ‘tabu list’) niet als huidige oplossing kunnen gekozen worden. Bij elke iteratie wordt er een nieuwe oplossing opgeslagen in de ‘tabu list’ en komt een andere oplossing terug vrij. Als een oplossing echter aantrekkelijk genoeg is, dan mag de tabu regel overschreden worden. Dit is bijvoorbeeld het geval als de oplossing tot een betere waarde van de doelfunctie zou leiden dan tot nu toe bekomen werd (Glover, Kelly, & Laguna, 1995). In de loop der jaren werden verschillende algoritmes ontwikkeld die gebaseerd zijn op Tabu Search, zoals bijvoorbeeld de Taburoute van Gendreau et al., het Taillard tabu search algoritme en het granulaire tabu search algoritme van Toth en Vigo (Cordeau et al., 2002). Een andere vermeldenswaardige metaheuristiek, is de Guided Local Search (GLS), beschreven door Kilby, Prosser en Shaw in 1999. Deze metaheuristiek is een variant op de gewone ‘local search’ metaheuristieken. De GLS verhoogt de doelfunctie met een ‘penalty’ kost gebaseerd op hoe dicht de nieuwe oplossing zich bij een reeds bezocht lokaal minimum bevindt, waardoor diversificatie bevorderd wordt. Hier worden dus niet enkel oplossingen aanvaard die de doelfunctie verslechteren, zoals het geval is bij de gewone ‘local search’ metaheuristieken, maar daar bovenop wordt ook de doelfunctie zelf aangepast om lokale minima uit te sluiten. In onderstaande figuur wordt het verschil tussen een gewone ‘local search’ metaheuristiek (Tabu Search) en ‘guided local search’ visueel voorgesteld. Local Search
Guided Local Search
f(x)
f(x)
Lokaal minimum
Globaal minimum
x
Lokaal minimum
Globaal minimum
x
Figuur 2-8: Local Search en Guided Local Search
11
De klassieke ‘local search’ metaheuristiek gaat van de ene oplossing x naar de volgende door het toepassen van een set van elementaire bewegingen. De sprongen die in het groen aangeduid zijn leiden naar een lokaal minimum, bij elke sprong wordt de waarde van de doelfunctie kleiner. Eens het lokaal minimum bereikt is worden ook sprongen toegelaten (in rood aangeduid) die de waarde van de doelfunctie opnieuw verhogen, dit om aan het lokaal minimum te ontsnappen. Aangezien alle recent bezochte oplossingen taboe verklaard worden, zal het zoekalgoritme niet terugkeren naar vorige betere oplossingen. De Guided Local Search daarentegen maakt het ontsnappen aan locale minima op een andere manier mogelijk. Hier worden lokale minima ‘verwijderd’ door het aanpassen van de doelfunctie. In bovenstaande figuur wordt het lokaal minimum teniet gedaan in drie iteraties (groen – oranje – rood).
2.3 HET ROLLON - ROLLOFF VEHICLE ROUTING PROBLEM Het VRP dat het dichtst aanleunt bij het planningsprobleem in ArcelorMittal Gent, is het Rollon – Rolloff Vehicle Routing Problem (RRVRP). Het onderzoek naar het RRVRP is nog volop in ontwikkeling, tot nu toe zijn er vijf werken beschikbaar waarin algoritmes voor het RRVRP voorgesteld worden. Het probleem werd geïntroduceerd door Cristallo G. in zijn masterproef “Optimisation de Tournées de Véhicules de Transport Container” in 1994 en wordt verder ook beschreven in De Meulemeester, Laporte, Louveaux en Semet (1997); Bodin, Mingozzi, Baldacci en Ball (2000) en Archetti en Speranza (2004). Enkel in Bodin et al. (2000) wordt het probleem expliciet onder de naam RRVRP behandeld. De andere auteurs spreken eerder over het ‘1-skip collection problem’. Het RRVRP is één van de drie basis afvalophalingsproblemen. In het Residential Pickup Problem wordt een dagelijkse route uitgestippeld voor voertuigen die huisvuil ophalen aan woningen. Deze voertuigen maken tussen 600 en 1500 stops per dag en rijden gemiddeld niet meer dan drie keer naar een afvallocatie. In het Container Pickup Problem wordt de inhoud van containers opgehaald die verspreid staan op bepaalde locaties, zoals ziekenhuizen, scholen, restaurants, enz.. Een dagelijkse route bestaat uit het ophalen van een 100 tot 200-tal containers en ook hier wordt de afvallocatie niet meer dan drie keer per dag bezocht. Het RRVRP tenslotte is gericht op het plannen van routes voor het ophalen van grote trailers (of skips) die zich bijvoorbeeld op bouwwerven of aan shopping centers bevinden. Een voertuig kan maar één trailer tegelijk vervoeren en moet dus onmiddellijk na het ophalen van de trailer de inhoud gaan legen op de afvallocatie. De weg die door een voertuig afgelegd moet worden voor het bedienen van een trailer, wordt een ‘trip’ genoemd. De dagelijkse route van een voertuig is dus een opeenvolging van trips, waarbij elke trip toegewijd is aan de bediening van één bepaalde klant. In het algemeen worden niet meer dan 15 trips per dag uitgevoerd, dit door de grote afstanden die moeten
12
overbrugd worden in vergelijking met de eerste twee afvalophalingsproblemen. Het RRVRP kan gezien worden als een variant op het Pickup and Delivery VRP, met het verschil dat voertuigen in het RRVRP slechts één trailer tegelijk kunnen vervoeren, en dat dus de pickup en delivery van één klant steeds na elkaar dient te gebeuren. In deel 2.3.1 wordt een gedetailleerde beschrijving gegeven van het RRVRP door Bodin et al. (2000). Daarna worden in deel 2.3.2 de belangrijkste verschillen met de skip collection problems van Archetti en Speranza (2004) en De Meulemeester (1997) aangehaald.
2.3.1 HET RRVRP DOOR BODIN ET AL. (2000) In het RRVRP beschreven door Bodin et al. (2000) is er één centraal depot van waaruit de voertuigen hun route starten en één afvallocatie waar de trailers gedumpt worden. Het doel is tweevoudig. Enerzijds moet de operationele kost, namelijk de totale reistijd van de voertuigen nodig om alle trips te kunnen bedienen, geminimaliseerd worden. Anderzijds vormt het minimaliseren van het aantal ingezette voertuigen of de kapitaalkost een tweede doel. De lengte van de routes mag een bepaalde limiet L (bvb. de duur van een shift) niet overschrijden. De capaciteit van de voertuigen wordt niet gespecificeerd aangezien er slechts één trailer tegelijk kan vervoerd worden. De auteurs categoriseren alle trips in vier klassen. Trips van het type 1 worden voorgesteld aan de hand van de bewegingsvector Mi = (si, vd, ei), waarbij vd gelijk is aan de afvallocatie, si vormt de startlocatie bij de klant en ei de eindlocatie (waarbij voor de meeste trips geldt dat si = ei). Een type 1 trip start dus bij de klant, waar een volle trailer op het voertuig geladen wordt. Daarna rijdt het voertuig naar de afvallocatie waar de trailer geleegd wordt en rijdt vandaar naar de eindlocatie om de trailer terug af te zetten. Trips van het type 2 worden voorgesteld door de bewegingsvector Mi = (vd, vi, vd) waarbij vi een locatie bij een klant voorstelt. Tijdens een type 2 trip haalt het voertuig een lege trailer op aan de afvallocatie, rijdt ermee naar de klant, zet de lege trailer af bij de klant en neemt een volle trailer van de klant terug mee naar de afvallocatie. Trips van het type 3 worden getypeerd door de bewegingsvector Mi = (vd , ei). In deze situatie wordt een lege trailer van de afvallocatie naar de klant vervoerd. In het algemeen komt dit overeen met de initiële levering van een trailer aan de klant. Trips van het type 4 tenslotte worden voorgesteld met de bewegingsvector Mi = (si, vd). Hier vertrekt het voertuig met een volle trailer bij de klant en rijdt naar de afvallocatie waar de trailer gelost wordt. Deze situatie komt in het algemeen overeen met de teruggave van een trailer omdat de klant er geen behoefte meer aan heeft. Onderstaande figuur geeft een visuele voorstelling weer van de 4 types trips.
13
T1
T3
T2
T4
Afvallocatie vd Depot
vo
Startlocatie voor Type 1 en Type 4 trips Tussenlocatie voor Type 2 trips en eindlocatie voor Type 3 trips Vervoer van een volle trailer Vervoer van een lege trailer Figuur 2-9: De vier trip types van Bodin et al. (2000, p. 273)
Elke trip i wordt gekenmerkt door een bepaalde bedieningstijd di, nodig om alle activiteiten gerelateerd aan de trip uit te voeren. De bedieningstijd wordt verondersteld gekend te zijn, zo gaat men bijvoorbeeld vooraf na hoelang het duurt om een trailer vast te hechten of te legen. Elk type trip heeft een specifieke formule om de bedieningstijd te berekenen. Naast de bedieningstijd van de trips zelf, is er ook een tijdsverloop tussen het bedienen van twee opeenvolgende trips. De tijd nodig om van de eindlocatie van trip i naar de beginlocatie van trip j te rijden, wordt de reistijd tij genoemd. Deze reistijden worden bijgehouden in een reistijd-matrix. Het doel om de operationele kost te minimaliseren komt eigenlijk neer op het minimaliseren van deze reistijden tussen twee opeenvolgende trips, in het artikel wordt dit de ‘deadhead time’ genoemd. De wiskundige formulering van het RRVRP verschilt enigszins van het klassieke VRP omdat het geen typisch ‘routing’ probleem is. Door de introductie van het type 2 trips, wordt het RRVRP een combinatie van een ‘routing’ en een ‘bin packing’ probleem. Hierdoor wordt het moeilijk om een efficiënt algoritme te ontwikkelen. Vier heuristische algoritmes werden door de auteurs beschreven en getest op 20 problemen om de efficiëntie te vergelijken. De Partial Enumeration Methode en het Decompositie Algoritme geven de beste oplossingen. Voor een gedetailleerde beschrijving van de vier heuristieken, zie Bodin et al. (2000).
14
2.3.2 VERGELIJKING MET ANDERE WERKEN Het 1-skip collection problem van Archetti en Speranza (2004) is ruimer dan Bodin et al. (2000) in die zin dat er Time Windows worden toegekend aan de klanten en dat de klanten worden opgedeeld in twee groepen: klanten die met een vaste frequentie bediend moeten worden en klanten die bediend moeten worden als hun trailer vol is. De klanten met een vaste frequentie krijgen daarbij een hogere prioriteit dan de andere klanten. Verder bevat het probleem meerdere afvallocaties en wordt er een beperking opgelegd ten aanzien van het soort trailer. Een voertuig mag enkel trailers van eenzelfde type ophalen gedurende een volledige route. Er worden ook penalty costs toegekend per dag dat een klant te laat bediend worden (soft constraint) en de vertraging mag een vooraf gespecificeerd aantal dagen niet overschrijden (hard constraint). Hier wordt met 3 types trips gewerkt zoals ze gedefinieerd werden in Bodin et al. (2000). Trips van het type 2 ontbreken. De auteurs presenteren een nieuw heuristisch algoritme om het RRVRP op te lossen, het SMART-COLL algoritme. Voor een volledige beschrijving van het algoritme wordt verwezen naar het artikel. Net als bij Archetti en Speranza (2004) zijn er in De Meulemeester et al. (1997) meerdere afvallocaties. Ook hier worden de klanten opgedeeld in twee groepen: de ‘domestic’ klanten waarvan de trailer geleegd moet worden op een afvallocatie nabij het depot en de ‘industrial’ klanten waarvan de trailer op verschillende andere afvallocaties kan geleegd worden. In dit probleem worden enkel trips van het type 3 en 4 in beschouwing genomen. Twee heuristieken worden beschreven: het parallelle Clarke and Wright savings algoritme en een tweede heuristiek gebaseerd op de oplossing van een Transportation Problem. Op basis van een ontoelaatbare oplossing van het Transportation Problem wordt een optimale oplossing berekend aan de hand van een enumeratief algoritme.
15
3 CASE ARCELORMITTAL GENT Op basis van de studie van het Vehicle Routing Problem en de bijhorende heuristische optimalisatietechnieken, moet het mogelijk zijn een oplossing uit te werken voor een reëel planningsprobleem in ArcelorMittal Gent. Het doel van de case is tweevoudig. Ten eerste zal worden aangetoond dat de planning van het bennewagentransport ook op automatische wijze kan gebeuren, met eventueel betere resultaten tot gevolg. Ten tweede wordt nagegaan of het mogelijk is een kostenbesparing te realiseren door een reorganisatie van de infrastructuur, namelijk door het plaatsen van een nieuwe weegbrug. Het verloop van de case is als volgt georganiseerd. In deel 3.1 wordt ArcelorMittal Gent voorgesteld. Eerst wordt een kort overzicht gegeven aan de hand van enkele cijfers en daarna worden de activiteiten van de afdeling RBV iets uitgebreider toegelicht. De huidige organisatie van het bennewagentransport wordt behandeld in deel 3.2. In deel 3.3 wordt de probleemstelling en oplossingsmethodiek geformuleerd. Vervolgens wordt in deel 3.4 de dataverzameling besproken. In deel 3.5 wordt de ontwikkeling van de automatische planning van het bennewagentransport besproken en deel 3.6 onderzoekt verder wat het effect is van een wijziging in de infrastructuur. Tenslotte worden in deel 3.7 de belangrijkste conclusies samengevat.
3.1 BEDRIJFSVOORSTELLING 3.1.1 KORT OVERZICHT ArcelorMittal Gent, nog steeds beter gekend als Sidmar, maakt deel uit van de groep ArcelorMittal. Deze staalgroep ontstond in 2006 uit de fusie tussen Arcelor en Mittal Steel. ArcelorMittal is de grootste staalproducent ter wereld en produceert in normale omstandigheden1 ongeveer 110 miljoen ton ruwstaal per jaar. Hiervan wordt ongeveer vijf miljoen ton in Gent geproduceerd. Wereldwijd is ArcelorMittal gevestigd in meer dan 20 landen en stelt zo’n 320.000 werknemers tewerk. In 2008 werd een omzet gerealiseerd van 125 miljard euro. ArcelorMittal Gent produceert uitsluitend vlakke staalproducten. Er worden drie verschillende soorten eindproducten afgeleverd: warmgewalste, koudgewalste en beklede producten. Het is een maritiem staalbedrijf, gelegen aan de rechteroever van het kanaal Gent-Terneuzen. Via dit kanaal heeft het een vlotte verbinding met de Noordzee en dankzij deze maritieme ligging is ArcelorMittal Gent bereikbaar voor grote ertsschepen met een laadvermogen van ongeveer 65.000 ton en een diepgang tot 12,50 m.
1
Alle cijfers zijn gebaseerd op de periode vóór de huidige economische crisis. 16
ArcelorMittal Gent beschikt over een bedrijfsterrein van ongeveer 800 ha. Slechts een deel hiervan wordt vandaag gebruikt voor de huisvesting van de verschillende productieafdelingen. Dankzij deze grote oppervlakte kan het hele productieproces op een optimale manier worden geïntegreerd. ArcelorMittal Gent beschikt over alle productie-eenheden om vertrekkende van de grondstoffen het eindproduct te produceren. Dit heeft als bijkomend voordeel dat overbodige transporten en tussenopslag worden vermeden. Deze ver doorgedreven integratie heeft echter ook een nadeel, namelijk complexiteit. Een zeer groot aantal verschillende activiteiten moet dagelijks op elkaar worden afgestemd. In het kader van bedrijfsbezoeken en in informatiebrochures worden meestal alleen de hoofdactiviteiten van ArcelorMittal belicht. Deze zijn immers verantwoordelijk voor het grootste deel van de toegevoegde waarde van het eindproduct. Zo zullen velen onder ons al gehoord hebben van de cokesfabriek, de sinterfabrieken, de hoogovens, de staalfabriek, de continugieterijen, de warmwalserij en de koudwalserijen. Om een bedrijf als ArcelorMittal Gent efficiënt te laten werken is er echter meer nodig dan dit. Nevenactiviteiten zoals onderhoud, intern transport, recyclage, enz. zijn minstens even belangrijk. Deze processen leveren geen echte toegevoegde waarde aan het eindproduct, maar vertegenwoordigen wel een aanzienlijk deel van de kosten. Het is dan ook uiterst belangrijk deze activiteiten zo efficiënt mogelijk te organiseren. In deze case wordt één van deze nevenactiviteiten van naderbij bekeken, namelijk het bennewagentransport. De verantwoordelijkheid over het bennewagentransport behoort tot de afdeling ‘Recyclage en Baanvervoer’ (RBV). Op onderstaande figuur is met een gele stip aangeduid waar deze afdeling zich bevindt op het bedrijfsterrein. Het rood gearceerde gebied stelt het deel van het bedrijfsterrein voor dat onder de verantwoordelijkheid van de afdeling RBV valt.
17
2
Figuur 3-1: Grondplan ArcelorMittal Gent
3.1.2 DE AFDELING ‘RECYCLAGE EN BAANVERVOER’ (RBV) Zoals op het organogram van ArcelorMittal Gent in bijlage A aangeduid,, is de afdeling RBV een onderdeel van de afdeling “Grondstoffen, Grondstoffen, Haven, Haven Vervoer en Recuperatie” (GHV), (GHV) de logistieke tak van het bedrijf. RBV draagt de verantwoordelijkheid over een gebied gebie van 90 hectare. Dit gebied, op bovenstaande figuur uur in het rood gearceerd, doet voornamelijk dienst als opslagplaats voor recuperatiestoffen. RBV was vroeger een onderaanneming van het toenmalige Sidmar, Beremet genaamd. De afdeling is op het gebied van automatisering automatisering minder ver gevorderd in vergelijking met andere afdelingen. Op basis van deze scriptie wil het management van RBV dan ook het startschot geven van een evolutie naar meer gecomputeriseerde procedures. Deze evolutie moet, samen met een nauwere samenwerking ing met de andere afdelingen binnen ArcelorMittal Gent, in de toekomst leiden tot een verhoogde efficiëntie. De activiteitenportefeuille van RBV bestaat uit een en aantal uiteenlopende activiteiten, zoals onder andere de “drop ball”-operaties3, de stofbestrijding,, het verhuren van machines aan andere afdelingen en het bennewagentransport. Het is deze ze laatste activiteit die in deel 3.2 in detail zal behandeld worden.
2
Bron: Informatiebrochure ‘Zo maakt ArcelorMittal Gent staal’staal’ maart 2008
3
“Drop ball”-operaties operaties verbrijzelen materiaal, zoals slakken of ruwijzer uit de ruwijzerputten, ruwijzerputten, door een zware bol van op grote hoogte op dit materiaal te laten vallen. 18
3.2 HET BENNEWAGENTRANSPORT: AS-IS Het bennewagentransport of containertransport is één van de belangrijkste activiteiten van RBV en vormt in feite het interne afvaltransport van ArcelorMittal Gent. De voertuigen die het afvaltransport verzorgen worden ‘bennewagens’ genoemd en de ‘bennes’ zijn de containers waarin het afval wordt verzameld. Op onderstaande foto wordt een bennewagen afgebeeld die een benne aan het opladen is. De afdeling RBV beschikt over zes dergelijke containertrucks. De bennewagens hebben een laadcapaciteit van 20 ton (inclusief container) en rijden aan een snelheid van maximaal 50 km/u. Dit is de snelheidslimiet op het ganse bedrijfsterrein. De bennewagens kunnen bennes vervoeren met een inhoud van 4 m³ t.e.m. 15 m³. Het vervoerde materiaal wordt ingedeeld in drie categorieën: ten eerste is er het productieschroot afkomstig van de productielijnen (zoals bijvoorbeeld afgesneden randen, afgekeurde stukken platen, enz.), ten tweede het afbraakschroot afkomstig van afbraakwerken en als laatste worden ook recuperatiestoffen vervoerd. Over het gehele bedrijfsterrein staan ongeveer 240 bennes verspreid, zowel buiten als binnenin de gebouwen.
4
Figuur 3-2: Bennewagen
Momenteel gebeuren alle aanvragen tot afvalophaling telefonisch. De afdelingen delen via de telefoon mee aan de dispatcher van RBV welke benne geleegd moet worden. Deze laatste verwerkt de aanvragen op basis van ervaring en intuïtie. Hij weet waar en in welke toestand, geladen of ongeladen, de verschillende bennewagens zich bevinden en geeft de nieuwe opdracht aan de chauffeur die zich volgens hem het dichtst bij de volle benne bevindt. De plaats waar de volle benne opgehaald moet worden, wordt de ‘oorsprong’ genoemd en de plaats waar de benne geleegd moet worden, is de ‘bestemming’. Wanneer hun opdracht voltooid is, laten de chauffeurs dit via radiocontact aan de dispatcher weten. De dispatcher deelt hen vervolgens een nieuwe opdracht mee. Elke chauffeur doet 4
Foto ter beschikking gesteld door de afdeling RBV – ArcelorMittal Gent 19
bijgevolg een aaneenschakeling van oorsprongen en bestemmingen aan doorheen de shift. Er moet ook rekening gehouden worden met het feit dat de bennewagen bij elke omhaling moet gewogen worden op één van de twee weegbruggen aanwezig op het bedrijfsterrein. Tussen elke oorsprong en bestemming is er dus een bezoek aan de weegbrug. Schematisch kan de route van een bennewagen als volgt voorgesteld worden, waarbij O = oorsprong en B = bestemming: Depot – O1 – weegbrug – B1 – O1 – O2 – weegbrug – B2 – O2 – O3 – weegbrug – B3 – O3 – … – Depot. Aanvraag 1
Aanvraag 2
Aanvraag 3
De twee weegbruggen waar de bennewagens gebruik kunnen van maken, zijn aangeduid op het grondplan in bijlage B. De ‘weegbrug RBV’ bevindt zich vlakbij de kantoorgebouwen van de afdeling RBV en is 24 uur op 24 beschikbaar. De ‘baanweegbrug’ daarentegen staat in eerste instantie ten dienste van het externe transport en kan enkel tijdens de nacht, i.e. tussen 18u en 6u, ingezet worden voor het bennewagentransport. Tot op vandaag wordt geen gebruik gemaakt van een GPS-systeem. Elke chauffeur kiest zelf de route die hij het kortst acht. Het aantal ingezette voertuigen verschilt naargelang de shift. Op weekdagen worden in de voormiddag- en namiddag-shift meestal drie tot vier voertuigen ingezet en in de nacht-shift twee tot drie, alsook tijdens het weekend. De voormiddag-shift loopt van 6u tot 14u, de namiddag-shift van 14u tot 22u en de nacht-shift van 22 u tot 6u. Het aantal ritten per chauffeur per shift schommelt tussen 10 tot 14 en de gemiddelde uitvoeringstijd per aanvraag bedraagt 30 minuten. In 2008 bedroeg het totaal aantal ritten 33.776.
3.3 PROBLEEMSTELLING EN OPLOSSINGSMETHODIEK Na een korte beschrijving van de organisatie van het bennewagentransport, wordt in dit deel het onderzoeksprobleem aangekaart. Een aantal jaar geleden begon ArcelorMittal Gent met een ‘pull’-organisatie van de productie. In plaats van volledig op stock te produceren, wordt vandaag voor een deel geproduceerd op basis van het aantal binnengekomen orders. Deze verandering in de productie had een groot effect op de randprocessen en uit zich ook in de organisatie van het bennewagentransport. Vroeger kon de dispatcher op basis van de productieplanning van de verschillende afdelingen een dag op voorhand een inschatting maken van het aantal aanvragen dat elke afdeling zou plaatsen. Aan de hand hiervan werd bepaald hoeveel bennewagens nodig zouden zijn voor de uitvoering van de geplande aanvragen en werden de bennewagens toegewezen aan de bediening van één bepaalde afdeling. Door de grotere schommelingen in de productie vandaag, is het niet meer mogelijk om een bennewagen volledig aan 20
één afdeling toe te wijzen. Hierdoor rijden de bennewagens van de ene afdeling naar de andere met een grotere afgelegde afstand tot gevolg. De verhoogde complexiteit van het plannen van de aanvragen doet vragen rijzen over de huidige aanpak. Het wordt immers steeds moeilijker voor de dispatcher om op basis van zijn ervaring een optimale planning, i.e. een planning die totale afgelegde afstand van alle bennewagens minimaliseert, op te stellen. Het bennewagentransport is verantwoordelijk voor een aanzienlijk deel van de bedrijfskosten en men is van mening dat deze activiteit veel efficiënter georganiseerd kan worden. Het belang van efficiënte bedrijfsprocessen wordt ook met de huidige economische crisis steeds groter. In een eerste stap zal daarom onderzocht worden wat het effect is van het automatiseren van de planning van het bennewagentransport op de efficiëntie en de productiviteit. Om de efficiëntie te verhogen is het noodzakelijk dat de automatisatie een planning genereert die de totale afgelegde afstand verlaagt in vergelijking met de manuele planning. Dit kan gerealiseerd worden door een combinatie van een juiste verdeling van de aanvragen en een selectie van de kortste route voor elke aanvraag. Indien de afgelegde afstand daalt, zal logischerwijs het verbruik van de bennewagens verminderen, hetgeen resulteert in een verhoogde efficiëntie. Daarenboven zal een verlaagde afgelegde afstand leiden tot een kortere uitvoeringstijd per aanvraag, waardoor de bennewagens meer aanvragen per shift kunnen uitvoeren. Kort samengevat omvat het doel van het eerste deel van de case het realiseren van een efficiëntieverhoging door het automatiseren van de planning van het bennewagentransport. Het achterliggende doel is het verhogen van het aantal ritten per bennewagen, zodat minder bennewagens dienen ingezet te worden voor hetzelfde aantal aanvragen. Vertrekkende van deze automatische planning gaat het tweede deel van de case na of verdere efficiëntieverhogingen mogelijk zijn door het aanbrengen van wijzigingen in de infrastructuur. De specifieke onderzoeksvraag hier is of het bouwen van een nieuwe weegbrug de totale afgelegde afstand nog verder kan reduceren, en wat de ideale locatie is van deze weegbrug. Vooraleer de ontwikkeling van de oplossing voor deze problemen aangevat wordt, komt eerst een overzicht van de verzamelde data aan bod.
21
3.4 DATAVERZAMELING De eerste stap in het oplossen van de case betreft het verzamelen van de nodige data. Daarvoor is een stage gedurende twee weken in de afdeling RBV nuttig gebleken. Gesprekken met de dispatcher gaven mij inzicht in het planningsproces en de manier waarop prioriteiten toegekend worden aan de verschillende aanvragen. Vereenvoudigd kan men stellen dat er drie verschillende prioriteiten toegekend worden – 1, 2 en 3 – waarbij 3 de hoogste prioriteit vertegenwoordigt. Door het combineren van verschillende documenten over de locatie van de bennes en de bijhorende oorsprongen was het mogelijk één coherente database samen te stellen waarin eenduidig vermeld wordt tot welke oorsprong een bepaalde benne behoort. In dezelfde database werd ook een tabel opgenomen met alle mogelijke aanvragen, i.e. alle mogelijke combinaties van oorsprongen en bestemmingen. Voor elk van deze oorsprongen en bestemmingen werden de coördinaten opgezocht op het elektronisch grondplan van ArcelorMittal Gent, ter beschikking gesteld door de afdeling ‘Bedrijfsinfrastructuur/GIS’. Deze coördinaten zijn noodzakelijk om tijdens de automatische routeplanning het kortste pad te berekenen van elke aanvraag. Samen met een ervaren chauffeur was het mogelijk alle wegen die toegankelijk zijn voor de bennewagens aan te duiden op de plannen van ArcelorMittal Gent. Deze verbindingswegen zijn een belangrijke input voor de berekening van het kortste pad tussen twee locaties. Iets moeilijker was het om informatie te verzamelen over de uitgevoerde aanvragen. Deze aanvragen dienen als input voor de automatische planning, om de resultaten ervan te kunnen vergelijken met de werkelijkheid. Als referentieperiode werd gekozen voor de maand april 2008. Zo worden alle effecten van de huidige economische crisis vermeden. Het probleem hier was dat RBV geen digitale gegevens bijhoudt van het tijdstip waarop de aanvragen geplaatst worden door de afdelingen. Door het combineren van twee documenten, toegevoegd in bijlage C en D, was het mogelijk alle informatie met betrekking tot de aanvragen te verzamelen. Bijlage C bevat het aanvraagtijdstip (onder de kolom “Uur 1e oproep”), het tijdstip van de weging en het nummer van de bennewagen die de aanvraag uitvoerde (onder de kolom “Uitgevoerd door/met”). Aan de hand van het tijdstip van de weging en het nummer van de bennewagen kon daarna in het document in bijlage D de oorsprong (O), bestemming (B) en de benne (Bak) van elke aanvraag opgezocht worden. Daar deze informatie record per record aan de database diende toegevoegd te worden, werd geopteerd om gegevens van slechts drie dagen te testen. Met drie shiften per dag betekent dit dat de automatische planning van negen verschillende shiften zal vergeleken worden met de werkelijke planning. 22
Om de lezer inzicht te geven in de structuur van de Access-database Access database wordt hieronder het relatieschema afgebeeld. Dit relatieschema geeft de verschillende tabellen en hun relaties weer (tabellen waartussen geen relaties mogelijk gelijk zijn worden hier niet weergegeven). weergegeven) De volledige database is terug te vinden op bijgevoegde CD-rom. rom. Een gedetailleerde uitleg bij de verschillende tabellen is voorzien in bijlage E. E
Figuur 3-3:: Tabellen Tabel en relaties van an database “Inventaris_bennes_thesis”
3.5 DEEL 1: ROUTEPLANNING In dit deel van de case wordt het eerste onderzoeksprobleem onder handen genomen. Er zal met andere woorden een programma ontwikkeld worden dat op automatische wijze de aanvragen toewijst aan de beschikbare bennewagens, en daarmee samenhangend ook bepaalt hoeveel bennewagens er nodig zijn om alle aanvragen tegemoet te komen. Dit programma wordt in het vervolg aangeduid met de naam ‘routeplanning’. In essentie komt de routeplanning neer op het correct toewijzen van de bennewagens be aan de verschillende aanvragen. Dit is duidelijk een toepassing op het Vehicle ehicle Routing Problem, zij het op een speciale variant hiervan. Bij elke oproep moet immers een bennewagen gekozen worden, zodat de
23
totale afgelegde afstand minimaal is, rekening houdend met andere beperkingen zoals de prioriteit van de aanvraag. De indeling van het eerste deel van de case volgt het volgende traject. In deel 3.5.1 wordt een korte beschrijving gegeven van de gebruikte begrippen. Deel 3.5.2 behandelt de ontwikkeling van het algoritme dat aan de basis ligt van de routeplanning. Na het opstellen van het mathematisch model wordt in deel 3.5.3 de heuristische oplossingsmethode beschreven. Deel 3.5.4 geeft een kort overzicht van de implementatie van de heuristieken in Java om tenslotte in deel 3.5.5 te eindigen met een bespreking van de belangrijkste resultaten.
3.5.1 VERKLARING BEGRIPPEN In deel 2 (supra, p. 3) werd het VRP gedefinieerd als “het bepalen van een set van routes voor een vloot van voertuigen zodat aan alle eisen van een vooropgesteld aantal klanten wordt voldaan en dit met minimale kosten”. De klanten komen in dit specifiek probleem overeen met de aanvragen die geplaatst worden door de verschillende afdelingen. De bediening van een klant houdt met andere woorden in dat de gehele aanvraag uitgevoerd wordt. In de verdere beschrijving wordt een aanvraag voor de duidelijkheid vervangen door een ‘trip’. Een trip wordt gekenmerkt door een oorsprong (O) en een bestemming (B). Zoals hierboven reeds aangehaald werd, is de oorsprong de plaats waar de volle benne afgehaald moet worden en de bestemming de locatie waar de benne geleegd moet worden. Vóór het legen moet de benne gewogen worden op de weegbrug, dit wil zeggen dat er tussen oorsprong en bestemming een bezoek aan de weegbrug plaatsvindt. Na het legen op de bestemming wordt de lege benne teruggebracht naar de oorsprong en vandaar vertrekt de bennewagen naar de oorsprong van een volgende trip. Een trip kan als volgt voorgesteld worden:
Oorsprong
Weegbrug
Bestemming
Figuur 3-4: Schematische voorstelling van een trip
24
De route, uitgevoerd door een bennewagen tijdens het verloop van de shift, is een opeenvolging van trips. In het geval er drie bennewagens actief zijn, ziet een mogelijke oplossing er als volgt uit:
2
Depot
3
1
Figuur 3-5: Schematische voorstelling van een oplossing van de routeplanning met drie routes
Zoals aangeduid op bovenstaande figuur, vertrekken de bennewagens bij het begin van de shift allen uit het depot en keren pas terug aan het einde van de shift of vroeger als er geen trips meer uitgevoerd moeten worden. Elke stip stelt de oorsprong van een trip voor. Het rode kader rond de laatste stip van route 3 is een verwijzing naar Figuur 3-4. Het duidt aan dat in iedere stip van Figuur 3-5 een trip uit Figuur 3-4 verscholen zit. De pijlen in Figuur 3-5 zijn een maat voor de afstand tussen de trips en de pijlen in Figuur 3-4 stellen de afstand binnen de trip voor.
3.5.2 MATHEMATISCH MODEL Na een grondige studie van de literatuur werd snel duidelijk dat het planningsprobleem in ArcelorMittal Gent veel gelijkenissen vertoont met het Rollon-Rollof VRP (RRVRP). Net zoals in het RRVRP kan een bennewagen slechts één benne tegelijk vervoeren en is een route samengesteld uit een opeenvolging van trips. In deel 2.3.1 wordt vermeld dat het RRVRP een combinatie is van een routing en een bin packing probleem, waardoor het moeilijk is een efficiënt algoritme te ontwikkelen. Het planningsprobleem van deze case bevat echter geen trips van het type 2 (supra p. 13), zodat het toch tot een gewoon routing probleem herleid kan worden. De mathematische formulering hierna beschreven verschilt enigszins van het traditionele VRP-model in die zin dat niet de afstand geminimaliseerd wordt, maar wel het tijdsverloop. De vaak gebruikte term
∑ ∑ ij ij ontbreekt hier dus in de doelfunctie. De afstand dient echter wel als basis om het 25
tijdsverloop te berekenen, waardoor het minimaliseren van dit tijdsverloop uiteindelijk ook zal resulteren in een minimale afgelegde afstand. Op basis van Bodin et al. (2000) en Toth en Vigo (2002) en rekening houdend met de specifieke kenmerken van het planningsprobleem kan het model als volgend binair programmeringsprobleem geformuleerd worden:
V
verzameling van alle trips i, j (=vertices )
A
verzameling van alle verbindingen (i,j) (=arcs)
Beslissingsvariabelen: xijk
1 als trip j na trip i uitgevoerd wordt door wagen k, anders 0.
Parameters: tij
de reistijd, i.e. de benodigde tijd om zich van trip i naar trip j te verplaatsen.
si
de bedieningstijd, i.e. de benodigde tijd om trip i uit te voeren.
Ti
het aanvraagtijdstip, i.e. het tijdstip waarop trip i aangevraagd werd.
wi
het tijdstip waarop trip i uitgevoerd wordt.
pi
de prioriteit van trip i.
K
het aantal beschikbare wagens.
R
de vaste kost per ingezette wagen.
S
een penalty kost per seconde.
26
Minimaliseer:
ijk j i i ij i i i
"
oik
Onder voorwaarde: "
ijk 1
$% &\(0)
"
1
oik * +
2
"
"
ijk jik 2 "
$% &\(0)
"
3
oik iok
4
ijk i i ij j * 0
$/ +,
i i 4 0
$1 &\(0)
ijk (0,1)
$/ +,
$ 1, % 2
5 6
$ 1, % 2
7
Vergelijking (5) wordt met behulp van de binaire beperking (7) en de ‘Big M’-methode herleid tot volgende lineaire beperking: i i ij j * 1 ijk 71%
$/ +,
$ 1, % 2
5. 9
Het doel van dit probleem is het minimaliseren van de totale kost. De eerste twee delen van de doelfunctie stellen de operationele kost voor. De eerste term rekent een penalty kost S aan voor elke seconde dat een wagen moet wachten tussen de uitvoering van twee trips, i.e. de ‘stilstand’. De tweede term penaliseert het tijdsverschil tussen het aanvraagtijdstip van een trip en het tijdstip waarop de uitvoering aangevat wordt, rekening houdend met de prioriteit van de trip. Het derde deel van de doelfunctie stelt de vaste kost van de gebruikte bennewagens voor. Door deze vaste kost in rekening te brengen, wordt dus ook impliciet het aantal bennewagens geminimaliseerd. Beperking (1) zorgt ervoor dat elke trip j tot exact één route behoort, waarbij een route een aaneenschakeling van trips is, uitgevoerd door één bepaalde wagen k. Beperking (2) geeft aan dat niet
27
alle wagens actief moeten zijn gedurende een bepaalde shift. Beperking (3) garandeert dat er in elke vertex (trip) j exact 1 wagen aankomt en vertrekt. Beperking (4) zorgt ervoor dat het aantal wagens dat vertrekt uit het depot aan het begin van de shift gelijk is aan het aantal wagens dat er terug toekomt. Beperking (5) en (6) garanderen dat de oplossing klopt met betrekking tot het tijdsaspect en beperking (7) tenslotte legt op dat de beslissingsvariabelen binair moeten zijn. Er is geen beperking nodig voor de capaciteit van de wagens, aangezien slechts één benne tegelijk vervoerd kan worden. De bedieningstijd si in beperking (5) wordt berekend op basis van Bodin et al. (2000). In dit artikel veronderstellen de auteurs dat er vier verschillende soorten trips zijn (supra p.13). De trips in Arcelor Mittal Gent behoren allen tot het type 1. De bedieningstijd van een trip is samengesteld uit de tijd nodig op de benne op te laden op de oorsprong, de tijd nodig om van de oorsprong via de weegbrug naar de bestemming te rijden, de weegtijd, de tijd nodig om de inhoud van de benne te dumpen op de bestemming, de reistijd van de bestemming terug naar de oorsprong en de tijd nodig om de benne terug af te zetten op de oorsprong. In symbolen wordt dit: i a;i <;i, =i w u <=i, ;i d;i
$1 &\(0)
7
Waarbij: a;i
de tijd nodig om de benne vast te hechten en op te laden op de oorsprong.
<;i, =i
de tijd nodig om van de oorsprong, via de weegbrug, naar de bestemming te rijden.
w
de tijd nodig voor het wegen van de benne op de weegbrug.
u
de tijd nodig voor het dumpen van de inhoud van de benne op de bestemming.
<=i, ;i
de tijd nodig om van de bestemming naar de oorsprong te rijden.
d;i
de tijd nodig om de benne terug af te zetten op de oorsprong.
Uit tijdsmetingen blijkt dat volgende gemiddelden aanvaardbaar zijn (gebaseerd op een steekproef van tien verschillende trips): Aw Au
AaB
AdB
1’ 1’50” 6’30” 5’30”
Tabel 3-1: Gemiddelde duur van de basiselementen van de servicetijd
28
Vooraleer de bespreking van de heuristische oplossingsmethode aangevat wordt, is het noodzakelijk te vermelden dat een aantal vereenvoudigingen ingevoerd werden in vergelijking met de werkelijkheid. Ten eerste is het onmogelijk om onverwachte gebeurtenissen, die in realiteit vaak voorkomen, in rekening te brengen. Zo zal een wegversperring of een file ervoor zorgen dat de werkelijke uitvoering meer tijd in beslag neemt dan gepland in de routeplanning. Ten tweede volgt de uitvoering van het bennewagentransport in realiteit geen strak schema. De procedure, beschreven in deel 3.2, waarbij de afdelingen bellen naar de dispatcher om te melden dat een benne moet geleegd worden, is immers niet altijd geldig. Het komt vaak voor dat de chauffeur van een bennewagen tijdens zijn route een volle benne ziet staan zonder dat de verantwoordelijke afdeling dit meldde. De chauffeur geeft dit dan door aan de dispatcher en deze laatste neemt de opdracht op in de planning. In de routeplanning daarentegen wordt abstractie gemaakt van deze situaties. Er wordt bijgevolg verondersteld dat er steeds gebeld wordt. Ten derde is het zeer moeilijk om de ervaring van de dispatcher met betrekking tot de prioriteit van de trips te modelleren. Uit gesprekken met deze laatste kon ik een vereenvoudigd stelsel van prioriteiten (supra p.22) toekennen aan de verschillende oorsprongen, maar dit is niet voldoende om het reële beslissingsproces van de dispatcher exact te simuleren. Tenslotte dient vermeld te worden dat er geen rekening werd gehouden met de lunchpauze van 30 minuten die de chauffeurs gespreid over de hele shift kunnen opnemen. Daarnaast moet ook rekening gehouden worden met het real-time karakter van de planning van het bennewagentransport. Telkens er een nieuwe aanvraag geplaatst wordt, moet de planning van de daarvoor reeds geplande trips herzien worden. Als de nieuwe trip een hogere prioriteit heeft kan het immers voordeliger zijn om die eerst uit te voeren.
3.5.3 HEURISTISCHE BENADERING In dit onderdeel wordt de heuristische oplossingsmethode beschreven waarbij naar de best mogelijke oplossing van het mathematisch model gezocht wordt. Deze oplossing geeft voor één bepaalde shift weer welke trips door welke bennewagen dienen uitgevoerd te worden en in welke volgorde. In eerste instantie wordt in deel 3.5.3.1 de constructie van de initiële oplossing behandeld, om daarna in de drie volgende delen een overzicht te geven van de gebruikte ‘improvement’ heuristieken. Voor de eenvoud worden de trips in het vervolg voorgesteld door gehele getallen. Elk getal stelt dus één trip voor, waarvoor volgende data gegeven zijn: het aanvraagtijdstip, de prioriteit, de oorsprong en de bestemming. De oorsprong en de bestemming zijn twee knooppunten, gekenmerkt door een koppel coördinaten.
29
Als illustratie bij de behandeling van de constructie- en ‘improvement’ heuristieken wordt een eenvoudig voorbeeld uitgewerkt voor een shift met 8 trips en 3 beschikbare bennewagens. We veronderstellen hierbij dat het een voormiddag-shift betreft, beginnend om 6u en eindigend om 14u. De trips krijgen de cijfers 1 t.e.m. 8 toegewezen en het cijfer 0 verwijst zoals gewoonlijk naar het depot. De oplossingsvoorstelling, toegepast op dit voorbeeld, ziet er als volgt uit (de volgorde van de cijfers buiten beschouwing gelaten): Oplossing:
0
1
2
Lengte:
x
x
x
Kost:
x
x
x
Stilstand:
x
x
x
3
0
4
5
0
6
7
8
0
De oplossingsvoorstelling is samengesteld uit vier verschillende lijsten. De lijst ‘Oplossing’ geeft de volgorde van de trips in de drie routes weer, waarbij het begin en einde van de routes gekenmerkt wordt door een 0. Elke route start en eindigt immers in het depot. De lengte van de lijst is met andere woorden gelijk aan de som van het aantal trips en het aantal routes of wagens, plus één. In dit geval is dit gelijk aan 8+3+1=12. Bovenop de lijst ‘Oplossing’ bevat de oplossingsvoorstelling nog drie andere lijsten waarvan de lengte telkens gelijk is aan het aantal routes. Deze lijsten bevatten voor elke route respectievelijk de totale duur (in seconden), de kost en de totale stilstand (in seconden).
3.5.3.1 Constructie van de initiële oplossing: ‘cheapest insertion’ heuristiek Aan de hand van de sequentiële ‘cheapest insertion’ heuristiek (supra p.7) wordt in een eerste fase stap voor stap de initiële oplossing opgebouwd. Heel belangrijk bij het oplossen van dit probleem is dat de ‘real-time’ verwerking van de trips zo goed mogelijk nagebootst wordt. Daarom wordt er opgelegd dat een trip pas kan gepland worden na de beëindiging van de trips die reeds in uitvoering zijn. Het is immers onmogelijk om een trip in uitvoering af te breken. De pseudocode van de heuristiek ziet er als volgt uit: Stap 1: Vraag de te verwerken trips op en sorteer ze van klein naar groot op basis van het aanvraagtijdstip. Stap 2: Selecteer de eerste trip (i=0) uit de verzameling te verwerken trips en voeg die toe aan een willekeurige route k.
30
Stap 3: Veronderstel dat: K = het aantal bennewagens, i.e. het aantal routes, en n = het aantal trips, FOR elke nog te verwerken trip i: FOR alle bestaande routes k: Bereken de kost om trip i toe te voegen in de verschillende routes. Onthoud bij elke iteratie de huidige beste kost Ck* en de bijhorende positie van trip i. Als k < K, doe k+1 en bereken de kost om trip i toe te voegen in een lege route. Voeg i toe in de route en op de positie die de kleinste verhoging in kosten teweegbrengt. Verhoog de huidige kosten van de route met Ck*. Pas het tijdsverloop in de route aan. i = i + 1. Om de pseudocode te verduidelijken worden enkele iteraties toegepast op het voorbeeld. Onder de lijst ‘Oplossing’ wordt het aanvraagtijdstip van de trips ingevuld en boven de lijst komt het tijdstip waarop de trips afgewerkt zijn. Het tijdstip waarop de uitvoering van een trip aangevat wordt, is gelijk aan het tijdstip waarop de vorige trip afgewerkt werd of aan het aanvraagtijdstip van de trip, in het geval dat de trip pas aangevraagd werd na het tijdstip van afwerking van de vorige trip. Er wordt verondersteld dat de uitvoering van elke trip 30 minuten in beslag neemt. Merk op dat deze uitvoeringstijd niet gelijk is aan de bedieningstijd. De uitvoeringstijd omvat bovenop de bedieningstijd ook nog de tijd nodig om van de oorsprong van de vorige trip naar de oorsprong van de huidig trip te rijden. In de eerste stap is nog geen enkele trip toegewezen aan een route en bestaat de oplossing uit een reeks nullen. Stap 1:
0
0
0
0
0
0
0
0
0
0
0
0
Vervolgens wordt in de tweede stap de trip met het vroegste aanvraagtijdstip toegevoegd aan een willekeurige route. Het aanvraagtijdstip van het depot wordt gelijkgesteld aan het startuur van de shift, i.e. 6u, en het tijdstip van afwerking is gelijk aan het aanvraagtijdstip van de eerste trip, dus 6u30. De uitvoering van trip 1 start om 6u30 en is beëindigd om 7u. Na de toevoeging van trip 1 aan de ‘Oplossing’ worden ook de lijsten Lengte, Kost en Stilstand bijgewerkt. Stap 2:
6u30 7u
0
1
6u
6u30
0
0
0
0
0
0
0
0
0
0
Nadat de eerste trip aan een route is toegewezen, wordt deze procedure nu herhaald voor alle andere trips. Stel dat de tweede trip die moet toegevoegd worden een aanvraagtijdstip heeft van 6u50, dan zijn 31
de plaatsen waar deze trip kan toegevoegd worden hieronder in geel aangeduid. Trip 2 kan niet voor trip 1 ingevoegd worden aangezien om 6u30 reeds gestart werd met de uitvoering van trip 1 en trip 2 pas om 6u50 aangevraagd werd. Trip 2 kan daarentegen wel na trip 1 of in een andere (lege) route gepland worden. 6u30 7u
Stap 3:
0 6u
1
0
0
0
0
0
0
0
0
0
0
6u30
Trip 2 wordt ingevoegd op de plaats die de kosten het minst doet stijgen. In de veronderstelling dat het minder kost om trip 2 in een lege route toe te voegen, m.a.w. dat de opstartkost van een nieuwe route lager is dan de penalty kost die zou ontstaan als trip 2 na trip 1 toegevoegd wordt, ziet de oplossing er na deze iteratie als volgt uit: 6u30 7u
Stap 3:
0 6u
6u50 7u20
1
0
2
6u30
6u
6u50
0
0
0
0
0
0
0
0
Op dezelfde manier worden trips 3 t.e.m. 8 aan de routes toegewezen. Na de constructie van de initiële oplossing wordt een ‘local search’ toegepast om van de initiële oplossing naar het globaal minimum te proberen evolueren. De twee elementaire bewegingen die daarvoor gebruikt worden zijn de ‘swap’ en de ‘relocate’. Beide ‘improvement’ heuristieken zijn gebaseerd op het ‘best improvement’ principe (supra p.8). Dit houdt in dat alle mogelijke bewegingen uitgevoerd zullen worden waarna de beste beweging geselecteerd wordt.
3.5.3.2 ‘Improvement’ heuristiek: swap Het principe van deze heuristiek is heel éénvoudig. In elke iteratie worden er twee trips van plaats verwisseld. Dit kunnen zowel trips van éénzelfde route zijn of trips behorend tot een verschillende route, i.e. ‘within route’ en ‘between route’. De swap die de initiële kost het meest reduceert, wordt uitgevoerd en de initiële oplossing wordt overschreven met deze nieuwe oplossing. De pseudocode kan als volgt geformuleerd worden: Stap 1: Vertrek van de initiële oplossing of van een vorige verbeterde oplossing. Stap 2: FOR elke trip i: Verwissel i met elke trip j (≠i) uit dezelfde route en elke trip z uit de andere routes, indien dit toelaatbaar is op basis van het tijdsverloop. Herbereken het tijdsverloop en de bijhorende kost van alle routes na elke toelaatbare ‘swap’. 32
Voer de ‘swap’ uit die de grootste verbetering in de totale kost geeft.
Opnieuw wordt deze ‘improvement’-fase geïllustreerd aan de hand van het voorbeeld. Stel dat de volledige initiële oplossing er uit ziet als: 6u30
Stap 1:
7u
0 6u
1
7u40 8u10
3
4
6u30 7u10 7u30
6u50 7u20 8u20 8u50
0 6u
2
5
6u50 7u50
6 8u10
9u
9u30
10u
0
7
8
6u
9u
0
9u20
In dit geval is een swap tussen trip 2 en trip 3 toelaatbaar rekening houdend met het real-time karakter van de planning. Het aanvraagtijdstip van trip 2 is immers groter dan het aanvraagtijdstip van trip 1 en kleiner dan het aanvraagtijdstip van trip 4. Als de swap resulteert in een lagere waarde van de doelfunctie, dan wordt de swap uitgevoerd en worden de tijdstippen van afwerking herberekend. 6u30
Stap 2:
7u
0 6u
1
7u30
2
8u
4
6u30 6u50 7u30
7u10 7u40
0
3
6u 7u10
8u20
8u50
9u
9u30
10u
5
6
0
7
8
7u50
8u10
6u
9u
9u20
0
3.5.3.3 ‘Improvement’ heuristiek: relocate Deze heuristiek selecteert in elke iteratie een bepaalde trip en voegt die toe op een andere locatie, binnenin dezelfde route of in een andere route. De pseudocode van de heuristiek wordt gegeven door: Stap 1: Vertrek van de initiële oplossing of van een vorige verbeterde oplossing. Stap 2: FOR elke trip i: Voeg trip i toe op elke andere plaats binnenin dezelfde route en in alle andere routes, indien dit toelaatbaar is op basis van het tijdsverloop. Bereken het tijdsverloop en de bijhorende kost van alle routes. Voer de ‘relocate’ uit die de grootste verbetering in de totale kost geeft.
Vertrekkende van dezelfde initiële oplossing als in deel 3.5.3.2 is hieronder een mogelijke ‘relocate’beweging afgebeeld. 6u30
Stap 1:
0 6u
Stap 2:
7u
1
7u40 8u10
3
4
6u30 7u10 7u30
6u30
7u
7u30
8u
0
1
2
3
6u50 7u20 8u20 8u50
0 6u
2
6u50 7u50
8u30 7u50
4
6u 6u30 6u50 7u10 7u30
5
0
6 8u10
9u
9u30
10u
0
7
8
6u
9u
9u20
8u20
8u50
9u
9u30
10u
5
6
0
7
8
9u
9u20
6u 7u50
8u10
6u
0
0
33
3.5.3.4 Variable Neighborhood Search (VNS) Om betere waarden van de doelfunctie te bereiken dan mogelijk is met één enkele ‘swap’ of ‘relocate’ heuristiek, wordt een eenvoudige VNS toegepast. Het principe waarop VNS gebaseerd is, is dat de ‘neighborhood’ (supra p.8) van een oplossing bij elke iteratie verandert. Als bijvoorbeeld de ‘swap’ heuristiek uitgevoerd wordt op de initiële oplossing, dan bestaat de ‘neighborhood’ tijdens deze heuristiek uit alle oplossingen die door het toepassen van een ‘swap’ beweging op de initiële oplossing bereikt kunnen worden. De oplossing uit de ‘neighborhood’ die de beste verbetering levert, wordt dan geselecteerd als zijnde de nieuwe huidige oplossing. De ‘swap’ heuristiek kan nu echter nog eens uitgevoerd worden op de nieuwe huidige oplossing, waarbij er een nieuwe ‘neighborhood’ ontstaat die eventueel een betere oplossing bevat. Deze procedure wordt herhaald zolang er verbeteringen gevonden worden. Er worden zeven verschillende ‘improvement’ heuristieken behandeld, die later in deel 3.5.5 getest worden op de datasets. •
Optie 1 – Swap: Herhaal de ‘swap’ heuristiek tot er geen verbetering meer mogelijk is.
•
Optie 2 – Relocate: Herhaal de ‘relocate’ heuristiek tot er geen verbetering meer mogelijk is.
•
Optie 3 – Swap, Relocate: Herhaal de ‘swap’ heuristiek tot er geen verbetering meer mogelijk is. Voer daarna de ‘relocate’ heuristiek uit op de laatste verbetering en herhaal deze tot er geen verbetering meer mogelijk is.
•
Optie 4 – Relocate, Swap: Herhaal de ‘relocate’ heuristiek tot er geen verbetering meer mogelijk is. Voer daarna de ‘swap’ heuristiek uit op de laatste verbetering en herhaal deze tot er geen verbetering meer mogelijk is.
•
Optie 5 – Relocate met Swap: Voer de ‘relocate’ heuristiek één maal uit en pas daarna op deze eerste verbetering de ‘swap’ heuristiek toe. Herhaal deze laatste tot er geen verbetering meer mogelijk is en voer dan opnieuw de ‘relocate’ heuristiek uit op de laatste verbetering. Herhaal deze procedure tot de ‘relocate’ heuristiek geen verbeteringen meer kan vinden.
•
Optie 6 – Swap met Relocate: Voer de ‘swap’ heuristiek één maal uit en pas daarna op deze eerste verbetering de ‘relocate’ heuristiek toe. Herhaal deze laatste tot er geen verbetering meer mogelijk is en voer dan opnieuw de ‘swap’ heuristiek uit op de laatste verbetering. Herhaal deze procedure tot de ‘swap’ heuristiek geen verbeteringen meer kan vinden.
34
•
Optie 7 – Relocate of Swap: Voer bij elke iteratie zowel de ‘swap’ als de ‘relocate’heuristiek uit en herhaal dit tot geen van beide nog een verbetering kan vinden.
3.5.4 IMPLEMENTATIE Na een beschrijving van de oplossingsmethodiek wordt in dit deel kort de concrete implementatie van de routeplanning in Java behandeld. Om de structuur van het Java project te verduidelijken wordt in onderstaande figuur het class diagram voorgesteld. Data AfstandsMatrix - dijkstraMatrix: double[][] - afstandsMatrix: double[][] - dbConnection: Connection + AfstandsMatrix() + loadDriver(): void + connectDatabase(): void + constructDijkstraMatrix(): void + closeConnection(): void + constructAfstandsMatrix(): void + printDijkstraMatrix(): void + printAfstandsMatrix(): void
<<use>>
- aantalAanvragen: int - AanvraagLijst: Aanvraag[ ] + aantalActieveWagens: int - aantalWagensBeschikbaar: int=6 - Penalty: double - dbConnection: Connection - startuur: int - shiftnummer: int - loadDriver(): void - connectDatabase(): void - closeConnection(): void + Data(matrix) + printAanvraagLijst():void
<<use>> Dijkstra
+ dijkstra(): double[]
Knooppunt - Xcoord: double - Ycoord: double + Knooppunt() + Knooppunt(Xcoord, Ycoord) + Afstand(): double
Aanvraag - Depot: Knooppunt - Oorsprong: Knooppunt - Bestemming: Knooppunt - Prioriteit: int - TijdAanvraag:long - bennenummer: String - bestemming: String - ServiceTijd: double - indexOorsprong: int - indexBestemming: int - GemiddeldeSnelheid: double - matrix: AfstandsMatrix - afdrukTijd: long - afdrukAfgewerkteTijd: double - tijdstipAfgewerkt: double
Solution - data: Data - matrix: Afstandsmatrix - Dummy: Aanvraag - Oplossing: Aanvraag[] - Lengte: double[] - Kost: double[] - Stilstand: double[] - startStilstand: double[] - totaleKost: double - totaleLengte: double - totaleStilstand: double - opstartkost: double + Solution() + Solution(data, matrix) + sorteerBubble(): void + routeConstruction(): void + relocateSolution(): void + swapSolution(): void + printOplossing(): void
+ Aanvraag(matrix) + Aanvraag(o,b,Oorsprong, Bestemming, TijdAanvraag,Prioriteit, matrix, indexOorsprong, indexBestemming) + Reistijd(): double
Figuur 3-6: Class diagram van de routeplanning
Het project is samengesteld uit zes klassen. De klasse Data maakt in eerste instantie een connectie met de database “Inventaris_bennes_thesis”, waarbij alle trips behorende tot een bepaalde shift opgevraagd worden uit de tabel “Aanvragen”. Deze trips worden opgeslagen in de array AanvraagLijst[] en worden
35
gedefinieerd als zijnde van het type ‘Aanvraag’. De klasse AfstandsMatrix bouwt een ‘afstandsMatrix’ op die de kortste afstanden bevat tussen alle oorsprongen en bestemmingen. Om die kortste afstanden te berekenen, wordt gebruik gemaakt van het Dijkstra-algoritme in de klasse Dijkstra. In de klasse Solution tenslotte wordt, gebruik makend van de methode routeConstruction(), een initiële oplossing samengesteld waarop in een volgende stap de ‘improvement’ heuristieken uitgevoerd worden met behulp van de methoden relocateSolution() en swapSolution(). Om de penalty kost S en de opstartkost R uit de doelfunctie van het mathematisch model te bepalen, werd het programma getest met verschillende waarden voor deze kosten. Daaruit bleek dat met een opstartkost van 50 en een penalty kost van 0.05 realistische routeplanningen bekomen worden. Het volledige project staat op bijgevoegde CD-rom. Bij het runnen dient de gebruiker drie gegevens in te geven: de datum, het aantal beschikbare chauffeurs en het startuur van de shift. De data waarvan de trips in de database werden opgenomen zijn 1/04/2008, 2/04/2008 en 3/04/2008. De data moeten exact volgens deze notatie in het programma ingegeven worden. Voor de analyse van de resultaten die hierna besproken wordt, werd er steeds vanuit gegaan dat er zes chauffeurs beschikbaar zijn, zodanig dat er geen restrictie op het aantal bennewagens wordt opgelegd.
3.5.5 RESULTATEN In delen 3.5.1 t.e.m. 3.5.4 werd de aanpak van de automatische routeplanning uitgebreid behandeld. Dit deel analyseert de resultaten van deze routeplanning door middel van een test op negen verschillende datasets of shiften. In eerste instantie wordt in deel 3.5.5.1 de output van de routeplanning gegenereerd voor de negen shiften aan de hand van de zeven ‘improvement’ heuristieken (supra p. 34). De resultaten worden geanalyseerd en vergeleken met de realiteit. Daarna gaat deel 3.5.5.2 na hoe de routeplanning presteert wanneer de frequentie van de trips per shift toeneemt. In onderstaande analyse worden de shiften genummerd van 1 t.e.m. 9, waarbij geldt: •
Shift 1: 1 april 2008, voormiddag-shift
•
Shift 2: 1 april 2008, namiddag-shift
•
Shift 3: 1 april 2008, nacht-shift
•
Shift 4: 2 april 2008, voormiddag-shift
•
Shift 5: 2 april 2008, namiddag-shift
•
Shift 6: 2 april 2008, nacht-shift
•
Shift 7: 3 april 2008, voormiddag-shift
•
Shift 8: 3 april 2008, namiddag-shift
•
Shift 9: 3 april 2008, nacht-shift 36
3.5.5.1 Output routeplanning en vergelijking met de realiteit In onderstaande tabel wordt een overzicht gegeven van de output van de routeplanning, toegepast op de negen datasets. Voor elke dataset werd het programma zeven keer uitgevoerd, telkens gebruik makend van een andere ‘improvement’ heuristiek. Daarna werd voor elke shift de totale duur van de routes en de stilstand genoteerd van de optie die de laagste waarde van de doelfunctie bereikte. Deze waarde is, zoals beschreven in deel 3.5.2, samengesteld uit de opstartkost van de routes en de penalty kost voor de stilstand en het tijdsverschil tussen het aanvraagtijdstip en het begin van de uitvoering. De totale duur dat er effectief gereden werd tijdens de shift, wordt berekend door van de totale duur de stilstand in mindering te brengen (=Duur-Stilstand). Door deze effectief gereden duur tenslotte te delen door het aantal aanvragen, bekomt men de gemiddelde uitvoeringstijd per trip (=Gem. duur/trip). Shift 1
Shift 2
Shift 3
Shift 4
Shift 5
21
22
29
27
34
Kost optie 1
459,77
398,32
621,11
542,72
759,87
Kost optie 2
429,71
368,09
426,03
480,30
604,66
Kost optie 3
406,95
357,71
437,46
443,04
571,94
Kost optie 4
429,71
361,85
426,03
480,30
530,63
Kost optie 5
429,71
367,66
426,03
480,30
585,98
Kost optie 6
444,12
357,71
576,00
512,15
715,05
Kost optie 7
429,71
359,56
426,03
480,30
562,91
Totale kost
406,95
357,71
426,03
443,04
530,63
Totale duur
10:14:58
10:29:01
12:46:15
12:00:17
14:40:44
Stilstand
1:18:12
1:07:38
1:46:51
1:55:41
2:20:04
Duur-Stilstand
8:56:46
9:21:23
10:59:24
10:04:36
12:20:40
Gem. duur/trip
0:25:33
0:25:31
0:22:44
0:22:23
0:21:47
3
3
4
3
4
1,28
1,31
1,60
1,50
1,83
3
3
3
3
3
2,36
2,13
2,19
2,81
2,38
# trips
# wagens # wagens in voltijds eq. # wagens in realiteit # wagens in voltijds eq.
Shift 6
Shift 7
Shift 8
Shift 9
40
38
27
38
Kost optie 1
755,62
802,65
581,57
1047,24
Kost optie 2
649,56
694,87
589,40
1014,07
Kost optie 3
696,98
662,37
574,54
996,00
# trips
37
Shift 6
Shift 7
Shift 8
Shift 9
Kost optie 4
617,04
672,23
570,91
1002,86
Kost optie 5
625,80
678,86
581,70
1006,38
Kost optie 6
725,90
779,69
574,54
1027,50
Kost optie 7
616,71
671,94
574,99
1002,86
Totale kost
616,71
662,37
570,91
996,00
Totale duur
16:51:30
16:55:27
12:23:10
16:21:04
Stilstand
2:47:02
2:14:48
1:09:31
1:35:00
Duur-Stilstand
14:04:28
14:40:39
11:13:39
14:46:04
Gem. duur/trip
0:21:06
0:23:10
0:24:57
0:23:19
3
5
4
5
2,11
2,12
1,55
2,04
3
4
3
4
2,44
3,19
2,06
2,31
# wagens # wagens in voltijds eq. # wagens in realiteit # wagens in voltijds eq.
Tabel 3-2: Output van de automatische routeplanning
Uit de tabel blijkt dat de ‘improvement’-heuristiek van optie 1 over de hele lijn de slechtste waarden voor de doelfunctie geeft. De resultaten van de andere zes opties zijn vergelijkbaar. Verder kan geconcludeerd worden dat het aantal gebruikte bennewagens in de automatische planning sterker varieert dan het aantal bennewagens die in werkelijkheid werden ingezet tijdens de referentieperiode. Het aantal wagens is steeds groter of gelijk aan het aantal wagens in realiteit, maar worden steeds voor een kortere duur ingezet. Om het aantal wagens correct te kunnen vergelijken werd het ‘aantal wagens in voltijds equivalenten’ berekend. Dit is een maat voor het aantal wagens dat gedurende de hele shift gebruikt werd en wordt bekomen door de ‘totale duur’ te delen door 8u. Uit de resultaten blijkt duidelijk dat het ‘aantal wagens in voltijds equivalenten’ van de routeplanning steeds lager ligt dan in realiteit. Tenslotte toont Tabel 3-2 ook aan dat de zes beschikbare bennewagens nooit allemaal ingezet worden tijdens de uitvoering van een bepaalde shift. Het algemeen gemiddelde van de uitvoeringstijd per trip, i.e. het gemiddelde van de gemiddelde duur per trip over de negen datasets, bedraagt 23 minuten 23 seconden. Dit is beduidend lager dan huidige gemiddelde uitvoeringstijd van 30 minuten (supra p.20), waaruit kan besloten worden dat de automatische routeplanning in een verhoging van de efficiëntie resulteert ten aanzien van de huidige manuele planning. Het aantal trips dat een bennewagen per shift kan uitvoeren stijgt immers met 3 ten opzichte van de manuele planning. Een shift heeft een duur van 8 uur, rekening houdend met de lunchpauze van 30 minuten, wordt de tijd waarop effectief gereden wordt gelijk aan 7 uur 30 minuten. Op basis van de gemiddelde bedieningstijd van 30 minuten is het aantal ritten in de manuele planning
38
gemiddeld gelijk aan 7u30’/30’ = 14. Voor de automatische routeplanning daarentegen wordt dit: 7u30’/23’23’’ = 17. Om de verschillen tussen de automatische routeplanning en de realiteit te illustreren, wordt hierna de automatische planning van shift 1 vergeleken met de werkelijke planning. Het linkse deel van de tabel werd rechtstreeks overgenomen uit de output van de routeplanning. De resultaten in het rechtse deel werden berekend aan de hand van de ‘penalty’ kosten en de opstartkost uit de routeplanning. Het tijdstip waarop de trip in werkelijkheid afgewerkt werd, werd door een gebrek aan data bepaald op basis van de gemiddelde uitvoeringstijd per trip van 30 minuten. De tijdstippen van ‘Einde_uitvoering’ die in de laatste kolom gegeven worden zijn dus niet de exacte reële tijdstippen, maar wel een ruwe schatting. De totale kost, duur en stilstand worden bekomen door het aanvraagtijdstip en het tijdstip van afwerking van opeenvolgende trips met elkaar te vergelijken. Routeplanning
Realiteit
Aanvraagtijdstip
Einde_uitvoering
Aanvraagtijdstip
Einde_uitvoering
0:00:00
0:00:00
0:00:00
6:00:00
0:00:00
6:07:00
5:10:00
6:30:00
6:07:00
6:29:04
6:28:00
7:00:00
6:27:00
6:49:54
7:15:00
7:45:00
6:28:00
7:19:21
7:18:00
8:15:00
7:18:00
7:45:25
8:16:00
8:46:00
0:00:00
0:00:00
11:45:00
12:15:00
0:00:00
6:25:00
12:16:00
12:46:00
6:25:00
6:54:13
13:00:00
13:30:00
6:48:00
7:16:57
6:28:00
14:00:00
7:15:00
7:46:50
0:00:00
6:07:00
7:56:00
8:26:28
6:07:00
6:37:00
8:16:00
8:53:49
6:27:00
7:07:00
9:16:00
9:38:25
6:48:00
7:37:00
10:20:00
10:48:49
7:56:00
8:26:00
10:20:00
11:15:56
10:20:00
10:50:00
10:20:00
11:43:03
12:10:00
12:40:00
11:45:00
12:07:20
10:20:00
13:10:00
12:10:00
12:37:21
10:20:00
13:40:00
12:16:00
13:04:34
0:00:00
6:25:00
13:00:00
13:30:49
6:25:00
6:55:00
0:00:00
6:00:00
6:55:00
7:25:00
5:10:00
6:28:38
7:23:00
7:55:00
6:28:00
6:54:16
9:16:00
9:46:00
6:55:00
7:23:47
0:00:00
0:00:00
7:23:00
7:55:29
0:00:00
0:00:00
0:00:00
0:00:00
0:00:00
0:00:00
0:00:00
0:00:00
0:00:00
0:00:00
39
Routeplanning Totale kost: Totale duur: Totale stilstand: Duur - Stilstand: # wagens: # wagens in voltijds eq.
Realiteit 406,95 10:14:58 1:18:12 8:56:46 3 1,28
573,60 18:54:00 9:24:00 9:30:00 3 2,36
Totale kost: Totale duur: Totale stilstand: Duur - Stilstand: # wagens: # wagens in voltijds eq.
Tabel 3-3: Vergelijking automatische en manuele planning voor shift 1
Uit de tabel blijkt dat in beide gevallen drie bennewagens gebruikt worden voor de planning van shift 1. De volgorde waarin de trips gepland worden is echter heel verschillend. De totale kost en duur van de routes ligt veel hoger in werkelijkheid, dit voornamelijk door de hogere stilstand.
3.5.5.2 Scenario-analyse: Performantie van de routeplanning bij een hogere frequentie van de aanvragen Uit vorige analyse kan reeds geconcludeerd worden dat de routeplanning betere resultaten levert dan de manuele planning die vandaag door de afdeling toegepast wordt. Maar wat als de frequentie van de trips stijgt? Is de routeplanning dan nog in staat een aanvaardbare oplossing te leveren? Om dit scenario te testen werd het oorspronkelijke interval tussen twee opeenvolgende aanvraagtijdstippen gereduceerd met 20%. Dit zorgt voor een gemiddeld aantal trips van 37 over de negen shiften, tegenover een gemiddelde van 31 trips in de normale situatie. Merk op dat de onderstaande shiften niet kunnen vergeleken worden met de negen shiften uit de normale situatie omdat ze niet uit dezelfde trips bestaan.
# trips Kost optie 1 Kost optie 2 Kost optie 3 Kost optie 4 Kost optie 5 Kost optie 6 Kost optie 7 Totale kost Totale duur Stilstand Duur-Stilstand gem. duur/trip # wagens # wagens in voltijds eq.
Shift 1
Shift 2
Shift 3
Shift 4
Shift 5
27
32
34
42
56
711,15 634,77 644,13 628,50 628,50 698,15 623,66
708,54 616,46 615,17 592,38 599,40 660,09 589,78
754,95 766,56 734,11 752,77 764,08 734,11 756,77
741,56 702,56 712,99 671,66 686,57 723,95 675,23
909,59 747,64 847,66 747,64 747,64 883,26 747,64
623,66 12:55:21 2:18:40 10:36:41 0:23:34 4 1,62
589,78 14:02:47 2:33:24 13:07:50 0:24:37 4 1,76
734,11 15:40:02 0:54:57 14:45:05 0:26:01 2 1,96
671,66 19:12:04 5:21:06 13:50:58 0:19:47 4 2,40
747,64 23:32:40 2:55:45 20:36:55 0:22:05 5 2,94 40
Shift 6
Shift 7
Shift 8
Shift 9
34
38
34
35
Kost optie 1
700,50
803,50
1224,91
699,75
Kost optie 2
651,22
697,03
1162,78
573,83
Kost optie 3
623,79
739,10
1147,32
618,36
Kost optie 4
651,22
697,03
1162,78
566,71
Kost optie 5
651,22
697,03
1162,78
571,18
Kost optie 6
664,25
786,66
1193,33
663,85
Kost optie 7
651,22
697,03
1162,78
567,17
Totale kost
623,79
697,03
1147,32
566,71
Totale duur
15:10:55
17:09:40
15:25:29
14:58:56
Stilstand
1:45:32
4:30:05
2:19:33
1:44:46
Duur-Stilstand
13:25:23
12:39:35
13:05:56
13:14:10
gem. duur/trip
0:23:41
0:19:59
0:23:06
0:22:41
2
4
5
5
1,90
2,15
1,93
1,87
# trips/aanvragen
# wagens # wagens in voltijds eq.
Tabel 3-4: Output van de automatische routeplanning bij een hogere frequentie van de trips
In bovenstaande tabel is te zien dat de routeplanning ook in dit scenario een realistische planning genereert. De gemiddelde uitvoeringstijd per trip over de negen shiften is in dit geval gelijk aan 22 minuten 50 seconden en het aantal gebruikte bennewagens is ook hier altijd kleiner dan zes. Het eerste deel van de case kan beëindigd worden met volgende conclusie. De ontwikkelde automatische planning van het bennewagentransport slaagt erin voor elke geteste dataset een planning te genereren met een lagere gemiddelde uitvoeringstijd per trip dan met de huidige manuele planning mogelijk is. Dit heeft als gevolg dat de bennewagens gemiddeld drie trips meer kunnen uitvoeren per shift. Het gebruik van de automatische routeplanning zorgt met andere woorden voor een verhoging van de efficiëntie. Daarbovenop blijkt uit de scenario-analyse dat zelfs wanneer de frequentie van de trips toeneemt, in geen enkel geval meer dan vijf bennewagens ingezet worden. De zesde bennewagen waarover de afdeling RBV beschikt is dus eigenlijk overbodig.
3.6 DEEL 2: LOCATIE NIEUWE WEEGBRUG Nadat in het eerste deel van de case de automatisering van de planning van het bennewagentransport werd behandeld op basis van de huidige infrastructuur, wordt in het tweede deel nagegaan of een wijziging in de infrastructuur de efficiëntie verder kan opdrijven. Eerst wordt in deel 3.6.1 nog eens kort het probleem geschetst. Daarna beschrijven deel 3.6.2 en 3.6.3 respectievelijk de methodiek en de
41
implementatie van de oplossing. Tenslotte wordt in deel 3.6.4 een overzicht gegeven van de belangrijkste resultaten.
3.6.1 PROBLEEMSTELLING Zoals reeds vermeld in deel 3.5 moeten de bennewagens tijdens het uitvoeren van een trip de benne laten wegen op een weegbrug. Vandaag gebeurt dit op de weegbrug aan de kantoren van de afdeling RBV en op de baanweegbrug. De baanweegbrug is voor het intern transport echter enkel beschikbaar tussen 18u en 6u. Gedurende de dag wordt de baanweegbrug voorbehouden voor het extern transport. In onderstaande figuur wordt aangetoond dat de oorsprongen en bestemmingen van het overgrote deel van de trips in dezelfde regio gesitueerd kunnen worden. Op basis van data van de maand april 2008 blijkt dat 69% van de oorsprongen zich in de afdeling Koudwalserij bevindt en dat 64% van de trips de Staalfabriek als bestemming heeft. 64 % van de bestemmingen
69 % van de oorsprongen Figuur 3-7: Situering van het overgrote deel van de oorsprongen en bestemmingen op het grondplan van ArcelorMittal Gent
In bijlage B is een meer gedetailleerde versie van het grondplan voorzien, waarbij O een oorsprong in de Koudwalserij voorstelt en B een bestemming in de Staalfabriek. Daarnaast is ook de route aangeduid die door de bennewagens gevolgd wordt, wanneer een trip met oorsprong O en bestemming B uitgevoerd moet worden. Dit is het geval voor ongeveer 60% van alle trips. De trip begint in O, waarna de bennewagen zich naar de dichtstbijzijnde weegbrug verplaatst, vandaar naar de bestemming B en tenslotte terug naar O rijdt om de benne terug op zijn oorspronkelijke plaats af te zetten. In de huidige 42
situatie zal de bennewagen zich ’s nachts, i.e. tussen 18u en 6u, naar de baanweegbrug begeven en overdag, i.e. tussen 6u en 18u, naar de weegbrug aan de afdeling RBV. In bijlage B is duidelijk te zien dat in het laatste geval de extra afstand naar de weegbrug RBV significant is. Hierdoor gaat kostbare tijd verloren. Met de bedoeling om de uitvoeringstijd per trip verder naar beneden te halen, wordt in dit deel van de case naar een oplossing gezocht om de afgelegde afstand tijdens de uitvoering van de trips te minimaliseren. Volgens het management van de afdeling RBV bestaan er twee mogelijke oplossingen voor dit probleem. Het eerste alternatief betreft de installatie van een weegsysteem op de bennewagens, zodat het bezoek aan de weegbrug overbodig wordt. Het tweede alternatief is het plaatsen van een nieuwe weegbrug op een locatie die de totale afstand minimaliseert. Uit eerdere tests blijkt dat de installatie van een weegsysteem op de bennewagen zelf een aantal problemen met zich meebrengt. Alle geteste weegsystemen vertoonden vervroegde slijtage door de kracht die de benne erop uitoefent tijdens het laden. Verder marktonderzoek dient uitgevoerd te worden naar nieuwe technieken, maar dit behoort niet tot de scope van deze case. De case beperkt zich tot het onderzoeken van het tweede alternatief.
3.6.2 OPLOSSINGSMETHODIEK Het bepalen van de optimale locatie voor een nieuwe weegbrug is een klassiek geval van de ‘center-ofgravity’ methode. Deze methode wordt vaak gebruikt in het Gravity Location Problem om te berekenen waar een nieuwe plant, een magazijn bijvoorbeeld, moet worden gebouwd zodat de totale afstand, afgelegd door inkomende en uitgaande goederen, geminimaliseerd wordt. Het basisprincipe van deze methode kan ook toegepast worden op het weegbrugprobleem in ArcelorMittal Gent. In het klassieke Gravity Location Problem worden in eerste instantie alle toeleverende plants en afnemende markten van de nieuwe plant geïdentificeerd. Daarna wordt in een tweede fase, aan de hand van de ‘center-of-gravity’ methode, de locatie bepaald die de totale Euclidische afstand tussen al deze punten en de nieuwe plant minimaliseert. In plaats van het ‘center-of-gravity’ van een groep punten te bepalen moet in deze case daarentegen het center-of-gravity van een aantal lijnstukken berekend worden. De nieuwe weegbrug moet immers op een minimale afstand van de routes tussen de oorsprongen en bestemmingen van de trips liggen. Door het grote aantal mogelijke combinaties van oorsprongen en bestemmingen is het in realiteit zeer moeilijk om de ‘center-of-gravity’ methode toe te passen. Bovendien kan er niet om het even waar een nieuwe weegbrug gebouwd worden. Het gebied dat relevant is voor de locatie van deze weegbrug is
43
immers reeds zeer dicht bebouwd. Op basis van deze twee redenen wordt hier voor een andere aanpak geopteerd. Na enkele gesprekken met de managers van RBV werd al snel duidelijk dat er slechts vier potentiële locaties zijn waar voldoende plaats voorhanden is. De vier alternatieven zijn aangeduid op het grondplan in bijlage B. Dat deze alternatieven goed gelegen zijn blijkt uit het feit dat ze vlakbij de route OB gelokaliseerd zijn. Aangezien bijna 60% van de trips deze route gebruiken, is het waarschijnlijk dat de totale afgelegde afstand in deze gevallen lager zal liggen dan de afgelegde afstand in de huidige situatie. Bovenop de vorige vier alternatieven, wordt verder nagegaan wat er gebeurt als de baanweegbrug volledig voorbehouden wordt voor het bennewagentransport. In dit geval kan dus zowel ’s nachts als overdag van deze weegbrug gebruik gemaakt worden. De baanweegbrug is vlakbij de route OB gelegen, wat ook wijst op potentiële verbeteringen in vergelijking met de huidige situatie. Aangezien de weegbrug aan de afdeling RBV in de toekomst steeds in gebruik zal blijven, worden in onderstaande analyse derhalve 5 mogelijkheden getest: •
Optie 1: Alternatief 1 + weegbrug RBV
•
Optie 2: Alternatief 2 + weegbrug RBV
•
Optie 3: Alternatief 3 + weegbrug RBV
•
Optie 4: Alternatief 4 + weegbrug RBV
•
Optie 5: Baanweegbrug + weegbrug RBV
Deze mogelijkheden worden getest met behulp van een dataset die alle trips bevat, behorende tot een referentieperiode van 1 maand. Nadien worden de resultaten vergeleken met de huidige situatie. Als referentieperiode werd de maand april van vorig jaar gekozen. Concreet zal nagegaan worden welke optie de som van de afgelegde afstanden binnen de trips over de volledige referentieperiode minimaliseert. Merk op dat enkel de afstanden binnen de trips, dus de afstanden oorsprong – weegbrug – bestemming – oorsprong, gesommeerd worden. De afstanden tussen de oorsprongen van twee opeenvolgende trips wordt niet in rekening gebracht. Deze afstanden zullen immers niet veranderen door de ingebruikname van een nieuwe weegbrug. Aangezien geen informatie over het aanvraagtijdstip van de trips beschikbaar was, kan de huidige situatie, i.e. de weegbrug aan de afdeling RBV gecombineerd met de baanweegbrug ’s nachts, niet nagebootst worden. Daarom wordt in de berekening verondersteld dat in de huidige situatie enkel de weegbrug RBV gebruikt wordt. Er moet m.a.w. rekening worden gehouden met het feit dat de
44
kostenbesparing tussen de huidige situatie en de verschillende opties groter zal zijn in de resultaten van de case dan in werkelijkheid.
3.6.3 IMPLEMENTATIE Elke optie werd als volgt getest met behulp van de programmeertaal Java. Stap 1: Net zoals in het eerste deel van de case worden alle trips behorende tot de referentieperiode opgehaald uit de database, dit maal uit de tabel “Ritten_april_2008”. Dit gebeurt in de klasse Data. Stap 2: In de klasse Afstandsmatrix wordt een afstandsmatrix samengesteld die de kortste afstanden tussen alle oorsprongen en bestemmingen bevat. De kortste paden worden berekend aan de hand van het Dijkstra-algoritme in de klasse Dijkstra. Stap 3: Voor elke trip uit de dataset wordt in de klasse Oplossing de afstand berekend tussen oorsprong en bestemming en terug. Daarbij zal telkens die weegbrug geselecteerd worden die de afstand minimaliseert. In elke optie is er immers de keuze tussen een nieuwe, virtuele weegbrug of de baanweegbrug en de weegbrug RBV. Stap 4: De afgelegde afstanden van de verschillende trips worden opgeteld. Het class diagram van de implementatie in Java ziet er als volgt uit:
45
AfstandsMatrix - dijkstraMatrix: double[][] - afstandsMatrix: double[][] - dbConnection: Connection + AfstandsMatrix() + loadDriver(): void + connectDatabase(): void + constructDijkstraMatrix(): void + closeConnection(): void + constructAfstandsMatrix(): void + printDijkstraMatrix(): void + printAfstandsMatrix(): void
Data - aantalAanvragen: int - AanvraagLijst: Aanvraag[ ] - dbConnection: Connection - loadDriver(): void - connectDatabase(): void - closeConnection(): void + Data(matrix) + printAanvraagLijst():void
Solution
<<use>> Dijkstra
+ dijkstra(): double[]
Knooppunt - Xcoord: double - Ycoord: double + Knooppunt() + Knooppunt(Xcoord, Ycoord) + Afstand(): double
Aanvraag - Depot: Knooppunt - Oorsprong: Knooppunt - Bestemming: Knooppunt - bennenummer: String - bestemming: String -ServiceAfstand: double -ServiceAfstandWGB1: double - ServiceAfstandWGB2: double - indexOorsprong: int - indexBestemming: int - matrix: AfstandsMatrix
- data: Data - matrix: Afstandsmatrix - Dummy: Aanvraag - Oplossing: Aanvraag[] - length: double + Solution() + Solution(data, matrix) + routeConstruction(): void + printAfstand(): void
+ Aanvraag(matrix) + Aanvraag(o,b,Oorsprong, Bestemming, matrix, indexOorsprong, indexBestemming
Figuur 3-8: Class diagram van het project ‘Nieuwe weegbrug’
De volledige code is terug te vinden op bijgevoegde CD-rom, onder het project “Nieuwe weegbrug”.
3.6.4 RESULTATEN Zoals reeds vermeld zullen de besparingen in werkelijkheid iets lager liggen dan hieronder behandeld. Maar aangezien dit voor alle opties geldt, zal het geen invloed hebben op de keuze van het beste alternatief. Het runnen van de code gaf volgende resultaten voor de verschillende opties:
46
Figuur 3-9:: Resultaten van het programma, programma, getest op de referentieperiode april 2008
Uit bovenstaande grafiek blijkt onmiddellijk dat er een significante daling is van de totale afgelegde afstand onder alle opties ten opzicht van de huidige situatie. situatie Aangezien de locaties van de nieuwe weegbruggen onder optie 1 t.e.m. 4 dicht bij elkaar gelegen zijn, is hun totale afgelegde afstand vergelijkbaar. Gemiddeld leiden deze 4 opties tot een daling in de afgelegde afstand van 14,30%. 14 Optie 3 geeft iets betere resultaten dan de andere drie opties, maar in het algemeen kan gesteld worden dat het lijnstuk waarop deze vier alternatieve weegbruggen gelegen zijn, een goede goede locatie vormt om er een nieuwe weegbrug te bouwen. Een daling van 14,30% in de afgelegde afstand afstand leidt logischerwijs ook tot éénzelfde éé daling van de uitvoeringstijd stijd per trip. Uit het eerste deel van de case blijkt dat de automatische routeplanning resulteert in een gemiddelde uitvoeringstijd uitvoering van 23 minuten 23 seconden per trip. Deze bedieningstijd wordt na ingebruikname van een nieuwe weegbrug gelijk aan 20 minuten 2 seconden. Behalve een daling in de uitvoeringstijd uitvoering heeft een lagere afgelegde afstand ook ok in een daling van het brandstofverbruik tot gevolg. Wanneer we uitgaan van een gemiddelde gemiddelde brandstofprijs van € 0,5083 per liter5 en een verbruik van 25l per 100 km, km zorgt een daling in de afgelegde afstand met 14,30% voor een
5
Berekend op basis van het jaargemiddelde van 2008 en het gemiddelde van de eerste vier maanden van 2009 van de prijs van gasolie. (Bron: http://www.agoria.be) 47
besparing van 2490,986 km6 * 25l /100km * €0,5083/l = €316,54 op maandbasis. Op jaarbasis geeft dit een besparing van € 3798,50. Merk echter op dat optie 5, waarbij volledig gebruik kan gemaakt worden van de baanweegbrug, ook een daling van de afgelegde afstand met 10,2% teweegbrengt. Het verschil met de vorige opties is m.a.w. heel klein. De uitvoeringstijd per trip wordt in dit geval gelijk aan 20 minuten 59 seconden. De besparing in brandstofprijs op maandbasis is verder gelijk aan 1831,658km * 25l/100km * €0,5083/l = €232,76, hetgeen resulteert in een besparing van € 2793,10 op jaarbasis. Op basis van deze resultaten kan een investeringsanalyse uitgevoerd worden, waaruit zal blijken welk alternatief, het bouwen van een nieuwe weegbrug of een volledige terbeschikkingstelling van de baanweegbrug, het beste rendement opbrengt. Het bouwen van een nieuwe weegbrug resulteert in een extra jaarlijkse besparing van € 1005,407, maar daar tegenover is er een initiële investering nodig terwijl die bij het gebruik van de baanweegbrug niet het geval is. De beslissing tot het bouwen van een nieuwe weegbrug kan in elk geval niet enkel genomen worden op basis van het bennewagentransport alleen. Ook andere interne transporten die gebruik maken van de weegbruggen en het externe transport moeten in rekening gebracht worden. Op basis van deze analyse kan geconcludeerd worden dat alle vijf de opties de uitvoeringstijd per trip reduceren en bijgevolg ook de efficiëntie verder verbeteren. Om de vraag te kunnen beantwoorden welke optie geïmplementeerd moet worden, is verder onderzoek nodig, maar dit behoort niet tot de scope van deze scriptie.
3.7 CONCLUSIES EN VERDER ONDERZOEK In deel 3.3 werden twee onderzoeksproblemen geformuleerd. Op basis van het onderzoek in deel 3.5 en 3.6 blijkt dat op beide probleemstellingen een positief antwoord kan gegeven worden. In eerste instantie werd in deel 3.5 de planning van de trips geautomatiseerd op basis van de literatuur over het VRP. Uit de analyse van de resultaten kon geconcludeerd worden dat deze automatische routeplanning een efficiëntieverhoging realiseert ten aanzien van de huidige manuele planning. Op basis van de geautomatiseerde planning uit deel 3.5, werd in deel 3.6 nagegaan of een wijziging in de infrastructuur, namelijk het bouwen van een nieuwe weegbrug of een volledige terbeschikkingstelling van de baanweegbrug, de efficiëntie verder kan verhogen. Daar beide alternatieven de totale afgelegde afstand reduceren en bijgevolg ook de gemiddelde uitvoeringstijd per trip verminderen, kunnen we ook 6
2490,986 = 14,30% * 17417,575
7
€ 3798,50 – € 2793,10 = € 1005,40 48
hier concluderen dat een wijziging in de infrastructuur inderdaad een efficiëntieverhoging teweeg brengt. Het is echter niet mogelijk op basis van deze beperkte analyse te besluiten welk alternatief de voorkeur verdient. Daarvoor is een uitgebreider onderzoek nodig waarbij alle interne transporten en het externe transport in rekening gebracht worden. Een belangrijke opmerking bij bovenstaand onderzoek is dat gepoogd werd het real-time karakter van de planning van het bennewagentransport te simuleren, maar dat het in werkelijkheid toch nog anders verloopt. In realiteit is het immers niet mogelijk om de kost te minimaliseren nadat alle aanvragen gekend zijn, hetgeen in de routeplanning wel gebeurt aan de hand van de ‘improvement’ heuristieken. In realiteit ligt de kost van de trips die reeds uitgevoerd werden of in uitvoering zijn vast. Hierna volgen enkel suggesties voor verder onderzoek. In eerste instantie kan het mathematisch model aangepast worden tot een dynamisch VRP model, waarbij met alle aspecten van een real-time planning rekening wordt gehouden. Het kan verder nuttig zijn te onderzoeken of een combinatie van de automatische planning met een GPS-systeem voordelen biedt. Het gebruik van een GPS-systeem laat toe de bennewagens op elk moment te localiseren, waardoor de planning mijns inziens nog accurater georganiseerd kan worden. Ten derde is verder onderzoek nodig naar de modellering van het beslissingsproces van de dispatcher. In deze case werd een eenvoudig systeem van prioriteiten toegepast, maar een ‘vehicle dispatching’ model is in staat met meerdere criteria rekening te houden. Een vierde suggestie voor verder onderzoek is het toepassen van meer geavanceerde ‘improvement’ heuristieken op het mathematisch model. Tabu Search en Guided Local Search bijvoorbeeld zullen hoogstwaarschijnlijk nog betere waarden van de doelfunctie bereiken. Een laatste suggestie tenslotte betreft het in rekening brengen van bijkomende restricties in het mathematisch model, zoals de kans op file of een defect aan de wagens.
49
4 ALGEMEEN BESLUIT Een geïntegreerd staalbedrijf zoals ArcelorMittal Gent steunt op tal van uiteenlopende activiteiten die dagelijks op elkaar moeten afgestemd worden. In het streven naar efficiëntieverhoging werden in de loop der jaren verschillende beslissingsondersteunde instrumenten ontwikkeld om deze activiteiten te optimaliseren. Sommige activiteiten echter, waaronder het bennewagentransport, vielen tot nu toe uit de boot. De bennewagens verzorgen het interne afvaltransport in ArcelorMittal Gent. Elke afdeling beschikt over een aantal containers of bennes waarin het afval van de productie of van afbraakwerken opgevangen wordt. Wanneer deze bennes vol zijn, laten de afdelingen dit telefonisch aan de dispatcher van het bennewagentransport weten. Daarop beslist de dispatcher welke van de beschikbare bennewagens de opdracht moet uitvoeren zodanig dat totale afgelegde afstand zo klein mogelijk wordt. Voor dit manueel proces werd in deze masterproef een beslissingsondersteunend instrument, i.e. een automatische routeplanning, ontwikkeld. Het planningsprobleem van het bennewagentransport is een voorbeeld van een Vehicle Routing Problem (VRP), één van de meest bestudeerde onderwerpen in het operationeel onderzoek. Het doel van een VRP bestaat uit het bepalen van een set van routes voor een vloot van voertuigen zodat aan alle eisen van een vooropgesteld aantal klanten wordt voldaan en dit met minimale kosten. Een groot aantal optimalisatietechnieken werd reeds ontwikkeld om het VRP op te lossen. Heuristieken zoals de ‘Clarke and Wright savings’ heuristiek en de ‘insertion’ heuristieken en metaheuristieken zoals ‘Tabu Search’ en ‘Guided Local Search’ zijn enkele voorbeelden. De variant van het VRP die het meest aanleunt bij het planningsprobleem in ArcelorMittal Gent, is het Rollon-Rolloff VRP. Het Rollon-Rolloff VRP is een afvalophalingsprobleem waarbij routes worden uitgestippeld voor voertuigen die afvalcontainers moeten ophalen in een bepaald gebied. Elk voertuig kan daarbij slechts één container tegelijk vervoeren. De routes zijn samengesteld uit een opeenvolging van ‘trips’, waarbij elke trip de bediening van één klant voorstelt. In het geval van het bennewagentransport ziet een trip er als volgt uit: oorsprong – weegbrug – bestemming – oorsprong. Op de oorsprong wordt de volle benne opgehaald, waarna deze wordt gewogen op de weegbrug en geleegd op de bestemming. De trip wordt beëindigd met het terugbrengen van de lege benne naar de oorsprong. Het mathematisch model dat aan de basis ligt van de automatische routeplanning is gebaseerd op de literatuur van het Rollon-Rolloff VRP en beoogt de minimalisatie van de totale kost. Deze kost bestaat uit een opstartkost per route, een ‘penalty’ kost voor de tijd dat de ingezette bennewagens stilstaan, i.e.
50
onproductief zijn, en een ‘penalty’ kost voor het tijdsverloop tussen het moment waarop een trip aangevraagd werd en het tijdstip waarop de uitvoering aangevat wordt. Na het formuleren van het mathematisch model, wordt aan de hand van een heuristische benadering gezocht naar de oplossing die de waarde van de doelfunctie minimaliseert. De ‘cheapest insertion’ heuristiek zorgt voor de constructie van de initiële oplossing, waarna deze initiële oplossing verbeterd wordt met behulp van een ‘swap’ en een ‘relocate’ heuristiek. De automatische routeplanning werd getest op negen datasets, waarbij elke dataset één shift van acht uur vertegenwoordigt. Uit analyse van de resultaten blijkt dat de routeplanning systematisch een betere oplossing genereert dan de manuele planning die in werkelijkheid toegepast werd. De uitvoeringstijd per aanvraag bedraagt gemiddeld 23 minuten 23 seconden, tegenover een gemiddelde uitvoeringstijd van 30 minuten in werkelijkheid. Hierdoor kunnen met de automatische routeplanning gemiddeld drie aanvragen per shift meer verwerkt worden. Op basis van de automatische routeplanning wordt in een volgende stap onderzocht wat het effect is van een wijziging in de infrastructuur op de efficiëntie. Er wordt getest hoe de totale afgelegde afstand wijzigt bij een verandering van de locatie van de beschikbare weegbruggen. De resultaten tonen aan dat het wel degelijk mogelijk is de efficiëntie te verhogen door het bouwen van een nieuwe weegbrug of door een herstructurering van de huidige weegbruggen. Echter, om sluitende conclusies te kunnen maken, dienen ook andere interne transporten en het extern transport in rekening gebracht te worden. Een investeringsanalyse zal in de toekomst moeten uitwijzen of het de moeite loont een wijziging in de infrastructuur aan te brengen. De case is evenwel onderhevig aan een aantal beperkingen. Door een gebrek aan data en het real-time karakter van de planning is het niet mogelijk de planning en uitvoering van het bennewagentransport volledig na te bootsen. Een aantal vereenvoudigingen zijn dan ook onvermijdelijk. Verder onderzoek en een uitgebreidere dataset kunnen deze beperkingen eventueel opheffen. Op basis van een studie van dynamische VRP modellen en ‘vehicle dispatching’ modellen zou een complexer mathematisch model kunnen opgesteld worden dat het real-time karakter beter reflecteert. Verder zal het gebruik van meer geavanceerde heuristieken, zoals ‘Tabu Search’ of ‘Guided Local Search’, hoogstwaarschijnlijk tot betere oplossingen leiden dan mogelijk is met de huidige heuristieken.
51
5 LIJST VAN GERAADPLEEGDE WERKEN Aghezzaf, E.-H., 2006, Introduction to operations research, McGraw-Hill/ Irwin. Agoria, 2009, Marktprijzen van materialen: overzichtstabel gasolie,
. (14 mei 2009). Angelelli, E. en Speranza, M., 2002, The application of a vehicle routing model to a waste-collection problem: two case studies, Journal of the Operational Research Society, Vol. 53, Nr. 9, 944-952. Angelelli, E. en Speranza, M., 2002, The periodic vehicle routing problem with intermediate facilities, European Journal of Operational Research, Vol. 137, Nr. 2, 233-247. ArcelorMittal Gent, 2008, Zo maakt ArcelorMittal Gent staal, . (24 april 2009). Archetti, C. en Speranza, M., 2004, Vehicle routing in the 1-skip collection problem, Journal of the Operational Research Society, Vol. 55, Nr. 7, 717-727. Bodin, L., Mingozzi, A., Baldacci, R. en Ball, M., 2000, The Rollon-Rolloff Vehicle Routing Problem, Transportation Science, Vol. 34, Nr. 3, 271-288. Bräysy, O., 2001, Local Search and Variable Neighborhood Search Algorithms for the Vehicle Routing Problem with Time Windows, Acta Wasaensia, Nr. 87. Chopra, S. en Meindl, P., 2007, Supply Chain Management – Strategy, Planning & Operations, Pearson Prentice Hall, Upper Saddle River. Cordeau, J.-F. en Laporte, G., 2007, The dial-a-ride problem: models and algorithms, Annals of Operations Research, Vol. 153, Nr. 1, 29-46. Cordeau, J.-F., Gendreau, M., Laporte, G., Potvin, J.-Y. en Semet, F., 2002, A guide to vehicle routing heuristics, Journal of the Operational Research Society, Vol. 53, Nr. 5, 512-522. De Meulemeester, L., Laporte, G., Louveaux, F. en Semet, F., 1997, Optimal Sequencing of Skip Collections and Deliveries, Journal of the Operational Research Society, Vol. 48, Nr. 1, 57-64. Funke, B., Grünert, T. en Irnich, S., 2005, Local Search for Vehicle Routing and Scheduling Problems: Review and Conceptual Integration, Journal of Heuristics, Vol. 11, Nr. 4, 267-306. VI
Gendreau, M., Guertin, F., Potvin, J.-Y. en Séguin, R., 2006, Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries, Transportation Research Part C, Vol. 14, Nr. 3, 157-174. Gendreau, M. en Potvin, J.-Y., 2005, Metaheuristics in Combinatorial Optimization, Annals of Operations Research, Vol. 140, Nr. 1, 189-213. Glover, F., Kelly, J. en Laguna, M., 1995, Genetic algorithms and tabu search: hybrids for optimization, Computers Operations Research, Vol. 22, Nr. 1, 111-134. Potvin, J.-Y., Shen, Y., Dufour, G. en Rousseau, J.-M., 1995, Learning techniques for an Expert Vehicle Dispatching System, Expert Systems With Applications, Vol. 8, Nr. 1, 101-109. Toth, P. en Vigo, D., 2002, The Vehicle Routing Problem, SIAM, Philadelphia. Van Breedam, A., 2001, Comparing descent heuristics and metaheuristics for the vehicle routing problem, Computers & Operations Research, Vol. 28, Nr. 4, 289-315.
VII
Mechanica grondstoffen en haven
Elektriciteit grondstoffen en haven
Productie grondstoffen en bulkhaven
Preventie stofvervuiling
Dispatching en interne weegbrug
...
Staalfabriek
Operationele ondersteuning GHV
Hoogovens en sinterfabrieken
Bennetransport
RBV
Cokesfabriek
Productie haven en spoorvervoer
Grondstoffen, haven, vervoer en recuperatie Warmwalserij
Algemene en specifieke diensten voor alle afdelingen
Management
Koudwalserij
Sidgal
Organische verkledingslijn
Noble International Gent
6 BIJLAGEN
6.1 BIJLAGE A – ORGANOGRAM ARCELORMITTAL GENT
VIII
6.2 BIJLAGE B – SITUERING VAN DE WEEGBRUGGEN OP HET GRONDPLAN
O
Baanweegbrug
Alt. 4
Alt. 2
B Alt. 1
Weegbrug RBV
Alt. 3
IX
6.3 BIJLAGE C – OVERZICHT BINNENGEKOMEN AANVRAGEN PER SHIFT
X
6.4 BIJLAGE D – OVERZICHT RZICHT RITTEN PER CHAUFFEUR PER SHIFT
XI
6.5 BIJLAGE E – BESCHRIJVING VAN DE DATABASE “INVENTARIS_BENNES_THESIS” Deze
bijlage
geeft
een
overzicht
van
alle
tabellen
behorende
tot
de
database
“Inventaris_bennes_thesis”. De database is terug te vinden op bijgevoegde CD-rom. •
Tabel ‘Aanvragen’ Deze tabel bevat alle informatie over de aanvragen of trips, behorende tot de datasets die als input dienen voor de automatische routeplanning. Voor elke aanvraag zijn volgende data gegeven: de datum, de shift waarin de aanvraag werd uitgevoerd, het aanvraagtijdstip, het tijdstip waarop de benne werd gewogen, het nummer van de benne die opgehaald werd, de bestemming, het nummer van de bennewagen die de aanvraag uitvoerde en nog eens het aanvraagtijdstip, dit maal in seconden uitgedrukt.
•
Tabel ‘Aanvragen_Scenario’ Deze tabel vormt de input voor de automatische routeplanning in het kader van de scenarioanalyse. De gegevens in de tabel werden bekomen door de aanvragen uit de tabel ‘Aanvragen’ te dupliceren en daarna het interval tussen twee opeenvolgende aanvraagtijdstippen te reduceren met 20%.
•
Tabel ‘Afdeling’ Deze tabel geeft een overzicht van alle afdelingen die deel uit maken van ArcelorMittal Gent.
•
Tabel ‘Bennenummer_en_depot’ Alle bennes die over het hele grondgebied verspreid staan, werden in deze tabel ondergebracht. Voor elke benne zijn volgende data gegeven: de poort of plaats in de buurt waarvan de benne zich bevindt, de oorsprong tot dewelke de benne behoort, de coördinaten van de locatie van de benne, de prioriteit en de index van de benne in de afstandsmatrix van de java-projecten ‘Routeplanning’ en ‘Nieuwe weegbrug’.
•
Tabel ‘Bestemming’ Deze tabel geeft een overzicht van alle mogelijke bestemmingen, i.e. de plaatsen waar de bennes geleegd worden.
•
Tabel ‘Coördinaten_kruispunten’ Deze tabel bevat alle kruispunten op het bedrijfsterrein met bijhorende coördinaten. Deze tabel is een noodzakelijke input voor de berekening van het kortste pad tussen twee locaties.
•
Tabel ‘Kwaliteit’ In deze tabel worden alle materialen opgesomd die in de bennes verzameld worden.
•
Tabel ‘OBK’ Hier worden alle mogelijke combinaties van oorsprong – bestemming – kwaliteit weergegeven.
XII
•
Tabel ‘Oorsprong’ Deze tabel geeft een overzicht van alle oorsprongen, met bijhorende prioriteit en de sectie waartoe ze behoren.
•
Tabel ‘Ritten_april_2008 Deze tabel vormt de input voor het project ‘Nieuwe weegbrug’. Alle trips die uitgevoerd werden gedurende de referentieperiode april 2008 werden hier ondergebracht.
•
Tabel ‘Sectie’ In deze tabel wordt een overzicht gegeven van alle secties. Een sectie is onderdeel van een afdeling en een afdeling kan bijgevolg uit meerdere secties bestaan.
•
Tabel ‘Shortestpath’ Deze tabel duidt aan welke punten op het grondplan met elkaar verbonden zijn. Voor elke verbinding werd de Euclidische afstand berekend. De tabel dient als input voor het kortste padalgoritme.
•
Tabel ‘Weegbruggen’ In deze tabel werden alle weegbruggen, zowel de bestaande als de locaties voor de nieuwe weegbruggen, ondergebracht, met de bijhorende coördinaten.
XIII
