Publications
International Journal of Advanced Network, Monitoring and Controls
Xi'an Technological University
Subject: Computer Science, Software Engineering
eISSN: 2470-8038
SEARCH WITHIN CONTENT
An Efficient Density-Based Clustering Algorithm for the Capacitated Vehicle Routing Problem
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: https://doi.org/10.1109/iccnea.2017.96
License : (CC BY-NC-ND 4.0)
Published Online: 10-April-2018
- ARTICLE
- FIGURES & TABLES
- REFERENCES
- EXTRA FILES
- COMMENTS
ARTICLE
ABSTRACT
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.
FIGURES & TABLES
REFERENCES
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 G，Wright 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 H，Jameson 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.