A column generation scheme for the fixed fleet heterogeneous vehicle routing problem
2005 (English)Report (Other academic)
We present an optimizing column generation procedure for solving the vehicle routing problem with a fixed heterogeneous fleet of vehicles; if the method is used in a truncated fashion it turns into a heuristic. The method is based on a new mathematical formulation, which includes a new type of valid inequalities, strengthened by the use of Chvátal-Gomory rounding, and a Lagrangian dualization of this formulation. The dual problem is attacked by subgradient optimization and a near-optimal dual solution obtained is used for enumerating routes that are promising candidates for being used in an optimal solution. These routes are collected in a set partitioning problem, which is finally solved, and an upper bound to the optimal objective value is obtained. The method is evaluated on a set of small-scale test instances. The valid inequalities improves the lower bound significantly: the improvement depends on the ratio between total customer demand and total vehicle capacity. The qualities of the upper bounds varies quite much among the instances.
Place, publisher, year, edition, pages
Linköping: Linköpings universitet , 2005.
, LiTH-MAT-R, 12
IdentifiersURN: urn:nbn:se:liu:diva-29699Local ID: 15092OAI: oai:DiVA.org:liu-29699DiVA: diva2:250516