Advanced

The effectivity and easiness of Constraint Programming on the Vehicle Routing Problem

Pettersson, Emil LU (2016) In LU-CS-EX 2016-19 EDA920 20152
Department 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:
author
Pettersson, Emil LU
supervisor
organization
alternative title
Undersökning av Constraint Programmerings effektivitet och enkelhet på Vehicle Routing Problem
course
EDA920 20152
year
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},
  keyword      = {Constraint programming,Vehicle Routing Problem,jsprit,JaCoP,comparison},
  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},
}