Home > Department of Mathematics > Seminars > OR Seminar Series > Academic year 2013-14 > Stronger multi-commodity flow formulations for the capacitated vehicle routing problem
How to contact us

 

LSE 10 logo master_6


Department of Management
London School of Economics and Political Science
Houghton Street

London WC2A 2AE

  

Enquiries: dom.events@lse.ac.uk 

  

Follow us online

Facebook-Square-38x38Twitter-square-38x38Youtube-square-38x38

 

Stronger multi-commodity flow formulations for the capacitated vehicle routing problem

Wednesday 21st May 2014, 4.00pm

Graham Wallace Room, LSE

Adam Letchford

Lancaster University

Personal profile


Abstract:

The capacitated vehicle routing problem (CVRP) is a much-studied NP-hard combinatorial optimization problem.  Many different integer programming formulations have been proposed for the CVRP, including so-called single-commodity flow (SCF) and multi-commodity flow (MCF) formulations.  We review these formulations, and then present two new MCF formulations.  We show that they dominate all of the existing SCF and MCF formulations, in the sense that their continuous relaxations yield stronger lower bounds.  Some preliminary computational results will also be presented.  This talk is based on joint work with Professor Juan-Jose' Salazar from the University of La Laguna.

Share:Facebook|Twitter|LinkedIn|

 

A-Letchford