Optimizing the Vehicle Routes of End Devices Installation for Internet Speed Test Platform Using the Hybrid OVRP-TSP Model
Article Sidebar
Main Article Content
Abstract
The National Broadcasting and Telecommunications Commission (NBTC) Thailand has implemented a policy to evaluate the quality of Fixed Broadband (FBB) internet in response to numerous customer complaints across the country. One of the proposed solutions for assessing FBB internet quality involves installing end devices to test internet speeds with various internet service providers in the experimental area. However, due to the presence of many providers within the area, planning the vehicle routes for this mission is challenging, particularly given resource limitations. This paper proposes an approach to optimize the vehicle routes for the installation of internet speed test devices. The objective is to minimize the total transportation time, thereby reducing overall costs and carbon emissions. A hybrid OVRP-TSP (Open Vehicle Routing Problem - Traveling Salesman Problem) approach is introduced to address this challenge and is compared with the Clake-Wright Savings Heuristic, the Nearest Neighbor Heuristic, and existing methods. Furthermore, the hybrid OVRP-TSP is tested on 30 provider locations in the eastern region of Thailand. The results demonstrate that the hybrid OVRP-TSP provides the best solution across all measures (Total Time, Total Cost, and Total Emissions), while the other methods also yield efficient solutions compared to existing approaches.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
References
NBTC, “NBTC Thailand,” 2022. [Online]. Available: https://www.nbtc.go.th. [Accessed: 01-Jun-2022].
G. Laporte, “The traveling salesman problem: An overview of exact and approximate algorithms,” European Journal of Operational Research, vol. 59, no. 2, pp. 231–247, 1992.
K. L. Hoffman, M. Padberg and G. Rinaldi, “Traveling Salesman Problems,” Encyclopedia of Operations Research and Management Science, vol. 1, pp. 1573–1578, 2013.
T. Pichpibul and R. Kawtummachai, “A heuristic approach based on Clarke-Wright algorithm for open vehicle routing problem,” The Scientific World Journal, vol. 2013, no. 1, p. 874349, 2013.
I. Masudin, R. F. Sa’Diyah, D. M. Utama, D. P. Restuputri and F. Jie, “Capacitated Vehicle Routing Problems: Nearest Neighbour vs. Tabu Search,” International Journal Compututer Theory and Engineering, vol. 11, no. 4, pp. 76–79, 2019.
F. Camci, “The travelling maintainer problem: Integration of condition-based maintenance with the travelling salesman problem,” Journal of the Operational Research Society, vol. 65, no. 9, pp. 1423–1436, 2014.
Q. M. Ha, Y. Deville, Q. D. Pham and M. H. H`a, “On the min-cost Traveling Salesman Problem with Drone,” Transportation Research Part C: Emerging Technologies, vol. 86, pp. 597–621, Jan. 2018.
C. C. Murray and A. G. Chu, “The flying side-kick traveling salesman problem: Optimization of drone-assisted parcel delivery,” Transportation Research Part C: Emerging Technologies, vol. 54, pp. 86–109, May 2015.
R. Roberti and M. Wen, “The Electric Traveling Salesman Problem with Time Windows,” Trans-portation Research Part E: Logistics and Transportation Review, vol. 89, pp. 32–52, May 2016.
L. Schrage, “Formulation and structure of more complex/realistic routing and scheduling problems,” Networks, vol. 11, no. 2, pp. 229–232, 1981.
Y. Niu, Z. Yang, P. Chen and J. Xiao, “Optimizing the green open vehicle routing problem with time windows by minimizing comprehensive routing cost,” Journal of Cleaner Production, vol. 171, pp. 962–971, Jan. 2018.
R. Atefi, M. Salari, L. C. Coelho and J. Renaud, “The open vehicle routing problem with decoupling points,”European Journal of Operational Research, vol. 265, no. 1, pp. 316–327, 2018.
I. K. Altinel and T. Oncan, “A new enhancement of the Clarke and Wright savings heuristic for the capacitated vehicle routing problem,” The Journal of the Operational Research Society, vol. 56, no. 8, pp. 954–961, 2005.
H. Seyyedhasani and J. S. Dvorak, “Using the Vehicle Routing Problem to reduce field completion times with multiple machines,” Computers and Electronics in Agriculture, vol. 134, pp. 142–150, Mar. 2017.
H. Cipta and M. Fitriana Hasibuan, “Optimal Vehicle Routing Problem (VRP) For The Distribution Of Medical Devices By Applying The Clarke-Wright Algorithm,” International Journal of Science and Environment, vol. 3, no. 1, pp. 7–12, 2023.
R. Nurcahyo, D. A. Irawan and F. Kristanti, “The Effectiveness of the Clarke & Wright Savings Algorithm in Determining Logistics Distribution Routes (case study PT.XYZ),” in The 5th International Conference of Biospheric Harmony Advanced Research (ICOBAR 2023), E3S Web of Conferences, vol. 426, p. 01107, 2023.
L. Du and R. He, “Combining Nearest Neighbor Search with Tabu Search for Large-Scale Vehicle Routing Problem,” Physics Procedia, vol. 25, pp. 1536–1546, 2012.
T. S. Alemayehu and J. H. Kim, “Efficient Nearest Neighbor Heuristic TSP Algorithms for Reducing Data Acquisition Latency of UAV Relay WSN,” Wireless Personal Communications, vol. 95, no. 3, pp. 3271–3285, Aug. 2017.
N. Mostafa and A. Eltawil, “Solving the heterogeneous capacitated vehicle routing problem using K-means clustering and valid inequalities,” in Proceedings of the International Conference on Industrial Engineering and Operations Management, no. October, pp. 2239–2249, 2017.
A. Jaradat, B. Matalkeh and W. Diabat, “Solving Traveling Salesman Problem using Firefly algorithm and K-means Clustering,” 2019 IEEE Jordan International Joint Conference on Electrical Engineering and Information Technology (JEEIT), Amman, Jordan, pp. 586-589, 2019.
D. G. S´anchez, A. Tabares, L. T. Faria, J. C. Rivera and J. F. Franco, “A Clustering Approach for the Optimal Siting of Recharging Stations in the Electric Vehicle Routing Problem with Time Windows,” Energies, vol. 15, no. 7, 2022.
A. Kantasa-ard, T. Chargui, A. Bekrar, A. Aitel cadi and Y. Sallez, “Dynamic sustainable multiple-depot vehicle routing problem with simultaneous pickup and delivery in the context of the physical internet,” Journal of International Logistics and Trade, vol. 21, no. 3, pp. 110–134,2023.
V. Furnon and L. Perron, “OR-Tools Routing Library (Version v9.10),” Google, 2024.
K. M. R. Hoen, T. Tan, J. C. Fransoo, and G. J. Van Houtum, “Effect of carbon emission regulations on transport mode selection in supply chains,” Eindhoven University of Technoogy, 2010.