International Journal of Intelligent Systems and Applications (IJISA)
IJISA Vol. 9, No. 7, 8 Jul. 2017
Cover page and Table of Contents: PDF (size: 516KB)
Dynamic Vehicle Routing Problem: Solution by Ant Colony Optimization with Hybrid Immigrant Schemes
Full Text (PDF, 516KB), PP.52-60
Views: 0 Downloads: 0
Author(s)
Dhanya K.M.
1,*
S.Kanmani
2
Index Terms
Meta-Heuristics, Dynamic Vehicle Routing Problem, Ant Colony Optimization, Hybrid Immigrant Schemes, HIACO-I, HIACO-II, HIACO-III, Intensification, Diversification, Random Immigrant, Elitism based Immigrant
Abstract
During past decades, several Meta-Heuristics were considered by researchers to solve Dynamic Vehicle Routing Problem.In this paper, Ant Colony Optimization integrated with Hybrid Immigrant Schemes methods are proposed for solving Dynamic Vehicle Routing Problem. Ant Colony Optimization with hybrid immigrant schemes methods namely HIACO-I, HIACO-II and HIACO-III focused on establishing the proper balance between intensification and diversification. The performance evaluation of the algorithms in which Random Immigrants and Elitism based Immigrants were hybridized in different proportions and added to Ant Colony Optimization algorithm showed that they had produced better results in many dynamic test cases generated from three Vehicle Routing Problem instances.
Cite This Paper
Dhanya K.M., S.Kanmani,"Dynamic Vehicle Routing Problem: Solution by Ant Colony Optimization with Hybrid Immigrant Schemes", International Journal of Intelligent Systems and Applications(IJISA), Vol.9, No.7, pp.52-60, 2017. DOI:10.5815/ijisa.2017.07.06
Reference
[1]Barkaoui, M., Berger, J., Boukhtouta, A. Customer Satisfaction in dynamic vehicle routing problem with time windows.Appl. Soft Comput, 2015, 35:423-432.
[2]Boussaïd, I., Lepagnot, J., Siarry, P. A survey on optimization metaheuristics. Inform. Sciences.2013, 237:82–117.
[3]Brito, J., Martinez, F., J., Moreno, J.,Verdegay, J.,L. An ACO hybrid meta heuristic for close-open vehicle routing problem with time window and fuzzy constraints. Appl. Soft Comput. , 2015, 32:154-163.
[4]Cattaruzza, D., Absi, N., Feillet, D., Vidal, T. A memetic algorithm for the multi trip vehicle routing problem .Eur. J. Oper. Res.2014, 236: 833-848.
[5]Chiangn, T.,-C, Hsu, W.,-H.A knowledge-based evolutionary algorithm for the multiobjective vehicle routing problem with time windows. Comput. Oper. Res.2014, 45:25-37.
[6]Cruz, C., Gonza´lez, J., R., Pelta, D., A. Optimization in dynamic environments: A survey on problems, methods and measures. Soft Comput.2011, 15: 1427–1448
[7]De Armas, J., Melián -Batista, B. Variable Neighborhood Search for a Dynamic Rich Vehicle Routing Problem with Time Windows. Comput. Ind. Eng. 2015, 85:120-131.
[8]De Armas, J., Melián -Batista, B. Constrained dynamic vehicle routing problems with time windows. Soft Comput. 2015, 19:2481-2498.
[9]De Oliveira, F., Enayatifar, R., Sadaei, H., J., Guimarães, F., G., Potvin, J.,-Y. A cooperative coevolutionary algorithm for the Multi-Depot Vehicle Routing Problem. Expert Syst. Appl. 2016, 43:117–130.
[10]Eaton J., Yang, S., Mavrovouniotis, M. Ant colony optimization with immigrants schemes for the dynamic railway junction rescheduling problem with multiple delays. Soft Comput.2016, 20: 2951–2966.
[11]Euchi, J., Yassine, A., Chabchou, H. The dynamic vehicle routing problem: Solution with hybrid metaheuristic approach. Swarm Evol. Comput.2015, 21: 41–53.
[12]Ghannadpour, S., F., Noori, S., Tavakkoli-Moghaddam, R. A multiobjective dynamic vehicle routing problem with fuzzy time windows: Model, Solution and Application. Appl. Soft Comput. 2014, 14: 504-527.
[13]Jiang, J., Ng, K., M., Poh, K., L., Teo, K., M. Vehicle Routing Problem with a heterogeneous fleet and time windows. Expert Syst. Appl.2014, 41:3748-3760.
[14]Kar, A., K. Bio inspired computing – A review of algorithms and scope of applications. Expert Syst. Appl. 2016, 59:20–32.
[15]Karakatic, S., Podgorelec, V. A survey of genetic algorithms for solving multi depot vehicle routing problem. Appl. Soft Comput.2015, 27: 519-532.
[16]Koç, C., Bektas, T., Jabali, O., Laporte, G. Thirty years of heterogeneous vehicle routing. Eur. J. Oper. Res. 2016, 249: 1–21.
[17]Kourank Beheshti, A., Hejazi, S., R. A novel hybrid column generation-meta heuristic approach for the vehicle routing problem with general soft time window. Inform. Sciences. 2015, 316: 598-615.
[18]Lin, C., Choy, K., L., Ho, G., T., S., Chung, S.,H., Lam, H.,Survey of Green Vehicle Routing Problem: Past and Future Trends. Expert Syst. Appl, 2014, 1118-1138.
[19]Luo, W., Sun, J., Bu, C., Liang, H. Species – based Particle Swarm Optimizer enhanced by memory for dynamic optimization. Appl. Soft Comput.2016, 47:130-140.
[20]Mavrovouniotis, M., Li, C., Yang, S. A survey of swarm intelligence for dynamic optimization: algorithms and applications", Swarm Evol. Comput., 2016.
[21]Mavrovouniotis, M., Yang, S. A memetic ant colony optimization algorithm for the dynamic travelling salesman problem. Soft Comput., 2011.
[22]Mavrovouniotis, M., Yang, S. Ant colony optimization with immigrants schemes for the dynamic travelling salesman problem with traffic factors. Appl. Soft Comput. 2013, 13: 4023-4037.
[23]Mavrovouniotis, M., Yang, S. Dynamic Vehicle Routing: A Memetic Ant Colony Optimization Approach. Automated scheduling and planning .2013, 283-301.
[24]Mavrovouniotis, M., Yang, S. Ant algorithms with immigrant schemes for the dynamic vehicle routing problem. Inform. Sciences.2015, 294:456-477.
[25]Montoya-Torres, J., R., Lopez Franco, J., Nieto Isaza, S., Felizzola, H., J., Jimenz. A literature review on the vehicle routing problem with multiple depots. Comput. Ind. Eng. 2015, 79:115-129.
[26]Nasiri, B., Meyabodi, M., R., Ebadzadeh, M., M. History-Driven Particle Swarm Optimization in dynamic and uncertain environments. NeuroComputing. 2016, 172: 356-370.
[27]Nseef, S., K., Abdullah, S., Turky, A., Kendall, G. An adaptive multi-population artificial bee colony algorithm for dynamic optimisation problems. Knowl-based Syst.2016, 104: 14-23.
[28]Pillac, V., Gendreau, M., Gueret, C., Medaglia, A., L.A review of dynamic vehicle routing problems. Eur. J. Oper. Res. 2013, 225:1-11.
[29]Reed, M., Yiannakou, A., Evering, R. An ant colony algorithm for the multi-compartment vehicle routing problem. Appl. Soft Comput. 2014, 15: 169-176.
[30]Schyns, M. An ant colony system for responsive dynamic vehicle routing. Eur. J. Oper. Res. 2015, 245: 704-718.
[31]Yang, S. Genetic Algorithms with Memory- and Elitism-Based Immigrants in Dynamic Environments. Evol. Comput. 2008, 16: 385-416.
[32]Yang, S., Jiang, Y., Thanh Nguyen, T. Metaheuristics for Dynamic Combinatorial Optimization Problems. IMA J. Manage. Math, 2011, 1 -29.
[33]Yang, S., Tinos, R. A Hybrid Immigrants Scheme for Genetic Algorithms in Dynamic Environments. Int. J. Autom. Comput. 2007, 04: 243-254.
[34]Neo Networking and Emerging Optimization Research Group. Capacitated VRP Instances.2013 [online]. Available at: http://neo.lcc.uma.es/vrp/vrp-instances/capacitated-vrp-instances/
[35]Talbi, E.,G., Metaheuristics from Design to Implementation, John Wiley & Sons, Inc., Hoboken, New Jersey. 2009.