A Comprehensive Study of Vehicle Routing Problem With Time Windows Using Ant Colony Optimization Techniques

  • Authors

    • Avirup Guha Neogi
    • Singamreddy Mounika
    • Salagrama Kalyani
    • S A. Yogananda Sai
    2018-05-31
    https://doi.org/10.14419/ijet.v7i2.32.13532
  • Metaheuristics, Combinatorial Optimization, Ant Colony Optimization, Vehicle Routing Problem.

  • Ant Colony Optimization (ACO) is a nature-inspired swarm intelligence technique and a metaheuristic approach which is inspired by the foraging behavior of the real ants, where ants release pheromones to find the best and shortest route from their nest to the food source. ACO is being applied to various optimization problems till date and has been giving good quality results in the field. One such popular problem is known as Vehicle Routing Problem(VRP). Among many variants of VRP, this paper presents a comprehensive survey on VRP with Time Window constraints(VRPTW). The survey is presented in a chronological order discussing which of the variants of ACO is used in each paper followed by the advantages and limitations of the same.

     

     

  • References

    1. [1] M. Dorigo, V. Maniezzo and A. Colorni. (1991). Positive feedback as a search strategy, Tech. Rep.91-016. Politecnico di Milano.

      [2] M. Dorigo. (1992). Optimization, learning and natural algorithms. Ph.D. Thesis, Dip. Elettronica e Informazione, Politecnico di Milano, Italy.

      [3] J.-L. Deneubourg, S. Aron, S. Goss, and J.-M. Pasteels. (1990). The self-organizing exploratory pattern of the Argentine ant. Journal of Insect Behavior(vol. 3, p. 159).

      [4] G.B. Dantzig and J.H. Ramser (oct 1959). The Truck Dispatching Problem (pp. 80-91). Management Science Vol. 6, No. 1.

      [5] M. Dorigo, V. Maniezzo, and A. Colorni(Feb 1996 ). The Ant System: Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 26(1):1-13.

      [6] M.. Dorigo and T. Stutzle(2004). Ant Colony Optimization. MIT Press, Cambridge, MA,.

      [7] Marco Dorigo and Luca M. Gambardella(1997). Ant Colony System: A cooperative learning approach to the traveling salesman problem(pp. 53–66). IEEE Transactions on Evolutionary Computation, vol. 1, no. 1..

      [8] T. Stutzle, H.H. Hoos(2000). MAX-MIN Ant System. Future generation computer systems. 16(8): 889-914.

      [9] Clarke G, Wright JW(1961). Scheduling of vehicles from a central depot to a number of delivery points,†Operations Research: 12:568–81.

      [10] Bräysy, Olli, and Michel Gendreau(2005). Vehicle routing problem with time windows, Part I: Route construction and local search algorithms. Transportation science 39.1: 104-118.

      [11] Luca Maria Gambardella, Eric Taillard and Giovanni Agazzi(1999). MACS-VRPTW:A multiple ant colony system for vehicle routing problems with time window,(pp. 63-76). In D. Corne, M. Dorigo and F. Glover, editors, New Ideas in Optimization McGraw-Hill, London, UK,.

      [12] M. Solomon(1987). Algorithms for the Vehicle Routing and Scheduling Problem with Time Window Constraints.Operations Research 35, 254-365.

      [13] Benjamin Baran and Matilde Schaerer(2003). A Multiobjective ant colony system for vehicle routing problemwith time windows. Applied Informatics.

      [14] Xuan Tan, Xuyao Luo, W.N.Chen and Jun Zhang(2005). Ant colony system for optimizing vehicle routing problem with time windows. Proceedings of the International Conference on Computational Intelligence for Modelling, Control and Automation, and International Conference on Intelligent Agents, Web Technologies and Internet Commerce (CIMCA-IAWTIC’05).

      [15] Chia-Ho CHEN, Ching-Jung TING(2005). A hybrid ant colony system for vehicle routing problem with time windows,( pp. 2822 – 2836). Journal of the Eastern Asia Society for Transportation Studies, Vol. 6..

      [16] Tao Zhang, Shansham Wang and Wenxin Tian,Yuejie Zhang (2006 ). ACO-VRPTWRV:A New algorithm for the vehicle routing problems with time windows and re-used vehicle based on ant colony algorithm. Proceedings of the Sixth International Conference on Intelligent Systems Design and Applications (ISDA'06).

      [17] Xuan Tan, Xiaolan Zhuo, Jun Zhang(2006). Ant colony system for optimizing vehicle routing problem with time windows(VRPTW) (pp. 33 – 38), D.-S. Huang, K. Li, and G.W. Irwin (Eds.): ICIC 2006, LNBI 4115.

      [18] Daniela Favaretto, Elena Moretti, Paola Pellegrini(2007). Ant colony system for a vrp with multiple time windows and multiple visits( pp:264-284), Informa Ltd Registered in England and Wales Registered Number: 1072954 Registered office: Mortimer House, 37-41 Mortimer Street, London W1T 3JH, UK.

      [19] Weiwei Gong, Xue Liu,Jian Zhang, Zetian Fu(2007). Two-generation ant colony system for vehicle routing problem with time windows(pp:1917-1920). Networking and mobile.

      [20] Albero V. Donati, Roberto Montemanni, Norman Casagrande, Andrea E. Rizzoli, Luca M. Gambardella(2008). Time dependent vehicle routng problem with a multi ant colony system(pp: 1174–1191), European Journal of Operational Research 185.

      [21] Tong Zhen, Qiuwen Zhang, Wenshuai Zhang, Zhi Ma(2008). Hybrid ant colony algorithm for the vehicle routing with time windows,(pp:812), ISECS International Colloquium on Computing, Communication, Control, and Management .

      [22] Sabrina Moreira de Oliveira, Sergio Ricardo de Souza, Maria Amelia Lopes silva(2008). A Solution of dynamic vehicle routing problem with time windows via ant colony system metaheuristic,( pp:21-26) 10th Brazilian Symposium on Neural Networks.

      [23] Chengming Qi, Shoumei Cui, Yunchuan Sun(2008). Using ant colony system and local search methods to solve VRPTW, (pp:478-482). IEEE Pacific-Asia Workshop on Computational Intelligence and Industrial Application.

      [24] Farah BELMECHERI, Christian PRINS, Farouk YALAOUI, Lionel AMODEO, An ant colony optimization algorithm for a vehicle routing problem with heterogeneous fleet, mixed back hauls, and time windows, Proceedings of the 13th IFAC Symposium on Information Control Problems in Manufacturing Moscow, Russia, June 3-5, pp:1550-1555,2009.

      [25] Rieck, J., Zimmermann, J., & Glagow, M. (2007). Tourenplanungmittelständischer speditionsunternehmen in stückgutkooperationen: Modellierung und heuristische lösungsverfahren. Zeitschrift Planung and Unternehmenssteuerung, 17, 365–388

      [26] Li Guiyun(2009). An improved ant colony algorithm for open vehicle routing problem (ovrptw) with time windows,( pp:616-619) . International Conference on Information Management, Innovation Management and Industrial Engineering.

      [27] Pablo Ortega, Cristian Oliva, Jacques Ferland, Manuel Cepeda(2009). Multiple ant colony system for a vrp with time windows and scheduling loading,( pp. 393-403). Ingeniare, Revista chilena de ingenieria, vol. 17 No 3..

      [28] P. Toth and D. Vigo(2001) . The Vehicle Routing Problem. Society for Industrial and Applied Mathematic, Siam Monographs on Discrete Mathematics and Applications, .

      [29] Eduardo Goecking Carabetti, Sergio Ricardo de Souza, Marcelo Caramuru Fraga(2010). An application of the ant colony system metaheuristic to the vehicle routing problem with pickup and delivery and time windows,(pp 176-18). Eleventh Brazilian Symposium on Neural Networks.

      [30] Xin MA(2010). Vehicle routing problem with time windows based on improved ant colony algorithm,( pp 94-97). Second International Conference on Information Technology and Computer Science.

      [31] S.R.Balseiro, I.Loiseau, J.Ramonet(2010), An ant colony algorithm hybridized with insertion heuristics for the time dependent vehicle routing problem with time windows, (pp:1-23 )computers and operations research, September 12.

      [32] Bin Yu, Zhong Zhen Yang(2011). An ant colony optimization model: the period vehicle routing problem with time windows,( pp:166-181). Transportation Research part E 47.

      [33] Qiulei Ding, Xiangpei Hu, Lijun Sun, Yunzeng Wang(2012). An improved ant colony optimization and its application to vehicle routing problem with time windows, (pp:101-107,2012) Neurocomputing 98.

      [34] Jian Wang, Yanyan Wang,Hongyun Li(2012). Improved ant colony algorithm for logistics vehicle routing problem with time windows,( pp. 41–48) J. Lei et al. (Eds.): AICI 2012, CCIS 315, 2012.© Springer-Verlag Berlin Heidelberg.

      [35] Barry van Veen, Michael Emmerich, Zhiwei Yang, Thomas Back, Joost Kok(July 2013). Ant colony algorithms for the dynamic vehicle routing problem with time windows. International Work-Conference on the Interplay Between Natural and Artificial Computation, Springer, Berlin, Heidelberg, 2013.

      [36] Sandhya,Vijay Katiyar(July 2013). An enchanced ant colony system for solving vehicle routing problem with time windows. International Journal of Computer Applications (0975 – 8887) Volume 73– No.12.

      [37] Wenxue Ran, Li Liu and Guomin Yang(2013). A Hybrid ant colony algorithm for vehicle routing problem with time windows (pp:5701-5706). Information technology Journal 12(20).

      [38] Jian Wang, Hongyun Li, Hong Chen(2013). Mixed ant colony algorithm for vehicle routing problem with time windows,( pp 855-858). Advanced Materials Research Vols. 706-708.

      [39] Nihat Engin Toklu, Luca Maria Gambardella, Roberto montemanni(March 2014), A Multiple ant colony system for a vehicle routing problem with time windows and uncertain travel times,(pp:52-58). Journal of Traffic and Logistics Engineering Vol. 2, No. 1.

      [40] Mhand Hifi and Lei wu(2014). A Hybrid metaheuristic for vehicle routing problem with time windows. 2014 International Conference on Control, Decision and Information Technologies (CoDIT), Metz, 2014, pp. 188-194

      [41] Sandhya, V. Katiyar(October 2014). Integrating fuzzy and ant colony system for fuzzy vehicle routing problem with time windows, International Journal on Computational Sciences & Applications (IJCSA) Vol.4, No.5.

      [42] Hong-dou Zhang,(2014). A Improved pareto of ant colony algorithm to solve the vehicle routing problem with time windows(pp 1941-1944) . Switzerland :Trans Tech Publications, Advanced Materials Research Vols 1030-1032.

      [43] Zhiwei Yang, Michael Emmerich, Thomas Back(2015). Ant based solver for dynamic vehicle routing problem with time windows and multiple priorities(pp:2813-2819). Evolutionary Computation(CEC).

      [44] J. Brito, F.J. Martinez, J.L Verdegay, “An ACO Hybrid metaheuristic for close-open vehicle routing problems with time windows and fuzzy constraints,†Elsevier B.V, pp:1-10,2015.

      [45] Gerald Senarclens de Grancy(2015) . An Adaptive Metaheuristics for vehicle routing problems with time windows and multiple service workers,( pp:1143-1167). Journal of Universal Computer Science, vol. 21, no. 9.

      [46] Linling Liao, Xiushan Cai, Huadong huang, Yanhong Liu(2016). Vehicle routing with time windows based on two-stage optimization algorithm, (pp:4741-4745).Control and Descision.

      [47] Racula Necula, Mihaela Breaban, Madalina Raschip. Tackling dynamic vehicle routing problem with time windows by means ant colony system. 2017 IEEE Congress on Evolutionary Computation (CEC), 2017

      [48] Abbassi abderrahman, El Bouyahioy Karim, EL Hilali Alaoui Ahmed, Bellabdaoui Adil(2017). A Hybrid algorithm for vehicle routing problem with time windows and target time,( pp:210-219). Journal of Theoretical and Applied Information Technology,Vol.95.No.1.

      [49] Karim El Bouyahyiouy, Adil Bellabdaoui (2017). An ant colony optimization algorithm for solving the full truck load vehicle routing problem with profit,( pp:142-147) Logistics and supply chain.

      [50] Jyoti Gupta, Chander Diwaker(2017). Evaluation of capacitated vehicle routing problem with time windows using ACO-GA, (pp:610-615) International Journals of Advanced Research in Computer Science and Software Engineering ISSN: 2277-128X (Volume-7, Issue- 6).

  • Downloads

  • How to Cite

    Guha Neogi, A., Mounika, S., Kalyani, S., & A. Yogananda Sai, S. (2018). A Comprehensive Study of Vehicle Routing Problem With Time Windows Using Ant Colony Optimization Techniques. International Journal of Engineering & Technology, 7(2.32), 80-85. https://doi.org/10.14419/ijet.v7i2.32.13532