Page 56 - Fister jr., Iztok, Andrej Brodnik, Matjaž Krnc and Iztok Fister (eds.). StuCoSReC. Proceedings of the 2019 6th Student Computer Science Research Conference. Koper: University of Primorska Press, 2019
P. 56
21085.43 7461.45 [3] W. Ho, G. T.S. Ho, P. Ji, and H. C.W. Lau, “A hybrid genetic
algorithm for the multi-depot open vehicle routing problem,” Eng.
HS 21293.09 7656.94 Appl. Artif. Intell., vol. 21, pp. 401–421, 2008.
If we look at Table 6, we can see the rankings of the PSO [4] S. Karakatič and V. Podgorelec, “A survey of genetic
algorithm in fitness scores and runtime relative to the other algorithms for solving multi depot vehicle routing problem,”
algorithms. The PSO reached an average of 2.6 for fitness Appl. Soft Comput. J., vol. 27, pp. 519–532, 2015.
rankings and 1.6 for the runtime, and thus solved MDVRP cases
the best of all the tested algorithms. It handled more difficult cases [5] G. Laporte, M. Gendreau, J.-Y. Potvin, and F. Semet,
better but achieved the fastest resolution times for all of the “Classical and modern heuristics for the vehicle routing problem,”
MDVRP examples. Int. Trans. Oper. Res., vol. 7, pp. 285–300, 2000.
We ran the test cases again with second conversion of genotype to [6] S. Luke, Essentials of Metaheuristics, Second Edi. 2013.
phenotype but did not get any different results – all fitness scores
and running times have overall deteriorated. [7] B. M. Baker and M. A. Ayechew, “A genetic algorithm for the
vehicle routing problem,” Comput. Oper. Res., vol. 30, no. 5, pp.
Table 6. The PSO algorithm ranks 787–800, 2003.
Order of pr00 pr04 pr08 pr14 pr20 [8] A. P Engelbrecht, “Computational Intelligence.” p. 597, 2007.
place
Fitness 4 4 2 2 1 [9] A. Shukla, R. Tiwari, and R. Kala, Real Life Applications of
1 2 1 1 3 Soft Computing. 2012.
Run time
[10] R. Storn and K. Price, “Differential Evolution – A Simple
5. CONCLUSIONS and Efficient Heuristic for Global Optimization over Continuous
Spaces,” J. Glob. Optim., pp. 341–359, 1997.
In this paper we present the application of particle swarm
optimization algorithm with the usage of NiaPy optimization [11] P. Surekha, Sumathi, and Dr.S., “Solution To Multi-Depot
framework on the multi-depot capacitated vehicle routing Vehicle Routing Problem Using Genetic Algorithms,” World
problem. Our approach differs from the similar relevant Appl. Program., vol. 1, no. 3, pp. 118–131, 2011.
approaches in the way we represent the optimization problem. In [12] N. and E. O. G. University of Málaga, “Multiple Depot VRP
the literature it is normal to treat routing problems as discreet with Time Windows Instances,” 2013. [Online]. Available:
optimization problems. As this was not possible with the usage of http://neo.lcc.uma.es/vrp/vrp-instances/multiple-depot-vrp-with-
NiaPy optimization framework, we presented a method on how to time-windows-instances. [Accessed: 31-Aug-2019].
solve MDVRP as the continuous optimization problem.
[13] G. Vrbančič, L. Brezočnik, U. Mlakar, D. Fister, and I. Fister
The proposed method was tested on several standard MDVRP Jr., “NiaPy: Python microframework for building nature-inspired
benchmark sets and the results of PSO were compared with algorithms,” J. Open Source Softw., vol. 3, p. 613, 2018.
several evolutionary algorithms. The results of the experiment
[14] X.-S. Yang, “Firefly algorithms for multimodal
show that PSO of continuous optimization is a viable and optimization,” Springer-Verlag Berlin Heidelb., vol. 5792 LNCS,
competitive method for solving MDVRP, especially in the speed pp. 169–178, 2009.
of the optimization – it was the fastest in three cases out of five
sets. Our proposed PSO reached the best (shortest) route in only [15] X.-S. Yang and X. He, “Firefly algorithm: recent advances
one case and it resulted with second shortest routes in two other and applications,” Int. J. Swarm Intell., vol. 1, no. 1, pp. 36–50,
cases. Thus, we can conclude that PSO can effectively solve 2013.
MDVRP problem with competitive solutions in fastest run times
out of all five included algorithms. [16] Mohemmed, A.W., Sahoo, N.C. and Geok, T.K., 2008.
Solving shortest path problem using particle swarm optimization.
Future work includes the implementation of advanced PSO Applied Soft Computing, 8(4), pp.1643-1653.
operators from the referenced literature and customizing them for
the continuous optimization. Also, there are numerous other VRP [17] Ai, T.J. and Kachitvichyanukul, V., 2009. A particle swarm
variants, which should be tested with our proposed approach. optimization for the vehicle routing problem with simultaneous
pickup and delivery. Computers & Operations Research, 36(5),
6. ACKNOWLEDGMENTS pp.1693-1702.
The authors acknowledge financial support from the Slovenian [18] Yao, B., Yu, B., Hu, P., Gao, J. and Zhang, M., 2016. An
Research Agency (Research Core Funding No. P2-0057). improved particle swarm optimization for carton heterogeneous
vehicle routing problem with a collection depot. Annals of
7. REFERENCES Operations Research, 242(2), pp.303-320.
[1] W. Cao and W. Yang, “A Survey of Vehicle Routing [19] Kumar, R.S., Kondapaneni, K., Dixit, V., Goswami, A.,
Problem,” MATEC Web Conf., vol. 100, pp. 1–6, 2017. Thakur, L.S. and Tiwari, M.K., 2016. Multi-objective modeling of
production and pollution routing problem with time window: A
[2] I.-M. Chao, E. Wasil, and B. L. Golden, “A new heuristic for self-learning particle swarm optimization approach. Computers &
the multi-depot vehicle routing problem that improves upon best- Industrial Engineering, 99, pp.29-40.
known solutions,” Am. J. Math. Manag. Sci., vol. 13, no. 3–4, pp.
371–406, 1993. [20] Norouzi, N., Sadegh-Amalnick, M. and Tavakkoli-
Moghaddam, R., 2017. Modified particle swarm optimization in a
time-dependent vehicle routing problem: minimizing fuel
consumption. Optimization Letters, 11(1), pp.121-134.
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 56
Koper, Slovenia, 10 October
algorithm for the multi-depot open vehicle routing problem,” Eng.
HS 21293.09 7656.94 Appl. Artif. Intell., vol. 21, pp. 401–421, 2008.
If we look at Table 6, we can see the rankings of the PSO [4] S. Karakatič and V. Podgorelec, “A survey of genetic
algorithm in fitness scores and runtime relative to the other algorithms for solving multi depot vehicle routing problem,”
algorithms. The PSO reached an average of 2.6 for fitness Appl. Soft Comput. J., vol. 27, pp. 519–532, 2015.
rankings and 1.6 for the runtime, and thus solved MDVRP cases
the best of all the tested algorithms. It handled more difficult cases [5] G. Laporte, M. Gendreau, J.-Y. Potvin, and F. Semet,
better but achieved the fastest resolution times for all of the “Classical and modern heuristics for the vehicle routing problem,”
MDVRP examples. Int. Trans. Oper. Res., vol. 7, pp. 285–300, 2000.
We ran the test cases again with second conversion of genotype to [6] S. Luke, Essentials of Metaheuristics, Second Edi. 2013.
phenotype but did not get any different results – all fitness scores
and running times have overall deteriorated. [7] B. M. Baker and M. A. Ayechew, “A genetic algorithm for the
vehicle routing problem,” Comput. Oper. Res., vol. 30, no. 5, pp.
Table 6. The PSO algorithm ranks 787–800, 2003.
Order of pr00 pr04 pr08 pr14 pr20 [8] A. P Engelbrecht, “Computational Intelligence.” p. 597, 2007.
place
Fitness 4 4 2 2 1 [9] A. Shukla, R. Tiwari, and R. Kala, Real Life Applications of
1 2 1 1 3 Soft Computing. 2012.
Run time
[10] R. Storn and K. Price, “Differential Evolution – A Simple
5. CONCLUSIONS and Efficient Heuristic for Global Optimization over Continuous
Spaces,” J. Glob. Optim., pp. 341–359, 1997.
In this paper we present the application of particle swarm
optimization algorithm with the usage of NiaPy optimization [11] P. Surekha, Sumathi, and Dr.S., “Solution To Multi-Depot
framework on the multi-depot capacitated vehicle routing Vehicle Routing Problem Using Genetic Algorithms,” World
problem. Our approach differs from the similar relevant Appl. Program., vol. 1, no. 3, pp. 118–131, 2011.
approaches in the way we represent the optimization problem. In [12] N. and E. O. G. University of Málaga, “Multiple Depot VRP
the literature it is normal to treat routing problems as discreet with Time Windows Instances,” 2013. [Online]. Available:
optimization problems. As this was not possible with the usage of http://neo.lcc.uma.es/vrp/vrp-instances/multiple-depot-vrp-with-
NiaPy optimization framework, we presented a method on how to time-windows-instances. [Accessed: 31-Aug-2019].
solve MDVRP as the continuous optimization problem.
[13] G. Vrbančič, L. Brezočnik, U. Mlakar, D. Fister, and I. Fister
The proposed method was tested on several standard MDVRP Jr., “NiaPy: Python microframework for building nature-inspired
benchmark sets and the results of PSO were compared with algorithms,” J. Open Source Softw., vol. 3, p. 613, 2018.
several evolutionary algorithms. The results of the experiment
[14] X.-S. Yang, “Firefly algorithms for multimodal
show that PSO of continuous optimization is a viable and optimization,” Springer-Verlag Berlin Heidelb., vol. 5792 LNCS,
competitive method for solving MDVRP, especially in the speed pp. 169–178, 2009.
of the optimization – it was the fastest in three cases out of five
sets. Our proposed PSO reached the best (shortest) route in only [15] X.-S. Yang and X. He, “Firefly algorithm: recent advances
one case and it resulted with second shortest routes in two other and applications,” Int. J. Swarm Intell., vol. 1, no. 1, pp. 36–50,
cases. Thus, we can conclude that PSO can effectively solve 2013.
MDVRP problem with competitive solutions in fastest run times
out of all five included algorithms. [16] Mohemmed, A.W., Sahoo, N.C. and Geok, T.K., 2008.
Solving shortest path problem using particle swarm optimization.
Future work includes the implementation of advanced PSO Applied Soft Computing, 8(4), pp.1643-1653.
operators from the referenced literature and customizing them for
the continuous optimization. Also, there are numerous other VRP [17] Ai, T.J. and Kachitvichyanukul, V., 2009. A particle swarm
variants, which should be tested with our proposed approach. optimization for the vehicle routing problem with simultaneous
pickup and delivery. Computers & Operations Research, 36(5),
6. ACKNOWLEDGMENTS pp.1693-1702.
The authors acknowledge financial support from the Slovenian [18] Yao, B., Yu, B., Hu, P., Gao, J. and Zhang, M., 2016. An
Research Agency (Research Core Funding No. P2-0057). improved particle swarm optimization for carton heterogeneous
vehicle routing problem with a collection depot. Annals of
7. REFERENCES Operations Research, 242(2), pp.303-320.
[1] W. Cao and W. Yang, “A Survey of Vehicle Routing [19] Kumar, R.S., Kondapaneni, K., Dixit, V., Goswami, A.,
Problem,” MATEC Web Conf., vol. 100, pp. 1–6, 2017. Thakur, L.S. and Tiwari, M.K., 2016. Multi-objective modeling of
production and pollution routing problem with time window: A
[2] I.-M. Chao, E. Wasil, and B. L. Golden, “A new heuristic for self-learning particle swarm optimization approach. Computers &
the multi-depot vehicle routing problem that improves upon best- Industrial Engineering, 99, pp.29-40.
known solutions,” Am. J. Math. Manag. Sci., vol. 13, no. 3–4, pp.
371–406, 1993. [20] Norouzi, N., Sadegh-Amalnick, M. and Tavakkoli-
Moghaddam, R., 2017. Modified particle swarm optimization in a
time-dependent vehicle routing problem: minimizing fuel
consumption. Optimization Letters, 11(1), pp.121-134.
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 56
Koper, Slovenia, 10 October
