UNIVERSITEIT GENT FACULTEIT ECONOMIE EN BEDRIJFSKUNDE ACADEMIEJAAR 2013 – 2014
Verschillende heuristieken voor het Truck Driver Scheduling probleem van een Vlaams transportbedrijf
Masterproef voorgedragen tot het bekomen van de graad van Master of Science in de Toegepaste Economische Wetenschappen: Handelsingenieur
Marie Tack Lieze Verdonck onder leiding van Prof. Dr. Broos Maenhout
UNIVERSITEIT GENT FACULTEIT ECONOMIE EN BEDRIJFSKUNDE ACADEMIEJAAR 2013 – 2014
Verschillende heuristieken voor het Truck Driver Scheduling probleem van een Vlaams transportbedrijf
Masterproef voorgedragen tot het bekomen van de graad van Master of Science in de Toegepaste Economische Wetenschappen: Handelsingenieur
Marie Tack Lieze Verdonck onder leiding van Prof. Dr. Broos Maenhout
Voorwoord Een masterproef schrijf je niet alleen en in het geval van dit exemplaar kan dit letterlijk worden genomen. Onze samenwerking verliep zeer natuurlijk en zonder inspanningen waren we enorm goed op elkaar ingespeeld: we hadden niet veel woorden nodig om elkaar te verstaan en zaten (meestal) op hetzelfde spoor. Ook de taakverdeling vormde geen probleem. Het was voor ons steeds duidelijk wie de geschikte persoon van ons twee was voor welk deel van het werk. Dit zorgde ervoor dat we deze thesis op een e ciënte manier konden voltooien en dat we er echt voldoening uit haalden. Deze voldoening vond uiteraard ook zijn oorsprong in het onderwerp van deze thesis: we hebben van TransWest de kans gekregen om een deel van hun bedrijfsactiviteit uit te diepen en te simuleren. De samenwerking met het bedrijf verliep bijzonder vlot en wij willen TransWest hiervoor dan ook van harte bedanken. Daarnaast willen we onze promotor, professor Broos Maenhout, bedanken voor de vlotte samenwerking en om zijn enthousiasme voor het operationeel onderzoek in het algemeen en de personeel- en takenplanning in het bijzonder op ons over te brengen. Ook bedanken we graag Jonas Ingels voor zijn steeds prompte en uitvoerige hulp. Onze ouders verdienen eveneens een plaats in dit dankwoord: zij deelden onze zorgen en steunden ons waar ze konden, niet alleen gedurende dit zware semester maar doorheen onze gehele academische carièrre. We beseen dat hun investering in onze toekomst goud waard is en hopen hen met het bereiken van deze mijlpaal gerust te stellen dat we de goede weg op gaan. Tenslotte willen we onze vrienden en studiegenoten graag vermelden. Zonder hen hadden we met moeite het einde van dit semester gehaald: hun vriendschap, steun, begrip, humor iv
en zelfs hun eigen thesiszorgen maakten dit laatste semester van onze master en onze studietijd aan de UGent tot een onvergetelijke ervaring. Van deze vrienden willen we in het bijzonder Delphine Vandendriessche en Ruben Gryp bedanken. Zij bekeken deze thesis met een kritisch oog en gaven ons waardevol advies.
Marie Tack en Lieze Verdonck, mei 2014
Toelating tot bruikleen
Ondergetekende verklaart dat de inhoud van deze masterproef mag geraadpleegd en/of gereproduceerd worden, mits bronvermelding.
Marie Tack en Lieze Verdonck, mei 2014
vi
Inhoudsopgave Voorwoord
iv
Toelating tot bruikleen
vi
Gebruikte afkortingen
xi
I Inleiding en probleemstelling
1
1 Inleiding
2
1.1
TransWest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.2
Sectorgrootte
5
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 Probleemde nitie
10
2.1
Objectieven
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.2
Beperkingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.2.1
TransWest-speci eke beperkingen . . . . . . . . . . . . . . . . . . .
14
2.2.2
EG-verordening 561/2006
. . . . . . . . . . . . . . . . . . . . . . .
17
2.2.3
Overige beperkingen
. . . . . . . . . . . . . . . . . . . . . . . . . .
18
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
2.3
Overzicht
2.4
Oplossingen en methoden
. . . . . . . . . . . . . . . . . . . . . . . . . . .
3 Dataset
23
26
vii
4 Bedenkingen en verder verloop
28
II Oplossingsmethoden: modellen en resultaten
31
5 Input data
32
5.1
Orderlijst en capaciteitsmatrix . . . . . . . . . . . . . . . . . . . . . . . . .
33
5.2
Afstandsmatrix
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
5.3
Tijdsmatrix
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
5.4
Pre-processing voor exacte methode . . . . . . . . . . . . . . . . . . . . . .
35
6 Rittenplanning: TransWest
38
6.1
Orders met losadres TransWest weggelaten . . . . . . . . . . . . . . . . . .
38
6.2
Orders met losadres TransWest omgedraaid
39
. . . . . . . . . . . . . . . . .
7 Rittenplanning: constructieve heuristiek
40
7.1
Variabelen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
7.2
Model
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
7.3
Resultaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
7.3.1
Orders met losadres TransWest weggelaten . . . . . . . . . . . . . .
49
7.3.2
Orders met losadres TransWest omgedraaid
. . . . . . . . . . . . .
49
7.3.3
Combineren van korte ritten . . . . . . . . . . . . . . . . . . . . . .
50
8 Rittenplanning: mixed integer linear programming 8.1
8.2
Beperkt model
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.1.1
Beslissingsvariabelen
8.1.2
Parameters
8.1.3
Objective function
8.1.4
Constraints
8.1.5
52 52
. . . . . . . . . . . . . . . . . . . . . . . . . .
52
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
. . . . . . . . . . . . . . . . . . . . . . . . . . .
53
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
Resultaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
Uitgebreid model: Gurobi 5.6.2
. . . . . . . . . . . . . . . . . . . . . . . .
57
8.2.1
Beslissingsvariabelen
. . . . . . . . . . . . . . . . . . . . . . . . . .
57
8.2.2
Objective function
. . . . . . . . . . . . . . . . . . . . . . . . . . .
58
8.2.3
Constraints
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
8.2.4
CPU-tijd verlagende maatregelen
. . . . . . . . . . . . . . . . . . .
64
8.2.5
Resultaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
9 Personeelstoewijzing: binary integer linear programming
75
9.1
Scorematrix
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
75
9.2
Optimalisatie toewijzing personeel aan ritten . . . . . . . . . . . . . . . . .
78
9.2.1
Beslissingsvariabelen
. . . . . . . . . . . . . . . . . . . . . . . . . .
78
9.2.2
Objective function
. . . . . . . . . . . . . . . . . . . . . . . . . . .
78
9.2.3
Constraints
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
78
9.2.4
Resultaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
79
10 Resultatenvergelijking
82
III Conclusie en verder onderzoek
90
11 Conclusie
91
12 Verder onderzoek
94
Appendices
96
A Rij- en rustverordeningen
97
A.1
Begrippen
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.2
EG verordening 561/2006
. . . . . . . . . . . . . . . . . . . . . . . . . . .
97 98
B Berekening factor f
100
C Rittenplanning door TransWest
102
C.1
Overzicht rittenplanning
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
102
Hoofdstuk 0. Toelating tot bruikleen
D Heuristieken
106
D.1
Flow charts
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
D.2
Overzicht rittenplanning
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
106 113
E Exacte methode
118
F Personeeltoewijzing
122
Bibliogra e
126
L¼st van guren
129
L¼st van tabellen
130
x
Gebruikte afkortingen BILP
Binary Integer Linear Programming
CPU
Central processing unit
EU-TDSP
European Union Truck Driver Scheduling Problem
DP
Dynamic Programming
IP
Integer Programming
ILP
Integer Linear Programming
LP
Linear Programming
MDVCSP
Integrated Vehicle Crew Scheduling Problem with Multiple Depots
MILP
Mixed-Integer Linear Programming
MIP
Mixed-Integer Programming
NSP
Nurse Scheduling Problem
TDSP
Truck Driver Scheduling Problem
VDO
Vehicle Departure Optimization
VRP
Vehicle Routing Problem
VRPTW
Vehicle Routing Problem with Time Windows
VCRP
Vehicle-Crew-Rostering Problem
VCSP
Vehicle-Crew-Scheduling Problem
xi
Deel I Inleiding en probleemstelling
1
1 | Inleiding Personeelsplanning wordt door Ernst et al. [2] omschreven als het opstellen van geoptimaliseerde uurroosters voor personeel, dit met de bedoeling te voldoen aan de vraag van de klanten. Algemeen gezien omvat het planningsprobleem het toewijzen van geschikt personeel met het doel te voldoen aan een tijdsafhankelijke vraag voor verschillende diensten, rekening houdend met industriële arbeidsovereenkomsten en individuele preferenties.
In deze masterproef ligt de focus niet op het plannen van vrachtwagenpersoneel an sich, maar eerder op het
Vehicle Routing Problem
Samen vormen deze 2 delen het
dat deze personeelstoewijzing voorafgaat.
Truck Driver Scheduling Problem (TDSP).
Goel en Kok
[6] de niëren het TDSP als het probleem waarbij men rij-, werk-, break-, en rustperiodes op zo'n manier plant dat alle locaties bezocht zijn binnen een bepaalde tijdspanne en dat rij- en werkuren van de vrachtwagenchaueurs voldoen aan de relevante wetgeving. Aangezien deze case study een Belgisch bedrijf betreft, kan deze term uitgebreid, of beter, beperkt worden tot
The European Union Truck Driver Scheduling Problem (EU-TDSP).
Goel [5] de nieert dit vraagstuk als het probleem van het bepalen of rij- en werkuren van een vrachtwagenchaueur op zo'n manier kunnen worden gepland dat alle locaties bezocht worden binnen de opgegeven termijn en dat aan de EG-verordening 561/2006 voldaan is.
2
Hoofdstuk 1. Inleiding 1.1
TransWest
Het onderwerp van deze case study is het West-Vlaamse transportbedrijf TransWest, gelegen te Oostkamp. Het bedrijf heeft 170 werknemers in dienst, waarvan 85 chaueurs, en draaide in 2012 een kleine 35 miljoen euro omzet. TransWest is actief in de diepvrieslogistiek (85% van hun omzet) en diepvriesstockage (15%). Algemeen gezien kan gesteld worden dat de diepvriessector in België ten opzichte van de algemene economie een acyclisch gegeven is en een constante vraag kent, onder andere omdat het om een basisproduct gaat met geringe prijselasticiteit. Sommige productgroepen die TransWest vervoert kennen echter een cyclische vraag, neem bijvoorbeeld de vraag naar ijs in de zomer en kerststronken in de winter. De pieken in de vraag naar deze producten zijn evenwel niet van een zodanig grote orde en middelen elkaar als het ware uit.
De transportactiviteit van TransWest is op te delen in drie soorten:
1.
Volle ladingtransport: Bij dit soort transport benut men met behulp van één order de volledige capaciteit van de vrachtwagen (33 europaletten). Deze ritten kunnen als bestemming België, Frankrijk en Duitsland hebben.
2.
Groupagetransport:
Bij dit soort transport zijn de orders op zich te klein om
de capaciteit van de vrachtwagen volledig te benutten.
Daarom zal men trachten
de orders zo te combineren dat de ladingen zo dicht mogelijk bij een capaciteit van 100% aanleunen. Deze orders worden eerst allemaal opgelijst, daarna kan men orders met een gelijkaardige bestemming groeperen tot een volledig benutte capaciteit wordt bekomen. Binnen dit type transport maakt TransWest nog een onderverdeling gebaseerd op de plaats van het inladen van de te vervoeren goederen.
Een eerste mogelijkheid is om een volle lading goederen af te halen bij de klant. Deze worden dan in een buerstock geplaatst in de daarvoor voorziene stockageplaatsen van TransWest te Oostkamp. Als er later een order voor de des-
3
Hoofdstuk 1. Inleiding betreende goederen binnenkomt kan men deze rechtstreeks uit de buerstock halen.
Een alternatief hiervoor is
cross-docking
waarbij men de goederen van een in-
komende vrachtwagen direct overlaadt naar de daarvoor voorziene uitrijdende vrachtwagen.
Bij TransWest maken beide manieren van laden respectievelijk ongeveer 1/3 en 2/3 van het totaal aantal groupageritten uit. Voor de klant is
cross-docking
echter een
nogal dure aangelegenheid. TransWest komt de groupagelading halen bij de klant die de opdracht voor deze verzending gegeven heeft. Daarna stockeren werknemers een deel van de lading in TransWest of laden ze in koelwagens en worden deze uitgevoerd naar de gewenste bestemming. De afhalingen van de verzendingen bij de klant zijn duur want meestal vullen deze geen volle lading.
De klant moet voor deze dienst
evenwel de prijs van een volle lading betalen. Een goedkopere optie voor de klant is dus om TransWest volle ladingen te laten afhalen, deze te laten stockeren in het homedepot te Oostkamp en dan hun bestellingen voor de gewenste bestemming door te geven aan TransWest.
3.
Distributierondes:
Dit type transport is beperkt tot de landsgrenzen.
Met alle
klanten van deze distributierondes wordt er jaarlijks een contract opgesteld. Hierin wordt vastgelegd dat gedurende het volgende jaar elke week verschillende rondes worden afgelegd die bestaan uit meerdere haltes waar men een deel van de lading a evert.
Tijdens dat jaar worden er dan wekelijks orders doorgegeven die volgens
een vast routepatroon geleverd worden.
In deze case study hebben wij ervoor gekozen om te focussen op het nationaal volle ladingen groupagetransport. Hier slaat nationaal niet zozeer op de afbakening door de landsgrenzen dan wel op het feit dat de chaueurs die deze ritten a eggen dagelijks thuis overnachten of met uitzondering maximaal één overnachting in de rit opnemen.
4
Hoofdstuk 1. Inleiding 1.2
Sectorgrootte
Om het belang van de nationale distributie in de koeltransportsector aan te tonen, kan beroep worden gedaan op cijfers van de Belgische Federale Overheid [17] en van het Instituut wegTransport en Logistiek België (ITLB) [23]. Een eerste opmerkelijke vaststelling is dat de voorbije tien jaar het aantal ondernemingen en het aantal motorvoertuigen in de transportsector geen grote evoluties kenden en in 2013 stagneerden op een niveau van respectievelijk
8 548
en
54 004
in België.
Daarnaast is het gros van de transportbedrij-
ven in België geconcentreerd in de provincie West-Vlaanderen (19,83%) met een gedeelde tweede plaats voor Oost-Vlaanderen en Antwerpen (16,96%). Ten derde blijkt dat TransWest, dat in totaal 172 opleggers gebruikt, zich tot de grootste transport rma's van het land mag rekenen daar slechts 1,3% van de Belgische transportondernemingen meer dan 50 motorvoertuigen bezit.
In wat volgt wordt de focus van deze case studie, het nationaal volle lading- en groupagetransport van TransWest, gesitueerd binnen de Belgische transportsector aan de hand van data van de Belgische Federale Overheid [17] en van het Instituut wegTransport en Logistiek België (ITLB) [23].
Zoals gezegd heeft Transwest in totaal 172 opleggers ter
beschikking. Deze worden voor de nationale distributie gekoppeld aan 34 trekkers. Zoals in tabel 1.1 te zien is, is dit een veel gebruikt systeem.
5
Hoofdstuk 1. Inleiding Vrachtwagen Jaren
Met platte Gesloten
Afgedekte
Tankwagen
Met
Koelwagen opbouw
Voeding
Niet-voeding
laadbak
Totaal Overige
Trekker
Vervoerde hoeveelheden (in 1000 T)
2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011
Tabel 1.1:
14.366
6.939
30.022
2.970
1.311
6.178
31.195
25.563
267.836
386.380
14.209
6.996
28.158
2.995
828
5.250
32.800
25.877
280.178
397.291
14.611
6.617
26.010
2.907
806
4.306
25.424
22.585
274.894
378.160
15.191
5.485
11.571
2.298
836
3.384
21.217
17.413
269.293
346.689
14.611
4.853
19.099
2.140
554
3.523
17.561
13.901
261.620
337.863
13.383
4.597
19.411
2.096
386
2.838
16.884
12.576
276.282
348.453
11.861
3.908
35.413
2.400
291
2.251
13.775
9.601
272.632
352.132
6.629
3.408
5.941
1.580
180
2.842
10.659
8.151
278.209
317.599
7.489
2.432
10.140
1.597
271
2.891
8.755
6.593
257.656
297.824
6.261
2.205
19.065
1.039
85
2.386
7.449
4.458
253.200
296.149
7.804
1.899
3.495
1.246
162
1.727
7.399
4.988
260.420
289.140
2.7%
0.66%
1.21%
0.43%
0.06%
0.60%
2.56%
1.73% 90.10% 100.00%
Binnenlands en internationaal vervoer voor eigen rekening en voor rekening van derden
In tabel 1.2 is terug te vinden dat, wat de goederen betreft die vervoerd worden over de Belgische wegen, de voedings- en genotmiddelen, meer bepaald de categorie waarin diepvriesvoeding thuishoort, de tweede plaats innemen.
Vervoerde hoeveelheden 01 02 03
04 05 06 07 08 09 10
Producten van de landbouw, de jacht en de bosbouw; vis en visserijproducten. Steenkool en bruinkool; ruwe aardolie en aardgas. Metaalertsen en andere delfstoen; turf; uranium en thorium.
Voedings- en genotmiddelen.
Textiel en textielproducten; leder en lederwaren. Hout, hout- en kurkwaren (exclusief meubelen); vlechtwerk; pulp, papier en papierwaren; drukwerk en opgenomen media. Cokes en gera neerde aardolieproducten. Chemische producten en synthetische of kunstmatige vezels; producten van rubber of kunststof; splijt- en kweekstoen. Overige niet-metaalhoudende minerale producten. Metalen in primaire vorm; producten van metaal, andere dan machines en apparaten. 6
(in 1000 T) (in %) 16.774
5,8
481 73.785
0,2 25,5
43.872
15,2
16.315
5,6
12.714
4,4
23.056
8,0
35.372
12,2
13.438
4,6
1.824
0,6
Hoofdstuk 1. Inleiding
Vervoerde hoeveelheden 11
12 13 14 15 16 17
18
19 20 TOTAAL
Machines, apparaten en werktuigen, n.e.g.(*); kantoormachines en computers; elektrische machines en apparaten, n.e.g.(*); radio-, televisie- en telecommunicatieapparatuur; medische apparatuur en instrumenten, precisie- en optische instrumenten; uurwerken. Transportmiddelen. Meubelen; overige goederen en producten, n.e.g.(*). Secundaire grondstoen; gemeentelijk afval en overig afval. Brieven, pakketten. Uitrusting en materiaal voor het vervoer van goederen. Verhuisgoederen; niet door reiziger begeleide bagage; voor reparatiedoeleinden vervoerde voertuigen; overige niet voor de markt bestemde goederen,n.e.g.(*). Gegroepeerde goederen: diverse soorten goederen die gezamenlijk worden vervoerd. Niet-identi ceerbare goederen: goederen die om de een of andere reden niet te identi ceren zijn en daarom ook niet in de groepen 01-16 kunnen worden ingedeeld. Overige goederen, n.e.g.(*).
(in 1000 T) (in %) 5.325
1,8
1.058 4.278 5.010 7 2.999
0,4 1,5 1,7 0,0 1,0
892
0,3
11.703
4,0
14.645
5,1
5.590 28.9140 Tabel 1.2: Indeling van het totaal vervoer (binnenlands + internationaal) per hoofdstuk van de eenvormige goederennaamlijst voor de vervoerstatistieken (NST2007) - Jaar 2011
1,9 100,0
Als met behulp van tabel 1.3 de gangbare vervoerswijzen in België vergeleken worden, is duidelijk dat wegvervoer het meest voorkomt, in tegenstelling tot binnenscheepvaart en spoorvervoer.
Zoals eerder vermeld wordt in deze gevallenstudie zowel het vervoer van volle ladingen, wat in de onderstaande tabel 1.4 overeenkomt met Ophalingen en/of a everingen als de gegroepeerde transporten: Groupage bestudeert.
7
Hoofdstuk 1. Inleiding
1 000 T Absolute cijfers
%
2008
2009
2010
2008
2009
2010
259.649
243.144
252.356
81,3
83,5
.
Aanvoer (*)
81.487
74.724
76.382
54,4
57,7
.
Uitvoer (*)
94.686
84.828
87.560
65,0
68,8
.
Doorvoer zonder overlading (*)
42.229
37.260
46.467
77,5
82,0
.
478.051
439.956
462.765
71,4
74,6
.
Binnenlands vervoer
36.772
33.662
.
11,5
12,0
.
Aanvoer
53.472
44.196
.
35,7
34,1
.
Uitvoer
29.943
23.530
.
20,6
19,1
.
Doorvoer zonder overlading
10.163
6.854
.
18,6
15,1
.
130.350
108.242
.
19,5
18,4
.
Binnenlands vervoer
22.768
14.337
16.387
7,1
4,9
.
Aanvoer
14.902
10.601
10.986
9,9
8,2
.
Uitvoer
21.062
14.939
15.076
14,5
12,1
.
2.110
1.303
1.331
3,9
2,9
.
60.842
41.180
43.780
9,1
7,0
.
Binnenlands vervoer
319.189
291.143
.
47,7
49,4
.
Aanvoer
149.861
129.521
.
22,4
22,0
.
Uitvoer
145.691
123.297
.
21,8
20,9
.
54.502
45.417
.
8,1
7,7
.
669.243
589.378
.
100,0
100,0
.
Wegvervoer Binnenlands vervoer
Totaal
Binnenscheepvaart (1)
Totaal
Spoorvervoer
Doorvoer zonder overlading Totaal
Algemeen totaal
Doorvoer zonder overlading Totaal
Tabel 1.3:
Vergelijking van de hoeveelheden vervoerde goederen door Belgische en vreemde voertuigen en van de in België gepresteerde tonkilometer voor de belangrijkste wijzen van vervoer. Jaren 2008, 2009, 2010
8
Hoofdstuk 1. Inleiding
Soort van voertuigen
Ophaling en/of
Groupage
A everingen
Pendel-
Gecombineerd
Gecombineerd
Gewoon
reizen
spoorweg
zeeweg
traject
Totaal
C. Voor eigen rekening en voor rekening van derden (in 1 000 T) 1
Gesloten vrachtwagen
816
3.683
535
-
-
2.612
7.645
2
Afgedekte vrachtwagen
352
754
66
-
-
483
1.655
3
Vrachtwagen met platte opbouw
682
780
583
-
-
1.261
3.305
4
Koelwagen
185
640
3
-
-
345
1.172
5
Tankwagen voeding
8
95
3
-
-
35
141
6
Tankwagen niet voeding
545
738
27
-
-
409
1.719
7
Vrachtwagen met kipbak
270
516
4.148
-
-
2.275
7.209
8
Overige vrachtwagens
632
732
1.265
-
-
2.117
4.747
9
Trekkers
4.787
33.644
80.320
1
-
87.320
206.071
Totaal
8.275
41.582
86.949
1
-
96.856
233.663
Tabel 1.4:
Indeling van het vervoer in 1 000 ton en in 1 000 tonkilometer volgens de soort van voertuigen en de aard van het vervoer - Jaar 2011
9
2 | Probleemde nitie Uit de situering van TransWest ten opzichte van zijn sector blijkt dat het een groot transportbedrijf betreft waarvoor een nauwkeurige planning onontbeerlijk is.
De planners van de nationale ritten binnen TransWest combineren het gebruik van een
track-and-trace trace
systeem en een softwarepakket op een intuïtieve manier.
Dit
track-and-
systeem is via de boordcomputersoftware aanwezig in iedere vrachtwagen. Daarnaast
wordt de software
Chainware ®
van
Meer bepaald worden de orders in
Kewill
als beslissingsondersteunende tool gebruikt.
Chainware ®
ingegeven en het programma geeft de
facturatie van de orders en een gedeeltelijke planning terug die aan bepaalde (maar niet alle) voorwaarden voldoet. Een overzicht van de aanpak van het planningsdepartement binnen TransWest is terug te vinden in guur 2.1.
10
Hoofdstuk 2. Probleemde nitie
Figuur 2.1:
Plannen van nationale ritten in TransWest
Eerst wordt een lijst opgesteld van alle trekkers die ter beschikking zijn in het binnenland. Aan die trekkers worden dan chaueurs toegewezen.
Daarna worden de groupageritten
samengesteld en chaueurs aan deze ritten toegekend, dit o.b.v.
capaciteit en individu-
ele preferenties op vlak van elk type rit (groupage of volle vracht), tijdstip van de rit en talenkennis van de chaueur. Chaueurs die daarna overblijven, verkiezen om geen groupageritten te doen en worden toegewezen aan ritten die slechts één bestemming (een volle lading) hebben.
2.1
Objectieven
TransWest streeft er in het algemeen naar de opbrengst per kilometer zo hoog mogelijk te houden. Dit realiseren ze door het minimaliseren van de afgelegde afstand in balans te brengen met het minimaliseren van de duty time. Indien er zich bijvoorbeeld op de route van een chaueur een le of ongeval voordoet, beslist de chaueur zelf om om te rijden en het drukke verkeer te vermijden. Dit doet de afgelegde afstand stijgen maar verkleint
11
Hoofdstuk 2. Probleemde nitie evenwel zijn duty time en zorgt ervoor dat de chaueur nog binnen de vooropgestelde time windows kan leveren bij de klant. Zoals duidelijk uit bovenstaand voorbeeld blijkt , wordt bij TransWest veel in real time beslist en verschilt het evenwicht tussen het afstands- en duty time-objectief van rit tot rit. In de literatuur wordt deze afweging ook gemaakt. Onder andere in het artikel van Kok
Vehicle Routing Problem
et al. [14] wordt vermeld dat in het onderzoek naar VRP-TW (
with Time Windows ) de heuristische oplossingsmethoden meestal een doelfunctie gebruiken waarin het eerste objectief het minimaliseren van het aantal gebruikte voertuigen is en het tweede objectief het minimaliseren van de totale afgelegde afstand is. Niettemin kan dit tweede objectief tot lange wachttijden leiden door les omdat men door de kortste afstand ook de leknooppunten opzoekt.
Dit zorgt ervoor dat reistijden en dus de kosten van
de reis afhankelijk zijn van het tijdstip waarop men rijdt, en dit terwijl de afstand gelijk blijft. Daarom evalueren Kok et al. de kost van verschillende states (paden die beginnen bij de eerste node en daarna alle opgegeven nodes a eggen) op twee vlakken: het aantal vrachtwagens dat gebruikt werd en de totale duty time. States worden dus enkel vergeleken op het tweede vlak als ze gelijk zijn met betrekking tot het eerste.
Daarnaast onderzoeken de auteurs ook de invloed van die tijdsafhankelijke reistijden. Ze baseren zich hiervoor op Figliozzi [3] die zich op zijn beurt gebaseerd heeft op Solomon [20].
De uren gedurende dewelke een chaueur rijdt worden hier in 5 gelijke tijdsinter-
vallen opgedeeld.
Elk tijdsinterval heeft een bepaalde snelheid die afhankelijk is van de
verkeersdrukte op dat moment. Het eerste en het laatste tijdsinterval stellen de ochtenden avondspits voor en hebben dus de laagste snelheid. Om het voordeel van voor en na de ochtend- en avondpiek te rijden aan te tonen, breiden ze het interval twee uur voor en na de ochtend- en avondpiek uit. Gedurende deze intervallen bedraagt de snelheid de maximumsnelheid van dat patroon. Op deze manier ontwerpen ze 4 verschillende patronen met verschillende snelheden. Kok et al. voegen 1 snelheidspatroon toe waarin de snelheden doorheen de dag constant zijn en passen de patronen aan aan de EG-verordeningen.
Ook Steinzen et al. [21] incorporeren duty time: zij minimaliseren transport- en personeel-
12
Hoofdstuk 2. Probleemde nitie kosten in hun mathematisch model. Deze zijn, zoals hierboven, afhankelijk van respectievelijk rijtijden en idle times.
De vaststelling van Jütte et al. [12] dat personeelskosten een heel groot aandeel hebben in de operationele kosten, bevestigt dat de bijvoeging van het duty time-objectief economisch relevant is.
Het zou dus interessant zijn voor TransWest om in de planning niet enkel te focussen op het minimaliseren van afstand, maar ook rekening te houden met de personeelskosten. Een mogelijkheid is om meer aandacht aan de totale rijtijd te schenken. Een andere optie ligt in het minimaliseren van het aantal ritten door de capaciteitsbezetting per vrachtwagen zo hoog mogelijk te houden. Het streven naar verschillende objectieven wordt mogelijk met een multi-objectief model, zoals Mesquita et al.[16] het voorstellen met hun
gramming
probleem: zij combineren de optimalisatie-objectieven van
crew scheduling scheduling
Three-Objective Binary Non-Linear Pro-
en
crew rostering.
vehicle scheduling,
Respectievelijk minimaliseren ze de
vehicle-
en
crew
kosten, het aantal chaueurs dat toegewezen is en de maximale overtijd per
chaueur gedurende de planningsperiode in één mathematische uitdrukking. Het gebruik van dergelijke formulatie heeft als gevolg dat de oplossingsmethode zeer groot en complex wordt. Daarom lossen de auteurs het probleem eerst per dag op en voegen deze uitkomsten daarna samen om een planningsschema voor de gehele tijdshorizon te bepalen.
Een derde objectief dat TransWest nastreeft is het vermijden van lege kilometers. In de literatuur wordt hier naar verwezen als
deadhead trips.
Dit zijn de afstanden gedurende
dewelke een chaueur met een lege vrachtwagen rijdt en dus geen waarde creëert. Meestal wordt deze afgelegd tussen het laatste losadres en het depot te Oostkamp.
TransWest
tracht deze afstand te minimaliseren door ervoor te zorgen dat een vrachtwagen altijd een retourlading meeneemt die gestockeerd wordt in het depot te Oostkamp. Mesquita et al. [16] onderscheiden 3 soorten
deadhead trips :
ritten tussen de eindlocatie
van een trip en de beginlocatie van de volgende trip, van het depot naar de startlocatie van
13
Hoofdstuk 2. Probleemde nitie een trip (
pull-out trips ) en van een eindlocatie van een trip naar het depot (pull-in trips ).
Dit is een concept dat Jütte et al. [12] ook behandelen. Voor het optimaliseren van de personeelsplanning voor het vrachtvervoer door treinen bij DB Schenker in Duitsland implementeren zij een
Column Generation Based
optimalisatie. In de
Duty-Generation
fase
bakenen ze feasible paden met duties, die de kost van het huidige schema verbeteren, af. Hiervoor gebruiken Jütte et al. een
Resource-Constrained Shortest Path
bij stoten zij op een groot aantal potentiële
deadhead arcs :
algoritme. Daar-
de afstand afgelegd tussen de
beginhalte en de eerste halte bij het begin van een route, en de afstand die het treinstel a egt wanneer het wordt geparkeerd en dus geen lading vervoert. Om dit aantal te reduceren, berekenen de auteurs wat de bijdrage is van elke de kost van een duty. De
deadhead arc
deadhead arc
tot te verbetering van
wordt dan opgenomen in het netwerk als hij duties
kan produceren die het huidige schema verbeteren. Daarna volgt de
Master Solving
fase
waar de set duties met minimale kost uit de in de vorige fase gegenereerde duties wordt gekozen, zodat alle trips opgenomen worden terwijl de capaciteitsrestricties voldaan zijn.
2.2
Beperkingen
2.2.1 TransWest-speci eke beperkingen De beperkingen die voorkomen tijdens het plannen van de ritten van TransWest hebben betrekking op de capaciteit en preferenties van het personeelbestand, de beschikbare vrachtwagens en kenmerken van de klant.
2.2.1.1 Personeel Onder capaciteit van het personeel valt uiteraard het aantal beschikbare chaueurs voor de nationale distributieritten. Deze de nitie kan nog ver jnd worden door volgende aspec-
14
Hoofdstuk 2. Probleemde nitie ten:
Ten eerste hebben de chaueurs van TransWest de mogelijkheid voltijds of deeltijds te werken. Onder deeltijds vallen vier vijfden en halftijds werken.
Daarnaast is het van belang te weten of een chaueur fysisch capabel is om bij de klant paletten te heen. Bepaalde types paletten worden namelijk geruild: wanneer een chaueur dus X aantal paletten van dat type afhaalt of levert bij een klant, is het de bedoeling om hetzelfde aantal paletten respectievelijk achter te laten of mee te nemen. Deze restrictie is dus gelinkt aan het soort paletten dat de chaueur vervoert.
Zoals in de inleidende beschrijving van TransWest te lezen staat, zijn de nationale distributieritten niet afgebakend door de landsgrenzen.
Een aantal bestemmingen
in Nederland en enkele departementen van Frankrijk worden ook opgenomen in de bestemmingen. Uit ervaring weten de planners van TransWest dat het e ciënter is aan deze Franse bestemmingen en de bestemmingen in het Franstalig deel van ons land een chaueur toe te wijzen die de taal machtig is. Daarom wordt ook de kennis van de Franse taal van een chaueur als beperking opgenomen.
Tenslotte wordt er ook een verschil gemaakt in chaueurs op basis van hun vaardigheid om bij moeilijk bereikbare klanten te leveren. De klantenbestemmingen krijgen een moeilijkheidsgraad toegekend, deze worden dan gelinkt aan de rijvaardigheid van de chaueurs.
Daarbij is het ook van groot belang voor TransWest om met de preferenties van het personeel rekening te houden.
Dit verhoogt de werktevredenheid en productiviteit van de
chaueurs.
Een eerste onderdeel van preferenties van het personeel betreft de bereidheid van de chaueur om te overnachten tijdens een rit. Door een overnachting in te plannen
15
Hoofdstuk 2. Probleemde nitie kunnen vele (lege) kilometers uitgespaard worden. Ook kunnen zo de dichtstbijzijnde buitenlandse bestemmingen zonder probleem bij de korte ritten worden opgenomen en vlot van hun bestellingen worden voorzien.
Jütte et al.
[12] houden bij het
optimaliseren van de treinpersoneelsplanning van DB Schenker rekening met deze
Triebfahrzeugführer-Einsatz-
onpopulaire manier van plannen: de T.E.O.-software (
Optimierung )
die zij gebruiken evalueert het eect van het al dan niet inplannen
van een overnachting tijdens een rit. Om deze overnachtingen te vermijden kennen ze er een penalty kost aan toe. Hieruit blijkt dat een planning zonder overnachtingen enkel bereikt kan worden met hoge bijkomende kosten. Het aantal duties met een overnachting kan echter wel verminderd worden tot een acceptabel niveau met enkel een relatief kleine kostenverhoging.
Daarom neemt DB Schenker nu een ge-
middelde penalty kost voor overnachtingen op in zijn berekeningen om een hogere aanvaardbaarheid bij personeelsleden te bereiken.
Ten tweede mogen chaueurs bij TransWest opgeven of ze ritten naar het buitenland willen uitvoeren.
Ook wordt rekening gehouden met de zogenoemde tijdspreferenties van chaueurs: sommigen willen op bepaalde dagen van de week op een ander moment beginnen of stoppen met werken dan andere dagen.
Tenslotte wordt de preferentie voor een bepaald type rit (volle ladingritten, groupagetransport of distributierondes) in aanmerking genomen.
2.2.1.2 Vrachtwagens Ook het aantal vrachtwagens dat beschikbaar is kan onderverdeeld worden o.b.v. de kenmerken van de opleggers die eraan gekoppeld worden:
Er bestaan drie groottes van opleggers: ze kunnen 33, 28 of 25 paletten bevatten.
16
Hoofdstuk 2. Probleemde nitie
De aan- of afwezigheid van een laadklep bij een vrachtwagen moet gekoppeld worden aan respectievelijk de af- of aanwezigheid van een laad- en loskaai bij de klant.
Daarnaast zijn er een aantal opleggers waar publiciteit voor een bepaalde klant op aangebracht is.
Deze worden bij voorkeur niet naar een concurrent van die klant
gestuurd.
2.2.1.3 Klanten Klanten worden ten eerste gekenmerkt door bepaalde openingsuren gedurende dewelke een vrachtwagen mag laden en lossen. TransWest hecht veel belang aan het nastreven van tijdige leveringen. Laattijdige leveringen schaden de relatie met de klant en brengen meestal hoge boetes met zich mee. Daarenboven loopt TransWest het risico dat de lading ronduit geweigerd wordt bij een laattijdige levering, hetgeen opnieuw kosten met zich meebrengt. Kok et al.
[14] kijken dit tijdig leveren op een eenvoudige manier na: ze gebruiken het
Restricted DP -raamwerk
van Gromicho et al. [7]. Aan de hand van dit raamwerk worden
klanten sequentieel toegevoegd aan het einde van partiële routes. De toevoeging van een klant vereist evenwel een feasibility check. Deze houdt o.a. het nagaan van een aankomst binnen de openingsuren van de klant in. De auteurs controleren dit door gebruik van extra
state dimensions. TransWest houdt ook rekening met de bereikbaarheid van de klant. Moeilijk bereikbare klanten worden toegewezen aan ervaren chaueurs die over voldoende rijvaardigheid beschikken. Tenslotte moeten klanten die niet over een laad- en loskaai beschikken, bezocht worden door opleggers waarbij een laadklep aanwezig is.
2.2.2 EG-verordening 561/2006 Naast de TransWest-speci eke beperkingen zijn er de algemene beperkingen die gelden voor de meeste transportbedrijven in de E.U. . Het zijn constraints die betrekking hebben
17
Hoofdstuk 2. Probleemde nitie op algemene planningsbeperkingen voor transportbedrijven, aangevuld met de wettelijk bepaalde rij- en rusttijden voor voertuigen die minstens 3,5 ton vervoeren en voertuigen die meer dan negen personen kunnen vervoeren (EG-verordening 561/2006). Deze verordening is opgenomen in Appendix A. Hieronder zal kort worden aangehaald met welke verordeningen TransWest speci ek rekening houdt bij de planning van ritten (andere verordeningen worden geacht door de chaueur zelf in rekening gebracht te worden):
Elke chaueur mag maximum 9 uur per dag rijden en om de 4,5 uur moet er een pauze van 45 minuten worden genomen.
Twee maal per week mag een chaueur tot 10 uur per dag rijden.
Een chaueur moet 9 uur nachtrust krijgen, 1 nacht op 4 moet hij 11 uur rust nemen.
Tijdens het weekend moet een chaueur 45 uur rust krijgen.
Kok et al. [14] stellen, zoals hierboven al werd vermeld, voor hun VRP-TW met een planningshorizon van één week een
Restricted DP -heuristiek
voor die voldoet aan de sociale
wetgeving van de E.G. . Deze overeenstemming met de wetgeving kan worden gecontroleerd door het toevoegen van state dimensions die verschillende parameters bijhouden: de werktijd sinds de laatste pauze van minstens 45 minuten, de rijtijd sinds de laatste pauze van minstens 45 minuten, de tijd sinds de laatste rustperiode van minstens 11 uur, de rijtijd sinds de laatste rustpauze van minstens 11 uur, de werktijd sinds de laatste rustperiode van minstens 45 uur en de rijtijd sinds de laatste rustperiode van minstens 45 uur. Een
Break Scheduling Method
plant dan deze door de wet opgelegde pauzes in tijdens de rit
naar of bij de klant zelf.
2.2.3 Overige beperkingen Kenmerken van personeel, vrachtwagens en klanten die niet aanwezig zijn bij TransWest, maar wel regelmatig voorkomen in de relevante literatuur, zijn de volgende.
18
Hoofdstuk 2. Probleemde nitie
2.2.3.1 Personeel Yu et al. [24] lichten toe hoe voor het plannen van piloten voor lijnvluchten van Continental Airlines de pilootposities worden bijgehouden. Deze beschrijven de geogra sche locatie waar een piloot zijn/haar trips begint en eindigt (de basis), het type vliegtuig waarmee de piloot vliegt (de vloot) en de status van de piloot in de cockpit (kapitein, eerste o cier of tweede o cier). De gewoonte van piloten om frequent hun positie aan te passen en de veranderingen in de klantvraag, marktmogelijkheden etc. doen evenwel de behoefte aan een oplossing die kan inspelen op deze voortdurende wijzigingen ontstaan. Deze oplossing wordt de
system bid award
genoemd: de vliegmaatschappij biedt posities
aan aan de piloten op basis van een voorspelde vraag, waarop de piloten de posities aanvragen die ze wensen. Tenslotte worden de posities toegekend naar gelang de anciënniteit van de piloot. Ook wanneer men bij sommige taken een tekort aan personeel heeft en dit wil opvullen door overtollige piloten van andere taken te transfereren, wordt rekening gehouden met anciënniteit. Opnieuw worden deze taken aangeboden en wanneer er genoeg vraag is naar de niet-ingevulde taken, worden ze ingevuld door piloten op basis van deze anciënniteit. Indien dit niet het geval is, wordt het omgekeerde toegepast: piloten worden toegewezen op basis van
reverse seniority.
De anciënniteit van een werknemer is een kenmerk waarmee bij TransWest slechts in beperkte mate rekening wordt gehouden.
Meer bepaald worden aan de nieuwe chaueurs
eenvoudigere ritten toegekend dan aan chaueurs die reeds over tientallen jaren ervaring beschikken. Deze keuze wordt deels gedreven door het doel om chaueurs op die manier op te leiden maar vooral door de inherente winst aan e ciëntie. Het is ingewikkeld om de moeilijkheidsgraad van de ritten en de anciënniteit van chaueurs af te bakenen en de lezer begrijpt dat de toekenning van de ritten op vlak van dit aspect op een intuïtieve manier gebeurt. Daarom wordt dit personeelskenmerk niet in de modellen van deze thesis opgenomen.
19
Hoofdstuk 2. Probleemde nitie Hierbij moet opgemerkt worden dat met de behendigheid van chaueurs om hun vrachtwagen te parkeren wel rekening wordt gehouden in deze thesis. Dit kenmerk wordt echter los gezien van anciënniteit.
Een tweede personeelskenmerk dat meermaals terug te vinden is in de literatuur, maar dat niet voorkomt in de probleemstelling van TransWest, is de aanwezigheid van werknemers met verschillende vaardigheden. Safaei et al. [19] verwerken deze constraint in hun model als volgt: het benodigde aantal werknemers met een bepaalde skill in elke periode mag niet groter zijn dan het beschikbare aantal werknemers met die skill. Voor de formulering van de constraint baseren de auteurs zich op het
knapsack
probleem: het totaal aantal benodigde werknemers dat is toegewezen
aan een job mag niet groter zijn dan de beschikbare capaciteit.
2.2.3.2 Klanten De klanten van TransWest die bediend worden door de nationale volle lading- en groupageritten kunnen typisch enkel gedurende de weekdagen bereikt worden. Chaueurs rusten 45 uur in het weekend, afgezien van de uitzonderingen die op zaterdag terugkeren omdat ze op vrijdagavond aan hun wettelijk rijtijdlimiet kwamen. In andere sectoren zoals vrachttreinvervoer [12] werkt men 24 uur per dag, 7 dagen op 7. Hier kunnen ritten dus niet opgedeeld worden als dagelijkse problemen. Daarnaast is het onmogelijk om de personeelsleden in te delen in verschillende groepen (bv. chaueurs die enkel lokale treinen bedienen en zij die met langeafstandstreinen rijden) om hen daarna sequentieel in te plannen.
2.3
Overzicht
In onderstaande tabel 2.1 wordt een overzicht gegeven van de objectieven en constraints gebruikt in de voor deze case studie relevante literatuur. Deze kunnen vergeleken worden met hoe de planning vandaag de dag gebeurt in TransWest.
20
Hoofdstuk 2. Probleemde nitie Zoals al eerder aangehaald komt de doelfunctie van het mathematisch model van een personeelsplanning vaak neer op het minimaliseren van een kostenfunctie. Daarin zitten dan het minimaliseren van de afstand, de diensttijd, het gebruikte aantal voertuigen en/of personeel. Minder vaak wordt niet naar het minimaliseren van kosten gestreefd dan wel naar het opstellen van een kwalitatief model dat geëvalueerd wordt op basis van de vervulling van arbeidswetgeving en de preferenties van het personeel. Deze streefdoelen worden voornamelijk ingesnoerd door capaciteitsconstraints, time windows en arbeidsreguleringen die uitgaan van de overheid en van het bedrijf zelf.
21
tijdens rit
ritten
buitenlandse
x
x
bereikbaarheid
laad-loskaai
→ →
meerdere depots
ow conservation
Wetgeving en bedrijfsregelement Planning
x
x
x
time windows
→ → →
Klanten
x
x
x
depot
voertuigen
heterogene
→
−→
x
x
x
x
x
x
x
overnachten
x
rijvaardigheid
x
x
talenkennis
capaciteit
fysische
part time
full time/
−→ time preferences −→ rittype → voertuigen −→ voertuiggrootte −→ laadbrug
−→
−→
−→ −→
−→
−→
personeel
x
x
x
x
x
x
Tabel 2.1:
x
x
x
x
A time-space E cient
drivers in the
x
x
x
x
x
x
x
Steinzen et al.
x
x
x
Goel en Kok
European Union
VCSP with multiple depots
team truck
scheduling of
for the integrated
network approach
Optimizing
x
x
x
x
x
x
Yu et al.
airlines
for continental
and training
pilot planning
Optimizing
x
x
x
x
x
x
x
x
Jütte et al.
DB Schenker
scheduling at
railway crew
Scheduling
x
x
Cohn et al.
of Medicine
University School
at Boston
medical residents
Truck driver scheduling in
x
x
iteratief
Goel
Union
the European
Overzicht objectieven en constraints relevante literatuur
x
x
x
x
x
x
idle time
x
x
overuren
Capaciteit
→
x
x
x
x
x
x
x
# voertuigen
x
lege kilometers
breaks Mesquita et al.
computational study on rosters
and required
Kok et al.
and a
travel times
for the
for VRP with
x
x
diensttijd
x
x
Kok et al.
legislation
EC social
VRPTW and
A new model integrated VCRP
A DP heuristic time-dependent
# chaueurs
x
x
TransWest
afstand
Constraints
→ → → → → → →
Min. Kost
Objectief
Auteur
Paper
A DP
heuristic for
Vehicle
x
x
recursief
Goel
working hours
drivers'
routing with
scheduling and
x
x
x
x
x
Safaei et al.
a case study
aircraft eet:
scheduling for military
maintenance
Workforce-constrained
Hoofdstuk 2. Probleemde nitie 2.4
Oplossingen en methoden
Na het opstellen van een al dan niet mathematisch model van de case, gaat men over tot de implementatie van de oplossingsmethode.
Zoals in de inleiding reeds werd aangegeven, worden in de literatuur tal van cases teruggevonden waar men tracht de doelfunctie op te lossen tot optimalisatie. Jütte et al. [12] genereren een schema voor personeel van vrachttreinen van DB Schenker tegen een minimale kost. Yu et al.
[24] ontwikkelden een geavanceerde oplossingsmethode voor een grootschalige
pilotenplanning bestaande uit twee fasen: in de eerste fase minimaliseren ze o.a. de kost van het aannemen en plaatsen van piloten, in de tweede fase minimaliseren ze de toekenningen van
training resources
en e ciënt gealloceerde
aan piloten. Dit resulteert dus in optimale pilotentransities
training resources.
Aangezien TransWest het programma
Chainware ® enkel als beslissingsondersteunende tool
gebruikt, wordt hun huidig planningsschema als een feasible oplossing gecategoriseerd. Mesquita et al. [16] stellen een
multi-objective
optimalisatieprobleem voor waarbij ze fea-
sible oplossingen willen bekomen. Ze doen dit door een hogere prioriteit te geven aan de objectieven van het
Integrated Vehicle-Crew-Scheduling Problem
aan de objectieven van het
en een lagere prioriteit
Driver Rostering Problem.
Goel en Kok [6] bestuderen een probleem dat gelijkaardig is aan dat van TransWest: zij vinden een feasible oplossing voor het e ciënt plannen van vrachtwagenchaueurs die in team rijden. Deze oplossing voldoet aan de standaard van dagelijkse rijtijdlimieten. Om deze feasible oplossing te bekomen, stellen ze eerst een pseudo-feasible schema op.
Dit
schema breidt de EG-verordening, die stelt dat een rustperiode van minstens 9 uur wordt genomen 30 uur na het einde van de vorige rustperiode, uit naar rustperiodes van meer dan 9 uur. Daarna passen ze dit schema aan totdat weer aan de EG-verordening voldaan is en dus een feasible oplossing is gevonden.
23
Hoofdstuk 2. Probleemde nitie Cohn et al. [1] kennen arts-assistenten toe aan vijf shifttypes voor drie verschillende ziekenhuizen over een tijdshorizon van 365 dagen. Ze doen dit door het formuleren van een
Mixed-Integer Feasibility
probleem dat voldoet aan alle
hard constraints.
Daarna overleg-
gen ze met het ziekenhuis om uiteindelijk een schema te genereren dat balanceert tussen de opgelegde constraints en aanvaardbaarheid voor het betrokken personeel.
De keuze voor één van bovenstaande oplossingsmethodes zal verschillen naargelang de complexiteit van het probleem, de uitvoering van het model, de tolerantie m.b.t. de CPUtijd en de gewenste oplossingskwaliteit. Duidelijk is dat een onderscheid kan worden gemaakt tussen exacte oplossingsmethoden en heuristische methodes. Hooker [9] stelt dat exacte methodes meestal de vorm aannemen van vertakkingsmethoden (bv.
Branch-and-bound ) of ander grondig onderzoek (LP, IP,. . . ).
Ze
worden toegepast op eenvoudige problemen [22] en geven een optimale oplossingskwaliteit. Heuristische methodes daarentegen zijn van een heel andere aard, bv. lokaal onderzoek,
Single-Pass
algoritmes of de imitatie van een natuurlijk proces zoals biologische evolutie [9]
Genetic Algorithm ) en worden toegepast op eenvoudige alsook complexe problemen.
(
Hier
zal nooit een optimale oplossing worden bereikt, maar dit kan echter afgewogen worden tegen de verminderde CPU-tijd. Zoals in onderstaande tabel te zien is, wordt deze afweging in de literatuur ook gemaakt. Men zal bv. de complexiteit van een werkelijke probleemstelling verminderen en een exacte methode toepassen om een optimale oplossing te bekomen.
24
Hoofdstuk 2. Probleemde nitie
Paper
Auteur
A DP heuristic for VHRPTW and
Oplossingsmethode Heuristiek Exacte methode
Probleem/Doel VRPTW
Restricted DP heuristic
Kok et al. EC social legislation Voldoen aan EG wetgeving
Break-scheduling method (basic and extended)
A DP heuristic for VRP with
Routes samenstellen
Restricted DP heuristic
Kok et al. time-dependent travel times
VDO probleem
and required A new model breaks for the integrated
Binary Non-Linear Mesquita et al.
VCRP and a computational
ILP
Sequentieel algoritme in een Multi-Objective Optimization Preemptive Goal Programming raamwerk
study on rosters
probleem MDVCSP: set kolommen en
A time-space network approach for Steinzen et al.
Lagrangian relaxation
lower bound voor objective
the integrated VCSP with multiple
function
depots
MDVCSP: een feasible integer
Integer Programming
solution bepalen Een planning die voldoet aan E cient scheduling of team truck
Goel en Kok
Depth- rst-breadth-second search de standaard dagelijkse
drivers in the European Union
algoritme rijtijd limieten vinden. Piloot training probleem:
Optimizing pilot planning and Yu et al. training for continental airlines
MIP
pilot-transitioning phase Piloot training probleem:
Branch-and-bound: depth- rst approach
Assignment probleem: MIP
training-class-scheduling phase Optimizing railway crew scheduling
Jütte et al.
Column-generation based optimization
Crew scheduling
at DB Schenker
software package
Scheduling medical residents at Boston University School of
Cohn et al.
NSP
Multiphased, interactive approach
Goel
EU-TDSP
Breadth- rst search
Goel
EU-TDSP
Large neighbourhood search algoritme
Safaei et al.
Time-indexed MIP
IP
Medicine Truck driver scheduling in the European Union Vehicle scheduling and routing with drivers' working hours Workforce-constrained maintenance scheduling for military aircraft eet:
Branch-and-bound
a case study
Tabel 2.2:
Overzicht oplossingsmethodes - onderscheid exact vs. heuristisch
25
3 | Dataset Om het probleem beschreven in deze thesis, het nationale volle lading- en groupagetransport van TransWest, te situeren op vlak van grootte van de dataset, wordt in onderstaande tabel een overzicht gegeven van de werkelijke data gebruikt in vergelijkbare case studies in de literatuur. Chaueurs /
Voertuigen
Voertuigtypes
Bestemmingen
Aantal ritten / dag
werknemers Safaei et al. ( 1st example )[19]
12
18
2
10
Safaei et al. ( 2nd example )[19]
12
24
2
15
Safaei et al. ( 3d example )[19]
16
40
2
20
TransWest: nationale ritten
47
34
8
485
Mesquita et al.[16]
50 122-238
Yu et al.[24]
4500
345
Jütte et al.[12]
3500
19000
Tabel 3.1:
4
1100 36000
Overzicht probleemgroottes relevante case studies
In theoretische papers werkt men niet met werkelijke datasets, maar zal men de ontwikkelde oplossingsmethoden meestal toetsen op test cases afgeleid van referentieproblemen die eerder werden voorgesteld door onderzoekers. De 56 benchmark-problemen van Solomon [20] vormen een voorbeeld van zo'n referenties die in de voor deze case study relevante literatuur terug te vinden zijn en zijn een standaard referentie in de VRP-literatuur. Ze zijn gebaseerd op zes groepen probleemklassen met 100 klanten.
Klantenlocaties worden willekeurig gegenereerd, geclusterd of bestaan
26
Hoofdstuk 3. Dataset uit een mix van willekeurig gegenereerde en geclusterde klantenbestemmingen. Een greep uit de auteurs die zich op Solomon gebaseerd hebben zijn: Figliozzi [3], Goel [4] en Kok et al. [14][15].
27
4 | Bedenkingen en verder verloop Uit de vergelijkende analyses van de probleemde nitie, de oplossingen, de oplossingsmethodes en de dataset kunnen volgende conclusies genomen worden met betrekking tot het verder verloop van deze thesis:
In de literatuur wordt vaak de afweging gemaakt tussen het minimaliseren van de afstand en het minimaliseren van de duty time.
Heuristische oplossingsmethoden
Vehicle Routing Problem with Time Windows ) gebruiken meestal
van het VRP-TW (
een doelfunctie waarin het eerste objectief het minimaliseren van het aantal gebruikte voertuigen is en het tweede objectief het minimaliseren van de totale afgelegde afstand is. Niettemin kan dit tweede objectief tot lange wachttijden leiden door les omdat men door de kortste afstand ook de leleknooppunten opzoekt. Daarom kan de kost van verschillende states op twee vlakken geëvalueerd worden: het aantal vrachtwagens dat gebruikt werd en de totale duty time.
Om duty time op een correcte manier te evalueren is het noodzakelijk rekening te houden met het eect van verkeersdrukte. Uit de analyse van deze gevallenstudie en de bijhorende literatuur komt voort dat verkeersdrukte een actueel probleem is in de transportsector. De invloed van deze verkeersdrukte op de reistijd kan nagegaan worden door tijdsafhankelijke reistijden in te voeren. Hiervoor kan met tijdsintervallen worden gewerkt waaraan, afhankelijk van het tijdstip, een snelheid wordt gekoppeld. Algemeen kan gesteld worden dat binnen België de verkeersdrukte ook plaatsafhankelijk is. Binnen de verschillende modellen in deze thesis zal de verkeersdrukte worden
28
Hoofdstuk 4. Bedenkingen en verder verloop opgenomen gebaseerd op de hierboven vermelde tijdsafhankelijke variabelen.
Voor het plannen binnen time windows vooropgesteld door klanten kan een
DP -framework gebruikt worden.
Restricted
Hier worden bestemmingen sequentieel toegevoegd
aan routes nadat de feasibility van de route werd gecheckt. Deze controle houdt in dat
state dimensions,
die het tijdstip van aankomst bij de klant bijhouden, binnen
de openingsuren moeten vallen. Daarnaast kunnen
state dimensions
ook toegepast worden om de gebruikte capaciteit
van een vrachtwagen (het aantal paletten dat geladen is verminderd met het aantal paletten dat gelost werd) en tijdsparameters bij te houden. gecombineerd worden met een
Break Scheduling Method
Deze laatste kunnen
om op die manier het volgen
van de wetgeving in verband met rij- en rusttijden te verzekeren.
Overnachtingen kunnen ingepland worden om zo lege kilometers te vermijden.
Er
kan hier een penalty kost aan worden toegekend zodat deze onpopulaire manier van plannen vermeden wordt en aanvaardbaar blijft voor het personeel.
De grootte van een dataset kan gekoppeld worden aan de keuze voor een exacte dan wel heuristische oplossingsmethode. Voor grote problemen met een uitgebreide dataset wordt vaak een heuristische methode gebruikt.
Wanneer men echter een
optimale oplossing wil bereiken, is een exacte methode voor de hand liggend. Ook kunnen exacte en heuristische methodes gecombineerd worden.
Na het bestuderen van de literatuur met betrekking tot personeelsplanning, en meer speci ek
Truck Driver Scheduling,
kan gesteld worden dat de probleemgrootte en complexiteit
van deze case study gemiddeld is in vergelijking met soortgelijke cases. Daarnaast is terug te vinden dat op het vlak van oplossingsmethoden vaak, voor zowel eenvoudige als complexe problemen, een combinatie van exacte en heuristische methoden worden gebruikt. Daarom zullen in wat volgt beide methodes toegepast worden op de case study. In hoofdstuk 5 worden eerst en vooral de verschillende invoergegevens afgeleid uit het probleem van de nationale volle lading- en groupageplanning van TransWest en worden deze
29
Hoofdstuk 4. Bedenkingen en verder verloop verder toegelicht.
Deze invoergegevens vormen de input voor elk van de oplossingsme-
thoden hierna besproken. Om te beginnen worden de planningsmethode en de resultaten van TransWest, het onderwerp van deze gevallenstudie, in hoofdstuk 6 aangehaald. Deze planningsmethode wordt ten eerste vergeleken met een constructieve heuristiek (hoofdstuk 7).
Daarenboven wordt een exacte methode uitgewerkt in hoofdstuk 8.
Meer bepaald
wordt een MILP opgesteld dat eerst in een beperkte vorm wordt opgelost met Excel en Gurobi 5.6.2. (sectie 8.1), daarna wordt in sectie 8.2 het uitgebreid model besproken en opgelost met Gurobi 5.6.2. . Voor elk van deze benaderingen worden de variabelen (7.1, 8.1.1 en 8.2.1), het model (7.2, 8.1.3 en 8.2.2) en de resultaten (7.3 en 8.2.5) overlopen. Vervolgens wordt in hoofdstuk 9 het tweede deel van het
blem,
Truck Driver Scheduling Pro-
i.e. de toewijzing van het personeel aan de ritten bekomen uit de planning van de
verschillende oplossingsmethodes, geoptimaliseerd.
In hoofdstuk 10 wordt tenslotte een
uitgebreide vergelijking over de verschillende oplossingsmethoden heen gemaakt.
30
Deel II Oplossingsmethoden: modellen en resultaten
31
5 | Input data Zowel de planning van TransWest zelf, als de verder besproken heuristische en exacte oplossingsmethodes, verwerken verschillende inputbestanden tot een planning voor het nationale transport, exclusief de distributierondes, van verschillende vrachtwagens over één dag.
Deze bestanden omvatten ten eerste een klantenlijst die de relevante klantenken-
merken weergeeft zoals de openingsuren, de aanwezigheid van een laad- en loskaai en de moeilijkheidsgraad van de parking voor elk van de 485 klanten. Daarnaast wordt ook een lijst ingelezen met voor elke klant de postcode en coördinaten van zijn locatie.
Om de toewijzing van de coördinaten aan alle klanten e ciënt te la-
ten verlopen werd volgende methode gebruikt. Aan elke klant worden coördinaatgegevens toegevoegd op basis van de postcode. Deze coördinaten werden geraadpleegd in een lijst met gps-coördinaten van Belgische steden [8]. De lezer merkt op dat de coördinaten die aan de klanten worden toegewezen niet overeenkomen met deze van hun exacte adres. Dit impliceert dat adressen met dezelfde postcode als eenzelfde locatie worden beschouwd. Tenslotte wordt een overzicht van de orders voor de nationale distributierondes, die op dat moment onuitgevoerd zijn, ingevoerd. Bij deze laatste wordt de dag dat het order werd vrijgegeven, de vervaldag, het laadadres, de losplaats en de laadindex meegegeven.
Een extra inputbestand met het aantal opleggers en hun speci eke info, zoals de maximale capaciteit, bijzondere publiciteitsopschriften, aan- of afwezigheid van een laadbrug, worden niet in de planning opgenomen. Dit omdat opleggers met een capaciteit verschillend
32
Hoofdstuk 5. Input data van 33 enkel worden gebruikt voor de nationale distributierondes, wat buiten de scope van deze thesis valt. In wat volgt zal dus elke planningsmethode ervan uitgaan dat er enkel standaard opleggers met een maximale capaciteit van 33 paletten beschikbaar zijn. Aangezien elke chaueur beschikt over een vaste trekker, wordt aangenomen dat er ook evenveel opleggers als chaueurs voor het nationaal volle lading- en groupagetransport beschikbaar zijn. Daarom worden in wat volgt de begrippen chaueurs en vrachtwagens dooreen. Deze integratie wordt in hoofdstuk 9, waar de personeelstoewijzing wordt uiteengezet, verder toegelicht.
5.1
Orderlijst en capaciteitsmatrix
De orderlijst is een werkelijke lijst waarop de planning voor de nationale distributieritten van TransWest voor één dag gebaseerd is. Deze bevat 170 orders. Vooraleer de oplossing van het heuristische en exacte programma met de resultaten van TransWest kan vergeleken worden, moet de inputdata van de orderlijst voorbereid worden met behulp van enkele lters. Zo wordt verondersteld dat alle te leveren goederen reeds in het diepvriesmagazijn van TransWest in Oostkamp aanwezig zijn. Hierdoor zullen tijdens iedere rit enkel ladingen gelost kunnen worden.
Dit in tegenstelling tot het werkelijke
probleem waar bij de klanten zowel wordt geladen als gelost. Deze veronderstelling kan op twee manieren worden doorgetrokken in de orderlijst:
Alle orders krijgen als laadadres het homedepot in Oostkamp toegewezen en de orders met losadres TransWest worden uit de orderlijst verwijderd.
Bij alle orders waarvan het losadres TransWest is, worden de laad- en losadressen omgedraaid. Dit houdt in dat deze als laadadres het homedepot in Oostkamp toegewezen krijgen, het nieuwe losadres wordt dan de klantenbestemming waar oorspronkelijk de lading opgepikt moest worden.
33
Hoofdstuk 5. Input data Beide orderlijsten zullen worden verwerkt door de drie planningsmethoden, i.e. de planning door TransWest, de constructieve heuristische planning en de exacte planning op basis van het MILP. De resultaten hiervan zijn terug te vinden in respectievelijk hoofdstuk 6 en in secties 7.3 en 8.2.5. Tenslotte zullen deze resultaten ook over de methodes heen vergeleken worden in hoofdstuk 10.
Uit deze orderlijsten wordt tenslotte een capaciteitsmatrix gegenereerd. Deze geeft voor alle klanten weer hoeveel paletten moeten worden gelost op de dag waarvoor wordt gepland. Voor klanten die niet opgenomen zijn in de orderlijst wordt een
5.2
0
opgenomen.
Afstandsmatrix
In de literatuur zijn verschillende methoden terug te vinden om de afstand tussen coördinaten te bepalen. Een eerste manier is om de euclidische afstand tussen de punten
(x1 , y1 ) en p2 = (x2 , y2 ) te berekenen.
De bijhorende formule
d=
p
p1 =
(x1 − x2 )2 + (y1 − y2 )2
neemt echter maar twee dimensies. Aangezien een correcte afstand in drie dimensies wordt berekend, wordt verder de Haversine formule gebruikt waarbij deze derde dimensie in kaart wordt gebracht [10]:
sin2 (∆ϕ/2)
a
=
c
= 2*arctan 2
d
=
cos(ϕ1 )*cos(ϕ2 )*sin2 (∆λ/2) √ p ( a, (1 − a)) +
R∗c
Hierbij stelt
ϕ
de breedtegraad voor,
= 6,371km) en
d
λ
de lengtegraad,
R
de aardstraal (gemiddelde straal
de afstand.
Met behulp van deze formulering kan bij het begin van het heuristische en exacte programma uit de coördinatenlijst een afstandsmatrix gegenereerd worden. Deze matrix bevat
n2
elementen, met
n
het aantal klanten, en geeft de rechtlijnige afstanden tussen alle
mogelijke combinaties van twee klanten uit
n.
34
Hoofdstuk 5. Input data 5.3
Tijdsmatrix
Vervolgens wordt uit de afstandsmatrix een tijdsmatrix gegenereerd met behulp van de volgende formule: (in minuten),
f
t=f
d s
met
t de tijd nodig om van de ene naar de andere klant te rijden
de factor die zorgt voor een aanpassing vanwege de niet rechtlijnige wegen,
d de rechtlijnige afstand als uitkomst van de Haversine formule (in km) en s de gemiddelde snelheid van een vrachtwagen (in km/minuut). Om de factor
f
te bepalen werden verschillende factorgroottes vermenigvuldigd met de
rechtlijnige afstand tussen een aantal steden die steekproefsgewijs geselecteerd werden. De bekomen waarden werden vergeleken met de reële afstand die men via autowegen a egt tussen de desbetreende steden.
Uiteindelijk werd de factor die de kleinste gemiddelde
afwijking ten opzichte van de reële afstand opleverde gekozen. Deze berekeningen werden in de Appendix B opgenomen, waar de lezer kan zien dat een waarde van vergrotingsfactor
f
1, 2
voor de
bekomen werd.
Naast de correctie voor de niet-rechtlijnige wegen, moet ook rekening gehouden worden met het feit dat de snelheid van een vrachtwagen wordt beïnvloed door de verkeersdrukte. Deze varieert van regio tot regio.
In onderstaande tabel 5.1 wordt een overzicht weergegeven
van de gemiddelde lefactor per gewest. Wanneer een vrachtwagen dan van klant A naar klant B rijdt, wordt
t
vermenigvuldigd met de gemiddelde lefactor van klant A en B.
Het incorporeren van deze lefactoren heeft als doel een realistische weergave van de rijtijd te bekomen om zo de totale rijtijd op een juiste manier te kunnen toetsen aan de toegelaten rijtijd en eventuele rusttijden in te plannen.
5.4
Pre-processing voor exacte methode
Vooraleer de orderlijst aan het MILP-model kan worden doorgegeven, moeten, naast de algemene aanpassingen met betrekking tot het weglaten en omdraaien van orders met
35
Hoofdstuk 5. Input data
Regio's
Postcode
File factor
Brussels Hoofdstedelijk Gewest
1000-1299
2
Provincie Waals-Brabant
1300-1499
1.66
Provincie Vlaams-Brabant
1500-1999, 3000-3499
1.75
Provincie Antwerpen
2000-2999
1.75
Provincie Limburg
3500-3999
1.25
Provincie Luik
4000-4999
1.25
Provincie Namen
5000-5999
1.25
Provincie Henegouwen
6000-6599,7000-7999
1.25
Provincie Luxemburg
6600-6999
1
Provincie West-Vlaanderen
8000-8999
1
Provincie Oost-Vlaanderen
9000-9999
1.5
Frankrijk, Nederland
-
Tabel 5.1:
1.25
Overzicht verschillende lefactoren per gewest
als losadres TransWest, nog enkele veranderingen aan deze lijst worden doorgevoerd ter voorbereiding van het oplossen met Gurobi 5.6.2.. Overeenkomstig het heuristisch model (zie sectie 7.2) worden eerst alle bestemmingen waar een volle lading moet worden geleverd uit de orderlijst gehaald en aan de lijst volle ladingen toegevoegd. Dit is een stap die voor het exacte model buiten het domein van de optimalisatie valt en daarom hier beschreven wordt. In deze stap worden ook de orders, waarvoor meer dan één dag totale rijtijd nodig is voor het leveren bij de klant en het terugkeren naar het home depot, uit de orderlijst gehaald. Om te bepalen om welke orders het gaat, worden alle orders uit de orderlijst aan volgende check onderworpen: indien de rijtijd van TransWest tot het order groter is dan 230 minuten wordt dit order als een aparte rit beschouwd. Deze grens van 230 minuten bouwt een mooie buer in aangezien de totale rijtijd wordt berekend via volgende formule, die uitvoerig besproken wordt bij het modelleren van de heuristische oplossing in 7.1:
tc = t1a + H + h ∗ la + ta1
36
Hoofdstuk 5. Input data In deze vergelijking zijn
H
en
h vaste parameters die de handling activities omvatten : H
de vaste tijd nodig voor het uitvoeren van klant.
h
handling activities
is de variabele tijd nodig voor het uitvoeren van
2 minuten per palet. De eigenlijke rijtijd (t1a
+ ta1 )
is
en bedraagt 15 minuten per
handling activities
en bedraagt
loopt, in het geval van een rijtijd van
230 minuten, op tot 460 minuten. Daarbij worden, in het extreme geval dat het order 32 paletten bevat, maximaal 79 minuten aan
handling activities (H + h ∗ la )
toegevoegd. Er
moet geen rekening worden gehouden met het geval een order 33 paletten heeft, aangezien dit sowieso in de lijst van volle ladingen werd opgenomen. Deze grens van 230 minuten is weliswaar een eerder strenge beperking waarbij het kan voorkomen dat voor een klein aantal orders een verkeerde toewijzing aan de lijst met volle ladingen wordt gedaan.
Dit is bijvoorbeeld het geval wanneer een order met een verre
bestemming, met een laadindex van zes paletten, een rijtijd heeft van 240 minuten. Door dit pre-proces zal dit order aan de lijst met volle ladingen worden toegewezen wegens de rijtijd die langer is dan 230 minuten, terwijl dit order door het kleine palettenaantal perfect binnen een tijdspanne van de wettelijk toegestane 540 minuten kan worden volbracht. Er wordt desalniettemin beslist om deze strenge beperking te behouden daar er slechts een algemene lefactor van 1,25 aan het buitenland wordt toegekend.
De daarmee gepaard
gaande mogelijke afwijkingen van de werkelijke rijtijd worden dan uitgemiddeld door de hierboven beschreven beperking.
Deze suboptimale aparte ritten die over twee dagen lopen zouden kunnen worden samengenomen met andere orders om zo de capaciteit en rijtijd van de gecombineerde ritten ten volle te benutten. Er wordt evenwel besloten om deze maatregel niet door te voeren aangezien deze buiten de scope van deze thesis valt daar de planningen in deze thesis een tijdshorizon van slechts één dag hebben.
37
6 | Rittenplanning: TransWest Vóór de uiteenzetting van de verschillende oplossingsmethoden voor het transportprobleem van TransWest, wordt hier eerst de planning, opgesteld door TransWest zelf, van naderbij bekeken. Voor de werkwijze van het planningsdepartement van TransWest wordt verwezen naar hoofdstuk 2, meer bepaald naar guur 2.1. Om een vergelijking te maken tussen de bekomen resultaten van de verschillende oplossingsmethoden in deze thesis en de resultaten van TransWest, wordt eerst vertrokken vanuit de orderlijst waar alle orders met losadres TransWest werden verwijderd. Dit werd uitvoerig besproken in sectie 5.1.
6.1
Orders met losadres TransWest weggelaten
Aantal ritten 53 Totale afstand (km) Totale lading (paletten) De cit (paletten) Totaal Gemiddelde Gemiddelde afwijking Tabel 6.1:
12277
1603
147
231,64
30,24
2,76
177,17
3,62
3,62
Samenvatting werklijst TW - orders die lossen bij TW weggelaten
Wanneer TransWest deze aangepaste orderlijst inplant, wordt een werklijst bekomen waarvan de belangrijkste parameters opgenomen zijn in tabel 6.1. Over de 53 ritten bekeken, wordt er in totaal
12 277
km gereden. Per rit zijn de vrachtwagens gemiddeld voor 91,65
% gevuld, wat neerkomt op een gemiddeld capaciteitsde cit van 2,76 paletten per vracht-
38
Hoofdstuk 6. Rittenplanning: TransWest wagen.
De bezetting van de vrachtwagens is vrij constant met een gemiddelde absolute
deviatie van 3,62 paletten per rit. Een volledig overzicht van de details per rit is terug te vinden in tabel C.1 in de Appendix in deel C.1.
6.2
Orders met losadres TransWest omgedraaid
Wanneer de orderlijst zo wordt aangepast dat orders met losadres TransWest worden omgedraaid (zodat het laadadres TransWest wordt en het losadres een klantenbestemming aanneemt) geeft de planning door TransWest de volgende resultaten (tabel 6.2). De volledige werklijst kan geraadpleegd worden in de Appendix in tabel C.2
Aantal ritten 88 Totale afstand (km) Totale lading (paletten) De cit (paletten) Totaal Gemiddelde Gemiddelde afwijking Tabel 6.2:
18315
2431
443
208,12
27,63
5,03
148,25
6,52
6,18
Samenvatting werklijst TW - orders die lossen bij TW omgedraaid
Uiteraard is het totale aantal gereden kilometers voor deze planning groter dan in de eerste werklijst aangezien hier alle orders worden opgenomen. Er worden 88 ritten gepland en de gemiddelde bezetting per vrachtwagen is 83,71%. Het gemiddelde capaciteitsde cit ligt hoger dan bij de eerste werklijst alsook de gemiddelde afwijking van het gemiddeld aantal paletten per rit.
De parameters van de werklijst die TransWest voor deze orderlijst heeft opgesteld worden dan ook als ijkpunt gebruikt.
39
7 | Rittenplanning: constructieve heuristiek In wat volgt zal de heuristische methode voor het plannen van het nationaal volle ladingvan groupagetransport van TransWest beschreven worden. De processen en subprocessen van deze methode zijn allen weergegeven in ow charts. Deze processen kunnen op verschillende niveaus bekeken worden: de guren van de hoofdprocessen (niveaus 1 en 2) kan de lezer terugvinden in de hoofdtekst, de ow charts van de subprocessen (niveau 3) werden opgenomen in Appendix D.1.
7.1
Variabelen
Voor het model initialiseren we de volgende variabelen:
lv :
de vorige locatie
ts :
startuur (= openingsuur eerste klant - rijtijd tot eerste klant)
tc :
cumulatieve rijtijd
tij :
rijtijd tussen node
C:
de maximale capaciteit van een vrachtwagen
H:
vaste
h:
variabele
i
en node
handling activities
j
die bij iedere node moeten worden uitgevoerd
handling activities
waarvan de duur afhangt van het aantal
paletten 40
Hoofdstuk 7. Rittenplanning: constructieve heuristiek li :
code
0 1
7.2
laadindex order
i
wanneer door toevoeging van het order de tijds- of capaciteitslimiet wordt overschreden wanneer een order niet kan worden toegevoegd wegens het overschrijden van de openingsurenbeperking
Model
Voor het modelleren van de constructieve heuristiek, wordt aangenomen dat TransWest de eerste node is. In guur 7.1 wordt een overzicht gegeven van de drie grote delen die doorlopen worden: allereerst wordt de datum van de dag waarvoor men wil plannen en het aantal vrachtwagens dat ter beschikking wordt gesteld voor de nationale volle lading-en groupageritten ingegeven. Daarna worden twee verschillende soorten ritten samengesteld: de ritten met één bestemming, i.e.
de volle ladingen, en de groupageritten.
Vervolgens
worden een totale werklijst met alle opgenomen orders voor elke soort rit en de werklijsten per vrachtwagen voor de groupageritten naar txt-documenten geëxporteerd.
Het tweede proces, het ophalen van ritten met een volle lading, is vrij eenvoudig. Eerst worden uit de orderlijst alle bestemmingen geselecteerd waar een volle lading moet worden geleverd. Vervolgens worden de gegevens van deze klanten in een lijst geplaatst die aan het einde van het heuristische programma worden geprint, zoals hierboven reeds vermeld is. Opmerkelijk is dat, in tegenstelling tot de pre-processing voor de exacte methode, hier wel verder gewerkt wordt met ritten naar het buitenland zonder volle lading, en deze dus mogelijks langer dan 540 minuten rijtijd vereisen. Om de planning toch feasible te houden, wordt hiervoor verder in het algoritme nog een aanpassing doorgevoerd.
Het derde proces, namelijk het samenstellen van een groupagerit, is weergegeven in guur
41
Hoofdstuk 7. Rittenplanning: constructieve heuristiek Datum en aantal beschikbare vrachtwagens ingeven
Plannen van ritten met volle lading
Plannen van groupageritten
Lijsten updaten
Figuur 7.1:
Overzicht heuristiek - niveau 1
7.2. Zoals de lezer merkt kan dit proces nog verder onderverdeeld worden in verschillende subprocessen. Deze subprocessen worden in de volgende paragrafen besproken.
Vooraleer het eerste subproces van dit algoritme gedetailleerd wordt bekeken, vereisen de verschillende lijsten die hier woren besproken enige uitleg. Met de
werklijst
met de eectief geplande orders voor de groupagerit bedoeld. De
lijst met onmogelijk te
plannen orders
wordt de lijst
betreft een lijst waaraan orders, die niet meer kunnen worden gepland
wegens de capaciteits- of de tijdsconstraint, worden toegevoegd.
Aan deze lijst worden
gedurende de procedure per rit enkel orders toegevoegd, aangezien eenmaal de capaciteitsof tijdscontraint is overschreden het order nog onmogelijk toe te voegen is aan die bepaalde rit.
In het geval van de
lijst met voorlopig onmogelijk te plannen orders
worden orders
toegevoegd die voorlopig niet gepland kunnen worden wegens de openingsurenbeperking. Deze lijst wordt, telkens een order eectief wordt toegewezen aan de werklijst van de groupagerit, terug leeggemaakt.
Dit gebeurt omdat na het toevoegen van een order, de
ETA van het nieuw te plannen order wijzigt, en dit ervoor kan zorgen dat het eerder voorlopig onmogelijk te plannen order, toch in de goupagerit kan worden opgenomen. Na
42
Hoofdstuk 7. Rittenplanning: constructieve heuristiek Start plannen van rit
Bereken de dichtste locatie
Bereken startuur vrachtwagen indien nodig
Check capaciteitsconstrai nt
Niet OK
OK
Check tijdsconstraint
Update variabele code naar 0
Niet OK
OK Niet OK Check openingsuren
Update variabele code naar 1
OK
Ja
Order toevoegen aan werklijst
Alles updaten naar vorige waarden
Nog orders in orderlijst?
Volgende mogelijkheid zoeken
Neen
Eind plannen rit
Figuur 7.2:
Plannen van43een groupagerit - niveau 2
Hoofdstuk 7. Rittenplanning: constructieve heuristiek de procedure van het plannen van één rit, worden deze lijsten leeggemaakt zodat alle nog te plannen orders nog in aanmerking komen voor de volgende rit.
Dichtste locatie berekenen In het hoofdproces weergegeven in guur 7.2, is duidelijk dat het algoritme start met het selecteren van de bestemming die het dichtst van de laatst geselecteerde node in de werklijst ligt. In de gedetailleerde guur D.1 in Appendix D.1 is te zien dat eerst en vooral een waarde wordt gegeven aan
lv .
Indien de werklijst voor de te plannen vrachtwagen
nog leeg is, krijgt deze variabele de waarde één en zal voor iedere klant in de orderlijst de afstand van TransWest tot die locatie berekend worden. In het geval er reeds orders aan de werklijst zijn toegevoegd, krijgt lv het klantnummer van het vorig order toegewezen en zal men de afstanden berekenen tussen deze node en alle andere locaties in de orderlijst. Om uiteindelijk het dichtst mogelijk te plannen order te selecteren, wordt op elk van de locaties de volgende vragen toegepast:
Werd het order reeds opgenomen in een werklijst?
Werd het order reeds opgenomen in de
lijst met onmogelijk te plannen orders
voor
deze rit?
Werd het order reeds opgenomen in de
orders
lijst met voorlopig onmogelijk te plannen
voor deze rit?
Indien men a rmatief kan antwoorden op één of meerdere van bovenstaande vragen, moet men het geselecteerde order al dan niet voorlopig buiten beschouwing laten bij het plannen van deze rit. In het geval er wel een geschikt order is gevonden, wordt de afstand van
lv
tot de bestemming van dit order vergeleken met de tot nog toe gevonden kleinste afstand. Indien de berekende afstand kleiner is dan deze kleinste afstand wordt dit order als voorlopig kleinste order geselecteerd. Zolang er nog orders in de lijst aanwezig zijn, zal men op het volgend order in de lijst opnieuw deze voorgaande stappen, startende vanaf de drie
44
Hoofdstuk 7. Rittenplanning: constructieve heuristiek bovenstaande vragen, toepassen. Wanneer alle orders zijn overlopen en dus het order met de kleinste afstand overblijft, wordt van dit order het order- en klantnummer opgeslagen.
Startuur berekenen Nadat de dichtstbijzijnde klant is bepaald en op voorwaarde dat er nog geen order is gepland voor de huidige werklijst, wordt het moment dat de vrachtwagen zou vertrekken bij TransWest vastgelegd. De exacte werkwijze voor het berekenen van het startuur kan teruggevonden worden in guur D.2: het startuur is gelijk aan het moment waarop de vrachtwagen ten vroegste mag leveren bij de dichtstbijzijnde klant, verminderd met de rijtijd tot deze klant en is opgenomen in de variabele ts . Wanneer ts kleiner of gelijk is aan het door TransWest vroegste toegelaten startuur (meerbepaald 4 uur 's morgens), wordt het toegelaten startuur als startuur genomen. startuur wordt
ts
Wanneer
ts
groter is dan het toegelaten
behouden. Het startuur heeft ook verder in het proces een invloed op
welke nodes aan de rit kunnen worden toegevoegd. Dit zal later in dit werk gedetailleerder aan bod komen. Na de bepaling van het startuur van de rit, worden drie controles uitgevoerd.
Overschrijden capaciteitslimiet nagaan Eerst wordt nagegaan of de maximaal mogelijke lading al dan niet overschreden wordt na het toevoegen van dit order ( guur D.3). Wanneer dit wel het geval is, geeft deze functie false terug en wordt de variabele
code
op 0 gezet, in het omgekeerde geval worden de
voorlopige lading en nog te vullen ruimte van de oplegger geüpdatet en geeft de functie true terug.
Overschrijden tijdslimiet nagaan Het nagaan of door het toevoegen van een node de planning van de chaueur nog voldoet aan de EG-verordening 561/2006, gebeurt door het controleren van de tijdsconstraint ( guur D.4): men kijkt of
tc ,
de cumulatieve rijtijd, de toegelaten dagelijkse rijtijd niet
45
Hoofdstuk 7. Rittenplanning: constructieve heuristiek overschrijdt. Om, zoals eerder vermeld, de orders die in het buitenland liggen ook te kunnen opnemen in de planning, wordt voor de ritten die deze buitenlandse orders bevatten de maximale rijtijd opgetrokken tot twee werkdagen. In het totaal mag de rit dan maximaal 1080 minuten duren.
Deze wordt wel onderbroken door de dagelijkse verplichte rusttijd
van 45 minuten na 4,5 uur rijden en de verplichte overnachting, i.e. een rusttijd van 12 uur. Deze manier heeft het voordeel dat, in tegenstelling tot het pre-processen bij de exacte methode, de rit met het buitenlands order ook nog andere orders kan opnemen. Zo gebeurt de toewijzing van alle orders toch steeds met oog op het minimaliseren van de afstand, rekening houdend met capaciteits- en tijdsconstraint.
Om na te gaan of het order eectief aan de rit mag worden toegevoegd, moet eerst de cumulatieve rijtijd,
tc ,
berekend worden.
Wanneer de geselecteerde node de eerste bestemming is van de route, wordt deze variabele als volgt berekend:
tc = t1a + H + h ∗ la + ta1 Merk op dat door de laatste term,
tc
ta1 ,
steeds rekening gehouden wordt met het feit dat in
ook de retourtijd van deze node tot TransWest zit.
Wanneer de geselecteerde node niet de eerste bestemming van de route is, wordt bij de berekening van tc voor het toevoegen van de vorige node ook als laatste term de rijtijd van de geselecteerde node tot TransWest toegevoegd. Deze moet uiteraard worden afgetrokken omdat de vorige node niet langer de voorlopig laatste klant is:
tc = t1a + H + h ∗ la + ta1 − t(a−1)1 Vooraleer wordt gecontroleerd of
tc
groter is dan de toegelaten rijtijd, wordt aan
tc
even-
tueel nog 45 minuten dagelijkse rusttijd toegevoegd. Dit komt voor wanneer de berekende rijtijd
tc
groter is dan 270 minuten en indien de rusttijd nog niet is opgenomen. Een ge-
lijkaardige bijkomende check vindt plaats indien er een buitenlands order is opgenomen in
46
Hoofdstuk 7. Rittenplanning: constructieve heuristiek de rit en de cumulatieve rijtijd de dagelijkse toegelaten rijtijd overschrijdt. Hier wordt een overnachting, i.e.
een rusttijd van 12 uur, aan de cumulatieve rijtijd toegevoegd indien
deze de dagelijkse limiet van 540 minuten schendt en de nachtrust nog niet is opgenomen. In het geval de maximale rijtijd per dag wordt overschreden door het toevoegen van het order geeft de functie false terug en wordt aan
code
een waarde 0 toegekend. Indien er
wel aan de beperking voldaan is, geeft de functie true terug.
Bij het niet voldoen aan één van de twee voorgaande checks, wordt de hieronder beschreven controle niet uitgevoerd.
Aankomst binnen openingsuren klant nagaan Wanneer echter wel aan de twee voorgaande controles voldaan is, wordt gekeken of de chaueur binnen de openingsuren van de geselecteerde node kan aankomen. Dit proces kan
Estimated Time of Arrival ) is logischerwijze
de lezer terugvinden in guur D.5. De ETA (
gelijk aan het moment waarop de chaueur bij TransWest vertrekt, vermeerderd met Wanneer deze niet binnen de time windows valt, wordt aan de variabele
code
tc .
een waarde
1 toegekend.
Wanneer het geselecteerde order voldoet aan alle drie voorgaande checks, wordt het toegevoegd aan de werklijst. Hierna wordt gekeken of er nog te plannen orders in de orderlijst overblijven. Als dit het geval is, begint het proces opnieuw vanaf het berekenen van het dichtste locatie gebaseerd waarop het laatst geselecteerd order een invloed heeft.
Volgend mogelijk order zoeken Als echter aan één van de drie beperkingen niet voldaan is, worden de lading, de ETA en tc geüpdatet naar de waarden die ze hadden vóór het controleren van de geselecteerde node en wordt naar een volgend mogelijk order gezocht D.6. Hiervoor wordt allereerst gekeken naar de waarde die werd meegegeven aan de variabele
47
Hoofdstuk 7. Rittenplanning: constructieve heuristiek code.
Wanneer deze 0 is, overschrijdt de planning door toevoegen van het desbetreende
order de tijds- of capaciteitslimiet en is het onmogelijk om dit op te nemen in de rit. Het order wordt dan toegevoegd aan de
lijst met onmogelijk te plannen orders.
Wanneer
code
een waarde 1 heeft, kon het order niet worden toegevoegd omdat de aankomst bij de klant niet binnen diens openingsuren lag. Hier was wel voldaan aan de tijds- en capaciteitslimiet. In dit geval bestaat, zoals eerder vermeld, de mogelijkheid dat het order bijvoorbeeld kan worden ingepland nadat een ander order toegevoegd is zodat de chaueur later, en binnen de openingsuren, toekomt bij de klant. Orders met toegevoegd aan de
code
1 worden dan ook slechts tijdelijk
lijst met voorlopig onmogelijk te plannen orders.
Na het toevoegen van
een order aan de rit, komen deze orders nog in aanmerking om opgenomen te worden in de huidige groupagerit. Nadat het geselecteerde order is toegevoegd aan de correcte lijst, wordt het aantal nog te plannen orders berekend. Dit bestaat uit het totale aantal orders, verminderd met de geplande orders in de werklijst en de (voorlopig) onmogelijk te plannen orders. Indien dit aantal verschillend is van 0, wordt het volgend order in de lijst met nog niet geplande orders geselecteerd. Hierop doorloopt het order dezelfde capaciteits-, tijds- en openingsurenchecks als hierboven vermeld. Wanneer het order niet aan de capaciteits- of tijdsconstraint voldoet, wordt het toegevoegd aan de lijst met onmogelijk te plannen orders.
Wanneer het niet
voldoet aan de openingsurenbeperking, wordt het toegevoegd aan de lijst met voorlopig onmogelijk te plannen orders. Indien na deze checks nog orders in de lijst met nog niet geplande orders staan, doorloopt het volgende order in de lijst met nog niet geplande orders hetzelfde proces. Als een order aan alle constraints voldoet, wordt het order gepland en aan de werklijst toegevoegd. Daarna wordt opnieuw gekeken of er nog orders in de orderlijst staan ( guur 7.2) en begint het planningsproces opnieuw vanaf het berekenen van het startuur voor de vrachtwagen.
48
Hoofdstuk 7. Rittenplanning: constructieve heuristiek 7.3
Resultaten
7.3.1 Orders met losadres TransWest weggelaten Eerst wordt het heuristische programma gerund voor de orderlijst waarbij de orders met losadres TransWest zijn weggelaten. Dit om de veronderstelling dat enkel bij TransWest wordt geladen te doen kloppen. Dit resulteert in onderstaande waarden. Het overzicht van de volledige rittenplanning kan men terugvinden in tabel D.1 in Appendix D.2 op pagina 113.
Aantal ritten 55 Totale afstand (km) Totale rijtijd (min) Totale lading (paletten) De cit (paletten) Totaal Gemiddelde Gemiddelde afwijking Tabel 7.2:
12555
18556
1776
72
224,20
331,36
31,71
1,29
124,06
141,54
1,93
1,93
Samenvatting werklijst heuristiek - orders die lossen bij TW weggelaten
7.3.2 Orders met losadres TransWest omgedraaid De aanname dat bij TransWest enkel wordt geladen en niet gelost kan ook worden vervuld door de orders met losadres TransWest om te draaien, zodat voor die orders TransWest het laadadres wordt en de klantenbestemming het losadres.
Het heuristieke programma
werd ook voor deze orderlijst gerund met tabel 7.3 als resultaat. De volledige werklijst is te vinden in Appendix D.2 in tabel D.2 op pagina 114.
Aantal ritten 82 Totale afstand (km) Totale rijtijd (min) Totale lading (paletten) De cit (paletten) Totaal Gemiddelde Gemiddelde afwijking Tabel 7.3:
16324
25506
2510
196
199,07
311,05
30,61
2,39
109,33
127,13
3,55
3,55
Samenvatting werklijst heuristiek - orders die lossen bij TW omgedraaid
49
Hoofdstuk 7. Rittenplanning: constructieve heuristiek
Vergelijking resultaten Uit de vergelijking van de rittenplanning van deze heuristiek voor de omgedraaide orderlijst (tabel 7.3) en de rittenplanning van TransWest voor dezelfde orderlijst (6.2) kan worden besloten dat de daling in het gemiddelde aantal paletten per rit ten opzichte van de planningen voor de orderlijst waarbij de orders met losadres TransWest zijn weggelaten, te wijten is aan de aard van de orderlijst en niet aan de planningsmethode.
7.3.3 Combineren van korte ritten In de volledige werklijst (tabel D.2) heeft een relatief groot deel van de ritten een rijtijd die ver onder de maximaal toegelaten rijtijd per dag (i.e.
540 minuten) ligt, met een
gemiddelde van 311,05 minuten per rit. Deze ritten hebben echter wel een capaciteit die het maximale palettenaantal benadert met een gemiddelde van 30,61 paletten per rit. De oorzaak van deze lage rijtijden ligt in de aanname dat een vrachtwagen volgeladen vertrekt vanuit het home depot en enkel ladingen lost tijdens een rit.
Om een hogere gemiddelde rijtijd te bekomen en zo de capaciteit van de chaueurs ten volle te benutten, worden daarom na de rittenplanning onder de ritten met een rijtijd minder dan 400 minuten combinaties van ritten gezocht die de maximale rijtijd niet overschrijden. Zo werden 24 ritten van tabel D.2 gecombineerd tot 12 ritten, waarbij nog steeds voldaan is aan de verordeningen van de E.G. met betrekking tot de dagelijkse toegelaten rijtijd. Deze bewerking reduceert het aantal ritten tot 69. De resultaten zijn te vinden in tabel D.3.
Vergelijking van de resultaten Wanneer tabel 7.3 en tabel 7.4 worden vergeleken, springen volgende zaken in het oog: de totale afstand, rijtijd en capaciteit zijn logischerwijze gelijk door de maatregel die genomen werd om de gebruikte capaciteit per individuele rit te bekijken. De gelijkheid kan ook verklaard worden doordat geen ritten weggelaten worden en een combinatie van 2 ritten erin
50
Hoofdstuk 7. Rittenplanning: constructieve heuristiek Aantal ritten 69 Totale afstand (km) Totale rijtijd (min) Totale lading (paletten) De cit (paletten) Totaal Gemiddelde Gemiddelde afwijking Tabel 7.4:
16324
25506
2510
196
233,20
362,27
30,61
2,39
114,05
139,39
3,55
3,55
Samenvatting werklijst heuristiek - orders die lossen bij TW omgedraaid en ritten gecombineerd
bestaat dat een chaueur 1 rit a egt en terugkeert naar het home depot van TransWest en daarna een tweede rit begint om ook bij de klanten van de tweede rit op tijd toe te komen en vervolgens, binnen de toegelaten rijtijd, terug te rijden naar TransWest. De gemiddelde afstand en rijtijd per rit ligt wel beduidend hoger en ook de gemiddelde afwijking t.o.v afstand en rijtijd is hoger. Dit komt doordat meer
outliers
worden gemaakt omdat ritten
worden gecombineerd tot ritten met een hoge rijtijd en afstand.
51
8 | Rittenplanning: mixed integer linear programming Om een eerste beeld te krijgen van de optimale oplossing van de case study, werd een lineair model opgesteld dat opgelost werd in Excel 2007 met Premium Solver 2014. Het betreft een deelprobleem met tien nodes en genereert een planning voor één vrachtwagen. Het depot van TransWest wordt voorgesteld door node 1. Er wordt aangenomen dat de vrachtwagen bij vertrek vanuit node 1 volgeladen is en op zijn route enkel ladingen lost.
8.1
Beperkt model:
Premium Solver 2014 en Gurobi
5.6.2
8.1.1 Beslissingsvariabelen 1 xij 0 1 zi 0
als vrachtwagen van node
i
naar node
j
rijdt
in de andere gevallen
als de vrachtwagen node
i
niet aandoet
als de vrachtwagen node
i
wel aandoet
52
Hoofdstuk 8. Rittenplanning: mixed integer linear programming
8.1.2 Parameters dij :
de afstand (in km) tussen node
i
tij :
de tijd (in minuten) nodig om van node
u:
de penaltykost voor de minimalisatie van
ci :
het aantal paletten dat een vrachtwagen laadt bij node
p:
de penaltykost van een capaciteitsde cit
T:
de maximale tijd (in minuten) die een vrachtwagenchaueur op één werkdag
en node
i
j naar node
j
te rijden
zi i
mag werken
C:
de maximale capaciteit van een vrachtwagen, uitgedrukt in aantal paletten
n:
de
H:
de vaste tijd (in minuten) nodig voor het uitvoeren van
shortage capacity
van de vrachtwagen (=
C-
P10
i=1 ci )
handling activities
bij een node
h:
de variabele tijd (in minuten) nodig voor het uitvoeren van
handling activities
bij een node, afhankelijk van het aantal paletten
8.1.3 Objective function M in.
10 X 10 X
dij xij + u
10 X
i=1 j=1
zi + p ∗ n
(8.1.1)
i=1
8.1.4 Constraints
10 X
xij ∈ {0, 1}
(8.1.2)
zi ∈ {0, 1}
(8.1.3)
xij ≤ 1 ∀ j ∈ {1, ..., 10}
i=1
53
(8.1.4)
Hoofdstuk 8. Rittenplanning: mixed integer linear programming 10 X
xij ≤ 1 ∀ i ∈ {1, ..., 10}
(8.1.5)
j=1 10 X
xij −
i=1
10 X
xij = 0 ∀ i, j ∈ {1, ..., 10}
(8.1.6)
j=1
zi +
10 X
xij = 1 ∀i ∈ {1, ..., 10}
(8.1.7)
j=1
X
xij ≤ | S | −1 ∀ S ⊂ {1, 2, ..., 10}
(8.1.8)
i,j∈S 10 X 10 X i=1 j=1
10 X 10 10 X X tij xij + H( xij − 1) + h ci ≤ T ∀ j ∈ {1, ..., 10} i=1 j=10
(8.1.9)
i=1 10 X i=1
ci
10 X
xij ≤ C
(8.1.10)
j=1 10 X
xii = 0
(8.1.11)
xi1 = 1
(8.1.12)
x1j = 1
(8.1.13)
i=1 10 X i=1 10 X j=1
Het objectief van dit model is het minimaliseren van de afstand van één vrachtwagen. Dit wordt aangevuld met het objectief om zoveel mogelijk nodes op te nemen in een tour en de vrachtwagen zo dicht mogelijk bij zijn capaciteit te vullen. Het streven naar deze twee laatste objectieven wordt gerealiseerd door respectievelijk de penalties
u
en
p
aan de
objective function toe te voegen.
Constraints (8.1.2) en (8.1.3) zijn domeinbeperkingen die betrekking hebben op de beslissingsvariabelen. Beperkingen (8.1.4) en (8.1.5) stellen dat er voor elke node
54
i
hoogstens één vrachtwagen
Hoofdstuk 8. Rittenplanning: mixed integer linear programming respectievelijk mag toekomen en weggaan. De
ow conservation constraint
wordt voorgesteld door (8.1.6) en deze geeft aan dat de
som van de vrachtwagens die toekomt bij een node gelijk moet zijn aan de som van de vrachtwagens die vertrekken van een node. De beperking (8.1.7) is een relaxatie van de constraint elke locatie moet worden aangedaan.
P10 P10 i=1
j=1
xij = 1,
dat stelt dat
Aangezien dit model slechts de planning voor één
vrachtwagen voorstelt, is het onmogelijk dat steeds alle orders binnen één rit kunnen worden gepland.
De relaxatie in de vorm van variabele
toegevoegd. Hieraan werd ook een penalty-kost
u
zi
wordt dan ook aan het model
toegekend, die opgenomen wordt in het
objectief opdat het aantal orders dat in de planning wordt opgenomen maximaal is. Deze penalty wordt in dit model als een constante variabele opgenomen. Het model biedt ook de mogelijkheid om de penalty
ui
te introduceren en deze voor elke locatie
i te laten variëren.
Hoe groter deze penalty, hoe belangrijker de opname van deze klant in de rit is. De
subtour elimination constraint
voor een subset van nodes en
(8.1.8) verbiedt het vormen van subtours. Hier staat
| S | voor het aantal elementen in S .
S
Subtours met elementen
van node 2 t.e.m. node 10 mogen niet voorkomen. Verder verhindert constraint (8.1.9) het overschrijden van de dagelijkse rijtijd, toegelaten door de EG-verordening 561/2006. In deze dagelijkse rijtijd wordt de tijd nodig om van node
i
naar node
nodig voor
j
te rijden, de tijd nodig voor
handling activities
handling activities
per node en de tijd
per palet inbegrepen.
De capaciteits constraint wordt voorgesteld door (8.1.10), terwijl beperking (8.1.11) eist dat arti ciële ritten worden vermeden. Tenslotte zorgen (8.1.12) en (8.1.13) ervoor dat de gegenereerde rit begint en eindigt bij het home depot.
8.1.5 Resultaten Bovenstaand model werd ook geïmplementeerd in XCode 5.1.1. en opgelost met Gurobi 5.6.2. . De resultaten kan men raadplegen in onderstaande tabel 8.1. Gezien de betrekke-
55
Hoofdstuk 8. Rittenplanning: mixed integer linear programming lijke grootte van het probleem is de CPU-tijd verwaarloosbaar en is deze niet opgenomen. Solver
Gurobi 5.6.2 200
300
Aantal nodes
6
6
6
6
6
6
6
Geselecteerde
1.8-3.6-6.9-8.3
1.8-3.6-6.9-8.3
1.8-3.6-6.9-8.3
1.10-3.8-6.3-8.1
1.8-3.6-6.9-8.3
1.10-3.8-6.3-8.1
1.8-3.6-6.9-8.3
zi (8.1.7)
1
Premium Solver 2014 50 100
penalty
nodes
-9.10-10.1
-9.10-10.1
-9.10-10.1
-9.6-10.9
-9.10-10.1
-9.6-10.9
-9.10-10.1
1-8-3-6-9-10-1
1,8,3,6,9,10,1
1,8,3,6,9,10,1
1,10,9,6,3,8,1
1,8,3,6,9,10,1
1,10,9,6,3,8,1
1-8-3-6-9-10
Totale afstand
164
165
165
165
165
165
165
Totale rijtijd
352
352
351
352
352
352
351
33
33
33
33
33
33
33
Route
Lading
Tabel 8.1:
Vergelijking Premium Solver 2014 - Gurobi 5.6.2 voor model 10 nodes
Op de tweede rij van de tabel wordt de penalty weergegeven toegekend aan de variabele
zi .
Hoe hoger deze penalty, hoe meer belang wordt gehecht aan de minimalisatie van deze
variabele en dus hoe meer nodes zouden moeten opgenomen worden in een rit. Dit kan nagegaan worden in de beschrijving van het mathematische model, en meer bepaald in constraint (8.1.7). Zoals de lezer kan waarnemen brengt deze constraint echter geen veranderingen teweeg in de resultaten van het model, met uitzondering van de volgorde van de nodes in een rit. Daarom wordt deze constraint niet opgenomen in het model dat wordt opgelost in Gurobi 5.6.2. . De lezer merkt daarnaast ook op dat Premium Solver 2014 en Gurobi 5.6.2 identieke resultaten opleveren. Het model in Excel implementeren, brengt een relatief grote werklast met zich mee. Daarenboven is er op vlak van modelgrootte slechts een beperkte mogelijkheid om Premium Solver 2014 te gebruiken. Voor lineaire problemen kunnen slechts tot
2 000
variabelen verwerkt worden en het model zorgt ook maar voor de planning van één
vrachtwagen. Om het MILP-model toe te passen op het volledige klantenbestand en voor het implementeren van bijkomende constraints die het model dichter bij de praktijk van TransWest brengen, wordt de uitgebreidere mathematische programmerings-solver Gurobi 5.6.2. gebruikt.
56
Hoofdstuk 8. Rittenplanning: mixed integer linear programming 8.2
Uitgebreid model: Gurobi 5.6.2
8.2.1 Beslissingsvariabelen 1 xvij 0 =0 ≥0 ewvij ≤0
arc ) van i naar j
als de verbinding (
geselecteerd is voor vrachtwagen
v
in de andere gevallen
i
als een vrachtwagen van node
j
als een vrachtwagen node
naar node
j
gaat
aandoet nadat eender welke vrachtwagen
(dezelfde of een andere) node
i
heeft aangedaan
in de andere gevallen
1 sv 0 1 oi 0
als vrachtwagen
v
geselecteerd is
in de andere gevallen
als node
i
opgenomen is in de orderlijst
in de andere gevallen
nv :
shortage capacity
mv :
surplus capacity
avi :
tijdstip van aankomst van vrachtwagen
tij :
de tijd nodig om van node
dij :
de afstand tussen node
wvij :
wachttijd die vrachtwagen
c:
capaciteit van een vrachtwagen, uitgedrukt in aantal paletten
T:
de maximale tijd gedurende dewelke een vrachtwagenchaueur op één werkdag
v
van vrachtwagen
van vrachtwagen
i
i
naar node
en node
v
v v j
op locatie
i
te rijden
j
oploopt als hij van node
i
naar
j
gaat.
mag werken
ci :
het aantal paletten dat een vrachtwagen laadt bij node
H:
de vaste tijd nodig voor het uitvoeren van
h:
de variabele tijd nodig voor het uitvoeren van afhankelijk van het aantal paletten
57
i
handling activities
bij een node
handling activities
bij een node,
Hoofdstuk 8. Rittenplanning: mixed integer linear programming pi :
openingsuur node
i
qi :
sluitingsuur node
i
ri :
het vroegste uur waarop een vrachtwagen vanuit TransWest mag vertrekken
plc :
penalty voor het hebben van een
shortage capacity
phc :
penalty voor het hebben van een
surplus capacity
pwt :
penalty voor de wachttijd
8.2.2 Objective function M in.
20 X 485 X 485 X
dij xvij + plc nv + phc mv + pwt wvij ∀ i, j ∈ {1, ..., 485} , v ∈ {1, ..., 20}
v=1 i=1 j=1 (8.2.1)
8.2.3 Constraints
485 X
xvij −
i=1
485 X
xvij , sv , oi ∈ {0, 1}
(8.2.2)
0 ≤ wvij ≤ 1
(8.2.3)
xvij = 0 ∀ i, j ∈ {1, ..., 485} , v ∈ {1, ..., 20}
(8.2.4)
j=1 485 X 20 X
xvij = oi ∀ i ∈ {1, ..., 485}
(8.2.5)
cij xvij + nv − mv = c ∗ sv ∀ v ∈ {1, ..., 20}
(8.2.6)
j=1 v=1 485 X 485 X i=1 j=1
485 X 485 X i=2 j=1
tij xvij +H(
485 X 485 X
xvij −1)+h
i=2 j=1
485 X
ci +t1j
i=2
485 X
xv1j ≤ T ∀ j ∈ {1, ..., 485} , v ∈ {1, ..., 20}
j=1 (8.2.7)
485 X
xvii = 0 ∀ v ∈ {1, ..., 20}
i=2 58
(8.2.8)
Hoofdstuk 8. Rittenplanning: mixed integer linear programming 485 X
xi1 = 1 ∀ v ∈ {1, ..., 20}
(8.2.9)
x1j = 1 ∀ v ∈ {1, ..., 20}
(8.2.10)
i=1 485 X j=1
avi + tij + H + h ∗ ci − M (1 − xvij ) ≤ avj ∀ i, j ∈ {2, ..., 485} , v ∈ {1, ..., 20}
(8.2.11)
av1 + t1j − M (1 − xv1j ) ≤ avj ∀ j ∈ {1, ..., 485} , v ∈ {1, ..., 20}
(8.2.12)
avi ≥ ri ∗ oi
(8.2.13)
avi ≥ pi ∗ oi
(8.2.14)
avi ≤ qi ∗ oi
(8.2.15)
avi + tij + H + h ∗ ci + wvij + ewvij = avj ∀ i, j ∈ {2, ..., 485} , v ∈ {1, ..., 20}
(8.2.16)
av1 + t1j + wv1j + ewv1j = avj ∀ j ∈ {1, ..., 485} , v ∈ {1, ..., 20}
(8.2.17)
wvij ≤ xvij ∀ i, j ∈ {1, ..., 485} , v ∈ {1, ..., 20}
(8.2.18)
Constraints (8.2.2) en (8.2.3) zijn domeinbeperkingen die betrekking hebben op de beslissingsvariabelen. De
ow conservation constraint
wordt weergegeven door (8.2.4) en geeft aan dat de som
van vrachtwagens die toekomt bij een node gelijk moet zijn aan de som van vrachtwagens die vertrekken van een node. Om te garanderen dat enkel orders kunnen worden geselecteerd die in de uitgedunde orderlijst aanwezig zijn, wordt constraint (8.2.5) toegevoegd. Deze uitgedunde lijst bevat alle orders van de ingegeven dag die niet in aanmerking komen voor volle lading. De capaciteitsconstraint (8.2.6), voor elke vrachtwagen, is uitgebreider dan die in het beperkt model. Naast de totale lading wordt hierbij ook de
59
shortage capacity
opgeteld en de
Hoofdstuk 8. Rittenplanning: mixed integer linear programming eventuele
surplus capacity
afgetrokken zodat deze totale waarde gelijk is aan de maximaal
toegestane lading, vermenigvuldigd met het feit of de rit al dan niet leeg is. In het geval de rit niet wordt opgenomen in de tour, moet het rechterlid van de constraint echter gelijk zijn aan 0. Constraint (8.2.7) verhindert voor alle vrachtwagens het overschrijden van de dagelijkse rijtijd, toegelaten door de EG-verordening 561/2006. In deze dagelijkse rijtijd wordt opnieuw de tijd nodig om van node node en de tijd nodig voor
i
naar node
handling activities
j
te rijden, de tijd nodig voor activities per
per palet inbegrepen. Daarbij wordt ook de
rijtijd nodig om van de laatste locatie terug naar TransWest te rijden, ingecalculeerd. Verder zorgt beperking (8.2.8) ervoor dat, met uitzondering van klant 1 ( i.e. TransWest), geen arti ciële ritten mogelijk zijn. Beperkingen (8.2.10) en (8.2.9) zorgen dat de gegenereerde rit begint en eindigt bij het home depot. Tenslotte stellen (8.2.11) tot en met (8.2.18) de openingsurenbeperkingen voor. Een meer gedetailleerde uiteenzetting over deze
time windows
is verder terug te vinden op pagina
62.
Penalties Opnieuw is het objectief van deze functie het minimaliseren van de afstand. In tegenstelling tot het beperkt model beschreven in deel 8.1, kan met dit uitgebreider model de rittenplanning voor meerdere vrachtwagens opgesteld worden. Opnieuw worden hierbij enkele penalties toegevoegd. De aandachtige lezer zal opmerken dat, zoals vermeld bij de resultaten van het beperkt model, de beslissingsvariabele
zi
niet in dit model wordt opgenomen.
Andere penalties die wel aan het model zijn toegevoegd:
plc , phc
en
pwt .
De exacte waar-
den van deze penalties worden in volgend paragraaf bepaald. Wat wel al vaststaat is de verhouding van de grootte van deze penaltywaarden tegenover elkaar:
Aangezien de maximale capaciteit absoluut niet mag worden overschreden, wordt aan
phc
de hoogste waarde toegewezen.
60
Hoofdstuk 8. Rittenplanning: mixed integer linear programming
Om de toewijzing van de orders aan de vrachtwagen zo economisch mogelijk te laten verlopen, en dus voor zoveel mogelijk ritten de maximale capaciteit van 33 paletten per vrachtwagen te benaderen, wordt
plc
geïntroduceerd.
Deze penalty wordt ver-
menigvuldigd met het aantal paletten minder dan de maximale capaciteit (i.e. het capaciteitsde cit).
plc
De waarde die
krijgt, moet afgewogen worden tegenover de
andere waarden in het objectief. Aangezien de totale afstand in kilometer het hoofdobjectief is, moet deze penalty binnen het interval van de afstandsmatrix liggen.
Als laatste is er
pwt ,
de penalty voor de wachttijd. Deze waarde zal de laagste van
de penalties zijn daar wachttijden bij klanten moeten worden vermeden maar niet noodzakelijkerwijs verboden zijn. Op die manier laat het model toe om een andere locatie te selecteren waar wel binnen de openingsuren geleverd kan worden.
Scenarionummer Penalty low capacity ( plc ) Penalty high capacity ( phc ) Penalty_wachttijd ( pwt ) Afstand ( in km ) Totaal capaciteitsde cit ( in # paletten ) Objectief Gap ( in %)
1
2
3
4
5
6
7
8
100
50
10
200
500
50
50
50
1 000 000
1 000 000
1 000 000
1 000 000
1 000 000
10 000
10 000
10 000
50
50
50
50
50
50
25
5
0
751
751
751
751
751
751
751
11
11
11
11
11
11
11
11
0
1450
890.5
3350
7750
1450
1450
1450
17.78
26.56
39.53
8.15
4.98
26.50
25.95
26.04
Tabel 8.3:
Evaluatie verschillende penalty-waarden
Om de waarde van de penalties te bepalen, wordt de waarde van één penalty-variabele telkens ceteris paribus gevarieerd.
In tabel 8.2.3 zijn in scenario 1 de oorspronkelijke
penaltywaarden voorgesteld. Eerst wordt de waarde voor penalty aan bod komen.
plc
gevarieerd zodat zowel lagere als hogere waarden
Concreet neemt deze penalty de waarden 50, 10, 100, 200 en 500 aan
en genereert het uitgebreid model de resultaten binnen een tijdslimiet van 600 seconden. Het is duidelijk zichtbaar dat deze waarden geen invloed hebben op de afstand en het
61
Hoofdstuk 8. Rittenplanning: mixed integer linear programming totale capaciteitsde cit.
Uiteraard zijn er wel grote verschillen in het objectief, maar
opmerkelijk is dat er ook grote afwijkingen zijn betreende de gap ten opzichte van de optimale oplossing. In de gegenereerde resultaten is het duidelijk dat er een kleiner gap is naargelang de penalty een grotere waarde heeft. Dit kan verklaard worden door het feit dat het model duidelijkere en dus minder afwegingen moet maken bij het in gebruik nemen van grotere penalties. Daartegenover staat wel dat vermoedelijk een andere optimale oplossing gevonden zal worden bij een kleinere penalty aangezien er meer afwegingen tussen afstand en capaciteit gemaakt zullen worden. Aangezien dit model slechts 20 nodes heeft en de CPU-tijd niet onwaarschijnlijk hoog is, zal de waarde voor
plc
op 50 vastgepind worden. Dit omdat deze waarde realistisch is ten
opzichte van de afstanden in de afstandsmatrix. Wat de waarde voor nemen.
phc
betreft, zijn opnieuw enkel in de gap grote verschillen waar te
Aangezien zelfs bij een penalty van
10 000
kan worden uitgesloten dat er ritten
worden gepland die meer dan de maximale capaciteit vereisen, wordt hier wel voor de oplossing met de kleinste gap gekozen. Als laatste wordt de waarde voor
pwt
kleinere invloed moeten hebben dan
bepaald. Zoals eerder vermeld zou deze penalty een
plc
en
voor getallen kleiner dan de waarden van
phc .
plc .
Hierdoor werden enkel scenario's gerund
Aangezien hier de resultaten opnieuw enkel
dierentiëren op vlak van de gaps, wordt zoals bij de penalty voor
shortage capacity
de
waarde beslist op basis van een realistische afweging: liever 25 km rijden dan één uur bij de klant te moeten wachten alvorens men kan leveren.
Time windows Een belangrijke toevoeging van dit uitgebreid MILP-model aan het eerder besproken beperkt model is de opname van de openingsurenbeperking. Via de klantenlijst wordt aan iedere klant een
time window
interval toegekend. Concreet houdt de beperking in dat het
order bij iedere klant binnen dit interval geleverd moet worden. Een eerste stap is het toevoegen van beperkingen (8.2.14) en (8.2.15). Hierdoor vallen de
62
Hoofdstuk 8. Rittenplanning: mixed integer linear programming ETA's strikt binnen de opgegeven intervallen. Constraint (8.2.13) zorgt dat de vrachtwagen niet eerder dan
ri ,
het vroegste uur waarop een vrachtwagen vanuit TransWest mag
vertrekken, vertrekt. Om de volgorde van klanten per rit te respecteren, moeten de ETA's ook aan deze sequentie voldoen. Om deze logische volgorde van aankomsttijden te garanderen wordt beperking (8.2.11) geïntroduceerd, gebaseerd op het werk van Kallehauge et al. waarde 1 aanneemt (meer bepaald, indien vrachtwagen node
j
rijdt), moet de aankomsttijd bij node
zijn dan de aankomsttijd bij node
j.
i,
Als
rechtstreeks van node
xvij i
de
naar
vermeerderd met de totale rijtijd, kleiner
In het geval
niet altijd op. Hierdoor is het noodzakelijk een
v
[13].
xvij
big M
gelijk is aan 0 gaat de vergelijking
toe te voegen die er ook in dit laatste
geval voor zorgt dat de constraint voldaan is. Aangezien de ritten die gepland worden niet vóór vier uur mogen starten, kan het verschil tussen
avi
en
avj
niet groter zijn dan 18 uur
als enkel met de rijtijd rekening wordt gehouden. Indien ook nog de deze vergelijking worden opgenomen, moet
big M
handling activities
bij
een grotere waarde aannemen. Daarom
wordt aan deze constante een waarde van 24 toegekend. Constraint (8.2.12) is een minder uitgebreide versie van de hierboven beschreven constraint. Deze wordt namelijk enkel voor node
1 gebruikt,
waar voor nodes
2 tot 485 constraint (8.2.11) deze beperking oplegt.
Het onderscheid tussen deze twee is het al dan niet incalculeren van de vaste en variabele
handling activities. Constraint (8.2.16) zorgt voor een extra dimensie van de
time windows
beperking. Deze
constraint stelt dat de aankomsten bij de nodes (klanten) elkaar zo goed mogelijk opvolgen. Logischerwijs is dit niet altijd perfect mogelijk. Daardoor wordt een variabele voegd die maximaal één uur wachttijd bij locatie
j
wvij
toege-
kan opvangen. Constraint (8.2.18) zorgt
ervoor dat deze enkel een waarde groter dan 0 kan aannemen indien de beslissingsvariabele
xvij
1 is. Voor het geval er geen directe verbinding is tussen node
arti ciële variabele
Aangezien
ewvij
i
en node
j,
wordt een
toegevoegd die voor de nodige correctie zorgt.
time windows -constraint (8.2.11) ook een unieke volgorde aan de nodes oplegt,
worden hier ook alle mogelijke subtours geëlimineerd.
63
De exacte
subtour elimination -
Hoofdstuk 8. Rittenplanning: mixed integer linear programming constraints worden dan overbodig in het uitgebreid model.
8.2.4 CPU-tijd verlagende maatregelen Het opstellen van dit uitgebreid MILP-model heeft als doel een feasible en indien mogelijk exact resultaat te vinden voor het plannen van een realistische orderlijst van TransWest met 170 orders, gebaseerd op een klantenlijst met 485 klanten, welke beschreven werden in hoofdstuk 5 op pagina 32. Desalniettemin blijkt het onmogelijk om met dit uitgebreid MILP-model tot een oplossing te komen. Met een dergelijk aantal variabelen en na introductie van de
time windows -constraints,
gaat de CPU-tijd van de solver Gurobi namelijk
op astronomische wijze de hoogte in.
Tijd-geïndexeerde formuleringen 20 X 485 X
bvti ≤ 1 ∀ v ∈ {1, ..., 20} t ∈ {1, ..., 9}
(8.2.19)
v=1 i=1 20 X 9 X
bvti = oi ∀ i ∈ {1, ..., 485}
(8.2.20)
v=1 t=1
bvti ≤
485 X
xvij ∀ v ∈ {1, ..., 20} , i ∈ {1, ..., 485}
(8.2.21)
j=1
bvt1 i ∗ ut1 + tij + H + h ∗ ci − M (1 − xvij ) ≤ bvt2 j ∗ ut2 ∀ v ∈ {1, ..., 20} ,
(8.2.22)
i, j ∈ {2, ..., 485} , t1 , t2 ∈ {1, ..., 9} bvt1 i ∗ ut1 − M (1 − xv1j ) ≤ bvt2 j ∗ ut2 ∀ v ∈ {1, ..., 20} , j ∈ {1, ..., 485} , t1 , t2 ∈ {1, ..., 9} (8.2.23)
Een oplossing hiervoor zou zijn om de
time windows
in intervallen op te delen zoals terug
te vinden is in tabel (8.4). Voor elke klant wordt aan elk interval een binaire beslissingsvariabele
t
bvti
toegekend, die aangeeft of de vrachtwagen
bij de klant
i
mag leveren.
64
v
al dan niet binnen dit tijdsinterval
Hoofdstuk 8. Rittenplanning: mixed integer linear programming
Tijdsinterval Beginuur Einduur 1
4
6
2
6
8
3
8
10
4
10
12
5
12
14
6
14
16
7
16
18
8
18
20
9
20
22
Tabel 8.4:
Overzicht nieuwe tijdsintervallen
Vervolgens kan elke vrachtwagen slechts één
duty
per interval uitvoeren, zoals terug te
vinden is in (8.2.19). Daarbij kan volgens (8.2.20) voor iedere klant die opgenomen is in de orderlijst slechts één tijdsinterval over alle vrachtwagens geselecteerd worden. Constraint (8.2.21) stelt dat een bepaald tijdsinterval voor vrachtwagen men kan worden indien locatie
i
v
en locatie
i
slechts opgeno-
geselecteerd is voor de rit van vrachtwagen
v.
Als laatste
stellen constraints (8.2.22) en (8.2.23) opnieuw de logische volgorde tussen de aankomsttijden voor. Deze aankomsttijden worden voorgesteld als de starttijden tijdsintervallen en klant
i.
t1
ut1
van de nieuwe
op voorwaarde dat dit tijdsinterval geselecteerd is voor vrachtwagen
Door het invoeren van de beslissingsvariabelen
bvti
v
en bijhorende constraints,
moet Gurobi minder afwegingen maken en zou zo de CPU-tijd kunnen verbeteren. Pessoa et al.[18] gebruiken deze tijd-geïndexeerde formuleringen voor de mathematische programmering van hun
Single and Parallel Machine Scheduling Problems.
Ze passen de IP tijd-
geïndexeerde formuleringen toe zodat de uitvoeringstermijn van elke taak in hun probleem wordt voorgesteld door een binaire variabele die geïndexeerd is over een discrete tijdsspanne. De auteurs vermelden erbij dat deze formuleringen zorgen voor betere grenzen. Bij het testen van deze formuleringen op het MILP, bleek echter dat door het toepassen van deze maatregel de grootte van het uitgebreid MILP-probleem niet veranderde en dat deze methode bijgevolg geen oplossing biedt voor de lange CPU-tijd.
65
Hoofdstuk 8. Rittenplanning: mixed integer linear programming
Clusters Een tweede mogelijkheid om de CPU-tijd te verlagen en die wel tot succes heeft geleid, bestaat erin om het probleem in subproblemen onder te verdelen. Meer bepaald zullen de klanten die in de orderlijst voorkomen, in clusters worden onderverdeeld op basis van hun geogra sche ligging. Om te bepalen welke clustergrootte gebruikt kan worden voor de subproblemen, werd het MILP-model gerund voor een verschillend aantal nodes. Er werd gestart met 20 nodes, daar het optimalisatieproces een minimaal aantal nodes nodig heeft om deze te combineren tot ritten met betrekkelijk goede resultaten. Dit minimale aantal wordt daarna telkens met één geincrementeerd om zo de optimale clustergrootte te bepalen. Aangezien het bekomen van een exacte oplossing een aanzienlijke CPU-tijd vereist, wordt een tijdslimiet van 900 seconden ingesteld. Een vergelijking kan dan gemaakt worden op basis van de bekomen gap. Uit tabel 8.5 kan geconcludeerd worden dat de gap sterk toeneemt vanaf een model van 22 nodes. Uit deze resultaten kan gesteld worden dat een clustergrootte van 20 nodes kan helpen om het probleem vlot aan te pakken.
Aantal vrachtwagens Tabel 8.5:
Aantal nodes
20
21
22
23
10
2,02%
5,91%
14,90%
76,90%
Vergelijking aantal nodes per cluster
In de literatuur zijn verschillende soorten methodes terug te vinden die voor een goede clusterverdeling kunnen zorgen. De methode die het meest aangeraden wordt, is clustering [11]. Hier moet het aantal clusters zelf ingegeven worden en via het
k-means
k-means -
algoritme worden alle gegevens aan een bepaalde cluster toegekend. Zoals eerder vermeld, wordt in dit werk het clusteren gebruikt om de orderlijst in subproblemen onder te verdelen. Dit gebeurt op basis van de klantennummers en de bijhorende coördinaten. Volgens dit algoritme worden eerst alle klanten aan een cluster toegewezen en ontstaat zo een ini-
66
Hoofdstuk 8. Rittenplanning: mixed integer linear programming tiële verdeling. Hierna wordt het gemiddelde van de coördinaten van de klanten die tot één cluster behoren als clustercentrum opgenomen. Vervolgens worden onderstaande twee stappen iteratief uitgevoerd tot de clusters stabiliseren:
Creëer nieuwe clusters door alle klanten toe te wijzen aan het dichtstbijzijnde clustercentrum.
Bereken de clustercentra gebaseerd op de nieuwe verdeling van de clusters.
Een beperking van dit
k-means
algoritme is dat de clustergroottes sterk kunnen variëren.
Zoals aangetoond in tabel 8.5, leidt het onderverdelen van de orderlijst in subproblemen van elk 20 nodes tot een oplossing die, binnen een aannemelijke CPU-tijd, het best aanleunt bij de exacte oplossing. Aangezien het doel van dit clusteren het bekomen is van clusters met min of meer gelijke grootte, wordt het
Figuur 8.1:
k-means
algoritme verder niet gebruikt.
Initiële clusters - 19 nodes per cluster
67
Hoofdstuk 8. Rittenplanning: mixed integer linear programming
Cluster linkerbovenhoek als startcluster
Ja
Clusters in de buurt met minder klanten dan maximaal?
Aantal klanten groter dan maximaal toegelaten?
Neen
Neen
Aangrenzend cluster selecteren
Ja Selecteer cluster met minst aangrenzende clusters
Cluster aanvullen tot maximum aantal klanten
Nog steeds te veel klanten in oorspronkelijk cluster?
Neen
Selecteer volgend aangrenzend cluster Ja
Ja
Nog meer dan 1 aangrenzende cluster?
Neen Alle orders te veel doorschuiven naar cluster
Figuur 8.2:
Algoritme clustervorming 68
Hoofdstuk 8. Rittenplanning: mixed integer linear programming
53% 52.5% 52%
Cluster%1%
51.5%
Cluster%2%
51%
Cluster%3%
50.5%
Cluster%4%
50%
Cluster%5%
49.5%
Cluster%6%
49%
Cluster%7%
48.5% 1.5%
2.5%
Figuur 8.3:
3.5%
4.5%
5.5%
6.5%
Opdeling in 7 clusters - orderlijst zonder 1
Omdat in de literatuur weinig vermeld staat over clustermethodes die resulteren in clusters met gelijke grootte, werd voor deze thesis een eigen clusteralgoritme ontwikkeld. De eerste stap van dit algoritme bepaalt hoeveel clusters er gecreëerd kunnen worden met de beperking dat het aantal nodes per cluster niet groter mag zijn dan 19. Er wordt met 19 in plaats van de eerder berekende 20 nodes gewerkt omwille van het feit dat de eerste node, i.e. TransWest, ook telkens in de orderlijst moet worden opgenomen. Ook bij dit algoritme wordt eerst een initiële clusterverdeling opgesteld. Dit gebeurt door voor de orderlijst, waarvan elke oplossingsmethode beschreven in deze thesis vertrekt (zie sectie 5.1 op pagina 33), de minimale en maximale waarden van de lengte- en breedtecoördinaten over alle orders heen te bepalen. Op basis hiervan kunnen de hoekpunten van het clusterrooster en de afbakening van de individuele clusters bepaald worden. Als tenslotte blijkt dat het order binnen de clusterranden ligt, wordt dit order logischerwijs aan de cluster toegevoegd. Voor sommige aantallen van clusters is het meetkundig onmogelijk om een rooster zoals
69
Hoofdstuk 8. Rittenplanning: mixed integer linear programming
53% Cluster%1%
52.5% 52%
Cluster%2%
51.5%
Cluster%3%
51%
Cluster%4%
50.5%
Cluster%5%
50%
Cluster%6%
49.5%
Cluster%7%
49%
Cluster%8%
48.5%
Cluster%9% 1.5%
2%
2.5%
3%
Figuur 8.4:
in guur 8.1 op te stellen.
3.5%
4%
4.5%
5%
5.5%
6%
6.5%
7%
Opdeling in 9 clusters - orderlijst omgedraaid
Een voorbeeld hiervan wordt teruggevonden bij de orderlijst
waar orders met losadres TransWest zijn weggelaten. Deze lijst bevat een totaal van 117 orders. Dit aantal kan benaderd worden door zeven clusters van maximaal 19 orders, en logischerwijs kan dit aantal orders niet opgedeeld worden in gelijke clusterroosters.
Om
dit te verhelpen, wordt het aantal initiële clusters gewijzigd naar een aantal dat wel aan deze voorwaarde voldoet. Meer speci ek zullen in het begin in dit geval slechts zes clusters gevuld worden.
Hierna wordt een zevende, extra cluster toegevoegd die voorlopig geen
enkel order bevat Aangezien het aantal nodes in deze initïele en extra cluster enorm kunnen variëren, is het noodzakelijk dat sommige orders naar andere clusters verschoven worden. Dit algoritme is weergegeven in guur 8.2 op pagina 68, en is beschreven in de volgende paragrafen. Eerst en vooral wordt de startcluster bepaald. Hiervoor wordt eerst de cluster in de linkerbovenhoek geselecteerd.
Op deze cluster wordt eerst een check uitgevoerd om na te
gaan of er meer dan het toegelaten aantal klanten in de cluster aanwezig zijn. Indien dit
70
Hoofdstuk 8. Rittenplanning: mixed integer linear programming het geval is, wordt onderstaand proces uitgevoerd.
In het geval er onvoldoende klanten
opgenomen zijn in dit cluster, wordt een andere aangrenzende cluster geselecteerd die wel aan de voorwaarde voldoet en start het proces vanuit deze cluster. Na de selectie van het cluster, wordt gekeken welke omringende clusters in de buurt minder klanten hebben dan de maximale toegelaten hoeveelheid. Indien meerdere aangrenzende clusters in deze staat verkeren, wordt gekeken naar het aantal omringende clusters van deze laatste cluster. De cluster die het minste aantal aangrenzende clusters heeft, wordt als eerste geselecteerd om tot aan de maximale hoeveelheid klanten aan te vullen.
Dit
aanvullen gebeurt opnieuw op basis van de coördinaten, en de orders met een bestemming die het dichtst bij de te vullen cluster liggen worden verschoven. Als er dan nog steeds te veel klanten in de oorspronkelijke cluster zijn opgenomen, wordt opnieuw gekeken of er nog omliggende clusters zijn die mogelijk aanvulling kunnen gebruiken. Indien dit niet meer het geval is, worden alle overtollige klanten toch naar de cluster met de meest omringende clusters verschoven. Dit algoritme blijft steeds doorgaan tot alle clusters de maximale hoeveelheid hebben bereikt, met uitzondering van enkele clusters op het einde die niet meer volledig gevuld kunnen worden wegens gebrek aan klanten. Het eindresultaat van dit algoritme voor de orderlijst waar orders met losadres TransWest zijn weggelaten, is terug te vinden in guur 8.3. Voor de orderlijst waarbij de orders met laadadres TransWest zijn omgedraaid werd een resultaat van 9 clusters bekomen en deze is op zijn beurt terug te vinden in guur 8.4.
8.2.5 Resultaten Onderstaande twee tabellen 8.6 en 8.7 geven een samenvatting van de planning door de exacte methode voor de orderlijsten waarbij respectievelijk de orders met laadadres TransWest zijn weggelaten en deze waar de orders met laadadres TransWest zijn omgedraaid. De volledige planning voor deze overzichten is te vinden in tabellen E.1 en E.2 in de Appendix op pagina 118 en 120. In de samenvattende tabellen 8.6 en 8.7 zijn dezelfde kenmerken als bij de heuristische
71
Hoofdstuk 8. Rittenplanning: mixed integer linear programming methode opgenomen: het totale aantal ritten, de totale afstand, rijtijd, capaciteit en het capaciteitsde cit.
Daarnaast zijn de relevante parameters van het optimaliseringsproces
opgenomen: de CPU-tijd, de relatieve gap tot de optimale oplossing en het soort oplossing. Wat deze gap betreft, wordt duidelijk uit de tabellen dat de grootte zeer afhankelijk is van de input, zijnde de orderlijsten afkomstig uit de clusterverdeling. Wanneer deze gap 0% bedraagt, heeft Gurobi een optimale oplossing bereikt. Andere bijkomende waarden zoals het aantal orders en het aantal geplande ritten per cluster werden ook in deze tabel opgenomen.
Totaal aantal ritten 64 Afstand Rijtijd Lading De cit CPU-tijd (km) (min) (paletten) (paletten) Cluster 1 Cluster 2 Cluster 3 Cluster 4 Cluster 5 Cluster 6 Extra cluster TOTAAL GEMIDDELDE GEMIDDELDE AFWIJKING Tabel 8.6:
Gap
Soort Aantal Aantal oplossing orders ritten
691
2014
461
1
422,52
0%
optimaal
20
14
794
1608
167
31
900
92,2%
feasible
16
6
2447
3631
81
150
900
66,2%
feasible
16
7
2571
4165
263
34
900
74,50%
feasible
20
9
1258
2245
231
0
900
75,2%
feasible
16
7
4293
6021
252
111
900
70,9%
feasible
16
11
370
1275
299
31
900
89,99%
feasible
20
10
12424 194,13
20959 327,48
1754 27,41
358 5,59
135,53
174,61
7,98
7,98
Samenvatting werklijst exacte methode - orders die lossen bij TW weggelaten
Wat uit de tabellen af te leiden valt, is dat de gemiddelde lading per rit voor zowel tabel 8.6 als 8.7 relatief laag is. Dit is te wijten aan de onvolledige volle ladingen, die in tabellen E.1 en E.2 op pagina 118 en 120 met een grijze achtergrond zijn weergegeven. Deze orders hebben meestal een buitenlandse bestemming waardoor de rijtijd boven het dagelijks toegelaten aantal uren ligt. Sommige binnenlandse orders, zoals deze in de provincie Luxemburg, worden ook in deze lijst opgenomen aangezien het ook kan voorkomen dat de totale rijtijd te groot is. Daarom worden deze lange ritten als volle ladingen beschouwd en apart gepland. Deze maatregel doet uiteraard de gemiddelde bezetting dalen en het aantal
72
Hoofdstuk 8. Rittenplanning: mixed integer linear programming Totaal aantal ritten 86 Afstand Rijtijd Lading De cit Soort Aantal Aantal CPU-tijd Gap (km) (min) (paletten) (paletten) oplossing orders ritten Cluster 1 Cluster 2 Cluster 3 Cluster 4 Cluster 5 Cluster 6 Cluster 7 Cluster 8 Cluster 9 TOTAAL GEMIDDELDE GEMIDDELDE AFWIJKING Tabel 8.7:
148
1218
410
19
900
94,0%
feasible
20
13
1051
2016
284
13
900
31,8%
feasible
20
9
1836
2869
131
67
900
88,3
feasible
20
6
733
1659
243
21
900
30,6%
feasible
20
8
1968
3421
318
12
900
85,3%
feasible
20
10
5352
8218
276
153
900
88,9%
feasible
19
13
2621
4027
261
36
900
93,0%
feasible
20
9
651
1611
283
14
900
87,0%
feasible
20
9
314
1317
325
38
900
87,5%
feasbile
20
11
14674 166,75
26356 299,50
2521 28,65
383 4,35
128,88
166,40
5,50
5,50
Samenvatting werklijst exacte methode - orderlijst met orders die lossen bij TW omgedraaid
ritten stijgen omdat er geen rekening wordt gehouden met het feit dat deze onvolledige volle ladingen mogelijks met andere ritten gecombineerd kunnen worden.
Deze praktijk
zou namelijk een planningshorizon van meer dan één werkdag vereisen, hetgeen buiten het bestek van deze thesis valt.
Om de vertekening door deze suboptimaal geplande onvolledige volle ladingen weg te werken, wordt in tabellen 8.8 en 8.9 een overzicht gegeven van de planning door Gurobi resulterend uit respectievelijk de orderlijst waarbij de orders met losadres TransWest zijn weggelaten en de orderlijst waarbij de orders met losadres TransWest zijn omgedraaid. In deze tabellen werden de ritten met onvolledige volle ladingen weggelaten. De lezer merkt een signi cante stijging op in de gemiddelde lading per rit en ook het aantal ritten is, uiteraard, gedaald.
73
Hoofdstuk 8. Rittenplanning: mixed integer linear programming Totaal aantal ritten 56 Afstand Rijtijd Lading De cit CPU-tijd (km) (min) (paletten) (paletten) Cluster 1 Cluster 2 Cluster 3 Cluster 4 Cluster 5 Cluster 6 Extra cluster TOTAAL GEMIDDELDE GEMIDDELDE AFWIJKING Tabel 8.8:
Gap
Soort Aantal Aantal oplossing orders ritten
691
2014
461
1
422,52
0%
optimaal
20
11
794
1608
167
31
900
92,20%
feasible
16
3
1019
1505
50
49
900
66,20%
feasible
16
0
1565
2777
230
1
900
74,50%
feasible
20
3
1258
2245
231
0
900
75,20%
feasible
16
4
3487
4921
250
47
900
70,90%
feasible
16
5
370
1275
299
31
900
89,99%
feasible
20
5
9184 164
16345 291,88
1688 30,14
160 2,86
115
155,6
4,51
4,51
Samenvatting werklijst exacte methode - orderlijst met orders die lossen bij TW weggelaten - excl. onvolledige volle lading Totaal aantal ritten 80 Afstand Rijtijd Lading De cit Soort Aantal Aantal CPU-tijd Gap (km) (min) (paletten) (paletten) oplossing orders ritten
Cluster 1 Cluster 2 Cluster 3 Cluster 4 Cluster 5 Cluster 6 Cluster 7 Cluster 8 Cluster 9 TOTAAL GEMIDDELDE GEMIDDELDE AFWIJKING Tabel 8.9:
148
1218
410
19
900
94,0%
feasible
20
13
1051
2016
284
13
900
31,8%
feasible
20
9
1836
2869
131
67
900
88,3
feasible
20
6
733
1659
243
21
900
30,6%
feasible
20
8
1968
3421
318
12
900
85,3%
feasible
20
10
5352
8218
276
153
900
88,9%
feasible
19
13
2621
4027
261
36
900
93,0%
feasible
20
9
651
1611
283
14
900
87,0%
feasible
20
9
314
1317
325
38
900
87,5%
feasbile
20
11
11210 140,13
21552 269,40
2473 30,91
167 2,09
108,40
144,48
2,63
2,63
Samenvatting werklijst exacte methode - orderlijst met orders die lossen bij TW omgedraaid - excl. onvolledige volle lading
74
9 | Personeelstoewijzing: binary integer linear programming 9.1
Scorematrix
Nadat werklijsten zijn opgesteld voor zowel de groupageritten als voor de ritten met een volle lading, wordt geschikt personeel toegewezen aan deze ritten. Dit wordt opnieuw via optimalisatie door middel van Gurobi 5.6.2.
gedaan.
Alvorens de optimalisatie wordt
uitgevoerd, worden voor iedere rit de volgende kenmerken opgehaald:
Rittype: groupage of volle lading
Moeilijkheidsgraad van de parking van de klant(en): deze varieert van 1 tot 4
Vereiste talenkennis van de chaueur afhankelijk van de regio waar klanten gelokaliseerd zijn (Vlaanderen, Brussels Hoofdstedelijk Gewest, Wallonië, Frankrijk of Nederland)
Aan- of afwezigheid van een laad- en loskaai bij de klant
Start- en stopuur van de rit
Eventueel vereiste overnachting
75
Hoofdstuk 9. Personeelstoewijzing: binary integer linear programming De kenmerken die bijgehouden worden zijn grotendeels klant-speci ek. Voor groupageritten, die meerdere klanten bevatten, worden enkel de hoogste moeilijkheidsgraad van de parkings van de verschillende bestemmingen bijgehouden.
De relevante kenmerken van de chaueurs en vrachtwagens worden gezamenlijk opgeslagen, zodat aan elke chaueur een vrachtwagen is toegekend. Dit weerspiegelt de praktijk van TransWest om chaueurs zo veel mogelijk met hun eigen vrachtwagen te laten rijden.
Voorkeur van de chaueur voor groupageritten of ritten met een volle lading
Parkeervaardigheden, varieert van 1 tot 4
Talenkennis
Aan- of afwezigheid van een laadklep aan de vrachtwagen
Voorkeur van chaueurs m.b.t. hun uurrooster (i.e.
Bereidheid tot overnachten tijdens rit
time preferences )
De kenmerken van elke rit worden dan vergeleken met de kenmerken van de chaueurs en vrachtwagens. Wanneer deze niet overeenkomen, worden penalties toegekend. Het gewicht van deze penalties wordt zo gekozen dat het weerspiegelt welke praktijken TransWest vooropstelt. Zo mogen ritten met parkings van moeilijkheidsgraad 4, niet worden toegekend aan chaueurs die slechts een rijvaardigheid van graad 2 hebben. Ook mogen enkel vrachtwagens met een laadklep naar klanten zonder laad- en loskaai worden gestuurd.
Deze
combinaties tussen de verschillende geplande ritten en vrachtwagens/chaueurs worden enkel onderling vergeleken. Daarom worden de penalties op één schaal gezet, met 1 000 de hoogste penalty voor combinaties die niet mogen voorkomen. Onderstaand vindt de lezer een overzicht van de waarden van de penalties.
Voor het soort rit wordt met twee soorten penalties gewerkt.
Een chaueur kan
namelijk aangeven of hij bereid is dit type rit wel, uitzonderlijk wel of niet te rijden. Wanneer een chaueur wordt toegewezen aan een rit van het type waarvan hij
76
Hoofdstuk 9. Personeelstoewijzing: binary integer linear programming heeft aangegeven het niet te willen uitvoeren, wordt een penalty van 1 000 toegekend. Wanneer hij wordt toegewezen aan een rit waarvan hij aangeeft deze enkel in uitzonderlijke omstandigheden te willen uitvoeren, wordt een penalty van 500 toegekend.
Ook voor het soort parking bestaan twee penalties: wanneer een chaueur te weinig gekwali ceerd is wordt een penalty van 1 000 toegekend, wanneer hij te veel gekwali ceerd is een penalty van 500.
Voor het niet overeenkomen van de talenkennis wordt een penalty van 750 toegekend.
Wanneer een vrachtwagen zonder laadklep naar een klant zonder laad- en loskaai zou worden gestuurd, wordt een penalty van 1 000 toegekend.
Wanneer een chaueur aan een rit wordt toegewezen die niet binnen zijn
rences
time prefe-
ligt, wordt een penalty van 900 toegekend
De gedachtegang van het voorgaande punt volgend, wordt een penalty van 900 toegekend wanneer een chaueur tijdens een rit moet overnachten wanneer hij aangegeven had daar niet toe bereid te zijn.
Uit de kenmerken van de ritten en de chaueurs/vrachtwagens wordt een scorematrix gegenereerd die voor elke chaueur een score per rit weergeeft. De score is de som van de eventueel toegekende penalties. De lezer begrijpt uit bovenstaande uiteenzetting dat deze score evenredig is met de aversie van een chaueur voor een bepaalde rit. De matrix wordt voor een vast aantal ritten gegenereerd. Wanneer het geplande aantal ritten kleiner is dan dit vaste aantal, wordt de matrix verder opgevuld met lege ritten die een penalty krijgen hoger dan diegene die kunnen toegekend worden met betrekking tot de combinaties van geplande ritten en chaueurs/vrachtwagens. Wanneer het aantal chaueurs/vrachtwagens nodig voor het uitvoeren van de verschillende soorten ritten (groupage en volle lading) het aantal chaueurs dat beschikbaar is voor deze nationale ritten overschrijdt, wordt voor het aantal chaueurs dat tekort schiet, de matrix verder gevuld met chaueurs die voor elke geplande rit een score krijgen hoger dan
77
21 600
Hoofdstuk 9. Personeelstoewijzing: binary integer linear programming (i.e.
de som van alle penalties).
Dit om te verzekeren dat de chaueurs die gewoonlijk
nationale groupage- en volle ladingritten rijden prioriteit krijgen wanneer ze toegekend worden aan ritten die meest geschikt zijn voor hen.
De chaueurs die de overige ritten
opvullen, zijn gewoonlijk chaueurs van TransWest bestemd voor internationale ritten, onderaannemers of chaueurs van derden (i.e. concurrenten). Er wordt geopteerd voor het gebruik van deze hoge score wegens gebrek aan gegevens over deze laatste groep. Ook valt het opmaken van een scorematrix voor deze groep buiten het bestek van deze thesis.
Op basis van deze scorevector worden de chaueurs/vrachtwagens tenslotte aan de geplande ritten toegewezen door middel van optimalisatie.
9.2
Optimalisatie toewijzing personeel aan ritten
9.2.1 Beslissingsvariabelen 1 xrv 0 1 or 0 srv :
als vrachtwagen
v
aan rit
r
is toegewezen
in de andere gevallen
als er verschillende nodes in een rit
r
zitten
voor lege ritten
score toegekend aan de combinatie van rit
r
en chaueur/vrachtwagen
v
9.2.2 Objective function M in.
20 X 20 X
srv xrv ∀ r, v ∈ {1, ..., 20}
(9.2.1)
r=1 v=1
9.2.3 Constraints xrv , or ∈ {0, 1}
78
(9.2.2)
Hoofdstuk 9. Personeelstoewijzing: binary integer linear programming 20 X
xrv ≤ 1 ∀ v ∈ {1, ..., 20}
(9.2.3)
xrv = or ∀ r ∈ {1, ..., 20}
(9.2.4)
r=1 20 X v=1
Het objectief (9.2.1) van dit model is het selecteren van rit-chaueur/vrachtwagen-combinaties met een zo klein mogelijke score. Het streven naar dit objectief is onderhevig aan domeinrestricties (9.2.2) op de variabelen
xrv
en
orv .
Daarnaast bepaalt restrictie (9.2.3) dat per
chaueur/vrachtwagen hoogstens één rit mag geselecteerd worden. Constraint (9.2.4) stelt dat wanneer een rit niet leeg is, er één en slechts één chaueur/vrachtwagen aan toegekend mag worden. Wanneer een rit echter leeg is, mogen er geen chaueurs/vrachtwagens aan toegewezen worden.
9.2.4 Resultaten De personeelstoewijzing op basis van bovenstaand model werd uitgevoerd met de werklijsten geproduceerd door de twee verschillende oplossingsmethoden als input.
In volgende
paragrafen zijn de belangrijkste parameters opgenomen.
Heuristisch programma In tabel F.1 in de Appendix op pagina 123 wordt de volledige personeelstoewijzing op basis van de werklijsten van het heuristisch programma beschreven. De relevante resultaten zijn de volgende:
Zonder 1 1 omgedraaid Objectief Gemiddelde score Gemiddelde afwijking Tabel 9.1:
302700
1077400
5405,36
13139,02
7905,42
14393,52
Samenvatting resultaten toekenning personeel o.b.v. heuristische planning
79
Hoofdstuk 9. Personeelstoewijzing: binary integer linear programming Er wordt in tabel 9.1 een onderscheid gemaakt tussen de waarden van de personeelstoewijzing die de werklijsten van de heuristische planning zonder orders met losadres TransWest (i.e. klant 1) gebruikt en de toewijzing die de heuristische werklijsten o.b.v. een orderlijst waarbij de orders met losadres 1 zijn omgedraaid. De verklaring en verantwoording van dit onderscheid vindt de lezer terug in sectie 5.1 op pagina 33. Het opvallend grote verschil tussen de gemiddelde score (i.e. de som van de penalties per chaueur) van kolom 1 en kolom 2, vindt zijn oorzaak in het feit dat de orderlijst waarin de orders met losadres TransWest zijn omgedraaid en niet weggelaten, simpelweg meer orders bevat. Daardoor wordt voor deze personeelstoewijzing een groter deel van de geplande ritten noodgedwongen toegekend aan chaueurs die een zeer hoge score per rit hebben (dit werd behandeld in sectie 9.1), wat de gemiddelde score logischerwijze doet stijgen.
Exacte methode In de Appendix op pagina 125 in tabel F.2 wordt de volledige personeelstoewijzing weergegeven op basis van de werklijsten gegenereerd door optimalisering met Gurobi. In onderstaande tabel 9.2 vindt de lezer een samenvatting.
Zonder 1 1 omgedraaid Objectief Gemiddelde score Gemiddelde afwijking Tabel 9.2:
542900
1250000
8482,81
14225,57
11431,01
14698,90
Samenvatting resultaten toekenning personeel o.b.v. heuristische planning
Opnieuw kan opgemerkt worden dat de gemiddelde score per chaueur van de personeelstoewijzing op basis van orderlijst 1 omgedraaid hoger ligt dan bij de personeelstoewijzing op basis van orderlijst zonder 1. Hier kan opnieuw in dezelfde richting gekeken worden voor de oorzaak, namelijk de aanvulling van het tekort aan chaueurs door chaueurs bestemd voor internationale ritten, onderaannemers of chaueurs van derden (i.e. concurrenten).
80
Hoofdstuk 9. Personeelstoewijzing: binary integer linear programming
Vergelijking van de resultaten
Wanneer de resultaten van de personeelstoewijzing op basis van de werklijsten geproduceerd door de twee verschillende oplossingsmethodes worden vergeleken, valt op dat de gemiddelde score per chaueur substantieel hoger ligt voor de exacte methode dan voor de heuristische methode. Dit wordt simpelweg verklaard door het feit dat de exacte methode een werklijst met meer ritten genereert. Het aantal beschikbare chaueurs voor nationale distributieritten bij TransWest blijft echter gelijk. Een relatief groter deel van de ritten van de werklijst van de exacte methode moet dus worden uitbesteed aan reserve chaueurs die, zoals in sectie 9.1 werd vermeld, een hogere aversie-score dan de gewone chaueurs hebben. Dit leidt uiteindelijk tot een hogere gemiddelde score voor de exacte methode.
81
10 | Resultatenvergelijking In de overzichtstabel 10.1 op pagina 83 zijn de meest relevante kenmerken van de verschillende versies van de planningsmethoden voor de nationale distributierondes van TransWest opgenomen. Voor iedere methode, zijnde planning door TransWest, heuristische planning en optimalisatieplanning, zijn de twee versies weergegeven die doorheen deze thesis werden gebruikt: een planning gebaseerd op de orderlijst waarbij de orders met losadres TransWest zijn weggelaten en een planning gebaseerd op de orderlijst waarbij de orders met losadres TransWest zijn omgedraaid. Voor meer uitleg over deze orderlijsten wordt verwezen naar sectie 5.1 op pagina 33. De aandachtige lezer merkt op dat een vergelijking tussen de verschillende methodes op basis van de ene orderlijst, dezelfde resultaten zou moeten opleveren als een vergelijking tussen de verschillende methodes op basis van de tweede orderlijst, aangezien deze laatste, ruim bekeken, een grote versie is van de eerste. Deze stelling wordt inderdaad grotendeels bevestigd maar moet genuanceerd worden. Dit wordt duidelijk wanneer we de capaciteitsbezetting vergelijken (zie onder).
Voor een vergelijking tussen de verschillende versies van de orderlijsten per oplossingsmethode kan men secties 6.2 op pagina 39 , 7.3.2 op pagina 49 en 8.2.5 op pagina 71 raadplegen. In volgende paragrafen worden de meest opvallende verschillen tussen de methodes onderling besproken.
82
Hoofdstuk 10. Resultatenvergelijking (1) TransWest - zonder 1 53 ritten Totale afstand (km) Totale lading (paletten) De cit (paletten)
(2) TransWest - omgedraaid 88 ritten
Totaal
Gemiddelde
Gemiddelde afwijking
Totaal
Gemiddelde
Gemiddelde afwijking
12276,9
231,64
177,17
18314,9
208,12
148,25
1602,5
30,24
3,62
2431
27,63
6,52
146,5
2,76
3,62
443
5,03
6,18
(3) Exacte methode - zonder 1 64 ritten
(4) Exacte methode - omgedraaid 86 ritten
Totaal
Gemiddelde
Gemiddelde afwijking
Totaal
Gemiddelde
Gemiddelde afwijking
Totale afstand (km)
12424
194
135,53
14674
166,75
128,88
Totale rijtijd (min)
20959
327,48
174,61
26356
299,50
166,40
1754
27,41
7,98
2521
28,65
5,50
358
5,59
7,98
383
4,35
5,50
Totale lading (paletten) De cit (paletten)
(5) Exacte methode - zonder 1 - excl. onvolledige volle lading 56 ritten
(6) Exacte methode omgedraaid - excl. onvolledige volle lading 80 ritten
Totaal
Gemiddelde
Gemiddelde afwijking
Totaal
Gemiddelde
Gemiddelde afwijking
Totale afstand (km)
9688
169,96
120,17
11210
140,13
108,40
Totale rijtijd (min)
17044
299,02
161,39
21552
269,40
144,48
1706
29,93
4,78
2473
30,91
2,63
175
3,07
4,78
167
2,09
2,63
Totale lading (paletten) De cit (paletten)
(7) Heuristiek - zonder 1 55 ritten
(8) Heuristiek - omgedraaid 82 ritten
Totaal
Gemiddelde
Gemiddelde afwijking
Totaal
Gemiddelde
Gemiddelde afwijking
Totale afstand (km)
12555
224,20
124,06
16324
199,07
109,33
Totale rijtijd (min)
18556
331,36
141,54
25506
311,05
127,13
1776
31,71
1,93
2510
30,61
3,55
72
1,29
1,93
196
2,39
3,55
Totale lading (paletten) De cit (paletten)
(9) Heuristiek - omgedraaid - met combinaties 69 ritten Totaal
Gemiddelde
Gemiddelde afwijking
Totale afstand (km)
16324
233,20
114,05
Totale rijtijd (min)
25506
362,27
139,39
2510
30,61
3,55
196
2,39
3,55
Totale lading (paletten) De cit (paletten)
Tabel 10.1:
Overzicht resultaten verschillende oplossingsmethoden
De totale rijtijd voor de methode (1) en (2) van TransWest is niet beschikbaar en om die reden niet weergegeven.
83
Hoofdstuk 10. Resultatenvergelijking
Aantal ritten Wat het aantal ritten betreft, wordt het hoge aantal bij de exacte methode met orderlijst zonder 1 (3) verklaard doordat gedurende het pre-processen voor de optimalisatie (sectie 5.4, pagina 35 ) de ritten met een rijtijd hoger dan 230 minuten tussen TransWest en de klant als aparte rit worden gecategoriseerd. Hierdoor hebben deze ritten niet de mogelijkheid gecombineerd te worden met andere ritten, ook al is de lading van deze rit met een rijtijd hoger dan 230 minuten niet volledig benut. In het geval deze lange ritten op een optimale manier in de planning zouden worden opgenomen, zoals het geval is bij de heuristische methode zou het aantal ritten tussen 80 en 86 liggen, respectievelijk het aantal ritten afkomstig van de exacte methode exclusief de onvolledige volle ladingen (6) en de exacte methode inclusief de onvolledige volle ladingen (4). Dit aantal ritten is dan min of meer vergelijkbaar met het aantal ritten bij de heuristische planning (9).
Totale afstand en rijtijd In guur 10.1 is een gra ek van de totale lading en rijtijd van alle methodes, weergegeven in tabel 10.1, te zien waarin volgende zaken opvallen:
Om de totale afstand tussen de exacte methode en de heuristische methode te kunnen vergelijken moet eerst een een nuancering gemaakt worden. Bij de exacte methodes (3) en (4) worden de suboptimale buitenlandse ritten in de rittenplanning meegeteld, waardoor de totale afstand toch een redelijke afwijking naar boven met zich mee brengt. In guur 10.2 is duidelijk waarneembaar dat hierdoor deze oplossing (3) de bovengrens van de exacte oplossing voorstelt. In het geval deze ritten met overnachting niet in de planning worden opgenomen, meer bepaald bij methodes (5) en (6), wordt een kleinere totale afstand dan de optimale afstand verwacht. Deze oplossingsmethode (5) vormt logischerwijs de ondergrens van het probleem.
84
Hoofdstuk 10. Resultatenvergelijking 30000" 27500" 25000" 22500" 20000" 17500" 15000" 12500" 10000" 7500" 5000" 2500" 0" (1)"
(2)"
(3)"
(4)"
(5)"
Totale"afstand"(km)"
Figuur 10.1:
(6)"
(7)"
(8)"
(9)"
Totale"rij=jd"(min)"
Vergelijking tussen verschillende oplossingsmethodes: totale afstand en rijtijd
De totale rijtijd voor de methode (1) en (2) van TransWest is niet beschikbaar en om die reden niet weergegeven.
Als dezelfde scenario's worden doorgetrokken naar de heuristische oplossingsmethode, is een rangschikking terug te vinden zoals op de rechteras van guur 10.2. De bovenste grens stelt dan een methode voor waarbij orders met buitenlandse bestemming als suboptimale aparte ritten worden opgenomen. Aangezien ritten met een relatief hoge gemiddelde afstand een kenmerk zijn van de heuristische oplossing, resulteert dit groter aantal ritten in een grotere totale afstand. Dezelfde redenering kan gemaakt worden voor een heuristische oplossing zonder buitenlandse orders, waarbij in de planning minder ritten woren opgenomen en de totale afstand dus daalt. Bij het heuristisch model is duidelijk dat oplossingsmethode (7) tussen de heuristische bovengrens en ondergrens ligt. Om uiteindelijk een treende vergelijking te maken tussen het exacte en heuristische model, wordt verondersteld dat ook bij het MILP-model de optimale
85
Hoofdstuk 10. Resultatenvergelijking
Figuur 10.2:
Situering oplossing exacte en heuristische methode
oplossing voor dit probleem tussen de grenzen ligt. Let wel dat deze redenering enkel van toepassing is bij het vergelijken op basis van de totale afstand. Als uiteindelijk deze vergelijking tussen het exacte en heuristische model eectief wordt doorgevoerd, is het zoals verwacht, duidelijk dat het primair objectief, i.e. het minimaliseren van de totale afstand, het best benaderd wordt door het exacte model.
Het is duidelijk dat de exacte methodes (3), (4), (5) en (6) als objectief het minimaliseren van afstand hebben (zie ook sectie 8.2.2 op pagina 58). Hiertegenover staat wel dat geen poging wordt gedaan om mogelijk drukke verkeersverbindingen tussen de orders te vermijden. De verhouding totale rijtijd op totale afstand is dan bijvoorbeeld ook aanzienlijk groter voor de exacte methode (3) in vergelijking met de constructieve heuristische methode (7). Niettegenstaande het vermijden van drukke verkeersverbindingen niet expliciet in deze oplossingsmethodes wordt opgenomen, wordt toch een lefactor aan de tijdsmatrix toegevoegd. Deze kan echter niet verklaren waarom de relatieve totale rijtijd groter is voor de exacte methode, aangezien de lefactor enkel dient om een realistische rijtijd weer te geven (zie ook 5.3 op pagina 35). Het zou dus interessant zijn voor verder onderzoek om na te gaan hoe de rijtijd wordt beïnvloed door verschillende oplossingsmethoden en wat het eect is van een focus op minimaliseren van rijtijd.
86
Hoofdstuk 10. Resultatenvergelijking De heuristische methode (8) en de heuristische methode (9) op basis van de orderlijst waar orders met losadres TransWest zijn omgedraaid geven exact dezelfde totale resultaten. Dit ligt aan het feit dat methode (9) in feite een verbetering is van methode (8) op vlak van rittenaantal en gemiddelde afstand en rijtijd per rit. Methode (9) combineert namelijk ritten van methode (8) tot ritten die een, binnen de wetgeving toegelaten, hogere gemiddelde afstand en rijtijd hebben. Zo verlaagt men het aantal ritten en dus het aantal chaueurs nodig en verhoogt men de capaciteitsbezetting op vlak van rijtijd.
32" 30" 28" 26" 24" 22" 20" 18" 16" 14" 12" 10" 8" 6" 4" 2" 0" (1)"
(2)"
(3)"
(4)"
(5)"
Gemiddelde"lading"
Figuur 10.3:
(6)"
(7)"
(8)"
(9)"
Gemiddelde"deficit"
Vergelijking tussen verschillende oplossingsmethodes: gemiddelde lading en de cit
Capaciteitsbezetting Zoals verwacht is het capaciteitsde cit bij de heuristische methodes lager dan bij de exacte methode. Dit is te verklaren door het feit dat orders telkens iteratief worden toegewezen aan een rit en dit tot wanneer enerzijds de capaciteit- of tijdsconstraint wordt overschreden of tot wanneer anderzijds geen orders meer kunnen worden toegevoegd wegens de openingsurenbeperking.
Het eerstvolgend mogelijk toe te voegen order wordt weliswaar
steeds geselecteerd op basis van de kleinste afstand, maar indien dit order onmogelijk te plannen valt wordt het volgend mogelijk te plannen order geselecteerd, opnieuw op basis van kleinste afstand. Hierdoor kan het dus voorkomen dat een order dat ver verwijderd is van het laatst toegevoegde order toch wordt opgenomen in de rit enkel en alleen omdat
87
Hoofdstuk 10. Resultatenvergelijking dit nog feasible blijkt te zijn op vlak van de wettelijk toegelaten rijtijd en de capaciteitsbezetting.
Dit zorgt er dus voor dat de capaciteit van de vrachtwagens ten volle benut
wordt, en dat het aantal vrachtwagens opmerkelijk gereduceerd kan worden. De prijs die hiervoor betaald wordt, zijn de veel grotere afstanden die deze ritten met zich meebrengen, zoals zichtbaar is in tabel 10.1. Uiteindelijk weegt deze grotere gemiddelde afstand niet zwaar door in de totale afstand van het probleem omdat deze gecompenseerd wordt door het kleiner aantal ritten. Dit is zeker het geval bij de constructieve heuristische methode (7).
Bij de ander heuristische methode (8), waarbij adressen worden omgedraaid, is er ten opzichte van het exacte model toch een groter verschil in totale afstand waar te nemen. Dit ligt aan het feit dat er, zoals terug te vinden in tabel D.2 op pagina 114, enkele ritten werden gepland met een groot capaciteitsde cit. Sommige van deze ritten, zouden in de realiteit nog gecombineerd kunnen worden daar deze samen noch de capaciteitsconstraint, noch de rijtijdconstraint zouden overschrijden.
De reden waarom deze dan niet worden
samen gezet in het heuristische programma is terug te vinden bij de openingsurenbeperking.
Het startuur van een rit wordt bij de heuristische methode bepaald op basis van
de openingsuren van de eerste klant, zoals terug te vinden in de ow chart D.2 op pagina 108. Dit heeft als gevolg dat het startuur niet optimaal bepaald is, zoals in onderstaand voorbeeld wordt bevestigd. Stel dat het tijdsinterval waarbinnen een eerste order van de rit geleverd mag worden, bijvoorbeeld 7 uur tot 15 uur is. Op basis van het algoritme startuur bepalen zal het startuur zo worden berekend zodanig dat het eerste order om 7 uur geleverd kan worden. Een tweede order, op een afstand van 50 kilometer, kan aan de rit worden toegevoegd indien enkel de capaciteits- en de rijtijdconstraints in rekening worden gebracht. Een extra beperking stelt dat dit tweede order enkel tussen 10 uur en 18 uur geleverd kan worden. Aangezien de klantenservice belangrijk is voor TransWest, werd deze openingsurenbeperking als een hard constraint opgenomen en kan dit order niet ingepland worden volgens de constructieve heuristische methode. Nochtans is in het in de realiteit mogelijk om deze
88
Hoofdstuk 10. Resultatenvergelijking twee orders toch samen in één rit op te nemen als het startuur later wordt gezet. Deze suboptimale ritten hebben een grote invloed op tal van variabelen die inbegrepen zijn in resultaten van de heuristische methode (9): eerst en vooral zorgt dit voor een hoger gemiddeld capaciteitsde cit dan verwacht zou kunnen worden indien men reeds de resultaten van heuristiek (7) in de vorige paragraaf heeft geïnterpreteerd. Dit gevolg is terug te vinden in tabel 10.3.
Ten tweede hebben deze suboptimale ritten ook als gevolg dat
het aantal ritten niet veel lager is dan deze van de exacte oplossing. Tenslotte zorgt de combinatie van meer ritten (door deze suboptimale ritten) en langere ritten (wat typerend is voor de heuristische oplossing) ervoor dat de afstand van heuristiek (8) heel wat hoger is dan de totale afstand als resultaat van het exacte programma (4).
89
Deel III Conclusie en verder onderzoek
90
11 | Conclusie In deze thesis wordt het
Truck Driver Scheduling
probleem van het Vlaams transportbe-
drijf TransWest geanalyseerd. Het probleem wordt in twee onderdelen opgedeeld: het
Windows
Vehicle Routing Problem with Time
en de personeelstoewijzing.
Voor het VRP-TW worden twee verschillende oplossingsmethoden voorgesteld: een constructieve heuristiek die het minimaliseren van het aantal vrachtwagens vooropstelt en een
Mixed Integer Linear Program
met een objectief van afstandsminimalisatie. Beiden starten
van een lege oplossing. De personeelstoewijzing wordt in twee stappen aangepakt: eerst wordt een scorematrix opgesteld die in een tweede fase geoptimaliseerd wordt door middel van
Binary Integer
Linear Programming. De resultaten van de heuristische en exacte methode voor het VRP-TW worden nadien tegenover elkaar geplaatst. Uit deze analyse kunnen we de volgende conclusies trekken. Het heuristische programma zal nooit de afstand minimaliseren, maar geeft wel een mooi evenwicht tussen dit objectief en het minimaliseren van het aantal ritten. Zo zal er een balans zijn tussen transport- en personeelskosten aan de ene kant en voorraad- en personeelskosten aan de andere kant. Daarnaast zijn er de algemene voordelen van een heuristiek tegenover een optimalisatie zoals de lagere CPU-tijd. Tenslotte beschikt het heuristische programma over de eigenschap dat wanneer door een onverwachte gebeurtenis de input van de methodes wijzigt, het heuristisch programma sneller en e ciënter een oplossing zal geven. De optimalisatiemethode daarentegen zal in dit geval eerst verschillende pre-processen moeten
91
Hoofdstuk 11. Conclusie doorlopen om de probleemgrootte te verkleinen. Deze eigenschap is niet te verwaarlozen in een dynamische omgeving zoals die van TransWest. Natuurlijk kan men niet naast het primair objectief van TransWest kijken, namelijk het minimaliseren van de afstand.
Dit kan enkel voor 100% doorgevoerd worden in het op-
timalisatieproces. Een laatste kanttekening bij de toepassing van het optimalisatieproces voor TransWest is dat de kans miniem is dat dit proces een totale optimale oplossing geeft vanwege de clustervorming die nodig is om de grote input te verwerken.
De personeelstoewijzing van TransWest wordt daarentegen wel globaal geoptimaliseerd door BILP. Dit brengt positieve gevolgen met zich mee zoals betere klantenservice en meer personeelstevredenheid. Waarden die de meeste bedrijven tegenwoordig en TransWest niet in het minst hoog in het vaandel dragen.
De meest relevante assumpties die werden gemaakt in deze gevallenstudie om verscheidene redenen waarvan de meest voorkomende het verminderen van de complexiteit is, zijn de volgende:
Het probleem in deze thesis beschrijft enkel het lossen van ladingen gedurende een route. Er wordt aangenomen dat een vrachtwagen volgeladen vertrekt en geen vracht laadt tijdens de rit.
De berekening van de afstanden tussen klanten werd gedaan op basis van coördinaten van postcodes, niet van exacte adressen.
Er wordt verondersteld dat de vervoerde goederen op één soort paletten wordt gestockeerd van een soort dat niet geruild wordt. De fysische capaciteit van chaueurs om deze handeling uit te voeren werd dus ook niet opgenomen in de personeelskenmerken. Dit komt niet overeen met de realiteit waar verschillende soorten paletten worden vervoerd, waarvan sommige moeten worden geruild.
In de exacte methode die het probleem oploste aan de hand van MILP is het niet
92
Hoofdstuk 11. Conclusie mogelijk om voor buitenlands ritten over twee dagen te plannen. Deze worden individueel gepland.
93
12 | Verder onderzoek Aangezien er heel wat beperkingen en assumpties zijn opgenomen in deze modellen, is er nog ruimte voor toekomstig onderzoek. Hieronder worden de meest relevante suggesties opgenomen.
Laden en lossen
Eerst en vooral werd de belangrijke assumptie gemaakt dat alle goe-
deren reeds in het homedepot aanwezig zijn. In de realiteit is het natuurlijk ondenkbaar, en vooral economisch niet haalbaar, dat vrachtwagens enkel goederen zouden lossen terwijl ze hun tour afwerken. Deze veronderstelling zorgt ervoor dat TransWest heel wat lege kilometers op de teller heeft staan. Deze dure
deadhead trips
kunnen worden vermeden door
tussendoor, of na het laatste losadres, goederen te laden die voor een korte termijn in het homedepot worden gestockeerd of tijdens dezelfde rit worden gelost. Volgens de resultaten van de verschillende oplossingsmethoden zijn er in alle scenario's nog tal van ritten terug te vinden waar de totale rijtijd nog ver onder de maximaal toegelaten rijtijd ligt. Het is dus in vele gevallen perfect mogelijk enkele tientallen kilometers om te rijden en zo een lading op te pikken, waardoor deze lege kilometers drastisch verminderen. Opnieuw speelt hier terug de afweging tussen het minimaliseren van transportkosten en het minimaliseren van voorraadkosten. Een extra toevoeging hierbij kan zijn om
cross-docking
in te plannen als een order, waarbij
ook rekening moet worden gehouden met time windows, capaciteits - en tijdsbeperkingen. Door de combinatie met gewone orders zou de kostprijs van deze anders dure, maar veel voorkomende, aangelegenheid gedrukt kunnen worden.
94
Hoofdstuk 12. Verder onderzoek
Clusters: combineren van resterende ritten
Aangezien het plannen van de volledige
orderlijst via het MILP-model een onredelijke CPU-tijd vereist, werd het probleem via klantenclusters in verschillende subproblemen opgesplitst. Voor elk van deze clusters werd dan een optimale oplossing bepaald. Het komt voor dat binnen elk van deze oplossingen een suboptimale rit aanwezig is, omdat er binnen de cluster geen orders meer aanwezig zijn om erin op te nemen.
Interessant zou zijn om na te gaan of deze resterende ritten
uit de verschillende clusters met elkaar gecombineerd kunnen worden, en wat de invloed hiervan zou zijn op verschillende parameters zoals de totale afstand, de totale rijtijd, het capaciteitsde cit en het aantal ritten.
Trade-o afstand en rijtijd
Uit de resultaten blijkt dat er een groot relatief verschil
bestaat tussen de totale afstand en de totale rijtijd en hoe deze zich ten opzichte van elkaar verhouden. Vooral bij de exacte methode, waar de focus ligt op het minimaliseren van afstand, is de rijtijd relatief groot ten opzichte van de totale afstand. De reden hiervoor kan niet direct achterhaald worden en verder onderzoek wordt aangewezen om na te gaan hoe de rijtijd wordt beïnvloed door de verschillende oplossingsmethodes. Een andere interessante insteek kan zijn om voor het VRP-TW een afweging te maken tussen minimaliseren van de afstand en het minimaliseren van de rijtijd. Dit vertaalt zich in een trade-o gemaakt tussen transportkosten en personeelskosten. Optimaal zou ook zijn om bij het objectief minimaliseren van rijtijd een tijdsafhankelijke lefactor in het objectief te verwerken, zodanig dat de drukke knooppunten zo veel mogelijk vermeden kunnen worden.
95
Appendices
96
A | Rij- en rustverordeningen A.1
Begrippen
Vooraleer een overzicht wordt gegeven van de beperkingen die de EG-verordening 561/2006 met zich meebracht, worden enkele belangrijke begrippen gede nieerd:
Rijtijd [5]: De tijd gedurende dewelke een chaueur een voertuig bestuurt met inbegrip van de tijd waarin het voertuig tijdelijk stilstaat door omstandigheden gerelateerd aan het rijden, vb. le
Dagelijkse rijtijd [4]: De geaccumuleerde rijtijd tussen het einde van een dagelijkse of wekelijkse rustperiode en het begin van de volgende dagelijkse of wekelijkse rustperiode
Wekelijkse rijtijd [4]: De geaccumuleerde rijtijd gedurende een week.
Werktijd [14]: Zoals terug te vinden in
Directive 2002/15/EG
wordt werktijd ge-
de nieerd als de rijtijden, tijd om te laden en lossen, schoonmaak en onderhoud en andere momenten gedurende dewelke een chaueur niet vrijelijk kan beschikken over zijn tijd, zoals onvoorziene wachttijden
Rusttijd [5]: Langere periodes gedurende dewelke een chaueur vrijelijk mag beschikken over zijn/haar tijd
Onderbreking of break [5]: Korte periodes die enkel gebruikt mogen worden voor recuperatie en voor geen enkel ander werk
97
B¼lage A. Rij- en rustverordeningen A.2
EG verordening 561/2006 Na een rijtijd van 4,5 uur moet een chaueur een ononderbroken onderbreking inlassen van 45 min. Uitzondering: de onderbreking mag vervangen worden door een onderbreking van minstens 15 min, gevolgd door een onderbreking van minstens 30 min. Goel et al. [5] tonen echter aan dat onderbrekingen opsplitsen in twee delen niet echt een voordeel biedt voor goederenvervoer over een lange afstand.
Als de
onderbrekingen korter zijn dan respectievelijk 45 min, 15 min of 30 min, dan worden deze niet als rusttijden meegerekend, noch als rijtijd; dit is dan gewoon
idle time.
De dagelijkse rijtijd mag niet langer zijn dan 9 uur. Uitzondering: maximaal twee maal per week mag de dagelijkse rijtijd uitgebreid worden naar 10 uur. Deze uitzondering is van belang wanneer vertragingen door bijvoorbeeld druk verkeer leiden tot langere rijtijden dan vooraf gepland.
De wekelijkse rijtijd: de geaccumuleerde rijtijd gedurende een week mag niet langer zijn dan 56 uur.
Tweewekelijkse rijtijd is beperkt tot 90 uur
Eén dagelijkse rustperiode (minstens 11 uur) moet plaatsvinden binnen een periode van 24u na het eind van de vorige dagelijkse of wekelijkse rustperiode.
Ook deze
dagelijkse rustperiode kan opgesplitst worden in twee ononderbroken periodes (eerste: minstens 3 uur, tweede: minstens 9 uur. Dus in totaal maakt dit minstens 12 uur.) Een uitzondering hierop is de
reduced daily rest period :
maximaal drie keer per twee
weken mag men na 9 uur rusten al terug verder rijden en hiervoor moet er geen compensatie voorzien worden. Ook deze uitzondering komt van pas bij onverwachte verlengingen van de rijtijd. Door het verkorten van de dagelijkse rustperiode kunnen deze verlengingen worden opgevangen en creëert men een robuuste planning, waarbij de gevolgen van vertragingen niet voelbaar zijn in de volgende rijperiodes.
98
B¼lage A. Rij- en rustverordeningen
Wekelijkse rust mag niet later starten dan na 6 opeenvolgende 24-uur-periodes (144 uur) na het eind van de vorige wekelijkse rustperiode en deze periode moet groter zijn dan 45 opeenvolgende uren.
period
De uitzondering hierop is de
reduced weekly rest
van minimaal 24 uur. Deze moet wel binnen de drie weken gecompenseerd
worden in één blok, en dit blok moet vasthangen aan een dagelijkse rustperiode van minimaal 9 uur.
99
B | Berekening factor f Onderstaand vindt de lezer de berekeningen tot het bekomen van een accurate factor die wordt vermenigvuldigd met de rechtlijnige afstand tussen twee bestemmingen om zo de afstand via autowegen te benaderen.
Vooreerst werden tien klantenbestemmingen van TransWest willekeurig gekozen en werd
TM de afstand tussen TransWest en de klanten via Google Maps opgezocht.
Klantnummer Postcode
Plaats
Afstand in km (Google MapsT M )
76
4671
Barchon
195
236
4700
Eupen
220
323
3920
Lommel
167
86
1080
Sint-Jans-Molenbeek
84.5
207
8000
Brugge
11.9
273
8400
Oostende
28.4
268
6041
Gosselies
136
140
8630
Veurne
50.6
89
3850
Binderveld
156
64
2000
Antwerpen
95.6
Tabel B.1:
Afstanden van TransWest tot klanten
Daarna werden de rechtlijnige afstanden berekend o.b.v. van de coördinaten vermenigvuldigd met de verschillende factoren.
Tenslotte werd bepaald met welke factor gemiddeld de minste afwijking t.o.v.
100
de reële
B¼lage B. Berekening factor f
Klantnummer 76 236 323 86 207 273 268 140 89 64
1
1.1
1.2
180.055
198.061
216.066
204.405
30.1329
145.364
Factor 1.3
1.4
1.5
234.0715
252.077
270.0825
245.286
265.7265
286.167
306.6075
159.9
174.4368
188.9732
203.5096
218.046
81.9864
90.185
98.38368
106.58232
114.78096
122.9796
14.5882
16.047
17.50584
18.96466
20.42348
21.8823
19.7015
21.6716
23.6418
25.61195
27.5821
29.55225
111.975
123.172
134.37
145.5675
156.765
167.9625
33.6415
37.0056
40.3698
43.73395
47.0981
50.46225
142.195
156.414
170.634
184.8535
199.073
213.2925
83.2085
19.5204
99.8502
108.17105
116.4919
124.81275
Tabel B.2:
Vermenigvuldiging rechtlijnige afstand met factoren
afstand werd bekomen. Factor
1
1.1
1.2
1.3
1.4
1.5
-14.945
3.061
21.066
39.0715
57.077
75.0825
-15.595
-189.8671
25.286
45.7265
66.167
86.6075
-21.636
-7.1
7.4368
21.9732
36.5096
51.046
-2.5136
5.685
13.88368
22.08232
30.28096
38.4796
2.6882
4.147
5.60584
7.06466
8.52348
9.9823
-8.6985
-6.7284
-4.7582
-2.78805
-0.8179
1.15225
-24.025
-12.828
-1.63
9.5675
20.765
31.9625
-16.9585
-13.5944
-10.2302
-6.86605
-3.5019
-0.13775
-13.805
0.414
14.634
28.8535
43.073
57.2925
-12.3915
-76.0796
4.2502
12.57105
20.8919
29.21275
Totale afwijking -127.8799 -292.8905 75.54412 Tabel B.3:
177.25613 278.96814 380.68015
Afwijkingen tabel B.2 t.o.v. tabel B.1
101
C | Rittenplanning door TransWest C.1
Overzicht rittenplanning
De werklijst resulterend uit de planning van TransWest zelf, nadat de orders met losadres TransWest uit de orderlijst werden verwijderd, is terug te vinden in tabel C.1.
Aantal orders Order
1 2 4 tem 11 14 - 18 19 - 25, 143 26 27 28 29 30 31 - 37 35 43,44 45,46 49,51 52, 53, 54, 55, 56, 57 60 62 61 63 65,151 66,67 77 - 80 82 87, 88 89-92,94 93 95 96 - 100 102, 103
Afstand (km)
100 46 281 708 551 0 20 0 98 98 172 49 100 80 208 235,5 167 26 0 154 445 384 344 272 120 145 215 0 468 418
53 Capaciteit (paletten)
33 21 33 24 32 33 4 32 33 33 32 33 19 28 19 28 33 33 33 33 27 31 27 33 33 32 33 33 33 28,5
102
De cit (paletten)
0 12 0 9 1 0 29 1 0 0 1 0 14 5 14 5 0 0 0 0 6 2 6 0 0 1 0 0 0 4,5
B¼lage C. Rittenplanning door TransWest Order
105 - 107 110 112 - 115 118 120,121 124,125 131 132 136-138, 164-168 135 139 140 141 144 145, 146, 163 147, 148 152 153 155 156 162 169, 170 171
Totaal Gemidddelde Gemiddelde afwijking
Afstand (km)
Capaciteit (paletten)
De cit (paletten)
12277 231,64 177,17
1603 30,24 3,62
147 2,76 3,62
0 0 474 96 216 71,4 94 0 306 42 395 194 281 349 425 104 642 738 656 614 16 573 86
33 33 32 33 33 20 26 26 32 33 33 33 30 33 32 30 33 33 33 33 33 33 33
0 0 1 0 0 13 7 7 1 0 0 0 3 0 1 3 0 0 0 0 0 0 0
Tabel C.1: Overzicht werklijst opgemaakt door TransWest - orders met losadres TransWest weggelaten
De werklijst resulterend nadat de orders met losadres TransWest omgedraaid werden, is terug te vinden in tabel C.2.
Aantal orders Order
1 2 3 4 tem 11 12,13 14 - 18 19 - 25, 143 26 27 28 29 30 31 - 37 38-42
Afstand (km)
100 46 58 281 157 708 551 0 20 0 98 98 172 126
88 Capaciteit (paletten)
33 21 3 33 20 24 32 33 4 32 33 33 32 21
103
De cit (paletten)
0 12 30 0 13 9 1 0 0 0 0 0 1 12
B¼lage C. Rittenplanning door TransWest Order
43,44 45,46 47,48 49-51 52, 53, 54, 55, 56, 57 58,59 60 61 62 63 64 65 66 67 68 69-71 72-73 74-76 77 - 80 81 82 83-85 86 87, 88 89-92,94 93 95 96 - 99 100 101 102 103 104 105 - 107 108 109 110 111 112 - 115 116,117 118 119 120,121 124,125 126,127 128,129 130 131 132 133,134 135 136-138, 164 - 168 139 140 141
Afstand (km)
100 80 72 208 235,5 88 167 0 26 154 0 150 280 300 297 31 59 142 344 119 272 312 72 120 145 215 0 384 312 0 250 322 320 0 119 119 0 119 474 130 96 85 216 71,4 59 137 284 94 0 85 42 306 395 0 281
Capaciteit (paletten)
19 28 33 19 28 28 33 33 33 33 10 27 6 25 1 23 33 32 27 32 33 32 33 33 32 33 33 33 33 33 33 24 26 33 31 33 33 33 32 32 33 21 33 20 28 31 5 26 26 9 33 32 33 33 30
104
De cit (paletten)
14 5 0 14 5 5 0 0 0 0 23 6 27 8 32 10 0 1 6 1 0 1 0 0 1 0 0 0 0 0 0 9 7 0 2 0 0 0 1 1 0 12 0 13 5 2 28 7 7 24 0 1 0 0 3
B¼lage C. Rittenplanning door TransWest Order
142 144 146 147, 148 149,150,122,123 151 152 153 154 155 156 157 158 159,160 161 162 163, 145 169, 170 171
Totaal Gemiddelde Gemiddelde afwijking
Afstand (km)
Capaciteit (paletten)
De cit (paletten)
18315 208,12 148,25
2431 27,63 6,52
443 5,03 6,18
290 349 216 104 210 252 642 738 121 656 614 344 829 252 599 16 320 573 86
3 33 33 30 24 33 33 33 33 33 33 33 33 24 1 33 32 33 33
30 0 0 3 9 0 0 0 0 0 0 0 0 9 32 0 1 0 0
Tabel C.2: Overzicht werklijst opgemaakt door TransWest - orders met losadres TransWest omgedraaid
105
D | Heuristieken D.1
Flow charts
In guren D.1 t.e.m. D.6 vindt de lezer de subprocessen van de heuristische methode terug.
106
B¼lage D. Heuristieken
Einde bereken de dichtste locatie
Start bereken de dichtste locatie
Ja
Update variabele vorige_locatie naar 1 (klantnummer TW)
Is werklijst nog leeg?
Neen
Alle nodige waarden updaten en opslaan in vector volgende_klant
Update variabele vorige_locatie naar klantnummer vorig order
Bereken afstand vanaf vorige_locatie voor iedere locatie aanwezig in orderlijst
Neen Selecteer volgend order in de lijst
Ja
Nog orders in orderlijst?
Order reeds in Ja werklijst opgenomen? Selecteer order als voorlopig order met kleinste afstand
Nee n Order reeds opgenomen in lijst onmogelijk te plannen orders?
Ja
Nee n
Ja
Order reeds opgenomen Ja in lijst voorlopig onmogelijk te plannen orders?
Is de afstand van order kleiner dan kleinste afstand?
Nee n
Figuur D.1:
Dichtste locatie berekenen - niveau 3
107
Neen
B¼lage D. Heuristieken
Start bereken startuur voor vrachtwagen
Bereken variabele startuur = openingsuur klant rijtijd tot klant
startuur kleiner of gelijk aan vroegste toegelaten startuur?
Neen
Ja
startuur = vroegste toegelaten uur
Einde bereken startuur voor vrachtwagen
Figuur D.2:
Startuur berekenen - niveau 3
108
B¼lage D. Heuristieken
Start check capaciteitsconstr aint
Ja
Totale lading kleiner of gelijk aan 33 als geslecteerd order toegevoegd is?
Nee
Waarden updaten
Update check variabele naar "OK"
Update check variabele naar "Niet OK"
Einde check capaciteitsconstraint
Figuur D.3:
Overschrijden capaciteit nagaan - niveau 3
109
B¼lage D. Heuristieken
Start check tijdsconstraint
Ja
Is werklijst nog leeg?
Bereken variabele cumulatieve_tijd via methode 1
Neen
Bereken variabele cumulatieve_tijd via methode 2
Ja
Bevat de rit een order voor het buitenland?
Update maximale rijtijd naar 1080 minuten
Neen Is rusttijd van toepassing en moet deze nog toegevoegd worden?
Neen
Ja Voeg de noodzakelijke rusttijd toe
Ja
Waarden variabelen updaten
Is de rijtijd kleiner of gelijk aan maximale rijtijd?
Neen
Update check variabele naar "Niet OK" Update check variabele naar "OK"
Einde check tijdsconstraint
Figuur D.4:
Overschrijden110 tijdslimiet nagaan - niveau 3
B¼lage D. Heuristieken
Check openingsuren
Bereken ETA (Estimated Time of Arrival)
Ja
Valt de ETA Neen binnen de openingsuren van de klant? Update check variabele naar "Niet OK"
Update check variabele naar "OK"
Einde check openingsuren
Figuur D.5:
Aankomst binnen openingsuren klant nagaan - niveau 3
111
B¼lage D. Heuristieken Start volgende mogelijkheid zoeken
code = 0
Order toevoegen aan lijst onmogelijk te plannen orders
Wat is de waarde van de variabele code?
code = 1
Order toevoegen aan lijst voorlopig onmogelijk te plannen orders
Aantal nog niet geplande orders berekenen
Ja
Aantal nog niet geplande orders gelijk aan 0? Neen
Selecteer volgend order in lijst nog niet geplande orders
Check capaciteit
Niet OK
Voeg order toe aan lijst onmogelijk te plannen orders
OK
Check tijdsconstraint
Niet OK
OK Niet OK
Check openingsuren
Ja
Nog orders aanwezig in lijst nog niet geplande orders?
Voeg order toe aan lijst voorlopig onmogelijk te plannen orders
OK
Order toevoegen
Einde volgende mogelijkheid zoeken
Figuur D.6:
Volgende mogelijkheid zoeken - niveau 3
112
Neen
B¼lage D. Heuristieken D.2
Overzicht rittenplanning
In tabel D.1 vindt men het resultaat van het heuristieke programma door verwerking van de orderlijst waarbij de orders met losadres TransWest zijn weggelaten.
Aantal ritten Orders
1 2,125 5-7,99,112 9,53,137,145,148,164,165,167 14,33,55-57,88-90 17,103 18,19,97,98,113 20,114 21,225 22,25,49,51,77,115,143 23,78,120 24,80,96 26 27,32,132,136 28,92 30 31,34,91,94,124,166 35,131 36,45,46 37 43,44,138 50,237,325,331,333,387,390 54,60,228,264 61 62 63 66,244,268 79,121, 168 82 87 93 95 100 102 105 106 107 110 118 135 139 140 141
Totale afstand (km)
430 79 244 385 159 583 469 339 360 397 452 463 40 139 30 428 241 76 80 160 122 190 261 126 156 14 200 346 44 240 166 108 188 166 364 364 364 70 428 68 172 166 204
Totale rijtijd (min)
523 175 429 577 346 734 658 484 504 577 572 584 121 267 126 521 401 172 191 245 234 407 378 209 241 95 300 452 125 327 251 191 273 251 455 455 455 153 521 149 257 251 328
113
55 Totale lading (paletten)
33 33 30 32 32 30 29 31 30 33 32 32 33 33 33 33 33 33 33 33 33 32 33 33 33 33 33 26 33 33 33 33 33 33 33 33 33 33 33 33 33 33 30
De cit (paletten)
0 0 3 1 1 3 4 2 3 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3
B¼lage D. Heuristieken Orders
144 146 147 151 152 153 154 155 156 162 169 170
Totaal Gemiddelde Gemiddelde afwijking
Totale afstand (km)
Totale rijtijd (min)
Totale lading (paletten)
De cit (paletten)
12447 226,3090909 124,6254545
18365 333,9090909 142,0727273
1743 31,69090909 1,960330579
72 1,309091 1,960331
68 204 152 62 166 180 0 130 242 156 504 502
149 289 219 143 251 265 81 213 329 241 614 606
33 33 24 33 33 33 33 33 33 33 18 15
Tabel D.1: Overzicht werklijst heuristiek - orders met losadres TransWest weggelaten
0 0 9 0 0 0 0 0 0 0 15 18
Het overzicht van de planning voor een orderlijst waarbij de orders met losadres TransWest omgedraaid zijn, bevindt zich in tabel D.2.
Om het aantal ritten te reduceren en de
capaciteit van de chaueurs op vlak van toegelaten rijtijd per dag ten volle te benutten, werden 24 ritten van tabel D.2 gecombineerd tot 12 ritten, wat het aantal ritten reduceerde tot 70. De resultaten zijn te vinden in tabel D.3.
Aantal ritten Type Orders
V G G G G G V G V V G V G G V V V V G
1 13,73 17 20,114 23,103 24,329 26 28,92 29 30 35,131 37 48,68 53,108 60 61 62 63 65
Totale afstand (km)
430 115 430 339 436 436 40 30 160 428 76 160 117 147 108 126 156 14 110
Totale rijtijd (min)
523 341 514 484 573 577 121 126 245 521 172 245 268 246 191 209 241 95 181
114
82 Totale lading (paletten)
33 27 6 31 25 27 33 33 33 33 33 33 31 33 33 33 33 33 27
De cit (paletten)
0 6 27 2 8 6 0 0 0 0 0 0 2 0 0 0 0 0 6
B¼lage D. Heuristieken Type
G G G V G V V V V V V V V V V V V V V G V V V G G V G V G V V V V V V V V V G G G G G G G G G G G G G G G G G
Orders
66,163 80,159 81 82 84,128 86 87 93 95 100 101 102 105 106 107 109 110 111 118 120,121 135 139 140 141 142 144 145,168 146 147 151 152 153 154 155 156 157 158 162 169 170 12,55,85,116 14,56,88,90,125 161,246,482 18,97,98,113 19,22,96,112,143 2,3,33,57,89 21,78,83 27,64,122 31,39,91,94,133,166 32,34,69,70,123,124 34,43,44 36,126,127 36,38,42,47,72 4,5,16,52,99 40,45,46
Totale afstand (km)
259 297 106 44 102 82 240 166 108 188 252 166 364 364 364 0 70 240 428 166 68 172 166 204 204 68 214 204 152 62 166 180 0 130 242 60 166 156 504 502 198 149 564 452 411 130 357 59 227 95 91 68 122 256 80
Totale rijtijd (min)
472 449 187 125 200 165 327 251 191 273 339 251 455 455 455 81 153 327 521 266 149 257 251 328 229 149 387 289 219 143 251 265 81 213 329 141 251 241 614 606 328 291 723 616 606 273 522 199 386 251 243 179 264 444 187
115
Totale lading (paletten)
28 27 32 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 30 3 33 24 33 24 33 33 33 33 33 33 33 33 33 18 15 33 33 27 24 33 33 33 15 33 33 31 33 33 32 31
De cit (paletten)
5 6 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 30 0 9 0 9 0 0 0 0 0 0 0 0 0 15 18 0 0 6 9 0 0 0 18 0 0 2 0 0 1 2
B¼lage D. Heuristieken Type
G G G G G G G G
Orders
41,79,138,148,149,165 49,51,115,130 58,74,167 59,71,132 6-11,15,50,54 75,117,119 76,129,137,164 77,150,160
Totaal Gemiddelde Gemiddelde afwijking
Type
C C C C C C C C C C C C G G G G G G G G G G G G G G G G G G G G G G G G
Aantal ritten Orders
Totale afstand (km)
Totale rijtijd (min)
Totale lading (paletten)
De cit (paletten)
16324 199,07 109,33
25506 311,05 127,13
2510 30,61 3,55
196 2,39 3,55
Totale afstand (km)
Totale rijtijd (min)
69 Totale lading (paletten)
De cit (paletten)
288 352 152 30 235 73 121 330
525 486 266 141 484 185 249 449
28 33 33 33 33 33 33 33
Tabel D.2: Overzicht werklijst heuristiek - orders met losadres TransWest omgedraaid
12,55,85,109,116 154,155 26,95 28,92,101 110,111 11,75,117,141 2,3,33,57,84,8128 58,61,74,167 142,147 32,34,69,70,87,123,124 37,65 81,139 63 82 157 151 135 144 86 60 62 162 29 93 102 140 152 158 153 100 146 156 105 106 107 30
198 130 148 282 310 277 232 278 356 335 270 278 14 44 60 62 68 68 82 108 156 156 160 166 166 166 166 166 180 188 204 242 364 364 364 428
409 147 312 465 480 513 473 475 448 578 426 444 95 125 141 143 149 149 165 191 241 241 245 251 251 251 251 251 265 273 289 329 455 455 455 521
116
33+33 33+33 33+33 33+33 33+33 30+33 33+33 33+33 24+3 33+33 27+33 33+33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33
5 0 0 0 0 0 0 0
0 0 0 0 0 3 0 0 6 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
B¼lage D. Heuristieken Type
G G V V V V V V V V V V V V V V V V V V V V V V V V V V V V V V V V
Orders
118 1 27,64,122 59,71,132 36,38,42,47,72 31,39,91,94,133,166 36,126,127 40,45,46 48,68 35,131 14,56,88,90,125 34,43,44 76,129,137,164 41,79,138,148,149,165 13,73 53,108 66,163 6-11,15,50,54 4,5,16,52,99 145,168 77,150,160 49,51,115,130 120,121 80,159 19,22,96,112,143 21,78,83 161,246,482 18,97,98,113 23,103 24,329 20,114 17 170 169
Totaal Gemiddelde Gemiddelde afwijking
Totale afstand (km)
Totale rijtijd (min)
Totale lading (paletten)
De cit (paletten)
16324 233,20 114,05
25506 311,05 127,13
2510 30,47 3,62
196 2,80 4,06
428 430 59 30 122 227 68 80 117 76 149 91 121 288 115 147 259 235 256 214 330 352 166 297 411 357 564 452 436 436 339 430 502 504
521 523 199 141 264 386 179 187 268 172 291 243 249 525 341 246 472 484 444 387 449 486 266 449 606 522 723 616 573 577 484 514 606 614
33 33 15 33 33 33 33 31 31 33 33 31 33 28 27 33 28 33 32 24 33 33 33 27 33 33 27 24 25 27 31 6 15 18
Tabel D.3: Overzicht werklijst heuristiek met rittencombinaties - orders met losadres TransWest omgedraaid
117
0 0 18 0 0 0 0 2 2 0 0 2 0 5 6 0 5 0 1 9 0 0 0 6 0 0 6 9 8 6 2 27 18 15
E | Exacte methode De planningen resulterend uit de optimalisatie met Gurobi zijn terug te vinden in tabel E.1 en E.2. Tabel E.1 geeft de volledige planning weer voor de orderlijst met orders die als laadres TransWest hebben weggelaten. Tabel E.2 geeft deze voor de orderlijst waarbij orders met laadadres TransWest zijn omgedraaid.
Totaal aantal ritten Type
Orders
CLUSTER 1
Totale afstand (km)
Totale rijtijd (min)
66 Totale lading (paletten)
De cit (paletten)
V G V G V G V V V V V V V V
1 2, 35, 36 26 28 30 31, 32, 93, 162 37 61 62 94 99 117 134 161
68 116 0 0 68 147 68 0 14 0 78 68 50 14
167 241 81 79 149 331 149 81 97 81 167 149 145 97
33 33 33 32 33 33 33 33 33 33 33 33 33 33
0 0 0 1 0 0 0 0 0 0 0 0 0 0
G G V V G V
4, 5, 6, 9, 10, 14 50, 52, 53, 54, 88 60 87 90 153
190 180 136 106 76 106
417 357 273 203 141 217
31 27 33 33 10 33
2 6 0 0 23 0
G G G V V
7, 18 8, 19, 22, 98 15, 16, 96, 97, 111 17 20
387 349 283 430 338
465 516 524 579 567
6 13 31 6 16
27 20 2 27 17
CLUSTER 2
CLUSTER 3
118
B¼lage E. Exacte methode Type
Orders
Totale afstand (km)
Totale rijtijd (min)
Totale lading (paletten)
De cit (paletten)
5 4
28 29
V V
21 112
330 330
491 489
G V V G G G V V V
34, 65, 137 63 125 135, 140, 165 136, 144, 163, 166, 167 146, 147, 164 150 151 168
116 108 502 224 224 155 190 548 504
229 219 689 452 427 320 275 855 699
33 33 15 32 33 33 33 33 18
0 0 18 1 0 0 0 0 15
G G V G V V V
11, 33, 51, 55 56, 66, 78, 79, 80 101 119, 120 143 145 170
174 254 166 166 166 166 166
366 512 315 277 251 251 273
33 33 33 33 33 33 33
0 0 0 0 0 0 0
V G V G G V G V V V V
23 24, 113, 142 25 67 77, 102, 114 82 95 138 152 154 155
436 442 370 240 313 226 214 372 612 542 526
577 540 523 403 520 371 375 463 789 637 823
1 17 1 25 28 33 15 33 33 33 33
32 16 32 8 5 0 18 0 0 0 0
G G G G G V V V V V
27, 44, 130 43, 46, 57, 89, 164 44, 45 65 91, 123, 124 104 105 106 109 139
78 100 60 67 65 0 0 0 0 0
212 273 168 26 191 81 81 81 81 81
31 33 33 4 33 33 33 33 33 33
2 0 0 29 0 0 0 0 0 0
CLUSTER 4
CLUSTER 5
CLUSTER 6
EXTRA CLUSTER
TOTAAL GEMIDDELDE GEMIDDELDE AFWIJKING
12424 194,13 135,53
20959 327,48 174,61
1754 27,41 7,98
Tabel E.1: Overzicht werklijst exacte methode - orders met losadres TransWest weggelaten
119
358 5,59 7,98
B¼lage E. Exacte methode Totaal aantal ritten Type
Orders
CLUSTER 1
Totale afstand (km)
Totale rijtijd (min)
87 Totale lading (paletten)
De cit (paletten)
G G V G V V V V V V G V V
2, 3, 94 27, 70, 91, 92, 124 62 69 95 101 105 106 107 110 132 140 162
67 41 14 12 0 0 0 0 0 0 0 0 14
189 189 97 14 81 81 81 81 81 81 67 81 95
29 29 33 29 33 33 33 33 33 33 26 33 33
4 4 0 4 0 0 0 0 0 0 7 0 0
G G V G G V V V V
4, 11, 14, 53, 54, 89 33, 57, 66, 125 60 68, 108 81, 88 87 109 111 154
195 84 136 106 106 106 106 106 106
251 228 219 223 245 189 203 229 229
26 28 33 32 33 33 33 33 33
7 5 0 1 0 0 0 0 0
G G V V G V
5, 6, 7, 8, 112 9, 15, 16, 38, 50, 52 17 18 97, 98, 99, 113, 130 157
237 183 430 374 334 278
457 392 615 503 537 365
30 30 6 4 28 33
3 3 27 29 5 0
G G G G V G G G
13, 167, 168 31, 136, 163 32, 119 58, 133, 134 63 74, 128 75, 129, 161 116, 117
158 163 50 50 108 72 70 62
306 312 145 176 191 186 183 160
33 27 23 32 33 32 31 32
0 6 10 1 0 1 2 1
G G G G V V V G V V
49, 51, 55 56, 77, 80, 96 66, 67, 79 78, 83 82 93 102 120, 121 144 146
173 258 255 226 226 166 166 166 166 166
311 453 430 346 399 337 293 308 293 251
27 33 32 28 33 33 33 33 33 33
6 0 1 5 0 0 0 0 0 0
CLUSTER 2
CLUSTER 3
CLUSTER 4
CLUSTER 5
CLUSTER 6
120
B¼lage E. Exacte methode Type
Orders
Totale afstand (km)
Totale rijtijd (min)
Totale lading (paletten)
De cit (paletten)
25 18 2 1 24 29 33 1 33 33 33 33 1
8 15 31 32 9 4 0 32 0 0 0 0 32
G G V V G G V V V V V V V
19, 21, 114 20, 23, 25 22 24 103 104, 115 139 143 153 155 156 158 161
344 36 340 436 290 306 372 364 612 542 526 670 514
502 527 499 633 397 483 511 577 867 847 757 941 677
G G G G G V V V V
65, 138 137, 147, 164 141, 142 145, 149, 150, 166 148, 159, 160, 165 151 152 169 170
113 153 204 217 190 190 548 504 502
237 307 318 434 371 275 785 569 731
31 32 33 33 33 33 33 18 15
2 1 0 0 0 0 0 15 18
V G V V G V G V V
1 12, 34, 44, 84, 85 29 30 35, 36, 38, 39, 40, 41 37 73 100 118
68 84 68 68 73 68 76 78 68
149 240 159 159 253 159 164 161 167
33 32 33 33 30 33 23 33 33
0 1 0 0 3 0 10 0 0
V G G G G V G G V G V
26 28 42, 45, 46 47, 48 59, 72, 122, 123 61 64 71, 131 86 126, 127 135
CLUSTER 7
CLUSTER 8
CLUSTER 9
0 81 33 0 79 32 54 171 31 50 165 33 30 160 31 0 81 33 0 35 10 50 153 28 50 131 33 30 130 28 50 131 33 TOTAAL 14674 26356 2531 GEMIDDELDE 166,75 299,50 28,76 GEMIDDELDE AFWIJKING 128,88 166,40 5,56 Tabel E.2: Overzicht werklijst exacte methode - orders met losadres TransWest omgedraaid
121
0 1 2 0 2 0 23 5 0 5 0 373 4,24 5,56
F | Personeeltoewijzing In tabelF.1 is de volledige toewijzing van de ritten gepland door de heuristische oplossingsmethode aan de chaueurs opgenomen.
Rit
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
Zonder 1 als losadres Chaueur Score
50 11 41 5 19 13 7 8 2 25 26 20 52 43 10 54 45 55 49 31 28 21 38 36 51 9 53 1 16 48 56 18 34 14
30000 1000 1900 0 900 900 0 0 0 900 900 900 30000 1000 1900 30000 1000 30000 30000 900 1000 1000 0 1000 30000 1650 30000 0 900 30000 30000 0 1000 0
Orders met 1 als losadres omgedraaid Rit Chaueur Score
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
122
65 25 8 49 72 9 13 71 28 79 68 59 6 20 67 19 38 66 55 35 10 7 5 52 31 53 2 26 24 51 16 74 1 70
30000 0 0 30000 30000 900 900 30000 1000 30000 30000 30000 900 900 30000 900 0 30000 30000 1000 900 0 0 30000 900 30000 0 0 0 30000 900 30000 0 30000
B¼lage F. Personeeltoewijzing Rit
Zonder 1 als losadres Chaueur Score
35 22 36 32 37 29 38 44 39 47 40 24 41 37 42 6 43 33 44 3 45 17 46 35 47 27 48 39 49 40 50 30 51 46 52 42 53 4 54 23 55 15 56 12 Objectief Gemiddelde score Gemiddelde afwijking
0 0 1000 0 1000 1000 1000 1000 0 0 1000 1000 2750 0 0 1000 600 600 1000 0 1000 0 302700 5405,36 7905,42
Orders met 1 als losadres omgedraaid Rit Chaueur Score
35 54 30000 36 45 1000 37 36 1000 38 60 30000 39 22 0 40 37 1000 41 42 600 42 11 1000 43 40 0 44 56 30000 45 46 600 46 47 1000 47 18 0 48 27 2000 49 81 30000 50 12 0 51 33 0 52 14 0 53 39 0 54 73 30000 55 62 30000 56 61 30000 57 48 30000 34 1000 76 30000 60 30 1000 61 78 30000 62 80 30000 63 63 30000 64 57 30000 65 21 1000 66 82 30000 67 15 1000 68 69 30000 69 23 0 70 75 30000 71 44 0 72 32 0 73 3 0 74 64 30000 75 29 1000 76 50 30000 77 43 2000 78 4 1000 79 77 30000 80 41 1000 81 58 30000 82 17 1000 Objectief 1,08E+06 Gemiddelde score 13139,02 Gemiddelde afwijking 14393,52 Tabel F.1: Personeelstoewijzing op basis van werklijsten heuristische methode
123
B¼lage F. Personeeltoewijzing Rit
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
Zonder 1 als losadres Chaueur Score
41 25 7 35 13 2 31 19 32 20 23 1 5 9 39 50 24 53 28 8 4 26 36 58 6 60 16 38 54 61 15 43 59 63 10 21 64 11 45 34 51 14 12 42 33 57 17 47 40 48 29 37 49 3
1000 0 0 1000 0 0 0 1000 1000 900 0 900 0 0 0 30000 0 30000 1000 0 1000 0 1000 30000 0 30000 0 0 30000 30000 1000 1500 30000 30000 1000 1000 30000 1000 1000 1900 30000 0 1000 1600 900 30000 2000 1000 0 30000 1000 1000 30000 900
Orders met 1 als losadres omgedraaid Rit Chaueur Score
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
124
49 23 2 47 11 5 64 9 13 19 10 25 87 28 59 66 53 88 69 70 80 38 43 75 81 54 1 24 52 8 39 36 6 26 16 78 7 84 62 56 45 50 15 27 31 20 77 57 63 65 74 22 44 14
30000 0 0 1000 1000 0 30000 0 0 0 900 0 30000 1000 30000 30000 30000 30000 30000 30000 30000 0 1500 30000 30000 30000 750 0 30000 0 0 1000 500 0 0 30000 0 30000 30000 30000 1000 30000 1000 1000 1000 0 30000 30000 30000 30000 30000 0 0 0
B¼lage F. Personeeltoewijzing Rit
Zonder 1 als losadres Chaueur Score
55 52 56 56 57 46 58 18 59 55 60 44 61 27 62 62 63 30 64 22 Objectief Gemiddelde score Gemiddelde afwijking
30000 30000 600 900 30000 0 2000 30000 1900 900 542900 8482,81 11431,01
Orders met 1 als losadres omgedraaid Rit Chaueur Score
55 17 1000 56 33 0 57 76 30000 58 4 1000 59 42 600 60 35 1000 61 3 0 62 46 600 63 58 30000 64 12 0 65 83 30000 67 30000 86 30000 68 82 30000 69 37 1000 70 18 0 71 79 30000 72 72 30000 73 55 30000 74 21 1000 75 48 30000 76 61 30000 77 73 30000 78 71 30000 79 60 30000 80 51 30000 81 29 1000 82 34 1000 83 68 30000 84 85 30000 85 40 0 86 41 1000 87 32 0 88 30 1000 Objectief 1,25E+06 Gemiddelde score 14225,57 Gemiddelde afwijking 14698,90 Tabel F.2: Personeelstoewijzing op basis van werklijsten exacte methode
125
Bibliogra e [1] Amy Cohn, Sarah Root, Carisa Kymissis, Justin Esses, and Niesha Westmoreland. Scheduling medical residents at boston university school of medicine.
Interfaces,
39
(3):186195, 2009.
[2] Andreas T Ernst, Houyuan Jiang, Mohan Krishnamoorthy, Bowie Owens, and David Sier.
An annotated bibliography of personnel scheduling and rostering.
Annals of
Operations Research, 127(1-4):21144, 2004. [3] Miguel Andres Figliozzi. A route improvement algorithm for the vehicle routing problem with time dependent travel times.
In
Proceeding of the 88th Transportation
Research Board Annual Meeting CD rom, January 2009. [4] Asvin Goel. Vehicle scheduling and routing with drivers' working hours.
Transporta-
tion Science, 43(1):1726, 2009. [5] Asvin Goel. Truck driver scheduling in the european union.
Transportation Science,
44(4):429441, 2010.
[6] Asvin Goel and Leendert Kok. E cient scheduling of team truck drivers in the european union.
Flexible services and manufacturing journal, 24(1):8196, 2012.
[7] J.J. Gromicho, A.L. van Hoorn, J.M.J. Kok, and Schutten. The exibility of restricted dynamic programming for vrps.
[8] Thomas Hambach.
Beta Working Paper, 266:114, 2010.
http://www.rdlt.com/postcodes-van-alle-gemeentes-van-belgie-
met-gps-coordinaten. Internet, juni 2007.
126
Bibliogra e [9] JN Hooker. Toward uni cation of exact and heuristic optimization methods.
Inter-
national Transactions in Operational Research, pages 12, 2013. [10] Frank Ivis. Calculating geographic distance: Concepts and methods.
NESUG,
pages
19, 2006.
[11] Anil K Jain. Data clustering: 50 years beyond k-means.
Pattern Recognition Letters,
31(8):651666, 2010.
[12] Silke Jütte, Marc Albers, Ulrich W Thonemann, and Knut Haase. Optimizing railway crew scheduling at db schenker.
Interfaces, 41(2):109122, 2011.
[13] Brian Kallehauge, Jesper Larsen, Oli BG Madsen, and Marius M Solomon.
routing problem with time windows.
Vehicle
Springer, 2005.
[14] AL Kok, EW Hans, JMJ Schutten, and WHM Zijm. A dynamic programming heuristic for vehicle routing with time-dependent travel times and required breaks.
Flexible
services and manufacturing journal, 22(1-2):83108, 2010. [15] AL Kok, EW Hans, and JMJ Schutten. Optimizing departure times in vehicle routes.
European Journal of Operational Research, 210(3):579587, 2011. [16] Marta Mesquita, Margarida Moz, Ana Paias, José Paixão, Margarida Pato, and Ana Respício. A new model for the integrated vehicle-crew-rostering problem and a computational study on rosters.
Journal of Scheduling, 14(4):319334, 2011.
[17] Belgische Federale Overheid. Verkeer en vervoer - goederenvervoer over de weg in 2011, 2012.
URL
http://statbel.fgov.be/nl/modules/publications/statistiques/
verkeer_vervoer/verkeer_en_vervoer_-_Goederenvervoer_over_de_weg_-_ 2011.jsp. [18] Artur Pessoa, Eduardo Uchoa, M Poggi de Aragao, and Rosiane Rodrigues.
Algo-
rithms over arc-time indexed formulations for single and parallel machine scheduling problems.
Report RPEP, 8(8):124, 2008. 127
Bibliogra e [19] Nima Safaei, Dragan Banjevic, and Andrew KS Jardine. Workforce-constrained maintenance scheduling for military aircraft eet:
a case study.
Annals of Operations
Research, 186(1):295316, 2011. [20] Marius M Solomon. Algorithms for the vehicle routing and scheduling problems with time window constraints.
Operations research, 35(2):254265, 1987.
[21] Ingmar Steinzen, Vitali Gintner, Leena Suhl, and Natalia Kliewer. A time-space network approach for the integrated vehicle-and crew-scheduling problem with multiple depots.
Transportation Science, 44(3):367382, 2010.
[22] Mario Vanhoucke.
Applied Operations Research.
Academia Press/Gent, 2013.
[23] Instituut wegTransport en Logistiek België. Itlb-permanente studies-kerncijfers van het goederenvervoer over de weg, februari 2013. URL
http://www.itlb.be/.
[24] Gang Yu, Julian Pachon, Benjamin Thengvall, Darryal Chandler, and Al Wilson. Optimizing pilot planning and training for continental airlines. 264, 2004.
128
Interfaces, 34(4):253
L¼st van guren 2.1
Plannen van nationale ritten in TransWest . . . . . . . . . . . . . . . . . .
11
7.1
Overzicht heuristiek - niveau 1 . . . . . . . . . . . . . . . . . . . . . . . . .
42
7.2
Plannen van een groupagerit - niveau 2 . . . . . . . . . . . . . . . . . . . .
43
8.1
Initiële clusters - 19 nodes per cluster . . . . . . . . . . . . . . . . . . . . .
67
8.2
Algoritme clustervorming . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
8.3
Opdeling in 7 clusters - orderlijst zonder 1
69
8.4
Opdeling in 9 clusters - orderlijst omgedraaid
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
70
10.1 Vergelijking tussen verschillende oplossingsmethodes: totale afstand en rijtijd 85 10.2 Situering oplossing exacte en heuristische methode . . . . . . . . . . . . . .
86
10.3 Vergelijking tussen verschillende oplossingsmethodes: gemiddelde lading en de cit
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
D.1
Dichtste locatie berekenen - niveau 3
D.2
Startuur berekenen - niveau 3
87
. . . . . . . . . . . . . . . . . . . . .
107
. . . . . . . . . . . . . . . . . . . . . . . . .
108
D.3
Overschrijden capaciteit nagaan - niveau 3 . . . . . . . . . . . . . . . . . .
109
D.4
Overschrijden tijdslimiet nagaan - niveau 3 . . . . . . . . . . . . . . . . . .
110
D.5
Aankomst binnen openingsuren klant nagaan - niveau 3 . . . . . . . . . . .
111
D.6
Volgende mogelijkheid zoeken - niveau 3
112
129
. . . . . . . . . . . . . . . . . . .
L¼st van tabellen 1.1
Binnenlands en internationaal vervoer voor eigen rekening en voor rekening van derden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2
6
Indeling van het totaal vervoer (binnenlands + internationaal) per hoofdstuk van de eenvormige goederennaamlijst voor de vervoerstatistieken (NST2007) - Jaar 2011
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.3
Hoeveelheid vervoerde goederen in België voor belangrijkste vervoerswijzen
8
1.4
Indeling van het vervoer in 1 000 ton en in 1 000 tonkilometer volgens de soort van voertuigen en de aard van het vervoer - Jaar 2011
. . . . . . . .
9
2.1
Overzicht objectieven en constraints relevante literatuur . . . . . . . . . . .
22
2.2
Overzicht oplossingsmethodes - onderscheid exact vs. heuristisch . . . . . .
25
3.1
Overzicht probleemgroottes relevante case studies
. . . . . . . . . . . . . .
26
5.1
Overzicht verschillende lefactoren per gewest
. . . . . . . . . . . . . . . .
36
6.1
Samenvatting werklijst TW - orders die lossen bij TW weggelaten
. . . . .
38
6.2
Samenvatting werklijst TW - orders die lossen bij TW omgedraaid . . . . .
39
7.2
Samenvatting werklijst heuristiek - orders die lossen bij TW weggelaten . .
49
7.3
Samenvatting werklijst heuristiek - orders die lossen bij TW omgedraaid
49
7.4
Samenvatting werklijst heuristiek - orders die lossen bij TW omgedraaid en
.
ritten gecombineerd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
130
51
L¼st van tabellen 8.1
Vergelijking Premium Solver 2014 - Gurobi 5.6.2 voor model 10 nodes . . .
56
8.3
Evaluatie verschillende penalty-waarden
. . . . . . . . . . . . . . . . . . .
61
8.4
Overzicht nieuwe tijdsintervallen . . . . . . . . . . . . . . . . . . . . . . . .
65
8.5
Vergelijking aantal nodes per cluster
66
8.6
Samenvatting werklijst exacte methode - orders die lossen bij TW weggelaten 72
8.7
Samenvatting werklijst exacte methode - orderlijst met orders die lossen bij
. . . . . . . . . . . . . . . . . . . . .
TW omgedraaid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.8
Samenvatting werklijst exacte methode - orderlijst met orders die lossen bij TW weggelaten - excl. onvolledige volle lading . . . . . . . . . . . . . . . .
8.9
73
74
Samenvatting werklijst exacte methode - orderlijst met orders die lossen bij TW omgedraaid - excl. onvolledige volle lading
. . . . . . . . . . . . . . .
74
9.1
Samenvatting resultaten toekenning personeel o.b.v. heuristische planning .
79
9.2
Samenvatting resultaten toekenning personeel o.b.v. heuristische planning .
80
10.1 Overzicht resultaten verschillende oplossingsmethoden . . . . . . . . . . . .
83
B.1
Afstanden van TransWest tot klanten . . . . . . . . . . . . . . . . . . . . .
100
B.2
Vermenigvuldiging rechtlijnige afstand met factoren . . . . . . . . . . . . .
101
B.3
Afwijkingen tabel B.2 t.o.v. tabel B.1 . . . . . . . . . . . . . . . . . . . . .
101
C.1
Overzicht werklijst opgemaakt door TransWest - orders met losadres TransWest weggelaten
C.2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
103
Overzicht werklijst opgemaakt door TransWest - orders met losadres TransWest omgedraaid
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
105
D.1
Overzicht werklijst heuristiek - orders met losadres TransWest weggelaten .
114
D.2
Overzicht werklijst heuristiek - orders met losadres TransWest omgedraaid
116
D.3
Overzicht werklijst heuristiek met rittencombinaties - orders met losadres TransWest omgedraaid . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
131
117
E.1
Overzicht werklijst exacte methode - orders met losadres TransWest weggelaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
E.2
119
Overzicht werklijst exacte methode - orders met losadres TransWest omgedraaid
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
121
F.1
Personeelstoewijzing op basis van werklijsten heuristische methode . . . . .
123
F.2
Personeelstoewijzing op basis van werklijsten exacte methode . . . . . . . .
125
