Optimalisatie van distributie- en transportplanning bij Palm Gijs Hompes
Promotor: Prof. Dr. El-Houssaine Aghezzaf Begeleiders: Steven De Schrijver (Möbius), Alex De Smet (Palm) Masterproef ingediend tot het behalen van de academische graad van Master in de ingenieurswetenschappen: bedrijfskundige systeemtechnieken en operationeel onderzoek
Vakgroep Technische Bedrijfsvoering Voorzitter: prof. Dr. El-Houssaine Aghezzaf Faculteit Ingenieurswetenschappen en Architectuur Academiejaar 2011-2012
Optimalisatie van distributie- en transportplanning bij Palm Gijs Hompes
Promotor: Prof. Dr. El-Houssaine Aghezzaf Begeleiders: Steven De Schrijver (Möbius), Alex De Smet (Palm) Masterproef ingediend tot het behalen van de academische graad van Master in de ingenieurswetenschappen: bedrijfskundige systeemtechnieken en operationeel onderzoek
Vakgroep Technische Bedrijfsvoering Voorzitter: prof. Dr. El-Houssaine Aghezzaf Faculteit Ingenieurswetenschappen en Architectuur Academiejaar 2011-2012
"De auteur(s) geeft(geven) de toelating deze masterproef voor consultatie beschikbaar te stellen en delen van de masterproef te kopiëren voor persoonlijk gebruik. Elk ander gebruik valt onder de beperkingen van het auteursrecht, in het bijzonder met betrekking tot de verplichting de bron uitdrukkelijk te vermelden bij het aanhalen van resultaten uit deze masterproef." Voor elk gebruik wenst de auteur via email gecontacteerd te worden. "The author(s) gives (give) permission to make this master dissertation available for consultation and to copy parts of this master dissertation for personal use. In the case of any other use, the limitations of the copyright have to be respected, in particular with regard to the obligation to state expressly the source when quoting results from this master dissertation." The author wishes to be contacted through email before every use of this paper.
Gent, 4 juni 2012 De auteur,
Gijs Hompes
The most beautiful thing we can experience is the mysterious. It's the source of all true art and science.
ALBERT EINSTEIN
Voorwoord Er zijn een aantal personen die ik wens te bedanken om me te steunen tijdens het schrijven van deze thesis. Allereerst zijn verontschuldigingen op zijn plaats voor de mensen wiens kostbare tijd ik in beslag nam terwijl ik er zeker van ben dat ze op zo'n momenten wel iets beters te doen hadden. Het schrijven van een thesis is geen eenmanswerk. Zonder een team van bekwame begeleiders en personen in mijn kennissenkring zou deze thesis nooit zijn geworden wat hij nu is. Allereerst gaat mijn dank uit naar mijn promotor, Prof. Dr. El-Houssaine Aghezzaf voor zijn begeleiding, intellectuele en wetenschappelijke inbreng zowel gedurende de jaren die hij mij doceerde als bij de thesis. Met hem werd de thesis beetje bij beetje een concreet werk met waardevol onderzoek en nieuwe inzichten voor realistische routeringsproblemen. Dankzij de professionele input van de personen die altijd ter beschikking stonden bij Möbius, het bedrijf dat deze thesis begeleidde, ben ik steevast verder geraakt. Speciale dank gaat daarom ook uit naar Steve De Schrijver voor het begeleiden van de thesis en het contacten leggen met Palm, An De Wispelaere voor haar eerlijke en waardevolle inbreng betreende de implementatie van het algoritme en tot slot Dimi De llet om steevast ter beschikking te staan om me van zowel antwoord als advies te voorzien voor kleine en grote problemen. Graag wens ik collega en kameraad Pauwel De Smedt te bedanken om samen met mij dit ongelofelijke avontuur aan te gaan. Toen we onze samenwerking startten denk ik dat geen van beiden ooit had kunnen denken dat het afwerken van een thesis zo'n turbulent gegeven kon zijn.
Ik dank Pauwel voor zijn tomeloze inzet, zijn scherpzinnige geest en
enthousiasme. Als laatste bedank ik iedereen die me nauw aan het hart ligt. Vanzelfsprekend zijn mijn ouders en mijn zus hierbij. Het is ongelofelijk hoe ze me blijven steunen door dik en dun, helpen en begeleiden doorheen mijn leven. Als afsluiter bedank ik de studentenvereniging VTK. Dankzij VTK leerde ik onnoemelijk interessante mensen kennen die me in Gent een ongelofelijke tijd bezorgden. Gijs Hompes Juni 2012
Optimalisatie van distributie- en transportplanning bij Palm Exact model en metaheuristisch DSH algoritme voor grootschalige TDVRPTW door
Gijs Hompes Promotor: prof. dr. El-Houssaine Aghezzaf Begeleider: Steven De Schrijver Masterproef ingediend tot het behalen van de academische graad van Master in de ingenieurswetenschappen: bedrijfskundige systeemtechnieken en operationeel onderzoek Vakgroep Technische Bedrijfsvoering Voorzitter: prof. dr. El-Houssaine Aghezzaf Faculteit Ingenieurswetenschappen en Architectuur Academiejaar 2011-2012 Samenvatting U
In deze thesis wordt onderzoek gedaan naar tijdsafhankelijke routegeneraties, kortweg TDVRP. Na een grondige literatuurstudie wordt een benaderend wiskundig model voorgesteld en getest op kleine cases van een tiental klanten. Een nieuw zeer performant metaheuristisch algoritme - het DSH algoritme - wordt voorgesteld en uitgewerkt. Ook deze metaheuristiek wordt op dezelfde cases getest om de performantie na te gaan. Invloed van belangrijke parameters wordt besproken om uiteindelijk routes te genereren voor een grote dataset van Palm Breweries. Hoofdstuk 1 geeft de motivatie, de achtergrond en de algemene inleiding voor deze thesis Hoofdstuk 2 bespreekt algemene info rond Palm, waarvan later een businesscase opgelost wordt. Hoofdstuk 3 geeft een uitgebreide literatuurstudie rond TSP, VRP, VRPTW en TDVRP. Dit werd voor een groot deel samen met Pauwel De Smedt geschreven. Hoofdstuk 4 geeft een gedetailleerde omschrijving van het probleem voor deze thesis. Hoofdstuk 5 onderzoekt een exact wiskundig model voorgesteld om een TDVRP probleem op te lossen. Dit model werd ontwikkeld in samenwerking met P. De Smedt. Hoofdstuk 6 werd ook samen met P. De Smedt tot stand gebracht en geeft een metaheuristisch algoritme (DSH algoritme) om grote TDVRPs aan te pakken. Hoofdstuk 7 onderzoekt de invloeden op enkele belangrijke parameters. Hoofdstuk 8 geeft de dataverwerking en een heuristische tijdsafhankelijke oplossing voor de businesscase van Palm Breweries. Hoofdstuk 9 bespreekt mogelijk toekomstig onderzoek met deze thesis als basis. Hoofdstuk 10 formuleert een algemene conclusie op dit thesisonderzoek. Sleutelwoorden: TDVRP, VRPTW,TDVRPTW, DSH algoritme, metaheuristiek U
U
Optimalisatie van distributie- en transportplanning bij Palm Mathematical model and metaheuristic DSH algorithm for large scale TDVRPTW Gijs Hompes & Pauwel De Smedt Supervisor(s): prof.dr. El-Houssaine Aghezzaf, Steven De Schrijver
Abstract - This thesis paper discusses the extension of the VRP to a TDVRPTW. This means that the travel time between two customers is dependent on the starting time at that customer. Soft time windows are taken into account, as well as the capacity of the trucks. . This paper will propose a mathematical model and a powerful metaheuristic algorithm to deal with large scale routing problems with a realistic time dependent nature. Keywords - DSH algorithm, metaheuristics, TDVRPTW
I. INTRODUCTION Transportation is an essential aspect in every industry. Transportation and routing problems will only gain importance in the future since there is an increasing need for efficient and realistic routing and cost calculations to deal both with the everyday customer delivery and the strategic transportation decisions. II. LITERATURE REVIEW When implementing time dependent travel data, FIFO problems can arise. These can be solved by linearising the travel times, or by changing the travel time model to a speed model, as described by Ichoua [1] and Donati [2]. Exact model for TDVRP are a lot less discussed than the ordinary VRP, despite that some decent research has already been conducted. Malandraki [3] and Daskin [4] first described this problem. More advanced exact model can be found with Figliozzi [5] and Lieckens [6]. Figliozzi [7] discusses an exact model for the TDVRPTW with soft time windows. The exact model for TDVRPTW discussed in this paper had the Haghani model [8] as a basis. III. MATHEMATICAL MODEL The developed model is based on the work of Haghani [8] and represents a robust interval model to generate routes and calculate costs for time dependent VRP with soft time windows. First a finetuned exact mathematical model was developed to calculate the gap between the mathematical model and the DSH algorithm. For bigger testcases the robust interval model is used. The model is stated as follows:
A. Model First the collections are discussed: D represents all customers, S all starting depots and E all ending depots, De=DUE, T=DUS, Da=DUEUS, K are all vehicles. The parameters are as follows: f is the fixed cost for a truck, pw the penalty for early arrival, pd de penalty for late arrival, RC is the traveling cost per minute, Zc the service cost per minute. qi is the demand, Qk the truck capacity, [Ai,Li] is the time window, αk the starting interval for a truck. Ci is the service time, [α,ω] is the planning period. The decision variables: xmij is 1 when a truck goes from i to j in interval m, vki is 1 if node i gets visited by truck k, ci is the truck content when leaving i, ui is a random variable for subtour elimination, tij is the exact starting time driving from i to j, is the travel time, wi and di the time a truck arrives early or late. The complete model is stated as follows:
+ + + + ∈ ∈
∈ ∈
= 1 " ∈ #, " ≠ &, ' ∈ (
∈
∈
= 1 & ∈ ), " ≠ & ∈
∈
(1) (2) (3)
* ≥ ,-. − 1 + 0 -. " ∈ # , ' ∈ (
(4)
* ≤ -. 2. " ∈ 45
(5)
* ≥ 0 + * + , 6 − 17 " ∈ 8 , & ∈ 49 , " ≠ &
(6)
: 15<= − 1> + ? ≤ 15@ & ∈ ), " ≠ &
(7)
= 1 & ∈ 4, " ≠ &
(8)
∈
.∈3
∈
∈
A −
A∈
∈
= 0 & ∈ 4, " ≠ &, & ≠ ℎ
(9)
-. = 1 " ∈ 45
(10)
≤ 1 − -. + -. " ∈ 8, & ∈ 49 , " ≠ &, ' ∈ (
(11)
≥ D − 15<= − 1> + & ∈ 4, " ≠ &
(12)
≥ 0 & ∈ 4
(13)
≥ 15<= − 1> + + − E & ∈ 4, " ≠ &
(14)
≥ 0 & ∈ 4
(15)
.∈3
∈
∈
G. Hompes and P. De Smedt and are with the Faculty of Industrial Engineering and Operations Research of Ghent University (UGent), Gent, Belgium. E-mail:
[email protected] and
[email protected]
∈
15<= − 2> A < : 15<= − 1> + + ?
A∈
∈
15<= −
A∈
1> A
(16)
& ∈ 49 , " ≠ &, & ≠ ℎ
≥ : 15<= − 1> + + ? ∈
& ∈ 49 , " ≠ &, & ≠ ℎ
+ ≤ 1 " ∈ 4, & ∈ 4, " ≠ &
H − H + I ∗ ≤ I − 1 " ∈ 4, & ∈ 4, " ≠ &
(17)
(18) (19)
Here (1) represents the objective function, (2) makes sure a truck starts at his depot during his starting interval, (3) assure that every truck ends in the depot, (4)-(6) are the capacity constraints, (7) assures trucks arrive before the end of the planning period, (8) will see that every client is visited exactly once, (9) is the continuity constraint, (10) makes sure every node is visited by exactly one vehicle, with (11) two adjacent nodes are visited with the same truck, (12)-(15) calculate the early and late time, (16)-(17) are the arrival time constraints, (18) makes sure a route between two clients in never two ways, (19) is the subtour elimination constraint. B. Tests To evaluate the performance of the proposed model, several tests were set up. Firstly a test was set up comparing the proposed interval model with a refined model. Tests were condoned on a set of five datasets carefully selected to represent reality. For further information regarding the outcome of these tests see section V were results and gaps are discussed. IV. METAHEURISTIC ALGORITHM Sung et al. [9] introduces a way to adapt the Dijkstra algorithm to time dependency. This is used as a base to develop an advanced algorithm called the DSH algorithm (De Smedt - Hompes). The code of the DSH algorithm is depicted in code 6.1. A GRASP parameter is introduced to enhance the algorithm to a metaheuristic algorithm. The DSH algorithm is executed using a Java implementation. The flexibility of the algorithm allows to vary the starting time of the trucks, the service time of the customers, the time windows and the truck capacity. Multiple tours per truck can be performed and multiple depots can be handled when every depot has it's predetermined customers. A. Code In the following pseudo code, the DSH method is explained. There exist 2 collections,U(nserved) and S(erved) containing all customers and the served customer pool which is initially empty. As long as there are customers in the unserved pool the algorithm keeps looking for the next feasible customer to service. A feasible node is defined by taking into account the constraints posed by the problem: truck capacity, time windows. Labels d(j) are given to possible next nodes to be able to find the best next node set.
V. GAPS To verify the performance of the DSH algorithm in comparison with the mathematical refined model, both the model and the algorithm were run with the same small testcases and the same parameters, which means a one minute accuracy and a fixed starting time of all trucks. All gaps were lower than 1,5% and positive, which means that the exact model is better, but the DSH algorithm is very performing. Since the robust interval model is used in further testcases, the gap between the refined model and the robust interval model is calculated. Since all the gaps are smaller than 1%, it is allowed to use the robust interval model to calculate further gaps for the DSH algorithm performance checks. When the robust interval is compared to the full strength DSH algorithm, it is noted that in almost all cases the DSH algorithm performs better and a lot faster. This is caused by the higher accuracy and the variable starting times for the DSH algorithm, which are features that the robust interval model cannot offer. Case
No. Refined Model DSH Nodes Fixed Start 1A 5 437,9 438 1B 7 540,4 548 1C 8 663,4 664 1 9 698,0* 705 Table 1: Gap between refined model and DSH fixed start. Case
No. Refined Interval Nodes Model 1A 5 437,9 438,00 1B 7 540,4 545,00 1C 8 663,4 664,00 1 9 698* 702,68 Table 2:Gap between refined model and interval model. * This test ran out of memory after running 17 hours. Hence, the result is not final. Case
Interval DSH DSH Model Fixed Start Variable Start 1 702,78 705 700 2 665,23 663 659 3 629,80 624 621 4 799,90 804 792 5 665,13 674 657 Table 3: Gap between Interval model and DSH with fixed and variable start.
VI. INFLUENCE OF PARAMETERS The three most important parameters are discussed: the GRASP value, the starting time of the trucks and the service time at the customers. The GRASP 1-2-33-4 is used, which means that the GRASP parameter can decide for selecting four different nodes. It is observed that a parameter value between 0,7 and 1 gives the best results. When the starting time is investigated, it is noted that in almost every testcase it is best to start the trucks as late as possible, while making sure that every customer is visited during the planning peri period. It is logical that the traveling time and the costs are directly proportional to the service time at the customers. VII. DEVELOPED SOFTWARE To implement the aforementioned DSH algorithm a software package was developed (as seen in figure 1). The problem can be modeled by defining a set of customers and trucks in a set of specialized files. All parameters are freely adjustable to guarantee a best possible outcome. Out of the software contains a routing schedule per inputfile and a total cost of this routing.
routing schedules. Another really appealing field is the RTRT TDVRPTW where it would become possible to update the routing schedule with real-time time congestion information. It is possible to implement the service of different goods or a heterogeneous fleet, which implies extra constraints. The current DSH algorithm doesn’t support clients with a demand higher than truck capacity, this can be b expanded in future research. Soft time windows can be introduced into the DSH algorithm as it already is implemented In the mathematical interval model. Efficient use of data structures and databases is essential to improve route generation speeds with DSH. D A parallel route processing is a possibility that was already tried, but one should find a solution to relieve some of the extra pressure on the databases cause by this parallel implementation. X. CONCLUSION This thesis paper proposes both an exact and a robust mathematical model to generate routes for TDVRPTW’s. Apart from that, a metaheuristic algorithm was developed, called the DSH algorithm. This is a high per formant and fast algorithm taking time dependency, time windows, truck capacity, starting timee and multiple routes into account. This powerful tool allows companies to both generate day to day scheduling routings in a realistic way and calculate yearly transportation costs while avoiding congestion. This results in a realistic and efficient cost calculation alculation that can be used as a solid baseline to take strategic decisions concerning the transportation of the company. REFERENCES [1]
[2]
[3] Figure 1: DSH routing software
VIII. BUSINESS CASE PALM The algorithms and techniques described in V to VII are used to handle the business case of Palm Breweries. Investment benchmarks were made to see if investing in extra trailers would be viable. Preliminary results based on a testset of 50 days and the 100 largest customer base denied that executing such an investment would be a good plan. It was noted that by implementing a shorter service time at the depot overall cost would rise with 0,5%. This value could point out that investing in extra trails would have no effect due to the complicated nature of traffic and routing with time dependency. Further strategic decisions such as the best start times for a truck should be and can be taken on a day to day basis. IX. FUTURE RESEARCH Starting from this thesis paper,, there are some very interesting and challenging expansions possible. Once the TDVRPTW routing has been generated, one could find a time dependent route optimization algorithm, for example time dependent local search heuristics. It could be possible to ma make the program assign customers to a depot when dealing with a multidepot problem in order to generate even more efficient
[4]
[5]
[6]
[7]
[8]
[9]
Ichoua, S., Gendreau, M., & Potvin, J.-Y. J. (2003). Vehicle dispatching with time-dependent dependent travel times. European Journal of Operational Research, 144(2), 379-396. doi:10.1016/S0377-2217(02)00147-9 doi:10.1016/S0377 Donati, a, Montemanni, R., Casagrande, N., Rizzoli, a, & Gambardella, L. (2008). Time dependent vehicle routing problem with a multi ant colony system. European Journal of Operational Research, Research 185(3), 1174-1191. doi:10.1016/j.ejor.2006.06.047 Malandraki, C. (1989). Time Dependent Vehicle Routing Problems: Formulations, Solution Algorithms and Computational Experiments. Evanston, Illinois: Northwestern University Malandraki, C., & Dasking, M. (1992). Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms. Transportation Science, 26(3). Transportation Science. Figliozzi, M. A. (n.d.). The Impacts of Congestion C on Time-definitive Urban Freight Distribution Networks CO 2 Emission Levels : Levels results from a case study in Portland , Oregon. Review Literature And Arts Of The Americas, (December 2009), 1-27. 1 Lieckens, K., & Vandaele, N. (2007). Reverse logistics logist network design with stochastic lead times. Computers & Operations Research, 34(2), 395-416. doi:10.1016/j.cor.2005.03.006 Andres Figliozzi, M. (2012). The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution ution algorithm, and solution characteristics. Transportation Research Part E: Logistics and Transportation Review, 48(3), 616-636. Haghani, A., & Jung, S. (2005). A dynamic vehicle routing problem with time-dependent dependent travel times. Computers & Operations Operatio Research, 32(11), 2959-2986. doi:10.1016 Kiseok Sung, Michael G. H. Bell, and Soondal Park. Shortest paths in a network with time-dependent dependent _oow speeds. European Journal Of Operational Research, 121:32_39, 2000.
Inhoudsopgave 1 Inleiding
1
1.1
Achtergrond . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Indeling van de thesis
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.3
Motivatie
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2 Bedrijfsvoorstelling 2.1
Geschiedenis PALM
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
PALM Breweries in 2012 . . . . . . . . . . . . . . . . . . . . . . . . .
4
Möbius . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.1.1 2.2
3
3 Literatuurstudie
5
3.1
Introductie
3.2
Traveling salesman problem
3.3
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
. . . . . . . . . . . . . . . . . . . . . . . . . . .
6
3.2.1
Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
3.2.2
Oplossingsmethodes
. . . . . . . . . . . . . . . . . . . . . . . . . . .
6
Vehicle Routing Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
3.3.1
Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
3.3.2
Soorten VRP's
8
3.3.3
Exacte oplossingsmethodes
. . . . . . . . . . . . . . . . . . . . . . .
9
3.3.4
Heuristieken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
3.3.4.1
Clarke and Wright . . . . . . . . . . . . . . . . . . . . . . .
11
3.3.4.2
Gillet and Milller (Sweep) . . . . . . . . . . . . . . . . . . .
13
3.3.4.3
Tabu Search Algoritme
. . . . . . . . . . . . . . . . . . . .
14
3.3.4.4
Genetisch algoritme
. . . . . . . . . . . . . . . . . . . . . .
15
3.3.4.5
Local search heuristieken
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
i
. . . . . . . . . . . . . . . . . . .
15
ii
INHOUDSOPGAVE
3.3.4.6
GRASP . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
VRPH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
Vehicle routing problems met tijdsvensters . . . . . . . . . . . . . . . . . . .
18
3.4.1
Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
3.4.1.1
Wiskundig model
. . . . . . . . . . . . . . . . . . . . . . .
19
3.4.1.2
Functie van doelfunctie en de restricties . . . . . . . . . . .
20
3.3.5 3.4
3.5
3.4.2
Exacte oplossingsmethodes
. . . . . . . . . . . . . . . . . . . . . . .
21
3.4.3
Heuristieken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
Vehicle routing problem met dynamische reistijden
. . . . . . . . . . . . . .
22
3.5.1
Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
3.5.2
FIFO
23
3.5.3
Exacte oplossingsmethodes
3.5.4
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
3.5.3.1
Verzamelingen
. . . . . . . . . . . . . . . . . . . . . . . . .
24
3.5.3.2
Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
3.5.3.3
Beslissingsvariabelen . . . . . . . . . . . . . . . . . . . . . .
26
3.5.3.4
Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
3.5.3.5
Functie doelfunctie en restricties
. . . . . . . . . . . . . . .
27
Heuristieken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
3.6
Vendor Managed Inventory
. . . . . . . . . . . . . . . . . . . . . . . . . . .
29
3.7
Inventory Routing Problem
. . . . . . . . . . . . . . . . . . . . . . . . . . .
29
4 Probleemstelling
33
4.1
Algemene beschrijving
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
4.2
Beschikbare gegevens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
4.2.1
34
Aanpak van het probleem
. . . . . . . . . . . . . . . . . . . . . . . .
5 Wiskundige modellering
37
5.1
Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
5.2
Gegevens
37
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.1
Verzamelingen
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
5.2.2
Parameters
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
5.2.3
Beslissingsvariabelen . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
5.2.3.1
38
Binair . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
INHOUDSOPGAVE
5.3
5.4
5.5
iii
5.2.3.2
Integer
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
5.2.3.3
Float
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
Exact wiskundig model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
5.3.1
Model en restricties
. . . . . . . . . . . . . . . . . . . . . . . . . . .
39
5.3.2
Uitleg bij de restricties . . . . . . . . . . . . . . . . . . . . . . . . . .
40
5.3.3
Intervalmodel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
5.3.3.1
Benaderend wiskundig model . . . . . . . . . . . . . . . . .
44
5.3.3.2
Uitleg bij doelfunctie en de restricties
. . . . . . . . . . . .
45
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
5.4.1
Dataverwerking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
5.4.2
Model
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
Testen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
5.5.1
Testcase 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
5.5.2
Overige testcases . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
5.5.3
Testcases met jnere intervallen . . . . . . . . . . . . . . . . . . . . .
50
Modellering in AMPL
6 Metaheuristiek
53
6.1
Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
6.2
Het DSH-Algoritme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
6.2.1
54
6.3
6.4
Metaheuristiek
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Implementatie van DSH-algoritme
. . . . . . . . . . . . . . . . . . . . . . .
55
. . . . . . . . . . . . . . . . . . . . . .
55
6.3.1
Dataverwerking en databases
6.3.2
Postcodeclusters
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
6.3.3
Postcodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
6.3.4
Oracle MySQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
6.3.5
Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
6.3.6
DSH in Java
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
6.3.7
Opensource mapping & routing software . . . . . . . . . . . . . . . .
62
6.3.8
Parameters
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
6.3.9
Verloop van het programma . . . . . . . . . . . . . . . . . . . . . . .
65
Testen van DSH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
67
6.4.1
68
R
Testcase 1: Vaste starttijd . . . . . . . . . . . . . . . . . . . . . . . .
iv
INHOUDSOPGAVE
6.5
6.4.2
Alle testcases: vaste starttijd
. . . . . . . . . . . . . . . . . . . . . .
68
6.4.3
Testcase 1: variabele starttijd . . . . . . . . . . . . . . . . . . . . . .
69
6.4.4
Alle testcases: variabele starttijd
. . . . . . . . . . . . . . . . . . . .
69
Bepalen van de gap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
6.5.1
Gap tussen AMPL met ver jnde intervallen en heuristiek
. . . . . .
71
6.5.2
Gap tussen AMPL ver jnd en benaderend intervalmodel . . . . . . .
71
6.5.3
Gap tussen AMPL en heuristiek: vaste starttijden
72
6.5.4
Gap tussen AMPL en heuristiek: variabele starttijden
6.5.5
Gap tussen heuristiek met vaste en variabele starttijden
. . . . . . . . . . . . . . . . . . . . . . . . .
7 Invloed van de parameters 7.1
GRASP parameter
α
73 73
77
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
77
7.1.1
GRASP 1-2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
77
7.1.2
GRASP 1-2-3-4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
78
7.1.3
GRASP 1-2-R-R
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
78
7.2
Starttijden van de trucks . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
79
7.3
Servicetijden bij de klanten
79
. . . . . . . . . . . . . . . . . . . . . . . . . . .
8 Routering voor Palm Breweries
83
8.1
Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83
8.2
Assumpties
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83
8.3
Kostenparameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
84
8.4
Aanpak
84
8.5
Impact van het aankopen van extra opleggers
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
85
9 Future research
87
10 Conclusie
89
A Testcases in AMPL
91
A.1
Testcase 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
A.2
Testcase 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
A.3
Testcase 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
93
A.4
Testcase 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
93
INHOUDSOPGAVE
v
B Testcases met DSH B.1
97
DSH met vaste starttijden . . . . . . . . . . . . . . . . . . . . . . . . . . . .
97
B.1.1
Testcase 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
97
B.1.2
Testcase 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
97
B.1.3
Testcase 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99
B.1.4
Testcase 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99
C DSH met variabele starttijden
103
C.1
Testcase 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
C.2
Testcase 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
C.3
Testcase 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
C.4
Testcase 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
D Invloed van de starttijd op DSH
109
D.1
Testcase 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
D.2
Overige testcases
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
vi
INHOUDSOPGAVE
Lijst van afkortingen 3PL
Third Party Logistics
3W
Wie,Wat en Wanneer
ACS
Ant Colony System
API
Application Programming Interface
CVRP
Capacitated Vehicle Routing Problem
DSH
De Smedt-Hompes
DSN
Data Source Name
FIF
Fleet Information File
FIFO
First In First Out
GRASP
Greedy Randomized Adaptive Search Procedure
GUI
Graphical User Interface
IDE
Integrated Developer Environment
IP
Integer Programming
IRP
Inventory Routing Problem
JDBC
Java Database Connectivity
MACS
Multi Ant Colony System
MDVRP
Multi Depot Vehicle Routing Problem
NP-hard
Non-deterministic Polynomial-time hard
ODBC
Open Database Connectivity
PVRP
Perioded Vehicle Routing Problem
RDBMS
Relational database management system
SDVRP
Split Delivery Vehicle Routing Problem vii
viii
INHOUDSOPGAVE
SERR
Selection, Extraction, Recombination, Reallocation
SQL
Structured Query Language
SVRP
Stochastic Vehicle Routing Problem
TDVRP
Time Dependent Vehicle Routing Problem
TDVRPTW Time Dependent Vehicle Routing Problem with Time Windows TSP
Traveling Salesman Problem
VMI
Vendor Managed Inventory
VRP
Vehicle Routing Problem
VRPH
Vehicle Routing Problem Heuristics
VRPPD
Vehicle Routing Problem with Pickup and Delivery
VRPSF
Vehicle Routing Problem with Sattelite Facilities
VRPTW
Vehicle Routing Problems with Time Windows
Hoofdstuk 1
Inleiding 1.1
Achtergrond
Deze thesis is een uitbreiding op de thesis die vorig academiejaar werd geschreven door de Ir. Joost Denys. Zijn thesis behandelde Optimalisatie van de distributie- en transportplanning bij PALM Breweries.
Het uiteindelijke doel, het optimaliseren van de distributie-
en transportplanning bij PALM Breweries, blijft behouden.
In deze thesis tracht men
enkele extra restricties toe te voegen die er voor moeten zorgen dat de resultaten nog waarheidsgetrouw ' worden. Het systeem waarbij PALM zelf gaat beslissen wanneer een klant een levering krijgt, zijnde VMI (Vendor Managed Inventory) wordt behouden. Het voorraadbeheer bij de klanten blijft de verantwoordelijkheid van PALM Breweries. De uitbreidingen van deze thesis ten opzichte van de thesis van vorig jaar betrekken zich op de volgende onderwerpen:
1. Rekening houden met tijdsvensters, zijnde de openingsuren van de klant bij levering.
2. Rekening houden met de congestietijden om de routes van de transportmiddelen te bepalen
(a) Hoe kan men les vermijden in de planning? (b) Niet structurele les laat men achterwege. (c) Wat is de impact van de starttijden van de chaueurs op een planning die rekening houdt met congestie?
3. Is het interessant om in eigen transport middelen te investeren?
(a) Kan het laden en lossen op de site van Palm o ine gebeuren door te investeren in extra opleggers? (b) Hoe kan deze thesispaper helpen voor strategische routeringsbeslissingen?
1
2
1.2
HOOFDSTUK 1.
INLEIDING
Indeling van de thesis
De thesis is als volgt ingedeeld.: In hoofdstuk 2 wordt er informatie gegeven over PALM als bedrijf en welke producten de brouwerij produceert. In hoofdstuk 3 wordt er aan de hand van een grondige literatuurstudie een diepgaand begrip ontwikkeld van de theorie die nodig is om een oplossing te creëren voor het thesisonderwerp zoals aangegeven in sectie 1.1. In hoofdstuk 4 wordt een gedetailleerde beschrijving van de probleemstelling geformuleerd. In hoofdstuk 5 wordt een exact en benaderend wiskundig model voorgesteld om het TDVRP (Time Dependent Vehicle Routing Problem) op te lossen. Dit model werd volledig ontwikkeld in samenwerking met Pauwel De Smedt. Dit in het kader van zijn thesis die ook het TDVRP behandelt bij Recupel. Ook hoofdstuk 6 werd in samenwerking met P. De Smedt tot stand gebracht. Het resultaat van deze samenwerking is een metaheuristiek die in staat is grotere TDVRPTW cases op te lossen. In hoofdstuk 7 worden, in samenwerking met P. De Smedt de verschillende testcases en de invloeden op enkele parameters besproken. Hoofdstuk 8 geeft een heuristische tijdsafhankelijke oplossing voor de grote dataset van de Palm case. In hoofdstuk 9 wordt kort besproken welk voortgaand onderzoek kan uitgevoerd worden met deze thesis en de thesis van G. Hompes als basis. Hoofdstuk 10 sluit af met een algemene conclusie.
1.3
Motivatie
In de reële wereld komen vele bedrijven en instanties in aanraking met problemen gerelateerd tot het transporteren van mensen, goederen of informatie. Deze set van problemen wordt in literatuur uitvoerig besproken onder de noemer routing-problemen. Het type probleem is niet beperkt tot de transportsector alleen, zo kan onder meer het transport van goederen in een productieomgeving in of tussen verschillende fabrieken. Onder druk van een steeds toenemende globalisatie zal transport, waar dan ook, enkel maar belangrijker worden in de toekomst. Uit een onderzoek [1] blijkt dat tegen 2030 de totale vervoerde tonnage op de weg met 51% zou stijgen (referentiejaar 2005). Voor andere transportmiddelen zoals zee- ,luchtvaart en pijpleidingen zou dit 70% bedragen. De hoeveelheid tonkm veroorzaakt door wegtransport zou dalen van 76% naar 71%.
Wegtransport blijft dus steeds verantwoordelijk voor het
grootste aandeel aan vervoer. Uit voorgaande cijfers blijkt dat elk type van probleem, routing en planning, belangrijk zijn en een belangrijk deel van de tak Operations Research uitmaakt. Indien de mogelijkheid bestaat om zelfs maar een marginale verbetering te implementeren kan dit, gezien de schaal van de transportsector, leiden tot grote besparingen, een vermindering van de belasting van het wegennet, een vermindering van geluidsoverlast en emissies.
Hoofdstuk 2
Bedrijfsvoorstelling 2.1
Geschiedenis PALM
Voor het ontstaan van PALM Breweries[2] keert men terug naar het jaar 1747, het jaar waarin Anne Theresia Cornet de huisbrouwerij van haar vader omdoopte tot de dorpsbrouwerij van Steenhuel. De brouwerij kende toen nog de naam De Hoorn, een naam die pas in 1975 veranderd zou worden naar PALM. De Hoorn maakte van bieren met hoge gisting en nam zich voor trouw te blijven aan deze specialiteit. Zelfs na een totale vernieling tijdens de eerste wereldoorlog, een tijdperk waarin pilsbieren enorm opkwamen, bleef de brouwerij bij de heropbouw met veel overtuiging vasthouden aan de continuïteit en de eigenheid van zijn streekbier, dit boven de eventuele groeikansen van pilsbieren. Arthur Van Roy was de verantwoordelijke voor deze opmerkelijke keuze. Arthur Van Roy gaf in 1929 het bier gebrouwen te Steenhuel de speciale merknaam : Speciale PALM, als teken van overwinning van zijn hoge gistingsbier op het steeds populairdere pils. Ter gelegenheid van het 200jarig bestaan van de brouwerij, danken Arthur en zijn zoon Alfred de klanten in 1947 met een eindejaarscadeau, de Dobbel PALM. Dit werd een traditie die zich nog steeds elk jaar voordoet. Doordat brouwerij De Hoorn meer en meer bekend stond voor de productie van hun PALM bier, veranderde het zijn naam in 1975 naar Brouwerij PALM. Het was ook dan dat het logo uitgebreid werd met een Brabants trekpaard, dit om duidelijk te maken dat PALM een Brabantse specialiteit met traditie is. Brouwerij PALM blijft groeien en zal in het jaar 1989 de grens oversteken en Nederland overtuigen van de kwaliteit van hun bier. Enkele jaren later zal de brouwerij ook nog 2 andere vestigingen overnemen, zo is er in 1998 de overname van de Brouwerij Rodenbach en in 2001 de overname van de Brouwerij De Gouden Boom te Brugge. Hierdoor kan de brouwerij zijn aanbod uitbreiden met Rodenbach bier, Brugse stadsbieren en de abdijbieren van Steenbrugge. In 2003 vindt een tweede naamsverandering plaats waarbij Brouwerij PALM N.V. wordt omgedoopt tot de naam waaronder we de brouwerij vandaag de dag kennen, PALM Breweries N.V.. 3
4
HOOFDSTUK 2.
BEDRIJFSVOORSTELLING
2.1.1 PALM Breweries in 2012 Momenteel is PALM Breweries nog steeds een Belgische onafhankelijke, familiale brouwersgroep die als enige ter wereld Belgische authentieke bieren brouwt volgens de vier aloude gistingswijzen: hoge, gemengde, spontane en lage gisting. Dit doen ze op de volgende locaties: Palm te Steenhuen, Rodenbach te Roeselare en Boon te Lembeek. Deze drie sites zijn samen goed voor een gezamenlijke productiecapaciteit van 1 miljoen hl, een geconsolideerde omzet van 50 miljoen euro en om en bij de 250 werknemers.
2.2
Möbius
Deze thesis werd uitgevoerd in samenwerking met consultancy bureau Möbius. Dit bedrijf werd opgericht in 1997 door professor dr. ir. Hendrik Vanmaele als een spin-o van Gent Universiteit. De core businessen van Möbius zijn: Supply Chain Management, Business Process Management en Business Process ICT Architects [3].
Deze thesis bevindt zich
vooral in het luik "Supply Chain Management". Meer informatie over het thesisonderwerp kan teruggevonden worden in het hoofdstuk 4.
Hoofdstuk 3
Literatuurstudie 3.1
Introductie
Zoals aangetoond in Analyse van de Verkeerscongestie in België [4] zal het in de toekomst enkel complexer worden om deel te nemen aan het verkeer. De transportsector staat met zekerheid voor een grote set problemen die men zal moeten oplossen om competitief te blijven.
Uit de analyse van De Federale Overheidsdienst mobiliteit en verkeer blijkt uit
een simulatie voor het jaar 2020, die op basis van data uit 2007 werd opgesteld, dat de gemiddelde lelengte in het Gewest Vlaanderen met 55% zou toenemen, van 103 km in 2007 tot 160 in 2020. Het aantal voertuigverliesuren zou toenemen van 4334 naar 6358, een toename van 47%. Uit de gegevens in tabel 3.1 valt af te leiden dat het algemene leleed enkel maar zal toenemen in België. Gezien de immer hogere brandstofprijzen en emissies als gevolg van de toenemende congesties, heeft een modern bedrijf er alle nut bij zo optimaal mogelijk zijn transport te organiseren. In de studie [4] wordt voorspeld dat er in België 107,2% meer brandstof zou worden gebruikt. Dit ten gevolge van de hogere congestiegraad. Een lagere gemiddelde snelheid ten gevolge van deze hogere congestiegraad zal leiden tot een hoog verbruik. Door de lagere gemiddelde snelheid is er immers een hogere frequentie aan stoppen en vertrekken. Het type probleem dat gepaard gaat met het vinden van een optimale oplossing om tegemoet te komen aan bovenstaande problemen is een probleem van het type VRP (Vehicle Routing Problem) VVU
Filelengte
VVU
Filelengte
(vtgu/u)
(km)
(vtgu/u)
(km)
Regio
2007
2007
2020
2020
Gewest Vlaanderen
4334
103
6358
160
Gewest Wallonië
21
1700
15
2242
Gewest Brussel
198
-
335
-
Agglomeratie Anwerpen
387
16
565
25
Agglomeratie Gent
122
11
173
17
Agglomeratie Luik
47
5
86
9
Tabel 3.1:
Voertuigverliesuren en lelengtes op het wegennet in 2007 en 2020 voor de
verschillende regio's [4]
5
6
HOOFDSTUK 3.
LITERATUURSTUDIE
Een probleem waarbij men enkel de routering bestudeert van het systeem bevat enkel een geogra sche component. tijdscomponent.
Een probleem waar een planning aan te pas komt, bevat een
De problemen voorgesteld in literatuur zijn vaak een vereenvoudiging
van real-life problemen.
Hoewel er door de vereenvoudigingen verschillende parameters
en beperkingen worden weggelaten (bijvoorbeeld beperkingen ten gevolge van wetten, de natuur of vakbonden) zijn de resultaten van de onderzoeksmodellen, hun eigenschappen en hun resultaten vaak gebruikt als basis voor de kern van praktische toepassingen.
Er
bestaan zodoende een set van modellen die door de wetenschappelijke gemeenschap als zijnde relevant worden beschouwd. Een overzicht van deze modellen wordt hier besproken in functie van hun relevantie voor deze thesis.
3.2
Traveling salesman problem
3.2.1 Inleiding Het probleem van de handelsreiziger, in de literatuur standaard TSP (Traveling Salesman Problem) genoemd, is één van de meest onderzochte problemen in het operationeel onderzoek en de computerwetenschappen. Op Figuur 3.1 kan men een gra sche weergave van het TSP terugvinden. Dit probleem is een onderdeel van de grafentheorie en kan kortweg als volgt geformuleerd worden [5]:
"Als er n steden gegeven zijn die een handelsreiziger moet bezoeken, samen met de afstand tussen ieder paar van deze steden, vind dan de kortste weg die kan worden gebruikt, waarbij iedere stad precies eenmaal wordt bezocht.".
Figuur 3.1: Een typische oplossing van een TSP [6]
Het TSP een NP-hard(Non-deterministic Polynomial-time hard) probleem. rechtstreeks oplossen voor
n
locaties
n!
Aangezien
combinaties vergt, is dit computertechnisch quasi
onmogelijk om dit voor meer dan 25 locaties uit te uitvoeren.
Ter illustratie: In 1998
berekenden wiskundigen van de Universiteit van Princeton de exacte oplossing voor 15.112 steden in Duitsland. De oplossing kostte 22,6 jaar computertijd en de berekeningen werden op een netwerk van 110 processors uitgevoerd [7]. Meer algemene info over het TSP kan men terugvinden op verscheidene websites gewijd aan dit populaire probleem [8].
3.2.2 Oplossingsmethodes Onderzoekers hebben reeds een veelvoud aan algoritmes voorgesteld om het TSP te kunnen oplossen.
Zowel exacte algoritmes, metaheuristieken als heuristieken werden hierop
3.3.
VEHICLE ROUTING PROBLEM
7
toegepast. Populaire algoritmes hierbij zijn de Cutting Plane Method [9], de methode via three-opt tours [10, 11, 12] ook te zien in guur 3.2, Shortest Spanning Subtree [10] en het Ant Colony System algoritme [13]. Verdere optimalisaties kunnen worden uitgevoerd door onder andere simulated annealing [13, 12].
Figuur 3.2: 3-opt move
3.3
Vehicle Routing Problem
3.3.1 Inleiding Een VRP, wordt gezien als een uitbreiding op het TSP. Dit probleem werd voor het eerst geïntroduceerd door Dantzig en Ramser in 1959 [14] en kan worden omschreven als[15]:
"The problem of designing optimal delivery or collection routes from one or several depots to a number of geographically scattered cities or customers, subject to side constraints." Een VRP, waarvan een oplossing geïllustreerd in guur 3.3, zoekt een optimale routering voor bepaalde leverings- of ophaalpunten in een bepaalde geogra sche omgeving, waarbij de routering eventueel moet voldoen aan enkele vooraf opgelegde restricties.
Figuur 3.3: Illustratie van een Vehicle Routing Probleem
Er is veel geschreven over verschillende oplosmethodes. Gezien een VRP NP-Hard is, is het meeste van het beschikbare onderzoek gericht op het ontwerpen van heuristieken om het VRP op te lossen. Een groot aantal van technieken is reeds beschreven, deze houden onder meer VRP met tijdsvensters en VRP met 'pickup and delivery'. Het is echter wel zo dat de meeste oplossingen voorgesteld voor VRP's er vanuit gaan dat de reistijden tussen twee punten (klant-klant of depot-klant) constant zijn.
Zoals eerder al vermeld in de
introductie stijgt het aantal les met zekerheid. Vooral op de piekuren (tijdens de morgen) komen klassieke VRP's met vaste reistijden in de tijd niet meer tegemoet aan de vraag om goede routevoorstellen te genereren. Reistijden tussen twee verschillende locaties, vooral
8
HOOFDSTUK 3.
LITERATUURSTUDIE
in stedelijke gebieden zijn vooral afhankelijk van de vertrektijden van de voertuigen. Deze verschillen met de klassieke VRP's worden onder andere in rekening gebracht in dit werk.
3.3.2 Soorten VRP's Er bestaan verschillende soorten van VRP's, De meest besproken types worden hierna voorgesteld. Verder zullen VRPTW (Vehicle Routing Problems with Time Windows) en de TDVRP gedetailleerder worden besproken gezien deze van belang zijn voor het oplossen van de thesis. De volgende VRP's bestaan:
Capaciteitsrestricties
Bij een VRP met capaciteitsrestrictie, kortweg CVRP, hebben de
vrachtwagens een bepaalde capaciteit [16].
Ophaling en afhaling
De VRPPD (Pickup and Delivery) houdt in dat sommige locaties
ophaalpunten, sommige a everpunten en sommige beide zijn.
Hierbij moet steeds
rekening gehouden worden met de verschillende goederen zodat de beperking van het volume en gewicht van de vrachtwagen in rekening wordt gebracht.
Periodieke bezoeken
Bij de PVRP kan levering bij bepaalde locaties enkel op een aantal
vastgelegde dagen gebeuren [17].
Meervoudige levering
Een SDVRP wordt gede nieerd als een VRP met een al dan niet
heterogene vloot waarbij de klanten worden bediend door verschillende wagens met elk een deel van de lading in plaats van dat één wagen met de volledige lading de klant bevoorraadt. Dit wordt enkel toegepast als de kosten op deze manier gedrukt kunnen worden[18].
Ongekende vraag
Wanneer de vraag niet gekend is moet de VRP aangepast worden met
stochastische data. Men spreekt dan van een stochastic-VRP, kortweg SVRP.
Meerdere depots
Wanneer het netwerk uit meer dan één depot bestaat, heeft men te
maken met een MDVRP [19].
Klanten kunnen bediend worden uit meer dan één
depot. Dit wil zeggen dat een vrachtwagen een verschillend startpunt en eindpunt kan hebben.
Bevoorrading
Soms kan een vrachtwagen opnieuw bevoorraad worden tijdens een ronde.
Hier is dan sprake van een VRPSF [20]. Er wordt gebruik gemaakt van zogenaamde satellietdepots (Satellite Facilities) zodat het niet telkens nodig is voor de vrachtwagen om opnieuw naar het centrale depot te rijden.
Tijdsvensters 6, 22].
Wanneer de klanten tijdsvensters hebben betreft het een VRPTW [21,
Dit wil zeggen dat vrachtwagens enkel binnen een vooraf opgegeven tijd
kunnen leveren of ophalen bij een klant. Meer uitleg over VRPTW wordt gevonden in paragraaf 3.4.
Dynamisch reistijden
Wanneer de reistijd tijdsafhankelijk is, spreekt men over TDVRP
[23, 24, 25, 26]. Dit type probleem bepaalt het grootste deel van deze thesis. Verdere uitleg vindt men onder sectie 3.5.
3.3.
VEHICLE ROUTING PROBLEM
9
3.3.3 Exacte oplossingsmethodes Een VRP is een IP (Integer Programming) probleem dat in de categorie valt van de NPhard problemen.
De doelfunctie bestaat standaard uit een kostenminimalisatie of een
serviceverbetering. Een model voor een VRP moet een oplossingsruimte voorstellen aan de hand van een aantal restricties, zoals:
•
Aan de vraag van alle klanten moet tegemoet gekomen worden.
•
Het aantal knopen/klanten toegewezen aan elk voertuig wordt al dan niet begrensd door een vooropgesteld maximum.
•
De maximum kost (afstand en of rijtijd) per voertuig mag de maximale toelaatbare waarde niet overschrijven.
•
De lading van elk voertuig moet kleiner of gelijk zijn dan de maximale capaciteit van het voertuig.
Deze restricties vormen het voornaamste verschil tussen een TSP en een VRP. In 1981 werd een oplossing gevonden via Dynamic Programming met State Space Relaxation [27] en met de Branch-and-Bound methode. omvang van ongeveer 25 klanten.
Deze oplossing was haalbaar tot de bescheiden
In 1985 werd de Branch-and-cut methode toegepast,
waarbij gebruik gemaakt werd van k-shortest spanning trees en paths [28]. Hiermee werd een oplossing bekomen tot 60 klanten. Nadien hebben nog enkele andere onderzoekers de Branch-and-cut methode op een aangepaste manier toegepast, zodat het aantal klanten vergroot kon worden [29, 30]. Hieronder wordt in detail een exacte methode weergeven via een VRP IP-formulering, beschreven door Kulkami en Bhave in 1985 [31] waarbij wordt gewerkt met een Multi-depot VRP.
M
Het aantal depots
N
Het aantal klanten
V
Het aantal beschikbare voertuigen
Pk
Capaciteit van voertuig
Tk
Maximaal toegelaten kost per route van voertuig k.
Qi
Vraag in node
cij
Kost om van
xijk
1 indien het paar
i
k
i. naar
j
i, j
te rijden.
deel uitmaakt van de route van voertuig
0 in alle andere gevallen
k
10
HOOFDSTUK 3.
LITERATUURSTUDIE
Het model is als volgt geformuleerd:
M inimaliseer Z =
NX +M NX +M NX +M i=1
j=1
cij xijk
(3.1)
k=1
De voorgaande doelfunctie 3.1 is onderhevig aan volgende restricties:
NX +M X V
xijk = 1
j = 1, 2, ..., N
(3.2)
xijk = 1
i = 1, 2, ..., N
(3.3)
j=1 k=1 NX +M X V j=1 k=1 NX +M
xihk −
NX +M
i=1 NX +M
xhjk = 0
k = 1...V, h = 1...N + M
(3.4)
j=1
Qi
i=1
NX +M
xijk ≤ Pk
k = 1...V
cij xijk ≤ Tk
k = 1...V
(3.5)
j=1
NX +M NX +M i=1
j=1
NX +M
N X
(3.6)
xijk ≤ 1
k = 1...V
(3.7)
xijk ≤ 1
k = 1...V
(3.8)
i=N +1 j=1 NX +M
N X
j=N +1 i=1
yi − yj + (M + N )
V X
xijk ≤ N + M − 1
1 ≤ i ≤ M + N, i 6= j
(3.9)
k=1
De functie van de doelfunctie en de verschillende restricties zijn:
3.1
De kosten van de route minimaliseren.
3.2
Elke klant wordt bediend door exact één voertuig.
3.3
Zie 3.2.
3.4
Zorgt ervoor dat het voertuig vertrekt uit de node waar hij is toegekomen.
3.5
Zorgt ervoor dat de capaciteitsrestrictie van de vrachtwagen in ere wordt gehouden.
3.6
Zorgt er voor dat de maximale kost per route niet overschreden kan worden.
3.7
Elke vrachtwagen mag vanuit een depot maar naar maximaal één klant vertrekken.
3.3.
VEHICLE ROUTING PROBLEM
3.8
11
Elke vrachtwagen mag vanuit een klant maar naar maximaal één depot vertrekken.
3.9
Staat in voor de subtour eliminatie.
De restrictie ter eliminatie van de subtours kan op deze manier compacter worden weergegeven:
ui − uj + (M + N )
V X
xijk ≤ N + M − 1
1 ≤ i 6= j ≤ M + N − 1
(3.10)
k=1
3.3.4 Heuristieken In de loop der jaren hebben enkele onderzoekers gezocht naar algoritmen en heuristieken om een VRP op te lossen [39].
De oplossingswijze bestaat standaard uit 2 fasen.
De
eerste fase construeert een mogelijk tour, de tweede fase optimaliseert de bekomen tour. De meeste heuristieken werden afgeleid uit de heuristieken ontwikkeld voor de TSP. Het eerste en meeste bekende heuristisch algoritme voor de VRP werd in 1964 ontwikkeld en staat bekend als het Clark & Wright Savings Algorithm [32].
Tien jaar later werd het
Sweep Algorithm ontwikkeld door Gillet en Miller [33]. Verschillende inter- en intra-route methodieken werden voorgesteld zoals simulated annealing en tabu search [34]. Eén van de meest recente ontwikkelingen op basis van de VRP heuristieken is de SERR-methodiek (Selection, Extraction, Recombination, Reallocation), geïntroduceerd in 2004 [35]. Hieronder worden de twee bekendste algoritmes gedetailleerder besproken: het Clark & Wright Savings Algorithm en het Sweep Algorithm.
3.3.4.1 Clarke and Wright Clarke en Wright [32]hebben Clark & Wright als eerste een oplossing gevonden voor het CVRP [83]. Aangezien dit een heuristiek is bekomt men uiteraard geen optimale oplossing, maar hetgeen verkregen wordt door dit algoritme zijn zeer goede oplossingen. Verschillende producten moeten aan de klanten geleverd worden vanuit een bepaald depot. Hiervoor zijn een aantal vrachtwagens beschikbaar, elk met hun speci eke capaciteit. Elke vrachtwagen wordt hierbij gebruikt, legt een route af waarbij het een aantal klanten bedient en keer uiteindelijk terug naar zijn depot. De klanten moeten toegewezen worden aan de routes, de volgorde en de vrachtwagens die hierbij gebruikt worden zijn van belang. Het doel is uiteraard de minimalisatie van de totale transportkosten, waarbij men rekening moet houden met een aantal restricties zoals capaciteit, klantenvraag en de verplichting dat alle klanten bediend moeten worden. Dit algoritme steunt op het "savings" concept, zoals weergegeven in guur 3.4.
Dit wil
zeggen dat er een kostenbesparing gezocht wordt door twee routes te herleiden naar één route.
12
HOOFDSTUK 3.
LITERATUURSTUDIE
Figuur 3.4: Schema van het savings concept
Op de linkerkant van guur 3.4, deel a, is te zien dat de nodes
ien j
bezocht worden door
van het depot (=0) naar i te gaan, om daarna terug te keren en een gelijkaardige route uit te voeren om node
j
te bezoeken. Op de rechterkant, deel b, worden nodes
door van het depot naar node gaan, om uiteindelijk vanuit
j
i
i
en
j
bezocht
te gaan, daarna rechtstreeks van node i naar node j te
terug naar het depot te keren. De totaal afgelegde afstand
in deel a in duidelijk groter dan in deel b. Wanneer we dit uitdrukken in transportkosten krijgen we de volgende scenario's:
deel a =: Ca = C0i + Ci0 + C0j + Cj0
(3.11)
deel b = Cb = C0i + Cij + Cj0
(3.12)
Het is duidelijk dat deel a een grotere kost met zich meebrengt naar deel b. De besparing die gerealiseerd wordt door de route zoals in deel b te kiezen in plaats van in deel a bedraagt:
Sij = Ca − Cb = C0i + C0j − Cij De waarde van
Sij
(3.13)
kan soms heel groot zijn, zodat dit savings algorithm een heel perfor-
mante heuristiek is. De totale heuristiek bestaat uit drie verschillende stappen:
Stap 1
Bereken de besparingen
met
Sij
voor
∀i, j = 1...n
en
i 6= j .
Vorm de routes
(0, i, 0)
i = 1...n.
Stap 2
Rangschik de besparingen in dalende volgorde.
Stap 3
Beschouw twee routes bestaande uit de tak
deze twee routes samen tot de tak
(i, 0)
en
(0, j).
Indien
Sij > 0,
(i, j) en verwijder de takken (i, 0) en (0, j).
voeg
Hierbij
stelt 0 het depot voor.
De route uit stap 3 kan geïmplementeerd worden in de nieuwe routering indien ze voldoet aan alle voorwaarden. Deze stappen worden herhaald tot geen verdere verbetering meer mogelijk is. Er zijn twee manieren om de savings te gaan bekijken: serieel of parallel. Bij de seriële savings moet men telkens opnieuw starten van de top van de lijst (de lijst gemaakt in stap 2) wanneer een verbinding is gemaakt tussen een paar. Bij de parallelle savings
3.3.
VEHICLE ROUTING PROBLEM
13
moet men maar één keer door de lijst. Over het algemeen zal de parallelle methode een beter resultaat geven, maar omdat de parallelle methode meerdere routes tegelijk vormt zal dit naar alle waarschijnlijkheid rekenintensiever zijn en dus meer tijd vergen voor de computer. Deze afweging (tijd <> kwaliteit) moet zorgvuldig beredeneerd worden om op die manier de meest optimale oplossingsmethode te kiezen.
3.3.4.2 Gillet and Milller (Sweep) Een andere constructieve heuristiek werd voorgesteld door Gillet en Miller [33]. Het sweep algoritme dat werd voorgesteld werkt als volgt: Er wordt een halve rechte gede nieerd met als oorsprong het depot. Door deze halve rechte stapsgewijs te laten roteren worden er steeds nodes toegevoegd aan de route. De route wordt afgesloten als ze niet meer kan voldoen aan de restricties. Een schematische weergave van dit concept is te zien in guur 3.5. Een voorbeeld van het verloop van dit algoritme is weergegeven in guur 3.6. Het voorstel van Gillet en Miller is de basis van een groep heuristieken met de naam petale heuristieken.
Deze vertrouwen op initieel gegenereerde routes (dus niet alle mogelijke
routes) om tot een oplossing te komen.
Figuur 3.5: Constructie van mogelijke routes met behulp van een sweep. De capaciteit van de truck is Q=10.
Figuur 3.6: Verloop van een sweep heuristiek (richting tegen de klok in)[36].
14
HOOFDSTUK 3.
LITERATUURSTUDIE
We beschouwen alle klanten hun locatie ten opzicht van het depot als een set van poolcoördinaten
θi , ρ i .
Deze worden gerangschikt volgens oplopende hoek
θ.
De stappen die het
sweep-algoritme dan doorloopt zijn dan als volgt:
Stap 1
Initialisatie: beschouw een ongebruikt voertuig.
Stap 2
Constructie: start met een knoop met de kleinste poolhoek die nog niet verbonden
is aan de route en voeg knopen toe tot zolang de capaciteit van het voertuig dit toelaat.
Indien na overschrijden van de capaciteitsrestrictie nog knopen over zijn,
keer dan terug naar stap 1.
Stap 3
Optimalisatie:
elke geconstrueerde route kan geoptimaliseerd worden door het
oplossen van een TSP binnen elke route. Wissel knopen uit tussen naburige routes indien dit zou leiden tot kortere afstanden (m.b.v. local search methodes). De methode kan zowel met de klok als tegen de klok in worden uitgevoerd.
3.3.4.3 Tabu Search Algoritme Een gedetailleerde beschrijving over tabu search is te vinden in papers van Glover in 1989 [37] en 1990 [38]. Het tabu search algoritme onderzoekt de oplossingsruimte door bij elke iteratie te veranderen van de ene oplossing naar de beste oplossing in een subset van zijn omgeving [22]. In tegenstelling tot de klassieke heuristieken laat de tabu search toe dat de nieuwe oplossing minder optimaal is dan de huidige oplossing, dit om te vermijden dat reeds onderzochte paden opnieuw aangedaan worden en op die manier dus het blokkeren op lokale minima te vermijden. de voorwaarden.
Het is ook mogelijk dat een oplossing niet voldoet aan
De graad waarin deze oplossing afwijkt van een toegestane oplossing
wordt verwerkt door aan de doelfunctie een penalty toe te voegen. Om een oneindige lus tegen te gaan, worden alle reeds onderzochte oplossingen verboden en toegevoegd aan de zogenaamde "tabu" lijst. De vier belangrijke stappen voor het tabu search algoritme zijn:
Stap 1
Initieel is de tabu-lijst
T := 0.
het depot. Noem deze oplossing
Stap 2
De nieer
N (x),
x
Vorm heen-en-terug routes tussen de klanten en en zijn kost
de omgeving van
x,
F (x).
als de set van alle oplossingen die bekomen
worden door het toevoegen van een arbitraire knoop in zijn buurt aan de hand van de GENI [39] procedure. Als met de laatste kost in
Stap 3
N (x)\T = Ø ga dan naar stap 3.
N (x)\T
en stel
x := y .
Zoek anders de oplossing
Update de best gekende oplossing.
Indien het maximum aantal iteraties bereikt is, ga dan naar stap 4. Keer anders
terug naar stap 1 en stap 2.
Stap 4
Probeer de bekomen routes te verbeteren aan de hand van de local searches.
Er bestaan heel wat verschillende varianten van het tabu search algoritme zoals Osman's algorithm, Gendreau-Hertz-Laporte Taburoute Algorithm, Taillard's Algorithm en vele andere. Een overzicht hiervan kan men vinden in :[34].
3.3.
VEHICLE ROUTING PROBLEM
15
3.3.4.4 Genetisch algoritme Dit algoritme is een adaptieve zoekheuristiek, gebaseerd op de natuur en de populatiegenetica [40].
De basis hiervan werd in 1975 geïntroduceerd door Holland [41].
In een
genetisch algoritme evolueert een populatie van individuen, meestal gecodeerd als chromosomen, door het creëren van nieuwe generaties. Dit gebeurt door een iteratieve procedure tot wanneer voldaan is aan enkele vooropgestelde criteria. Deze criteria zijn bijvoorbeeld het maximaal aantal iteraties. De best gegenereerde chromosoom wordt dan gedecodeerd en daaruit wordt de optimale oplossing gehaald.
De creatie van zo'n nieuwe generatie
gebeurt volgens vier belangrijke stappen: representatie, selectie, recombinatie en mutatie. Eén van de meest bekende genetische algoritmes is de mierenkolonieoptimalisatie, beter bekend als het ACS (Ant Colony System) [13]. Deze optimalisatie is gemodelleerd op basis van de activiteit van een mierenkolonie. De zogenaamde "mieren" doorzoeken de mogelijke oplossingsruimte en komen zo tot een lokaal optimum.
Echte mieren laten feromonen
achter om de andere mieren te helpen bij het vinden van voedsel. In dit algoritme doen de kunstmatige mieren dit door registratie van hun lokaal optimum en de kwaliteit ervan, op die manier kunnen tijdens latere iteraties hierop nog verbeteringen gevonden worden, zoals ook te zien is op guur 3.7 en beschreven wordt door Donati [42].
F
F
N
N
N
1
2
3
F
b
a
Figuur 3.7: Illustratie van het ant colonoy system
3.3.4.5 Local search heuristieken Laporte [43] beschrijft twee types van verbeteringsheuristieken die toepasbaar zijn op het VRP: intra-route en inter-route. In beide gevallen gebeurt er post-optimalisatie (er wordt dus vertrokken van een bestaande set routes).
In het geval van inter-route verbetering,
worden de nodes verplaatst van de ene naar de andere route. In het geval van intra-route worden er 2-opt en of 3-opt moves gebruikt [44]. Laporte rapporteert dat de meest voorkomende operaties ter verbetering van de route het verplaatsen van nodes is van de ene naar
16
HOOFDSTUK 3.
LITERATUURSTUDIE
de andere routes. Een overzicht en beschrijving van dergelijke operaties wordt gegeven in sectie 3.3.4.5. Algemeen kan worden gezegd dat de performantie van klassieke heuristieken goed is, maar niet fantastisch. Ze worden dan ook best gebruikt als bouwblok binnen een metaheuristiek. Wanneer reeds een initiële oplossing gevonden is door een gekozen heuristiek, is het via lokale zoekoperatoren (local search) mogelijk om deze oplossing te verbeteren. De uiteindelijke uitkomst van een local search optimalisatie is heel erg afhankelijk van de initiële oplossing. De soort van lokale zoekoperator zal beslissen welke oplossing gegenereerd wordt.
Het
is deze oplossing die vervolgens vergeleken wordt met de huidige oplossing. Er zijn twee courante beslissingsmethoden om een nieuwe oplossing te selecteren: ofwel wordt de eerste verbetering geaccepteerd, ofwel wordt de beste verbetering geselecteerd. De zogenaamde " rst-accept" strategie selecteert de eerste buur die voldoet aan het acceptatiecriterium, terwijl de "best-accept" strategie alle buren onderzoekt die voldoen aan de criteria, en daaruit de beste optie selecteert [22]. Er zijn enkele zoekoperatoren waaruit kan gekozen worden voor een optimalisatie via local search [36]. Een overzicht:
One-Point Move:
verplaatst 1 node naar een andere route ( guur 3.8a)
Two-Point Move:
verwisselt 2 nodes van positie ( guur 3.8b)
Intra-Route Two-Opt Move:
verwijdert 2 verbindingen van een route en vervangt ze
door 2 nieuwe verbindingen in dezelfde route ( guur 3.8c)
Inter-Route Two-Opt Move:
verwijdert 2 verbindingen in 2 verschillende routes en
vervangt ze door 2 nieuwe verbindingen in deze 2 routes ( guur 3.8d)
Or-Opt Move:
verwijdert 2, 3 of 4 klanten van de oplossing en geeft deze een nieuwe
positie ( guur 3.8e)
Three-Opt Move:
verwijdert 3 verbindingen van een route en voegt 3 nieuwe verbindin-
gen toe zodat nog steeds aan alle restricties voldaan is. ( guur 3.8f )
Three-Point Move:
dit is een speciaal geval van het algoritme van Osman [34].
De
positie van twee opeenvolgende nodes wordt hier verwisseld met de positie van een derde node. ( guur 3.8g) Naast deze veel voorkomende zoekoperatoren zijn er ook nog enkele operatoren die minder vaak gebruikt worden maar toch het vermelden waard zijn [22]:
CROSS-exchange
Move: verwijdert 2 verbindingen in één route en 2 verbindingen in
een andere route, om daarna de verbindingen op een andere manier te leggen zodat de betrokken nodes veranderen van route. Op guur 3.9a is te zien dat verbinding
(j, l)
en verbinding
(i, k)
simultaan opnieuw in de routes wordt toegevoegd, en dat
de oriëntatie hierbij behouden blijft.
3.3.
VEHICLE ROUTING PROBLEM
17
Figuur 3.8: Lokale zoekoperatoren
GENI-exchange
Move: dit is een uitbreiding van de One-Point Move, waarbij een klant
ook kan toegevoegd worden tussen twee andere klanten in de dichtsbijzijnde route, ook al zijn deze klanten niet opeenvolgend. Op guur 3.9b is te zien dat klant i van de bovenste route ingevoegd wordt in de onderste route tussen
k
j
en
k.
Omdat
j
en
elkaar niet opvolgen in de onderste route moet deze gereorganiseerd worden.
Cyclic Transfer Move:
ingewikkelde zoekoperator die enkel heuristisch kan uitgevoerd
worden door de complexiteit ervan. Het basisidee is het gelijktijdig cyclisch transfereren van de klanten aangeduid met een witte cirkel, tussen de verschillende routes. Op guur 3.9c is dit het geval voor klanten
p in route 4.
a en c in route 1, f
en
j
in route 2, en
o en
Zij worden simultaan getransfereerd naar routes 2, 4 en 1 respectievelijk.
Voor meer details over deze operator wordt verwezen naar [22].
3.3.4.6 GRASP De GRASP (Greedy Randomized Adaptive Search Procedure) is een iteratief proces dat bestaat uit twee verschillende fasen: de constructiefase en de local search fase (die reeds werd uitgelegd in de vorige sectie). Er wordt gewerkt met een "best-accept" strategie voor de local search [40]. Op guur 3.10 is de pseudocode weergegeven voor een GRASP. Deze methode zal door de parameter
α
steeds een andere oplossing weergeven, waardoor
men hier kan spreken van een metaheuristiek.
Deze methode is adaptief aangezien de
18
HOOFDSTUK 3.
j
l j
i j –1
i–
i–
i–1
i –1
LITERATUURSTUDIE
l
i
i
k
k
k
k–
j+1
a m o e b1
d
j
k+1
l +1
–
l+1
i
j
4
e
k
j
f
a g c
o
3
n p
m
l
d b
2
n p
1 a
i c
h
b
j +1
k
k+1 k–
l
3 k
4 f
j
g2
i h
c Figuur 3.9: Minder courante lokale zoekoperatoren procedure grasp( f (·),g(·),maxitr,x∗ ) 1 x∗ = ∞; 2 for k = 1, 2, . . . , maxi t r do 3 construct(g(·),α,x); 4 local( f (·),x); 5 if f (x) < f (x∗ ) do 6 x∗ = x; 7 end if; 8 end for; end grasp
procedure construct(g(·),α,x) / 1 x = 0; 2 Initialize candidate set C; 3 while C = 0/ do 4 s = min{ g(t) | t ∈C} ; ¯s¯= max{ g(t) | t ∈C} ; 5 RCL = { s ∈C | g(s) ≤ s + α( s¯− s)} ; 6 ¯ the RCL; ¯ 7 Select s, at random, from
procedure local( f (·),N(·),x) 1 H = { y ∈N(x) | f (y) < f (x)} ; 2 while |H| > 0 do 3 Select x ∈H; 4 H = { y ∈N(x) | f (y) < f (x)} ; 5 end while; end local
8 x = x ∪{ s} ; 9 Update candidate set C; 10 end while; end construct
Figuur 3.10: Pseudocode GRASP
voordelen van elk element geüpdatet worden bij elke iteratie van de constructiefase. Op die manier worden de eecten duidelijk weergegeven tussen de verschillende oplossingen. Meer details rond deze methode kan men vinden in [40] en Resende [45].
3.3.5 VRPH De VRPH (Vehicle Routing Problem Heuristics) is een open source softwarebibliotheek ontwikkeld door Groër [36]. Deze bibliotheek is geschreven in C/C++ en gebruikt e ciënte object-georiënteerde datastructuren om initiële routeringsoplossingen te genereren, alsook verschillende local search heuristieken om deze initiële oplossing te optimaliseren.
Op
onderstaande guren zijn twee voorbeelden van een VRPH oplossing weergegeven. Figuur 3.11 toont een oplossing met het Clark & Wright algoritme, Figuur 3.12 illustreert de werking met het Sweep algoritme. Een groot voordeel van de VRPH is de exibiliteit tot uitbreiding van de bibliotheek. Op die manier kan men met enkele aanpassingen ook een VRP met tijdsvensters oplossen, of een VRP met meerdere depots gaan uitwerken. De VRPH is dus een exibele open source softwarebibliotheek die goede oplossingen kan leveren voor uiteenlopende VRP varianten.
3.4
Vehicle routing problems met tijdsvensters
3.4.1 Inleiding De VRPTW is een realistischere uitbreiding van de TSP en de VRP. Het komt erop neer dat er restricties worden toegevoegd zodat de optimale oplossingen ook voldoet aan tijds-
3.4.
VEHICLE ROUTING PROBLEMS MET TIJDSVENSTERS
199 nodes 9608.41
199 routes
199 nodes 4968.29
40
40
20
20
0
0
-20
-20
-20
0
20
-20
(a) Init ial Solut ion
19
124 routes
0
20
(b) Aft er 100 Merges 199 nodes 1408.80
17 routes
40
20
0
-20
-20
0
20
(c) Final Clarke-Wright Solut ion
Figuur 3.11: Illustratie VRPH met Clarck & Wright a) initiële oplossing b) na 100 iteraties c) uiteindelijke oplossing
vensters. In de realiteit kan men dit zien als een restrictie zodat de klanten bediend worden tijdens hun openingsuren. Een grondige uiteenzetting van dit probleem en mogelijke oplossingsmethoden wordt gegeven in de master thesis van Larsen [6].
3.4.1.1 Wiskundig model Minimaliseer de volgende doelfunctie [6]:
XXX
cij xijk
(3.14)
k∈V i∈N j∈N
Deze doelfunctie is onderhevig aan de volgende restricties:
XX
i∈C
xijk = 1
(3.15)
k∈V j∈N
X
di
X
xijk ≤ q
i∈C
j∈N
X
x0jk = 1
j∈N
k∈V
k∈V
(3.16)
(3.17)
20
HOOFDSTUK 3.
10 nodes
169.04
1 routes
100 nodes 1469.72
40
40
20
20
0
0
-20
-20
-20
0
20
-20
(a) 10 Nodes Added
0
LITERATUURSTUDIE
11 routes
20
(b) 100 Nodes Added 199 nodes 2730.61
22 routes
40
20
0
-20
-20
0
20
(c) Final Solut ion Figuur 3.12: Illustratie VRPH met het Sweep algoritme a) 10 nodes toegevoegd b) 100 nodes toegevoegd c) uiteindelijke oplossing
X
xihk −
i∈N
X
X
xhjk = 0
h ∈ C, k ∈ V
(3.18)
j∈N
xi,n+1,k = 1
k∈V
(3.19)
i∈N
sik + tij − K(1 − xijk ) ≤ sjk
i ∈ N, j ∈ N, k ∈ V
(3.20)
ai ≤ sik ≤ bi
i ∈ N, k ∈ V
(3.21)
xijk ∈ {0, 1}
i ∈ N, j ∈ N, k ∈ V
(3.22)
3.4.1.2 Functie van doelfunctie en de restricties 3.14
De doelfunctie is een kostenminimalisatiefunctie
3.15Zorgt
ervoor dat elke klant exact één keer bezocht wordt
3.16is
de capaciteitsrestrictie. Deze zorgt ervoor dat geen enkele vrachtwagen meer lading kan ophalen dan zijn capaciteit
3.17Deze
restrictie zorgt ervoor dat elke vrachtwagen vertrekt vanuit het depot 0
3.18Is
de continuïteitsrestrictie. Deze zorgt ervoor dat wanneer een vrachtwagen toekomt in node h, deze ook terug van daaruit moet vertrekken.
3.19Zorgt
ervoor dat elke vrachtwagen naal terug toekomt in het depot n+1
3.4.
VEHICLE ROUTING PROBLEMS MET TIJDSVENSTERS
21
3.20Verzekert dat een vrachtwagen niet in node j kan toekomen voor de som van de vertrektijd in node i en de reistijd tussen i en j. 3.21Zorgt
ervoor dat de tijdsvensters gerespecteerd worden
3.22Beperkt de beslissingsvariabele xijk tot een binaire waarde
Merk op dat een ongebruikt voertuig een "lege" route rijdt tussen
0
enn
+ 1.
Merk ook
op dat de VRPTW gereduceerd wordt tot een normale VRP wanneer restrictie 3.21 niet bindend is.
3.4.2 Exacte oplossingsmethodes De modellen die gebruikt worden om VRPTW's, zoals hetgeen in de voorgaande sectie, op te lossen zijn gebaseerd op de standaard VRP modellen. Terwijl men timewindows als een absolute restrictie kan beschouwen bestaat ook de mogelijkheid om deze als 'soft' te beschouwen. In bepaalde modellen bestaat de mogelijkheid toch buiten de tijdsframes te leveren, maar dan wordt er een extra kost of strafpunt toegewezen voor deze handeling.
Indien deze
mogelijkheid voorzien is in het model spreekt men over softe tijdsvensters [46]of algemeen VRPSTW (Vehicle Routing Problem with Soft Time Windows) De reden voor het toestaan van deze softe tijdsvensters is de mogelijkheid om aanzienlijke reducties door te voeren in het aantal voertuigen dat nodig is en tevens de totale afstand en tijd van alle routes te reduceren.
Door voor elke klant
i
een beginservicetijd
Ei en
een eindservicetijd
Li in
te stellen kan er een systeem van strafpunten worden opgezet waardoor enkel voor de geselecteerde klanten er al dan niet binnen het tijdsframe geleverd kan worden.
In [46]
wordt een straunctie als lineair beschouwd. Aan de hand van twee strafpuntcoë ciënten,
ai en bi wordt er gede nieerd wat de straf is per eenheid van tijd.
Indien het niet wenselijk is
dat de klant buiten zijn tijdsvenster beleverd mag worden, dan worden de strafpunten voor het toch leveren bij de klant op oneindig gezet. Een voorbeeld van een strafpuntenfunctie is weergegeven in vergelijking 3.23.
a (E − ti ) ∀ti < Ei i i Pi (ti ) = 0 ∀Ei ≤ ti ≤ Li b (t − L ) ∀t > L i i i i i
(3.23)
Er zijn vele varianten op dit strafpuntensysteem mogelijk. Bij een VRPTW is de mogelijkheid tot een onoplosbaar probleem steevast groter dan bij een VRPSTW. Het is exact deze eigenschap die het implementeren van een VRPSTW interessanter maakt voor toepassingen dan het VRPTW. Door een afweging te maken tussen de vaste kosten van een vervoersmiddel en de kosten die betaald moeten worden indien een levering niet binnen het
22
HOOFDSTUK 3.
LITERATUURSTUDIE
gespeci ceerde tijdsframe plaatsvindt kan men aan de hand van VRPTW en VRPSTW bepalen of er al dan niet extra (of minder) transportmiddelen moeten worden ingezet [23].
3.4.3 Heuristieken De heuristieken om een VRPTW op te lossen zijn reeds veel intensiever onderzocht dan de exacte oplossingsmethoden.
Twee types van heuristieken worden onderscheiden:
de
route-building heuristieken en de route-improving heuristieken [6].
Route-building heuristieken
De bekendste is zonder twijfel (een uitbreiding van) de
savings heuristiek van Clark & Wright [32], deze heuristiek werd reeds uitgebreid besproken in sectie 3.3.4.1. Ook het sweep algoritme van Gillet en Miller [33] kan oplossingen genereren voor een VRPTW, zoals reeds besproken werd in sectie 3.3.4.2. Een samenvatting van verschillende heuristische route-building algoritmes kan men terugvinden in Larssen [6].
Route-improvement heuristieken
De basis van bijna alle route-improvement heuris-
tieken ligt bij de lokale zoekmethodes met zoekoperatoren [39, 47], zoals reeds besproken in sectie 3.3.4.5. Ook de tabu search methode [37, 38] wordt vaak gebruikt om routes te optimaliseren met een heuristisch algoritme, zie sectie 3.3.4.3.
Een uitgebreid onderzoek rond de mogelijke heuristieken voor een VRPTW kan men terugvinden bij Lau [48], Liu [21] en Braysy & Gendreau [22].
3.5
Vehicle routing problem met dynamische reistijden
3.5.1 Inleiding In de voorgaande secties werd uitgebreid besproken hoe verschillende soorten VRP kunnen opgelost worden aan de hand van exacte modellen en heuristische algoritmes. Hierbij werd echter telkens verondersteld dat de reistijd tussen twee klanten onafhankelijk is van de tijd. Het is echter veel realistischer om bij de routering ook rekening te houden met les. Op die manier worden de reistijden tussen twee klanten tijdsafhankelijk.
In deze sectie
wordt onderzocht op welke manier een VRP met tijdsafhankelijke reistijden kan behandeld worden. Het thesisonderzoek zelf zal een TDVRP oplossen aan de hand van exacte modellen en heuristische algoritmes. De tijdsafhankelijke reistijden worden voorgesteld door een planningsperiode op te delen in een aantal tijdsintervallen, voor elk tijdsinterval wordt de reistijd meegegeven tussen twee knopen met starttijd in een bepaald interval. Deze soort van problemen krijgt meer en meer aandacht door de realistische aard van het probleem, maar het valt zeker op dat er tot nog toe veel minder onderzoek uitgevoerd werd op de TDVRP dan op de alom bekende VRP en VRPTW. De TDVRP heeft enorm veel belang in het bedrijfsleven aangezien transport sowieso gepaard gaat met onzekerheden. Door les en opstoppingen in rekening te brengen bekomt
3.5.
VEHICLE ROUTING PROBLEM MET DYNAMISCHE REISTIJDEN
23
men een meer realistische route dan wanneer een standaard VRP wordt gebruikt om een routering te genereren. Een TDVRP zorgt met andere woorden voor een mogelijke reductie van de transportkosten voor bedrijven in heel uiteenlopende industrietakken. Zoals later zal besproken worden bij het heuristisch algoritme, is de beschikbaarheid van data vaak een beperkende factor voor het volledig realistisch oplossen van een TDVRP. Het is namelijk vaak onmogelijk om voor elke mogelijke postcode van-naar combinatie correcte ledata te verkrijgen.
Deze problematiek zal ook later tijdens de ontwikkeling van het
heuristisch algoritme van deze thesis aan bod komen.
3.5.2 FIFO De tijdsafhankelijke reistijden die via de data ter beschikking gesteld worden, zijn vaak gegeven onder de vorm van constante reistijden in bepaalde intervallen. Dit kan echter in veel gevallen leiden tot het ongunstige eect dat de FIFO (First In First Out) eigenschap verloren gaat.
Het kan dan namelijk gebeuren dat een voertuig later vertrekt en toch
vroeger aankomt, hetgeen niet realistisch is. Zo'n situatie kan men gemakkelijk inzien aan de hand van guur 3.13a: vertrekken op tijdstip vertrekken op tijdstip
s
impliceert een latere aankomsttijd dan
t.
Figuur 3.13: Vergelijking tussen een FIFO en niet-FIFO systeem
Er zijn verschillende mogelijkheden om situaties zoals in guur 3.13a te vermijden. Een optie is afstappen van het datamodel met constante reistijden gedurende een bepaald tijdsinterval en over te schakelen op een snelheidsmodel. Een uitgebreide beschrijving van zo'n snelheidsmodel is onder andere terug te vinden in het werk van Ichoua [49] en Donati [42]. De logica achter dit model is het veranderen van de snelheid in verschillende tijdsintervallen. Zoals te zien is op 3.13b wordt op deze manier de FIFO eigenschap gegarandeerd.
24
HOOFDSTUK 3.
LITERATUURSTUDIE
Een andere methode om FIFO te garanderen is het lineariseren van de reistijden tussen twee tijdsintervallen. Concreet gezien ziet dit er als volgt uit met tijdsintervallen (startend bij één),
t het exacte tijdstip en l
m en m+1 opeenvolgende
de lengte van het interval. Men
vindt dan formule 3.24.
Reistijdt =
l·m−t t − l · (m − 1) · Reistijdm + · Reistijdm+1 l l
(3.24)
Aangezien voor deze thesis de data van reistijden gegeven werd als constante reistijden per interval, zal volgens de werkwijze van formule 3.24 gewerkt worden om de FIFO eigenschap te vrijwaren. Een beperking van dit model is echter dat het verschil in reistijden tussen twee intervallen nooit groter mag zijn dan de intervallengte. Dit is echter niet het geval voor realistische toepassingen.
3.5.3 Exacte oplossingsmethodes Exacte oplossingsmethodes voor TDVRP worden in de literatuur veel minder besproken dan exacte oplossingsmethodes voor de VRP. Desondanks zijn er toch enkele goed gedocumenteerde papers die een exacte oplossing bieden voor dit complex probleem.
Een
eerste oplossingsalgoritme voor het probleem werd gegeven door Malandraki in 1989 en Malandraki-Daskin in 1992 [50]. Meer geavanceerde en gedetailleerde oplossingen voor de TDVRP worden besproken door Figliozzi [51] en Lieckens [52]. De Camargo [53] bespreekt een niet-lineaire MIP formulering, Figliozzi [54] bespreekt een algoritme voor de TDVRP met (zachte) tijdsvensters. Haghani [23] bespreekt de TDVRP, waarbij zowel ophalen als afhalen mogelijk is.
Hier
kan de vrachtwagen op een optimale tijd aankomen bij de klant, met extra kosten wanneer hiervan afgeweken wordt.
Er wordt in deze paper zowel een exact wiskundig model als
een genetisch heuristisch algoritme besproken. Aangezien het exact wiskundig model van Haghani als basis zal dienen voor het model van deze thesis, wordt dit model hieronder gedetailleerd weergegeven.
3.5.3.1 Verzamelingen P
Verzameling van klanten waar goederen opgehaald worden
B
Verzameling van klanten waar goederen afgehaald worden
D
Verzameling van alle klanten(P
V1
Verzameling met informatie over de gebruikte voertuigen: identi catienummer
∪ B)
voertuig, startnode, eindnode.
U
Verzameling van gebruikte voertuigen {set van
i
S1
Verzameling van startnodes voor gebruikte voertuigen {set van
in
V1 (i, j, k)} j
in
V1 (i, j, k)}
3.5.
VEHICLE ROUTING PROBLEM MET DYNAMISCHE REISTIJDEN
E1
Verzameling van eindnodes voor gebruikte voertuigen {set van
k
V0
Verzameling met informatie over de niet-gebruikte voertuigen:
25
in
V1 (i, j, k)}
identi catie-
nummer voertuig, startnode, eindnode.
N
Verzameling van niet gebruikte voertuigen {set van
i
S0
Verzameling van startnodes voor niet-gebruikte voertuigen {set van
E0
Verzameling van eindnodes voor niet-gebruikte voertuigen {set van
K
Verzameling van alle voertuigen
S
Verzameling van startnodes voor voertuigen.
E
Verzameling van eindnodes voor voertuigen.
(E1 ∪ E0 )
T
Zijnde de unie van alle vraag- en startnodes
(D ∪ S)
De
Alle nodes zonder startnodes
Da
Alle nodes
Ds
Alle vraagnodes behalve de startnodes
in
V0 (i, j, k)} j in V0 (i, j, k)}
k in V0 (i, j, k)}
(S1 ∪ S0)
((D ∪ E) − S)
(D ∪ E ∪ S) (D − S)
3.5.3.2 Parameters f
De vaste kost voor het gebruiken van een transportmiddel.
pw
Kost per eenheid van tijd wanneer een vrachtwagen te vroeg aankomt.
pd
Kost per eenheid van tijd wanneer een vrachtwagen te laat vertrekt
Rc
De transportkost per eenheid van tijd.
α
Starttijd van de transportmiddelen.
ω
Einde van de planningshorizon.
qi
Vraag in node
Qk
Capaciteit van transportmiddel
t Rij
De reistijd tussen
Ai
Gewenste aankomsttijd aan node
lk
Vertrektijd van voertuig
i.
Negatief in waarde, aangezien het product afgeleverd wordt.
i
en
j
k.
met start op tijdstip
k
t.
i.
vanuit zijn startpunt.
26
HOOFDSTUK 3.
LITERATUURSTUDIE
3.5.3.3 Beslissingsvariabelen xtij
=1 indien er een transportmiddel van
i
naar
j
gaat met start op tijdstip
t
.
=0 in alle andere gevallen.
vik
i
=1 indien punt
wordt bezocht door transportmiddel
k.
=0 in alle andere gevallen
ci
Inhoud van een transportmiddel wanneer het de klant
wi
Tijd dat de vrachtwagen te vroeg komt ten opzicht van
di
Tijd dat de vrachtwagen te laat komt ten opzicht van
Hi
Het nummer van de vrachtwagen die node
i
i
verlaat.
Ai
Li
in node
in node
i.
i.
bezoekt.
3.5.3.4 Model Minimaliseer de volgende doelfunctie:
f
ω X X X
xtij + Rc
i∈S j∈De t=α
ω X X X
X X t t Rij xij + pw wi + p d di
i∈T j∈De t=α
i∈D
(3.25)
i∈D
onderhevig aan volgende restricties:
ω X X
xtij ≤
t=α j∈D
X
xliji
X
xtij
i ∈ S0
(3.26)
j∈De
=1
i ∈ S1 , i 6= j
(3.27)
j∈De ω X
X X
X X
xtij =
i∈D j∈E0 t=α+1 ω XX xtij = 1 i∈D t=α
xαij
(3.28)
i∈S0 j∈De
i ∈ E1
ci ≥ M (vik − 1) −
X
qj vjk
(3.29)
i ∈ S, k ∈ K
(3.30)
j∈D
ci ≤
X
vik Qk
i ∈ Da
(3.31)
k∈K
cj ≥ qj + ci + M
ω X
! xtij − 1
i ∈ T, j ∈ De , i 6= j
(3.32)
t=α ω XX i∈D t=α ω XX i∈T t=α
t xtij t + Rij
xtij = 1
≤ω
j∈E
j ∈ Ds , i 6= j
(3.33)
(3.34)
3.5.
VEHICLE ROUTING PROBLEM MET DYNAMISCHE REISTIJDEN
ω X X
xtjh
−
ω X X
t=α h∈De
t=α i∈T
X
i ∈ Da
vik = 1
xtij = 0
j ∈ Ds , j 6= h, i 6= j
27
(3.35)
(3.36)
i∈T
X
kvik = Hi
i∈B∪S∪E
(3.37)
k∈K
M
ω X
! xtij − 1
≤
t=α
M
1−
X
kvik − kvjk
i ∈ T, j ∈ De , i 6= j
(3.38)
kvik − kvjk
i ∈ T, j ∈ De , i 6= j
(3.39)
k∈K ω X
! xtij
≥
t=α
wi = M ax 0, Ai −
X k∈K
ω XX
! xtij t
i∈De t=α ! ω XX t di = M ax 0, xij t − Ai i∈De t=α ω ω X X XX t t txjh = xtij t + Rij i∈T t=α h∈De t=α
j∈T
(3.40)
j∈T
(3.41)
j ∈ De , j 6= h, i 6= j
(3.42)
3.5.3.5 Functie doelfunctie en restricties 3.25
De doelfunctie zorgt ervoor dat de kost wordt geminimaliseerd. Het eerste deel geeft de vaste kost weer om een voertuig in te zetten, het tweede deel stelt de reiskosten voor en de laatste twee factoren stellen de kosten voor die worden aangerekend voor het te vroeg of te laat komen bij een klant tegenover hun tijdsvenster.
3.26/3.27
Deze restricties zorgen ervoor dat de voertuigen vertrekken vanuit hun startnodes op hun starttijd. Voor nog niet ingezette voertuigen gebruikt men als starttijd de starttijd van het systeem en is de vertrekplaats het depot. Voor reeds gebruikte voertuigen wordt de node waar het voertuig zich bevindt gebruikt als referentie.
3.28/3.29
Deze zorgen ervoor dat alle voertuigen terugkeren naar het depot.
3.30/3.31/3.32 Zijn de capaciteitsrestricties van de voertuigen.
3.33
Deze restrictie zorgt ervoor dat elk voertuig voor het einde van de planningshorizon terugkeert naar het depot.
3.34
Zorgt ervoor dat elke klant exact éénmaal wordt bezocht tijdens de planningsperiode.
3.35/3.36
Deze beperkingen zorgen ervoor dat elke node door maximaal één voertuig kan worden bezocht.
28
3.37
HOOFDSTUK 3.
LITERATUURSTUDIE
Deze restrictie wijst de nodes een voertuig toe. Eenmaal dit voertuig is toegewezen aan een node kan dit niet meer veranderen, inclusief start- en stopnodes.
3.38/3.39
Indien twee nodes met elkaar zijn verbonden, zorgen deze restricties ervoor dat deze nodes ook door hetzelfde voertuig worden bezocht.
3.40/3.41
Deze restricties berekenen de kost wanneer een voertuig te vroeg aankomt of te laat vertrekt in een node, ten opzichte van het tijdsvenster van die node.
3.42
Deze restrictie zorgt ervoor dat een voertuig niet te vroeg kan vertrekken vanuit een vorige node.
3.5.4 Heuristieken Naast de exacte modellen die ontwikkeld worden voor een TDVRP is er ook nood aan heuristieken die realistische routeringproblemen met tijdsafhankelijke reistijden kunnen behandelen. De eerder besproken heuristieken voor VRP en VRPTW in sectie 3.3 en 3.4 kunnen op een aangepaste manier ook voor de TDVRP gebruikt worden [50].
Hier ko-
men echter veelal extra moeilijkheden bij kijken. Wanneer bijvoorbeeld een local search wordt toegepast op een initiële oplossing voor de TDVRP, kan de hele routering veranderen door het aanpassen van één enkele verbinding. Dit maakt optimaliseren van tijdsafhankelijke routeringproblemen veel complexer dan het optimaliseren van een standaard VRP of VRPTW. Deze complexiteit is één van de redenen waarom heuristieken voor TDVRP tot nog toe veel minder intensief bestudeerd werden dan de standaard VRP en VRPTW. Toch zijn er enkele heuristieken die waardevol zijn voor het genereren van routes bij een TDVRP. Een belangrijke heuristiek hiervoor is het MACS (Multi Ant Colony System) [42]. Donati beschrijft hierbij een uitbreiding van de ACS waarbij twee arti ciële kolonies aangemaakt worden, die elk instaan voor één van de doelstellingen van de optimalisatie. Een eerste kolonie staat in voor de minimalisatie van het aantal tours, terwijl een tweede kolonie de totale afstand optimaliseert. Deze twee kolonies werken samen door een informatie-uitwisseling aan de hand van arti ciële feromonen. Dit algoritme coördineert de activiteit van de twee kolonies simultaan om zo een verbeterde mogelijke oplossing te zoeken die ofwel minder tours bezit, ofwel hetzelfde aantal tours bezit met een lagere totaalafstand.
Wanneer zo'n oplossing
gevonden wordt, worden de kunstmatige feromonen globaal gezien geüpdatet zodat beide kolonies opnieuw gebruik kunnen maken van de geüpdate informatie. Om de problematiek aan te pakken die in deze thesis besproken wordt, wordt een nieuwe heuristiek ontwikkeld die grote datasets op korte tijd kan verwerken.
Deze heuristiek
moet compatibel zijn met tijdsafhankelijke reistijden en zal daarbovenop rekening kunnen houden met capaciteitsrestricties van verschillende trucks, tijdsvensters van de klanten en het depot, en de starttijden van de trucks. De ontwikkeling van de heuristiek en resultaten zijn terug te vinden respectievelijk in secties 6, 7 en 8.
3.6.
VENDOR MANAGED INVENTORY
3.6
29
Vendor Managed Inventory
Bij VMI staat de producent of handelaar in voor de stock van de klanten.
Bij het toe-
passen van VMI wenst men zowel de kosten als de service van een logistiek systeem te verbeteren. Dit komt doordat de leveringen frequenter zullen plaatsnemen. Producenten vinden VMI interessant omdat de onzekerheid van de vraag door het toepassen van het systeem verlaagd. Door VMI toe te passen kan men grote orders van klanten vermijden en moet er minder overcapaciteit worden voorzien. Dit omdat de leveringsfrequenties kunnen toenemen van maandelijks naar wekelijks naar zelfs dagelijks. Hierdoor kan men de productie constanter laten verlopen en de voorraden laten dalen. Door VMI toe te passen kan de e ciëntie van het transport toenemen.
Dit omdat de
producent overstapt naar een strategie waarbij men volle trucks wil laten rijden en een e ciëntie routeplanning wenst te gebruiken [55]. Het is namelijk de producent zelf die kies wanneer welke klant wordt beleverd. Een direct gevolg hiervan is dat hogere service levels mogelijk zijn. Een reden om voor VMI te kiezen voor een handelaar of producent is een eectieve daling door te voeren van de kosten betreende voorraadbeheer en tevens de variabiliteit uit deze voorraad te halen. In principe wordt de handelaar dus manager van de voorraad bij de klant.
De klant zal tevens van de voordelen van VMI genieten gezien de leverancier
frequenter zal leveren en er voor zorgen dat er steeds een bepaald service niveau gehaald wordt.
3.7
Inventory Routing Problem
In dit onderdeel wordt het IRP (Inventory Routing Problem) geïntroduceerd. Waar bij een VRP het probleem zich beperkte tot het plannen en coördineren van een transportmiddel, wordt dit probleem uitgebreid tot een IRP door rekening te houden met de voorraad bij de klant. Een typisch IRP probleem heeft dezelfde karakteristieken [56]. Bij een IRP zijn de volgende elementen aanwezig:
•
Producten worden vervoerd van de leverancier naar de klant.
•
Het transport gebeurt door middel van een voertuig dat gelimiteerd is in:
•
transportcapaciteit
rijtijden
Kosten worden aangerekend per eenheid van afgelegde afstand.
Algemeen wordt getracht om de transportkosten van het gehele systeem te minimaliseren. De kosten worden dan ook in de doelfunctie ingebracht. Het is echter ook mogelijk dat er andere factoren worden toegevoegd aan het model en systeem zoals het comfort van de
30
HOOFDSTUK 3.
LITERATUURSTUDIE
chaueurs ,betrekking hebbende tot zijn rij- en rusttijden, om het systeem te optimaliseren. Zoals eerder vermeld is het type IRP een probleem van een geheel andere aard vergeleken met een klassiek VRP. De oorzaak hiervan is een meer realistische benadering van de reële wereld. In de meeste problemen in de industrie zijn immers ook de voorraden gelimiteerd in capaciteit. Tevens consumeren de klanten hun geleverde producten tegen een bepaalde snelheid. De leverancier moet er voor zorgen, in het optimale geval, dat de klanten nooit een stock-out ervaren. Doordat er voorraden worden veronderstelt bij de klant speelt tijd wel een rol waar dit niet het geval was bij een klassiek VRP. Omdat er rekening mee wordt gehouden dat de klant een voorraad heeft wordt het routen van de transportmiddelen complexer gemaakt op twee verschillende manieren.
1. De te leveren hoeveelheid bij de klant is afhankelijk van de voorraad van de klant. 2. Kosten kunnen gevorderd worden voor het houden van voorraad.
Los van voorgaande karakteristieken zijn er nog een aantal eigenschappen die al dan niet geïmplementeerd kunnen worden in een IRP. Er zijn nog een hele resem eigenschappen die het IRP in complexiteit kunnen doen toenemen. Deze zijn onder meer;
•
Werken met een eindige of oneindige planningshorizon
•
Voorraadkosten kunnen wel of niet als relevant beschouwd worden
•
Voorraadkosten kunnen al dan niet enkel bij de klant worden aangerekend of bij zowel de klant als leverancier.
•
De snelheden waarmee de klanten hun product consumeren kunnen ofwel deterministisch zijn ofwel stochastisch van aard zijn.
•
De productie van goederen verloopt op een ogenblikkelijke manier ofwel op een continue manier.
•
De verzameling van mogelijke oplossingen kan beschouwd worden als alle mathematische oplossingen die mogelijk zijn oftewel als een subset van deze oplossingen die voldoen aan een set voorwaarden die beleidsmatig worden opgesteld.
De beslissingen die gemaakt worden om een IRP op te lossen bestaan uit de volgende onderdelen:
•
Wanneer levert de leverancier bij de klanten?
•
Hoeveel levert de leverancier bij de klanten?
•
Hoe stuurt de leverancier de transportmiddelen op een zo e ciënt mogelijke manier, (op het vlak van kosten, brandstof gebruik, emissies, of een set van andere parameters) naar de klanten.
3.7.
INVENTORY ROUTING PROBLEM
31
De totale kost voor een bepaalde oplossing bevat altijd de kosten die afkomstig zijn van het transportmiddel. De kosten om goederen op te slaan in de warenhuizen kunnen al dan niet in de totale kosten vervat zitten. Enkel het onderdeel waarin de routingcomponent wordt bepaald van het IRP is op zich al een NP-hard probleem. Zelfs indien het probleem wordt gereduceerd tot een TSP (Traveling Salesmen Problem), waarbij de planningshorizon één is, de voorraadkosten tot nul worden gereduceerd, de capaciteit van het transportmiddel oneindig is en alle klanten moeten bediend worden kan het probleem varianten van het probleem nog steeds moeilijk (hard) op te lossen zijn door middel van computers.
32
HOOFDSTUK 3.
LITERATUURSTUDIE
Hoofdstuk 4
Probleemstelling 4.1
Algemene beschrijving
Voor elk bedrijf dat actief is op logistiek vlak is in het bijzonder het transport tussen verschillende punten een essentiële component.
Gezien het transporteren van goederen
een kostelijke aangelegenheid is, is er een brede interesse naar de optimalisatie van hun routering. Het oorspronkelijke probleem is een VRP waarbij een kostenminimalisatie nodig is. Bijkomend aan deze VRP worden tijdsafhankelijke reistijden in rekening gebracht, wat de complexiteit van het probleem enorm verhoogt. De totale reistijd kan nu eigenlijk gezien worden als een driedimensionale matrix waarbij de totale reistijd afhankelijk is van het vertrekpunt, het eindpunt en het tijdsinterval.
Bijkomende restricties waaraan het pro-
bleem moet voldoen, zijn onder andere de capaciteit van de trucks, de tijdsvensters van de klanten en de planningsperiode van de routering. Deze planningsperiode zal standaard één dag bedragen. Het uiteindelijke doel van dit thesisonderzoek is het ontwikkelen van één of meerdere methodes om op een e ciënte en accurate wijze routes te generen en kosten te bepalen voor grootschalige TDVRPTW's.
Het is hierbij belangrijk om zo realistisch mogelijk te
werk te gaan. Dit wil zeggen enkel assumpties te maken wanneer het niet anders kan.
4.2
Beschikbare gegevens
De nodige gegevens worden ter beschikking gesteld door Möbius. Het betreft Accessbestanden voor de klantdata van Palm werd gebruik gemaakt van de data ter beschikking gesteld met de Thesis Ir.
Denys, de tijdsonafhankelijke reistijd (TimeDistanceMatrix.accdb) en
de letijd (FileInformatie.accdb). De respectievelijke databases kunnen worden teruggevonden op de datadrager, bijgevoegd bij deze thesis.
Deze databases voor de reistijden
bevatten informatie van postcode A naar postcode B, voor de tijdsafhankelijke database wordt hier nog een interval bijgevoegd.
De data moeten op verschillende manieren ver-
werkt worden om toepasbaar te zijn voor het exacte model en het heuristisch algoritme 33
34
HOOFDSTUK 4.
dat ontwikkeld zal worden.
PROBLEEMSTELLING
Deze dataverwerking is niet vanzelfsprekend wanneer grote
datasets verwerkt moeten worden, zoals bij Palm-case het geval is. Voor verdere verwerking van de data is het nodig om de databases TimeDistanceMatrix.accdb (346.921 records) en FileInformatie.accdb (1.597.536 records) samen te voegen tot één grote database met 33.304.416 records. Als de le-informatie beschikbaar is van een bepaalde node naar een bepaalde node, wordt deze opgeteld bij de tijdsonafhankelijke reistijd. Als de le informatie niet beschikbaar is, wordt de letijd verwaarloosd en is de totale reistijd dus gelijk aan de tijdsonafhankelijke reistijd.
Merk op dat op die manier
niet de volledige route tijdsafhankelijk kan zijn, dit is echter niet wijten aan de aard van het algoritme, maar aan het gebrek aan volledige data. Momenteel wordt namelijk slechts ongeveer 5% van het totale wegennet gedocumenteerd qua les. Wanneer volledige data beschikbaar zou zijn van elke node naar elke node, is het mogelijk om volledig tijdsafhankelijke routes te genereren aan de hand van dit heuristisch algoritme.
4.2.1 Aanpak van het probleem Deze thesis rond TDVRP wordt op twee verschillende manieren aangepakt. Zoals hierboven reeds gezegd, wordt een exact wiskundig model ontwikkeld. Het exact wiskundig model heeft als doel een exacte optimale oplossing te vinden voor een TDVRP. Door de enorm complexe aard van dit wiskundig model zal dit maar oplosbaar zijn voor een zeer beperkt aantal nodes. Daarom wordt een benaderend wiskundig model voorgesteld dat iets grotere datasets aankan.
Aangezien de Palm case voor veel meer klanten een oplossing moet
genereren, is het noodzakelijk een metaheuristisch algoritme te ontwikkelen dat in staat is om voor grotere datasets op een aanvaardbare tijdspanne een correcte en kwalitatieve oplossing te genereren. Het is de bedoeling om eerst het wiskundig model te ontwikkelen en dit toe te passen op een beperkte dataset.
Daarna wordt een metaheuristisch algoritme ontwikkeld om
TDVRPTW routeringen voor grotere datasets te genereren . Aangezien dit algoritme ontwikkeld werd door P. De Smedt en G.Hompes, wordt hierna naar het algoritme verwezen als het DSH-algoritme.
Deze metaheuristiek is in staat om voor grote datasets tijdsaf-
hankelijke routeringen te genereren met variabele truckcapaciteit, variabele starttijden, beperkingen volgens truckcapaciteit en tijdsvensters. Zowel het wiskundig model als het DSH algoritme krijgen dezelfde testcases als input. Het verschil tussen deze twee oplossingen zal de kwaliteit en performantie van het metaheuristisch algoritme weergeven. Indien deze metaheuristiek kwalitatief genoeg is, zal hiermee worden gewerkt voor de dataset van Palm, alsook om de invloed van enkele parameters te bespreken zoals de starttijd van de trucks, de capaciteit van de truck en de waarde van de GRASP-parameter. Zoals in sectie 3.3.4.6 vermeld, is het de implementatie van de GRASP-parameter die het algoritme een metaheuristisch karakter meegeeft. Dit zal leiden tot een oplossing die minstens even goed of beter is dan een zuivere heuristiek zonder metaheuristische eigenschappen.
4.2.
BESCHIKBARE GEGEVENS
35
Uiteindelijk zal deze metaheuristiek een routering weergeven voor een geselecteerde dataset van Palm. Tevens kan Palm de eigen kostenparameters ingeven in de heuristiek om zo een kostenberekening te verkrijgen van dagelijkse routeringen, alsook de strategische jaarlijkse routeringskosten. Deze kost kan door Palm zelf worden vergeleken met de huidige kost om afwegingen naar de toekomst te maken in verband met de gebruikte transportmiddelen en 3PL's.
36
HOOFDSTUK 4.
PROBLEEMSTELLING
Hoofdstuk 5
Wiskundige modellering 5.1
Inleiding
Het model dat wordt gebruikt om de routes te genereren voor de verschillende trucks is gebaseerd op het werk van Haghani [23]. Dit model kan werken met congestiedata onder de vorm van reistijden van i naar j tijdens een interval m. In dit model zijn alle parameters integer.
De beslissingsvariabelen zijn opgedeeld in binair, integer en oats.
Het model
geeft een oplossing voor een TDVRPTW (Time Dependent Vehicle Routing Problem with Time Windows).
5.2
Gegevens
5.2.1 Verzamelingen D
Verzameling van alle klanten
S
Verzameling van startnodes voor voertuigen.
S := {Sk , k ∈ K}
E
Verzameling van eindnodes voor voertuigen.
E := {Ek , k ∈ K}
De
Alle nodes zonder startnodes (D
Da
Alle nodes
V
Verzameling die informatie bijhoudt over de voertuigen: identi catienummer,
∪ E ).
(D ∪ E ∪ S).
startnode, eindnode.
(k, Sk , Ek )
K
Verzameling van alle voertuigen.
T
Zijnde de unie van alle vraag-en startnodes
37
(D ∪ S).
38
HOOFDSTUK 5.
WISKUNDIGE MODELLERING
5.2.2 Parameters f
De vaste koste voor het gebruiken van een transportmiddel.
pw
Kost per eenheid van tijd wanneer een vrachtwagen te vroeg aankomt.
pd
Kost per eenheid van tijd wanneer een vrachtwagen te laat vertrekt.
Rc
Transportkost per eenheid van tijd.
Zc
Servicekost per eenheid van tijd.
qi
Vraag in node
Ai
De start van het tijdsvenster bij node
Li
Het einde van het tijdsvenster bij node
αk
Vertrekinterval van voertuig
Ci
Servicetijd bij klant
α
Eerste tijdsinterval in de planningsperiode (als
ω
Laatste tijdsinterval in de planningsperiode.
i.
k
i. i.
vanuit zijn startpunt.
i. α = 1 → 00 : 00 99K 24 : 00)
5.2.3 Beslissingsvariabelen 5.2.3.1 Binair xm ij
=1 indien er een transportmiddel van in interval
i naar j
gaat met als start op een tijdstip
m.
=0 in alle andere gevallen.
vik
=1 indien punt
i
bezocht wordt door transportmiddel k.
=0 in alle andere gevallen
5.2.3.2 Integer ci
Inhoud van een transportmiddel na verlaten van node
ui
Variabele nodig voor de subtour eliminatie.
i.
5.2.3.3 Float tij t
De exacte starttijd om van node
i
naar
j
te rijden.
Rijij
De reistijd tussen
wi
Tijd dat de vrachtwagen te vroeg komt ten opzicht van
di
Tijd dat de vrachtwagen te laat komt ten opzicht van
i
en
j
met start op tijdstip
tij . Ai in
Li
node
in node
i.
i.
5.3.
5.3
EXACT WISKUNDIG MODEL
39
Exact wiskundig model
5.3.1 Model en restricties Minimaliseer de volgende doelfunctie:
f
ω X X X
xm ij + Rc
ω X X X
X X X t Rijij xm Cj + pw wi + p d di ij + Zc
i∈T j∈De m=α
i∈S j∈D t=α
j∈D
i∈D
(5.1)
i∈D
onderhevig aan volgende restricties:
X
xαijk = 1
i ∈ S; k ∈ K, i 6= j
(5.2)
j ∈ E, i 6= j
(5.3)
j∈De ω XX
xm ij = 1
i∈T m=α
X ci ≥ M vik − 1 − qj vjk
i ∈ S, k ∈ K
(5.4)
j∈D
X
ci ≤
vik Qk
i ∈ Da
(5.5)
k∈K ω X
cj ≥ qj + ci + M
! xm ij − 1
i ∈ T, j ∈ De ; i 6= j
(5.6)
m=α ω X X
tij xm ≤ 15ω ij tij + Rij
i∈T m=α ω XX
xm ij = 1
i∈T m=α ω X X
xm jh −
ω X X m=α i∈T
X
i ∈ Da
k∈K ω X
(5.7)
j ∈ D, i 6= j
m=α h∈De
vik = 1
j ∈ E, i 6= j
xm ij = 0
(5.8)
j ∈ D, i 6= j, , j 6= h
(5.9)
(5.10)
k k xm ij ≤ 1 − vi + vj
i ∈ T ; j ∈ De ; i 6= j; k ∈ K
(5.11)
m=α
wj ≥ Aj −
ω XX
tij xm t + R ij ij ij
j ∈ D, i 6= j
(5.12)
i∈T m=α
wj ≥ 0 dj ≥
X
j∈D tij xm t + R + C ij j − Lj ij ij
ω X
(5.13)
j ∈ D, i 6= j
(5.14)
i∈T m=α
dj ≥ 0 X
ω X
h∈De m=α ω X
j∈D tjh xm jh =
(5.15)
X
ω X
tij xm ij tij + Rij + Cj
j ∈ De , i 6= j, j 6= h
(5.16)
i∈T m=α
15(m − 1)xm ij ≤ tij
m=α
i ∈ T, j ∈ De , i 6= j
(5.17)
40
HOOFDSTUK 5.
ω−1 X
15mxm ij > tij
WISKUNDIGE MODELLERING
i ∈ T, j ∈ De , i 6= j
(5.18)
m=α t Rijij
≥
ω−1 X
xm ij
m=α
15m − tij 15
T Tijm
+
tij − 15(m − 1) 15
T Tijm+1
i ∈ T, j ∈ De , i 6= j (5.19)
ω X
m xm ij + xji ≤ 1
i ∈ D, j ∈ D, i 6= j
(5.20)
m=α
ui − uj + n ·
ω X
xm ij ≤ n − 1
i ∈ D, j ∈ D, i 6= j
(5.21)
m=α
5.3.2 Uitleg bij de restricties Hieronder wordt de functie uitgelegd van de doelfunctie en de verschillende bijhorende restricties:
5.1
De doelfunctie zorgt ervoor dat de kost wordt geminimaliseerd. Het eerste deel representeert de vaste kost om een voertuig in te zetten, het tweede deel stelt de reiskosten voor en de 2 laatste factoren stellen de kosten voor die worden gevorderd voor het te laat of te vroeg komen t.o.v. een tijdsvenster.
5.2
Een vrachtwagen moet vertrekken vanuit zijn startpunt, zijnde het depot. Deze vrachtwagen zal naar exact één node startinterval
5.3
αk .
Deze node
j
j
vertrekken vanuit zijn depot, in het
kan elke node zijn, behalve zijn startpunt.
Zorgt ervoor dat elk voertuig dat uitgestuurd is, exact éénmaal moet toekomen in het depot. Door te werken met verzameling T is het mogelijk om een vrachtwagen rechtstreeks van start naar einde te sturen. Dit maakt het mogelijk om een vrachtwagen "zonder kost" te laten uitrijden.
5.4
Deze ongelijkheid verzekert dat indien een vrachtwagen vertrekt uit zijn depot, zijn totale lading voldoende moet zijn om alle klanten in zijn rit te voorzien van hun vraag. In het geval van productophaling wil dit zeggen dat de vrachtwagen voldoende begincapaciteit moet hebben om de ophaling van alle klanten tijdens deze rit te kunnen waarborgen.
5.5
De lading van een vrachtwagen mag op geen enkel moment de vrachtwagencapaciteit overschrijden.
5.6
De lading in node
j
is groter of gelijk aan de lading in node
opgeteld bij de vraag van node
j.
Het grote getal
M
i
(=vorige node)
zorgt ervoor dat deze
ongelijkheid enkel van kracht is wanneer er ook werkelijk een verbinding is tussen 5.7
i
en
j
met vrachtwagen
k.
Zorgt ervoor dat elk voertuig voor het einde van de planningsperiode terugkeert naar het depot.
5.3.
EXACT WISKUNDIG MODEL
5.8
41
Zorgt ervoor dat elke klant exact eenmaal wordt bezocht tijdens de planningsperiode.
5.9
Indien een vrachtwagen toekomt in een bepaalde vraagnode
j,
moet deze ook
vertrekken vanuit deze node. 5.10
Zorgt ervoor dat elke node door exact één voertuig wordt bezocht.
5.11
Zorgt ervoor dat indien twee nodes met elkaar zijn verbonden, deze nodes ook bezocht worden door dezelfde vrachtwagen.
5.12
Deze restrictie berekent de tijd die een vrachtwagen te vroeg toekomt in een node, dit wil zeggen voor de start van het tijdsvenster van deze node.
5.13
Deze restrictie zorgt ervoor dat de tijd dat een vrachtwagen te vroeg toekomt in een node nooit negatief kan zijn.
5.14
Deze restrictie berekent de tijd dat een vrachtwagen te laat vertrekt uit een node, dit wil zeggen na het einde van het tijdsvenster van deze node.
5.15
Deze restrictie zorgt ervoor dat de tijd dat een vrachtwagen te laat vertrekt uit een node nooit negatief kan zijn.
5.16
Zorgt ervoor dat een voertuig niet te vroeg kan vertrekken vanuit een vorige node. De vertrektijd vanuit node node i, waarbij de reistijd tussen
5.17
j
wordt op deze manier de vertrektijd vanuit
i→j
en de servicetijd van
j
opgeteld worden.
Controleert samen met 5.18 of de starttijd van de vrachtwagen uit node node
j
i
naar
in het interval m ligt.
5.18
Zie 5.17.
5.19
Berekent de reistijd
t
Rijij
met de exacte starttijd
tij
als een linearisatie tussen
de gegevens uit de database die gekend zijn om het kwartier. 5.20
Zorgt ervoor dat er geen verbindingen heen en weer zijn tussen twee nodes.
5.21
Is de subtour eliminatie restrictie.
Dit wiskundige model bezit enkele niet-lineariteiten zoals te zien is in restricties 5.7, 5.12, 5.14, 5.16 en 5.19.
In het bijzonder zijn deze niet-lineariteiten
t
ij xm ij Rij
en
xm ij tij .
Deze
niet-lineariteiten kunnen omzeild worden door het invoeren van volgende restricties:
t
t
ij ij xm ij Rij → Yij
(5.22)
m xm ij tij → Zij
(5.23)
Om er voor te zorgen dat de nieuwe beslissingsvariabelen
m Zij
en
t
Yijij
voldoen aan alle
nodige restricties, worden volgende restricties toegevoegd:
t
t
Yijij ≤ Rijij
i ∈ T, j ∈ De , i 6= j
(5.24)
42
HOOFDSTUK 5.
t
Yijij ≤ M xm ij t t Yijij ≥ Rijij t Yijij ≥ 0 m Zij ≤ tij m Zij m Zij
≤
i ∈ T, j ∈ De , i 6= j, m = α...ω
− M (1 − xm ij )
(5.25)
i ∈ T, j ∈ De , i 6= j, m = α...ω
(5.26)
i ∈ T, j ∈ De , i 6= j
(5.27)
i ∈ T, j ∈ De , i 6= j, m = α...ω
M xm ij
(5.28)
i ∈ T, j ∈ De , i 6= j, m = α...ω
≥ tij − M (1 −
m Zij ≥0
WISKUNDIGE MODELLERING
xm ij )
(5.29)
i ∈ T, j ∈ De , i 6= j, m = α...ω
(5.30)
i ∈ T, j ∈ De , i 6= j
(5.31)
De restricties 5.7, 5.12, 5.14 en 5.16 worden respectievelijk 5.30,5.31, 5.32, 5.33 en 5.34:
ω XX
t
m (Zij + Yijij ) ≤ 15ω
j ∈ E, i 6= j
(5.32)
i∈T m=α
wj ≥ Aj −
ω XX
t
m (Zij + Yijij )
j ∈ D, i 6= j
i∈T m=α ω XX t m dj ≥ (Zij + Yijij + Cj ) − Lj i∈T m=α ω ω X X XX t m tjh xm = (Zij + Yijij jh i∈T m=α h∈De m=α m Rij
≥
ω−1 X m=α
m 15m − Zij 15
T Tijm xm ij
j ∈ D, i 6= j
+ Cj )
+
(5.33)
(5.34)
j ∈ De , i 6= j, j 6= h
m − 15(m − 1) Zij 15
T Tijm+1 xm ij
(5.35)
i ∈ T, j ∈ De , i 6= j (5.36)
Dit aangepaste model is theoretisch gezien een sterk en nauwkeurig wiskundig model voor het oplossen van een TDVRPTW. Om dit model te kunnen oplossen binnen een aanvaardbare rekentijd is het echter aangewezen om enkele vereenvoudigingen door te voeren in dit model.
5.3.3 Intervalmodel Dit model is een vereenvoudiging van het model dat eerst voorgesteld werd. Het wordt gerealiseerd door de reistijd te bekijken per interval in plaats van per tijdseenheid. De starttijd aan een bepaalde node
i wordt gekoppeld aan een interval en afhankelijk van dit interval is
een bepaalde totale reistijd van toepassing. De starttijd wordt op die manier gelijkgesteld aan het begin van het desbetreende interval m. Daardoor komt de vrachtwagen één of enkele intervallen later toe in node j. Dit vereenvoudigt het model aanzienlijk aangezien er geen linearisaties nodig zijn van reistijden, noch linearisaties van niet-lineaire restricties. Het nadeel van dit robuustere model is dat de oplossing per de nitie minder nauwkeurig is, maar dit weegt niet op tegen het voordeel van de eenvoudigere en snellere werking van dit aangepaste model.
Het grootste verschil is dat hierdoor de beslissingsvariabele
vervangen wordt door de parameter beperking dat het niet van
i
naar
m. Rij
i
t
Rijij
Het eerst opgestelde model heeft als bijkomende
kan rijden.
Aangezien de data die ingelezen wordt
5.3.
EXACT WISKUNDIG MODEL
43
een "Postcode_Van" en "Postcode_Naar" bevat, wil dit zeggen dat het met dit model onmogelijk is om meerdere klanten te bezoeken die in dezelfde postcode gelegen zijn. Dit is niet optimaal aangezien het net aantrekkelijk zou zijn om klanten in dezelfde postcode te kunnen bedienen in dezelfde route. Dit probleem kan omzeild worden door een variabele servicetijd te introduceren en de vraag van deze klanten te gaan sommeren. Dit betekent concreet dat klant
A
met vraag
X
en klant
B
met vraag
postcode, in het model samengevoegd worden tot klant
C
Y,
allebei gelegen in dezelfde
met vraag
X +Y .
De servicetijd
wordt dan uit de database uitgelezen en wordt op de volgende manier voorgesteld:
Cj = 20y − 5 Waarbij
Cj
(5.37)
de servicetijd in node
j
voorstelt en
y
het aantal nodes die samengevoegd
worden tot één node. Deze formule is tot stand gekomen omdat elke node standaard 15 minuten servicetijd heeft, en de reistijd tussen twee nodes binnen dezelfde postcode standaard op 5 minuten wordt gezet. Dit impliceert ook dat een vrachtwagen altijd minstens één interval later vertrekt dan wanneer hij toekomt, hetgeen een vereiste is voor het wiskundig model. Indien meer nauwkeurigheid vereist wordt, kan een interpolatie gebeuren tussen de letijd waardoor de intervallen kleiner kunnen worden.
Beide methodes zijn
echter buiten de scope van deze thesis. Hier wordt dus gewerkt per postcode in plaats van per klant.
Aangezien gewerkt wordt met een robuust intervalmodel, vertrekt de vrachtwagen vanuit een node altijd aan het beginpunt van een bepaald interval. Er wordt eerst een controle uitgevoerd om na te gaan in welk interval de vrachtwagen toekomt bij een bepaalde klant. Hier wordt de servicetijd bijgeteld en op die manier bekomt men de tijd waarop de vrachtwagen vertrekt naar de volgende klant. Door de aard van het intervalmodel moet op dit moment bekeken worden in welk "interval" de vrachtwagen zal starten. Vanaf dan wordt verondersteld dat de vrachtwagen start bij het begin van dat interval. Wanneer een vrachtwagen vertrekt op een tijdstip tussen interval
m
om deze te laten starten in het begin van interval start in het begin van interval
m
en
m + 1,
kan de keuze gemaakt worden
m of in het begin van interval m + 1.
Bij
wordt de tijd ctief telkens even teruggeschoven, zoals te
zien is op Figuur 5.1a. Dit heeft als nadelig eect dat de totale reistijd onderschat wordt. De reeds verlopen tijd van dat interval wordt namelijk telkens verwaarloosd, en dit cumulatief over alle klanten. Het alternatief is de vrachtwagen voor elke klant laten starten aan het begin van interval
m + 1, zoals te zien is op Figuur 5.1b.
Op deze manier verkrijgt men
een overschatting van de totale reistijd aangezien steeds de nog niet verstreken tijd in het desbetreende interval overgeslagen wordt, en dit ook cumulatief voor alle klanten. Deze laatste optie is echter beter om te implementeren in het model aangezien een overschatting van de reistijd veiliger is voor de correctheid van de routering. Met de eerste optie is het immers mogelijk een routering te verkrijgen die in de realiteit niet haalbaar blijkt, terwijl dit nooit kan voorvallen bij de tweede optie. Omwille van deze redenen werd gekozen voor alternatief twee, waarbij de vrachtwagen telkens vertrekt aan het begin van interval Dit is in het wiskundig model merkbaar bij restricties 5.53 en 5.54.
m + 1.
44
HOOFDSTUK 5.
WISKUNDIGE MODELLERING
a) aankomst
vertrek
X m-1 b)
m
m+1
aankomst
m+2
vertrek
X m-1
m
m+2
m+1
Figuur 5.1: Intervalmodel Twee opties voor begintijd van een truck naar een klant bij het intervalmodel. a) naar het begin van interval
m.
b) naar het begin vaninterval
m+1
5.3.3.1 Benaderend wiskundig model Minimaliseer de volgende doelfunctie:
f
ω X X X
xm ij + Rc
ω X X X
X X X m m Rij xij + Zc Cj + pw wi + p d di
i∈T j∈De m=α
i∈S j∈D t=α
j∈D
i∈D
(5.38)
i∈D
Deze doelfunctie is onderhevig aan volgende restricties:
X
xαijk = 1
i ∈ S; k ∈ K, i 6= j
(5.39)
j ∈ E, i 6= j
(5.40)
j∈De ω XX
xm ij = 1
i∈T m=α
X ci ≥ M vik − 1 − qj vjk
i ∈ S, k ∈ K
(5.41)
j∈D
ci ≤
X
vik Qk
i ∈ Da
(5.42)
k∈K
cj ≥ qj + ci + M
ω X
! xm ij − 1
i ∈ T, j ∈ De ; i 6= j
(5.43)
m=α ω X X
m xm ij (15 (m − 1)) + Rij ≤ 15ω
i∈T m=α ω XX
xm ij = 1
i∈T m=α ω X X
xm jh −
j ∈ D, i 6= j ω X X
m=α h∈De
m=α i∈T
X
i ∈ Da
k∈K ω X m=α
vik = 1
j ∈ E, i 6= j
k k xm ij ≤ 1 − vi + vj
xm ij = 0
(5.44)
(5.45)
j ∈ D, i 6= j, , j 6= h
(5.46)
(5.47)
i ∈ T ; j ∈ De ; i 6= j; k ∈ K
(5.48)
5.3.
EXACT WISKUNDIG MODEL
wj ≥ Aj −
ω XX
45
m xm ij 15(m − 1) + Rij
j ∈ D, i 6= j
(5.49)
i∈T m=α
wj ≥ 0 dj ≥
j∈D
ω XX
(5.50)
m xm ij 15(m − 1) + Rij + Cj − Lj
j ∈ D, i 6= j
(5.51)
i∈T m=α
dj ≥ 0 X
ω X
j∈D
(5.52)
15(m − 2)xm jh <
h∈De m=α
X
ω X
m xm ij 15 (m − 1) + Rij + Cj
j ∈ De , i 6= j, j 6= h
i∈T m=α (5.53)
ω X X
15(m − 1)xm jh ≥
h∈De m=α
ω XX
m xm ij 15 (m − 1) + Rij + Cj
j ∈ De , i 6= j, j 6= h
i∈T m=α (5.54)
ω X
m xm ij + xji ≤ 1
i ∈ D, j ∈ D, i 6= j
(5.55)
m=α
ui − uj + n ·
ω X
xm ij ≤ n − 1
i ∈ D, j ∈ D, i 6= j
(5.56)
m=α
5.3.3.2 Uitleg bij doelfunctie en de restricties 5.38
De doelfunctie zorgt ervoor dat de kost wordt geminimaliseerd. Het eerste deel representeert de vaste kost om een voertuig in te zetten, het tweede deel stelt de reiskosten voor en de 2 laatste factoren stellen de kosten voor die worden gevorderd voor het te laat of te vroeg komen t.o.v. een tijdsvenster.
5.39
Een vrachtwagen moet vertrekken vanuit zijn startpunt, zijnde het depot. Deze vrachtwagen zal naar exact één node startinterval
5.40
αk .
Deze node
j
j
vertrekken vanuit zijn depot, in het
kan elke node zijn, behalve zijn startpunt.
Zorgt ervoor dat elk voertuig dat uitgestuurd is, exact éénmaal moet toekomen in het depot. Door te werken met verzameling
T
is het mogelijk om een vracht-
wagen rechtstreeks van start naar einde te sturen. Dit maakt het mogelijk om een vrachtwagen "zonder kost" te laten uitrijden. 5.41
Deze ongelijkheid verzekert dat indien een vrachtwagen vertrekt uit zijn depot, zijn totale lading voldoende moet zijn om alle klanten in zijn rit te voorzien van hun vraag. In het geval van productophaling wil dit zeggen dat de vrachtwagen voldoende begincapaciteit moet hebben om de ophaling van alle klanten tijdens deze rit te kunnen waarborgen.
5.42
De lading van een vrachtwagen mag op geen enkel moment de vrachtwagencapaciteit overschrijden.
5.43
De lading in node
j
is groter of gelijk aan de lading in node
opgeteld bij de vraag van node
j.
Het grote getal
M
i
(=vorige node)
zorgt ervoor dat deze
46
HOOFDSTUK 5.
WISKUNDIGE MODELLERING
ongelijkheid enkel van kracht is wanneer er ook werkelijk een verbinding is tussen 5.44
i
en
j
met vrachtwagen
k.
Zorgt ervoor dat elk voertuig voor het einde van de planningsperiode terugkeert naar het depot.
5.45
Zorgt ervoor dat elke klant exact eenmaal wordt bezocht tijdens de planningsperiode.
5.46
Indien een vrachtwagen toekomt in een bepaalde vraagnode
j,
moet deze ook
vertrekken vanuit deze node. 5.47
Zorgt ervoor dat elke node door exact één voertuig wordt bezocht.
5.48
Zorgt ervoor voor dat indien twee nodes met elkaar zijn verbonden, deze nodes ook bezocht worden door dezelfde vrachtwagen.
5.49
Deze restrictie berekent de tijd dat een vrachtwagen te vroeg toekomt in een node, dit wil zeggen voor de start van het tijdsvenster van deze node.
5.50
Deze restrictie zorgt ervoor dat de tijd dat een vrachtwagen te vroeg toekomt in een node nooit negatief kan zijn.
5.51
Deze restrictie berekent de tijd dat een vrachtwagen te laat vertrekt uit een node, dit wil zeggen na het einde van het tijdsvenster van deze node.
5.52
Deze restrictie zorgt ervoor dat de tijd dat een vrachtwagen te laat vertrekt uit een node nooit negatief kan zijn.
5.53
Zorgt samen met 5.54 voor dat een voertuig niet te vroeg kan vertrekken vanuit een vorige node. Het vertrekinterval vanuit node vertrekinterval vanuit node van
j
wordt op deze manier het
waarbij de reistijd tussen
i→j
en de servicetijd
opgeteld worden. Aangezien dit interval kleiner moet zijn dan het begin
van het interval
m,
i,
j
m+1
en groter of gelijk moet zijn dan het begin van interval
wordt verzekerd dat steeds gestart wordt van het begin van interval
m.
5.54
Zie 5.53.
5.55
Zorgt ervoor dat er geen verbinding heen en weer kan zijn tussen twee nodes.
5.56
Is de restrictie die zorgt voor subtour eliminatie.
5.4
Modellering in AMPL
Voor het oplossen van het intervalmodel van de TDVRPTW wordt gebruik gemaakt van algebraïsche modelleertaal AMPL[57]. Het is ook mogelijk om ILOG CPLEX Optimization Studio [58] van IBM te gebruiken, maar door de implementatie van meerdimensionale matrices blijkt het handiger om het model in AMPL uit te werken. Deze software wordt speci ek gebruikt voor optimalisatieproblemen in het operationeel onderzoek. De gebruikte hardware voor de tests is een Windows 7 64-bit core i7 1.73GHz en 6GB RAM.
5.4.
MODELLERING IN AMPL
47
5.4.1 Dataverwerking De nodige data werd geleverd door Möbius als Microsoft Access databases. De volledige databases zijn terug te vinden op de bijgevoegde datadrager. De databases TimeDistanceMatrix.accdb en FileInformatie.accdb worden samengevoegd om op die manier van één database de totale tijdsafhankelijke reistijd te kunnen uitlezen.
Aangezien de samenge-
voegde database miljoenen datarecords bevat, 33.304.416 om precies te zijn, is het nuttig en tevens onontbeerlijk om over te stappen naar MySQL Server om de bruikbaarheid van de database te verhogen.
Meer details over deze handeling en de methode waarop dit
gebeurde is terug te vinden in de sectie over MySQL 6.3.4. De data die als input dient voor de AMPL-code kan ingelezen worden uit een tekstbestand. De meest uitdagende dataverwerkingsstap hiervoor is de formulering van de reistijden zodat deze rechtstreeks door AMPL kunnen verwerkt worden. De locatiedata die gebruikt wordt om in te lezen in AMPL wordt aangereikt als postcode. Op die manier wordt een rit afhankelijk van de startpostcode, de eindpostcode en het startinterval van de rit. In de AMPL .dat- le worden de tijdsafhankelijke reistijden per route gede nieerd als volgt:
T r a v e l T i m e :=
[ PostCodeVan , PostCodeNaar , ∗ ] I n t e r v a l R e i s t i j d
De reistijd voor een rit van postcode 1000 naar postcode 4600 tussen de intervallen 50 en 55 zou er dan als volgt uitzien:
param
TravelTime
50
63
51
62
52
60
53
64
54
62
55
62;
:=
[1000 ,7000 ,∗]
Om de data op deze manier aan te reiken aan het AMPL programma werd een Java programma geschreven met de database als input en bovenstaande datavorm als tekstbestand output. Deze code kan men terugvinden op de bijgevoegde datadrager. De andere datade nities van het model in AMPL verlopen volgens de normale structuren van een AMPL .dat bestand. Zo krijgen de parameters een waarde in de .dat le en worden ze op die manier als parameter opgeroepen in het .mod bestand. Met een testset bestaande uit 10 klanten en een depot, kan een .dat le er uitzien zoals in code 5.1. Hierbij wordt de TravelTime in de .dat le gede nieerd zoals aangegeven werd in het bovenstaande voorbeeld.
Voor de dataset met 10 klanten wordt deze datahoeveelheid
uiteraard te groot om hier integraal als voorbeeld weer te geven.
48
HOOFDSTUK 5.
WISKUNDIGE MODELLERING
Code 5.1 Code van een .mod le param n param
:=
10;
Trucks
:=
1;
param M :=
100;
param
f
0;
param
alpha
:=
24;
param
omega
:=
86;
param
TravelCost
param
ServiceTime
:=
15;
param
ServiceCost
:=
1;
:=
param Pw :=
2;
param Pd :=
2;
:=
1;
s e t PARAMETERS:= Demand set
S
s e t D :=7000 set
E
set
T :=1000
set
De
Latest ;
7100
7300
7500
7600
7700
7800
7900
8000
8300;
7000
7100
7300
7500
7600
7700
7800
7900
8000
:=1000; :=7000
s e t K :=
7100
7300
7500
7600
7700
7800
7900
8000
8300
8300; 1000;
truck ;
param :
VehCap:=
param :
Demand
1000
0
0
1440
7000
1
0
1440
7100
1
0
1440
7300
1
0
1440
7500
1
0
1440
7600
1
0
1440
7700
1
0
1440
7800
1
0
1440
7900
1
0
1440
8000
1
0
1440
8300
1
0
1440;
param
Earliest
:=1000;
truck
Earliest
50; Latest
:=
T r a v e l T i m e : = [ PostCodeVan , PostCodeNaar , ∗ ]
Interval
Reistijd ;
5.4.2 Model Het model in AMPL is een vertaling van het wiskundige intervalmodel naar de code. In de .mod- le wordt het wiskundig model uitgeschreven met zijn doelfunctie en alle nodige restricties. Daarbovenop worden alle verzamelingen, parameters, constanten en beslissingsvariabelen ook in de .mod- le gede nieerd. In de .dat- le wordt alle nodige data ingelezen. De volledige code, van zowel het model als de .dat les, kan teruggevonden worden op de datadrager die bijgevoegd zit bij deze thesis.
5.5
Testen
Het benaderend wiskundig model wordt na een implementatie in AMPL getest op verscheidene testsets om de correctheid van de routering na te gaan. Het model wordt getest op
5.5.
TESTEN
49
vijf uiteenlopende testcases om op die manier de kans van een toevallige correctheid uit te sluiten. Als deze testcases correcte resultaten geven is het bewezen dat het exacte model correct routes kan genereren.
De volledige datasets en oplossingsdata kan worden terug
gevonden op de datadrager bij deze thesis. Zoals reeds aangehaald is het model een ruwe benadering van de werkelijkheid. Om deze werkelijkheid nauwkeuriger te benaderen wordt de uiteindelijke routering bepaald aan de hand van de werkelijke reistijden.
De routeringoutput van de AMPL code wordt dus
gebruikt om daarmee de echte reistijden op te halen en zo een nauwkeurige routering te kunnen weergeven. Hieronder wordt de eerste testcase uitgebreid besproken. De andere testcases worden hier samengevat, de uitgebreide oplossing hiervan is te vinden in appendix A. Testcase 1 wordt standaard het meest uitgebreid besproken in deze thesis omdat deze route duidelijk een tijdsafhankelijk karakter heeft.
5.5.1 Testcase 1 De input en resultaten van testcase 1, zijn als volgt: Depot := 1000 Klanten := 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000 Vertrektijd := 360 (interval 24) AMPL
output
:=
(1000,2000,24)
(5000,4000,55)
(9000,8000,34)
(6000,5000,51)
(3000,1000,66) (2000,9000,29) (4000,3000,60) (8000,7000,39) (7000,6000,47)
Deze output stelt een route voor waarvan er via Excel een route wordt gemaakt met exacte gelineariseerde reistijden. Het resultaat van deze operatie is te zien in tabel 5.1. Locatie
Reistijd
Aankomst
Vertrek
Interval 1
Interval 2
TT 1
TT 2
X
Y
360
24
25
46
48
4,35
50,85
2000
46,00
406,00
421,00
28
29
52
51
4,39
51,21
9000
51,93
472,93
487,93
32
33
58
55
3,71
51,05
8000
56,41
544,35
559,35
37
38
101
101
3,21
51,24
7000
101,00
660,35
675,35
45
46
37
37
3,96
50,46
6000
37,00
712,35
727,35
48
49
35
36
4,45
50,42
5000
35,49
762,84
777,84
51
52
53
53
4,85
50,46
4000
53,00
830,84
845,84
56
57
64
69
5,58
50,65
3000
65,95
911,78
926,78
61
62
36
36
4,69
50,88
1000
36,00
962,78
4,35
50,85
1000
Tabel 5.1: Berekening exacte reistijden testcase 1. De afkorting TT
x
staat voor de reistijd in interval
x
tussen locatie en aankomst.
Met de volgende kostenfactoren kan de totaalkost van deze route berekend worden. Het resultaat hiervan is zichtbaar in tabel 5.2. Deze kost zal vergeleken worden met de kost van dezelfde klantenset, opgelost via de heuristiek. Op deze manier wordt de procentuele gap bepaald van de heuristiek tegenover de exacte oplossing. Ter illustratie kan men op guur 5.2 de routering voor deze testcase waarnemen.
50
HOOFDSTUK 5.
WISKUNDIGE MODELLERING
#Trucks
1
Vaste kost
100
Reiskost
1
Klanten
10
Servicetijd
15
Servicekost
1
Totaalkost
702,78
Tabel 5.2: Kostenbepaling testcase 1
Breedtegraad
Routering Testcase 1 51,30 51,20 51,10 51,00 50,90 50,80 50,70 50,60 50,50 50,40 50,30 3,00
3,50
4,00
4,50 Lengtegraad
Route
5,00
5,50
6,00
Depot
Figuur 5.2: Route testcase 1
5.5.2 Overige testcases De handelingen die in paragraaf 5.5.1 worden uitgevoerd voor 4 andere testcases.
De
resultaten van deze testcases kan men terugvinden onder algoritme 5.2.
5.5.3 Testcases met jnere intervallen In hoofdstuk 6 wordt een metaheuristisch algoritme voorgesteld dat wel met exacte reistijden kan werken. Aangezien de performantie van de metaheuristiek zal worden nagegaan door het bepalen van een gap tussen het benaderende wiskundige model en de heuristiek, is het nodig voor een correcte berekening dat zowel het metaheuristisch algoritme als het benaderende wiskundige model dezelfde nauwkeurigheid van data hanteren. Daarom wordt in deze sectie een test uitgevoerd op het AMPL model met data die nauwkeurig is op de minuut. Aangezien deze methode per minuut veel te tijdrovend is wordt normaal gezien het intervalmodel per kwartier gebruikt, zoals eerder besproken. Het is echter nodig toch deze test per minuut te doen om op een correcte manier de performantie van de metaheuristiek na te gaan. De data voor deze test werd verkregen door lineaire interpolatie per minuut van de originele data per kwartier. Er moeten ook enkele aanpassingen uitgevoerd worden aan het
5.5.
TESTEN
51
Code 5.2 Resultaten testcases 2 t.e.m. •
•
Klanten := 1600, 1800, 1880, 2150, 2300, 2400, 2650, 2800, 3300, 6000 Kost := 665.23
Depot := 1000 Klanten := 1150, 1200, 9300, 9340, 9400, 9450, 9550, 9600, 9850, 9900 Kost := 629.86
Testcase 4
•
Depot := 1000
Testcase 3
•
5
Testcase 2
Depot := 1000 Klanten := 4600, 4700, 4900, 5000, 53000, 5500, 6000, 6200, 6500, 6600 Kost := 799.9
Testcase 5
Depot := 1000 Klanten := 7000, 7100, 7300, 7500, 7600, 7700, 7800, 7900, 8000, 8300 Kost := 665.13
.dat bestand. Zo wordt het begininterval en eindinterval respectievelijk 360 en 1304, wat overeenkomt met een tijdsvenster tussen 6 uur 's ochtends en 21u45 's avonds. Er wordt eerst geprobeerd om de originele testcase 1 uit te voeren voor dit ver jnde intervalmodel. Na meer dan 17 uur rekentijd geeft dit echter een "out of memory" fout. Op dit moment geeft de beste oplossing 698 als kost. Aangezien dit niet de uiteindelijke kost is - het programma is namelijk vroegtijdig afgesloten door geheugentekort - mag deze kost niet letterlijk gebruikt worden voor het bepalen van gaps tussen dit ver jnde model en de DSH metaheuristiek. Daarom wordt in tabel 6.4 en tabel 6.5 van sectie 6.5 deze kost aangeduid met een sterretje. Om toch voor het ver jnder model testcases uit te voeren werd de eerste testcase beperkt tot 3 testcases 1A, 1B en 1C zichtbaar in tabel 5.3. Indien er staat 1000->3000 wil dit zeggen dat men nodes 1000,2000 en 3000 opneemt in de testcase. Testcase
Nodes
Rekentijd(s)
Kost
1A
1000->5000
60
437,866
1B
1000->7000
827
540,4
1C
1000->8000
613
663,4
1D
Volledige set
61214
/
Tabel 5.3: Resultaten ver jnde intervallen AMPL
52
HOOFDSTUK 5.
WISKUNDIGE MODELLERING
Hoofdstuk 6
Metaheuristiek 6.1
Inleiding
In het werk van Sung et.
all.
[59] wordt er een methode aangegeven om het originele
algoritme van Dijkstra [60] aan te passen aan een time-dependent omgeving. Het voorgestelde algoritme is en
v
O(n2 + mv)
terwijl het origineel van Dijkstra
O(n2 + m)
is, met
n,m
respectievelijk het aantal nodes, links en het aantal tijdsframes. De tijdstoename die
gepaard gaat met het construeren van een oplossing is minimaal: voor 100.000 willekeurig gegenereerde nodes kan het algoritme een oplossing voorzien binnen de seconde. Het hier gepresenteerde algoritme heeft als basis het originele Dijkstra algoritme [60] en de toepassing van time dependency op Dijkstra in [59].
6.2
Het DSH-Algoritme
Het is op basis van voorgaande dat het volgende algoritme wordt voorgesteld. Gezien er geen rekening wordt gehouden met de capaciteiten van voertuigen en timewindows worden deze toegevoegd om het probleem realistischer te benaderen. Het voorgestelde algoritme is als pseudocode in algoritme DSH (De Smedt-Hompes) en als Java code op de bijgevoegde datadrager. 53
54
HOOFDSTUK 6.
METAHEURISTIEK
DSH Figuur 6.1: Logo DSH
S
bevat de geselecteerde nodes,
U
bevat de set van nodes beschikbaar om een route uit
op te bouwen. Arr_time(d(i), (i,j)) , te zien in code 6.2, wordt gede nieerd als zijnde de aankomsttijd op node gaande node met
i
j,
startende vanuit node i. D letter
wordt opgeslaan in pred(j).
A(i)
o
stelt het depot voor. De voor-
stelt de verzameling van alle verbindingen
i.
6.2.1 Metaheuristiek Het DSH-algoritme zal een oplossing zoeken voor een TDVRPTW. Gezien de natuur van een algoritme, zal de uitvoering ervan met één en de zelfde dataset steeds voor de zelfde oplossing zorgen. Dit zou ook het geval zijn voor dit algoritme indien GRASP niet toegepast word. Dit is een gevolg van de greedy aanpak. Door deze greedy aanpak worden er steeds lokale optima verkozen in elke stap van het DSH-algoritme. Het is niet zeker dat deze aanpak een globaal optimum zal vinden, maar het is mogelijk dat door locale optima te vinden er toch een globaal optimum wordt gevonden. Een gevolg van deze aanpak is dat de punten die ver gelegen zijn van het depot, de zogenaamde outliers ten opzicht van de puntenwolk van klanten, niet of steeds in een laatste dagtour gekozen worden. Om de nadelen die hiervoor werden vermeld te vermijden, voegen we ook nog een implementatie in van GRASP . We weten dat het greedy algoritme steeds het locale optimum verkiest, GRASP zorgt ervoor dat in gekozen voor het locale optimum. In
(1 − α)%
α%
van de gevallen er wordt
van de gevallen wordt er geopteerd voor de
2de beste keuze. Alzo worden er meerdere oplossingen bekomen, en tevens wordt de kans groter dat er voor de outliers gekozen wordt. De parameter
αcontroleert het aantal greedy
beslissingen t.o.v.
α = 1
dig greedy, voor
willekeurigheid in het algoritme.
α=0
Voor
is het algoritme volle-
is de oplossing volledig willekeurig. Het aantal nodes waartussen
gekozen wordt, in de pseudocode 6.1 , kan worden uitgebreid naar believen.
l(i, j)
stelt de afstand voor tussen de nodes
leggen afstand,
vk (i, j)
i
en
stelt de reissnelheid tussen
j, i
Res_lenght is de overblijvende af te en
j
in tijdslot
k
voor.
Twee mogelijke methodes zijn mogelijk om de aankomsttijden te berekenen. Beide voldoen
6.3.
IMPLEMENTATIE VAN DSH-ALGORITME
55
Code 6.1 DSH (De Smedt-Hompes) Algoritme Begin
S:=Ø; U:=N; d(i):=∞ ∀ i∈N; d(o):=0; pred(o):=0; WHILE (|S| < n) AND (C < DCT ) do Begin let y ∈ U for which: dy = min(dj ) : j ∈ U ; let z ∈ U − y for which: dz = min(dj ) : j ∈ (U − y); di =Select random from dy (chance α) or dz (chance 1 − α) if CD + Di < CT for each (i,j)∈A(i,j) do if d(j)>Arr_time(d(i), (i,j)) then if Ai ≤ di ≤ Li then d(j):=Arr_time(d(i), (i, j)) ; pred(j ):=i; S := S ∪ {i}; U := U − {i}; End End
aan het in de literatuur vermelde FIFO principe.
In het geval van reissnelheden (code
6.2) rijdt de functie Arr_time als het ware over de verbindingsweg tussen dit te doen wordt de resterende afstand steeds kleiner.
i
en
j.
Door
Eenmaal aangekomen geeft de
functie de aankomsttijd door aan de oproepende instantie. In het geval van reistijden (code 6.3), worden zowel congestietijd als basisreistijd opgeteld vanuit de beschikbare data. Het is deze laatste implementatie, beschikbare reistijden, die gebruikt wordt in de eigenlijke implementatie van de heuristiek.
6.3
Implementatie van DSH-algoritme
Om het DSH algortime op een performante manier te kunnen implementeren werden enkele technieken gebruikt die in deze sectie zullen worden verklaard.
6.3.1 Dataverwerking en databases De data betreende zowel de reistijden als letijden werden initieel als Microsoft Acces Databases ter beschikking gesteld. Het bestand TimeDistanceMatrix.accdb bestaat uit een tabel waar alle informatie vervat zit betreende de reis van postcode x, naar postcode y. Bij elke postcode hoort een coördinatenset en een stadsnaam. De belangrijkste informatie uit
56
HOOFDSTUK 6.
Code 6.2
METAHEURISTIEK
Functie om aankomsttijden te berekenen met time dependent snelheden als
input.[59].
Functie Arr_time(d(i), (i, j)) ; Res_length=l(i, j); let k ∈ {0,1,2,...,V} for which fk(i,j) ≤ d(i) ≤ fk+1(i,j) Res_length:=Res_lenght-vk(i,j) (fk+1(i,j) − d(i)); While Res_length>0 Do begin k:=k+1; Res_length:=Res_length-vk(i,j) (fk+1(i,j) − fk(i,j) ); end; Arr_time=fk+1(i,j) +Res_length/vk(i,j) ; Return
Code 6.3
Functie om aankomsttijden te berekenen met time dependent traveltimes als
input.[59].
Functie Arr_time(d(i), (i, j)) ; Arr_time=d(i)+TimeDistanceMatrix(i,j)+Filedata(i,j,k) Return
deze tabel is de 'DriveTime'. Deze tabel bevat de reistijd tussen twee postcodes. De grootte van deze tabel is
346.921
records en dit met een bestandsgrootte van
35.356KB .
Het
bestand FileInformatie.accdb bevat de tabel CongestionInfo en bevat tevens VAN-NAAR combinaties. Het grote verschil met de TimeDistanceMatrix is dat men voor elk kwartier van de dag ,dus van 00:00 tot 24:00 opgedeeld in 96 intervallen, informatie heeft over de congestietijden die bij de standaardreistijden zou moeten worden opgeteld. Deze informatie is terug te vinden in de tabel CongestionTime. Het bestand telt
186.028KB
groot.
1.597.536
records en is
Gezien er een kwasi lineair verband is in Microsoft Acces Databases
tussen het aantal records en de bestandsgrootte, werd het duidelijk dat Microsoft Acces een maat te klein zou zijn om de volledige data le te kunnen verwerken die nodig is om het probleem op te lossen.
Gezien in de oplossingsmethode unieke combinaties van
VAN-NAAR-TIJD velden nodig zijn, bekomt men dat er 96 maal de informatie van de CongestionInfo nodig is en dit voor elke VAN NAAR combinatie in België. leiden tot een database van
33.304.416
records met een geschatte grootte van
Dit zou
3388M B .
Uit de speci caties van Acces 2010 [61] kan men a eiden dat deze database te groot zou zijn, gezien er een limit is op de Total size for an Acces 2010 database (.accdb) van 2 gigabytes (2048M B). Om dit probleem op te lossen werd er overgestapt naar performantere
R
en robustere database oplossing, zijnde Oracle MySQL .
6.3.
IMPLEMENTATIE VAN DSH-ALGORITME
57
6.3.2 Postcodeclusters In de database TimeDistanceMatrix staan niet alle postcodes van België. Er zijn bijvoorbeeld enkele deelgemeentes met een aparte postcode die niet opgenomen zijn in de database. De tabel beneluxclusters kan hiervoor een oplossing bieden. Deze werkt aan de hand van postcodeclusters. Op deze manier worden bijvoorbeeld alle postcodes tussen 1500 en 1546 herleid tot postcode 1520. Wanneer het systeem van deze clusters standaard zou toegepast worden op de hele TimeDistanceMatrix database zou dit leiden tot 130 verschillende locaties in België. Dit leidt echter tot onnodige afrondingen en vereenvoudigen, aangezien er ook heel wat postcodes wél opgenomen zijn in de database.
In het DSH programma
zal dus als volgt te werk gegaan worden: wanneer een klant gevestigd is in een bepaalde postcode, wordt eerst gecontroleerd of deze postcode voorkomt in de ledata tabel. Als dit het geval is worden deze waarden gebruikt voor de routering, anders wordt aan de hand van de postcodeclusters een nieuwe, postcode voorgesteld die wel terug te vinden is in de database.
Een bijkomend probleem is dat sommige postcodes die worden voorgesteld door de postcodeclusters niet aanwezig zijn in de ledata. noch in de ledata. Dit is het geval voor 13 postcodes, zoals te zien is in tabel 6.1. Deze niet-bestaande postcodes worden vervangen door de postcode van de dichtstbijzijnde gemeente, of de hoofdgemeente waarvan deze postcode een deelgemeente is.
Originele postcode
Aangepaste postcode
Originele postcode
Aangepaste postcode
2050
2000
5100
5000
2100
2000
6100
6000
2600
2000
8200
8000
2660
2000
8211
8210
3221
3220
9050
9000
3746
9740
9636
9630
4200
4210
Tabel 6.1: Vervanging postcodes in beneluxpostcodeclusters
6.3.3 Postcodes Gezien de mogelijkheid is voorzien om routes weer te geven op een kaart, moet het programma beschikken over de coördinaten van elke klant. Om te kunnen voorzien dat het programma voor meerdere problemen inzetbaar is beschouwen we de coördinaten die bij een speci eke postcode als zijnde voldoende om voor een weergave te zorgen. Deze data wordt opgeslagen in de tabel postcodes.
Het zou mogelijk zijn deze positiedata te ver-
jnen aan de hand van de adressen van de klanten, maar gezien de weergave enkel voor informatieve doeleindes zal dienen, is deze stap achterwege gelaten in deze thesis.
58
HOOFDSTUK 6.
METAHEURISTIEK
R 6.3.4 Oracle MySQL MySql is het meest gebruikte relationele database management systeem in de wereld. Het speciale aan MySQL is dat de volledige broncode beschikbaar is onder de GNU General Public License. Het gebruik van de database is ook gratis. Eenvoudigweg wil dit zeggen dat iedereen vrij is om MySQL aan te passen en te gebruiken naar believen, de enige voorwaarde is dat de volledige broncode wederom onder GNU GPL ter beschikking wordt gesteld. Het is mogelijk om een MySQL server op min of meer elk besturingssysteem te installeren. Bedrijven die onder meer gebruik maken van MySQL zijn: Flickr, Nokia.com, Youtube, Wikipedia, Google (niet voor search), Facebook en Twitter. Het is duidelijk dat indien organisaties zoals Google en Wikipedia de keuze maken voor MySQL, MySQL mag worden beschouwd als een professionele en betrouwbare tool. Gezien MySQL primair een RDBMS (Relational database management system) is, zijn er standaard geen GUI's (Graphical User Interface) beschikbaar om de database te beheren of aan te passen, zoals wel eenvoudig zou kunnen met Microsoft Acces. Om dit probleem te omzeilen en het gebruiksgemak te verhogen wordt er gebruik gemaakt van MySQL Workbench. MySQL Workbench is de o ciële tool van Oracle om het beheer en gebruik van een MySQL database te vereenvoudigen.
Met behulp van deze tool voerden we de
volgende stappen uit om een gebruiksklare database te hebben voor ons probleem:
•
•
Installeren van een MySQL Server 5.5 op de volgende testsystemen
Windows 7 64-bit, Intel i7 920 @ 2,67 Ghz - 6GB RAM
Windows XP 32-bit, Intel Core 2 Duo @ 2,0Ghz - 2GB RAM
Aanmaken DSN (Data Source Name) in ODBC (Open Database Connectivity) verbindingen in Windows met de twee oorspronkelijke Acces databases.
•
Exporteren van Acces databases naar MySQL database via ODBC.
96 maal dupliceren van nieuwe tabel TimeDistanceMatrix met unieke index die overeenkomt met de index per periode (0-95).
•
Samenvoegen TimeDistanceMatrix en CongestionInfo waar de velden Van/Naar/Time_id matchen.
•
Het aanmaken van een index over de kolommen Van/Naar/Time.
Het aanmaken van een index zorgt er voor dat bepaalde waardes sneller kunnen worden opgezocht in de database. Zonder het gebruik van indices zou MySQL rij per rij gaan zoeken naar een speci eke waarde om de relevantie informatie op te zoeken. Hoe groter de tabel is, hoe meer tijd dit kost. Indien een tabel
1000 •
rijen heeft, is de query minstens 100 maal sneller[62].
Het aanmaken van een gebruiker java, om toegang tot MySQL te voorzien (via het lokale netwerk) tot de MySQL Server.
6.3.
IMPLEMENTATIE VAN DSH-ALGORITME
59
Het aanmaken van een aparte gebruiker naast de bestaande root user zorgt er voor dat er een beter beheer mogelijk is van de database en dat het op elk moment transparant is wat er op de MySQL server gebeurt. Tevens wordt toegang tot de server over het netwerk voorzien, zodat er één machine toegewezen kan worden om het DSH-algoritme uit te voeren en een andere om de database uit te voeren. Dit maakt het gehele setup performanter.
•
Het verhogen van de key_buer_size van MyISAM in MySQL zodat de indices in het geheugen blijven zitten om aldus een performantere operatie te voorzien van de database.
Het verhogen van de query_cache_size zodat het resultaat van eerdere
queries uit het geheugen kunnen worden gehaald i.p.v. steeds opnieuw het resultaat op te zoeken.
Het verhogen van de cache_size heeft als gevolg dat als een initiële query seconden duurt, de herhaling van deze zelfde query slechts
300
42
milliseconden in
beslag neemt.
Alle voorgaande handelingen hebben als gevolg dat de databasestructuur er uitziet zoals in guur 6.2.
filedata beneluxclusters PK
id
INTEGER
clustername lon lat from to
INTEGER DOUBLE DOUBLE INTEGER INTEGER
PK,I1 PK,I1 PK,I1
Van Naar period_id
INTEGER INTEGER INTEGER
Afstand Standaardtijd Tijd Filetijd Totaal
DOUBLE DOUBLE INTEGER DOUBLE INTEGER
postcodes PK
postcode
INTEGER
lat lon
DOUBLE DOUBLE
Figuur 6.2: Databasestructuur
Om een verbinding aan te gaan met de database vanuit Java wordt er gebruikt gemaakt van de JDBC (Java Database Connectivity) API (Application Programming Interface). Dit gebeurt door gebruik te maken van de connectiestring: j d b c : mysql : / / l o c a l h o s t : 3 3 0 6 / f i l e d a t a
6.3.5 Java Java is een programmeertaal die oorspronkelijk werd ontwikkeld door Sun Microsystems. Een groot voordeel van Java is dat gecompileerde Java code op elk besturingssysteem kan worden uitgevoerd.
Dit wil zeggen dat de software die in deze thesis ontwikkeld werd,
kan worden geïmplementeerd op verschillende systemen zoals Windows, Mac en Linux. Onderzoek toont aan dat programma's in Java ongeveer
1, 5
maal trager zijn dat die in
C/C++[63]. Er werd echter toch voor Java gekozen om dit project in te ontwikkelen gezien dit de productiesnelheid aanzienlijk zou verhogen.
60
HOOFDSTUK 6.
METAHEURISTIEK
6.3.6 DSH in Java De software werd geschreven in NetBeans IDE 7.1.1.[64]. De software geschreven om het DSH-algortime te implementeren in Java is opgedeeld in verschillende onderdelen:
•
Conn.java
•
Deze klasse staat in voor de verbinding met de MySQL database.
Customer.java
Deze klasse voorziet de aanmaak van een klantobject met als eigenschappen zijn postcode, servicetime, ID, vraag, openingstijd, sluitingstijd en enkele algoritme speci eke eigenschappen zoals labeltime en skip. Verder wordt er nog bijgehouden wat de tijd is waarop deze node bezocht wordt en dewelke de lading van de bezoekende truck is op dat moment. Ze controleert ook of de postcode van de klant wel aanwezig is in de ledatabase. Indien dit niet zo is wordt aan de hand van de postcodeclusters (zie 6.3.2) een nieuwe postcode bepaald om mee te werken.
Het is aan de hand van deze laatste, dan de coordinaten van een
plaats worden ingelezen uit de tabel postcodes.
•
DSHAlgorithm.java
Dit is de kern van de implementatie van het DSH Algoritme.
In deze klasse
worden klantendata, truckdata en reistijden ingelezen uit tekstbestanden en database. Tevens wordt het algoritme beschreven onder performAlgorithm. Alle datastructuren worden geïnitialiseerd en door het gebruik van de datastructuur HashMap kan de ledata uit de database op een erg performante manier worden opgezocht en gebruikt worden. Het algoritme kan afhankelijk van de parameters alfa, reistijdenverschuiving en GRASP meermaals worden uitgevoerd. Als het volledige algoritme is uitgeoerd bestaat er een object publicBest met daarin de gegvens van de best gegenereeerde route.
Deze informatie kan later wor-
den gebruikt om een visuele weergaven te geven van de gegeneerde routes. De belangrijkste functies/procedures in deze klasse zijn:
∗
arrivalTime: deze berekent aan de hand van de informatie uit de database de geïnterpoleerde aankomsttijd van een truck tussen twee postcodes op een bepaald tijdstip.
∗
CalculateCosts: deze berekent de exacte kost van een oplossing.
∗
ndMinimalDistance:
deze zoekt de vier dichtstbijzijnde klanten vanuit
een bepaalde node. Indien de switch random aanstaat worden de derde en vierde node willekeurig bepaald.
De functie geeft de klanten in volgorde
terug zodat er een keuze kan gemaakt worden via GRASP.
∗
performAlgorithm: voert de eigenlijke routering uit.
6.3.
IMPLEMENTATIE VAN DSH-ALGORITME
∗
61
printRoute: geeft de route weer voor ofwel alle trucks in een route ofwel voor één truck afhankelijk van de input.
∗
readCustomers: leest de klantendata in uit een .txt bestand van de harde schijf en maakt voor elke klant een klantobject aan. De waardes zijn gescheiden door tabs en het bestand heeft de volgende structuur:
·
ID, postcode, vraag, openingstijd (uu:mm), sluitingstijd (uu:mm), servicetijd (in minuten)
∗
readTra c: deze maakt een query aan op basis van de ingelezen klanten en het depot om alle mogelijke ledata betreende deze klanten op te halen uit de database. Deze informatie wordt opgeslaan in een HashMap.
∗
readTrucks: leest alle trucks in uit een tekstbestand en maakt een Truck object aan voor elke entry. Het bestand is net zoals de klantendata gesplitst door tabs en heeft de volgende structuur:
·
ID, capaciteit, starttijd, vaste kost, tijdskost, afstandskost, trucktype (1=3PL)
•
Depot.java
maakt het mogelijk een depotobject aan te maken met als eigenschappen een postcode, servicetijd en een positie.
•
FrameWindow.java
In dit bestand wordt de volledige GUI beschreven van de applicatie. Zo wordt ondermeer de kaart ingevoegd en staan de procedures verantwoordelijk voor de gra sche weergave van de routes in dit bestand.
•
FrameWindowManager.java
•
Main.java
•
Deze is nodig om een GUI in Java op het scherm te brengen.
Deze le is de eerste die Java start en brengt de GUI op het scherm.
NodeGroup.java
Dit object stelt een verzameling van twee of vier nodes voor. Een node wordt gede nieerd als zijnde een Customer object (zie Customer.java).
•
OpslagObj.java
Deze klasse voorziet de mogelijkheid om een object aan te maken dat alle gegenereerde data in het programma bijhoudt. Indien deze module aanstaat wordt er voor elke instantie van het algoritme de volgende informatie bijgehouden:
62
HOOFDSTUK 6.
METAHEURISTIEK
alfa, de tijdsverschuiving, pogingnummer. van GRASP, de totale kost, het aantal gebruikte trucks, het totaal aantal klanten, het bediende aantal klanten, de volledige routering voor elke truck in deze oplossing.
Door deze data weg te
schrijven kan men de invloed van de verschillende parameters bestuderen.
•
Pair.java
Deze wordt gebruikt om een pair object aan te maken dat gebruikt wordt om unieke postcode combinaties: Van-Naar, op te zoeken in de ledata.
•
Triplet.java
Een triplet stelt een combinatie voor van een van-en-naar postcode in combinatie met de tijd. Triplets worden gebruikt om data op te zoeken in de ledata. Door analoog aan de indices in MySQL een hashcode te genereren kan men zeer snel data opzoeken uit de ledata.
•
Truck.java
Dit object stelt een truck voor en bevat de volgende eigenschappen: ID,capaciteit, starttijd, tijdskost, afstandskost, vaste kost, inhoud, type (eigen of 3PL) en een route object dat een lijst van bezocht klanten bijhoudt.
De volledige java code kan men terugvinden op digitale drager die aan dit document is toegevoegd.
6.3.7 Opensource mapping & routing software Om de gra sche weergave en de eectieve wegroutes tussen 2 klanten te bekomen worden twee verschillende technieken aangewend. OpenStreetMap[65] project.
Enerzijds wordt er gebruikt gemaakt van het
Dit project stelt de gratis kaarten ter beschikking die voor
deze software werden gebruikt. De data is volledig opensource en kan op elk moment als geheel gedownload worden van de website om zo eventueel een eigen kaartenserver op te zetten. Dit kan interessant zijn indien men niet afhankelijk wenst te zijn van het internet voor het bekijken van de kaarten. Anderzijds wordt er gebruikt gemaakt van de CloudMade[66] routing API om de exacte routeringen tussen twee discrete punten in het probleem te vinden. Een huidige beperking van deze API is dat het momenteel enkel mogelijk is om de korstte route tussen twee punten te bepalen. Dit stelt echter geen probleem gezien we de verkregen data als puur illustratief behandelen.
In de huidige implementatie wordt het depot zowel als start en eindpunt
aangegeven en vormen de klanten tussenliggende punten op de route, in de volgorde die werd berekend door het DSH algoritme. Gezien de relatieve onnauwkeurigheid van de postcodes en hun coördinaten t.o.v. van de reële positie van een klant is het mogelijk dat er geen route kan worden bepaald tussen
6.3.
IMPLEMENTATIE VAN DSH-ALGORITME
63
deze punten. In dit geval valt het programma terug op een eenvoudige voorstelling waarbij de verschillende punten door een lijnstuk worden verbonden.
6.3.8 Parameters In dit onderdeel worden de verschillende parameters besproken die gebruikt worden om het DSH-algoritme aan te sturen. De drie parameters die het verloop van het algoritme bepalen zijn respectievelijk:
1. Starttijdvariatie 2. Alfa 3. Het aantal pogingen.
Deze drie parameters zitten in elkaar gelust. Dit wil zeggen dat binnen een starttijdsvariatie er testen worden uitgevoerd waarin een aantal pogingen worden gedaan om tot een resultaat te komen.
Stel dat men voor de volgende parameters kiest: 4 starttijdsintervallen, alfa
van 0,6 t.e.m.
1 in stappen van 0,1 en 500 pogingen.
4 · 5 · 500 = 10.000
Dit zal er voor zorgen dat er
instanties van DSH naar een oplossing zoeken.
De starttijdvariatie zorgt ervoor dat de starttijden van de trucks verhoogd kunnen worden, om zo eventueel tot een betere totaaltijd te komen. De parameter alfa bepaalt hoe het GRASP algoritme toegepast wordt. Afhankelijk van de waarde alfa
α
en een willekeurig getal
R,
worden de volgende nodes gekozen zoals in het
stroomdiagram in guur 6.3. De laatste parameter, het aantal pogingen, zijnde het aantal maal dat de combinatie tijdsverschuiving/alfa wordt uitgevoerd door DSH. Er zijn verschillende parameters en zogenaamde switches (booleans) aangebracht doorheen de code van het programma. Hieronder volgt een overzicht van alle instelbare parameters en de invloed van die parameters op het verloop van het programma. De volgorde van de lijst komt overeen met de volgorde van verschijnen van de opties in de code.
random34
als boolean (True of False) bepaalt of in de procedure ndMinimalDistance
de derde en de vierde node willekeurig worden gekozen (True) of als zijnde derde en vierde meest nabije node (False).
debug
als boolean bepaalt of de ontwikkelaarsoutput zichtbaar is voor de gebruiker of
niet.
Indien deze op True staat zal men volgende berichten in de output van het
programma zien: Bij elke iteratie van DSH de parameters alfa,tijdsverschuiving en de GRASP poging, steeds indien een vrachtwagen in het depot aankomt, indien er geen klanten meer mogelijk zijn en de vrachtwagen terug naar het depot moet keren, in welke node de vrachtwagen momenteel is, informatie over alle controles (capaciteit, tijdvensters en terugkeermogelijkheid).
64
HOOFDSTUK 6.
Genereer willekeurig getal R tussen 0 en 1
METAHEURISTIEK
Kies node 4
Nee
Nee
Nee
Ja
Ja
Ja
Kies node 1
Kies node 2
Kies node 3
Figuur 6.3: Stroomdiagram keuze GRASP
output
als boolean zorgt ervoor dat alle resultaten worden opgeslaan in het object opslag
(OpslagObj).
Dit object wordt later weggeschreven naar een bestand om zo de
invloed van bepaalde parameters te kunnen bestuderen in externe software zoals Excel.
interpolatie
als boolean bepaalt of het programma op een interpolerende manier omgaat
met de data (True) of analoog aan het AMPL programma enkel de lowerbound neemt als zijnde de rouwe data beschikbaar uit de database.
Deze optie werd voorzien
om een fundamentele vergelijking toe te staan tussen het wiskundig model en de implementatie van het DSH-algoritme. Standaard staat deze waarde op True.
alfaStart
bepaalt als waarde (tussen 0 en 1) de start van het interval waartussen alfa mag
variëren.
alfaStop
bepaalt als waarde (tussen 0 en 1) het einde van het interval waartussen alfa
mag variëren.
alfaDelta
is de stapgrootte waarmee er van alfaStart tot alfaStop wordt gegaan.
Deze
waarde wordt bij de huidige alfa geteld totdat alfaStop wordt overschreden.
graspPogingen
is het aantal keren dat een test wordt uitgevoerd voor eenzelfde waarde
vor alfa en starttijdverschuiving.
deltaTijd
is de tijd in minuten waarmee de starttijdsverschuiving per iteratie mee wordt
verhoogd.
startTijdIntervallen
is het aantal keren dat de starttijd van de trucks moet worden
verhoogd met de waarde deltaTijd. Bv.: indien deltaTijd 15 is en startTijdIntervallen 4, dan wordt de starttijd van de truck met maximaal 1 uur (60 minuten) verhoogd.
6.3.
IMPLEMENTATIE VAN DSH-ALGORITME
65
6.3.9 Verloop van het programma Indien de gebruiker het java programma opstart vanuit de IDE(Integrated Developer Environment) wordt hem een GUI voorgeschoteld zoals in guur 6.4. Het programma bestaat uit 3 elementen met elk hun functie:
•
De adresbalk
Hier heeft men het absolute pad naar de werkmap in.
Dit pad moet van de
vorm X: \...\..\ zijn. De De commitknop zorgt er voor dat het programma start met het oplossen van het probleem.
•
Het statusvenster
In dit onderdeel van de GUI kan men de interne voortgang uitlezen van het programma. Als er fouten optreden bij het inlezen van de databestanden worden deze ook in dit venster gemeld.
•
De kaart
Deze component geeft na het drukken op Commit de posities van de depots en nodes weer met hun onderlinge routes.
De volgorde waarin de nodes worden
bezocht gebeurd op basis van de uitkomst van het algoritme. Elk bestand dat wordt verwerkt krijgt een eigen kleur op de kaart. De eigenlijke routering tussen twee punten moet men als puur illustratief beschouwen. Voor deze 'subroute' wordt de shortest path methode gebruikt.
Men kan navigeren door ofwel te slepen met de rechtermuisknop, te dubbelklikken met de linkermuisknop om in te zoomen, door gebruik te maken van het scrollwiel of door gebruik te maken van de slider en bijhorende knoppen in de linkerbovenhoek van de kaart.
Om het algoritme te con gureren moet de gebruiker een werkmap aanmaken met daarin enkele bestanden die verloop van het programma zullen bepalen. Het eerste bestand zorgt voor de con guratie van het DSH-algoritme. Hiervoor maakt men een con g.ini bestand aan in de werkmap. Dit con guratiebestand heeft een structuur zoals in code 6.5. Indien wenselijk kan men vrij commentaren aanbrengen in dit bestand door middel van #. Elke parameters die in onderstaand bestand aanwezig is, is verplicht. Zonder dit con guratiebestand zal het DSH-algoritme niet functioneren. Om aan te geven welke vloot beschikbaar is voor het programma voegt men het bestand truck le. f toe aan de werkmap. in de FIF (Fleet Information File) kan men eenvoudig trucks de niëren door een regel toe te voegen zoals in code 6.4. Belangrijk is dat de waardes van elkaar moeten gescheiden worden met een tab. Deze tab wordt voorgesteld door een pijl: ->. Door de optie 3PL op 0 of 1 te zetten vertelt men het programma of de truck behoort tot de eigen vloot of niet.
66
HOOFDSTUK 6.
METAHEURISTIEK
Figuur 6.4: DSH GUI
Code 6.4 truck le. f ID−>L a d i n g −>S t a r t t i j d
−>V a s t e
Kost −>K o s t / min−>K o s t /km−>3PL
Voorbeeld: 1
350
06:00
50
1
0
0
2
100
06:15
100
1.3
0
0
Klanten en hun eigenschappen kan men ingeven in .dsh bestanden.
Deze hebben een
structuur zoals in code 6.6. Analoog aan de f, zijn de waardes van elkaar gescheiden door het gebruik van een tab. Deze wordt voorgesteld door ->. Het is belangrijk te weten dat de eerste regel altijd als depot wordt beschouwd. Dit stelt dus de locatie voor vanwaar uit de transportmiddelen zullen vertrekken. Men kan eenvoudig het programma routes laten aanmaken voor meerdere dagen/logische verdelingen door eenvoudigweg meerdere .dsh bestanden in de werkmap te plaatsen. Een laatste maar belangrijke opmerking is dat de bestandsnamen geen spaties mogen bevatten.
Na het aanpassen van de werkmap, drukt de gebruiker op de knop commit. Het werkpad moet eindigen op een backslash. Als dit gebeurt starten er een reeks van procedures die de gehele dataset initialiseren en het algoritme uitvoeren. Het programma scanned voor alle bestanden in de werkmap met de extensie .DSH of .dsh. Voor elk van deze bestanden wordt er een output bestand aangemaakt met de extensie .dsh.out.
De naam van de
output is gelijk aan de naam van het klantenbestand met als extensie .dsh.out.
6.4.
TESTEN VAN DSH
67
Code 6.5 con g.ini ####C o n f i g u r a t i e #C o n f i g u r a t i e
DSH
alfa
a l f a S t a r t =0.0 a l f a S t o p =1.01 a l f a D e l t a =0.01 #C o n f i g u r a t i e GRASP p o g i n g e n =1000 #C o n f i g u r a t i e
starttijdsverschuiving
( in
minuten )
d e l t a T i j d =15
v e r s c h u i v i n g e n =0 ####C o n f i g u r a t i e
Runtime DSH
#Random GRASP 34 random34= f a l s e #D e b u g g e r
output
in
console
debug= f a l s e #V o l l e d i g e
datadump
#WAARSCHUWING met #h e t
systeem
output
grote
aanzienlijk
testsets
zal
deze
operatie
vertragen
o u t p u t= f a l s e #I n t e r p o l a t i e
tussen
datapunten
uit
database
i n t e r p o l a t i e =t r u e
Code 6.6 klantenbestand.dsh Naam−>P o s t c o d e −>Vraag−>O p e n i n g s t i j d −> S l u i t i n g s t i j d
−> S e r v i c e t i j d
Voorbeeld: D
1000
0
00:00
24:00
20
6
6000
20
06:00
08:00
17
4
4000
10
06:00
12:00
15
De ow van het programma kan men volgen in guur 6.5. De manier waarop het de kern van het programma, zijnde het DSH algoritme, door zijn iteraties loopt, kan men volgen op guur 6.6. De duur van het programma om tot een resultaat te komen is zeer afhankelijker van het aantal keren dat het DSH algoritme naar een oplossing moet zoeken. Het aantal keer dat DSH naar een oplossing moet zoeken is parameter afhankelijk. De verschillende parameters worden verklaard in de vorige sectie.
6.4
Testen van DSH
Zoals besproken bij de implementatie van de heuristiek, is het zowel mogelijk om de heuristiek uit te voeren met een vaste starttijd van de trucks als met een variabele starttijd van de trucks. Logischerwijze zal de methode met een variabele starttijd betere resultaten bekomen. Om de heuristiek met het AMPL model te kunnen vergelijken, worden alle testcases eerst uitgevoerd met dezelfde vaste starttijd van 360. Aangezien een troef van de heuristiek is dat de starttijd variabel kan ingesteld worden, zullen daarna alle testcases onderzocht worden met deze variabele starttijd.
68
HOOFDSTUK 6.
METAHEURISTIEK
Inlezen filedata
Inlezen truckdata
Output beste resultaat in x.dat
Inlezen klantendata x.txt
DSH-Algortime
Tijdsverschuiving Alfa Grasp
Herhaal voor alle parameters Figuur 6.5: Verloop DSH in Java
6.4.1 Testcase 1: Vaste starttijd De oplossing, zichtbaar in code 6.7, werd bekomen in
30, 156
milliseconden (ongeveer 30
seconden). Met de volgende kostenparameters bepaalt de Java code de beste route en de totaalkost in tabel 6.2.
Code 6.7 Output Java testcase 1:vaste starttijd Depot := 1000 Klanten := 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000 Vertrektijd := 360 (interval 24) Algemene vorm Java output := klantID ; Postcode ; aankomsttijd ; truckload Java output := D;1000;360;0 3;3000;392;100 4;4000;473;110 5;5000;544;160 6;6000;596;180 7;7000;648;190 8;8000;764;250 9;9000;834;290 2;2000;899;320 D;1000;965;0
De route van deze testcase is zichtbaar in guur 6.7.
De route die het DSH-Algoritme
genereerde is exact dezelfde als die van het AMPL resultaat.
Het grote verschil tussen
beide routes is dat ze in de omgekeerde richting worden afgelegd door de voertuigen. Dit is natuurlijk een belangrijk verschil gezien de tijdsafhankelijkheid van de reistijden tussen de klanten.
6.4.2 Alle testcases: vaste starttijd De resultaten van alle andere testcases zijn zichtbaar in code 6.8
6.5.
BEPALEN VAN DE GAP
69
#trucks
1
Vaste kost
100
Reiskost
1
#klanten
10
Servicetijd
15
Servicekost
1
Iteraties per GRASP alfa
1000
Alfa min
0
Alfa max
1
Alfa staplengte
0,01
Totaalkost
705,00
Tabel 6.2: Kostenbepaling testcase 1: heuristiek: vaste starttijden.
6.4.3 Testcase 1: variabele starttijd Men kan hier dus opmerken dat de starttijd van de trucks verlaat wordt tot 495. heuristiek werd uitgevoerd op
399.625
Deze
milliseconden (ongeveer 6.5 minuten). Met de kos-
tenparameters in 6.9 bepaalt de Java code de beste route en de totaalkost. #trucks
1
Vaste kost
100
Reiskost
1
#klanten
10
Servicetijd
15
Servicekost
1
Iteraties per GRASP alfa
1000
Alfa min
0
Alfa max
1
Alfa staplengte
0,01
Totaalkost
700,00
Tabel 6.3: Kostenbepaling testcase 1: heuristiek: variabele starttijden.
De route bekomen door deze aanpak is dezelfde als bij AMPL en de case met vaste starttijd ( guur 6.7). Het kostenverschil tussen de vaste en variabele starttijd is dus te wijten aan het tijdsafhankelijke karakter van de routering.
6.4.4 Alle testcases: variabele starttijd De resultaten van alle andere testcases zijn zichtbaar in code 6.10
6.5
Bepalen van de gap
Om de performantie van de heuristiek na te gaan is het aangewezen om de gap te bepalen tussen de exacte oplossingsmethode via AMPL en de heuristiek. Het is de bedoeling om de vergelijking tussen de heuristiek en het AMPL model zo eerlijk mogelijk te laten verlopen.
70
HOOFDSTUK 6.
Code 6.8 Resultaten testcases 2 t.e.m. •
Klanten := 1600, 1800, 1880, 2150, 2300, 2400, 2650, 2800, 3300, 6000 Kost := 663
Depot := 1000 Klanten := 1150, 1200, 9300, 9340, 9400, 9450, 9550, 9600, 9850, 9900 Kost := 624
Testcase 4
•
Depot := 1000
Testcase 3
•
5 met vaste starttijden.
Testcase 2
•
METAHEURISTIEK
Depot := 1000 Klanten := 4600, 4700, 4900, 5000, 53000, 5500, 6000, 6200, 6500, 6600 Kost := 804
Testcase 5
Depot := 1000 Klanten := 7000, 7100, 7300, 7500, 7600, 7700, 7800, 7900, 8000, 8300 Kost := 674
Daarom wordt eerst de gap bepaald tussen het AMPL model met jnere intervallen zoals in sectie 5.5.3. Hier kunnen we enkel vergelijken voor heel kleine testcases, anders krijgt men een "out of memory" fout bij AMPL. Aangezien bij AMPL de starttijd 360 is, zal de gap vergeleken worden met een vaste starttijd van 360 voor de DSH heuristiek.
Na de vergelijking tussen heuristiek en benaderend model met ver jnde intervallen, wordt eerst bekeken hoeveel het ver jnde interval verschilt met het benaderende intervalmodel met intervallen per 15 minuten, even nauwkeurig dus dan de aangereikte data. Indien deze gap klein genoeg is, wordt de rest van de gaps bepaald met dit benaderende intervalmodel per 15 minuten als basis, aangezien het ver jnde intervalmodel te rekenintensief blijkt.
De gap wordt bepaald tussen het benaderende AMPL model en de heuristiek, waarbij de intervallen in het AMPL model wel per 15 minuten lopen, even nauwkeurig dus dan de aangereikte data. De heuristiek wordt hier ook ingesteld op een vaste starttijd. Daarna wordt de gap bekeken tussen het benaderend AMPL model en de metaheuristiek op diens volle kracht, dit wil zeggen met variabele starttijd en alle andere parameterwijzigingen.
Om af te sluiten wordt bekeken wat de gap is tussen de metaheuristiek met vaste starttijden en variabele starttijden, dit om na te gaan of het de extra tijd en moeite waard is om het programma te laten lopen met variabele starttijden.
6.5.
BEPALEN VAN DE GAP
71
Code 6.9 Output Java testcase 1:variabele starttijd Depot := 1000 Klanten := 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000 Vertrektijd := te bepalen door de heuristiek Algemene vorm Java output := klantID ; Postcode ; aankomsttijd ; truckload output Java := D;1000;495;0 3;3000;530;100 4;4000;606;110 5;5000;670;160 6;6000;721;180 7;7000;773;190 8;8000;889;250 9;9000;958;290 2;2000;1028;320 D;1000;1095;0
6.5.1 Gap tussen AMPL met ver jnde intervallen en heuristiek Aangezien het ver jnde benaderende model en de heuristiek hier vergeleken worden met gelijkaardige eigenschappen zoals intervallengte en starttijd, is het nodig dat alle gaps positief zijn. Dit wil zeggen dat voor elke testcase de kost voor het ver jnde benaderende wiskundig model maximaal even groot mag zijn dan de heuristiek. Indien niet het geval is moeten de methoden herbekeken worden. Deze gaps worden gecontroleerd met de testcases die reeds gede nieerd werden in sectie 5.5.3. Testcase
kost AMPL
kost heuristiek
gap (%)
1A
437
438
0,03
1B
540
548
1,40
1C
663
664
0,09
1
698*
705
0,99
Tabel 6.4: Gaps tussen het AMPL model met ver jnde intervallen en heuristiek.
In tabel 6.4 is te zien dat alle gaps positief zijn en dat deze gaps zeer klein zijn.
Dit
wil zeggen dat het ver jnde benaderende model beter presteert dan de heuristiek met vaste starttijden. Dit is logisch aangezien hier een exact model vergeleken wordt met een heuristiek met dezelfde nauwkeurigheid. Het feit dat deze gaps zo klein zijn toont aan dat de heuristiek heel performant is, er worden namelijk bijna even optimale kosten bekomen met de heuristiek dan met het ver jnde wiskundig model.
6.5.2 Gap tussen AMPL ver jnd en benaderend intervalmodel Het is nodig om de gap te bepalen tussen het ver jnde en het benaderende intervalmodel. Wanneer deze gap klein genoeg is, mag voor de berekening van de hierop volgende gaps gebruik gemaakt worden van het benaderende intervalmodel. Dit is namelijk berekenbaar in een kortere rekentijd en daarom kunnen er meer testen op uitgevoerd worden. Ook deze
72
HOOFDSTUK 6.
Code 6.10 Resultaten testcases 2 t.e.m. •
Klanten := 1600, 1800, 1880, 2150, 2300, 2400, 2650, 2800, 3300, 6000 Kost := 659
Depot := 1000 Klanten := 1150, 1200, 9300, 9340, 9400, 9450, 9550, 9600, 9850, 9900 Kost := 621
Testcase 4
•
Depot := 1000
Testcase 3
•
5 met variabele starttijden
Testcase 2
•
METAHEURISTIEK
Depot := 1000 Klanten := 4600, 4700, 4900, 5000, 53000, 5500, 6000, 6200, 6500, 6600 Kost := 792
Testcase 5
Depot := 1000 Klanten := 7000, 7100, 7300, 7500, 7600, 7700, 7800, 7900, 8000, 8300 Kost := 657
gaps worden gecontroleerd met de testcases die reeds gede nieerd werden in sectie 5.5.3. De uitleg hiervoor werd reeds gegeven in sectie 5.5.3. Testcase
Kost ver jnd
Kost interval
Gap (%)
1A
437,8
438
0,03
1B
540,4
545
0,84
1C
663,4
664
0,09
1
698*
702,78
0,68
Tabel 6.5: Bepaling gap tussen AMPL ver jnd en benaderend intervalmodel
Uit tabel 6.5 kan men a eiden dat de gap tussen het ver jnde en het benaderende intervalmodel klein genoeg is om vanaf nu gaps te gaan berekenen tussen het benaderende intervalmodel en de metaheuristiek. Hierbij moet men wel in het achterhoofd houden dat de gaps die vanaf nu berekend worden niet exact zijn, maar eerder een aanwijzing voor de performantie van de DSH metaheuristiek zijn.
6.5.3 Gap tussen AMPL en heuristiek: vaste starttijden In tabel 6.6 is te zien dat deze gaps miniem zijn en voor twee cases zelfs al negatief. Dit kan men verklaren aangezien in het benaderend model van AMPL een vereenvoudiging van de realiteit werd ingevoerd, zodat de reistijden bepaald werden aan de hand van hun
6.5.
BEPALEN VAN DE GAP
interval.
73
Deze vereenvoudiging werd ingevoerd om de berekening en routegeneratie via
AMPL in een haalbare rekentijd te laten verlopen.
Dit is robuuster dan de realiteit en
op die manier minder nauwkeurig dan de DSH heuristiek. Bij de DSH heuristiek wordt hetzelfde algoritme namelijk een groot aantal keren uitgevoerd en wordt het minimum daarvan als oplossing genomen. Daarom is het zeker een mogelijk uitkomst dat de DSH heuristiek beter presteert. Testcase
Kost AMPL
Kost heuristiek
Gap(%)
1
702,78
705
0,31
2
665,23
663
-0,34
3
629,8
624
-0,93
4
799,9
804
0,51
5
665,13
674
1,32
Tabel 6.6: Gap tussen AMPL model en heuristiek: vaste starttijden
6.5.4 Gap tussen AMPL en heuristiek: variabele starttijden Aangezien de kracht van de heuristiek in zijn snelheid zit, is het mogelijk om deze heuristiek verschillende duizenden keren na elkaar te laten uitvoeren waarbij verschillende parameters telkens gewijzigd worden, zoals de GRASP parameter en de starttijd van de trucks. Aangezien AMPL deze exibiliteit niet heeft, is het logischer om het complete benaderende model te vergelijken met de complete heuristiek. Dit wil zeggen dat we de performantie van het AMPL model zullen vergelijken met de performantie van de heuristiek wanneer deze volledig in werking is, dus ook met variabele starttijden. In tabel 6.7 is te zien dat de DSH heuristiek voor elke testcase beter is dan de oplossing via het benaderend wiskundig model in AMPL. Testcase
Kost AMPL
Kost heuristiek
Gap(%)
1
702,78
700
-0,40
2
665,23
659
-0,95
3
629,8
621
-1,42
4
799,9
792
-1,00
5
665,13
657
-1,24
Tabel 6.7: Gap tussen AMPL model en heuristiek: variabele starttijden
6.5.5 Gap tussen heuristiek met vaste en variabele starttijden De heuristiek heeft ongeveer tien keer meer tijd nodig om routes te genereren wanneer gewerkt wordt met een variabele starttijd tegenover een vaste starttijd. In het geval van testcases met een tiental klanten komt dit op 10 minuten in plaats van 1 minuut.
Om
te bepalen of deze extra tijd het waard is om met variabele starttijd te rekenen, worden de twee kosten met elkaar vergeleken. In tabel 6.8 kan men zien dat het verschil tussen vaste en variabele starttijd niet groot is. Dit is echter maar op een testcase van een tiental
74
klanten.
HOOFDSTUK 6.
METAHEURISTIEK
Wanneer dit uitvergroot wordt tot realistische datasets kan er een signi cant
kostenverschil optreden. Het is dus nuttig om toch met een variabele starttijd rekening te houden bij het genereren van tijdsafhankelijke routes. Testcase
Kost variabele starttijd
Kost vaste starttijd
Gap (%)
1
700
705
0,71
2
659
663
0,60
3
621
624
0,48
4
792
804
1,49
5
657
674
2,52
Tabel 6.8: Gap tussen heuristiek met vaste en variabele starttijden
Figuur 6.6: Intern verloop van DSH
START
Zijn er nog klanten in customers?
Neen
Voeg depot toe aan truck.route Update truck.content=0 Update huidige tijd Huidige node = depot Alle nodes terug bereikbaar
Ja
STOP huidige truck
Neen
Neen
Kan de truck de vraag van deze node aan?
Neen
Ja
Zoek dichtste punt (GRASP) in bereikbare nodes.
Zet node op onbereikbaar.
Zet node op onbereikbaar.
Neen
Kan de truck de vraag van deze node aan?
Zijn er nog bereikbare nodes?
Neen
Zitten we in het depot?
Ja
Zijn er nog bereikbare nodes?
Ja
Zoek dichtste punt (GRASP) in bereikbare nodes.
Ja
Ja
Terug naar depot mogelijk?
Neen
Neen
Terug naar depot mogelijk?
Ja
Ja
Ja
Mogelijk binnen tijdsvenster?
Neen
Ja
Voeg node toe aan truck.route Update truck.content Update huidige tijd Verwijder klant uit klanten. Huidige node = bediende node Alle nodes terug bereikbaar
Neen
Mogelijk binnen tijdsvenster?
6.5. BEPALEN VAN DE GAP 75
76
HOOFDSTUK 6.
METAHEURISTIEK
Breedtegraad
Routering Testcase 1 51,30 51,20 51,10 51,00 50,90 50,80 50,70 50,60 50,50 50,40 50,30 3,00
3,50
4,00
4,50 Lengtegraad
Route
5,00
5,50
Depot
Figuur 6.7: Routering testcase 1:heuristiek
6,00
Hoofdstuk 7
Invloed van de parameters Teneinde de heuristiek beter te begrijpen en ten volle te benutten, is het nodig om een gedetailleerd inzicht te krijgen in de invloed van verschillende parameters van het programma. Hieronder zullen de invloeden van de belangrijkste parameters besproken worden.
7.1
GRASP parameter
α
Zoals reeds uitgelegd in SECTIE bepaalt de GRASP parameter node zal genomen worden als volgende klant.
Hoe groter
α,
α
met welke kans welke
hoe groter de kans dat de
dichtstbijzijnde klant zal worden gekozen als de volgende klant in de route.
Hieronder
worden drie mogelijkheden besproken. Eerst wordt de optie bekeken met twee alternatieven: de dichtste en de tweede dichtste node. Daarna wordt bekeken hoe de oplossing kan veranderen wanneer er door GRASP vier mogelijke volgende nodes zijn. Tenslotte wordt onderzocht of het nuttig is om met een kleine kans te rijden naar een willekeurige node. Dit wordt gedaan om de kans op outliers te minimaliseren.
Het is belangrijk om op te
merken dat voor deze testen de vaste kost voor de trucks op 0 gezet wordt. Dit heeft geen impact op de werking van het algoritme. Voor alle volgende tests werd alfa incrementeel verhoogd tussen 0 en 1 met als stapgrootte 0,01.
7.1.1 GRASP 1-2 Hierbij wordt de dichtstbijzijnde klant de volgende zolang het random getal kleiner is dan
α,
anders wordt de op één na dichtstbijzijnde klant de volgende klant in de route.
De
resultaten van deze studie zijn zichtbaar in guur 7.4. Wanneer nu de invloed bestudeerd wordt van de parameter worden wanneer
α
α,
kan men merken dat tevens de beste resultaten verkregen
varieert tussen 0,7 en 1. Een uitzondering hierop is testcase 1, dit valt
te verklaren door het feit dat de parameterinvloed van
α
heel caseafhankelijk is en bij
testcase 1 de klanten heel ver uit elkaar liggen. Aangezien bij testcase 1 deze afstanden zo hoog zijn, is de kans op een outlier veel hoger. Een algemene trend is echter dat er betere resultaten verkregen worden voor hogere waarden van 77
α.
78
HOOFDSTUK 7.
INVLOED VAN DE PARAMETERS
Testcase 2
800
750
750
700
Kost
Kost
Testcase 1
700 650
650 600
0
0,5
1
0
0,5
Parameter alfa
Parameter alfa
Testcase 4
Testcase 3
1000
850 750
Kost
Kost
1
650
900 800
550 0
0,5
0
1
0,5
1
Parameter alpha
Parameter alpha
Testcase 5 Kost
750 700 650 600 0
0,5
1
Parameter alpha Figuur 7.1: Resultaten GRASP 1-2
7.1.2 GRASP 1-2-3-4 Het is aangewezen om de GRASP methode meer doorslag te geven om op die manier outliers zoveel mogelijk te elimineren. Op guur 7.2 wordt voor de duidelijk weer weergegeven op welke manier de keuze gemaakt wordt voor de volgende klant in de route.
Hierbij stelt
"Node 1" de dichtstbijzijnde node voor, "Node 2" de op één na dichtstbijzijnde node, enzovoort. Wanneer de verschillende testcases worden uitgevoerd volgens bovenstaande strategie bekomt men een kostenverloop afhankelijk van de GRASP parameter
zoals in FIGUUR.
Hieruit kan men opnieuw bevestigen dat de laagste kost telkens gevonden wordt wanneer varieert tussen 0,7 en 1. De resultaten van deze testen zijn terug te vinden in guur 7.3.
7.1.3 GRASP 1-2-R-R Voor de volledigheid wordt ook elke testcase getest met een GRASP scenario waarbij keuze 3 en 4 ingesteld worden op willekeurige nodes. Dit geeft echter geen noemenswaardige verschillen met het 1-2-3-4 GRASP scenario.
Aangezien de complexiteit verhoogt
wanneer het 1-2-Random-Random scenario gebruikt wordt zonder merkbare verbetering, wordt geopteerd voor de 1-2-3-4 GRASP strategie voor het oplossen van alle testcases en de uiteindelijke Palm case.
7.2.
STARTTIJDEN VAN DE TRUCKS
79
Genereer willekeurig getal R tussen 0 en 1
Kies node 4
Nee
Nee
Nee
Ja
Ja
Ja
Kies node 1
Kies node 2
Kies node 3
Figuur 7.2: Stroomdiagram keuze GRASP 1-2-3-4
7.2
Starttijden van de trucks
Een grote kracht van de heuristiek is het feit dat de starttijd kan variëren om zo op zoek te gaan naar de minimale kost voor een bepaalde klantenset. In het onderzoek werd elk van de vijf testcases onderzocht naar invloed van de starttijd, telkens met 4 mogelijk waarden voor de GRASP parameter
namelijk ={0.7 ; 0.8 ; 0.9 ; 1} aangezien deze in vorige paragraaf
als beste waarden bekomen werden. Het is belangrijk om op te merken dat de invloeden enkel besproken worden voor routeringen waarbij elke klant bezocht wordt. Het is namelijk de bedoeling dat elke klant bezocht wordt binnen de planningsperiode. Net zoals bij de invloed van de GRASP parameter wordt voor de komende berekeningen geen rekening gehouden met de vaste kost van een truck.
Dit wordt gedaan om de variabele kost zo
zuiver mogelijk te evalueren. Op guur 7.4 is voor de eerste testcase te zien dat de totaalkost daalt naarmate de starttijd verlaat. Dit kan echter niet eindeloos doorgaan aangezien de routering van de dag verplicht alle klanten moet bezoeken. Deze resultaten bevestigen het belang van de implementatie van een variabele starttijd in het DSH algoritme. In appendix XXX kunnen de resultaten teruggevonden worden voor de andere testcases.
7.3
Servicetijden bij de klanten
Standaard staat de servicetijd bij de klanten op vijftien minuten. Het kan echter interessant zijn om de invloed van de servicetijd te bekijken om op die manier na te gaan of een kortere servicetijd een grote invloed heeft op de totaalkost van de routering. Zoals te zien is op guur 7.5 is de invloed van de servicetijd heel lineair. Kleine afwijkingen van een evenredig gedrag van de kost tegenover de servicetijd zijn te verklaren door het tijdsafhankelijke karakter van de reistijden. De invloed van de servicetijd wordt op guur 7.5 aangetoond voor de vijfde testcase. Aangezien dit quasi evenredig gedrag identiek is voor alle andere testcases, worden de resultaten hiervan niet opgenomen in deze thesispaper.
80
HOOFDSTUK 7.
INVLOED VAN DE PARAMETERS
Testcase 2
780 760
Kost
Kost
Testcase 1 740 720 0
0,5
800 750 700 650 600
1
0
0,5
Parameter alfa
Parameter alfa
Testcase 3
Testcase 4 Kost
Kost
750 650 550 0
1
0,5
850 750 650 550
1
0
Parameter alpha
0,5
1
Parameter alpha
Testcase 5 Kost
850 750 650 550 0
0,5
1
Parameter alpha Figuur 7.3: Resultaten GRASP 1-2-3-4
Alpha = 0,8
Alpha = 0,7 760
Kost
Kost
760 680 600
600 360
395
430
465
500
360
395
430
Starttijd
Starttijd
Alpha = 0,9
Alpha = 1
760
465
500
465
500
760 Kost
Kost
680
680 600
680 600
360
395
430 Starttijd
465
500
360
395
430 Starttijd
Figuur 7.4: Invloed van starttijden trucks op de totale kost.
SERVICETIJDEN BIJ DE KLANTEN
81
800
Kost
7.3.
Alfa 0,7
600
Alfa 0,8 Alfa 0,9 Alfa 1
400 0
10
20
30
Servicetijd Figuur 7.5: Invloed van de servicetijd op de kost voor testcase 5
82
HOOFDSTUK 7.
INVLOED VAN DE PARAMETERS
Hoofdstuk 8
Routering voor Palm Breweries 8.1
Inleiding
In dit hoofdstuk wordt het ontwikkelde DSH-algoritme toegepast op de businesscase van Palm Breweries. In de huidige situatie beschikt palm over een set eigen trucks en wordt er i de hulp van een externe transport rma ingezet ter aanvulling van de transportvloot. In dit hoofdstuk wordt er bekeken op welke manier het klantenbestand van Palm Breweries kan worden bevoorraad en meer speci ek welke zijn de dagelijkse routes die moeten gereden worden. Door het klantenbestand te verwerken kan men zowel dagelijkse routes ontwikkelen als strategische beslissingen nemen betreende de jaarlijkse transportkosten. Het bestaande werk dat reeds werd uitgevoerd door Ir.
J.Denys in zijn thesis [67] zal
grotendeels als basis worden beschouwd om verdere verbeteringen te implementeren bij het distributiesysteem van Palm Breweries. De belangrijkste input die wordt gebruikt om de case op te lossen zijn de kostenbepalingen en de 3W (Wie,Wat en Wanneer) data. De case die hierna volgt is beperkt tot een tijdspanne van 50 dagen en beschouwd en dit voor de 100 grootste klanten voor Palm. Op de data worden verschillende scenario's uitgevoerd die het mogelijk moeten maken om enkele strategische beslissingen te nemen betreende de uitbreiding van de vloot of de eventuele aankoop van extra opleggers.
8.2
Assumpties
Palm beschikt over 4 eigen trucks. Indien er niet aan deze capaciteit kan worden voldaan worden 3PL (Third Party Logistics) ingezet om tegemoet te komen aan de transportcapaciteit die nodig is. Elk van de Palm trucks wordt gemodelleerd door in de eet information door de juist eigenschappen toe te kennen aan de trucks. Gezien in het geval van Palm we te maken hebben met een uitgebreide productmix zal er een vereenvoudiging moeten plaatsvinden betreende deze producten.
De producten
worden als gelijk beschouwd. Aan de hand van conversiefactoren worden de verschillende 83
84
HOOFDSTUK 8.
ROUTERING VOOR PALM BREWERIES
producten omgezet naar de zelfde eenheid: liters. De vraag van de klanten wordt dus ook uitgedrukt in liters. Als uitbreiding op voorgaande thesis is het wel mogelijk om meerdere ritten uit te voeren per truck per dag. Hoewel dit in realiteit ook mogelijk is, wordt er echter geen rekening gehouden met verplichte rij en rusttijden om het probleem op te lossen. De grootste trucks beschikken over een capaciteit van 12.500 liter.
8.3
Kostenparameters
Om het mogelijk te maken eventueel een vergelijking aan te gaan tussen de vorige thesis bij Palm en de huidige oplossingen wordt een kostenstructuur zoals in tabel 8.1 toegepast op het probleem. De andere kosten worden niet in rekening gebracht in deze thesis. Factor
Kost
Eenheid
Eigen transport per uur
40
per uur
Eigen transport per km
0,6
per km
Kost extern transport
52
per uur
Vaste kost extern transport
124
per dag
Tabel 8.1: Transportkosten
8.4
Aanpak
Om verschillende businesscases te kunnen uitvoeren op het klantenbestand van Palm Breweries wordt er gefocust op de transportcomponent van het probleem. De volgende invloeden worden bestudeerd en hun impact op de totale kosten voor de bestudeerde periode worden besproken:
•
Het inzetten van meer eigen rollende materieel. D.w.z. bestuderen wat de impact zou zijn op de totale kost mochten er extra voertuigen in eigen beheer genomen worden.
•
Het bestuderen van de impact van de aanschaf van extra opleggers. Het aankopen van extra opleggers resulteert in een reductie van de laad en los tijden in het depot van 1 uur naar 15 minuten.
Gezien het algoritme en zijn parameters grondig werd besproken in hoofdstuk 7 werd er geopteerd om de volgende instellingen te gebruiken: parameter alfa van 0,6 tot 1 in stappen van 0,05, 1000 GRASP pogingen en 8 verschuivingen van elk 30 minuten. Dit resulteert in 36.000 routes waaruit de beste optie wordt aanvaard. Dit wordt uitgevoerd voor elk van de 50 input les. De servicetijden worden als volgt aangekomen. Om de goederen te lossen bij een klant gebruiken we standaard een tijd van 30 minuten. Een vrachtwagen opnieuw vullen in het depot neemt 1 uur in beslag. Er wordt een con g.ini en een truck le. f aangemaakt
8.5.
IMPACT VAN HET AANKOPEN VAN EXTRA OPLEGGERS
85
om de algemene parameters van het model en de informatie rond de beschikbare trucks te bepalen. De vorm van deze inputdata werd reeds besproken. Het resultaat van bovenstaande is een kost van 18.453 over een tijdspanne van 50 dagen voor de 100 grootste klanten. De trucks die worden ingegeven in de . f le zijn beschikbaar voor elke dag. Dit wil zeggen dat elke routering beschikt over dezelfde set trucks. Gezien de performantie van de heuristiek ten opzichte van de zowel exacte als benaderende modellen is het mogelijk om per dag een routering te generen voor alle trucks.
Het is
echter ook mogelijk om meerdere dagen te onderwerpen aan het DSH-Algoritme om aldus een set van strategische beslissingen te kunnen nemen aan de hand van gedetailleerde routeringskosten. Om verder te gaan dan enkel de kosten die gepaard gaan met het routeren van de trucks en zijn goederen, zou men het 3W model moeten toepassen uit de vorige thesis. Dit valt echter buiten het bestek van de huidige thesis.
8.5
Impact van het aankopen van extra opleggers
Figuur 8.1: Route voor 30 dagen ter illustratie van de routeringsoftware.
Gezien het aankopen van extra opleggers voor een reductie in tijd met zich meebrengt betreende de tijd dat een truck moet wachten om opnieuw uit te rijden, zou men verwachten dat hier een aanzienlijk kostenvoordeel mee gepaard zou gaan gezien de trucks langer op de baan kunnen zijn en er minder onkosten betaald moeten worden. Uit enkele tests bleek echter dat de impact van dergelijke operatie miniem bleek. Over de hiervoor reeds besproken proefperiode van 50 dagen bleek dat de resulterende kost zelfs marginaal
86
HOOFDSTUK 8.
ROUTERING VOOR PALM BREWERIES
slechter zou zijn. Het resultaat voor dit opzet is 18.532. Dit komt overeen met een stijgen van de kosten van ongeveer 0,5%. Dit schijnbaar vreemde resultaat is eenvoudig te verklaren gezien er rekening moet gehouden met de tijdsgevoeligheid van het systeem.
Het is mogelijk dat deze impact om
voorgaande reden zelfs een slecht eect heeft op de totale reistijd en dus kost.
Hoofdstuk 9
Future research Momenteel wordt in het heuristisch DSH-algoritme een oplossing gegenereerd voor een TDVRPTW. Er is echter nog geen manier voorzien om de initiële oplossing te optimaliseren, bijvoorbeeld door het toevoegen van lokale zoekoperatoren voor tijdsafhankelijke reistijden. Deze implementatie verloopt veel moeizamer dan de implementatie voor een gewone VRP aangezien het verwisselen van twee of meer nodes en/of verbindingen een invloed kan hebben op de volledige route, hetgeen niet het geval is voor de gewone VRP. Zowel het benaderende wiskundig model als het heuristisch algoritme zijn reeds voorbereid op het gebruik van routering met meerdere depots.
In de heuristiek is het mogelijk om
meerdere data les van dezelfde dag uit te voeren - één data le per depot bijvoorbeeld en op die manier dus een oplossing te genereren voor meerdere depots.
Het zou echter
optimaler zijn dat het programma zelf een keuze maakt welke klanten bij welk depot horen om zo een e ciëntere routering te krijgen. Het zou voor bedrijven zeer aantrekkelijk zijn om een zogenaamd RT-TDVRPTW probleem te kunnen oplossen. Dit wil zeggen dat de le-informatie real-time wordt geüpdatet [56], in het beste geval zelfs met GPS informatie [57], om zo op een snelle manier de tijdsafhankelijke optimale route te kunnen berekenen.
Op die manier wordt in de GPS van
de vrachtwagen telkens het volgende deel van de route berekend wanneer de vrachtwagen vertrekt bij een bepaalde klant. Dit verzekert dus de optimale route op dat moment. De tijdsafhankelijke algoritmes voorgesteld in deze thesis houden nog geen rekening met het vervoer van verschillende producten.
In verdere studies zou de besproken methode
uitgebreid kunnen worden om op die manier een realistische routering te krijgen voor meerdere soorten producten. De huidige DSH metaheuristiek kan momenteel geen klanten bezoeken die een vraag hebben groter dan de truckcapaciteit. Een uitbreiding voor deze metaheuristiek kan dus zijn om ook klanten te bezoeken die een hogere vraag hebben dan de truckcapaciteit. Er zullen dan meerdere trucks dezelfde klant kunnen bezoeken, of dezelfde truck kan verschillende keren dezelfde klant bezoeken tijdens verschillende routes. Het zou interessant kunnen zijn om in plaats van hard time windows, zoals in de huidige implementatie in de DSH heuristiek, de optie toe te voegen om met soft time windows te 87
88
HOOFDSTUK 9.
FUTURE RESEARCH
werken. Het werd opgemerkt dat bij het uitvoeren van de bedrijfscases in geval van time windows soms geen oplossing kon gevonden worden gezien de klant niet bereikbaar was binnen zijn harde tijdsvenster. Hoewel de kern van het DSH algoritme e ciënt en snel kan opereren, is het vooral de dataverwerking vooraf, meer speci ek het uitlezen van de ledata en andere gegevens uit een database die het meeste overhead vragen tijdens het programma. Het is mogelijk om hier een e ciëntere manier van werken te implementeren. De initiële implementatie van het DSH algoritme is een seriële implementatie.
Dit wil
zeggen dat elk .dsh bestand na elkaar werd verwerkt. Een latere implementatie gebruikte de mogelijkheid om parallel .dsh bestanden te verwerken, maar deze versie was niet voorbereid op de extra lasten die dan op de databases werden losgelaten (in sommige gevallen kwam dit neer op meer dan 50 bestanden, die elk instaan voor hun eigen verbinding met de database). Een grote verbetering in performantie kan dus nog worden gerealiseerd met een degelijke implementatie van resource management.
Hoofdstuk 10
Conclusie In deze thesispaper wordt na een algemene inleiding en een grondige literatuurstudie, een exact en benaderend wiskundig model voorgesteld voor de routegeneratie van een TDVRPTW. Dit benaderend exact model wordt aan de hand van verschillende testcases onderzocht om zo tot oplossingen en routeringen te komen. Na het opstellen van een benaderend exact model wordt een krachtige metaheuristiek ontwikkeld die op een heel exibele manier in staat is om TDVRPTW problemen op te lossen. Deze metaheuristiek wordt het DSH algoritme genoemd, naar de ontwikkelaars P. De Smedt en G. Hompes. In deze metaheuristiek wordt naast tijdsafhankelijke reistijden en tijdsvensters ook rekening gehouden met de capaciteit van elke truck en de starttijd van de trucks. Het DSH algoritme staat toe om meerdere vrachtwagens per dag uit te sturen en meerdere routes per vrachtwagen te genereren om op die manier de volledige klantenset van die dag te bedienen. Door de algemene en exibele aanpak van de metaheuristiek wordt het mogelijk om zowel voor Palm als voor andere bedrijven zoals Recupel de kost te berekenen voor tijdsafhankelijke routeringen. Het bedrijf kan zijn speci eke kostenparameters meegeven zoals vaste kost van de trucks, servicetijd en kost per kilometer om op die manier een bedrijfspeci eke kostenberekening te bekomen. Het DSH algoritme en zijn Java implementatie geeft een krachtige tool voor bedrijven om op een e ciënte wijze tijdsafhankelijke routeringen te genereren. Op die manier kan men verantwoorde en realistische strategische beslissingen nemen met betrekking tot de kosten voor grootschalige routeringen, evenals de kostenberekening en routering van de dagelijks te bedienen klantenset.
In tegenstelling tot huidige systemen die geen rekening houden
met le waardoor er extra onverwachte lekosten bijkomen.
89
90
HOOFDSTUK 10.
CONCLUSIE
B¼lage A
Testcases in AMPL A.1
Testcase 2
Depot := 1000 Klanten := 1600, 1800, 1880, 2150, 2300, 2400, 2650, 2800, 3300, 6000 Vertrektijd := 360 (interval 24) AMPL
output
:=
(1000,3300,24)
(2650,2800,46)
(1800,1600,55)
(2800,1880,49)
(2300,2150,39) (6000,1000,62) (1880,1800,52) (3300,2400,29) (2400,2300,35) (1600,6000,58) (2150,2650,43)
Deze output wordt gebruikt om in Excel tabel A.1 te verkrijgen. Locatie
Reistijd
Aankomst
Vertrek
Interval 1
Interval 2
TT 1
TT 2
X
Y
360
24
25
46
48
4,35
50,85
3300
46,00
406,00
421,00
28
29
75
75
4,92
50,82
2400
75,00
496,00
511,00
34
35
40
39
5,13
51,21
2300
39,93
550,93
565,93
37
38
39
38
4,93
51,34
2150
38,27
604,20
619,20
41
42
12
14
4,49
51,19
2650
12,56
631,77
646,77
43
44
19
19
4,43
51,15
2800
19,00
665,77
680,77
45
46
29
30
4,46
51,04
1880
29,38
710,15
725,15
48
49
25
26
4,35
51,00
1800
25,34
750,49
765,49
51
52
29
30
4,44
50,93
1600
29,03
794,53
809,53
53
54
41
41
4,25
50,79
6000
41
850,53
865,53
57
58
59
60
4,45
50,42
1000
59,70
925,23
4,35
50,85
1000
Tabel A.1: Berekening exacte reistijden testcase 2
Met de volgende kostfactoren kan dan de totaalkost voor deze route berekend worden in tabel A.2 De routering is als in guur A.1.
A.2
Testcase 3
Deze output wordt gebruikt om in Excel tabel A.3 te verkrijgen. 91
92
BLAGE A. TESTCASES IN AMPL
Trucks
1
Vaste kost
100
Reiskost
1
Klanten
10
Servicetijd
15
Servicekost
1
KOST
665,23
Tabel A.2: Kostbepaling testcase 2: AMPL
51,4
Breedtegraad
51,2 51 50,8
Route
50,6
Depot
50,4 50,2
4
4,2
4,4
4,6
4,8
5
5,2
Lengtegraad
Figuur A.1: Routering testcase 2: AMPL
Depot := 1000 Klanten := 1150, 1200, 9300, 9340, 9400, 9450, 9550, 9600, 9850, 9900 Vertrektijd := 360 (interval 24) AMPL
output
:=
(1000,9300,24)
(9450,9400,53)
(9900,9850,37)
(1200,1150,61)
(9400,1200,56) (9550,9450,50) (9340,9900,31) (1150,1000,63) (9600,9550,46) (9850,9600,41) (9300,9340,28)
Locatie
Reistijd
Aankomst
Vertrek
Interval 1
Interval 2
TT 1
TT 2
X
Y
360
24
25
36
38
4,35
50,85
9300
36,00
396,00
411,00
27
28
21
26
4,04
50,95
9340
23,00
434,00
449,00
29
30
61
61
3,95
50,97
9900
61,00
510,00
525,00
35
36
37
34
3,57
51,19
9850
37,00
562,00
577,00
38
39
49
47
3,56
51,06
9600
48,07
625,07
640,07
42
43
42
43
3,60
50,76
9550
42,67
682,74
697,74
46
47
25
24
3,90
50,87
9450
24,48
722,22
737,22
49
50
24
24
4,00
50,88
9400
24,00
761,22
776,22
51
52
50
50
4,02
50,79
1200
50,00
826,22
841,22
56
57
7
8
4,44
50,85
1150
7,0815
848,30
863,30
57
58
26
27
4,44
50,83
1000
26,55
889,86
4,35
50,85
1000
Tabel A.3: Berekening exacte reistijden testcase 3
A.3.
TESTCASE 4
93
Met de volgende kostfactoren kan dan de totaalkost voor deze route berekend worden in tabel A.4 Trucks
1
Vaste kost
100
Reiskost
1
Klanten
10
Servicetijd
15
Servicekost
1
KOST
629,86
Tabel A.4: Kostbepaling testcase 3: AMPL
De routering is als in guur A.2.
Breedtegraad
51,40 51,20 51,00
Route
Depot
50,80 50,60
3
3,5
4
4,5
5
Lengtegraad
Figuur A.2: Routering testcase 3: AMPL
A.3
Testcase 4
Depot := 1000 Klanten := 4600, 4700, 4900, 5000, 53000, 5500, 6000, 6200, 6500, 6600 Vertrektijd := 360 (interval 24) AMPL
output
:=
(1000,5000,24)
(4900,6600,47)
(5500,6500,59)
(6500,6200,64)
(4600,4700,37) (5000,5300,29) (6000,1000,72) (6600,5500,53) (4700,4900,42) (5300,4600,32) (6200,6000,69)
Deze output wordt gebruikt om in Excel tabel A.5 te verkrijgen. Met de volgende kostfactoren kan dan de totaalkost voor deze route berekend worden in tabel A.6 De routering is als in guur A.3.
A.4
Testcase 5
Deze output wordt gebruikt om in Excel tabel A.7 te verkrijgen. Met de volgende kostfactoren kan dan de totaalkost voor deze route berekend worden in tabel A.8 De routering is als in guur A.4.
94
BLAGE A. TESTCASES IN AMPL
Locatie
Reistijd
Aankomst
1000
Vertrek
Interval 1
Interval 2
TT 1
TT 2
X
Y
360
24
25
58
61
4,35
50,85
5000
58,00
418,00
433,00
28
29
30
29
4,85
50,46
5300
29,13
462,13
477,13
31
32
54
54
5,06
50,49
4600
54,00
531,13
546,13
36
37
48
46
5,70
50,74
4700
47,18
593,32
608,32
40
41
54
49
5,70
50,74
4900
51,23
659,54
674,54
44
45
69
69
5,87
50,48
6600
69,00
743,54
758,54
50
51
67
67
5,76
50,03
5500
67,00
825,54
840,54
56
57
57
58
4,94
50,24
6500
57,04
897,58
912,58
60
61
45
45
4,26
50,23
6200
45,00
957,58
972,58
64
65
21
19
4,52
50,39
6000
19,3227
991,90
1006,90
67
68
53
53
4,45
50,42
1000
53,00
1059,90
4,35
50,85
Tabel A.5: Berekening exacte reistijden testcase 4 Trucks
1
Vaste kost
100
Reiskost
1
Klanten
10
Servicetijd
15
Servicekost
1
KOST
799,90
Tabel A.6: Kostbepaling testcase 4: AMPL 50,9 50,8 50,7 50,6 50,5 50,4 50,3 50,2 50,1 50,0 49,9
Route Depot
4
4,5
5
5,5
6
Figuur A.3: Routering testcase 4: AMPL Depot := 1000 Klanten := 7000, 7100, 7300, 7500, 7600, 7700, 7800, 7900, 8000, 8300 Vertrektijd := 360 (interval 24) AMPL
output
:=
(1000,8300,24)
(7300,7000,57)
(7700,7500,42)
(8000,7700,36)
(7000,7100,60) (7500,7900,45) (7800,7600,51) (8300,8000,32) (7100,1000,63) (7600,7300,54) (7900,7800,48); 51,40 Breedtegraad
51,20
51,00 50,80
Route
50,60
Depot
50,40 50,20
3,00
3,50
4,00
4,50
Lengtegraad
Figuur A.4: Routering testcase 5: AMPL
A.4.
TESTCASE 5
Locatie
95
Reistijd
Aankomst
Vertrek
Interval 1
Interval 2
TT 1
TT 2
X
Y
360
24
25
91
92
4,35
50,85
8300
91,00
451,00
466,00
31
32
28
31
3,33
51,34
8000
28,20
494,20
509,20
33
34
58
55
3,21
51,24
7700
55,16
564,36
579,36
38
39
31
32
3,23
50,74
7500
31,62
610,98
625,98
41
42
24
26
3,38
50,59
7900
25,46
651,45
666,45
44
45
19
18
3,62
50,61
7800
18,57
685,02
700,02
46
47
29
30
3,78
50,64
7600
29,67
729,69
744,69
49
50
27
26
3,59
50,52
7300
26,35
771,04
786,04
52
53
18
19
3,79
50,43
7000
18,40
804,44
819,44
54
55
26
25
3,96
50,46
7100
25,3704
844,81
859,81
57
58
65
66
4,17
50,46
1000
65,32
925,13
4,35
50,85
1000
Tabel A.7: Berekening exacte reistijden testcase 5
Trucks
1
Vaste kost
100
Reiskost
1
Klanten
10
Servicetijd
15
Servicekost
1
KOST
665,13
Tabel A.8: Kostbepaling testcase 5: AMPL
96
BLAGE A. TESTCASES IN AMPL
B¼lage B
Testcases met DSH B.1
DSH met vaste starttijden
B.1.1 Testcase 2 Depot := 1000 Klanten := 1600, 1800, 1880, 2150, 2300, 2400, 2650, 2800, 3300, 6000 Vertrektijd := 360 (interval 24) Algemene vorm Java output := klantID ; Postcode ; aankomsttijd ; truckload Java output := D;1000;360;0 7;1880;389;30 9;2800;431;50 3;2650;466;60 8;2150;500;70 1;2300;556;80 2;2400;609;85 10;3300;692;95 6;1800;748;100 5;1600;793;110 4;6000;849;130 D;1000;923;0
Deze heuristiek werd uitgevoerd op 46.438 milliseconden (ongeveer 46 seconden). Met de volgende kostenparameters bepaalt de Java code de beste route en de totaalkost in tabel B.1 De resulterende route in guur B.1
B.1.2 Testcase 3 Deze heuristiek werd uitgevoerd op 46.031 milliseconden (ongeveer 46 seconden). Met de volgende kostenparameters bepaalt de Java code de beste route en de totaalkost in tabel B.2 De resulterende route in guur B.2 97
98
BLAGE B. TESTCASES MET DSH
Trucks
1
Vaste kost
100
Reiskost
1
Klanten
10
Servicetijd
15
Servicekost
1
Iteraties per GRASP alpha
1000
Alpha min
0
Alpha max
1
Alpha staplengte
0,01
Kost
663,00
Tabel B.1: Kostbepaling testcase 2: vaste starttijden DSH 51,4 Breedtegraad
51,2
51 50,8
Route
50,6
Depot
50,4 50,2
4
4,2
4,4
4,6
4,8
5
5,2
Lengtegraad
Figuur B.1: Routering testcase 2: vaste starttijden DSH Depot := 1000 Klanten := 1150, 1200, 9300, 9340, 9400, 9450, 9550, 9600, 9850, 9900 Vertrektijd := 360 (interval 24) Algemene vorm Java output := klantID ; Postcode ; aankomsttijd ; truckload Java output := D;1000;360;0 10;1150;378;1 9;1200;400;2 1;9400;473;3 3;9450;512;4 4;9550;548;5 2;9600;606;6 6;9900;683;7 5;9850;733;8 7;9340;788;9 8;9300;826;10 D;1000;884;0 51,25 51,2 51,15 51,1 51,05 51 50,95 50,9 50,85 50,8 50,75 50,7
Route Depot
3
3,5
4
4,5
5
Figuur B.2: Routering testcase 3: vaste starttijden DSH
B.1.
DSH MET VASTE STARTTIJDEN
99
Trucks
1
Vaste kost
100
Reiskost
1
Klanten
10
Servicetijd
15
Servicekost
1
Iteraties per GRASP alpha
1000
Alpha min
0
Alpha max
1
Alpha staplengte
0,01
Kost
624,00
Tabel B.2: Kostbepaling testcase 3: vaste starttijden DSH
B.1.3 Testcase 4 Depot := 1000 Klanten := 4600, 4700, 4900, 5000, 53000, 5500, 6000, 6200, 6500, 6600 Vertrektijd := 360 (interval 24) Algemene vorm Java output := klantID ; Postcode ; aankomsttijd ; truckload Java output := D;1000;360;0 4;5000;418;1 5;5300;463;2 1;4600;532;3 2;4700;595;4 3;4900;664;5 10;6600;748;6 6;5500;830;7 9;6500;902;8 8;6200;962;9 7;6000;996;10 D;1000;1064;0
Deze heuristiek werd uitgevoerd op 46.031 milliseconden (ongeveer 46 seconden). Met de volgende kostenparameters bepaalt de Java code de beste route en de totaalkost in tabel B.3 De resulterende route in guur B.3
B.1.4 Testcase 5 Deze heuristiek werd uitgevoerd op 45.719 milliseconden (ongeveer 45 seconden). Met de volgende kostenparameters bepaalt de Java code de beste route en de totaalkost in tabel B.4 De resulterende route in guur B.4
100
BLAGE B. TESTCASES MET DSH
Trucks
1
Vaste kost
100
Reiskost
1
Klanten
10
Servicetijd
15
Servicekost
1
Iteraties per GRASP alpha
1000
Alpha min
0
Alpha max
1
Alpha staplengte
0,01
Kost
804,00
Tabel B.3: Kostbepaling testcase 4: vaste starttijden DSH 50,9 50,8 50,7 50,6 50,5 50,4 50,3 50,2 50,1 50,0 49,9
Route Depot
4
4,5
5
5,5
6
Figuur B.3: Routering testcase 4: vaste starttijden DSH Depot := 1000 Klanten := 7000, 7100, 7300, 7500, 7600, 7700, 7800, 7900, 8000, 8300 Vertrektijd := 360 (interval 24) Algemene vorm Java output := klantID ; Postcode ; aankomsttijd ; truckload Java output := D;1000;360;0 2;7100;414;1 1;7000;460;2 3;7300;496;3 8;7900;546;4 7;7800;580;5 5;7600;622;6 4;7500;662;7 6;7700;705;8 9;8000;779;9 10;8300;823;10 D;1000;934;0 51,40 Breedtegraad
51,20
51,00 50,80
Route
50,60
Depot
50,40 50,20
3,00
3,50
4,00
4,50
Lengtegraad
Figuur B.4: Routering testcase 5: vaste starttijden DSH
B.1.
DSH MET VASTE STARTTIJDEN
101
Trucks
1
Vaste kost
100
Reiskost
1
Klanten
10
Servicetijd
15
Servicekost
1
Iteraties per GRASP alpha
1000
Alpha min
0
Alpha max
1
Alpha staplengte
0,01
Kost
674,00
Tabel B.4: Kostbepaling testcase 5: vaste starttijden DSH
102
BLAGE B. TESTCASES MET DSH
B¼lage C
DSH met variabele starttijden C.1
Testcase 2
Depot := 1000 Klanten := 1600, 1800, 1880, 2150, 2300, 2400, 2650, 2800, 3300, 6000 Vertrektijd := Te bepalen door de heuristiek Algemene vorm Java output := klantID ; Postcode ; aankomsttijd ; truckload Java output := D;1000;465;0 7;1880;499;30 9;2800;547;50 3;2650;581;60 8;2150;613;70 1;2300;662;80 2;2400;713;85 10;3300;797;95 6;1800;853;100 5;1600;899;110 4;6000;955;130 D;1000;1024;0
Deze heuristiek werd uitgevoerd op 608.641 milliseconden (ongeveer 10 minuten). Met de volgende kostenparameters bepaalt de Java code de beste route en de totaalkost in tabel C.1. De resulterende route in guur C.1.
C.2
Testcase 3
Deze heuristiek werd uitgevoerd op 604.968 milliseconden (ongeveer 10 minuten). Met de volgende kostenparameters bepaalt de Java code de beste route en de totaalkost: C.2. De resulterende route in guur C.2. 103
104
BLAGE C. DSH MET VARIABELE STARTTIJDEN
Trucks
1
Vaste kost
100
Reiskost
1
Klanten
10
Servicetijd
15
Servicekost
1
Iteraties per GRASP alpha
1000
Alpha min
0
Alpha max
1
Alpha staplengte
0,01
Kost
659,00
Tabel C.1: Kostbepaling testcase 2: variabele starttijden DSH 051 Breedtegraad
051 051 051
Route
051
Depot
050 050 004
005
005
006
Lengtegraad
Figuur C.1: Routering testcase 2: variabele starttijd DSH Depot := 1000 Klanten := 1150, 1200, 9300, 9340, 9400, 9450, 9550, 9600, 9850, 9900 Vertrektijd := Te bepalen door de heuristiek Algemene vorm Java output := klantID ; Postcode ; aankomsttijd ; truckload Java output := D;1000;450;0 10;1150;472;1 9;1200;495;2 8;9300;551;3 7;9340;588;4 5;9850;643;5 6;9900;687;6 2;9600;770;7 4;9550;829;8 1;9400;876;9 3;9450;913;10 D;1000;971;0
051 051 051 051
Route
051
Depot
051 051 003
004
004
005
005
Figuur C.2: Routering testcase 3 variabele starttijd DSH
C.3.
TESTCASE 4
105
Trucks
1
Vaste kost
100
Reiskost
1
Klanten
10
Servicetijd
15
Servicekost
1
Iteraties per GRASP alpha
1000
Alpha min
0
Alpha max
1
Alpha staplengte
0,01
Kost
621,00
Tabel C.2: Kostbepaling testcase 3: variabele starttijden DSH
C.3
Testcase 4
Depot := 1000 Klanten := 4600, 4700, 4900, 5000, 53000, 5500, 6000, 6200, 6500, 6600 Vertrektijd := Te bepalen door de heuristiek Algemene vorm Java output := klantID ; Postcode ; aankomsttijd ; truckload Java output := D;1000;375;0 4;5000;436;1 5;5300;473;2 1;4600;542;3 2;4700;603;4 3;4900;667;5 10;6600;751;6 6;5500;833;7 9;6500;905;8 8;6200;965;9 7;6000;999;10 D;1000;1067;0
Deze heuristiek werd uitgevoerd op 612.218 milliseconden (ongeveer 10 minuten). Met de volgende kostenparameters bepaalt de Java code de beste route en de totaalkost in tabel C.3. De resulterende route in guur C.3.
C.4
Testcase 5
Deze heuristiek werd uitgevoerd op 612.218 milliseconden (ongeveer 10 minuten). Met de volgende kostenparameters bepaalt de Java code de beste route en de totaalkost in tabel C.4. De resulterende route in guur C.4.
106
BLAGE C. DSH MET VARIABELE STARTTIJDEN
Trucks
1
Vaste kost
100
Reiskost
1
Klanten
10
Servicetijd
15
Servicekost
1
Iteraties per GRASP alpha
1000
Alpha min
0
Alpha max
1
Alpha staplengte
0,01
Kost
792,00
Tabel C.3: Kostbepaling testcase 4: variabele starttijden DSH 051 051 051 050
Route
050
Depot
050 050 004
005
005
006
006
Figuur C.3: Routering testcase 4 variabele starttijd DSH Depot := 1000 Klanten := 7000, 7100, 7300, 7500, 7600, 7700, 7800, 7900, 8000, 8300 Vertrektijd := Te bepalen door de heuristiek Algemene vorm Java output := klantID ; Postcode ; aankomsttijd ; truckload Java output := D;1000;435;0 2;7100;494;1 1;7000;541;2 3;7300;576;3 5;7600;614;4 8;7900;646;5 7;7800;680;6 4;7500;731;7 6;7700;772;8 9;8000;845;9 10;8300;887;10 D;1000;992;0
051 Breedtegraad
051 051 051
Route
051
Depot
050 050 003
004
004
005
Lengtegraad Figuur C.4: Routering testcase 5 variabele starttijd DSH
C.4.
TESTCASE 5
107
Trucks
1
Vaste kost
100
Reiskost
1
Klanten
10
Servicetijd
15
Servicekost
1
Iteraties per GRASP alpha
1000
Alpha min
0
Alpha max
1
Alpha staplengte
0,01
Kost
657,00
Tabel C.4: Kostbepaling testcase 5: variabele starttijden DSH
108
BLAGE C. DSH MET VARIABELE STARTTIJDEN
B¼lage D
Invloed van de starttijd op DSH D.1
Testcase 2
Alfa = 0,7
Alfa = 0,8
680
680 Kost
720
Kost
720
640
640
600
600 360
405
450
495
540
360
405
Starttijd
450
495
540
Starttijd
Alfa = 0,9
Alfa = 1 720
720
Kost
Kost
680 360
640 600
0 360
405
450
495
540
Starttijd
360
420
480
540
Starttijd
Figuur D.1: Invloed van de starttijd op testcase 2
Het is duidelijk merkbaar dat een latere starttijd over het algemeen een mindere totaalkost met zich meebrengt. Bij alfa = 1 merken we een val naar een nulkost vanaf t=480. De reden hiervoor is dat er vanaf t=480 niet steeds alle klanten worden bediend. Indien dit niet mogelijk is achten we de route als zijnde nuttig en vervalt de kost naar 0.
D.2
Overige testcases
109
110
BLAGE D. INVLOED VAN DE STARTTIJD OP DSH
Alpha = 0,7
Alpha = 0,8 660 Kost
Kost
660
620
580
620
580 360
420
480
540
360
420
Starttijd
Alpha = 0,9
540
Alpha = 1 660 Kost
660 Kost
480 Starttijd
620
580
620
580 360
420
480
540
360
Starttijd
420
480
540
Starttijd
Figuur D.2: Invloed van de starttijd op testcase 3
Alpha = 0,8
880
880
860
860
Kost
Kost
Alpha = 0,7
840 820
840 820
360
420
480
540
360
Starttijd
480
540
Starttijd
Alpha = 0,9
Alpha = 1
880
880
860
860
Kost
Kost
420
840 820
840 820
360
420
480 Starttijd
540
360
420
480
Starttijd
Figuur D.3: Invloed van de starttijd op testcase 4
540
OVERIGE TESTCASES
111
Alpha = 0,8
735
735
690
690
Kost
Kost
Alpha = 0,7
645
645 600
600 360
420
480
360
540
420
Alpha = 0,9 690
690
Kost
735
645 600 420
480 Starttijd
540
480
540
Alpha = 1
735
360
480 Starttijd
Starttijd
Kost
D.2.
540
645 600 360
420 Starttijd
Figuur D.4: Invloed van de starttijd op testcase 5
112
BLAGE D. INVLOED VAN DE STARTTIJD OP DSH
Bibliogra e [1] M. I. Hertveldt B, Hoornaert B,
referentiescenario.
Langetermijnvooruitzichen voor transport in België:
Federaal Planbureau, Feb. 2009.
[2] Palm Breweries. [Online]. Available: http://palm.be/ [3] Möbius, Möbius website. [Online]. Available: http://www.mobius.eu [4] Y. I. Maerivoet S.,
Analyse van de verkeerscongestie in België,
07th ed.
Federale
Overheidsdienst Mobiliteit en Vervoer, 2008. [5] Handelsreizigersprobleem.
[Online].
Available:
http://nl.wikipedia.org/wiki/
Handelsreizigersprobleem [6] J. Larsen,
Parallelization of the vehicle routing problem with time windows,
Ph.D. dissertation,
Technical University of Denmark,
1999. [Online]. Available:
http://www2.imm.dtu.dk/documents/ftp/phdliste/phd62_99.pdf [7] Solution
of
a
15.112-city
Traveling
salesman
problem.
[Online].
Available:
http://www.tsp.gatech.edu/d15sol/ [8] Traveling Salesman Problem. [Online]. Available: http://www.tsp.gatech.edu/ [9] D. Applegate, R. Bixby, V. Chavat, and W. Cook, TSP cuts which do not conform to the template paradigm. [10] B. Joseph and J. Kruskal, On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem, 1953. [11] S. Lin, Computer Solutions of the Traveling Salesman Problem, 1965. [12] S. Lin and W. Kernigham, An Eective Heuristic Algorithm for the Traveling Salesman Problem, 1973. [13] M. Dorigo and L. M. Gambardella, Ant Colony System - A Cooperative Learning Approach to the Traveling Salesman Problem, 1997. [14] G. Dantzig and J. Ramser, The Truck Dispatching Problem, vol. 6, no. 1, pp. 8091, 1959. 113
Management Science,
114
BIBLIOGRAFIE
[15] G. Laporte, The Vehicle Routing Problem : An overview of exact and approximate
European Journal Of Operational Research,
algorithms, [16] T.
Ralphs,
L.
Kopman,
and
W.
Mathematical,
routing problem,
Pulleyblank,
vol. 59, pp. 345358, 1992.
On
the
capacitated
vehicle
no. 94, pp. 343359, 2003. [Online]. Available:
http://www.springerlink.com/index/1CUAN1JHFL6NRDV3.pdf [17] S. Coene, A. Arnout, and F. Spieksma, The periodic Vehicle Routing Problem: a case study, 2008.
Discrete
[18] M. Dror, G. Laporte, and P. Trudeau, Vehicle routing with split deliveries,
Applied Mathematics,
vol. 50, no. 3, pp. 239254, 1992.
The Vehicle Routing Problem and Local Search Metaheuristics.
[19] C. Hjorring,
Depart-
ment of Engineering Sciences, The University of Auckland, 1995. [20] J. F. Bard, for
the
L. Huang,
VRP
with
M. Dror,
satellite
and P. Jaillet,
facilities,
A branch and cut algorithm
IIE Transactions,
821834, Sep. 1998. [Online]. Available:
vol.
30,
no.
9,
pp.
http://www.tandfonline.com/doi/abs/10.
1080/07408179808966528 [21] S.-C.
Liu
and
W.-T.
Lee,
A
problem with time windows,
heuristic
method
for
the
inventory
Expert Systems with Applications,
pp. 13 22313 231, Sep. 2011. [Online]. Available:
routing
vol. 38, no. 10,
http://linkinghub.elsevier.com/
retrieve/pii/S0957417411006658 [22] O. Braysy and M. Gendreau, Part
I:
Science,
Route vol.
Vehicle Routing Problem with Time Windows,
Construction
39,
no.
1,
and
pp.
Local
104118,
Search
Feb.
Transportation
Algorithms,
2005.
[Online].
Available:
http:
//transci.journal.informs.org/cgi/doi/10.1287/trsc.1030.0056 [23] A. Haghani and S. Jung, A dynamic vehicle routing problem with time-dependent travel
times,
Computers & Operations Research,
29592986, Nov. 2005. [Online]. Available:
vol.
32,
no.
11,
pp.
http://linkinghub.elsevier.com/retrieve/
pii/S0305054804000887 [24] a.L.
Kok,
travel
E.
times:
Research,
vol.
Hans,
and
The
impact
39,
no.
5,
J.
Schutten,
Vehicle
of
congestion
pp.
910918,
routing
2012.
time-dependent
Computers & Operations
avoidance, May
under
[Online].
Available:
http:
//linkinghub.elsevier.com/retrieve/pii/S0305054811001614 [25] L. Kok, The VRP with time-dependent travel times. [26] J.-Y.
Potvin,
Y.
Xu,
dynamic travel times,
and
I.
Benyahia,
routing
Computers & Operations Research,
11291137, Apr. 2006. [Online]. Available: pii/S0305054804002291
Vehicle
and
scheduling
vol. 33,
no. 4,
with pp.
http://linkinghub.elsevier.com/retrieve/
BIBLIOGRAFIE
115
[27] N. Christo des, A. Mingozzi, and P. Toth, State-space relaxation procedures for the
Networks,
computation of bounds to routing problems,
vol. 11, no. 2, pp. 145164,
Jan. 1981. [Online]. Available: http://doi.wiley.com/10.1002/net.3230110207 [28] G. Laporte, Y. Nobert, and M. Desrochers, Optimal Routing under Capacity and Distance Restrictions,
Operations Research,
vol. 33, no. 5, pp. 10501073, Sep. 1985.
[Online]. Available: http://or.journal.informs.org/cgi/doi/10.1287/opre.33.5.1050 [29] U. Blasum and W. Hochstattler, Application of the Branch and Cut Method to the Vehicle Routing Problem, 2002. [30] K. Wenger, Generic Cut Generation Methods for Routing Problems. Phd Thesis, 2003. [31] R. Kulkarni and P. Bhave, Integer programming formulations of vehicle routing problems,
European Journal of Operational Research,
5867, Apr. 1985. [Online]. Available:
vol.
20,
no.
1,
pp.
http://linkinghub.elsevier.com/retrieve/pii/
037722178590284X [32] G. Clarke and J. W. Wright, Scheduling of Vehicles from a Central Depot to a
Operations Research,
Number of Delivery Points,
vol. 12, no. 4, pp. 568581, 1964.
[Online]. Available: http://www.jstor.org/stable/167703 [33] B. Gillett and L. Miller, A heuristic algorithm for the vehicle-dispatch problem,
Operations research,
vol.
22,
no.
2,
pp.
340349,
1974.
[Online].
Available:
http://www.jstor.org/stable/10.2307/169591 [34] G. Laporte and H. Etudes, Tabu Search Heuristics for the Vehicle Routing Problem, 2002. [35] R. D. Franceschi, M. Fischetti, and P. Toth, A new ILP-based re nement heuristic for Vehicle Routing Problems, 471499,
Mathematical Programming,
Nov. 2005. [Online]. Available:
vol. 105, no. 2-3, pp.
http://www.springerlink.com/index/10.
1007/s10107-005-0662-8 [36] C. Groër, B. Golden, and E. Wasil, A library of local search heuristics for the vehicle routing problem,
Mathematical Programming,
[37] F. Glover, Tabu SearchPart I,
no. 2, pp. 79101, 2010.
INFORMS Journal on Computing,
vol. 1, no. 3,
pp. 190206, Jan. 1989. [Online]. Available: http://joc.journal.informs.org/cgi/doi/ 10.1287/ijoc.1.3.190 [38] , Tabu SearchPart II,
INFORMS Journal on Computing,
vol. 2, no. 1, pp.
432, Jan. 1990. [Online]. Available: http://joc.journal.informs.org/cgi/doi/10.1287/ ijoc.2.1.4 [39] O. Braysy and M. Gendreau, Part
I:
Route
Construction
Vehicle Routing Problem with Time Windows, and
Local
Search
Algorithms,
Transportation
116
BIBLIOGRAFIE
Science,
vol.
39,
no.
1,
pp.
104118,
Feb.
2005.
[Online].
Available:
http:
//transci.journal.informs.org/cgi/doi/10.1287/trsc.1030.0056 [40] ,
Vehicle Routing Problem with Time Windows,
Transportation Science,
Part II: Metaheuristics,
vol. 39, no. 1, pp. 119139, Feb. 2005. [Online]. Available:
http://transci.journal.informs.org/cgi/doi/10.1287/trsc.1030.0057 [41] J.
H.
Holland,
Adaptation
in
University of Michigan Press,
natural 1975.
and
arti cial
[Online].
systems.
Available:
Ann Arbor MI
http://www.journals.
uchicago.edu/doi/abs/10.1086/318962 [42] A. V. Donati, R. Montemanni, N. Casagrande, A. E. Rizzoli, and L. M. Gambardella, Time dependent vehicle routing problem with a multi ant colony system,
Journal of Operational Research,
European
vol. 185, no. 3, pp. 11741191, Mar. 2008. [Online].
Available: http://linkinghub.elsevier.com/retrieve/pii/S0377221706006345 [43] G. Laporte, What you should know about the vehicle routing problem.
search Logistics,
Naval Re-
vol. 54, pp. 811819, 2007.
[44] B. W. Kerninghan and S. Lin, An eective heuristic algorithm for the travelingsalesman problem.
Operations research,
no. 21, pp. 498516, 1973.
[45] T. A. Feo and M. G. C. Resende, Greedy Randomized Adaptive Search Procedures,
Journal of Global Optimization,
vol. 6, no. 2, pp. 109133, Mar. 1995. [Online].
Available: http://www.springerlink.com/index/10.1007/BF01096763 [46] N. Balakrishnan, Simple Heuristics for the Vehicle Routeing Problem with Soft Time Windows,
Journal of the Operational Research Society,
vol. 44, no. 3, pp. 279287,
1993. [47] C. Groër, B. Golden, and E. Wasil, A library of local search heuristics for the vehicle routing problem,
Mathematical Programming Computation,
vol. 2, no. 2, pp.
79101, Apr. 2010. [Online]. Available: http://www.springerlink.com/index/10.1007/ s12532-010-0013-5 [48] H. Lau, Vehicle routing problem with time windows and a limited number of vehicles,
European Journal of Operational Research,
vol. 148, no. 3, pp. 559569, Aug. 2003.
[Online]. Available: http://linkinghub.elsevier.com/retrieve/pii/S0377221702003636 [49] S. Ichoua, M. Gendreau, and J.-Y. Potvin, Vehicle dispatching with time-dependent travel times,
European Journal of Operational Research,
vol. 144,
no. 2,
pp.
379396, Jan. 2003. [Online]. Available: http://linkinghub.elsevier.com/retrieve/pii/ S0377221702001479 [50] C. Malandraki and M. Dasking, Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms, 1992.
Transportation Science,
vol. 26, no. 3,
BIBLIOGRAFIE
[51] M.
A.
117
Figliozzi,
Planning
approximations
to
the
routing problems with time window constraints,
B: Methodological,
vol. 43,
no. 4,
pp. 438447,
average
length
of
vehicle
Transportation Research Part May 2009. [Online]. Available:
http://linkinghub.elsevier.com/retrieve/pii/S0191261508000969 [52] K. Lieckens and N. Vandaele, Reverse logistics network design with stochastic lead times,
Computers & Operations Research,
vol. 34, no. 2, pp. 395416, Feb. 2007.
[Online]. Available: http://linkinghub.elsevier.com/retrieve/pii/S0305054805001012 [53] R. de Camargo, G. Miranda Jr., R. Ferreira, and H. Luna, Multiple allocation
Computers & Operations
hub-and-spoke network design under hub congestion,
Research,
vol.
36,
no.
12,
pp.
30973106,
Dec.
2009.
[Online].
Available:
http://linkinghub.elsevier.com/retrieve/pii/S0305054808001998 [54] M.
Andres
windows:
Figliozzi, Benchmark
vol.
time
dependent
problems,
an
vehicle
e cient
routing
solution
problem
algorithm,
with
and
time
solution
Transportation Research Part E: Logistics and Transportation
characteristics,
Review,
The
48,
no.
3,
pp.
616636,
May
2012.
[Online].
Available:
http:
//linkinghub.elsevier.com/retrieve/pii/S1366554511001426 [55] M. Waller, E. M. Johnson, and T. Davis, Vendor Managed Inventory in the Retail Supply Chain,
Journal of Business Logistics,
vol. 20, pp. 183203, 1999.
[56] S. M. G. Bertazzi L, Savelsbergh M, Inventory Routing,
blem,
The Vehicle Routing Pro-
p. 24, 2008.
[57] AMPL Modeling Language for Mathematical Programming. [Online]. Available: http://www.ampl.com/ [58] IBM - Solving optimization problems - IBM ILOG CPLEX Optimization Studio -
Software,
May
2012.
[Online].
Available:
http://www-01.ibm.com/software/
integration/optimization/cplex-optimization-studio/ [59] K. Sung, M. G. H. Bell, and S. Park, Shortest paths in a network with time-dependent oow speeds,
European Journal Of Operational Research,
vol. 121, pp. 3239, 2000.
[60] E. W. Dijkstra, A note on two problems in connexion with graphs,
Mathematik,
vol.
1,
no.
1,
pp.
269271,
Dec.
1959.
[Online].
Numerische Available:
http://www.springerlink.com/index/10.1007/BF01386390 [61] Microsoft, Acces 2010 Speci cations. [Online]. Available:
http://o ce.microsoft.
com/en-us/access-help/access-2010-speci cations-HA010341462.aspx [62] How MySQL Uses Indexes. [Online]. Available: http://dev.mysql.com/doc/refman/ 5.0/en/mysql-indexes.html [63] The Computer Language Benchmark Game. [Online]. Available: http://shootout. alioth.debian.org/
118
BIBLIOGRAFIE
[64] NetBeans IDE 7.1.2. [Online]. Available: http://netbeans.org/ [65] OpenStreetMap. [Online]. Available: http://www.openstreetmap.org/ [66] Cloud Made - Routing.
[Online]. Available:
http://developers.cloudmade.com/
projects/show/routing-http-api [67] J. Denys, Optimalisatie van de distributie- en transportplanning bij PALM Breweries, Ph.D. dissertation, Universiteit Gent.
L¼st van guren 3.1
Een typische oplossing van een TSP [6] . . . . . . . . . . . . . . . . . . . . .
6
3.2
3-opt move
7
3.3
Illustratie van een Vehicle Routing Probleem
. . . . . . . . . . . . . . . . .
7
3.4
Schema van het savings concept . . . . . . . . . . . . . . . . . . . . . . . . .
12
3.5
Constructie van mogelijke routes met behulp van een sweep.
. . . . . . . .
13
3.6
Verloop van een sweep heuristiek (richting tegen de klok in)[36]. . . . . . . .
13
3.7
Illustratie van het ant colonoy system
. . . . . . . . . . . . . . . . . . . . .
15
3.8
Lokale zoekoperatoren
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
3.9
Minder courante lokale zoekoperatoren . . . . . . . . . . . . . . . . . . . . .
18
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.10 Pseudocode GRASP
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
3.11 Illustratie VRPH met Clarck & Wright . . . . . . . . . . . . . . . . . . . . .
19
3.12 Illustratie VRPH met het Sweep algoritme . . . . . . . . . . . . . . . . . . .
20
3.13 Vergelijking tussen een FIFO en niet-FIFO systeem . . . . . . . . . . . . . .
23
5.1
Intervalmodel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
5.2
Route testcase 1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
6.1
Logo DSH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54
6.2
Databasestructuur
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
6.3
Stroomdiagram keuze GRASP . . . . . . . . . . . . . . . . . . . . . . . . . .
64
6.4
DSH GUI
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
66
6.5
Verloop DSH in Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
6.6
Intern verloop van DSH
75
6.7
Routering testcase 1:heuristiek
. . . . . . . . . . . . . . . . . . . . . . . . .
76
7.1
Resultaten GRASP 1-2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
78
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
119
120
LST VAN FIGUREN
7.2
Stroomdiagram keuze GRASP 1-2-3-4
. . . . . . . . . . . . . . . . . . . . .
79
7.3
Resultaten GRASP 1-2-3-4
. . . . . . . . . . . . . . . . . . . . . . . . . . .
80
7.4
Invloed van starttijden trucks op de totale kost. . . . . . . . . . . . . . . . .
80
7.5
Invloed van de servicetijd op de kost voor testcase 5
. . . . . . . . . . . . .
81
8.1
Route voor 30 dagen ter illustratie van de routeringsoftware. . . . . . . . . .
85
A.1
Routering testcase 2: AMPL
. . . . . . . . . . . . . . . . . . . . . . . . . .
92
A.2
Routering testcase 3: AMPL
. . . . . . . . . . . . . . . . . . . . . . . . . .
93
A.3
Routering testcase 4: AMPL
. . . . . . . . . . . . . . . . . . . . . . . . . .
94
A.4
Routering testcase 5: AMPL
. . . . . . . . . . . . . . . . . . . . . . . . . .
94
B.1
Routering testcase 2: vaste starttijden DSH
. . . . . . . . . . . . . . . . . .
98
B.2
Routering testcase 3: vaste starttijden DSH
. . . . . . . . . . . . . . . . . .
98
B.3
Routering testcase 4: vaste starttijden DSH
. . . . . . . . . . . . . . . . . . 100
B.4
Routering testcase 5: vaste starttijden DSH
. . . . . . . . . . . . . . . . . . 100
C.1
Routering testcase 2: variabele starttijd DSH
C.2
Routering testcase 3 variabele starttijd DSH . . . . . . . . . . . . . . . . . . 104
C.3
Routering testcase 4 variabele starttijd DSH . . . . . . . . . . . . . . . . . . 106
C.4
Routering testcase 5 variabele starttijd DSH . . . . . . . . . . . . . . . . . . 106
D.1
Invloed van de starttijd op testcase 2 . . . . . . . . . . . . . . . . . . . . . . 109
D.2
Invloed van de starttijd op testcase 3 . . . . . . . . . . . . . . . . . . . . . . 110
D.3
Invloed van de starttijd op testcase 4 . . . . . . . . . . . . . . . . . . . . . . 110
D.4
Invloed van de starttijd op testcase 5 . . . . . . . . . . . . . . . . . . . . . . 111
. . . . . . . . . . . . . . . . . 104
L¼st van tabellen 3.1
Voertuigverliesuren en lelengtes op het wegennet in 2007 en 2020 voor de verschillende regio's [4] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1
Berekening exacte reistijden testcase 1.
5.2
Kostenbepaling testcase 1
5
. . . . . . . . . . . . . . . . . . . .
49
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
5.3
Resultaten ver jnde intervallen AMPL . . . . . . . . . . . . . . . . . . . . .
51
6.1
Vervanging postcodes in beneluxpostcodeclusters
57
6.2
Kostenbepaling testcase 1: heuristiek: vaste starttijden.
6.3
Kostenbepaling testcase 1: heuristiek: variabele starttijden.
. . . . . . . . .
69
6.4
Gaps tussen het AMPL model met ver jnde intervallen en heuristiek. . . . .
71
6.5
Bepaling gap tussen AMPL ver jnd en benaderend intervalmodel . . . . . .
72
6.6
Gap tussen AMPL model en heuristiek: vaste starttijden . . . . . . . . . . .
73
6.7
Gap tussen AMPL model en heuristiek: variabele starttijden . . . . . . . . .
73
6.8
Gap tussen heuristiek met vaste en variabele starttijden
. . . . . . . . . . .
74
8.1
Transportkosten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
84
A.1
Berekening exacte reistijden testcase 2
. . . . . . . . . . . . . . . . . . . . .
91
A.2
Kostbepaling testcase 2: AMPL . . . . . . . . . . . . . . . . . . . . . . . . .
92
A.3
Berekening exacte reistijden testcase 3
. . . . . . . . . . . . . . . . . . . . .
92
A.4
Kostbepaling testcase 3: AMPL . . . . . . . . . . . . . . . . . . . . . . . . .
93
A.5
Berekening exacte reistijden testcase 4
. . . . . . . . . . . . . . . . . . . . .
94
A.6
Kostbepaling testcase 4: AMPL . . . . . . . . . . . . . . . . . . . . . . . . .
94
A.7
Berekening exacte reistijden testcase 5
. . . . . . . . . . . . . . . . . . . . .
95
A.8
Kostbepaling testcase 5: AMPL . . . . . . . . . . . . . . . . . . . . . . . . .
95
B.1
Kostbepaling testcase 2: vaste starttijden DSH
98
121
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
69
122
LST VAN TABELLEN
B.2
Kostbepaling testcase 3: vaste starttijden DSH
. . . . . . . . . . . . . . . .
99
B.3
Kostbepaling testcase 4: vaste starttijden DSH
. . . . . . . . . . . . . . . . 100
B.4
Kostbepaling testcase 5: vaste starttijden DSH
. . . . . . . . . . . . . . . . 101
C.1
Kostbepaling testcase 2: variabele starttijden DSH
. . . . . . . . . . . . . . 104
C.2
Kostbepaling testcase 3: variabele starttijden DSH
. . . . . . . . . . . . . . 105
C.3
Kostbepaling testcase 4: variabele starttijden DSH
. . . . . . . . . . . . . . 106
C.4
Kostbepaling testcase 5: variabele starttijden DSH
. . . . . . . . . . . . . . 107
