Skip to Main content Skip to Navigation
Journal articles

Efficient Heuristics for the Heterogeneous Fleet Multitrip VRP with Application to a Large-Scale Real Case

Abstract : The basic Vehicle Routing Problem (VRP) consists of computing a set of trips of minimum total cost, to deliver fixed amounts of goods to customers with a fleet of identical vehicles. Few papers address the case with several types of vehicles (heterogeneous fleet). Most of them assume an unlimited number of vehicles of each type, to dimension the fleet from a strategic point of view. This paper tackles the more realistic tactical or operational case, with a fixed number of vehicles of each type, and the optional possibility for each vehicle to perform several trips. It describes several heuristics, including a very efficient one that progressively merges small starting trips, while ensuring that they can be performed by the fleet. This heuristic seeks to minimize the number of required vehicles as a secondary objective. It outperforms classical VRP heuristics, can easily handle various constraints, and gives very good initial solutions for a tabu search method. The real case of a French manufacturer of furniture with 775 destination stores is presented.
Document type :
Journal articles
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02493347
Contributor : Daniel Gavrysiak <>
Submitted on : Thursday, February 27, 2020 - 4:52:34 PM
Last modification on : Friday, February 28, 2020 - 1:31:19 AM

Links full text

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Christian Prins. Efficient Heuristics for the Heterogeneous Fleet Multitrip VRP with Application to a Large-Scale Real Case. Journal of Mathematical Modelling and Algorithms, Springer Verlag, 2002, 1 (2), pp.135-150. ⟨10.1023/A:1016516326823⟩. ⟨hal-02493347⟩

Share

Metrics

Record views

37