Vehicle routing problem: Difference between revisions

Revision as of 10:33, 4 July 2025

Revision as of 11:44, 8 July 2025

Line 49:

==Exact solution methods==

There are three main different approaches to modelling the VRP using [[Integer Programming|mixed-integer linear programming]] (MILP):<ref name=toth />

#'''Vehicle flow formulations'''—this uses integer variables associated with each arc that count the number of times that the edge is traversed by a vehicle. It is generally used for basic VRPs. This is good for cases where the solution cost can be expressed as the sum of any costs associated with the arcs. However it can't be used to handle many practical applications.<ref name=toth />

#'''Commodity flow formulations'''—additional integer variables are associated with the arcs or edges which represent the flow of commodities along the paths travelled by the vehicles. This has only recently been used to find an exact solution.<ref name=toth />

#'''Set-partitioning'''—This approach models the VRP as a [[set cover problem]], in which the locations make up the universe and the set of all feasible routes ([[Cycle_(graph_theory)|cycles]]) make up the collection of sets to choose from.<ref>{{cite journal |last1=Balinski |first1=M. L. |last2=Quandt |first2=R. E. |title=On an Integer Program for a Delivery Problem |journal=Operations Research |date=April 1964 |volume=12 |issue=2 |pages=300–304 |doi=https://doi.org/10.1287/opre.12.2.300}}</ref> The problem can then be modelled using a [[Set_cover_problem#Linear_program_formulation|linear programming model for the weighted set cover problem]], with the weight of a route set to its cost. Modelling the VRP in this way will possibly result in an exponential number of binary variables in the linear program, as one is associated with each of a potentially exponential number of feasible routes.<ref name=toth />

#'''Set partitioning problem'''—These have an exponential number of [[binary data|binary variables]] which are each associated with a different feasible circuit. The VRP is then instead formulated as a set partitioning problem which asks what is the collection of circuits with minimum cost that satisfy the VRP constraints. This allows for very general route costs.<ref name=toth />

===Vehicle flow formulations===