Polyhedral results for a vehicle routing problem (Q1176821): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Vicente Campos / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Angel Corberán / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Enrique Mota / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Reinhardt Euler / rank | |||
Normal rank |
Revision as of 17:45, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Polyhedral results for a vehicle routing problem |
scientific article |
Statements
Polyhedral results for a vehicle routing problem (English)
0 references
25 June 1992
0 references
Let \(G=(V,E)\) be the complete, undirected graph on \(n\) vertices. With any vertex we can associate a demand: 0 for vertex 1, the depot, and 1 for every other vertex. For any edge \(\{i,j\}\) we are given a distance \(c_{ij}\), and, finally, a fleet of \(K\) identical vehicles of integer capacity \(q\geq 2\) and based at the depot is available. The vehicle routing problem (VRP) considered in this paper is the following: Determine \(k\) routes for the vehicles such that: (1) every route begins and ends at the depot; (2) each vertex \(i\neq 1\) is visited exactly once and by only one vehicle; (3) the number of vertices visited by a vehicle never exceeds its capacity \(q\); (4) the total distance is minimized. This problem can be formulated as a 0-1 linear programming problem, involving degree, subtour-elimination and capacity constraints. The vehicle routing polytope \(P_{\hbox{VRP}}\) is defined to be the convex hull of all feasible solutions of this 0-1 problem. The authors determine the dimension of \(P_{\hbox{VRP}}\) depending on the number of customers, the number of vehicles and their capacity. They study the facial structure of \(P_{\hbox{VRP}}\) and establish conditions under which the trivial, the subtour elimination and the capacity constraints are facet-defining for \(P_{\hbox{VRP}}\).
0 references
complete, undirected graph
0 references
vehicle routing
0 references
0-1 linear programming
0 references
facial structure
0 references
subtour elimination
0 references