The effectivity and easiness of Constraint Programming on the Vehicle Routing Problem
(2016) In LU-CS-EX 2016-19 EDA920 20152Department of Computer Science
- Abstract (Swedish)
- Vehicle Routing Problem (VRP) är en variant på det mer kända Han- delsresandeproblemet. VRP går i stort ut på att finna rutter för en flotta av fordon som ska besöka ett antal kunder och i vissa fall optimera dessa rutter för att minimera sträckan som fordonen färdas. Det förekommer ofta flera bivillkor, exempelvis att en viss kund måste besökas innan en viss tidpunkt.
Jag har undersökt lättheten i att lösa VRP med hjälp av constraint pro- grammering. För att göra detta implementerar jag tre metoder som löser pro- blemet med hjälp av constraint-programmeringssolvern JaCoP. Dessa jäm- förs med den öppna programvaran jsprit och den kommersiella programvaran OPTRAK vad gäller lätthet i implementation av programmen samt beräk- ningstid. De... (More) - Vehicle Routing Problem (VRP) är en variant på det mer kända Han- delsresandeproblemet. VRP går i stort ut på att finna rutter för en flotta av fordon som ska besöka ett antal kunder och i vissa fall optimera dessa rutter för att minimera sträckan som fordonen färdas. Det förekommer ofta flera bivillkor, exempelvis att en viss kund måste besökas innan en viss tidpunkt.
Jag har undersökt lättheten i att lösa VRP med hjälp av constraint pro- grammering. För att göra detta implementerar jag tre metoder som löser pro- blemet med hjälp av constraint-programmeringssolvern JaCoP. Dessa jäm- förs med den öppna programvaran jsprit och den kommersiella programvaran OPTRAK vad gäller lätthet i implementation av programmen samt beräk- ningstid. De kriterier som introduceras för att en metod ska klassas som enkel är som följer; det är möjligt att lägga till och ta bort bivillkor utan att änd- ra annan kod, bivillkor interagerar inte på ett onaturligt sätt, det är enkelt att förstå koden och slutligen att nya bivillkor inte kräver att man ändrar algoritmerna för programmet.
Det visar sig att constraint-programmering är enklare, men skulle kräva att kombineras med ytterligare teknologi för att ge bra lösningar. (Less) - Abstract
- The Vehicle Routing Problem (VRP) is a variant of the more famous Travel- ling Salesperson Problem. The VRP basically consists of finding the routes for a fleet of vehicles to visit a number of customers and in some cases op- timize this route to minimize distance traveled. Often there are many side constraints, e.g. a certain customer must be visited before a certain time.
I have investigated the easiness of using constraint programming for sol- ving the VRP. To do this I implement three methods that solve the problem using the constraint programming solver JaCoP. These methods are compa- red to the open source software jsprit and the commercial software OPTRAK in regards to ease of implementation of the programs and the quality of the... (More) - The Vehicle Routing Problem (VRP) is a variant of the more famous Travel- ling Salesperson Problem. The VRP basically consists of finding the routes for a fleet of vehicles to visit a number of customers and in some cases op- timize this route to minimize distance traveled. Often there are many side constraints, e.g. a certain customer must be visited before a certain time.
I have investigated the easiness of using constraint programming for sol- ving the VRP. To do this I implement three methods that solve the problem using the constraint programming solver JaCoP. These methods are compa- red to the open source software jsprit and the commercial software OPTRAK in regards to ease of implementation of the programs and the quality of the solution. The introduced criteria for a method to be deemed as easy are the following; it’s possible to add and remove side constraints without having to change other code, side constraints does not interact unnaturally, it is easy to understand the code and finally that new side constraints don’t require a change of the main solution method of the program.
It turns out that the constraint programming is easier, but would need to be combined with other technology to give good solutions. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/student-papers/record/8884143
- author
- Pettersson, Emil LU
- supervisor
- organization
- alternative title
- Undersökning av Constraint Programmerings effektivitet och enkelhet på Vehicle Routing Problem
- course
- EDA920 20152
- year
- 2016
- type
- H3 - Professional qualifications (4 Years - )
- subject
- keywords
- Constraint programming, Vehicle Routing Problem, jsprit, JaCoP, comparison
- publication/series
- LU-CS-EX 2016-19
- report number
- LU-CS-EX 2016-19
- ISSN
- 1650-2884
- language
- Swedish
- id
- 8884143
- date added to LUP
- 2016-06-22 12:35:25
- date last changed
- 2016-06-22 12:35:25
@misc{8884143,
abstract = {{The Vehicle Routing Problem (VRP) is a variant of the more famous Travel- ling Salesperson Problem. The VRP basically consists of finding the routes for a fleet of vehicles to visit a number of customers and in some cases op- timize this route to minimize distance traveled. Often there are many side constraints, e.g. a certain customer must be visited before a certain time.
I have investigated the easiness of using constraint programming for sol- ving the VRP. To do this I implement three methods that solve the problem using the constraint programming solver JaCoP. These methods are compa- red to the open source software jsprit and the commercial software OPTRAK in regards to ease of implementation of the programs and the quality of the solution. The introduced criteria for a method to be deemed as easy are the following; it’s possible to add and remove side constraints without having to change other code, side constraints does not interact unnaturally, it is easy to understand the code and finally that new side constraints don’t require a change of the main solution method of the program.
It turns out that the constraint programming is easier, but would need to be combined with other technology to give good solutions.}},
author = {{Pettersson, Emil}},
issn = {{1650-2884}},
language = {{swe}},
note = {{Student Paper}},
series = {{LU-CS-EX 2016-19}},
title = {{The effectivity and easiness of Constraint Programming on the Vehicle Routing Problem}},
year = {{2016}},
}