INTEC   05402
INSTITUTO DE DESARROLLO TECNOLOGICO PARA LA INDUSTRIA QUIMICA
Unidad Ejecutora - UE
artículos
Título:
"A Cluster-based Optimization Approach for the Multi-depot Heterogeneous Fleet Vehicle Routing Problem with Time Windows"
Autor/es:
DONDO, RODOLFO G.; CERDA, JAIME
Revista:
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Editorial:
Elsevier
Referencias:
Lugar: Amsterdam; Año: 2007 vol. 176 p. 1478 - 1507
ISSN:
0377-2217
Resumen:
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.