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.