A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet

Puca Huachi Vaz Penna (), Anand Subramanian (), Luiz Satoru Ochi (), Thibaut Vidal () and Christian Prins ()
Additional contact information
Puca Huachi Vaz Penna: Universidade Federal de Ouro Preto
Anand Subramanian: Universidade Federal da Paraíba
Luiz Satoru Ochi: Universidade Federal Fluminense
Thibaut Vidal: Pontifícia Universidade Católica do Rio de Janeiro
Christian Prins: Université de Technologie de Troyes

Annals of Operations Research, 2019, vol. 273, issue 1, No 2, 5-74

Abstract: Abstract We consider a family of rich vehicle routing problems (RVRP) which have the particularity to combine a heterogeneous fleet with other attributes, such as backhauls, multiple depots, split deliveries, site dependency, open routes, duration limits, and time windows. To efficiently solve these problems, we propose a hybrid metaheuristic which combines an iterated local search with variable neighborhood descent, for solution improvement, and a set partitioning formulation, to exploit the memory of the past search. Moreover, we investigate a class of combined neighborhoods which jointly modify the sequences of visits and perform either heuristic or optimal reassignments of vehicles to routes. To the best of our knowledge, this is the first unified approach for a large class of heterogeneous fleet RVRPs, capable of solving more than 12 problem variants. The efficiency of the algorithm is evaluated on 643 well-known benchmark instances, and 71.70% of the best known solutions are either retrieved or improved. Moreover, the proposed metaheuristic, which can be considered as a matheuristic, produces high quality solutions with low standard deviation in comparison with previous methods. Finally, we observe that the use of combined neighborhoods does not lead to significant quality gains. Contrary to intuition, the computational effort seems better spent on more intensive route optimization rather than on more intelligent and frequent fleet re-assignments.

Keywords: Rich vehicle routing; Heterogeneous fleet; Matheuristics; Iterated local search; Set partitioning (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-017-2642-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:273:y:2019:i:1:d:10.1007_s10479-017-2642-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-017-2642-9

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().