An Enhanced ABC algorithm to Solve the Vehicle Routing Problem with Time Windows
Article Sidebar
Main Article Content
Abstract
This work proposes an enhanced artificial bee colony algorithm (ABC) to solve the vehicle routing problem with time windows (VRPTW). In this work, the fuzzy technique, scatter search method, and SD-based selection method are combined into the artificial bee colony algorithm. Instead of randomly producing the new solution, the scout randomly chooses the replacement solution from the abandoned solutions from the onlooker bee stage. Effective customer location networks are constructed in order to minimize the overall distance. The proposed algorithm is tested on the Solomon benchmark dataset where customers live in different geographical locations. The results from the proposed algorithm are shown in comparison with other algorithms in the literature. The findings from the computational results are very encouraging. Compared to other algorithms, the proposed algorithm produces the best result for all testing problem sets. More significantly, the proposed algorithm obtains better quality than the other algorithms for 39 of the 56 problem instances in terms of vehicle numbers. The proposed algorithm obtains a better number of vehicles and shorter distances than the other algorithm for 20 of the 39 problem instances.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
References
K. Halse, Modeling and solving complex vehicle routing problems. PhD diss., Technical University of Denmark, 1992.
B.D. Backer, V. Furnon, P. Prosser, P. Kilby and P. Shaw, “Local search in constraint programming: Application to the vehicle routing problem.” In Proc. CP-97 Workshop Indust. Constraint-Directed Scheduling, Schloss Hagenberg Austria, pp. 1-15, 1997.
B.I. Golden and E.A. Wasil, “Computerized Vehicle Routing in the Soft Drink Industry”, Operations Research, Vol.35, pp.6-17, 1997.
O. Bräysy and M. Gendreau, “Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms”, Transportation Science, Vol. 39, No.1, 104-118, 2005. DOI: 10.1287/trsc.1030.0056.
Rodrigue J-P and T. Notteboom, The Geography of Transport Systems, New York: Routledge, forth edition, ISBN 978-1138669574.
G.B. Dantzig and J.H. Ramser, “The truck dispatching problem”, Management science, Vol. 6, No. 1, 80-91, 1959.
P. Toth and D. Vigo, The Vehicle Routing Problem. Philadelphia: Siam, 2001.
B. Crevier, J.F. Cordeau, and G. Laporte G, “The multi-depot vehicle routing problem with inter-depot routes”, European Journal of Operational Research, Vol. 176, No.2, pp.756-773, 2007.
O. Bräysy and M. Gendreau, "Vehicle routing problem with time windows, Part I: Route construction and local search algorithms." Transportation science, Vol.39, no. 1, pp.104-118, 2005.
M. Gendreau and C.D. Tarantilis, Solving large-scale vehicle routing problems with time windows: The state-of-the-art, Montreal: Cirrelt, 2010.
K. Kantawong, “Multi-phase Method for Geographical Transportation”, International Journal of Geoinformatics, Vol.13, No.3, pp.37-49, 2017.
Rabinovich, E., Windle, R., Dresner, M. and Corsi, T. (1999), "Outsourcing of integrated logistics functions", International Journal of Physical Distribution & Logistics Management, Vol. 29 No. 6, pp. 353-374.
J.A. Sicilia, B. Royo, E. Larrodé and A. Fraile, "A decision support system for a long-distance routing problem based on the ant colony optimization metaheuristic." Procedia-Social and Behavioral Sciences 111, pp.1035-1044, 2014.
M. Caramia and F. Guerriero, "A heuristic approach to long-haul freight transportation with multiple objective functions." Omega, Vol.37, no. 3, pp.600-614, 2009.
F. Neves-Moreira, P. Amorim, L. Guimarães and B. Almada-Lobo, “A long-haul freight transportation problem: Synchronizing resources to deliver requests passing through multiple transshipment locations”, European Journal of Operational Research, Vol.248, No.2, pp.487-506, 2016.
P. Kilby and T. Urli, “Long-Haul Fleet Mix and Routing Optimisation with Constraint Programming and Large Neighbourhood Search”. Optimisation Research Group. NICTA Canberra Research Lab. Australia, 2015
S. Jawarneh and A. Salwani, "Sequential insertion heuristic with adaptive bee colony optimisation algorithm for vehicle routing problem with time windows." PloS one 10, no. 7 (2015): e0130224.
M. Alzaqebah, S. Jawarneh, H.M. Sarim, and S. Abdullah, “Bees Algorithm for Vehicle Routing Problems with Time Windows”. In Fifth International Conference on Advances in Computing, Control and Networking - ACCN, pp. 145-148, 2016.
M. Alzaqebah, S. Abdullah and S. Jawarneh "Modified artificial bee colony for the vehicle routing problems with time windows." SpringerPlus 5, no. 1, pp. 1298, 2016.
D. Karaboga, “An idea based on honey bee swarm for numerical optimization”. Vol. 200. Technical report-tr06, Erciyes university, engineering faculty, computer engineering department, 2005.
F.C. Weng, and H. Bin Asmuni, “An automated approach based on bee swarm in tackling university examination timetabling problem”. Int J Electr Comput Sci, Vol. 13 no. 02, pp.8-23, 2013.
K. Kantawong and R. Chaisrichareoun, “An Improving ABC Algorithm for Time Dependent Transportation Problem”. International Journal of Applied Engineering Research ISSN 09734562, Vol. 13, no. 5, pp.2809-2813, 2018.
M.M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, Vol. 35, no. 2, 254-265, 1987.
Glover, F. (1977) “Heuristics for Integer Programming Using Surrogate Constraints,” Decision Sciences, vol. 8, pp. 156-166.
R. Gupta, B. Singh, and D. Pandey, “Multi-objective fuzzy vehicle routing problem: a case study”. Int. J. Contemp. Math. Sciences, Vol. 5, no. 29, pp.1439-1454, 2010.
Glover, F., 1998. A Template for Scatter Search and Path Relinking. In: Hao, J.-K., Lutton, E., Ronald, E., Schoenauer, M., Snyers, D. (Eds.), “Artificial Evolution”, Lecture Notes in Computer Science 1363, Springer, pp. 13-54.
E. T. Yassen, M. Ayob, M.Z. Ahmad Nazri and N.R. Sabar, “A hybrid meta-heuristic algorithm for vehicle routing problem with time windows”. International Journal on Artificial Intelligence Tools, Vol. 24, no. 06, pp. 1550021, 2015.
B. Yu, Z.Z. Yang and B.Z. Yao, “A hybrid algorithm for vehicle routing problem with time windows”. expert systems with applications, Vol. 28, no.1, pp. 435-441, 2011.
H. C. Lau, Y.F. Lim and Q. Liu, “Vehicle routing problem with time windows and a limited number of vehicles”. European journal of operational research, Vol. 148, no. 3, pp. 559-569, 2003.