Polyhedral results for a vehicle routing problem (Q1176821)

From MaRDI portal
Revision as of 16:45, 10 February 2024 by RedirectionBot (talk | contribs) (‎Removed claims)
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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references