The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?". It generalises the well-known Travelling Salesman Problem (TSP). It first appeared in a paper by George Dantzig and John Ramser in 1959 [1], in which first algorithmic approach was written and was applied to petrol deliveries. Often, the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. The objective of the VRP is to minimize the total route cost. In 1964, Clarke and Wright improved on Dantzig and Ramser's approach using an effective greedy approach called the savings algorithm.
Determining the optimal solution is an NP-hard [2] problem in combinatorial optimization, so the size of problems that can be solved optimally is limited . The commercial solvers therefore tend to use heuristics due to the size of real world VRPs and the frequency that they may have to be solved.
The VRP has many obvious applications in industry. In fact the use of computer optimisation programs can give savings of 5% to a company [3] as transportation is usually a significant component of the cost of a product (10%) [4] - indeed the transportation sector makes up 10% of the EU GDP. Consequently, any savings created by the VRP even less than 5% are significant [5] .
The VRP concerns the service of a delivery company. How things are delivered from one or more depots which has a given set of home vehicles and operated by a set of drivers who can move on a given road network to a set of customers. It asks for a determination of a set of routes, S, (one route for each vehicle that must start and finish at its own depot) such that all customers' requirements and operational constraints are satisfied and the global transportation cost is minimised. This cost may be monetary, distance or otherwise [2].
The road network can be described using a
graph (mathematics) where the arcs are roads and vertices are junctions between them. The arcs may be directed or undirected due to the possible presence of one way streets or different costs in each direction. Each arc has an associated cost which is generally its length or travel time which may be dependent on vehicle type Cite error: A <ref>
tag is missing the closing </ref>
(see the
help page).
Several software vendors have built software products to solve the various VRP problems. Numerous articles are available for more detail on their research and results.
Although VRP is related to the Job Shop Scheduling Problem, the two problems are typically solved using different techniques. [6]
Name (alphabetically) |
License | API language | Brief info |
---|---|---|---|
jsprit | LGPL | Java | lightweight, java based, open source toolkit for solving rich VRPs. link An Excel-compatible user interface for jsprit is available with mapping, reporting and route editing functionality. link |
Open-VRP | LLGPL | Lisp | Open-VRP for Lisp, hosted on Github. link |
OptaPlanner | Apache License | Java | Open Source Java constraint solver ( optaplanner.org) with VRP examples. |
SYMPHONY | Common Public License 1.0 | Open-source solver for mixed-integer linear programs (MILPs) with support for VRPs. link | |
VRP Spreadsheet Solver | Creative Commons Attribution 4.0 International License | Microsoft Excel and VBA based open source solver, with a link to public GIS for data retrieval. link Video tutorial link | |
vrphlibrary (VRPH) | Common Public License 1.0 | Home page of open source VRPH software link and hosting page on COIN-OR link. | |
vroom | ? | Open source libraries for the VRP and dynamic VRP. link |
{{
cite book}}
: |first1=
has generic name (
help); |first1=
missing |last1=
(
help)CS1 maint: multiple names: authors list (
link)
{{
cite book}}
: |last1=
has generic name (
help)CS1 maint: multiple names: authors list (
link)
{{
cite book}}
: |last1=
has generic name (
help)CS1 maint: multiple names: authors list (
link)
{{
cite journal}}
: CS1 maint: date and year (
link)The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?". It generalises the well-known Travelling Salesman Problem (TSP). It first appeared in a paper by George Dantzig and John Ramser in 1959 [1], in which first algorithmic approach was written and was applied to petrol deliveries. Often, the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. The objective of the VRP is to minimize the total route cost. In 1964, Clarke and Wright improved on Dantzig and Ramser's approach using an effective greedy approach called the savings algorithm.
Determining the optimal solution is an NP-hard [2] problem in combinatorial optimization, so the size of problems that can be solved optimally is limited . The commercial solvers therefore tend to use heuristics due to the size of real world VRPs and the frequency that they may have to be solved.
The VRP has many obvious applications in industry. In fact the use of computer optimisation programs can give savings of 5% to a company [3] as transportation is usually a significant component of the cost of a product (10%) [4] - indeed the transportation sector makes up 10% of the EU GDP. Consequently, any savings created by the VRP even less than 5% are significant [5] .
The VRP concerns the service of a delivery company. How things are delivered from one or more depots which has a given set of home vehicles and operated by a set of drivers who can move on a given road network to a set of customers. It asks for a determination of a set of routes, S, (one route for each vehicle that must start and finish at its own depot) such that all customers' requirements and operational constraints are satisfied and the global transportation cost is minimised. This cost may be monetary, distance or otherwise [2].
The road network can be described using a
graph (mathematics) where the arcs are roads and vertices are junctions between them. The arcs may be directed or undirected due to the possible presence of one way streets or different costs in each direction. Each arc has an associated cost which is generally its length or travel time which may be dependent on vehicle type Cite error: A <ref>
tag is missing the closing </ref>
(see the
help page).
Several software vendors have built software products to solve the various VRP problems. Numerous articles are available for more detail on their research and results.
Although VRP is related to the Job Shop Scheduling Problem, the two problems are typically solved using different techniques. [6]
Name (alphabetically) |
License | API language | Brief info |
---|---|---|---|
jsprit | LGPL | Java | lightweight, java based, open source toolkit for solving rich VRPs. link An Excel-compatible user interface for jsprit is available with mapping, reporting and route editing functionality. link |
Open-VRP | LLGPL | Lisp | Open-VRP for Lisp, hosted on Github. link |
OptaPlanner | Apache License | Java | Open Source Java constraint solver ( optaplanner.org) with VRP examples. |
SYMPHONY | Common Public License 1.0 | Open-source solver for mixed-integer linear programs (MILPs) with support for VRPs. link | |
VRP Spreadsheet Solver | Creative Commons Attribution 4.0 International License | Microsoft Excel and VBA based open source solver, with a link to public GIS for data retrieval. link Video tutorial link | |
vrphlibrary (VRPH) | Common Public License 1.0 | Home page of open source VRPH software link and hosting page on COIN-OR link. | |
vroom | ? | Open source libraries for the VRP and dynamic VRP. link |
{{
cite book}}
: |first1=
has generic name (
help); |first1=
missing |last1=
(
help)CS1 maint: multiple names: authors list (
link)
{{
cite book}}
: |last1=
has generic name (
help)CS1 maint: multiple names: authors list (
link)
{{
cite book}}
: |last1=
has generic name (
help)CS1 maint: multiple names: authors list (
link)
{{
cite journal}}
: CS1 maint: date and year (
link)