An Efficient Density-Based Clustering Algorithm for the Capacitated Vehicle Routing Problem


Share / Export Citation / Email / Print / Text size:

International Journal of Advanced Network, Monitoring and Controls

Xi'an Technological University

Subject: Computer Science, Software Engineering


eISSN: 2470-8038





Volume / Issue / page

Related articles

VOLUME 2 , ISSUE 4 (December 2017) > List of articles

An Efficient Density-Based Clustering Algorithm for the Capacitated Vehicle Routing Problem

Jiashan Zhang

Keywords : CVRP, Two-phase heuristic, Density-based clustering algorithm, Max-min ant system

Citation Information : International Journal of Advanced Network, Monitoring and Controls. Volume 2, Issue 4, Pages 161-165, DOI:

License : (CC BY-NC-ND 4.0)

Published Online: 10-April-2018



The capacitated vehicle routing problem (CVRP) is one of the most challenging problems in the optimization of distribution. Most approaches can solve case studies involving less than 100 nodes to optimality, but time-consuming. To overcome the limitation, this paper presents a novel two-phase heuristic approach for the capacitated vehicle routing problem. Phase I aims to identifying sets of cost-effective feasible clusters through an improved density-based clustering algorithm. Phase II assigns clusters to vehicles and sequences them on each tour. Max-min ant system is used to order nodes within clusters . The simulation results indicate efficiency of the proposed algorithm.

Content not available PDF Share



PaoloT, Daniele V. Models, relaxations and exact approaches for the capacitated vehicle routing problem [J]. Discrete Applied Mathematics, 2002, 123: 487-512.


Gillett B, Miller L. A heuristic for the vehicle dispatching problem. Operations Researeh,1974,22:340-349.


Z. W. Qu, L. N. Cai et al, Solution framework for the large scale vehicle de-liver/collection problem, Journal of Tsinghua University (Sci. & Tech.), vol.44, no.5, pp.581-584,2004.


Y. F. Ouyang, Design of vehicle routing zones for large-scale distribution systems,Transportation Research Part B: Methodological, vol.41, no.10, pp.1079-1093, 2014.


Ester M. et al. A density-based algorithm for discovering clusters in large spatial databases with noise. Proceedings of 2nd Int'1 Conf, on

Knowledge Discovery and Data Mining (KDD'96), Portland, Oregon, Aug. 1996, pp. 226-231.


Dantzig, G., Ramser, J.. The truck dispatching problem. Management Science 6 (1), 80-91, 1959.


CIarke GWright J.W .Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, 1964,12:568-581.


Gillett B, Miller L.A heuristic for the vehicle dispatching problem. Operations Researeh,1974,22:340-349.


Mole R HJameson S R.A . Sequential Route-building Algorithm Employing Generalized Savings Criterion. Operational Research Quarterly,1976,27:503-511.


F. Glover, Tabu search and adaptive memory programming-Advances, applications, and challenges,Interfaces in Computer Science and Operations Research, 1996.


Pisinger D, Ropke S .A general heuristic for vehicle routing problems. Computers & Operations Research 2012,34:2403-2435.


B. Dorronsoro, D. Arias, A Grid-based hybrid cellular genetic algorithm for very large instances of the VRP. Parallel and Grid Computing for Optimization, PGCO 2007.


Czech Z. J, Czarnas P. Parallel Simulated Annealing for the Vehicle Routing Problem with Time Windows. Proceedings of the 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, 2015: 376-379.


Fisher, M., Jaikumar, R.. A generalized assignment heuristic for vehicle routing. Networks 11 (2), 109-124, 1981.


T. Stützle, H.H. Hoos, The MAX–MIN ant system and local search for the traveling salesman problem, Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC97), IEEE Press, Piscataway, USA, 1997, pp. 309-314.