Premium
Reverse multistar inequalities and vehicle routing problems with a lower bound on the number of customers per route
Author(s) -
Gouveia Luis,
RieraLedesma Jorge,
SalazarGonzález JuanJosé
Publication year - 2013
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21481
Subject(s) - vehicle routing problem , upper and lower bounds , context (archaeology) , inequality , routing (electronic design automation) , constraint (computer aided design) , computer science , mathematics , mathematical optimization , computer network , geography , mathematical analysis , geometry , archaeology
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