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
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. Ba~nOs, R., Ortega, J., Gil, C., et al. A hybrid metaheuristic
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. Naja , 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).
3428 R.K. Goel and R. Maini/Scientia Iranica, Transactions D: Computer Science & ... 28 (2021) 3412{3428
27. Miranda, D.M., Branke, J., and Conceic~ao, 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 modi ed 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  re
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
 re
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  re
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"problem", Journal of Heuristics,
21(3), pp. 359{390 (2015).