Optimization Online


Stronger Multi-Commodity Flow Formulations of the Capacitated Vehicle Routing Problem

Adam N Letchford (A.N.Letchford***at***lancaster.ac.uk)
Juan-Jose Salazar-Gonzalez (jjsalaza***at***ull.es)

Abstract: The Capacitated Vehicle Routing Problem is a much-studied (and strongly NP-hard) combinatorial optimization problem, for which many integer programming formulations have been proposed. We present some new multi-commodity flow (MCF) formulations, and show that they dominate all of the existing ones, in the sense that their continuous relaxations yield stronger lower bounds. Moreover, we show that the relaxations can be strengthened, in pseudo-polynomial time, in such a way that all of the so-called knapsack large multistar (KLM) inequalities are satisfied. The only other relaxation known to satisfy the KLM inequalities, based on set partitioning, is strongly NP-hard to solve. Computational results demonstrate that the new MCF relaxations are significantly stronger than the previously known ones.

Keywords: vehicle routing, cutting planes, multi-commodity flows, integer programming

Category 1: Combinatorial Optimization

Category 2: Applications -- OR and Management Sciences (Transportation )

Citation: Eventually published as: A.N. Letchford & J.J. Salazar (2015) Stronger multi-commodity flow formulations of the capacitated vehicle routing problem. Eur. J. Oper. Res., 244(3), 730-738.


Entry Submitted: 06/19/2014
Entry Accepted: 06/20/2014
Entry Last Modified: 05/19/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society