Show simple item record

AuthorLeggieri, Valeria
AuthorHaouari, Mohamed
Available date2020-08-20T08:06:21Z
Publication Date2017
Publication NameEuropean Journal of Operational Research
ResourceScopus
ISSN3772217
URIhttp://dx.doi.org/10.1016/j.ejor.2017.05.039
URIhttp://hdl.handle.net/10576/15704
AbstractWe propose compact formulations for the symmetric and asymmetric capacitated vehicle routing problems. These formulations are obtained by lifting, using the Reformulation-Linearization Technique, a novel polynomial size ordered path-based formulation. We show that the strongest proposed formulation is equivalent to the strongest multi-commodity flow formulation presented so far. In addition, we propose polynomial size valid inequalities that aim at further tightening the proposed formulations. Also, the tightest formulation is extended to model the fleet size and mix vehicle routing problem with fixed costs. We show that the new derived model is not comparable with a state-of-the-art polynomial length formulation. We present the results of computational experiments that demonstrate the tightness of the proposed formulations and the impact of the valid inequalities. 2017 Elsevier B.V.
Languageen
PublisherElsevier B.V.
SubjectCapacitated vehicle routing problem
Compact formulations
Heterogeneous VRP
Reformulation-Linearization Technique
Transportation
TitleLifted polynomial size formulations for the homogeneous and heterogeneous vehicle routing problems
TypeArticle
Pagination755-767
Issue Number3
Volume Number263
dc.accessType Abstract Only


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record