A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows
By R. Dondo, Jaime Cerdá. European Journal of Operational Research, 2007
331 citations recorded by the source corpus.
This paper presents a novel three-phase heuristic/algorithmic approach for the multi-depot routing problem with time windows and heterogeneous vehicles. It has been derived from embedding a heuristic-based clustering algorithm within a VRPTW optimization framework. To this purpose, a rigorous MILP mathematical model for the VRPTW problem is first introduced. Likewise other optimization approaches, the new formulation can efficiently solve case studies involving at most 25 nodes to optimality. To overcome this limitation, a preprocessing stage clustering nodes together is initially performed to yield a more compact cluster-based MILP problem formulation. In this way, a hierarchical hybrid procedure involving one heuristic and two algorithmic phases was developed. Phase I aims to identifying a set of cost-effective feasible clusters while Phase II assigns clusters to vehicles and sequences them on each tour by using the cluster-based MILP formulation. Ordering nodes within clusters and scheduling vehicle arrival times at customer locations for each tour through solving a small MILP model is finally performed at Phase III. Numerous benchmark problems featuring different sizes, clustered/random customer locations and time window distributions have been solved at acceptable CPU times.
Subfields: Building and Construction, Industrial and Manufacturing Engineering
View Paper: https://www.semanticscholar.org/paper/31828fecefc85c6b864e17351be56561524cc53c
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Building and Construction
In Industrial and Manufacturing Engineering
Citations in the corpus
- Industrial aspects and literature survey: Fleet composition and routing (2010, methodology): “Time windows are introduced to the FSMVRPMD by Dondo and Cerda [45], when developing a three-phase approach for the problem.”
- A mathematical model and a solving procedure for multi-depot vehicle routing problem with fuzzy time window and heterogeneous vehicle (2014, background): “Although the single-depot VRPs have attracted so much attention, they are not suitable for some cases where a company has more than one depot [6].”
- A survey of variants and extensions of the location-routing problem (2015, methodology): “The second one is a two-index arc-variable formulation based on the MDVRP formulation described in (Dondo and Cerdá 2007), the third one extends the two-index arc-variable standard LRP formulation by Prins et al. (2006a), and the fourth one is a path variable formulation.”