A Granular Local Search Matheuristic for a Heterogeneous Fleet Vehicle Routing Problem with Stochastic Travel Times

Ramon Faganello Fachini (), Vinícius Amaral Armentano () and Franklina Maria Bragion Toledo ()
Additional contact information
Ramon Faganello Fachini: Universidade Estadual de Campinas
Vinícius Amaral Armentano: Universidade Estadual de Campinas
Franklina Maria Bragion Toledo: Instituto de Ciências Matemáticas e de Computação, Universidade de São Paulo

Networks and Spatial Economics, 2022, vol. 22, issue 1, No 2, 33-64

Abstract: Abstract This paper addresses a multi-attribute variant of the vehicle routing problem which encompasses a heterogeneous fixed fleet, flexible time windows and stochastic travel times. The objective is to minimize the sum of the transportation and the service costs. The former comprises the vehicle fixed costs and route variable costs, and the latter corresponds to the penalty costs for violating customer time windows. The problem is formulated as a two-stage stochastic mixed-integer program with recourse and solved by a granular local search matheuristic. The stochastic travel times are approximated by a finite set of scenarios generated by Burr type XII distribution. Extensive computational tests are performed on 216 benchmark instances, and the advantages of both flexible windows and stochastic travel times are stressed. The experiments show that, compared to a state-of-art mathematical programming solver, the developed matheuristic found better solutions in 81% of the instances within shorter computational times. The proposed solution method also far outperformed an alternative decomposition algorithm based on the augmented Lagrangian relaxation. Furthermore, the flexible time windows yielded overall cost savings for 68% of the instances compared to the solutions obtained for hard time window problems. Finally, explicitly modeling the stochastic travel times provided 66% more feasible solutions than the adoption of a deterministic model with the random parameters fixed at their expected values.

Keywords: Vehicle routing problem; Heterogeneous fleet; Flexible time windows; Stochastic travel times; Matheuristic; Granular local search (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11067-021-09553-6 Abstract (text/html)
Access to full text is restricted to subscribers.

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:kap:netspa:v:22:y:2022:i:1:d:10.1007_s11067-021-09553-6

Ordering information: This journal article can be ordered from
http://www.springer. ... ce/journal/11067/PS2

DOI: 10.1007/s11067-021-09553-6

Access Statistics for this article

Networks and Spatial Economics is currently edited by Terry L. Friesz

More articles in Networks and Spatial Economics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().