INTEGER LINEAR-PROGRAMMING FORMULATION FOR VEHICLE-ROUTING PROBLEMS

A recently proposed integer linear programming formulation for the vehicle routing problems is found to have an error; in particular the distance constraint described is not sufficiently restrictive. The authors show that one specific constraint is designed to limit the maximum cost of a route, but the proof for this is not given, and if examined carefully the constraint is seen not to work. The difficulty has arisen because the constraint is not defined for the depot, and hence distances to and from the depot are omitted.