Spanning Cover Inequalities for the Capacitated Vehicle Routing Problem

• Guilherme G. Arcencio UFSCar
• Matheus T. Mattioli UFSCar
• Pedro H. D. B. Hokama UNIFEI https://orcid.org/0000-0002-3734-7679
• Mário César San Felice UFSCar https://orcid.org/0000-0001-6476-4534

DOI: https://doi.org/10.5753/etc.2021.16387

Resumo

In the k-Minimum Spanning Subgraph problem with d-Degree Center we want to find a minimum cost spanning connected subgraph with n - 1 + k edges and at least degree d in the center vertex, with n being the number of vertices. In this paper we describe an algorithm for this problem and present correctness demonstrations which we believe are simpler than those found in the literature. A solution for the k-Minimum Spanning Subgraph problem with d-Degree can be used to formulate spanning cover inequalities for the capacitated vehicle routing problem.

Palavras-chave: Lower Bounds, Minimum Spanning Subgraph, k-Degree Center Tree Problem

Referências

Balas, E. (1975). Facets of the knapsack polytope. Mathematical programming, 8(1):146–164.

Christofides, N., Mingozzi, A., and Toth, P. (1981). Exact algorithms for the vehiclerouting problem, based on spanning tree and shortest path relaxations. Mathematical programming, 20(1):255–282.

Fisher, M. L. (1994). Optimal solution of vehicle routing problems using minimum k-trees. Operations research, 42(4):626–642.

Wolsey, L. A. (1975). Faces for a linear inequality in 0–1 variables. Mathematical Pro-gramming, 8(1):165–178.