Het Extended Vehicle Routing Probleem met tijdstipafhankelijke reistijden onderworpen aan rij- en rusttijdreglementering

Het Extended Vehicle Routing Probleem met tijdstipafhankelijke reistijden onderworpen aan rij- en rusttijdreglementering Matthias Maes

Promotor: prof. dr. El-Houssaine Aghezzaf Begeleiders: Carles Sitompul, Yqing Zhong 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. ir. Hendrik Van Landeghem Faculteit Ingenieurswetenschappen Academiejaar 2009-2010

 

Het Extended Vehicle Routing Probleem met tijdstipafhankelijke reistijden onderworpen aan rij- en rusttijdreglementering Matthias Maes

Promotor: prof. dr. El-Houssaine Aghezzaf Begeleiders: Carles Sitompul, Yqing Zhong 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. ir. Hendrik Van Landeghem Faculteit Ingenieurswetenschappen Academiejaar 2009-2010

Woord vooraf Na maanden werken en schrijven mag ik met veel plezier zeggen dat mijn masterproef voltooid is. Het was een leerrijk proces waarbij gaandeweg mijn interesse voor dit probleem groeide. Hierdoor ging ik mij ook informeren in andere zoekpistes. Dit resulteerde in een wijziging van het thesisonderwerp. Het Inventory Routing Problem werd in overeenstemming met mijn promotor aangepast naar een Vehicle Routing Problem waarbij speciale aandacht uitging naar de wetgeving voor rij- en rusttijden. Voor het programmeren van deze masterproef wordt vooral gebruik gemaakt van Matlab. Het Iteratieve Multi Tour Opbouw- en Veteringsalgoritme, dat de basis vormt van deze thesis, wordt volledig geprogrammeerd in Matlab. Een kleine zijstap wordt gemaakt wanneer door middel van de Genetic and Evolutionary Algorithm Toolbox in Matlab het concept van Genetische Algoritmes wordt aangehaald. Deze toolbox is de ideale partner voor het oplossen van dit niet-lineair probleem. De handleidingen geschreven door Hartmut Pohlheim over deze Toolbox voor Matlab waren een handige leidraad. Een thesis schrijven kan je uiteraard niet alleen. Daarom wil ik iedereen bedanken die heeft bijgedragen aan het tot stand brengen van dit eindwerk. Zonder hen was dit resultaat niet behaald geweest. In het bijzonder gaat mijn dank uit naar mijn promotor professor ElHoussaine Aghezzaf die mij via kritische opmerkingen en nuttige tips goed geholpen heeft. Samen hebben we het pad uitgestippeld richting dit resultaat. De mensen van Digitach die mij meer uitleg gaven in verband met de wetgeving rond rij- en rusttijden zijn ook van harte bedankt. De Logistieke dienst van Colruyt verdient ook een vermelding net als de mensen van de Federale Overheidsdienst Mobiliteit en Vervoer die mij de nodige info bezorgden. Daarnaast bedank ik ook mijn vrienden die mij tijdens mijn 5 jaren aan de Universiteit Gent hebben bijgestaan om de niet-werkende tijd zo aangenaam mogelijk in te vullen. ZIj deden mij er aan denken dat er meer in het leven is dan studeren. Eveneens dank aan de mensen die fouten rapporteerden en/of verbeteringen suggereerden: Ann De Vijlder, Paul Maes. v

vi Speciale dank ook aan mijn schoonbroer Elie Deckers. Hij was het die op een familiefeest vroeg of ik rekening gehouden had met de rij-en rusttijdreglementering. Deze vraag leidde uiteindelijk tot een heroriëntering van mijn thesisonderwerp. Tot slot zou ik ook graag mijn ouders bedanken. Ik draag deze thesis dan ook aan hen op, voor hun constante steun in alles wat ik verkies te doen. Matthias Maes 21 augustus 2010

vii

Het Extended Vehicle Routing Probleem met tijdstipafhankelijke reistijden onderworpen aan rij- en rusttijdreglementering door Matthias Maes Masterproef ingediend tot het behalen van de academische graad van Master in de ingenieurswetenschappen: bedrijfskundige systeemtechnieken en operationeel onderzoek Academiejaar 2009–2010 Promotor: prof. dr. El-Houssaine Aghezzaf Begeleider: Carles Sitompul, Yqing Zhong Faculteit Ingenieurswetenschappen Universiteit Gent Vakgroep Technische bedrijfsvoering Voorzitter: prof. dr. ir. Hendrik Van Landeghem

Samenvatting Deze masterproef ontwerpt in eerste instantie een basismodel voor het Capacitated Vehicle Routing Probleem with Hard Time Windows. De routering wordt gekenmerkt door Multi Tours. Dit betekent dat een voertuig opnieuw kan binnenkomen in het depot voor herbevoorrading. Het basismodel wordt, nadat het zijn degelijkheid heeft bewezen, uitgebreid met de rij- en rusttijdreglementering die uitgaat van de Europese Unie. Hierdoor ontstaan Multi Tours waarbij rekening gehouden wordt met de verplichte rustpauzes om te vermijden dat er meer dan 4 uur en 30 minuten aan één stuk gereden wordt.

Trefwoorden Vehicle Routing Problem; Rij-en rusttijdreglementering; Multi Tour; Tijdstipafhankelijke reistijden;

The Extended Vehicle Routing Problem with time-dependent travel times subject to EU legislation on drivers’ working hours Matthias Maes Supervisor(s): El-Houssaine Aghezzaf Abstract— Legislation on drivers’ working hours is an important matter in distribution and logistics. This paper tries to design a model for the European context. In a first step, this survey designs a model to tackle the Capacitated Vehicle Routing Problem with hard time windows. The customers in this model are replenished by Multi Tours, a specific kind of tours in which vehicles can replenish their cargo in the depot. After this model has proven its value, the drivers’ working hours legislation imposed by the European Union is introduced into this model. Solutions are designed in a way that drivers take a break to avoid uninterrupted driving times of more than 4h30’. Keywords— Vehicle Routing Problem, Multi Tour, Time-Dependent Travel Times, Driving and rest time regulations

I. I NTRODUCTION On April 11, 2007 the new regulations within the European Union on drivers’ working hours entered into force. These regulations govern the working hours of truck and passenger carrying vehicle drivers. These regulations are created in order to improve road safety, to improve the working conditions of drivers and to promote fair competition between companies. These regulations are taken into account in the following Vehicle Routing Problem. II. BASIC VRPHTW MODEL A. Multi Tours and Time-dependent travel times The delivery locations of the n customers in this VRP with hard time windows have time windows within which the deliveries must be made. The objective function is the minimalisation of the route duration, route distance and vehicle rent costs. The following characteristics define the problem: aj ej gj lj qj tij yj

arrival time at customer j opening time of time window at customer j duration of service at customer j closing time of time window at customer j demand of customer j time-dependent travel time between customers i and j beginning of service a customer j

The difference (yj − aj ) is known as the waiting time at a customer location until the opening of the time window. So yj = max(ej , aj ), with aj = yi + gi + tij . A first step is to introduce Multi Tours in the mathematical model. A Multi Tour is driven by one vehicle that has the ability to replenish when it’s running out of cargo. In this way, a Multi Tour consists out of several subroutes during one Time Horizon.

Time-dependent travel time are captured into this model, using an adaption on the FIFO-based algorithm from Ichoua et al [3]. This algorithm calculates travel times from any two given customers i and j by using an iterative forward calculation from the arrival time at customer i. To design the necessary speed function, travelling speed data is obtained from the START/SITTER System, offered by the Belgian Ministery of Traffic and Infrastructure [4]. This service makes traffic data accesible of all the Belgian highways since 1999. B. Iterative Multi Tour Construction & Improvement Algorithm The Iterative Multi Tour Construction and Improvement Algorithm is an adaptation on an algorithm designed by M. Figliozzi to construct and improve routes [2]. The core of his IRCI algorithm is a construction algorithm were routes are sequentially built and improved. The solution method is divided into two phases: route construction and route improvement. Unlike local search heuristics, where customers or groups of customers are exchanged and inserted, the IRCI improves the solution of VRP problems creating and improving groups or sets of routes. These sets are selected using specific criteria as route duration, geographical proximity, route distance or number of customers in a route. The alterations made on Figliozzi’s algorithm are the introduction of Multi Tours in both phases and a different improvement method. Where Figliozzi improves a limited set of routes, the Multi Tour Improvement algorithm in this paper starts with all the Multi Tours and excludes every iteration one Multi Tour more from the improvement phase. The exclusion is based on performance criteria as mentioned above. III. D RIVERS ’ WORKING HOURS MODEL A. Regulations The EU rules apply to drivers of most vehicles used for the carriage of goods where the maximum permissible weight of the vehicle exceeds 3.5 tonnes and where the vehicle is used within EU and EEA countries and Switzerland. Driving time is the duration of driving activity or cargo handling recorded by a tachograph. After a driving period of no more than 4.5 hours, a driver must immediately take a uninterrupted break of at least 45 minutes or end his shift. Alternatively, a full 45minute break can be replaced by one break of at least 15 minutes followed by another break of at least 30 minutes. These breaks must be distributed over the 4.5-hour period. Breaks of less than

15 minutes will not contribute towards a qualifying break, but neither will they be counted as duty or driving time. A driver makes a ‘reset’ if he takes a 45-minute break (or qualifying breaks totalling 45 minutes) before or at the end of a 4.5hour (270’) driving period. This means that the next 4.5-hour period begins with the completion of that qualifying break, and in assessing break requirements for the new 4.5-hour period, no reference is to be made to driving time accumulated before this point [1]. Some correct driving time shedules are given in figure 1. A thick line stands for a reset.

Fig. 1. Correct examples of drivers’ working hours.

B. Model The Time Horizon is set from 7h00 until 16h45, which makes a maximum of 9 hours driving time possible. The Cumulated Driving Time (CDT ) on a moment in time t sums up the driving times (gi + tij ) between the time of the last reset and this moment t. The value CDT makes it possible to monitor the total driving time so that crossing the 270’ limit can be avoided. A new reset sets the CDT value back on 0. The Cumulated Break Time (CBT ) on a moment t gives the total break time taken since the last reset. This value is calculated to make a split break time possible. There are two kind of breaks. A first one is the Waiting Break (W B), which is a waiting time (yi − ai ) satisfying the constraints mentioned above. A second type is an Obligatory Breaks (OB), which has to be taken to avoid driving time violation. The diagram in figure 2 shows a mechanism calculating the arrival time aj , the service start time yj and the values CDTj and CBTj using CDTi and CBTi as input. These values are used in the Iterative Multi Tour Construction and Improvement algorithm to obtain Multi Tours which satisfy drivers’ working hours legislation. The following conditions are checked in a top-down approach: 1. Driving time violation during a travel time tij ? If this is the case, an Obligatory Break is needed to obtain a reset. 2. A Waiting Break provoking a reset? 3. Driving time violation during the service time gj . Because it’s unprofessional to interrupt a service time, an Obligatory Break after the travel time tij makes sure that no service time interruption is needed. 4. A Waiting Break which alters the CBT -value.

Fig. 2. Flow model describing the drivers’ working hours regulation.

IV. C ONCLUSIONS Computational results indicate that the algorithms solve the VRPHTW in a correct way while taking into acount the principles of time-dependent travel times and Multi Tours. The extension with the driver’s working legislation leads to satisfying results. ACKNOWLEDGMENTS The author would like to acknowledge M. Figliozzi for the inspiration derived from his paper [2]. R EFERENCES [1] COI. Rules on Drivers’ Hours and Tachographs. Vehiclee and Operator Services Agency, 2007. [2] M.A. Figliozzi. An iterative route construction and improvement algorithm for the vehicle routing problem with soft time windows. Transport. Res., Part C, 2009. [3] S. Ichoua, M. Gendreau, and J.Y. Potvin. Vehicle dispatching with time-dependent travel times. European Journal of Operational Research, 144(2):379–396, 2003. [4] Federale Overheidsdienst Mobiliteit-Vervoer. Samenwerkingsakkoord Federale Overheid - Gewesten - START/SITTER. http://www.start-sitter.be (laatst bekeken op 18 juni 2010), 2010.

Inhoudsopgave Gebruikte afkortingen en symbolen

xiii

1 Probleem beschrijving 1.1 Het Vehicle Routing Problem . . . . . . . . . . . . . . . . . . . . . . . 1.2 Extended Vehicle Routing Probleem met tijdstipafhankelijke reistijden worpen aan rij-en rusttijdreglementering . . . . . . . . . . . . . . . . . 1.3 Analyse van de complexiteit . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Oplossingsstrategie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Probleem formulering 2.1 Flow-arc formulering . . . . . . . . . 2.2 Algoritme T T T(tstart ,d,T I) . . . . . . 2.3 Variabelen . . . . . . . . . . . . . . . 2.4 Uitgewerkt voorbeeld . . . . . . . . . 2.5 Hulpwaarden . . . . . . . . . . . . . 2.6 Model voor een Time Windows VRP 2.6.1 Doelfunctie . . . . . . . . . . 2.6.2 Restricties . . . . . . . . . . .

. . . . onder. . . . . . . . . . . .

1 1 3 4 4

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

6 6 7 11 14 16 18 18 19

3 Het Iteratieve Multi Tour Opbouw- en Verbeteringsalgoritme 3.1 Het Ondersteunend Multi Tour Opbouwalgoritme Hr . . . . . . . . 3.1.1 Klant vj opnemen in de routering . . . . . . . . . . . . . . . 3.1.2 Routering vervolledigen met Nearest Neighbor algoritme . . 3.1.3 Algoritme Hr (Routering, vi , vj , Qi , C, ∆) . . . . . . . . . . . 3.2 Het Multi Tour Opbouwalgoritme Hc . . . . . . . . . . . . . . . . . 3.2.1 De Klantordenfunctie w(vi , C, W ) . . . . . . . . . . . . . . 3.2.2 Routering met behulp van Hr . . . . . . . . . . . . . . . . . 3.2.3 Algoritme Hc (Wi , Routeringi , vi , Qi , Ci ) . . . . . . . . . . . 3.3 Het Multi Tour Verbeteringsalgoritme Hv . . . . . . . . . . . . . . 3.3.1 De Multi Tour Ordenfunctie k(Routering − R) . . . . . . . 3.3.2 Algoritme Hv (Routering, W ) . . . . . . . . . . . . . . . . . 3.4 Resultaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1 Gegevens . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.2 Oplossingen . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

23 24 24 26 27 29 29 29 30 32 33 34 36 36 40

. . . . . . . .

x

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

xi

Inhoudsopgave 4 Model onderworpen aan rij- en rusttijdreglementering 4.1 Rij-en rusttijden . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Doel van de rij- en rusttijden . . . . . . . . . . . . 4.1.2 Rij- en rusttijdreglementering . . . . . . . . . . . . 4.1.3 Tachograaf . . . . . . . . . . . . . . . . . . . . . . 4.2 Aanpassen yj en aj aan de rij- en rusttijden . . . . . . . . 4.2.1 Benamingen . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Werking van het T ijd-algoritme . . . . . . . . . . 4.3 Voorbeeld . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Resultaten . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . .

44 44 44 44 48 48 48 51 56 58

. . . . . .

62 62 63 63 64 67 69

6 Besluit 6.1 Conclusies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Perspectieven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

72 72 73

A Algoritme W (X, n)

75

B Hr (Route, vi , vj , Qi , C, ∆) B.1 Hr.m . . . . . . . . . . B.2 T T T.m . . . . . . . . . B.3 T T T omg.m . . . . . . . B.4 degegevens.m . . . . . . B.5 Dcal.m . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

77 77 81 81 82 83

C Hc (W 1, Route, vi, Qi, Ci) C.1 Hc.m . . . . . . . . . . C.2 w.m . . . . . . . . . . . C.3 AddCustom.m . . . . . C.4 Kost.m . . . . . . . . . C.5 tot af stand.m . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

84 84 85 87 89 90

D Hv (Route, vi , vj , Qi , C, ∆) D.1 Hv.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.2 k.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.3 k.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

91 91 92 94

5 Genetisch algoritme 5.1 Werking Genetisch Algoritme . . . . . . . 5.2 Opstellen Genetisch Algoritme . . . . . . 5.2.1 Variabelen en VLUB . . . . . . . . 5.2.2 Doelfunctie . . . . . . . . . . . . . 5.2.3 Selectie, Recombinatie en Mutatie 5.3 Toepassing Genetisch Algoritme . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

Inhoudsopgave

xii

E T ijd(GRTi , GRTj ) E.1 T ijd.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E.2 T T T voor.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E.3 Hr1.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

96 96 98 98

Bibliografie

104

Gebruikte afkortingen en symbolen BPP

Bin Packing Problem

cd

Kostprijs per eenheid afgelegde weg

ct

Kostprijs per minuut dat route duurt

cv

Kostprijs per voertuig per dag

CVRP

Capacitated Vehicle Routing Problem

dij

Afstand tussen twee knooppunten i en j

ei

Starttijdstip Service Time Window

g(∆, i, j)

Gegeneraliseerde kostenfunctie

GA

Genetisch Algoritme

GEATbx

Genetic and Evolutionary Algorithm Toolbox

gi

Totale servicetijd

GNNH

Generalized Nearest Neighbor Heuristic

GOT

Gecumuleerde Onderbrekingstijd

gqi

Hoeveeldheidsafhankelijke servicetijd

GRT

Gecumuleerde Rijtijd

gstop

Standaard servicetijd

IMTOV

Iteratieve Multi Tour Opbouw- en Verbetering

IRP

Inventory Routing Problem

li

Sluitingstijdstip Service Time Window

MDVRP

Multi Depot Vehicle Routing Problem

NP

Nondeterministic Polynomial time

PVRP

Periodic Vehicle Routing Problem

qi

Hoeveelheid vraag voor de klant

qmax

Laadcapaciteit voertuig xiii

Hoofdstuk 0. Gebruikte afkortingen en symbolen SDVRP

Split Delivery Vehicle Routing Problem

tij

Reistijd ≥ 0

TSP

Traveling Salesman Problem

v0

Depot knooppunt waaruit alle subroutes vertrekken

vn+1

Depot knooppunt om te herbevoorraden of een subroute te stoppen

VO

Verplichte Onderbreking

VRP

Vehicle Routing Problem

VRPPD

Vehicle Routing Problem with Pick-up and Delivery

VRPTW

Vehicle Routing Problem with Time Windows

WO

Wachtonderbreking

Y0

Startuur van de werkdag

YT H

Einduur van de werkdag

xiv

Hoofdstuk 1

Probleem beschrijving 1.1

Het Vehicle Routing Problem

Basis van deze thesis is het Vehicle Routing Problem (VRP). Geformuleerd in 1959 door G. B. Dantzig and R.H. Ramser (3) vormt het VRP heden ten dagen nog steeds een boeiend onderwerp voor onderzoek binnen de logistiek. Het betreft een combinatorisch optimalisatieprobleem waarbij een aantal geografisch verspreide klanten van voorraad voorzien dienen te worden. Het VRP is een zeer belangrijk probleem in de transport- en distributiewereld. In sommige marktsectoren levert transport een groot aandeel in de toegevoegde waarde van de goederen. Daarom is het doel van het VRP de routes zodanig op te stellen dat alle klanten correct bevoorraad worden tegen een minimale distributiekost. Grootste kosten betreffen vooral de afstandvergoeding, de lonen van de chauffeurs en de huurprijs van een voertuig. Door op de kost van een voertuig een hoge prijs te kleven, wordt er aan fleet sizing gedaan. Hier wordt dan getracht de benodigde voertuigenvloot zo klein mogelijk te houden. De beschrijving van het Vehicle Routing Problem gaat als volgt: beschouw een één depot waarin enkele vrachtwagens instaan voor de bevoorrading van ‘n’ klanten gedurende een bepaalde werkdag. Deze klanten wensen een deterministische hoeveelheid van één of meerdere producttypes. De vloot voertuigen staat in om via bepaalde subroutes de goederen tot bij de klant te brengen vanuit het depot. Een subroute bestaat dus uit een vertrek vanuit een depot, het bezoek aan een aantal klanten en een terugkeer naar het depot. Elke klant kan bevoorraad worden binnen zijn Service Time Windows. Dit is het tijdsinterval waarbinnen levering mogelijk is aan de klantzijde. Het is nu aan de leverancier om een routering op te stellen waarbij aan elke klant de juiste hoeveelheid goederen geleverd wordt binnen het Service Time Window van deze klant.

1

Hoofdstuk 1. Probleem beschrijving

2

Figuur 1.1: Voorbeeld van 6 klanten die bedeeld worden door 2 routes.

Vele variaties op dit basismodel zijn reeds veelvuldig beschreven. Hieronder volgt een overzicht van enkele types: • Vehicle Routing Problem with Time Windows (VRPTW): de klanten hebben time windows waarbinnen de levering dient plaats te vinden. • Capacitated Vehicle Routing Problem (CVRP): de voertuigen hebben een beperkte capaciteit die ze kunnen vervoeren. • Multi Depot VRP (MDVRP): de verdeler beschikt over meerdere voorraaddepots. • VRP with Pick-Up and Delivery (VRPPD): een aantal goederen dienen bij een klant opgehaald te worden om ze bij een andere klant af te leveren. • Split Delivery VRP (SDVRP): de klanten kunnen bediend worden door verschillende voertuigen. • Periodic VRP (PVRP): leveringen kunnen meerdere dagen duren.


1.2

3

Extended Vehicle Routing Probleem met tijdstipafhankelijke reistijden onderworpen aan rij-en rusttijdreglementering

Het onderwerp van deze thesis is het VRP beschreven in bovenstaande titel. Dit model voldoet aan zowel het Capacitated Vehicle Routing Problem als het Vehicle Routing Problem met Time Windows. Alle klanten beschikken dus over een Time Window (VRPTW) waarbinnen geleverd moet worden door identieke vrachtwagens die een maximale laadcapaciteit hebben (CVRP). Daarenboven wordt er rekening gehouden met volgende restricties: Tijdstipafhankelijke reistijden De reistijden zijn afhankelijk van de afstand én het tijdstip waarop de reis wordt aangevat. De werkdag wordt ingedeeld in tijdsintervallen waarin een bepaalde snelheid gehanteerd wordt. Op deze manier is het mogelijk spitsuren weer te geven. Start een vrachtwagen met rijden in een bepaald tijdsinterval, dan wordt er gerekend dat de vrachtwagen rijdt aan de snelheid die gekoppeld is met dat interval. Wanneer een volgend tijdsinterval aanbreekt, wordt de gemiddelde snelheid aangepast aan deze van het nieuwe tijdsinterval. Multi Tour met herbevoorrading Een vrachtwagen kan zich na een subroute herbevoorraden in het depot. Een subroute bestaat uit een vracht die verdeeld wordt onder bepaalde klanten, waarna teruggekeerd wordt naar het depot. In het depot kan dan beslist worden om dit voertuig opnieuw de baan op te sturen met een nieuwe lading, of het voor de rest van de dagelijkse Time Horizon in het depot ongebruikt te laten. Over een hele dag gezien, maakt een voertuig dus een Multi Tour die bestaat uit meerde subroutes. Rij-en rusttijdreglementering Sinds 11 april 2007 heeft de Europese Unie de wetgeving rond rij- en rusttijden in het transportvervoer aangepast voor voertuigen zwaarder dan 3,5 ton. Zo worden de maximale dagelijkse, wekelijkse en tweewekelijkse rijtijden vastgelegd. Deze zijn onderhevig aan de nodige rusttijden. Deze nieuwe wetgeving is in werking sinds 1 mei 2007. Door middel van een tachograaf wordt de opvolging van deze wetgeving nagekeken. In hoofdstuk 4 wordt deze wetgeving dieper uitgespit, zodat ze toegepast kan worden op het model.


1.3

4

Analyse van de complexiteit

Van combinatorische problemen is graag geweten hoe moeilijk het is deze op te lossen. De complexiteitstheorie biedt een mogelijkheid om deze problemen in te delen. Het werk van M.R. Garey and D.S. Johnson (7) vormt een mooie inleiding tot deze theorie. Voor het Vehicle Routing Problem is bewezen dat het een NP-hard, zelfs NP-complete, probleem is (7). Voor zulke problemen is het vaak aangewezen benaderende oplossingen te vinden, die veel vlugger te vinden zijn. Hiervoor maakt men dan gebruik van heuristieken. Voor een variant op het Vehicle Routing Problem, namelijk het Vehcile Routing Problem met Time Windows is door M. Savelsberg (13) aangetoond dat het NP-complete is. Het hier gedefinieerde probleem is een versie van VPRTW die een hogere moeilijkheidsgraad heeft dan het VPRTW door het invoeren van Multi Tours, fleet sizing en tijdstipafhankelijke reistijden. Omdat de gewone VRPTW een gemakkelijkere versie is van dit probleem die NP-Complete is, kan men er vanuit gaan dat dit probleem eveneens NP-Complete is. Het Vehicle Routing Probleem is sterk gebaseerd op twee andere NP-Hard problemen die reeds veelvuldigd bestudeerd werden in de literatuur (4): • Het Traveling Salesman Problem: wanneer de capaciteit van de voertuigen oneindig gesteld wordt, bekomt men een instantie van een Mutliple Traveling Salesman Problem. Een MSTP instantie kan omgevormd worden tot een TSP instantie door aan de graaf k-1 extra kopies van knoop 0 toe te voegen samen met de takken die aan knooppunt 0 grenzen. (waarbij k het aantal routes bedraagt). • Het Bin Packing Problem: de vraag of er een feasible solution bestaat voor een gegeven instantie van het VRP is een instantie van het BPP. De beslissingen in het BPP zijn conceptioneel equivalent aan het VRP model waarbij alle takken hun kosten 0 bedragen. Er kan dus gesteld worden dat de eerste transformatie gelijk is aan een relaxatie van het onderliggende BPP en de tweede transformatie gelijk is aan een relaxatie van het onderliggende TSP. Een volledige oplossing van het VRP is dan een TSP tour die voldoet aan de BPP voorwaarden. Omwille van de wisselwerking tussen beide onderliggende modellen kunnen instanties van het Vehicle Routing Problem heel moeilijk op te lossen zijn in de praktijk.

1.4

Oplossingsstrategie

Een eerste stap is het opstellen van een wiskundig model dat het probleem beschrijft. In hoofdstuk 2 wordt een basismodel opgesteld dat voldoet aan VRPTW, CVRP, de tijdstipafhankelijke reistijden en de Multi Tour conditie. Er is getracht het wiskundig model op te stellen met zo weinig mogelijk variabelen zodat het eenvoudig ge¨ımplementeerd kan worden in zowel een Multi Tour Verbeteringsalgoritme als in een Genetisch Algoritme.


5

Het Iteratieve Multi Tour Opbouw- en Verbeteringsalgoritme, dat de belangrijkste oplossingsstrategie is van deze thesis, wordt behandeld in hoofdstuk 3. Dit algoritme maakt gebruik van twee fasen. In een eerste fase wordt een routering opgesteld en in een tweede fase wordt getracht deze routering te verbeteren. Bij de opbouwfase moet bepaald worden wie de eerstvolgende klant in de partiële routering wordt. Als er m ongerouteerde klanten over zijn, dan wordt de routering m maal vervolledigd, waarbij telkens een andere ongerouteerde klant als eerste aan bod komt in de vervollediging. De vervollediging van de partiële routering gebeurt door middel van een nearest neighbor algoritme. Uit de m volledige routeringen wordt dan de goedkoopste routering gekozen. De ongerouteerde klant die in deze routering als eerste toegevoegd wordt aan de partiële routering, wordt dan gekozen als eerstvolgende klant om definitief in de partiële routering opgenomen te worden. In de verbeteringsfase worden volgens bepaalde criteria enkele ‘mindere’ Multi Tour geselecteerd die opnieuw gerouteerd dienen te worden. Wanneer deze herschikte Multi Tours een goedkoper resultaat opleveren, worden zij opgenomen in de routering en worden de oorspronkelijke Multi Tours verwijderd. Pas in hoofdstuk 4 wordt dit basismodel uitgebreid met de rij- en rusttijdreglementering, zodat verzekerd kan worden dat het basismodel naar behoren werkt. In hoofdstuk 5 wordt het basismodel opgelost door middel van een eenvoudig Genetisch Algoritme. Voor het vak Applied Combinatorial Optimization and Heuristics werd gevraagd een Genetisch Algoritme op te stellen dat betrekking had op het thesisonderwerp. Met behulp van de Genetic and Evolutionary Algorithm Toolbox voor Matlab wordt een eenvoudige poging ondernomen een oplossing te vinden met behulp van een Genetisch Algoritme. Het betreft hier echter eerder een aanzet tot een oplossing, dan een echte wiskundig sterke oplossing. Maar voor de volledigheid is dit toch opgenomen in de thesis. Tot slot worden er in hoofdstuk 6 conclusies getrokken uit deze thesis.

Hoofdstuk 2

Probleem formulering 2.1

Flow-arc formulering

Een traditionele flow-arc formulering wordt gebruikt om het probleem te beschrijven. Het distributienetwerk bestaat uit een depot en n klanten, dat voorgesteld wordt door de graaf G(VG , A), met VG de knooppuntenverzameling {v0 , ..., vn , vn+1 } en A de verzameling takken {(vi , vj ) : i 6= j ∧i, j ∈ VG }. Elke tak (vi , vn ) heeft een daarmee gerelateerde constante afstand dij . Deze afstand wordt afgelegd in een reistijd tij (bi ) die afhankelijk is van het tijdstip van vertrekken bi . Per eenheid afgelegde afstand wordt een kost cd gerekend. De duur van de Multi Tour wordt belast per tijdseenheid met ct . De twee knooppunten v0 en vn+1 stellen beiden de depot voor. v0 wordt gebruikt als startpunt van elke subroute en vn+1 stelt het eindpunt voor van elke subroute. Dit kan dan optreden als definitief eindpunt wanneer de Multi Tour stopt of als herbevoorradingspunt als er een subroute volgt op de binnenkomende subroute. Identieke voertuigen die maximaal een capaciteit qmax kunnen vervoeren, worden naar de klanten gezonden. Per voertuig wordt een prijs cv gerekend per dag. De totale duur om deze vrachtwagen te laden is g0 . In deze g0 zit een constante waarde gstop bevat en een laadtijd g(q0 ). De Service Time Windows van de depot [e0 , l0 ] en [en+1 , ln+1 ] zijn gelijk. Deze worden gelijkgesteld aan [Y0 , YT H ]. Y0 stelt dan 7u00 voor, het begin van de werkdag (420 minuten). YT H stelt het einde van de dag voor, namelijk 16u45 (1005 minuten). In dit verslag wordt uitgegaan van een werkdag die 9 uren en 45 minuten bedraagt. Klanten hebben elk een vraag qi ≥ 0. De totale Service Time aan klantzijde is gi = g(qi ) + gstop ≥ 0. Het Service Time Window waarbinnen het voertuig moet aankomen is [ei , li ].

6

Hoofdstuk 2. Probleem formulering

7

Een korte samenvatting: cv ct cd dij [ei , li ] gi = gstop + gqi qi qmax tij v0 vn+1 Y0 YT H

kostprijs per voertuig per dag kostprijs per minuut dat Multi Tour duur kostprijs per eenheid afgelegde routeafstand afstand tussen twee knooppunten i en j starten sluitingstijd Service Time Window totale Service Time gevraagde hoeveelheid door de klant laadcapaciteit voertuig reistijd ≥ 0 depot knooppunt waaruit alle subroutes vertrekken depot knooppunt om te herbevoorraden of een subroute te stoppen starttijd van de Daily Time Horizon sluitingstijd van de Daily Time Horizon

Een Multi Tour bestaat dus uit één of meerdere subroutes. Deze subroutes moeten van elkaar onderscheiden worden. Daarom wordt elke subroute genoemd naar de laatste klant op zijn route. Zo zal de subroute die klant 3 als laatste klant heeft voor terugkomst in het depot, de naam 3 dragen. Deze methode is mogelijk, omdat elke klant slechts een keer bezocht wordt gedurende de werkdag.

2.2

Algoritme T T T(tstart ,d,T I)

Het doel van dit algoritme is om de tijdsafhankelijke reistijden te berekenen gegeven het tijdstip tstart waarop de rit start en de afstand d die afgelegd wordt. Input T I stelt een matrix voor. Deze is voorzien van een rij T van tijdsintervallen en een rij S van snelheden die corresponderen met die tijdsintervallen. Deze tijdsintervallen worden bepaald door een dag op te splitsen in p tijdsintervallen T= T1 , T2 , ..., Tp . Elk interval [Tk , Tk+1 [ wordt gelinkt aan een constante rijdsnelheid Sk die gedurende dit interval aangehouden wordt. Dit algoritme is een aanpassing op het algoritme van S. Ichoua, M. Gendreau, and J.Y. Potvin (8).


8

Start T(tstart ,d,T I) 1. t∗ ← 0 2. find k ∈ [1, ..., p], Tk ≤ tstart ≤ Tk+1 3. t∗ ← tstart + d/Sk 4. while (t∗ > Tk+1 ) do 5.

d ← d − (Tk+1 − tstart )Sk

6.

t∗ ← Tk+1 + d/Sk+1

7.

k ←k+1

8. end while 9. return (t∗ − tstart ) Als output wordt de totale rijtijd gegeven. Een belangrijke eigenschap van deze output is dat het principe van First In - First Out gerespecteerd wordt. Daardoor zal een voertuig dat klant vi verlaat om naar klant vj te gaan en vertrekt op tijdstip t steeds vroeger aankomen dan een voertuig dat hetzelfde traject aflegt maar start op een tijdstip t + σ (σ > 0). Een aangepaste versie van dit algoritme T T T omg(teind ,d,T I) wordt eveneens gebruikt. Hierbij berekent men de reistijd uitgaande van het tijdstip teind waarop het transport aankomt. De programmering van deze algoritmes in Matlab zijn beschreven in appendices B.2 en B.3. Data intervallen Voor de data van de gemiddelde snelheden van vrachtverkeer op de autowegen werd contact opgenomen met verschillende overheidsdiensten. De website http://www.start-sitter.be, opgericht door de Federale Overheidsdienst Mobiliteit en Vervoer (10), beschikt over deze data. Via een uitgebreid netwerk van meetpunten aanwezig aan tunnels, verkeerswisselaars, ringwegen en E-wegen registreren zij o.a. voertuigkilometers, verkeersvolumes, wegvak verzadiging, snelheid van personenwagens en vrachtverkeer, zwaarte van files, ... . Verantwoordelijke van deze applicatie, Danny Weckhuyzen, liet mij weten dat de data voor vrachtverkeer niet altijd even accuraat zijn. Voornamelijk bij vertraagd verkeer heeft het systeem moeite vrachtwagens van personenwagens te onderscheiden. Onderstaande figuur is een schermafdruk van de webapplicatie Start-Sitter. Via de verschillende kaders kunnen de gewenste data opgevraagd worden. De kolom S2 bevat de gemiddelde snelheden voor vrachtverkeer.


9

Figuur 2.1: Webapplicatie www.start-sitter.be.

Ondanks de beperkingen wordt toch een poging ondernomen om via deze applicatie een snelheidsfunctie op te stellen voor tijdsintervallen van 60 minuten. Deze snelheidsfunctie zal dan een goede leidraad zijn voor de snelheidsfunctie die gebruikt zal worden in de algoritmes. Uit de talrijke meetpunten wordt gekozen voor de ringweg R4 rond Gent. Dit is een weg met veel vrachtverkeer, dus een goede indicatie. Vervolgens worden de data bekeken voor een normale werkweek, namelijk van maandag 7 juni 2010 tot vrijdag 11 juni 2010. Van de (correcte) data wordt een weekgemiddelde genomen. Deze gemiddelde snelheidsfunctie wordt uitgevlakt aan de zijkanten en verminderd met 20km/h, omdat de trajecten niet enkel over autostrades lopen. Eveneens worden de ochtend- en avondspits benadrukt in de gecorrigeerde snelheidsfunctie. Dit levert volgend resultaat (alle data in km/h):

10


0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

7/6/10

8/6/10

9/6/10

10/6/10

11/6/10

Gemid. v

Gecorrig. v

101 100 101 101 101 103 96 90 88 89 92 90 91 93 90 90 92 91 93 101 99 102 105 100

100 100 100 100 100 98 95 90 89 91 91 92 91 90 91 92 93 95 96 96 102 102 103 103

101 102 103 101 102 100 92 86 84 84 87 89 89 86 88 88 88 81 87 94 99 99 100 155

138 138 138 130 132 102 90 87 85 86 87 87 87 87 85 86 87 85 88 91 98 98 97 100

100 100 100 100 100 100 93 90 88 90 91 91 91 90 92 89 92 92 95 99 101 102 102 99

100,5 100,5 101 100,5 100,75 100,6 93,2 88,6 86,8 88 89,6 89,8 89,8 89,2 89,2 89 90,4 88,8 91,8 96,2 99,8 100,6 101,4 100,5

80 80 80 80 80 80 71 68.6 66.8 68 69.6 69.9 69.8 69.2 69.2 69 70.4 68.8 71.8 76.2 80 80 80 80

Uiteraard is de gecorrigeerde snelheid in deze tabel slechts een leidraad voor een snelheidsfunctie. Wanneer men een specifiek Vehicle Routing Problem heeft, wordt de snelheidsfunctie opgesteld rekening houdend met probleemspecifieke factoren zoals de soort wegen (autostrade, gewestweg, dorpskern), de regio (ring Antwerpen, E19, ...), ... In onderstaande figuur ziet u een grafische voorstelling van de gecorrigeerde snelheidsfunctie. In de algoritmes wordt een andere snelheidsfunctie gebruikt waarbij de ochtend- en avondspits nog meer benadrukt worden.


11

Figuur 2.2: Gecorrigeerde snelheidsfunctie.

2.3

Variabelen

In wat volgt wordt een overzicht gegeven van de ingevoerde variabelen. Hun mening wordt verduidelijkt door middel van enkele figuren. In deze figuren worden klanten voorgesteld door cirkels en het depot door een rechthoek. Om de schetsen niet te ingewikkeld te maken, worden begindepot 0 en einddepot n + 1 in de routering niet op dezelfde plaats afgebeeld, hoewel beide depots dezelfde depot voorstellen. De y-variabelen geven tijdstippen weer. In het Multi Tour Verbeteringsalgoritme kunnen deze reële waarden aannemen. In het Genetisch Algoritme worden dit gehele waarden zodanig dat alle variabelen in het Genetisch Algoritme van het type integer zijn. Indien n het aantal klanten voorstelt, dan hebben we in totaal 4n variabelen: xi

i ∈ [1, n], xi ∈ [1, n + 1]

Integer beslissingsvariabele die aanduidt dat vanuit klant vi naar het knooppunt vxi gereisd wordt. Deze variabele geeft dus weer dat na een bezoek aan een klant vi , er gekozen wordt voor een bezoek aan een andere klant of voor binnenkomst in het depot. Zo wordt ervoor gezorgd dat er steeds een traject vertrekt uit een klant-knooppunt. De xi variabelen geven weer waarheen een route leidt vanuit een klant. Doordat enkele klanten ook richting het depot vn+1 trekken, komen niet alle klanten voor in de reeks [x1 , x2 , ..., xn ]. Voor de klanten die niet voorkomen in deze xi -variabelen wordt er vanuit gegaan dat zij bereikt worden via een route


12

die vertrekt uit het depot.

Figuur 2.3: De mogelijke waarden voor x.

yi

i ∈ [1, n], y i ∈ [max(Y0 , ei − t0i − g0 ), li − t0i − g0 ]

Reële of integer (GA) beslissingsvariabele die aanduidt wanneer de service start in het depot v0 om de tocht voor te bereiden naar klant vi . Met het starten van een service bedoelt men in het depot het inladen van de vrachtwagen. De waarde y i moet zodanig gekozen worden dat de aankomst bij de klant plaatsvindt binnen het Service Time Window van deze klant. Het vroegste vertrek uit het depot is dan pas mogelijk voor een ondergrens max(Y0 , ei − t0i − g0 ). De Multi Tour kan pas starten als de werkdag begonnen is, vandaar Y0 . Men wil bij de eerste klant ten vroegste aankomen op het moment dat het Service Time Window opengaat. Daarom moet de ondergrens van y i gekozen worden rekening houdend met de laadtijd g0 en rijtijd t0i , zodanig dat pas gestart wordt zodat er ten vroegste op ei aangekomen wordt bij klant vi . Onderstaande figuur toont eerst een voertuig dat onmiddellijk aan de service begint. Hierdoor moet er op de locatie van de klant nog gewacht worden (grijze balk). In de onderste voorstelling vindt deze wachttijd plaats in het depot, zodat de chauffeur zich nog kan bezighouden met andere taken dan wachten.

Figuur 2.4: Een voorbeeld voor de ondergrens van de y i -waarden. De groene balk stelt het Service Time Window voor van de klant. De onderste voorstelling is de correcte.

De bovengrens is via dezelfde gedachtengang berekend. y i dient zodanig gekozen te worden dat er rekening houdend met de laad- en rijtijd nog op tijd vertrokken wordt om de klant te bereiken voor het sluiten van zijn Service Time Window.


13

Figuur 2.5: Een voorbeeld voor de bovengrens van de y i -waarden. De onderste voorstelling is de correcte, waarbij er nog net op tijd gestart wordt om tijdig aan te komen bij de klant.

yi

i ∈ [1, n], yi ∈ [ei , li ]

Reële of integer (GA) beslissingsvariabele die aanduidt wanneer de service start in klant vi . Met het starten van een service bedoelt men aan klantzijde het uitladen van de vrachtwagen. Dit tijdstip moet binnen het Service Time Window van de klant gelegen zijn.

Figuur 2.6: yi moet binnen het Service Time Window vallen.

zi

i ∈ [1, n], zi ∈ [0,n+1].

Integer beslissingsvariabele die de volgende stap aanduidt voor een subroute die binnenloopt in het depot na het bezoek aan klant vi . zi = 0 betekent dat het transport van klant vi naar het depot niet plaatsvindt. Daardoor kan er ook geen opvolger gezocht worden. zi = n + 1 betekent dat deze subroute de laatste is en de Multi Tour eindigt daar. Na de binnenkomst in het depot zal dus geen nieuwe subroute meer vertrekken. zi = j met j ∈ [1, n] betekent dat er na binnenkomst in het depot terug vertrokken wordt richting klant vj . Voorwaarde hierbij is wel dat het transport van het depot naar vj plaatsvindt.


14

Figuur 2.7: De drie mogelijke waarden voor z.

2.4

Uitgewerkt voorbeeld

Om dit model duidelijk te maken, wordt hieronder een voorbeeld uitgewerkt. Stel u een voertuig voor dat klanten 1 tot 5 dient te bevoorraden. De VRP rekent uit dat volgend resultaat het best de kostenfunctie minimaliseert: Variabelen

xi yi yi zi

1

2

3

4

5

6

5 682 750 0

6

3 460 520 0

1

863 6

589 2

800 0

Service Time Windows

0 1 2 3 4 5

ei

li

420 420 750 500 520 800

1005 1005 1005 600 750 1005

In de afbeelding hieronder wordt een oplossing voorgesteld op basis van bovenstaande gegevens. Het voertuig wacht eerst in het depot om te vermijden dat bij de eerste klant reeds gewacht moet worden op de opening van het Service Time Window. In de depot kan de chauffeur zich ten minste nog nuttig maken op een andere manier. Daarom start de service in het depot pas om 460. De service in het depot omvat het inladen van het voertuig, gedurende g0 . Dit wordt gevolgd door een reistijd t04 naar de klant. Door de starttijd van de service in het depot af te stellen op het Time Window van klant 4, wordt er aangekomen aan


15

klant 4 gelijktijdig met het openen van het Time Window, namelijk 520. De service kan dus onmiddellijk starten. Daar wordt uitgeladen, g4 , waarna de trip verder gaat richting klant 3. Daar komt het voertuig aan binnen het Service Time Window van klant 3, want het uitladen g3 kan onmiddellijk beginnen op 589. Vervolgens wordt er terug naar het depot gereden. Aan de hand van de w3 -waarden is het mogelijk na te gaan of q4 w43 + q3 w33 ≤ qmax . De waarde z3 = 2 geeft aan dat er een nieuwe subroute vertrekt richting klant v2 . Daar wordt wederom halt gehouden zodanig dat er gewacht kan worden in het depot in plaats van op de locatie tot het openen van het Service Time Window bij de eerstvolgende klant . Op 682 start het inladen van de vrachtwagen in het depot. Om 750 kan dan, gelijktijdig met de opening van het Time Window de service bij klant 2 beginnen. De route trekt dan verder van klant 2 naar klant 5. Daar moet echter gewacht worden tot 800 voor het beginnen van y5 omdat het Service Time Window nog niet open is. Tot slot wordt via klant 1 naar het depot gereisd. Daar duidt de waarde z1 = 6 er op dat er geen nieuwe subroute meer uitrijdt. voertuig 1: v0 → v4 → v3 → v6 → v0 → v2 → v5 → v1 → v6

Figuur 2.8: Een voorbeeld van een distributiepatroon voor een voertuig met n=5. Grijs stelt wachttijden voor, oranje service tijden en roos reistijden.


2.5

16

Hulpwaarden

Het vooropgestelde model moet nog onderworpen worden aan enkele restricties. Dit zou perfect kunnen op basis van de 4n-variabelen. De voorstelling van de restricties wordt echter een pak eenvoudiger indien men uit deze 4n-variabelen enkele hulpwaarden berekend. Hieronder volgt de betekenis van deze hulpwaarden: i ∈ [1, n], xi ∈ {0, i}

xi

Deze hulpwaarden duiden aan of een klant vi bereikt wordt via een subroute startend in het depot. xi = i geeft dus weer dat klant i bereikt wordt vanuit het depot. xi = 0 geeft weer dat klant i bereikt wordt via een subroute startend bij een andere klant. Een voorbeeld voor n=3 maakt veel duidelijk:

Figuur 2.9: Voorbeeld voor de x-waarden met n=3.

De variabelen worden ten slotte verenigd in een vector X waarin eerst de n xi -waarden voorkomen, gevolgd door de n xi -variabelen. wis

i ∈ [0, n], s ∈ [1, n], wis ∈ {0, 1}

Zoals reeds vermeld is, worden subroutes genoemd naar de laatste klant voor hun terugkeer naar het depot. In bovenstaande figuur zou dit betekenen dat er subroute 1 en subroute 2 bestaan. Via deze binaire hulpwaarden wis duiden we aan of de subroute s die klant vi aandoet, vervolgens op een correcte manier verder reist naar eventuele volgende klanten en ten slotte terugkeert naar het depot vn+1 . Het algoritme beschreven in de appendix A kent enkel wis = 1 toe indien: • de klant vj die na vi komt reeds een waarde wjs = 1 heeft. Dit betekent dus dat vi verbonden wordt met een klant die reeds op een correcte manier verbonden is met het depot. • wss = 1: de klant die zijn naam verbonden heeft aan de subroute heeft een rechtstreeks transport naar het depot vn+1 .


17

• vi de enige klant is die naar vj reist. Hierdoor vermijdt men dat meerdere subroutes eenzelfde klant aandoen.

Figuur 2.10: Voorbeeld voor de w-waarden.

Het uiteindelijke doel in de restricties is er voor te zorgen dat elke klant juist 1 wis -waarde heeft die 1 is. Zodanig bekomt men een correcte routering waarin elke klant bezocht wordt door een correcte subroute. Subroutes die lussen beginnen maken worden zo vermeden. Meer hierover wanneer de restricties worden ingevoerd. In onderstaande figuur wordt eens een voorbeeld gegeven van de toekenning van de w-waarden voor n = 7. Vanuit klanten 3 en 7 wordt er op een correcte manier naar het einddepot 8 gereisd. De waarden w33 en w77 worden dus aan 1 gelijkgesteld. De s-index verwijst naar de naam van de subroute, die bepaald wordt door de laatste klant voor binnenkomst in het depot. Vervolgens zien we dat vanuit klant 1 op een correcte manier gereisd wordt naar klant 3, waarvan reeds aangetoond is dat vanuit klant 3 het depot bereikbaar is. Dus w13 = 1, omdat klant 1 in subroute 3 ligt. Vanuit klanten 5 en 6 reizen twee voertuigen naar klant 7 die reeds een w-waarde verschillend van 0 heeft. Het is echter niet toegestaan dat meerdere routes dezelfde klant aandoen. Vandaar dat klanten 5 en 6 geen w-waarde toegekend krijgen die gelijk is aan 1. Hierdoor weet het model dat klanten 5 en 6 niet correct gerouteerd zijn. Tot slot valt op dat klanten 2 en 4 ook geen w-waarden hebben die gelijk zijn aan 1. Dit omdat vanuit deze klanten het depot niet op een correcte manier bereikt wordt omwille van een lus.


18

Figuur 2.11: Voorbeeld van de toekenning van de w-waarden met n=7.

Opmerking Deze w-waarden lijken op het eerste zicht redelijk ingewikkeld. De verklaring hiervoor is te vinden in het feit dat het model ook geschikt is voor een Genetisch Algoritme. Terwijl het Iteratieve Multi Tour Opbouw- en Verbeteringsalgoritme intern over meer probleemspecifieke kennis beschikt, is dit bij het Genetisch Algoritme minder het geval. Daardoor moet er in deze w-waarden al enige intelligentie gestopt worden, zodanig dat de doelfunctie van het Genetisch Algoritme beter te sturen valt. Terwijl het Iteratieve Multi Tour Opbouw- en Verbeteringsalgoritme meteen correcte routes opbouwt, start het Genetisch Algoritme door willekeurige toekenningen aan de variabelen. Daardoor heeft het GA initieel routes die niet correct verlopen omwille van routes die plots stoppen, routes die uit het niets beginnen, lussen... Daarom moet het GA eerst gestuurd worden door middel van de w-waarden zodanig dat er een correcte routering verkregen wordt die men dan kan aanpassen. De wis -waarden zijn ook nodig om klanten binnen één subroute aan elkaar te linken, wat handig zal blijken in de restricties.

2.6 2.6.1

Model voor een Time Windows VRP Doelfunctie

De doelfunctie voor dit VRP is een kostenfunctie die geminimaliseerd dient te worden. De totale kostprijs van de gehele routering omvat de huur van het aantal voertuigen, de kilometervergoeding van de totaal afgelegde afstand en tot slot de uitbetaalde lonen aan de chauffeurs gedurende de routeduur. Volgende formulering van de doelfunctie wordt bekomen:

19

Hoofdstuk 2. Probleem formulering minimaliseer:

n n X X cv (zi = n + 1) + cd (d0xi + dixi ) i=1

(2.1)

i=1

n n h X +ct (xi = n + 1) yi + gi + ti i=1

n+1

i o i + (z i )+ (z i 6= n + 1)(y z − yi ) − (xi )+ y i

Een voertuig dat gebruikt wordt, zal op een gegeven moment zijn Multi Tour stoppen. Dit wordt gekenmerkt door zi = n + 1. Wanneer men dan kijkt hoeveel maal deze specifieke zi -waarde voorkomt, dan vindt men het aantal gebruikte voertuigen. Voor de afgelegde weg kijkt men eerst naar de routes van het depot naar de klanten. Stelt men d00 = 0 dan kan men deze afstand voorstellen door d0xi , want de trajecten die niet plaatsvinden, xi = 0, resulteren dan in een afstand d00 = 0. De totale afstand van de trajecten die vertrekken vanuit de klanten wordt dan voorgesteld door de som van dixi . Tot slot wordt de duur van de Multi Tours berekend. De routeduur wordt hier gedefinieerd als de tijdspanne tussen het starten van de service voor een subroute y i en het tijdstip waarop een subroute terug binnenkomt, yi + gi + ti n+1 . Deze laatste tijd wordt vermeerderd met de wachttijd in het depot tussen twee subroutes indien het een herbevoorrading betreft, vandaar i de term (z i )+ (z i 6= n + 1)(y z − yi ). De factoren (xi = n + 1) en (xi )+ zorgen ervoor dat enkel de tijdstippen gerekend worden van de klanten die laatst, respectievelijk eerst in een subroute liggen.

2.6.2

Restricties

Hierna volgen de restricties waaraan het model moet voldoen om correcte routes te genereren. Elke klant wordt bereikt n X j=1

(Xj == i) = 1

∀i ∈ [1, n]

(2.2)

Deze restrictie zorgt ervoor dat elke klant bereikt wordt. Elke klant moet exact eenmaal voorkomen in de vector X = [x1 ...xn x1 ...xn ]. Dit komt er dan op neer dat naar elke klant een traject wordt ondernomen ofwel vanuit het depot (xi ) ofwel vanuit een andere klant (xi ).

20

Hoofdstuk 2. Probleem formulering Laadcapaciteit voertuig n X j=1

qj wjs ≤ qmax

∀s ∈ [1, n]

(2.3)

Elke vrachtwagen kan maximaal zijn lading qmax uitdelen. De wis -waarden duiden aan welke klanten in eenzelfde subroute liggen. Het optellen van hun individuele goederenvraag moet dan kleiner zijn dan de laadcapaciteit van het voertuig. Elke klant ligt in een correcte subroute n X

wis = 1

s=1

∀i ∈ [1, n]

(2.4)

De routering moet zodanig opgesteld zijn dat elke klant juist eenmaal een wis -waarde heeft die 1 is. De klant is dan opgenomen in juist één subroute. Deze subroute loopt dan ook op een correcte manier terug naar het depot. In totaal betekent dit dat vanuit de klant op juist één manier het depot bereikt wordt via een subroute.

Figuur 2.12: Slechte routering want v2 en v4 niet opgenomen.

Deze wis -restricties dienen vooral om het zoekproces vlugger te sturen. Zodanig kan men vermijden dat er lussen voorkomen, dat voertuigen niet terugkeren, dat klanten niet in een correcte subroute zitten, ... In bovenstaand voorbeeld zijn v2 en v4 niet verbonden met het depot. De enige restrictie die dit zou duidelijk maken is dat het niet mogelijk is om tegelijk y4 > y2 en y2 > y4 te bekomen. Doordat voor geen enkele s-waarde w2s en w4s gelijk zijn aan 1, heeft het GA vlugger door dat er iets mis is met de xi -waarden van klant 2 of 4. Binnenkomst subroute (xi == n + 1) = (zi )+

∀i ∈ [1, n]

(2.5)

21


De klanten waarbij xi 6= n + 1 zijn niet de laatste klanten in een subroute. Voor hen wordt zi = 0 gesteld. Enkel voor de laatste klanten in een subroute, xi = n + 1, moet bepaald worden wat er gebeurd na binnenkomst in het depot. Dit kan het opstarten zijn van een nieuwe route of het eindigen van de Multi Tour. In beide gevallen zal de waarde van zi > 0. Voorafgaande subroute n X j=1

(zj == i) ≤ (xi )+

∀i ∈ [1, n]

(2.6)

Indien een subroute opgevolgd wordt door een andere subroute dan wordt via zi de link gemaakt tussen de laatste klant van de aankomende subroute en de eerste klant van de uitgaande subroute. De variabelen zi mogen dus enkel waarden aannemen van klanten die eerst liggen in een nieuwe subroute. Het kleiner of gelijk aan teken, houdt er rekening mee dat de eerste klant in de eerste subroute van een Multi Tour niet gelinkt wordt aan een vorige subroute. Volgorde service starttijden voor traject dat vanuit depot vertrekt

(xi )+ [yi − y i − g0 − t0i ] ≥ 0

∀i ∈ [1, n]

(2.7)

Wanneer een voertuig uit het depot vertrekt richting een klant i, xi > 0, dan moet het service starttijdstip aan klantzijde groter zijn dan het service starttijdstip aan de zijde van het depot vermeerderd met de laad- en reistijd.

22

Hoofdstuk 2. Probleem formulering Volgorde service starttijden voor traject dat vanuit klant vertrekt 1. for each i ∈ [1, n] do 2.

if (xi 6= n + 1) then

3. 4.

[yxi − gi − tixi − yi ] ≥ 0 else

5.

if (zi = n + 1)then

6.

[YT H − gi − ti

7.

− yi ] ≥ 0

else

8.

[y zi − gi − ti

9. 10.

n+1

n+1

− yi ] ≥ 0

end if end if

11. end for Via deze for-lus worden n voorwaarden opgesteld in verband met de volgorde van service starttijdstippen. Als xi 6= n + 1 dan worden trajecten beschouwd van klant naar klant. Het service starttijdstip van de laatste klant moet dan groter zijn dan dat van de eerste klant vermeerderd met de laad- en rusttijd. Als xi = n + 1 dan worden de voorwaarden opgesteld voor trajecten van een klant naar het depot. Het service starttijdstip van de volgende subroute moet dan groter zijn dan dat van de klant vermeerderd met de laad- en rusttijd. In het geval het de laatse subroute betreft van de Multi Tour, dan moet gekeken worden of deze subroute aankomt voor YT H .

Hoofdstuk 3

Het Iteratieve Multi Tour Opbouwen Verbeteringsalgoritme Het Iteratieve Multi Tour Opbouw- en Verbeteringsalgoritme (IMTOV) dat in deze thesis gebruikt wordt, is sterk gebaseerd op datgene uitgewerkt door Miguel Andres Figliozzi in zijn artikel “An iterative route construction and improvement algorithm for the vehicle routing problem with soft time windows” (6). De kern van het Iteratieve Multi Tour Opbouw- en Verbeteringsalgoritme bestaat uit een constructie algoritme waar Multi Tours sequentieel worden opgebouwd en verbeterd. De oplossingsmethode wordt opgedeeld in twee fasen: Multi Tour constructie en Multi Tour verbetering. De Multi Tour constructiefase gebruikt twee algoritmes: een ‘Ondersteunend Multi Tour Opbouwalgoritme’ Hr en een ‘Multi Tour Opbouwalgoritme’ Hc . De verbeteringsfase gebruikt het ‘Multi Tour Verbeteringsalgoritme’ Hv . Door gebruik te maken van een bottom up approach worden de algoritmes in de volgorde Hr , Hc en Hv ge¨ıntroduceerd. De m-files die de programmering in Matlab beschrijven, vindt u terug in de appendices B, C en D. De denkpistes die gevolgd worden in de constructiefase bij de algoritmes Hr en Hc zijn schatplichtig aan de algoritmes beschreven in het werk van Figliozzi. De beschrijvende paragrafen lijken sterk op deze in Figliozzi’s paper. Het grootste werk bestond er dan ook uit om deze algoritmes te programmeren én om te vormen tot het model uit deze paper met Multi Tours die herbervoorrading toepassen. Het Hc algoritme stond als pseudo algoritme uitgewerkt in Figliozzi’s paper. Het Hr algoritme daarentegen stond slechts beschreven in enkele regels, waardoor dit nog helemaal uitgewerkt diende te worden. In hoofdstuk 4 worden deze algoritmes nog verder uitgewerkt zodat ze voldoen aan de rij- en rusttijdreglementering. Het Multi Tour Verbeteringsalgoritme Hv is van eigen makelij. Dit algoritme verwijdert de beste Multi Tour uit de routering en kijkt na of een herroutering van de overige Multi Tour 23

Hoofdstuk 3. Het Iteratieve Multi Tour Opbouw- en Verbeteringsalgoritme

24

een betere oplossing oplevert. Als dit zo is, wordt deze routering bijgehouden. Indien niet, wordt de oude routering behouden. Vervolgens wordt dit algoritme herhaald waarbij nu één Multi Tour meer uit het verbeteringsproces gehouden wordt. Dit proces gaat zo door tot alle Multi Tours weerhouden worden van het verbeteringsproces.

3.1

Het Ondersteunend Multi Tour Opbouwalgoritme Hr

Dit algoritme is er op gericht een routering te vervolledigen op een vereenvoudigde manier. Gegeven de laatst bezochte klant in een partiële routering, een reeds bepaalde volgende te bezoeken klant en een verzameling van klanten die nog niet opgenomen zijn in een Multi Tour vervolledigt algoritme Hr de routering zodanig dat alle klanten bezocht worden. De gegenereerde routering voldoet aan alle restricties. In dit onderzoek is Hr (Routering, vi , vj , Qi , C, ∆ ) een ‘generalized nearest neighbor heuristic’ (GNNH). Deze GNNH heeft vijf inputparameters: Routering stelt de 4n variabelen voor die reeds een partiële routering beschrijven; vi stelt de laatste klant voor die reeds door Routering bezocht is; vj beschrijft de reeds bepaalde eerstvolgende klant die bezocht gaat worden; Qi stelt de hoeveelheid lading voor die overblijft in het voertuig na het bedienen van klant vi ; C is een verzameling die de klanten bevat die nog niet in een Multi Tour opgenomen zijn.

3.1.1

Klant vj opnemen in de routering

Het GNNH start eerst door vast te leggen dat na klant vi klant vj opgenomen wordt in Routering. Deze opvolging kan zich op drie manieren voltrekken. yj stelt hierbij het tijdstip voor waarop de service start bij een klant vj (j ∈ C), waarbij yj = max(aj , ej ). Hierdoor wordt verzekerd dat de service pas aanvat als het Service Time Window open is. In wat volgt wordt boven de horizontale lijn een overzicht gegeven van de nodige voorwaarden per scenario. Onder de lijn wordt op basis van dit scenario de toewijzing van de variabelen bepaald. Enkel de variabelen die een waarde verschillend van nul krijgen, worden weergegeven. De scenario’s worden doorlopen met een if-functie. Eerst wordt gekeken of er aan de voorwaarden voor a voldaan is, is dat niet het geval wordt er naar de voorwaarden voor b gekeken, is dat niet het geval dan wordt c uitgevoerd. a. Volgende klant in zelfde subroute Voorwaarden Qi − qj ≥ 0 yj ≤ lj

De vrachtwagen heeft nog voldoende voorraad na klant vi om klant vj te bedienen. De service bij klant vj kan starten voor het sluiten van het Time Window.

Hoofdstuk 3. Het Iteratieve Multi Tour Opbouw- en Verbeteringsalgoritme yj + gj + tjn+1 ≤ YT H

Toewijzingen xi = j yj Qi = Qi − qj C = C \ {vj }

25

Na het leveren bij klant vj is er nog voldoende tijd om tijdig het depot te bereiken alvorens de dagelijkse Time Horizon YT H overschreden wordt. Vanuit klant vi wordt rechtstreeks naar klant vj gereisd. Het tijdstip waarop de service start bij klant vj wordt vastgelegd. De vraag van klant vj wordt verminderd van de lading van de vrachtwagen. vj wordt verwijderd uit de verzameling van ongerouteerde klanten.

Als scenario a niet geldig is, wordt gekeken naar de voorwaarden van scenario b. b. Volgende klant in nieuwe subroute na herbevoorrading Voorwaarden Qi − qj ≤ 0 yj ≤ lj

yj + gj + tjn+1 ≤ YT H

Toewijzingen xi = n + 1 yj yj zi = j Qi = qmax − qj

C = C \ {vj }

De vrachtwagen heeft niet voldoende voorraad meer om klant vj te bevoorraden. De service bij klant vj kan starten voor het sluiten van het Time Window. yj wordt hier berekend rekening houdend met een passage langs het depot. Na het leveren bij klant vj is er nog voldoende tijd om tijdig het depot te bereiken alvorens de dagelijkse Time Horizon YT H overschreden wordt. Vanuit klant vi wordt naar het depot gereisd om te herbevoorraden. Het tijdstip waarop in het depot de service start om de subroute naar klant vj voor te bereiden, wordt vastgelegd. Het tijdstip waarop de service start bij klant vj wordt vastgelegd. De subroute komt binnen in het depot na klant vi , maar vertrekt na herbevoorrading richting klant vj . De heraangevulde voorraad qmax wordt verminderd met de vraag van klant vj . Het heraanvullen tot qmax is afhankelijk van de resterende hoeveelheid lading bij binnenkomst in het depot. vj wordt verwijderd uit de verzameling van ongerouteerde klanten.


26

Als scenario b niet geldig is, wordt overgaan op scenario c. c. Volgende klant wordt door nieuw voertuig bediend in een nieuwe Multi Tour Hier geen voorwaarden omdat alle klanten feasible moeten zijn wat lading en bereikbaarheid betreft. Dit betekent dat het voor elke klant mogelijk moet zijn deze klant te bereiken binnen zijn Time Window, een hoeveelheid af te leveren die kleiner is dan qmax , en vervolgens tijdig terug te kunnen keren naar het depot alvorens YT H overschreden wordt. Toewijzingen xi = n + 1 yj yj zi = n + 1 Qi = qmax − qj C = C \ {vj }

3.1.2

Vanuit klant vi wordt naar het depot gereisd om de Multi Tour te beëindigen. Het tijdstip waarop in het depot de service start om de nieuwe Multi Tour naar klant vj voor te bereiden, wordt vastgelegd. Het tijdstip waarop de service start bij klant vj wordt vastgelegd. De subroute komt binnen in het depot na klant vi en de Multi Tour wordt beëindigd. De laadcapaciteit qmax wordt verminderd met de vraag van klant vj . vj wordt verwijderd uit de verzameling van ongerouteerde klanten.

Routering vervolledigen met Nearest Neighbor algoritme

Dat klant vj de eerstvolgende klant wordt in de routering, ligt vast via de inputparameters. De rest van de ongerouteerde klanten in C moet nu nog bezocht worden. De eerstvolgende klant wordt gevonden door de ongerouteerde klant te vinden met de kleinste gegeneraliseerde kost. Voor elke volgende iteratie zoekt de heuristiek naar de volgende klant onder de ongerouteerde klanten met de kleinste gegeneraliseerde kost. De gegeneraliseerde kostenfunctie die gebruikt wordt in dit algoritme houdt rekening met: • nabijheid in afstand • nabijheid in reistijd • de resterende lading in het voertuig • de dringendheid alvorens het Service Time Windows sluit • het inzetten van een nieuw voertuig wanneer de volgende klant onbereikbaar is. De waarde voor de gegeneraliseerde kost g(∆, i, j) om na klant vi klant vj op te nemen in de routering is afhankelijk van hoe klant vj bereikt wordt. Wederom wordt gebruik gemaakt


27

van de hierboven beschreven scenario’s a, b en c. Indien scenario a mogelijk is dan stelt men g = ga . Is dit niet het geval dan wordt nagegaan of scenario b mogelijk is zodat g = gb . Als beide voorgaande scenario’s niet kunnen toegepast worden dan stelt men g = gc . ga (∆, i, j) = δ1 dij + δ2 (yj − yi ) + δ3 (lj − aj ) + δ4 (Qi − qj ) gb (∆, i, j) = δ1 (di n+1 + d0j ) + δ2 (yj − yi ) + δ3 (lj − aj ) + δ4 (qmax − qj ) gc (∆, i, j) = δ5 + δ1 (di n+1 + d0j ) + δ2 [(yj − y j ) + (gi + ti n+1 )] + δ3 (lj − aj ) + δ4 (qmax − qj ) De parameter δ1 bepaalt het gewicht toegekend aan de afstand tussen klant vi en klant vj . Parameter δ2 houdt rekening met de tijdspanne tussen het aanvangen van de service bij klant vi en het eerst mogelijke tijdstip waarop de service kan starten bij klant vj . De paper van M. M. Solomon (14) volgend, geeft δ3 gewicht aan de dringendheid waarmee klant vj bediend dient te worden. Deze dringendheid wordt uitgedrukt door de tijdspanne tussen de aankomsttijd aj en het laatst mogelijke tijdstip waarop bediend kan worden lj . In deze zelfde paper van Solomon wordt gesteld dat δ1 + δ2 + δ3 = 1. Parameter δ4 houdt rekening met de overblijvende lading in het voertuig na het bedienen van klant vj . Navraag bij Miguel Figliozzi leerde dat deze δ4 van dezelfde grootorde is als de voorgaande δ-waarden. Wanneer een nieuwe Multi Tour opgestart wordt voor klant vj dan wordt via δ5 een kost gerekend voor het nieuwe voertuig.

3.1.3

Algoritme Hr (Routering, vi , vj , Qi , C, ∆)

De geprogrammeerde m-files voor dit algoritme zijn opgenomen onder appendix B. Een eenvoudige voorstelling in pseudo algoritme wordt hieronder weergegeven. Gegevens: ∆ Routering Scenario vi vj Qi C

Set van de vijf δ-gewichten. Een vector met reeds partieel toegekende 4n variabelen: xi , y i , yi en zi . Functie die nakijkt volgens welk scenario a, b of c een klant kan toegevoegd worden aan de routering. Laatst bediende klant. Eerstvolgende te bedienen klant. De voorraad in het voertuig na levering aan klant vi . Verzameling van ongerouteerde klanten.

Hoofdstuk 3. Het Iteratieve Multi Tour Opbouw- en Verbeteringsalgoritme Start Hr (Routering, vi , vj , Qi , C, ∆) 1. scenario ← Scenario(vi , vj , Qi ) 2. Routering ← {Routering ∪ vj (scenario) } 3. Qi ← Qi (scenario) − qj 4. C ← C \ vj 5. vi ← vj 6. while (C 6= ∅) do 7.

besteW aarde ← ∞

8.

besteKlant ← ∞

9.

for each vj ∈ C

10.

scenario∗ ← Scenario(vi , vj , Qi )

11.

if (g(vi , vj , scenario∗ ) ≤ besteW aarde)

12.

besteKlant ← vj

13.

besteW aarde ← gj

14.

scenario ← scenario∗

15.

q ← qj

16.

end if

17.

end for

18.

Routering ← {Routering ∪ besteKlant(scenario) }

19.

Qi ← Qi (scenario) − q

20.

C ← C \ besteKlant

21.

vi ← besteKlant

22. end while 23. return Routering

28


29

In regels 1-5 wordt vj in de routering opgenomen, zoals beschreven in paragraaf 3.1.1. De waarde scenario legt vast of de routering gebeurd via scenario a, b of c. Deze waarde bepaalt dan mee hoe Qi en Routering hun waarden toegewezen krijgen. In regels 6-22 wordt beschreven hoe onder de niet-gerouteerde klanten gezocht wordt naar de klant met de kleinste g-waarde. Deze klant, genoteerd als besteKlant wordt dan als eerstvolgende gerouteerd. Als uiteindelijke output wordt de totale Routering gegeven.

3.2

Het Multi Tour Opbouwalgoritme Hc

In dit algoritme worden Multi Tours sequentieel opgebouwd. Gegeven een partiële routering en een verzameling ongerouteerde klanten zal dit algoritme op zoek gaan naar de Multi Tour met de kleinste kost. Hierbij maakt Hc gebruik van de Klantordenfunctie w(vi , C, W ). Deze functie genereert een verzameling van W ongerouteerde klanten die de kleinste gegeneraliseerde kost g(∆, vi , vj ) hebben als vj als eerstvolgende in de routering opgenomen wordt. De volledige routering wordt voor elk van de W klanten afgewerkt via het Ondersteunend Routeopbouwalgoritme Hr . Zodoende kan men deze ‘eenvoudig’ afgewerkte routes vergelijken op hun kost.

3.2.1

De Klantordenfunctie w(vi , C, W )

Deze functie heeft als input de laatst gerouteerde knoop vi , de verzameling C van ongerouteerde klanten en de waarde W die aangeeft hoeveel klantknopen gegenereerd dienen te worden als output. Zoals in vorige paragraaf wordt wederom voor elke ongerouteerde knoop gekeken wat de gegeneraliseerde kost g is om deze klant als eerstvolgende te routeren. Voor alle ongerouteerde klanten uit C wordt deze waarde bijgehouden. Op basis daarvan wordt een ranking gemaakt volgens deze gegeneraliseerde kosten. De W klantknopen met de minste kost vormen de output van deze functie. Indien er minder dan W klanten aanwezig zijn in verzameling C, dan worden er slechts | C | klanten als output gegeven. De geprogrammeerde m-file om deze functie in Matlab op te roepen, is terug te vinden in de appendices onder sectie C.2.

3.2.2

Routering met behulp van Hr

De hierboven beschreven w-functie selecteert dus de knopen die volgens de generaliserende kostenfunctie g het meest geschikt zijn om als volgende klant gerouteerd te worden. Voor elk van deze min(W, | C |) knopen vervolledigt men de routering waarbij elke w-knoop eens als eerstvolgende knoop na de partiële Routering gerouteerd wordt. De resterende klanten na de routering van zo’n w-knoop worden dan gerouteerd met het Ondersteunend Multi Tour Opbouwalgoritme Hr (Routering, vi , vj , Qi , C, ∆ ) dat het principe van nearest neighbor toepast met behulp van de generalisernde kostenfunctie g.


30

Er wordt dus een totale routering bekomen voor elke w-knoop die bestaat uit de reeds partiële Routering die als input gegeven is, aangevuld met de routering van de w-knoop. Dit geheel wordt dan vervolledigd met behulp van het Ondersteunend Multi Tour Opbouwalgoritme Hr . Zodoende bekomt men voor elk van deze w-knooppunten een volledige routering waarvan een totale kostprijs berekend kan worden. De w-knoop waarvan de routering de kleinste routeringskost heeft, wordt dan geselecteerd om als eerstvolgende in de initiële Routering opgenomen te worden, waarna deze w-knoop verwijderd wordt uit de verzameling C van ongerouteerde klanten. (Opgelet, de totale routeringskost 6= generaliserende kost). De totale routeringskost berekent men door rekening te houden met volgende kosten: • cv , de dagelijkse kost per voertuig. • cv , de kost per afgelegde kilometer. • cv , de kost per minuut dat een Multi Tour duurt. Dit principe om de beste klant te zoeken wordt toegepast tot de verzameling C van ongerouteerde klanten leeg is. Dan zullen alle klanten opgenomen zijn in de routering.

3.2.3

Algoritme Hc (Wi , Routeringi , vi , Qi , Ci )

De geprogrammeerde m-files die de werking van dit algoritme verzekeren, kunnen teruggevonden worden in appendix C. Hieronder volgt een eenvoudige voorstelling als pseudo algoritme. Gegevens: Ω n Routeringskost W Ci Qi

Set van ∆’s die elk vijf δ-gewichten beschrijven. Het aantal klanten. Functie die de kost berekent van een totale routering. Parameter die aangeeft hoeveel knopen de functie w zal genereren. Verzameling van ongerouteerde klanten. Initiële hoeveelheid lading in het voertuig.

Hoofdstuk 3. Het Iteratieve Multi Tour Opbouw- en Verbeteringsalgoritme Start Hc (Wi , Routeringi , vi , Qi , Ci ) 1. P rijs ← ∞ 2. for each ∆ ∈ Ω 3.

besteOpvolger ← 0

4.

Q ← Qi

5.

C ← Ci

6.

start ← vi

7.

while(C 6= ∅)

8.

W = min(W, | C |)

9.

C ∗ ← w(start, C, W )

10.

laagsteKost ← ∞

11.

for each vj ∈ C ∗

12.

if [Routeringskost(Hr (Routering, start, vj , Q, C, ∆ ))) < laagsteKost]

13.

laagsteKost ←Routeringskost(Hr (Routering, start, vj , Q, C, ∆ )))

14.

besteOpvolger ← vj

15.

end if

16.

end for

17.

C ← C \ {besteOpvolger}

18.

Routering ∗ ← Routeringi ∪ {besteOpvolger(scenario)}

19.

start ← besteOpvolger

20.

Q ← Q(scenario) − qj

21.

end while

22.

if (Routeringskost(Routering ∗ ) < P rijs)

23.

P rijs ← Routeringskost(Routering ∗ )

24.

Routering ← Routering ∗

25. end for 26. return Routering

31


32

Op regel 2 start een f or-lus die ervoor zorgt dat er meerdere ∆’s doorlopen worden, zodanig dat voor elke iteratie van deze lus de Routering gebeurt met een verschillende generaliserende functie g. Vervolgens zorgen regels 3-6 ervoor dat voor elke nieuwe set δ-waarden de initiële condities terug hersteld worden. De while-lus in regels 7-21 beschrijft de routeringsprocedure zoals ze in voorgaande paragrafen beschreven werd. Telkenmale genereert de w-functie een aantal klanten die het best geschikt zijn om als volgende klant te routeren. Afhankelijk van de totale routekost die routering met Hr oplevert, wordt dan beslist welke vj men als eerstvolgende routeert. De input data kunnen een lege Routering bevatten waarbij startknoop vi gelijkgesteld wordt aan het depot en de vrachtwagen leeg verondersteld wordt. In dat geval wordt van ’niets’ een hele routering opgebouwd. Het is echter ook mogelijk, zoals zal blijken in sectie 3.3, dat Routering reeds een gedeeltelijke routering bevat en dat Hc deze verder moet uitbouwen.

3.3

Het Multi Tour Verbeteringsalgoritme Hv

Het Multi Tour Verbeteringsalgoritme is er op gericht de minst goede Multi Tours te verbeteren. Met behulp van de Multi Tour Ordenfunctie k worden de Multi Tours geordend volgens bepaalde criteria. De beste Multi Tour behoudt men. De klanten die in de overige Multi Tours zitten, worden dan opnieuw gerouteerd met algoritme Hc . Is deze herroutering goedkoper dan de oorspronkelijke routering, dan wordt deze routering behouden. Anders wordt er verder gegaan met de oorspronkelijke routering. In elke volgende iteratie worden de Multi Tours wederom gerangschikt door de k -functie. Telkens weerhoudt men één Multi Tour meer van het herrouteringsproces. In de eerste iteratie wordt er dus getracht r-1 Multi Tours te herrouteren (met r het aantal Multi Tours in de routering), in de tweede iteratie r-2 (met r het aantal Multi Tours in die routering), ... Dit proces gaat door tot men uiteindelijk één Multi Tour overhoudt. Dan stop het algoritme. Het uiteindelijke doel is om door de verschillende iteraties een goedkopere routering te bekomen. De afbeelding hieronder weergegeven beeldt de werking van het algoritme uit. Onder de afbeelding wordt het proces nog eens beschreven.


33

Figuur 3.1: Voorbeeld van de werking van Hv . Multi Tours in rood weergegeven zijn niet meer beschikbaar voor herroutering.

Stel dat er 6 Multi Tours zijn: a, b, c, d, e & f. Deze worden door de k-functie geordend volgens bepaalde criteria. Het resultaat wordt weergegeven in box 2. De beste presterende Multi Tour is e. Deze wordt uit het herrouteringsproces gehouden (in rood weergegeven). De overige 5 Multi Tours worden wel geherrouteerd wat resulteert in box 3. Nu zijn er twee mogelijkheden: als de nieuwe routering goedkoper is dan de oorspronkelijke wordt lijn a-lijn gekozen, in het andere geval lijn b. Na deze keuze start een nieuwe iteratie van het Hv algoritme. De k-functie ordent wederom de niet-rode Multi Tours. Na deze ordening wordt de best presterende Multi Tour ook rood gemaakt, wat dus een tweede rode Multi Tour oplevert. De vier overige Multi Tours worden geherrouteerd... waarbij de cyclus dus opnieuw doorlopen wordt. Bij de overgang van 5b naar 6b zien we dat het herrouteringsproces zodanig verlopen is dat er een Multi Tour verdwenen is. Dit houdt in dat er een vrachtwagen minder moet rijden. In de overgang erna zal dan moeten blijken of deze herroutering goedkoper is dan de vorige.

3.3.1

De Multi Tour Ordenfunctie k(Routering − R)

De functie heeft als input de routering ‘Routering’ waarvan de verzameling niet-herrouteerbare klanten R verminderd wordt. Uit de Multi Tours die de overige klanten vormen wordt dan


34

een ordening gemaakt volgens bepaalde criteria. De beste presterende Multi Tour wordt als output terug gegeven. Zoals hierboven vermeld is, worden de Multi Tours geordend volgens bepaalde criteria. Deze criteria moeten weergeven dat een Multi Tour nog mogelijkheden heeft tot verbetering. Volgende criteria worden beschouwd: • routeduur • aantal klanten in een Multi Tour •

P (ladingsoverschot in voertuig na subroute)/klanten in Multi Tour

• (routeafstand)−1 • geografische nabijheid Uit talrijke experimenten bleek dat de beste resultaten bekomen werden met routeduur. Vrij logisch, omdat als een lege vrachtwagen door herbevoorrading terug de baan op kan, is het best dat een Multi Tour zolang mogelijk klanten blijft bevoorraden. Hierdoor kan een vrachtwagen die al na 1uur leveren leeg is, toch nog terug de baan op. Doel is dan ook de routeduur zo lang mogelijk te maken, zodanig dat het gebruik van extra vrachtwagens vermeden kan worden. Lange routes hebben een hogere routeduurkost, maar door de g-functie wordt verzekerd dat de duur van de route nuttig besteed wordt. Een rangschikking waarbij rekening gehouden wordt met de geografische middelpunten van de Multi Tours leek mij niet geschikt. Multi Tours kunnen zodanig opgesteld zijn dat één bepaalde subroute zich afspeelt in één geografische zone en de andere subroute van dezelfde Multi Tour zich in een totaal verschillende geografische zone afspeelt. Het geografische middelpunt van deze twee subroutes levert dan niet veel informatie op. Ordenen volgens omgekeerde routeafstand wordt eveneens niet toegepast. Een zeer functionele Multi Tour die enkele ‘verre’ klanten heeft, zou dan steeds in het herrouteringsproces vallen, hoewel deze Multi Tour heel efficiënt werkt.

3.3.2

Algoritme Hv (Routering, W )

De m-files ‘k.m’ en ‘Hv.m’ die instaan voor het Multi Tour Verbeteringsalgoritme zijn terug te vinden in appendix D.


35

Hieronder volgt een eenvoudige voorstelling als pseudo algoritme. Gegevens: Routering n Routeringskost W C R | Routering | S

Een volledig opgestelde Routering. Het aantal klanten. Functie die de kost berekent van een totale routering. Parameter die aangeeft hoeveel knopen de functie w zal genereren. Verzameling van klanten geschikt voor herroutering. Verzameling van Multi Tours die niet meer voor herroutering in aanmerking komen. Aantal Multi Tours in de routering Routering. Multi Tour die best presteert.

Start Hv (Routering, W ) 1. C ← {1, ..., n} 2. Routering ∗ ← Routering 3. P rijs ← Routeringskost(Routering) 4. R ← {} 5. while (| Routering \ R |> 1) 6.

S ← k(Routering \ R)

7.

C ←C \S

8.

R←R∪S

9.

Routering ∗ ← Hc (W, Routering, 0, 0, C)

10.

if (Routeringskost(Routering ∗ ) < P rijs)

11.

P rijs ← Routeringskost(Routering ∗ )

12.

Routerings ← Routerings∗

13.

end if

14. end while In regel 1 zijn alle klanten nog beschikbaar voor herroutering. De while-lus blijft lopen zolang er meer dan één Multi Tour geherrouteerd kan worden. Eén Mulit Tour wordt dus niet


36

meer geherrouteerd. In regel 6 zal de output van de k-functie de Multi Tour zijn die het best presteert op de criteria. In regel 7 worden de klanten uit deze Multi Tour vrijgesteld van herroutering. Regel 9 zorgt ervoor dat de klanten die nog in aanmerking komen voor herroutering opnieuw in het Hc -algoritme gestoken worden. De if -voorwaarde kijkt dan na of de herroutering een goedkoper resultaat gegenereerd heeft. Zoja, dan wordt de herroutering definitief aangepast en start een volgende run van de while-lus.

3.4

Resultaten

Figliozzi past zijn model toe op de databanken van Solomon (14). Deze databanken bevatten 6 soorten problemen waarbij gevarieerd wordt met Time Windows en met de klantlocaties (Random verspreide tegenover klanten die in cluster liggen). Solomons model minimaliseerde enkel de afstand. Het model in deze thesis met tijdsafhankelijke reistijden, Multi Tours en een andere kostenfunctie tracht andere doelstellingen te bereiken. Vergelijkingen zijn dan ook zeer moeilijk te maken. Bijvoorbeeld, het model in deze thesis maakt herbevoorrading mogelijk, daarom kan de maximumcapaciteit van de vrachtwagens kleiner gekozen worden dan in Solomons model. Maar hoe klein? Hoe kunnen de tijdstipafhankelijke reistijden in dit model vergeleken worden met de niet-tijdstipafhankelijke reistijden in Solomons werk? Daarom wordt ervoor gekozen een eigen, levensecht voorbeeld uit te werken in volgende paragrafen, gebaseerd op het distributienet van winkelketen Colruyt ®.

3.4.1

Gegevens

Klantlocaties Er wordt gekozen voor de winkelketen Colruyt. Deze succesvolle onderneming heeft vestigingen in heel het land. Om de oplossing overzichtelijk te houden wordt gekozen voor de winkels in Oost- en West-Vlaanderen. Deze 55 winkels worden in onderstaande afbeelding weergegeven.


37

Figuur 3.2: De verspreiding van de winkels van Colruyt in Oost- en West-Vlaanderen.

Colruyt beschikt over drie distributiecentra in België die gelegen zijn in Halle, Gellingen en Beersel. Deze drie centra liggen rond Brussel, zodat ze centraal genoeg liggen om het hele land te bevoorraden. Omdat dit een Single Depot Vehicle Routing Problem betreft wordt er gekozen voor één centrum, namelijk dat in Gellingen. Deze depot is voornamelijk gespecialiseerd in de verdeling van allerlei soorten dranken. Het depot wordt weergegeven op bovenstaande afbeelding door het logo van Colruyt. De exacte posities van de winkels werden achterhaald via de Belgische Lambert 72-coördinaten die beschikbaar waren via de website http://geo-vlaanderen.agiv.be/geo-vlaanderen/ kleurenortho/ (1). Time Windows Colruyt herbevoorraadt zijn winkels voornamelijk ’s nachts. De wegen zijn dan rustiger en files kunnen zo vermeden worden. In winkels in een stedelijke omgeving wordt wel overdag geleverd om de buurtbewoners geen hinder te bezorgen (2). In deze opgave wordt er wel vanuit gegaan dat er overdag geleverd kan worden. Redenen voor Time Windows zijn o.a. strikte levertijden in stedelijke omgevingen, leveren voor 10u, leveren na 16u, drukte spreiden over heel de dag, ... Er wordt in deze opdracht


38

vanuit gegaan dat de Service Time Windows zeer gevarieerd zijn, zoals blijkt uit tabel 3.5. Er wordt nagekeken of de Time Windows wel feasible zijn. Het moet dus mogelijk zijn om met een vrachtwagen de klant te bedienen binnen zijn Time Window en tijdig terug te kunnen zijn in het depot alvorens dit sluit op tijdstip YT H . Het Time Window mag dus niet te vroeg sluiten, of te laat openen. Voor het depot geldt Y0 = 4200 en YT H = 1005. Vraag De vraag van de klanten wordt random bepaald. Deze hoeveelheden zijn terug te vinden in tabel 3.5. De waarde qmax hangt nauw samen met de qi -waarden. Om het principe van Multi Tours te benadrukken, wordt de waarde van de maximale laadcapaciteit niet te groot genomen, namelijk qmax = 50.

Parameters Voor de δ-waarden heb ik contact opgenomen met M. Figliozzi om te zien welke waarden ik als richtlijn kan gebruiken. Zoals reeds verteld moet δ1 + δ2 + δ3 = 1 en is δ4 van dezelfde orde als de voorgaande δ’s. δ5 daarentegen is hoog, want een extra voertuig in de routering tracht men te vermijden. Het algoritme Hc is zondanig opgesteld dat het meermaals doorlopen wordt voor verschillende ∆-sets. De kostenfunctie wordt bepaald door drie parameters. Hiervoor heb ik contact opgenomen met de dienst Logistiek van Colruyt. De heer Guy Walravens liet mij weten welke kostparameters ze hanteren bij Colruyt. • Kost per kilometer: cd = e 1, 5/km • Bruto uurloon chauffeur: ct = (e 10, 58+ e 1, 09)/uur = e 0, 1945/min • Dagelijkse kost om vrachtwagen in te zetten: cv = e 470 De e 1, 09 in de loonkost bedraagt de ARAB-vergoeding. Deze wordt uitgekeerd aan nietsedentaire werknemers om hen tegemoet te komen in kosten die ze maken doordat ze niet beschikken over sanitair en eetgelegenheid (wasplaats, refters, toiletten, dranken, ...). De W -waarde bepaalt hoe uitgebreid de algoritmes te werk gaan in hun zoektocht naar de volgende klant om te routeren. De invloed van deze W wordt weergegeven in de oplossingen.

39


ei li qi ei li qi ei li qi ei li qi ei li qi

1

2

3

4

5

6

7

8

9

10

11

400 525 16

800 900 10

650 655 8

700 1000 3

820 840 10

500 600 5

500 800 12

420 600 50

420 905 6

420 1005 12

620 1005 14

12

13

14

15

16

17

18

19

20

21

22

420 1005 21

420 705 7

820 1005 14

420 605 3

420 1005 9

400 1005 8

720 1005 7

800 1005 16

420 905 13

420 1005 18

420 1005 11

23

24

25

26

27

28

29

30

31

32

33

420 1005 11

720 1005 9

720 780 9

620 905 15

420 1005 8

420 1005 19

420 1005 9

420 1005 6

420 1005 1

420 1005 12

420 1005 4

34

35

36

37

38

39

40

41

42

43

44

520 1005 4

420 705 9

750 1005 19

420 705 19

420 1005 12

420 905 41

420 1005 18

420 600 22

420 680 6

420 1005 21

700 1000 30

45

46

47

48

49

50

51

52

53

54

55

420 605 12

420 600 32

420 1000 46

440 1005 12

320 1005 14

520 905 21

620 1005 7

420 805 4

420 900 13

500 600 9

420 800 8

Tabel 3.5: Overzicht van de Time Windows en hoeveelheid vraag voor de 55 winkels.

40


3.4.2

Oplossingen

Nu worden er via Hc oplossingen gegenereerd voor verschillende W -waarden. Vervolgens wordt getracht deze oplossingen te verbeteren door middel van Hv (Hc , W )). Dit verbeteringsalgoritme wordt toegepast voor een W -waarde van 6 omdat uit de Hv -runs bleek dat dit goede resultaten levert. Onder de kosten van de routering staat de tijd weergegeven die nodig is om de oplossing te bekomen. De runs werden uitgevoerd op een MacBook Pro met 2.2 GHz Intel Core 2 Duo processor. W

1

3

5

7

9

Hc (W )

e 13812 (0’47”)

e 12523 (2’09”)

e 12350 (3’32”)

e 12316 (4’58”)

e 12477 (6’22”)

Hv (Hc (W ), 6)

e 12490 (4’06”)

e 12374 (6’49”)

e 12322 (7’06”)

e 12275 (7’17”)

e 12265 (7’03”)

Tabel 3.6: Kosten van de routeringen Hc (W ), en hun verbeteringen Hv (W )

De beste oplossing wordt bekomen na verbetering van de herroutering van Hc (9). Als W groter wordt, wordt er uitgebreider gezocht, en stijgt de looptijd van het algoritme. Toch valt te zien aan de kostfunctie dat een hogere W -waarde niet steeds een betere oplossing oplevert. Voor runs op andere routeringsproblemen met 50-100 klanten bleek steeds dat een W -waarde van 5 tot 7 de beste resultaten levert. Bij Hc (1) wordt slechts 1 w-knoop verder onderzocht. Deze knoop zal dan steeds gekozen worden. Dit komt dus neer op de oplossing met het Nearest Neighbor algoritme. De waarden bekomen met hogere W -waarden leveren dus duidelijk betere resultaten op. Details van de beste oplossing Hv (Hc (9), 6)worden afgebeeld in volgende figuur. Het Collectcommando geeft een matrixvoorstelling van de Multi Tours. Elke rij stelt een Multi Tour voor. Een grafische voorstelling van de routering volgt in de figuur erna.


Figuur 3.3: Printscreen van de oplossing in Matlab.

41


Figuur 3.4: Grafische voorstelling van de routering.

42


43

Door de zeer variërende Time Windows is de routering zeer hectisch en worden er veel kilometers gereden. Routeringen met veel Multi Tours na Hc hebben een grotere kans om met flinke stappen te verbeteren tijdens Hv omdat de kans groter is dat twee of meerdere Multi Tours versmelten tot één Multi Tour.

Hoofdstuk 4

Model onderworpen aan rij- en rusttijdreglementering 4.1 4.1.1

Rij-en rusttijden Doel van de rij- en rusttijden

De invoering van de digitale tachograaf baseert zich op vier doelstellingen: • de verkeersveiligheid verhogen • de arbeidsvoorwaarden van de bestuurders verbeteren • de eerlijke concurrentie bevorderen • het beheer van de ondernemingen vereenvoudigen

4.1.2

Rij- en rusttijdreglementering

De rij- en rusttijdreglementering is door de Europese Unie gewijzigd op 15 maart 2006. Deze wetswijziging is terug te vinden in Verordening (EG) nr. 561/2006 van het Europees Parlement en de Raad (11). Deze verordening trad in werking op 11 april 2007. Hieronder wordt de wetgeving weergegeven zoals beschreven op de site van Digitach, http: //www.digitach.be/NL/PDF/presn.pdf, opgericht door de Federale Overheidsdienst Mobiliteit en Vervoer (5). De bepalingen inzake rij- en rusttijden van Verordening (EG) 561/2006 zijn van toepassing op iedere verplaatsing die geheel of gedeeltelijk plaatsvindt op wegen die voor openbaar gebruik toegankelijk zijn, zowel in lege als in geladen toestand door een voertuig bestemd voor: • vervoer van goederen waarbij de toegestane maximummassa van de voertuigen, aanhangwagens en opleggers inbegrepen, meer dan 3,5 ton bedraagt. 44

Hoofdstuk 4. Model onderworpen aan rij- en rusttijdreglementering

45

• vervoer van personen door voertuigen die zijn gebouwd of permanent zijn toegerust om meer dan 9 personen, bestuurder inbegrepen, te kunnen vervoeren en daartoe bestemd zijn. Dagelijkse rijtijd Dagelijkse rijtijd is de totale bij elkaar opgetelde rijtijd tussen het einde van de ene dagelijkse rusttijd en het begin van een volgende dagelijkse rusttijd of tussen een dagelijkse rusttijd en een wekelijkse rusttijd. Deze mag niet meer bedragen dan 9 uur. Tweemaal per week mag deze verlengd worden tot 10 uur. Vervolgens zijn er ook nog restricties op de wekelijkse en tweewekelijkse rijtijd. Deze zijn niet van toepassing op dit VRP probleem met een Time Horizon van één werkdag. Daarom zijn deze niet opgenomen in deze paragraaf. Onderbreking van de rijtijd Na een rijperiode van 4 uur 30 minuten moet de chauffeur een aaneengesloten onderbreking van tenminste 45 minuten in acht nemen, tenzij hij aan een rusttijd begint. Rijperiode: De bij elkaar opgetelde rijtijden vanaf het ogenblik dat een bestuurder begint te rijden na een rusttijd of een onderbreking totdat hij een rusttijd of onderbreking neemt. Een rijperiode kan al dan niet onderbroken worden.

Onderbreking: Elke periode waarin de bestuurder niet mag rijden en ook geen andere werkzaamheden mag verrichten en die uitsluitend dient om te rusten. Dit betekent dus dat laden en lossen niet als onderbreking beschouwd worden.

Rusttijd: Elke periode waarin de bestuurder zijn dagtaak gedaan is, en het voertuig voor een langere tijd aan de kant laat. Een werkdag start na een russtijd en eindigt met een rusttijd.

Hieronder worden enkele correcte werkschema’s afgebeeld. Wanneer een onderbreking 45 minuten of langer duurt, vindt er na deze onderbreking een ‘reset’ plaats. De rijduur wordt terug op 0 minuten geplaatst. Na deze ‘reset’ kan er in principe terug 4 uur en 30 minuten


46

ononderbroken gereden worden (op voorwaarde dat de 9 uur dagelijkse rijtijd niet overschreden wordt.) Zo’n ‘reset’ wordt aangeduid door een dikke, rode streep in de afbeeldingen hieronder. Tussen elke twee rode strepen mag er maximaal 4 uur en 30 minuten rijtijd zitten.

Figuur 4.1: Voorbeeld van enkele reguliere rij- en rusttijden met gehele onderbreking.

De aaneengesloten onderbreking van 45 minuten kan evenwel vervangen worden door een eerste onderbreking van TEN MINSTE 15 minuten, gevolgd door een tweede onderbreking van TEN MINSTE 30 minuten. Beide onderbrekingen moeten elk zodanig tijdens de periode worden ingelast dat na een rij-periode van 4 uur 30 een onderbreking van ten minste 45 minuten in acht genomen is. Bij de opsplitsing in twee onderbrekingen moet de laatste onderbreking zeker langer duren dan 30 minuten. Wanneer de eerste onderbreking 30 minuten zou bedragen (correct, want langer dan 15 minuten) dan moet de tweede onderbreking nog steeds 30 minuten bedragen (correct, want langer dan 30 minuten). De gecumuleerde onderbreking bedraagt dan wel 60 minuten. Wederom volgen nu enkele correcte werkschema’s. (Gecumuleerde) ‘resets’ worden wederom met een dikke, rode streep aangegeven.


47

Figuur 4.2: Voorbeeld van enkele reguliere rij- en rusttijden met gesplitste onderbreking.

Hieronder volgen nog enkele niet-reguliere werkschema’s. De fouten in het schema zijn de volgende: 1. De tweede onderbreking is 25 minuten te kort. 2. De eerste twee rijperiodes overschrijden de 4 uur en 30 minuten alvorens de tweede onderbreking aanbreekt. 3. De twee rijperiodes na de laatste reset overschrijden de 4 uur en 30 minuten met hun gecumuleerde waarde van 7 uur en 30 minuten. 4. Er is geen tweede opgesplitste onderbreking die minstens 30 minuten bedraagt.

Figuur 4.3: Voorbeeld van enkele NIET-reguliere rij- en rusttijden.


4.1.3

48

Tachograaf

De naleving van de wetgeving wordt gecontroleerd door middel van een digitale tachograaf. Dit toestel met de grootte van een autoradio is verbonden met een bewegingsopnemer. Het is uitgerust met een geheugen, een leesvenster, een connector voor gegevensoverbrenging, twee kaartenlezers en een printer. Het toestel werkt in combinatie met digitale tachograafkaarten. Het registreert de rij- en rusttijden van de bestuurder, die ogenblikkelijk in het leesvenster af te lezen zijn. Drie geheime sleutels verzekeren de beveiliging van de registratie en de bewaring van de gegevens. Elke digitale tachograaf is volkomen interoperabel. Alle tachograafkaarten kunnen in elk apparaat gebruikt worden, wat ook het merk ervan weze. De tachograaf dient tot het registreren van verschillende gegevens: rij- en rusttijden, snelheid van het voertuig en afgelegde afstand. De gegevens worden opgeslagen in het geheugen van het apparaat; dit geheugen bewaart de gegevens van tenminste 365 kalenderdagen met betrekking tot het voertuig en alle opeenvolgende bestuurders van dit voertuig tijdens deze periode. De bestuurderskaart bewaart de gegevens betreffende de rij- en rusttijden van de chauffeur over een minimale periode van 28 dagen. De digitale tachograaf bevat eveneens een snelheidsmeter die toelaat de door het voertuig ontwikkelde snelheid per seconde en over de laatste 24 uur te registreren (deze meting kan van belang zijn voor, bijvoorbeeld, een ongevalanalyse) evenals de registratie van de overschrijding gedurende méér dan één minuut van de instelsnelheid van de snelheidsbegrenzer. Het vervoersbedrijf kan, met behulp van de eigen bedrijfskaart, alle in het geheugen van de digitale tachograaf opgeslagen gegevens downloaden of uitprinten teneinde een gegevensbestand te vormen die interne controles moet toelaten. Dergelijke gegevensbank kan eveneens een belangrijk hulpmiddel voor een efficiënt bedrijfsbeheer zijn (9).

4.2 4.2.1

Aanpassen yj en aj aan de rij-en rusttijden Benamingen

Voor de aanpassing van de algoritmes wordt er uitgegaan van maximaal 9u rijtijd per dag. Deze 9 uren vereisen de nodige onderbreking(en). Laten we voor het model ervan uit gaan dat de werkdag start om 7u00 (Y0 ) en eindigt om 16u45 (YT H ). De chauffeur kan dan maximaal 9u reglementair rijden.


49

Gecumuleerde Rijtijd (GRT) Tussen twee resets worden alle rijtijden opgeteld. De rijtijd na een knooppunt vi wordt berekend door voor dit knooppunt de servicetijd gi en de reistijd tij op te tellen. De Gecumuleerde Rijtijd (GRT) op een tijdstip t telt de rijtijden op tussen de laatste reset en het tijdstip t. Zodanig kan door middel van de GRT nagekeken worden dat de 270’-grens voor rijtijd niet overschreden wordt. Wanneer er een volgende reset plaatsvindt, wordt de waarde GRT terug op 0 gesteld. Gecumulueerde Onderbrekingstijd (GOT) Hierboven werd reeds aangehaald dat onderbrekingen opgesplitst mogen worden. De regels daarvoor zijn beschreven in paragraaf 4.1.2. Er moet dus bijgehouden worden hoeveel onderbrekingstijd al reglementair opgenomen is. De Gecumuleerde Onderbrekingstijd (GOT) op een tijdstip t telt de reglementair opgenomen onderbrekingstijden op tussen de laatste reset en het tijdstip t. Verplichte Onderbreking (VO) Een chauffeur kan geconfronteerd worden met twee soorten onderbrekingen. Eén daarvan is de Verplichte Onderbreking (VO) die tijdens of na het transport plaatsvindt en die moet vermijden dat de 4 uren en 30 minuten Gecumuleerde Rijtijd niet overschreden wordt. Deze onderbrekingen hebben dus als functie een ‘reset’ te creëeren zodanig dat er geen overtredingen worden gemaakt. Wachtonderbreking (WO) Een tweede soort oponthoud vindt plaats op klantlocatie. De chauffeur moet bij een klant wachten tot het Service Time Window opengaat. Deze wachttijden kunnen meetellen als onderbreking op twee manieren: • een eerste wachtonderbreking na een reset die langer duurt dan 15 minuten. • een wachtonderbreking na een geslaagde eerste wachtonderbreking duurt langer dan 30 minuten. (waarbij de eerste wachtonderbreking (< 450 ) nog geen reset heeft kunnen bereiken)


50

Figuur 4.4: Schema dat de weergeeft hoe een reset bereikt kan worden.

Hierboven wordt weergegeven hoe een ‘reset’ bereikt kan worden. VO stelt een verplichte onderbreking voor en WO een wachtondebreking. Een verplichte onderbreking treedt enkel op in laatste instantie om rijtijdoverschrijding te vermijden. In hoofdstuk 2, paragraaf 2.3, werd ervoor gezorgd dat bij de eerste klant van een subroute nooit gewacht moest worden op de opening van het Service Time Window. De wachttijd werd niet opgenomen op klantlocatie, maar wel in het depot. Zodoende kon de chauffeur zich nuttig bezighouden in het depot in plaats van nutteloos op klantlocatie te staan wachten. In dit hoofdstuk geldt dit enkel nog voor de allereerste klant van een Multi Tour, want zo wordt de rijtijd van de Multi Tour automatisch verkort. De Multi Tour start dan op tijdstip y j = max(ej − t0j − g0 , Y0 ), waardoor bij sommige Time Windows tijd bespaard kan worden. Voor de eerste klant na een herbevoorrading is dit niet meer geldig. De reden hiervoor is dat de wachttijden zeer flexibel moeten zijn, zodat zo efficiënt mogelijk gereden kan worden. Het principe dat hier toegepast wordt is: ”neem een reset zoveel mogelijk naar achteren in de tijd op”. Een reset die later valt heeft meer kans om de resterende rijtijd te coveren, terwijl


51

bij een vroegere reset de mogelijkheid bestaat dat de rijtijd toch nog de 4u30’ overschrijdt. Figuur 4.2.1 toont dit aan. In de bovenste, foute versie wordt de wachttijd opgenomen in het depot. Hierdoor is er later op de dag nog een VO nodig om te voldoen aan de rij- en rusttijdreglementatie. In het onderste, correcte geval wordt de wachttijd doorgeschoven naar de klantlocatie. Doordat de reset nu later valt, is het niet meer nodig een extra VO in te lassen.

Figuur 4.5: Verduidelijking van de startprocedure uit het depot. De donkergroene balk stelt het Time Window voor van klant vj .

4.2.2

Werking van het T ijd-algoritme

Er wordt gebruik gemaakt van het algoritme T ijd om het voorgaande model aan te passen aan het model met rij- en rusttijden. De algoritmes beschreven in hoofdstuk 3 maken allen gebruik van de variabelen aj en yj . In het nieuwe model worden deze waarden berekend, rekening houdend met de GRT en GOT die voor knooppunt vj gelden. Het T ijd-algoritme is in geprogrammeerde vorm terug te vinden in de appendix E. Bijgevoegd zit een aanpassing van de Hr .m file aan dit T ijd-algoritme. Enkele andere algoritmes hebben gelijkaardige aanpassingen als Hr .m nodig, maar deze aangepaste m-files zijn niet opgenomen in de appendices.


52

Hieronder wordt in een schema de werking van het algoritme weergegeven. Als input wordt er gebruik gemaakt van GRTi en GOTi op het tijdstip yi . Daaruit worden dan het aankomsttijdstip aj en het service starttijdstip yj berekend. GRTj en GOTj op tijdstip yj vormen het andere deel van de output.


Figuur 4.6: Schema dat de werking van het T ijd-algoritme weergeeft.

53


54

De verschillende mogelijkheden uit het schema worden nu overlopen: • GRTi + gi + tij ≥ 2700 In eerste instantie wordt er nagegaan of er tijdens de reistijd tij reeds een overschrijding van de GRT -grens plaatsvindt. Is dit het geval dan moet deze overschrijding vermeden worden door een Verplichte Onderbreking op het moment dat GRT = 2700 . Een eerst reistijd t∗ij start op yi + gi en eindigt op het moment dat GRT = 2700 . Vervolgens vindt een VO plaats die afhankelijk van GOTi 30 of 45 minuten bedraagt. Na deze VO wordt de resterende afstand tussen vi en vj afgelegd. De reistijd t∗∗ ij is tijdstipafhankelijk van het startmoment ∗ yi + gi + tij + V O. De afbeelding hieronder geeft een schets van de overtreding. Links wordt de overtreding afgebeeld, rechts worden de twee GOT -afhankelijke oplossingen weergegeven.

Figuur 4.7: Verduidelijking indien GRT-grens overschreden wordt gedurende tij .

Na de reistijd t∗∗ ij kan het nog voorvallen dat er een wachttijd yj − aj plaatsvindt. Afhankelijk van de grootte van die wachttijd worden GRT en GOT bepaald.


55

• (yj − aj ≥ 450 ) ∨ [(yj − aj ≥ 300 ) ∧ (GOTi = 150 )] Indien de eerste GRT -overtreding niet van toepassing is wordt er verder gekeken naar de wachttijd yj − aj . Deze wachttijd vindt plaats omdat er gewacht moet worden op de opening van het Service Time Window. De wachtonderbrekingen in de twee bovenstaande disjuncten leiden allebei tot een reset.

Figuur 4.8: Een wachtonderbreking vindt plaats omdat gewacht moet worden op de opening van het Time Window.

• GRTi + gi + tij + gj ≥ 2700 Indien de voorgaande gevallen niet van toepassing zijn, is het niet meer mogelijk dat een wachttijd in staat is een reset uit te voeren. De nog niet nader bekeken (wachttijd-GOTi ) combinaties zijn enkel in staat om de GOTj aan te passen. Daarom wordt een VO ingeroepen om te vermijden dat de GRT groter wordt dan 270 minuten .

Figuur 4.9: Verduidelijking indien GRT-grens overschreden wordt tijdens servicetijd gj .

In bovenstaande figuur wordt links een routering getoond waarin de 270 minuten grens overschreden wordt terwijl men bezig is het voertuig te lossen op locatie vj . Nu is het zeer onprofessioneel om een rustpauze in te lassen terwijl men aan het lossen is bij de klant. Dus om te vermijden dat er gerust wordt tijdens het lossen bij de klant, moet de reset plaatsvinden vóór er aan de service bij de klant wordt begonnen. De Verplichte Onderbreking wordt dan opgenomen na de reistijd tij . Dit is te zien rechts in bovenstaande afbeelding.


56

• yj − aj ≥ 150 Als alle voorgaande gevallen niet van toepassing zijn, wordt uiteindelijk rekening gehouden met de overige (wachttijd-GOTi ) combinaties. Indien yj − aj ≥ 150 dan wordt GOTj = 150 , anders blijft GOTj = 00 .

4.3

Voorbeeld

‘Hc1.m’ is een versie van ‘Hc.m’ aangepast aan de rij- en rusttijden. Het algoritme wordt hieronder uitgevoerd voor 10 klanten. In onderstaande print screen uit Matlab ziet u onder T imeW indows een matrix die de onderen bovengrens van de windows weergeven. Demand stelt de vraag voor van de klanten. qmax is in deze voorbeeldoefening gelijkgesteld aan 50. Vervolgens wordt het algoritme opgeroepen, waarbij W = 4 en Route een lege routering voorstelt. De oplossing A wordt bekomen. De eerste rij stelt de indices i van de klanten voor, de tweede rij stelt xi voor, de derde rij y i , de vierde rij yi en de vijfde rij stelt zi voor. Collect stelt de oplossing voor onder matrixvorm waarbij elke rij een Multi Tour voorstelt.

Figuur 4.10: Oplossing van Hc1.m voor n = 10.

De Multi Tour startend naar klant v1 wordt van nabij bekeken in onderstaande tabel. Er vindt

57


een reset plaats wanneer klant v3 bezocht wordt. Dit omwille van de wachtonderbreking die langer duurt dan 45 minuten. i

1

3

6

11

ai yi yi − ai GRTi GOTi

496.6667 496.6667 0 76.6667 0

564.4013 650 85.5987 0 0

777.8668 800 22.1332 127.8668 15

850.6924 850.6924 0 178.5592 15

Vervolgens wordt een volgende Multi Tour bekeken. Bij klant v9 loopt de wachtonderbreking op tot 41.9764 minuten. Hierdoor wordt GOT = 15. Tijdens de reistijd t10 2 wordt GRT gelijk aan 270’ op het tijdstip 749.0738. Omdat GOT op dat moment 15 minuten bedraagt, moet er een verplichte onderbreking gehouden worden van 30 minuten. Vervolgens wordt op het tijdstip 779.0738 de tijdstipafhankelijke reistijd t∗∗ 10 2 berekend voor de resterende afstand. Na aankomst bij klant v2 moet nog 15.7030 minuten gewacht worden alvorens de service kan starten. Vandaar dat GRT wederom 15’ bedraagt. i

7

9

5

10

2

11

4

11

ai yi yi − ai GRTi GOTi

500 500 0 62.9026 0

528.0236 570 41.9764 90.9262 15

607.2008 607.2008 0 128.1270 15

685.8926 685.8926 0 206.8188 15

784.2970 800 15.7030 0 15

910.8202 910.8202 0 110.8202 15

954.4541 954.4541 0 154.4541 15

1001.8000 1001.8000 0 201.8148 15

Onderstaande figuur toont hoe de drie Multi Tours verlopen. Elke kleur stelt één Multi Tour voor.


58

Figuur 4.11: Grafiche voorstelling van de oplossing voor n = 10.

4.4

Resultaten W

5

7

Hc (W )

e 12350 (3’32”)

e 12316 (4’58”)

Hc 1(W )

e 12990 (20’09”)

e 13129 (22’53”)

Hv (Hc (W ), 6)

e 12322 (7’06”)

e 12275 (7’17”)

Hv 1(Hc (W ), 6)

e 12862 (39’32”)

Tabel 4.1: Kosten van de routeringen en hun verbeteringen met en zonder reglementering

Hetzelfde probleem als in paragraaf 3.4.2 over de Colruyt-winkels wordt hier ook behandeld. Er wordt gekeken wat de kostprijs is van een routering, nu rekening houdend met de rij- en rusttijden. Normaal gezien zou door de extra restricties een duurdere routeringskost gevonden moeten worden, wat ook het geval is. Door de lange loopttijd worden de pogingen beperkt


59

tot de beste oplossingen uit vorige hoofdstuk. Tabel 4.1 toont de runs zonder reglementering (Hc &Hv ) en met reglementering (Hc 1&Hv 1). Het berekenen van GRT , GOT , aj en yj om de reistijden en onderbrekingen te berekenen, verzwaart het oplossen van het probleem overduidelijk. De runtims voor gereglementeerde oplossingen zijn veel langer dan die voor niet-gereglementeerde. Details van de beste oplossing Hv 1(Hc 1(5), 6) worden afgebeeld in volgende figuur. Het Collect-commando geeft een matrixvoorstelling van de Multi Tours. Elke rij stelt een Multi Tour voor. Een grafische voorstelling van de routering volgt in de figuur erna.

Figuur 4.12: Printscreen van de oplossing in Matlab.


Figuur 4.13: Grafische voorstelling van de routering.

60


61

Ten opzichte van de oplossing in vorig hoofdstuk die 9 vrachtwagens nodig had, valt op dat deze oplossing 10 vrachtwagens nodig heeft. De reglementering verzwaart het probleem dus duidelijk, wat leidt tot een hogere kost.

Hoofdstuk 5

Genetisch algoritme Zoals reeds aangehaald in hoofdstuk 1 & 2 werd het wiskundig model opgesteld met het oog op zowel het IMTOV-algoritme als een Genetisch Algoritme. De aanpak met een Genetisch Algoritme betreft een project voor het vak ‘Applied Combinatorial Optimization & Heuristics’. Ter volledigheid zal het projectverslag toegevoegd worden aan deze thesis. Het betreft de versie zoals deze is afgeleverd voor het vak. In het kader van mijn thesis heb ik geen verder onderzoek meer verricht naar de Genetische Algoritmes. De resultaten in dit hoofdstuk zijn dan ook niet diepgaand. In dit hoofdstuk wordt een Genetisch Algoritme opgesteld voor het beschreven wiskundig basismodel uit hoofdstuk 3. In een eerste fase wordt kort de werking van Genetische Algoritmes uitgelegd (12). Vervolgens wordt aan de hand van de handleiding opgesteld door H. Pohlheim (12) het Genetisch Algoritme gedefinieerd. Tot slot laten we dit Genetisch Algoritme lopen voor enkele experimenten. Aan de hand van de resultaten wordt getracht de parameters correct af te stellen.

5.1

Werking Genetisch Algoritme

Evolutionaire algoritmen zijn stochastische zoekmethodes die het proces volgen van natuurlijke evolutie. Deze algoritmen opereren op een populatie mogelijke oplossingen waarop het principe van survival of the fittest wordt toegepast. Wanneer geen van de individuen in de populatie aan de criteria voldoet voor een optimale oplossing, dan creëert men een nieuwe generatie. Deze nieuwe generatie ontstaat uit recombinatie van de individuen uit de oorspronkelijke generatie die de beste fitness hebben. Vervolgens wordt de nieuwe populatie vastgelegd bestaande uit een deel van de oude generatie en een deel van de nieuwe generatie. Deze cyclus wordt herhaald tot voldaan is aan de optimalisatie criteria. Hierna worden enkele typische kenmerken en procedures van het GA beschreven.

62

Hoofdstuk 5. Genetisch algoritme

63

Multiple subpopulations Wanneer meerdere subpopulaties worden gebruikt, verkrijgt men meestal een beter resultaat. Elke subpopulatie evolueert dan ge¨ısoleerd over een paar generaties alvorens een of meerdere individuen worden uitgewisseld tussen de subpopulaties. Dit principe komt meer overeen met hoe evolutie plaatsvindt in de natuur. Selection Selectie wordt gebruikt om te kiezen welke individuen gekozen dienen te worden voor reproductie. Voor de selectie maakt men gebruik van fitness toekenning aan elk individu. Vervolgens worden ouders gekozen volgens hun fitness. Dit kan gebeuren op verschillende manieren: roulette-wheel selection, stochastic universal sampling, local selection, ... Recombination Recombinatie produceert nieuwe individuen door informatie van de ouders te combineren. Voor dit model met integer beslissingsvariabelen is binary valued recombination van toepassing: single-point crossover, double-point crossover, multi-point crossover, shuffle crossover... Mutation Mutatie is de stap die plaatsvindt na recombinatie. Hierbij kan men instellen dat er mutaties plaatsvinden op sommige nakomelingen. Dit komt er op neer dat variabelen binnen de nakomeling een kleine kans hebben om gewijzigd te worden. Reinsertion Door middel van een reinsertion schema wordt bepaald welke individuen van de originele populatie vervangen zullen worden door nakomelingen.

5.2 5.2.1

Opstellen Genetisch Algoritme Variabelen en VLUB

De y-variabelen die in vorige hoofdstukken nog reële waarden voorstelden, worden hier afgerond naar gehele waarden. Dit om te vermijden dat de probleembeschrijving zowel gehele waarden als reële waarden bevat. Op die manier maakt het beschreven model gebruik van vier soorten integer variabelen. Door middel van de VLUB-vector definieert men de onderen bovengrens van de variabelen. Deze grenzen bepalen dan de intervalgrenzen waarbinnen de variabelen waarden kunnen aannemen. De variabelen worden opgeslagen in een Chromvector. Voor n klanten vindt men:

64

Hoofdstuk 5. Genetisch algoritme • xi Chrom LB UB

1 2 n+1

2 1 n+1

... ... ...

n 1 n+1

Hierbij kan er voor de eerste variabele x1 direct ingesteld worden dat x1 6= 1. Voor de overige variabelen is dit niet mogelijk. • yi Chrom LB UB

n+1 max(Y0 , e1 − t01 − g0 ) l1 − t01 − g0

... ... ...

2n max(Y0 , en − t0n − g0 ) ln − t0n − g0

Chrom LB UB

2n+1 e1 l1

... ... ...

3n e4 l4

Chrom LB UB

3n+1 0 n+1

... ... ...

4n 0 n+1

• yi

• zi

5.2.2

Doelfunctie

De doelfunctie 2.6.1 wordt voorgesteld door ObjV al. De restricties worden in het Genetisch Algoritme gedefinieerd door middel van bijkomende


65

doelfuncties. Restricties waar niet aan voldaan is, krijgen de waarde toebedeeld van de overtreding. Het Genetisch Algoritme zal dan proberen deze overtreding van de restricties te minimaliseren naar 0, zodat de toebedeelde overtredingswaarde verkleint. Wanneer de overtredingswaarde 0 wordt, is voldaan aan de restrictie. De omzetting van restrictie naar doelfunctie gebeurt als volgt: G1 ≥ 0 =⇒ ObjAdd1 = 0(G1 >= 0) − G1(G1 < 0)

(5.1)

G3 = 0 =⇒ ObjAdd3 = 0(G3 = 0) + G3(| G3 |> 0).

(5.3)

G2 ≤ 0 =⇒ ObjAdd2 = 0(G2 <= 0) + G2(G2 > 0)

(5.2)

Het opgestelde model bevat 7 soorten restricties, namelijk 2.2, 2.3, 2.4, 2.5, 2.6, 2.7 en 2.8. Elke soort komt n keer voor. Deze 7n restricties worden omgezet naar 7n ObjAdd-waarden≥ 0. Een restrictie is voldaan als zijn ObjAdd-waarde 0 is. Per restrictiesoort wordt nu de gewogen som genomen van de n restricties. Het aantal ObjAdd daalt nu van 7n naar 7: ObjAdd1 , ObjAdd2 , ObjAdd3 , ObjAdd4 , ObjAdd5 , ObjAdd6 en ObjAdd7 . De restricties van de vorm ObjAdd kunnen in Genetische algoritmes op twee manieren in rekening gebracht worden: Multi-objective optimization Hierbij worden de ObjAdd-waarden als afzonderlijke doelfuncties beschreven, wat resulteert in 8 doelfuncties: [ObjV al ObjAdd1 ObjAdd2 ObjAdd3 ObjAdd4 ObjAdd5 ObjAdd6 ObjAdd7 ]. Op deze doelfuncties wordt dan ranking toegepast. Bij ranking worden alle elementen gescored maar op evenwaardige basis (i.e. het aantal restricties dat overtreden is, en niet de waarde van de overtreding). Een mogelijk nadeel hiervan is dat je een vlakke kostenfunctie krijgt. Het voordeel is dat je geen probleem hebt met het bepalen van de gewichten (zie paragraaf Penaltyterm). In de eerste fase van de ontwikkeling van mijn GA werd gewerkt met de Multi-objective optimization methode. Ik bekwam wel goede resultaten, maar op een zeer trage wijze. Dit doordat ik de werking van het ranken niet volledig onder de knie had... . Toch volgen hier nog de bekomen resultaten voor een run van het GA met multi-objective optimization:


66

Figuur 5.1: Voorbeeld van multi-objective plotting.

Doelfunctie met penaltyterm Deze werkwijze wordt toegepast in de verdere beschrijving. Hierbij wordt van de restricties ObjV ali met i = 1 : n twee gewogen sommen genomen met gewichten 1. Eén som TR van de tijdsrestricties en een tweede som XR van de overige restricties. De opdeling in twee sommen is doordat de overtredingen van de tijdsrestricties een grotere waarde aannemen dan de binaire overtredingswaarde van de niet-tijdrestricties. Dit doordat de y-waarden een groter domein hebben. Deze twee gewogen sommen worden toegevoegd aan de primaire doelfunctie voorzien van penaltyfactoren αt en αx :

ObjF un = ObjV al + αt T R + αx XR

(5.4)

De keuze van de penaltyfactoren α is zeer belangrijk om tot een optimaal resultaat te komen. De factor α moet voldoende hoog zijn, want het voldaan zijn van de restricties heeft voorrang op het minimaliseren van de primaire doelfunctie. Daarom moet de hoogte van de α factoren afgewogen worden tov de primaire doelfunctie. De α waarden mogen ook niet te groot zijn omdat anders het zoekproces belemmerd wordt. Door de hoge penaltykost gaat het GA vermijden dat reeds voldaan restricties terug niet-voldaan worden. Het zoekproces wordt in dat geval vlug richting voldane restricties gestuurd, maar dit ten koste van een brede zoektocht in de zoekruimte van de primaire kostenfunctie. In deze primaire doelfunctie wordt de grootste kost bepaald door het aantal voertuigen.


67

Het huren van een voertuig kost namelijk cv = 470EU R per dag. De α-factor wordt hier aan afgewogen. 1 foutje aanwezig in de restrictiesom XR moet meer doorwegen dan het minimaliseren van de primaire kostenfunctie. Daarom moet αt een waarde aannemen die groter is dan cv . Er werd nu een grafiek opgesteld door voor een aantal combinaties (αx , αt ) de bijhorende ObjFun uit te rekenen. Volgende figuur wordt bekomen:

Figuur 5.2: De functiewaarde uitgezet tov αx en αt

Hierbij werd voor elke (αx , αt )-combinatie het gemiddelde genomen van tien runs. De twee koppels die het sterkst naar voor komen zijn (10, 500) en (10, 1000). Met de eerstgenoemde combinatie wordt verder gerekend. Voor αt = 1 werden non-feasible oplossingen bekomen. Dit duidt er dus op dat deze factor te klein is om de tijdsrestricties te laten gelden.

5.2.3

Selectie, Recombinatie en Mutatie

Bij de representatie van de variabele werd gekozen voor tbx3int. Deze functie definieert een aantal standaard parameters voor de optimalisatie van integer variabelen. Volgende instellingen worden standaard gekozen door tbx3int: • ’Recombination.Name’, ’recdis’ ... • ’Mutation.Name’, ’mutint’ ... • ’Mutation.Range’, [0.1, 0.03, 0.01, 0.003, 0.001, 0.0003] ...


68

• ’Mutation.Precision’, 16 ... De GEATbx bevatte echter al een basismodel voor VRP. Dit is verschillend aan dat van mij, maar er zijn ook overeenkomsten. Vandaar dat ik sommige parametersettings gelijk liet lopen aan deze van het VRP-model: • ’Recombination.Name’, ’recsh’ ... • ’Recombination.Rate’, 0.8 ... • ’Mutation.Rate’, 0.6 ... • ’Mutation.Range’, 1 ... • ’Selection.GenerationGap’, 0.85 ... Het grootste verschil is dat het GEATbx-VRP-model alle klanten reeds bevat, dus daar is permutatie mogelijk. In mijn model zitten niet alle klanten, omdat ik er vanuit ga dat ontbrekende klanten in de Chrom-vector bereikt worden via een traject van het depot naar de bewuste klant. Daardoor zijn instellingen zoals ’mutswap’, ’mutrandperm’, ’recgp’, ... niet rechtstreeks toepasbaar op mijn model. Kleine aanpassingen van bovenstaande parameters bracht weinig veranderingen teweeg vandaar dat op deze parameters niet dieper wordt ingegaan. Vervolgens wordt gekeken naar de invloed van het aantal subpopulaties. Hoe meer subpopulaties, hoe vlugger de streefwaarde bereikt wordt. Zoals in het begin van dit hoofdstuk reeds vermeld werd, zal de aparte ontwikkeling per subpopulatie het genetisch proces tot een betere oplossing doen leiden. In de afbeelding is dit ook te zien voor subpopulaties die 1, 2 of 3 bedragen.


69

Figuur 5.3: Invloed van het aanral subpopulaties op ObjFun.

Opmerking Dit model heeft nood aan mutaties en recombinaties die kennis van het model gebruiken om goede oplossingen te ontwikkelen. Deze zijn niet ontwikkeld in dit hoofdstuk. Wel wordt nu even aangehaald hoe betere recombinaties en mutaties opgesteld kunnen worden. Algemeen kan gesteld worden dat het mutatieproces belangrijk is om nieuwe informatie in de oplossingen te krijgen. Recombinaties zijn belangrijk om goede informatie van de ouderparen door te geven aan de nakomelingen. Een mogelijkheid voor het recombinatieproces bestaat erin om via de eerder beschreven k-functie de beste Multi Tours te selecteren uit een oplossing. De knooppunten die in deze Multi Tours zitten kunnen dan hun waarden behouden. De overige klanten kunnen dan via een mutatieproces aangepast worden zodat gewijzigde Multi Tours gegenereerd worden.

5.3

Toepassing Genetisch Algoritme

Tot slot geef ik een voorbeeld van een gegenereerde oplossing voor n=6 met parameters ingesteld zoals hierboven vermeld. De kostenparameters zijn hier veschillend van vorige hoofdstukken omdat bij het schrijven van dit hoofdstuk de informatie van Colruyt nog niet beschikbaar was: ct = e 0.5/min, cv = e 800/voertuig en cd = e 0.2/km. Volgende uitkomst wordt gevonden rekening houdend met tijdstipafhankelijke reistijden en een laadcapaciteit van 70. Na 200 generaties (0,35 minuten) bekomt men onderstaande voorstelling waarin 1 voertuig twee subtours aandoet. Men ziet hier duidelijk dat aan alle voorwaarden is voldaan: service tijden, laadcapaciteit, elke klant bezoeken, ...

70

Hoofdstuk 5. Genetisch algoritme Gegevens: i

1

2

3

4

5

6

xi yi yi zi

7

3

1

7

736 6

647 0

689 0

2 556 619 0

953 7

5 789 876 0

qi

8

18

22

6

11

10

Figuur 5.4: Voorstelling van de oplossing.

Hoewel de recombinatie- en mutatieprocessen niet op punt staan, bevat deze heuristiek toch nog enige interne kennis die er voor zorgt dat het GA betere resultaten genereert dan een random search. De kost van vorige routering bedroeg e 1109. De waarden (inclusief penaltytermen) gevonden voor 10000 random search pogingen, liggen minsten een factor 10 hoger.


Figuur 5.5: Vergelijking met een randomsearch.

71

Hoofdstuk 6

Besluit 6.1

Conclusies

Het basismodel van deze thesis was gebaseerd op het werk van Figliozzi. Het Multi Tour Opbouwalgoritme werd letterlijk overgenomen uit zijn paper Hc . De overige twee algoritmes Hr en Hv steunen wel op zijn beschrijvingen maar moesten nog volledig opgesteld en geprogrammeerd worden met de Multi Tours-problematiek ge¨ıntegreerd in het model. Dit leidde uiteindelijk tot algoritmes die correcte oplossingen genereerden. Het principe om de routering nog te verbeteren, komt ook voor in Figliozzi’s paper. Het Multi Tour Verbeteringsalgoritme in deze thesis pakt dit echter op een andere manier aan. Het betreft een iteratief proces waarbij telkens één Multi Tour minder geherrouteerd wordt. Doordat in het begin van het algoritme een groot aantal Multi Tours geherrouteerd worden, zorgt dit wel voor lange looptijden. Het hele basismodel leek correct te werken. Toch had het misschien nuttig geweest indien er vergelijkend onderzoek was uitgevoerd naar andere Multi Tour algoritmes. Dit was echter minder voor de hand liggend omdat dan een benchmark gevonden moet worden die hetzelfde probleem beschrijft (tijdstipafhankelijke reistijden, Multi Tours, Time Windows, ...). De rij- en rusttijden die in het model verwerkt werden, zorgden voor een creatieve inbreng. De hele problematiek werd van niets uitgewerkt. De resultaten die hieruit bekomen werden, leken op een correcte manier het probleem op te lossen. Het Genetische Algoritme was een geval apart. Dit werd voornamelijk opgenomen in deze thesis voor de volledigheid. Het wiskundig model was nu eenmaal opgebouwd voor beide aanpakken, dus was het logisch dat hoofdstuk 5 deze oplossingsmethode ook even aanhaalde. Goede resultaten werden niet bereikt met het GA. Voornamelijk omdat het mutatie- en recombinatieprocessen meer probleemspecifieke informatie nodig hadden om op een slimme

72

Hoofdstuk 6. Besluit

73

manier tot goede resultaten te komen. Zonder deze probleemspecifieke processen was het eerder een ‘slimme’ randomsearch.

6.2

Perspectieven

De drie algoritmes hierboven worden wel beperkt door de reistijdberekening. De afstanden die hiervoor gebruikt worden, zijn gerekend in vogelvlucht en bevatten geen informatie over de soort wegen die men gebruikt. Op autostrades wordt nu eenmaal een andere snelheid gehanteerd dan in een dorpskern. Een aanpassing zou eruit kunnen bestaan om tussen alle klanten de wegen door middel van een routeplanner te bestuderen. Zo kan men enerzijds de correcte afstand gebruiken. Dus niet in vogelvlucht. Anderzijds kan een routeplanner informatie geven over de wegenonderverdeling op het traject. Op die manier kunnen de tijdstipafhankelijke reistijden nauwkeuriger berekend worden door gebruik te maken van snelheidsfunctie per soort van weg. Een andere mogelijkheid is om voor alle trajecten de data op te zoeken via http://www.start-sitter.be. Zo kan men de gemiddelde snelheden te weten komen voor verschillende tijdsintervallen. Probleem hierbij is dat enkel de autostrades van meetpunten voorzien zijn. Een volgend perspectief ligt bij de Genetische Algoritmes. Indien het huidig GA behouden wordt, dient er kennis ge¨ınjecteerd te worden in de recombinatie- en mutatieprocessen. Een andere strategie is om een bestaand GA dat rond VRP handelt aan te passen aan de rij- en rusttijdreglementering. Tot slot wordt het oorspronkelijke thema van deze thesis even bekeken. In een eerste fase van de masterproef was het de bedoeling om deze thesis rond het Inventory Routing Problem (IRP) te laten handelen. Maar de ingeving van de rij-en rusttijdreglementering zorgde voor een wijziging van het onderwerp. Desalniettemin zou het hier voorgestelde model perfect verder uitgebouwd kunnen worden voor IRP. Onderstaande figuur geeft een idee hoe dit in zijn werk zou kunnen gaan. Het IRP probleem moet beslissen op welke dagen er aan welke klanten geleverd wordt volgens hun Service Time Windows zodanig dat deze klanten nooit zonder voorraad vallen. Zo bekomt men voor een werkweek vijf afzonderlijke VRP-problemen die samen met de inventory holding costs instaan voor de wekelijkse IRP kostenfunctie.

74

Hoofdstuk 6. Besluit

Figuur 6.1: Basisidee voor het IRP-model.

Bijlage A

Algoritme W (X, n) Het doel van dit algoritme is om uitgaande van de Xi -variabelen de wis -waarden te bepalen. X n

[x1 x2 ... xn x1 x2 ... xn ] Aantal klanten in het VRP probleem.

De wis -waarden worden verzameld in een vector W, waarvoor geldt: wis = W (in + s).

75

Bijlage A. Algoritme W (X, n)

76

Start W (X, n) 1. W ← zeros(1 : n(n + 1)) 2. i ← 0 3. for each s ∈ [n + 1, 2n] do 4.

if (X(s) = n + 1) then

5.

W ((s − n)(n + 1)) ← 1

6.

i←s−n

7.

k←0

8.

while (W (s − n) = 0) ∧ (k 6= n + 1) do

9.

k ← find(X = i)

10.

if size(k, 2) = 1 then

11.

if (k > n) then

12.

k ←k−n

13.

else if (k > 0) then

14.

k←0

15.

else

16.

k ←n+1

17.

end if

18.

i←k

19.

W (kn + (s − n)) ← 1

20.

else

21.

k =n+1

22.

end if

23. 24.

end while end if

25. end for

Bijlage B

Hr (Route, vi, vj , Qi, C, ∆) B.1

Hr.m

77 function Route = Hr(Qheden,Route,vi, vj,C,Delta) % Inladen van de gegevens (T, Q, qmax, D, E, L, n, ∼, ∼, cq, ∼, qstop, ∼, Y0, YTH, ∼, ∼)=degegevens(); Qi=Qheden; % Verbinding van vi naar vj vastleggen als vi gelijk is aan nul if (vi==0) yjdepot=max(E(vj)-TTTomg(E(vj),D(vj),T)-qstop-cq*qmax,Y0); yj=yjdepot+qstop+cq*qmax+TTT(yjdepot+qstop+cq*qmax,D(vj),T); Route(n+vj)=yjdepot; Route(2*n+vj)=yj; Qi=qmax-Q(vj); % Verbinding van vi naar vj vastleggen als vi niet gelijk is aan 0

yjdepot=max(E(vj)-TTTomg(E(vj),D(vj),T)-qstop-cq*(qmax-Qi),Route(2*n+vi) +qstop+cq*Q(vi)+TTT(Route(2*n+vi)+qstop +cq*Q(vi),D(vi*(n+1)+n+1),T)); yj=max(E(vj),Route(2*n+vi)+qstop+cq*Q(vi)+TTT(Route(2*n+vi)+qstop+cq*Q(vi),D(vi*(n+1)+vj),T)); yjj=yjdepot+qstop+cq*(qmax-Qi)+TTT(yjdepot+qstop+cq*(qmax-Qi),D(vj),T); if ((Qi-Q(vj)≥0)&&(yj+qstop+cq*Q(vj)+TTT(yj+qstop+cq*Q(vj),D(vj*(n+1)+(n+1)),T)≤YTH)&&(yj≤ L(vj))) t=1; elseif ((yjj+qstop+cq*Q(vj)+TTT(yjj+qstop+cq*Q(vj),D(vj*(n+1)+n+1),T)≤YTH)&&(yjj≤L(vj))) yj=yjj; t=2; else yjdepot=max(E(vj)-TTTomg(E(vj),D(vj),T)-qstop-cq*qmax,Y0); yj=yjdepot+qstop+cq*qmax+TTT(yjdepot+qstop+cq*qmax,D(vj),T); t=3; end

Bijlage B. Hr (Route, vi , vj , Qi , C, ∆)

else

% Afhankelijk van welke type ’t-waarde’ wordt de Route verder benoemd if (t==1) Route(2*n+vj)=yj; Route(vi)=vj; Qi=Qi-Q(vj); elseif (t==2) Route(vi)=n+1; Route(n+vj)=yjdepot; Route(2*n+vj)=yj; Route(3*n+vi)=vj; Qi=qmax-Q(vj); elseif (t==3) Route(vi)=n+1; Route(n+vj)=yjdepot;

78

end % Gegevens instellen voor de rest van de ongerouteerde klanten te routeren. vi=vj; type=Inf; lowestNext=vj; y=Inf; ydepot=Inf; C=setdiff(C,vj);


Route(2*n+vj)=yj; Route(3*n+vi)=n+1; Qi=qmax-Q(vj); end

% Verder verloop van het Nearest Neighbor Algorithm while(∼ isempty(C)) bestValue=inf; for j=1:size(C,2) yjdepot=max(E(C(j))-TTTomg(E(C(j)),D(C(j)),T)-qstop-cq*(qmax-Qi),Route(2*n+vi)+qstop+cq*Q(vi) +TTT(Route(2*n+vi)+qstop+cq*Q(vi),D(vi*(n+1)+n+1),T)); aj = Route(2*n+vi)+qstop+cq*Q(vi)+TTT(Route(2*n+vi)+qstop+cq*Q(vi),D(vi*(n+1)+C(j)),T); yj = max(E(C(j)),aj); yjj=yjdepot+qstop+cq*(qmax-Qi)+TTT(yjdepot+qstop+cq*(qmax-Qi),D(C(j)),T); if ((Qi-Q(C(j))>0)&&(yj+qstop+cq*Q(C(j))+TTT(yj+qstop+cq*Q(C(j)),D(C(j)*(n+1)+(n+1)),T)≤YTH)&&(yj≤L(C(j)))) g=Delta(1)*D(vi*(n+1)+C(j)) + Delta(2)*(yj-(Route(2*n+vi))) + Delta(3)*(L(C(j))-aj) + Delta(4)*(Qi-Q(C(j))); t=1; elseif ((yjj+qstop+cq*Q(C(j))+TTT(yjj+qstop+cq*Q(C(j)),D(C(j)*(n+1)+n+1),T)≤YTH)&&(yjj≤L(C(j)))) yj=yjj; aj = Route(2*n+vi)+qstop+cq*Q(vi)+TTT(Route(2*n+vi)+qstop+cq*Q(vi),D(vi*(n+1)+n+1),T) + qstop + cq*qmax+ +TTT(Route(2*n+vi)+qstop+cq*Q(vi)+TTT(Route(2*n+vi)+qstop+cq*Q(vi),D(vi*(n+1)+n+1),T) + qstop + cq*qmax,

79


D(C(j)),T); g=Delta(1)*(D(vi*(n+1)+n+1)+D(C(j))) + Delta(2)*(yj-Route(2*n+vi)) + Delta(3)*(L(C(j))-aj) + Delta(3)*max(E(C(j))-aj,0) +Delta(4)*(qmax-Q(C(j))); t=2; else yjdepot=max(E(C(j))-TTTomg(E(C(j)),D(C(j)),T)-qstop-cq*qmax,Y0); yj=yjdepot+qstop+cq*qmax+TTT(yjdepot+qstop+cq*qmax,D(C(j)),T); aj= Y0 + qstop + cq*qmax + TTT(Y0 + qstop + cq*qmax,D(C(j)),T); g=Delta(5) + Delta(1)*(D(vi*(n+1)+n+1)+D(C(j))) + Delta(2)*( yj-yjdepot + qstop+cq*Q(vi)+TTT(Route(2*n+vi)+qstop +cq*Q(vi),D(vi*(n+1)+n+1),T)) + Delta(3)*(L(C(j))-aj) + Delta(3)*max(E(C(j))-aj,0) + Delta(4)*(qmax-Q(C(j))); t=3; end if (g
80

B.2


elseif (type==3) Route(vi)=n+1; Route(n+lowestNext)=ydepot; Route(2*n+lowestNext)=y; Route(3*n+vi)=n+1; Qi=qmax-Q(lowestNext); end vi=lowestNext; C=setdiff(C,lowestNext); end d=find(Route==0); Route(d(1))=n+1; Route(3*n+d(1))=n+1;

T T T.m

function x = TTT(tstart, d, TI) k=TI(3,TI(1,:)≤tstart&(tstart-60)<TI(1,:)); tt=tstart+d/TI(2,k); while (tt≥TI(1,k+1)) d=d-(TI(1,k+1)-max(tstart,TI(1,k)))*TI(2,k); tt=TI(1,k+1)+d/TI(2,k+1); k=k+1; end x=tt-tstart;

B.3

T T T omg.m 81

function x = TTTomg(teind, d, TI)

B.4

degegevens.m

Dit bestand wijzigde voortdurend van gegevens. De versie die hier afgebeeld wordt, is niet de data gebruikt voor het Colruyt-probleem. function (T, Q, qmax, D, E, L, n, cd, ct, cq, cv, qstop, Delta, Y0, YTH, Xco, Yco)=degegevens()


k=TI(3,TI(1,:)≥teind&(teind-60)<TI(1,:)); tt=teind-d/TI(2,k); while (tt≤TI(1,k)) d=d-(min(teind,TI(1,k+1))-TI(1,k))*TI(2,k); tt=TI(1,k)-d/TI(2,k-1); k=k-1; end x=teind-tt;

% Parameters n=50;% Aantal klanten Delta=[[3 7 2 0.1 500]]; % Gegevens T(1,:)=0:60:2040; % Tijdsintervallen snelheidsfunctie T(2,:)=[1.5 1.5 1.5 1.5 1.5 1.5 1.3 1 0.9 1 1.2 1.2 1.2 1.2 1.2 1.2 1 0.9 0.8 1 1.2 1.3 1.4 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5]; T(3,:)=1:35; % Kostparameters cd=0.2; % Verbruikprijs 1kilometer cv=800; % Huurprijs voor een vrachtwagen ct=0.5; % Brutouurloon per minuut voor chauffeur

82

% R101 num = xlsread(’R101.xls’);

B.5


Xco(1:101)=num(:,2); % Basis ligt op (35,35) Yco(1:101)=num(:,3); Xco(n+2)=Xco(1); Yco(n+2)=Yco(1); D=Dcal(Xco, Yco,n); E=num(2:101,5); L=num(2:101,6); Q=num(2:101,4); cq=0; qstop=10; qmax=50; Y0=0; YTH=230;

Dcal.m

function D = Dcal(Xco,Yco,n) D=zeros((n+1)∧2,1); Xco(n+2)=0; % Omdat n+1 terug gelijk is aan de oorsprong overschrijf je de waarden van Xco dat meer waarden bevat dan n Yco(n+2)=0; for i=0:n for j=1:n+1 D(i*(n+1)+j)=sqrt((Xco(i+1)-Xco(j+1)∧2+(Yco(i+1)-Yco(j+1)∧2);% Doordat index 0 niet mag moet elke i +1 end end

83

Bijlage C

Hc(W 1, Route, vi, Qi, Ci) C.1

Hc.m

84 function Route2 = Hc(W1, Route, vi, Qi, Ci) (∼, ∼, ∼, ∼, ∼, ∼, n, ∼, ∼, ∼, ∼, ∼, Delta, ∼, ∼, ∼, ∼)=degegevens(); hRoute(1:4*n)=Route; hPrijs=Inf; for j=1:size(Delta,1) start=vi; vRoute(1:4*n)=Route; C=Ci; Q=Qi; lowestNext=0; W=W1; while(∼isempty(C)) W=min(W,size(C,2)); CC=w(W, vRoute, C, start, Delta(j,:), Qi); lowestCost=Inf;

Bijlage C. Hc (W 1, Route, vi, Qi, Ci)

for i=1:size(CC,2) unie=Hr(Q,vRoute, start, CC(i),C,Delta(j,:)); if (Kost(unie)
C.2

w.m 85

Bijlage C. Hc (W 1, Route, vi, Qi, Ci) 86

function F = w(W, Route, C, vi, Delta, Qi) (T, Q, qmax, D, E, L, n, ∼, ∼, cq, ∼, qstop, ∼, Y0, YTH, ∼, ∼)=degegevens(); F(1:2,1:size(C,2))=Inf; if (vi==0) for j=1:size(C,2) yjdepot= max(E(C(j))-TTTomg(E(C(j)),D(C(j)),T)-qstop-cq*qmax,Y0); yj= yjdepot + qstop + cq*qmax + TTT(yjdepot+qstop+cq*qmax, D(C(j)) ,T); aj= Y0 + qstop + cq*qmax + TTT(Y0 + qstop + cq*qmax,D(C(j)),T); g=Delta(5) + Delta(1)*(D(C(j))) + Delta(2)*(yj-yjdepot) + Delta(3)*(L(C(j))-aj) + Delta(3)*max(E(C(j))-aj,0) + Delta(4)*(qmax-Q(C(j))); M=[F(1,F(1,:)¡g) g F(1,F(1,:)¿=g)]; M(2,:)=[F(2,F(1,:)¡g) C(j) F(2,F(1,:)¿=g)]; F=M(1,:); F(2,:)=M(2,:); end F=F(2,1:W); else for j=1:size(C,2) yjdepot = max( E(C(j))-TTTomg(E(C(j)),D(C(j)),T)-qstop-cq*(qmax-Qi) , Route(2*n+vi)+qstop+cq*Q(vi) +TTT(Route(2*n+vi)+qstop+cq*Q(vi),D(vi*(n+1)+n+1),T)); aj = Route(2*n+vi)+qstop+cq*Q(vi)+TTT(Route(2*n+vi)+qstop+cq*Q(vi),D(vi*(n+1)+C(j)),T); yj = max(E(C(j)),aj); yjj = yjdepot+qstop+cq*(qmax-Qi)+TTT(yjdepot+qstop+cq*(qmax-Qi),D(C(j)),T); if ((Qi-Q(C(j))≥0)&& (yj+qstop+cq*Q(C(j))+TTT(yj+qstop+cq*Q(C(j)),D(C(j)*(n+1)+(n+1)),T)≤YTH)&&(yj≤L(C(j)))) g = Delta(1)*D(vi*(n+1)+C(j)) + Delta(2)*(yj-(Route(2*n+vi))) + Delta(3)*(L(C(j))-aj) + Delta(4)*(Qi-Q(C(j))); elseif ((yjj+qstop+cq*Q(C(j))+TTT(yjj+qstop+cq*Q(C(j)),D(C(j)*(n+1)+n+1),T)≤YTH)&&(yjj≤L(C(j)))) yj = yjj; aj = Route(2*n+vi)+qstop+cq*Q(vi)+TTT(Route(2*n+vi)+qstop+cq*Q(vi),D(vi*(n+1)+n+1),T) + qstop + cq*qmax + TTT(Route(2*n+vi)+qstop+cq*Q(vi)+TTT(Route(2*n+vi)+qstop+cq*Q(vi),D(vi*(n+1)+n+1),T) + qstop + cq*qmax,D(C(j)),T);


g=Delta(1)*(D(vi*(n+1)+n+1)+D(C(j))) + Delta(2)*(yj-Route(2*n+vi)) + Delta(3)*(L(C(j))-aj) + Delta(4)*(qmax-Q(C(j))); else yjdepot=max(E(C(j))-TTTomg(E(C(j)),D(C(j)),T)-qstop-cq*qmax,Y0); yj= yjdepot + qstop + cq*qmax + TTT(yjdepot+qstop+cq*qmax, D(C(j)),T); aj= Y0 + qstop + cq*qmax + TTT(Y0 + qstop + cq*qmax,D(C(j)),T); g=Delta(5) + Delta(1)*(D(vi*(n+1)+n+1)+D(C(j))) + Delta(2)*( yj-yjdepot + qstop+cq*Q(vi)+TTT(Route(2*n+vi) +qstop+cq*Q(vi),D(vi*(n+1)+n+1),T)) + Delta(3)*(L(C(j))-aj) + Delta(4)*(qmax-Q(C(j))); end M=[F(1,F(1,:)
C.3

AddCustom.m

87

function A = AddCustom(Qheden,Route,vi, vj) % Laad de gegevens in (T, Q, qmax, D,E,L, n, ∼, ∼, cq, ∼, qstop, ∼, Y0, YTH, ∼, ∼)=degegevens(); Qi=Qheden; if (vi==0) yjdepot=max(E(vj)-TTTomg(E(vj),D(vj),T)-qstop-cq*qmax,Y0); yj=yjdepot+qstop+cq*qmax+TTT(yjdepot+qstop+cq*qmax,D(vj),T); Route(n+vj)=yjdepot; Route(2*n+vj)=yj; Qi=qmax-Q(vj); else


% Check hoe vj verbonden kan worden aan het laatste punt vi in Route yjdepot=max(E(vj)-TTTomg(E(vj),D(vj),T)-qstop-cq*(qmax-Qi),Route(2*n+vi)+qstop+cq*Q(vi)+TTT(Route(2*n+vi)+qstop +cq*Q(vi),D(vi*(n+1)+n+1),T)); yj=max(E(vj),Route(2*n+vi)+qstop+cq*Q(vi)+TTT(Route(2*n+vi)+qstop+cq*Q(vi),D(vi*(n+1)+vj),T)); yjj=yjdepot+qstop+cq*(qmax-Qi)+TTT(yjdepot+qstop+cq*(qmax-Qi),D(vj),T); if ((Qi-Q(vj)≥0)&&(yj+qstop+cq*Q(vj)+TTT(yj+qstop+cq*Q(vj),D(vj*(n+1)+(n+1)),T)≤YTH)&&(yj≤L(vj))) t=1; elseif ((yjj+qstop+cq*Q(vj)+TTT(yjj+qstop+cq*Q(vj),D(vj*(n+1)+n+1),T)≤YTH)&&(yjj≤L(vj))) yj=yjj; t=2; else yjdepot=max(E(vj)-TTTomg(E(vj),D(vj),T)-qstop-cq*qmax,Y0); yj=yjdepot+qstop+cq*qmax+TTT(yjdepot+qstop+cq*qmax,D(vj),T); t=3; end % Afhankelijk van welke type ’t-waarde’ wordt de Route verder benoemd if (t==1) Route(2*n+vj)=yj; Route(vi)=vj; Qi=Qi-Q(vj); elseif (t==2) Route(vi)=n+1; Route(n+vj)=yjdepot; Route(2*n+vj)=yj; Route(3*n+vi)=vj; Qi=qmax-Q(vj); elseif (t==3) Route(vi)=n+1; Route(n+vj)=yjdepot; Route(2*n+vj)=yj;

88

end A=Qi; A(2:4*n+1)=Route;

C.4

Kost.m

89

function F cost=Kost(Route) % Laad de gegevens in (T, Q, ∼, D, ∼, ∼, n, cd, ct, cq, cv, qstop, ∼, ∼, ∼, ∼, ∼)=degegevens(); % Construeer de vector X X(n+1:2*n)=Route(1:n); for s=1:n if (sum((X(:)==s),2)==0) X(s)=s; end end % Pas de service starttijden aan: service starttijd + service + terugkeer depot for i=1:n Route(2*n+i)=Route(2*n+i)+qstop+cq*Q(i)+TTT(Route(2*n+i)+qstop+cq*Q(i),D(i*(n+1)+n+1),T); end % Voorbereiding om multi tour starttijden te berekenen EE=zeros(1,n); for i=1:n if (sum(Route(3*n+1:4*n)==i,2)==0) EE(i)=1; end end


Route(3*n+vi)=n+1; Qi=qmax-Q(vj); end

C.5

tot af stand.m

function d = tot afstand(X, D, n) d=(X(1:n)>0)*D(1:n); for i=1:n d=d+D(i*(n+1)+X(i+n)); end end

-


% Bereken de kost cost=cv*sum((Route(3*n+1:4*n)==n+1),2)+cd*tot afstand(X,D,n)+ct*sum(Route(2*n+1:3*n).*(Route(3*n+1:4*n)==n+1)) ct*sum(Route(n+1:2*n).*EE,2);

90

Bijlage D

Hv (Route, vi, vj , Qi, C, ∆) D.1

Hv.m

91 function Route = Hv(Route,W) (∼, ∼, ∼, ∼, ∼, ∼, n, ∼, ∼, ∼, ∼, ∼, ∼, ∼, ∼, ∼, ∼)=degegevens(); Prijs=Kost(MtoV(Route,n)); nRoute=Route; F=[]; P=Collect(Route); while(size(P,1)>1) S=ks(nRoute,size(P,1)) C=S(end,S(end,:) =n+1); C=C(C =0); F=[F C] G=setdiff(1:n,F); R=Route; R(2:5,G)=0; vRoute=Hc(W, MtoV(R,n), 0, 0, G)

end end

D.2

k.m

Bijlage D. Hv (Route, vi , vj , Qi , C, ∆)

if (Kost(MtoV(vRoute,n))¡Prijs) Prijs=Kost(MtoV(vRoute,n)); Route=vRoute; end nRoute=Route; nRoute(2:5,F)=0; nRoute(2,F)=F; P=Collect(nRoute);

function P = ks(Route, s) (∼, ∼, ∼, ∼, ∼, ∼, n, ∼, ∼, ∼, ∼, ∼, ∼, ∼, ∼, ∼, ∼)=degegevens(); W=Collect(Route); % Alle Q-indices met 1 omhoog, zodat Q1(1) gedefinieerd wordt als Q(0), Q1(2) als Q(1), ... Q1=[0; Q]; S(1:size(W,1),1:4)=Inf; P(1:size(W,1),1:4)=Inf; grens=min(s,size(W,1)); Q1(n+2)=0;

92

% Zet de gegevens van W om naar hun respectievelijke hoeveelheid vraag. G=zeros(size(W,1),size(W,2)+1); for i=1:size(W,1) for j=1:size(W,2) G(i,j)=Q1(W(i,j)+1); end

% Voorbereidingen om de afstand per route X(n+1:2*n)=Route(2,:); for s=1:n if (sum((X(:)==s),2)==0) X(s)=s; end end % Sorteren van de criteria for i=1:size(W,1) B=W(i,:);


end

% Routeduur j=W(i,find(B==n+1, 1, ’last’ )-1); P(i,1)=Route(4,j)+qstop+cq*Q1(j+1)+TTT(Route(4,j)+qstop+cq*Q1(j+1),D(j*(n+1)+n+1),T)-Route(3,W(i,1)); % Routenummer P(i,2)=i; % Gemiddeld ladingsoverschot over Multi Tour P(i,3)=(qmax*sum((B==n+1),2)-sum(G(i,:),2))/sum((B==n+1),2); % Routeafstand geinverteerd A=B((B¿0)); A=A((A¡n+1)); C=setdiff(1:n,A); Z=X; Z(C)=0; Z(C+n)=C;

93

% Orden M=[S(S(:,1)=P(i,1),1)]; M(:,2:4)=[S(S(:,1)=P(i,1),2:4)]; S=M; end S=S(1:grens,:); P=W(S(:,2),:); end

D.3

k.m


P(i,4)=1/tot afstand(Z,D,n);

function W = Collect(Route) (∼, ∼, ∼, ∼, ∼, ∼, n, ∼, ∼, ∼, ∼, ∼, ∼, ∼, ∼, ∼, ∼)=degegevens(); C=1:n; % Creeer de vector X die aanduidt naar waar de routes starten. X=zeros(1,2*n); X(n+1:2*n)=Route(2,:); for s=1:n if (sum((X(:)==s),2)==0) X(s)=s; end end

94

% Initialiseer matrix W rt=0; for s=1:n if ((X(s)==s)&&(sum(Route(5,:)==s,2)==0))


rt=rt+1; i=1; k=0; r=s; while (k =n+2) W(rt,i)=r; if (X(n+r)==n+1) i=i+1; W(rt,i)=n+1; r=Route(5,r); if (r==n+1) k=n+2; end else k=Route(5,X(n+r)); r=X(n+r); end i=i+1; end k=0; end end

95

Bijlage E

T ijd(GRTi, GRTj ) E.1

T ijd.m

96 function [aj, yj, GRT, GOT] = Tijd(i, j, yi, GRT, GOT, Qwagen) % Gegevens (T, Q, qmax, D, E, L, n, ∼, ∼, cq, ∼, qstop, ∼, Y0, YTH, ∼, ∼)=degegevens(); % Alle Q-waarden worden nu opgeroepen via index i + 1. Q(1) stelt dan de hoeveelheid voor die aangevuld wordt bij herbevoorrading. Q=[qmax-Qwagen; Q]; % Berekenen van de nodige waarden tij=TTT(yi+qstop+cq*Q(i+1), D(i*(n+1)+j), T); aj=yi+qstop+cq*Q(i+1)+tij; yj=max(E(j),aj); % Nakijken van de voorwaarden if (GRT+qstop+cq*Q(i+1)+tij>=270)

Bijlage E. T ijd(GRTi , GRTj )

limiet=270-GRT-cq*Q(i+1)-qstop; aj=yi+qstop+cq*Q(i+1)+limiet+45-15*(GOT==15)+TTT(yi+qstop+cq*Q(i+1)+limiet+45-15*(GOT==15),D(i*(n+1)+j) -TTTvoor(yi+qstop+cq*Q(i+1),yi+qstop+cq*Q(i+1)+limiet,T),T); yj=max(E(j),aj); GRT=TTT(yi+qstop+cq*Q(i+1)+limiet+45-15*(GOT==15),D(i*(n+1)+j)-TTTvoor(yi+qstop+cq*Q(i+1),yi+qstop+cq*Q(i+1) +limiet,T),T); if (yj-aj>=45) GRT=0; GOT=0; elseif (yj-aj>=15) GOT=15; else GOT=0; end elseif (yj-aj>=45) GRT=0; GOT=0; elseif ((yj-aj>=30)&&(GOT==15)) GRT=0; GOT=0; elseif (GRT +qstop+cq*Q(i+1)+ tij +qstop+cq*Q(j+1)>=270) aj=aj+45-15*(GOT==15); yj=max(E(j),aj); GRT=0; GOT=0; elseif (yj-aj>=15) GRT=GRT+qstop+cq*Q(i+1)+tij; GOT=15; else GRT=GRT+aj-yi;

97

E.2

T T T voor.m

Dit algoritme berekent hoeveel afstand is afgelegd in het de gedeeltelijke reistijd t∗∗ ij . function x = TTTvoor(tstart, teind, TI) eind=TI(3,TI(1,:)<=teind&(teind-60)<TI(1,:)); start=TI(3,TI(1,:)<=tstart&(tstart-60)<TI(1,:)); if (eind==start) x=TI(2,eind)*(teind-tstart); elseif (start==eind-1) x=TI(2,start)*(TI(1,start+1)-tstart); x=x+TI(2,eind)*(teind-TI(1,eind)); else x=TI(2,start)*(TI(1,start+1)-tstart); x=x+TI(2,eind)*(teind-TI(1,eind)); for i=start+1:eind-1 x=x+TI(2,i)*60; end end end

E.3


end end

Hr1.m

function Route = Hr(Qheden,Route,vi, vj,C,Delta, GRT, GOT)

98

% Inladen van de gegevens (T, Q, qmax, D, E, L, n, ∼, ∼, cq, ∼, qstop, ∼, Y0, YTH, ∼, ∼)=degegevens();

% Verbinding van vi naar vj vastleggen als vi gelijk is aan nul if (vi==0) yjdepot=max(E(vj)-TTTomg(E(vj),D(vj),T)-qstop-cq*qmax,Y0); yj=yjdepot+qstop+cq*qmax+TTT(yjdepot+qstop+cq*qmax,D(vj),T); Route(n+vj)=yjdepot; Route(2*n+vj)=yj; Qi=qmax-Q(vj); GRT=yj-yjdepot; GRT=0;


Qi=Qheden;

% Verbinding van vi naar vj vastleggen als vi niet gelijk is aan 0 else [∼, yj, GRTj, GOTj] = Tijd(vi, vj, Route(2*n+vi), GRT, GOT, Qi); [∼, yjdepot, GRTdepot, GOTdepot] = Tijd(vi, n+1, Route(2*n+vi), GRT, GOT, Qi); [∼, yjj, GRTjj, GOTjj] = Tijd(0, vj, yjdepot, GRTdepot, GOTdepot, Qi); if ((Qi-Q(vj)≥0)&&(yj+qstop+cq*Q(vj)+TTT(yj+qstop+cq*Q(vj),D(vj*(n+1)+(n+1)),T)≤YTH)&&(yj≤ L(vj))) t=1; GRT=GRTj; GOT=GOTj; elseif ((yjj+qstop+cq*Q(vj)+TTT(yjj+qstop+cq*Q(vj),D(vj*(n+1)+n+1),T)≤YTH)&&(yjj≤L(vj))) yj=yjj; GRT=GRTjj; GOT=GOTjj; t=2; else yjdepot=max(E(vj)-TTTomg(E(vj),D(vj),T)-qstop-cq*qmax,Y0); yj=yjdepot+qstop+cq*qmax+TTT(yjdepot+qstop+cq*qmax,D(vj),T); GRT=yj-yjdepot;

99

% Afhankelijk van welke type ’t-waarde’ wordt de Route verder benoemd if (t==1) Route(2*n+vj)=yj; Route(vi)=vj; Qi=Qi-Q(vj); elseif (t==2) Route(vi)=n+1; Route(n+vj)=yjdepot; Route(2*n+vj)=yj; Route(3*n+vi)=vj; Qi=qmax-Q(vj); elseif (t==3) Route(vi)=n+1; Route(n+vj)=yjdepot; Route(2*n+vj)=yj; Route(3*n+vi)=n+1; Qi=qmax-Q(vj); end end

100

% Gegevens instellen voor de rest van de ongerouteerde klanten te routeren. vi=vj; type=Inf; lowestNext=vj; y=Inf; ydepot=Inf;


GOT=0; t=3; end

101

% Verder verloop van het Nearest Neighbor Algorithm while(∼ isempty(C)) bestValue=inf; for j=1:size(C,2) [aj, yj, GRTj, GOTj] = Tijd(vi, C(j), Route(2*n+vi), GRT, GOT, Qi); [∼, yjdepot, GRTdepot, GOTdepot] = Tijd(vi, n+1, Route(2*n+vi), GRT, GOT, Qi); [ajj, yjj, GRTjj, GOTjj] = Tijd(0, C(j), yjdepot, GRTdepot, GOTdepot, Qi); if ((Qi-Q(C(j))>0)&&(yj+qstop+cq*Q(C(j))+TTT(yj+qstop+cq*Q(C(j)),D(C(j)*(n+1)+(n+1)),T)≤YTH)&&(yj≤L(C(j)))) g=Delta(1)*D(vi*(n+1)+C(j)) + Delta(2)*(yj-(Route(2*n+vi))) + Delta(3)*(L(C(j))-aj) + Delta(4)*(Qi-Q(C(j))); t=1; elseif ((yjj+qstop+cq*Q(C(j))+TTT(yjj+qstop+cq*Q(C(j)),D(C(j)*(n+1)+n+1),T)≤YTH)&&(yjj≤L(C(j)))) yj=yjj; aj = ajj GRTj=GRTjj; GOTj=GOTjj; g=Delta(1)*(D(vi*(n+1)+n+1)+D(C(j))) + Delta(2)*(yj-Route(2*n+vi)) + Delta(3)*(L(C(j))-aj) + Delta(3)*max(E(C(j))-aj,0) +Delta(4)*(qmax-Q(C(j))); t=2; else yjdepot=max(E(C(j))-TTTomg(E(C(j)),D(C(j)),T)-qstop-cq*qmax,Y0); yj=yjdepot+qstop+cq*qmax+TTT(yjdepot+qstop+cq*qmax,D(C(j)),T); GRTj=yj-yjdepot; GOTj=0; aj= Y0 + qstop + cq*qmax + TTT(Y0 + qstop + cq*qmax,D(C(j)),T); g=Delta(5) + Delta(1)*(D(vi*(n+1)+n+1)+D(C(j))) + Delta(2)*( yj-yjdepot + qstop+cq*Q(vi)+TTT(Route(2*n+vi)+qstop +cq*Q(vi),D(vi*(n+1)+n+1),T)) + Delta(3)*(L(C(j))-aj) + Delta(3)*max(E(C(j))-aj,0) + Delta(4)*(qmax-Q(C(j))); t=3; end


C=setdiff(C,vj);

Bijlage E. T ijd(GRTi , GRTj ) 102

if (g

C=setdiff(C,lowestNext); end d=find(Route==0); Route(d(1))=n+1; Route(3*n+d(1))=n+1;

103

Bibliografie [1] Agiv. Middenschalige kleurenorthofoto’s. http://geo-vlaanderen.agiv.be/geovlaanderen/kleurenortho/ (laatst bekeken op 29 juli 2010), 2010. [2] Colruyt. Op weg met een Colruyt-chauffeur. http://www.colruyt.be/colruyt/static/ (laatst bekeken op 26 juli 2010), 2009. [3] G. B. Dantzig and R.H. Ramser. The truck dispatching problem. Management Science 6, pages 80–91, 1959. [4] B. D. D´ıaz. The vrp web. http://neo.lcc.uma.es/radi-aeb/WebVRP (laatst bekeken op 16 juli 2010), 2007. [5] Digitach. Presentatie Tachograaf. www.digitach.be/NL/PDF/presn.pdf (laatst bekeken op 7 juli 2010), 2007. [6] M.A. Figliozzi. An iterative route construction and improvement algorithm for the vehicle routing problem with soft time windows. Transport. Res., Part C, 2009. [7] M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979. [8] S. Ichoua, M. Gendreau, and J.Y. Potvin. Vehicle dispatching with time-dependent travel times. European Journal of Operational Research, 144(2):379–396, 2003. [9] Catherine Maheux. Digitale tachograaf verplicht ... VBO, 2005. [10] Federale Overheidsdienst Mobiliteit-Vervoer. Samenwerkingsakkoord Federale Overheid - Gewesten - START/SITTER. http://www.start-sitter.be (laatst bekeken op 18 juni 2010), 2010. [11] Europees Parlement. Verordening (eg) nr. 561/2006. Publicatieblad van de Europese Unie, L 102/1:1–13, 2006. [12] H. Pohlheim. GEATbx: Tutorial and Parameter Options, 2006.

104

Bibliografie

105

[13] M. Savelsberg. Local search in routing problems with time windows. Annals of Operations Research, 4:285–305, 1985. [14] M. M. Solomon. Algorithms for the vehicle-routing and scheduling problems with time window constraints. Operations Research, 35(2):254–265., 1987.

 

Het Extended Vehicle Routing Probleem met tijdstipafhankelijke reistijden onderworpen aan rij- en rusttijdreglementering

Recommend Documents