The Effect of the Number of Hidden Layers on The Performance of Deep Q-Network for Traveling Salesman Problem

Benzfica Hanif, Aisyah Larasati, Rudi Nurdiansyah, Trung Le

Abstract


The Traveling Salesman Problem (TSP) effectively represents the complex distribution issues encountered by couriers, who must carefully plan a route that includes all customer addresses while minimizing the distance traveled. As the magnitude of deliveries and the range of destinations expand, the courier's responsibility becomes progressively challenging. In this particular context, the objective of our research is to expand the existing knowledge and explore the complete capabilities of Deep Q-Network (DQN) models in order to achieve the most efficient route determination. This endeavor can potentially bring about significant changes in the courier and delivery service sector. The foundation of our unique methodology relies on an empirical inquiry, utilizing a comprehensive dataset including 178 observations obtained from motorcycle-based package delivery agents. Our research is carefully planned and executed using a comprehensive factorial experimental design. This design incorporates three crucial factors: the number of hidden layers, episodes, and epochs. The hidden layer parameter is set to a singular level, while the episode parameter is configured to explore five levels, and the epoch parameter is designed to travel four levels. The evaluation of our DQN models' performance is conducted utilizing the MSE metric as a measure. This assessment is carried out at every iterative cycle, ensuring thorough scrutiny. The central focus of our research centers on the intricate connection between episodes and epochs, and their influence on MSE. The findings of our study reveal that the association between episodes, epochs, and errors is not statistically significant although different level of episodes and epochs produces slightly different level of error.

Full Text:

PDF

References


A. Jaradat, B. Matalkeh, and W. Diabat, “Solving Traveling Salesman Problem using Firefly algorithm and K-means Clustering,” 2019 IEEE Jordan Int. Jt. Conf. Electr. Eng. Inf. Technol. JEEIT 2019 - Proc., no. September, pp. 586–589, 2019, doi: 10.1109/JEEIT.2019.8717463.

J. N. Macgregor and T. Ormerod, “Human performance on the traveling salesman problem,” Percept. Psychophys., vol. 58, no. 4, pp. 527–539, 1996, doi: 10.3758/BF03213088.

F. S. Gharehchopogh and B. Abdollahzadeh, “An efficient harris hawk optimization algorithm for solving the travelling salesman problem,” Cluster Comput., vol. 25, no. 3, pp. 1981–2005, 2022, doi: 10.1007/s10586-021-03304-5.

W. Gao, “New ant colony optimization algorithm for the traveling salesman problem,” Int. J. Comput. Intell. Syst., vol. 13, no. 1, pp. 44–55, 2020, doi: 10.2991/ijcis.d.200117.001.

B. P. Silalahi, N. Fathiah, and P. T. Supriyo, “Use of Ant Colony Optimization Algorithm for Determining Traveling Salesman Problem Routes,” J. Mat. “MANTIK,” vol. 5, no. 2, pp. 100–111, 2019, doi: 10.15642/mantik.2019.5.2.100-111.

A. François, Q. Cappart, and L.-M. Rousseau, “How to Evaluate Machine Learning Approaches for Combinatorial Optimization: Application to the Travelling Salesman Problem,” 2019, [Online]. Available: http://arxiv.org/abs/1909.13121

M. P. Li, P. Sankaran, M. E. Kuhl, R. Ptucha, A. Ganguly, and A. Kwasinski, “Task Selection by Autonomous Mobile Robots in A Warehouse Using Deep Reinforcement Learning,” Proc. - Winter Simul. Conf., vol. 2019-Decem, pp. 680–689, 2019, doi: 10.1109/WSC40007.2019.9004792.

T. N. Adi, H. Bae, and Y. A. Iskandar, “Interterminal truck routing optimization using cooperative multiagent deep reinforcement learning,” Processes, vol. 9, no. 10, 2021, doi: 10.3390/pr9101728.

S. Singh and A. Lodhi, “Study of Variation in TSP using Genetic Algorithm and Its Operator Comparison,” Int. J. Soft Comput. Eng., no. 3, p. 264, 2013.

H. A. Abdulkarim and I. F. Alshammari, “Comparison of Algorithms for Solving Traveling Salesman Problem,” Int. J. Eng. Adv. Technol., vol. 4, no. 6, pp. 76–79, 2015.

G. Ding and L. Qin, “Study on the prediction of stock price based on the associated network model of LSTM,” Int. J. Mach. Learn. Cybern., vol. 11, no. 6, pp. 1307–1317, 2020, doi: 10.1007/s13042-019-01041-1.

E. Xing and B. Cai, “Delivery Route Optimization Based on Deep Reinforcement Learning,” Proc. - 2020 2nd Int. Conf. Mach. Learn. Big Data Bus. Intell. MLBDBI 2020, pp. 334–338, 2020, doi: 10.1109/MLBDBI51377.2020.00071.

H. van Hasselt, A. Guez, and D. Silver, “Deep Reinforcement Learning with Double Q-Learning,” Proc. Thirtieth AAAI Conf. Artif. Intell., pp. 2094–2100, 2016.

Z. Hu, R. Beuran, and Y. Tan, “Automated Penetration Testing Using Deep Reinforcement Learning,” Proc. - 5th IEEE Eur. Symp. Secur. Priv. Work. Euro S PW 2020, pp. 2–10, 2020, doi: 10.1109/EuroSPW51379.2020.00010.

Y. Shen, N. Zhao, M. Xia, and X. Du, “A deep Q-learning network for ship stowage planning problem,” Polish Marit. Res., vol. 24, no. S3, pp. 102–109, 2017, doi: 10.1515/pomr-2017-0111.

S. Yigit and M. Mendes, “Which effect size measure isappropriate for one-way andtwo-way anovamodels? A Monte Carlo simulation study,” Revstat Stat. J., vol. 16, no. 3, pp. 295–313, 2018.

R. A. Armstrong, F. Eperjesi, and B. Gilmartin, “The application of analysis of variance (ANOVA) to different experimental designs in optometry,” Ophthalmic Physiol. Opt., vol. 22, no. 3, pp. 248–256, 2002, doi: 10.1046/j.1475-1313.2002.00020.x.

W. J. Ridgman, Experimentation in Biology., vol. 32, no. 4. London: Blackie, 1975. doi: 10.2307/2529293.

A. E. Verawati and A. N. S. Kiswanto, “the Effect of the Number of Hidden Layers in the Backpropagation in Case Study Weather Classification,” Proxies J. Inform., vol. 2, no. 2, p. 58, 2021, doi: 10.24167/proxies.v2i2.3212.

M. Uzair and N. Jamil, “Effects of Hidden Layers on the Efficiency of Neural networks,” Proc. - 2020 23rd IEEE Int. Multi-Topic Conf. INMIC 2020, pp. 1–6, 2020, doi: 10.1109/INMIC50486.2020.9318195.

K. G. Sheela and S. N. Deepa, “Review on methods to fix number of hidden neurons in neural networks,” Math. Probl. Eng., vol. 2013, 2013, doi: 10.1155/2013/425740.

E. Tonnizam Mohamad, M. Hajihassani, D. Jahed Armaghani, and A. Marto, “Simulation of blasting-induced air overpressure by means of Artificial Neural Networks,” Int. Rev. Model. Simulations, vol. 5, no. 6, pp. 2501–2506, 2012.

M. Van Otterlo and M. Wiering, Reinforcement learning and markov decision processes, vol. 12, no. May. 2012. doi: 10.1007/978-3-642-27645-3_1.




DOI: http://dx.doi.org/10.17977/um018v6i22023p188-198

Refbacks

  • There are currently no refbacks.


Copyright (c) 2023 Knowledge Engineering and Data Science

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Flag Counter

Creative Commons License


This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View My Stats