Improved Multi-Ant-colony algorithm for solving Multi-Objective Vehicle Routing Problems

Document Type : Article

Authors

1 - Department of Computer Engineering, Punjabi University, Patiala, India (147002) - Department of Computer Science, Government College, Naraingarh, India (134101)

2 Department of Computer Engineering, Punjabi University, Patiala, India (147002)

Abstract

Classical vehicle routing problems (VRP) involves supply of goods/services from a central depot to geographically scattered customers. Besides the classical objective of minimizing the total travelled distance, the present work also considers simultaneous optimization of two additional objectives namely minimizing make span and minimizing distance imbalance. A mathematical model for this multi-objective version of VRP (MO-VRPTW) has been developed. A meta-heuristic based on multiple ant colony system for solving this MO-VRPTW has also been proposed. Firefly algorithm (FA) has also been applied to avoid local optima. Two new migration operators named Migration-I and Migration-II and multi-pheromone matrices have been developed to further improve the solution set. The proposed algorithm has been tested on a number of benchmark problems and its superiority over other state of art approaches and NSGA-II one of the commonly used method for multi-objective optimization problems is demonstrated.

Keywords

References

References:
1. Goel, R. and Maini, R. "Vehicle routing problem and its solution methodologies: a survey", International Journal of Logistics Systems and Management, 28(4), pp. 419-435 (2017).
2. Borgulya, I. "An algorithm for the capacitated vehicle routing problem with route balancing", Central European Journal of Operations Research, 16(4), pp. 331- 343 (2008).
3. Jozefowiez, N., Semet, F., and Talbi, E.G. "An evolutionary algorithm for the vehicle routing problem with route balancing", European Journal of Operational Research, 195(3), pp. 761-769 (2009).
4. Kritikos, M.N. and Ioannou, G. "The balanced cargo vehicle routing problem with time windows", International Journal of Production Economics, 123(1), pp.42-51 (2010).
5. Zhou, W., Song, T., He, F., and Liu, X. "Multiobjective vehicle routing problem with route balance based on genetic algorithm", Discrete Dynamics in Nature and Society, 2013, pp. 1-9 (2013).
6. Melian-Batista, B., De Santiago, A., Angel, Bello, F.,et al. "A bi-objective vehicle routing problem with time windows: A real case in Tenerife", Applied Soft Computing, 17, pp. 140-152 (2014).
7. Ombuki, B., Ross, B.J., and Hanshar, F. "Multiobjective genetic algorithms for vehicle routing problem with time windows", Applied Intelligence, 24(1), pp. 17-30 (2006).
8. Jozefowiez, N., Semet, F., and Talbi, E.G. "Multiobjective vehicle routing problems", European Journal of Operational Research, 189(2), pp. 293-309 (2008).
9. Garcia-Najera, A. and Bullinaria, J.A. "An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows", Computers & Operations Research, 38(1), pp. 287-300 (2011).
10. Dong, W., Zhou, K., Qi, H., He, C., and Zhang, J. "A tissue P system based evolutionary algorithm for multi-objective VRPTW", Swarm and Evolutionary Computation, 39, pp. 310-322 (2018).
11. Jozefowiez, N., Semet, F., and Talbi, E.G. "Parallel and hybrid models for multi-objective optimization: Application to the vehicle routing problem", In International Conference on Parallel Problem Solving from Nature, Springer, Berlin, Heidelberg, pp. 271-280 (2002).
12. Lau, H.C., Chan, T.M., Tsui, W.T., et al. "A fuzzy guided multi-objective evolutionary algorithm model for solving transportation problem", Expert Systems with Applications, 36(4), pp. 8255-8268 (2009).
13. BanOs, R., Ortega, J., Gil, C., et al. "A hybrid etaheuristic for multi-objective vehicle routing problems with time windows", Computers & Industrial Engineering, 65(2), pp. 286-296 (2013).
14. Widyadana, G.A. and Irohara, T. "Modelling multitour inventory routing problem for deteriorating items with time windows", Scientia Iranica, 26(2), pp. 932- 941 (2019).
15. Hasle, G. "Routing applications in newspaper delivery", SINTEF Report A23753, Oslo, Norway (2012).
16. Najafi, M., Eshghi, K., and Dullaert, W. "A multiobjective robust optimization model for logistics planning in the earthquake response phase", Transportation Research Part E: Logistics and Transportation Review, 49(1), pp. 217-249 (2013).
17. Zhou, Y. and Wang, J. "A local search-based multiobjective optimization algorithm for multiobjective vehicle routing problem with time windows", IEEE Systems Journal, 9(3), pp. 1100-1113 (2015).
18. Lacomme, P., Prins, C., Sevaux, M., et al. "A genetic algorithm for a bi-objective capacitated arc routing problem", Computers and Operations Research, 33(12), pp. 3473-3493 (2006).
19. Ghannadpour, S.F., Noori, S., Tavakkoli-Moghaddam, R., et al. "A multi-objective dynamic vehicle routing problem with fuzzy time windows: Model, solution and application", Applied Soft Computing, 14, pp. 504-527 (2014).
20. Chiang, T.C. and Hsu, W.H. "A knowledge-based evolutionary algorithm for the multiobjective vehicle routing problem with time windows", Computers and Operations Research, 45, pp. 25-37 (2014).
21. Kaiwartya, O., Kumar, S., Lobiyal, D.K., et al. "Multiobjective dynamic vehicle routing problem and time seed based solution using particle swarm optimization", Journal of Sensors, 2015, pp. 1-14 (2015).
22. Qi, Y., Hou, Z., Li, H., et al. "A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows", Computers & Operations Research, 62, pp. 61-77 (2015).
23. Ghannadpour, S.F. and Hooshfar, M. "Multi-objective vehicle routing problem with time windows and fuel consumption minimizing", In ICORES, pp. 92-99 (2016).
24. Gharib, Z., Bozorgi-Amiri, A., Tavakkoli-Moghaddam, R., et al. "A cluster-based emergency vehicle routing problem in disaster with reliability", Scientia Iranica, Transactions E, Industrial Engineering, 25(4), pp. 2312-2330 (2018).
25. Wang, J., Weng, T., Zhang, Q., et al. "A two-stage multiobjective evolutionary algorithm for multiobjective multidepot vehicle routing problem with time windows", IEEE Transactions on Cybernetics, (99), pp. 1-12 (2018).
26. Corberan, A., Fernandez, E., Laguna, M., et al. "Heuristic solutions to the problem of routing school buses with multiple objectives", Journal of the Operational Research Society, 53(4), pp. 427-435 (2002).
27. Miranda, D.M., Branke, J., and Conceicao, S.V. "Algorithms for the multi-objective vehicle routing problem with hard time windows and stochastic travel time and service time", Applied Soft Computing, 70, pp. 66-79 (2018).
28. Bansal, S. and Goel, R. "Multi objective vehicle routing problem: A survey", Asian Journal of Computer Science and Technology, 7(3), pp. 1-6 (2018).
29. Zhong, Y.G. and Ai, B. "A modified ant colony optimization algorithm for multi-objective assembly line balancing", Soft Computing, 21(22), pp. 6881- 6894 (2017).
30. Fister, I., Fister Jr, I., Yang, X.S., et al. "A comprehensive review of fire y algorithms", Swarm and Evolutionary Computation, 13, pp. 34-46 (2013).
31. Yang, X. "Fire y algorithms for multimodal optimization", Stochastic Algorithms: Foundations and Applications, Springer Berlin Heidelberg, pp. 169-178 (2009).
32. Yang, X. "Fire y algorithm, stochastic test functions and design optimisation", International Journal of Bio-Inspired Computation, 2(2), pp. 78-84 (2010).
33. Goel, R. and Maini, R. "A hybrid of ant colony and fire y algorithms (HAFA) for solving vehicle routing problems", Journal of Computational Science, 25, pp. 28-37 (2018).
34. Sanchez-Oro, J., Lopez-Sanchez, A.D., and Colmenar, J.M. "A general variable neighborhood search for solving the multi-objective open vehicle routing problem", Journal of Heuristics, 26(3), pp. 423-452 (2020).
35. Zitzler, E., Laumanns, M., and Thiele, L. "SPEA2: Improving the strength Pareto evolutionary algorithm", TIK-report, 103, pp. 1-22 (2001).
36. Zitzler, E. and Thiele, L. "Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach", IEEE Transactions on Evolutionary Computation, 3(4), pp. 257-271 (1999).
37. http://w.cba.neu.edu/ msolomon/problems.htm. 38. Yu, B., Yang, Z.Z., and Yao, B.Z. "A hybrid algorithm for vehicle routing problem with time windows", Expert Systems with Applications, 38(1), pp. 435-441 (2011).
39. Osaba, E., Carballedo, R., Yang, X.S., et al. "An evolutionary discrete fire y algorithm with novel operators for solving the vehicle routing problem with time windows". In Nature-Inspired Computation in Engineering, pp. 21-41, Springer, Cham (2016).
40. Deb, K., Pratap, A., Agarwal, S., et al. "A fast and elitist multiobjective genetic algorithm: NSGAII", IEEE Transactions on Evolutionary Computation, 6(2), pp. 182-197 (2002).
41. Mandal, S.K., Pacciarelli, D., Lkketangen, A., et al. "A memetic NSGA-II for the bi-objective mixed capacitated general routing problem", Journal of Heuristics, 21(3), pp. 359-390 (2015).
Scientia Iranica
Volume 28, Issue 6 - Serial Number 6
Transactions on Computer Science & Engineering and Electrical Engineering (D)
November and December 2021
Pages 3412-3428

Files

History

  • Receive Date: 27 September 2018
  • Revise Date: 17 June 2019
  • Accept Date: 29 July 2019

Share

How to cite

Statistics