Reverse multistar inequalities and vehicle routing problems with a lower bound on the number of customers per route

Journal Article


This article analyzes inequalities derived by projecting out the flow variables of a single‐commodity flow model for a vehicle routing problem. These inequalities are called reverse multistar (RMS) inequalities and are related to the MS inequalities analyzed and used in other articles. Although the MS RMS inequalities are irrelevant for some vehicle routing problems, in others they are fundamental. The article presents a vehicle routing problem in which the RMS are of interest. It is called the vehicle routing problem with lower and upper bound capacities (LU‐VRP). It concerns a vehicle routing problem with one depot and a homogeneous fleet of vehicles. All the customers have a unit demand, and there are upper and lower bounds on the demand covered by each vehicle. New families of inequalities are derived by strengthening the RMS inequalities. Computational experiments show that the new inequalities are useful when solving LU‐VRP instances. The experiments are based on variations of symmetric and asymmetric VRP library (VRPLIB) instances with up to 100 customers. The constraint on a minimum number of customers served in each route is implicit in the unit‐demand capacitated vehicle routing problem with a fixed number of vehicles. Therefore, the article also evaluates the impact of using the lower bound inequalities developed in the context of this variant. It is still unknown whether the new inequalities can help solve it or not. Our theoretical analysis suggests that one of the families of developed inequalities is not implied by other standard inequalities. This prompts us to pursue studies in the search for other families of lower bound based inequalities for this variant. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.