Page Header

Home > Vol 33, No 3 (2023) > Arree

Comparison of Vehicle-Routing for Grocery Car Service (Rod Phum-punag) by Applying the Travelling Salesman Problem with the Saving Algorithm, the Nearest Neighbor Algorithm, and the Microsoft Excel Solver: A Case Study of Service Area in Nong Bua Sala Sub

Worapon Arree, Nattiya Wonglakorn, Ratirat Aunsawat, Surachet Kaewfai, Chat Phayungwiwatthanakoo

Abstract


รถขายของชำ (รถพุ่มพวง) มีบทบาทในต่างจังหวัดของประเทศไทย โดยเฉพาะช่วงวิกฤตการณ์ไวรัสโควิด-19 ที่คนไทยส่วนใหญ่ต้องอยู่บ้าน อย่างไรก็ตาม การไม่วางแผนเส้นทางทำให้สิ้นเปลืองค่าใช้จ่ายและเวลา นอกจากนี้ การเร่งทำเวลาการให้บริการทำให้มีการขับรถย้อนศร ซึ่งผิดกฎจราจรและอาจเกิดอุบัติเหตุได้ งานวิจัยนี้มีวัตถุประสงค์เพื่อจัดเส้นทางการให้บริการรถพุ่มพวงโดยประยุกต์ใช้ปัญหาการเดินทางของพนักงานขาย โดยเปรียบเทียบวิธีเพื่อนบ้านใกล้ที่สุด วิธีเซฟวิ่งอัลกอริทึม และการใช้ฟังก์ชันเอ็กเซลโซลเวอร์ ในพื้นที่ตำบลหนองบัวศาลา จังหวัดนครราชสีมา ภายใต้ข้อจำกัด คือ 1) สามารถให้บริการครบทุกจุดบริการ 2) ไม่ละเมิดกฎจราจร และ 3) ระยะทางรวมหลังการจัดเส้นทางควรน้อยกว่าเดิม ข้อมูลเส้นทาง ระยะทาง จุดบริการ และพิกัด รวบรวมด้วย จีโอ แทร็คเกอร์ แอพพลิเคชั่น มีจุดจอด 45 แห่ง (ระยะทางรวม 31.24 กิโลเมตร) โดยเริ่มต้นจากตลาดสดประปา ทั้งนี้ การใช้ฟังก์ชันเอ็กเซลโซลเวอร์แสดงระยะทางสั้นที่สุด ซึ่งระยะทางลดลงร้อยละ 18.85 ขณะที่ วิธีเพื่อนบ้านใกล้ที่สุด และวิธีเซฟวิ่งอัลกอริทึม (เริ่มจากตลาดสดประปา หรือตลาดสุรนคร) มีระยะทางเพิ่มขึ้น ร้อยละ 0.58 ร้อยละ 9.99 และ ร้อยละ 8.77 ตามลำดับ การวิจัยนี้สามารถประยุกต์การจัดเส้นทางรถที่มีลักษณะวิ่งวนเป็นรอบ (มิลค์ รัน) เช่น รถสองแถว หรือรถรับส่งพนักงาน เพื่อเพิ่มประสิทธิภาพการขนส่ง

Grocery car servicing (Rod Phum-puang) plays a role in upcountry consumers in Thailand, especially in the Coronavirus disease (COVID-19) crisis when most Thai population have to stay home. However, Rod Phum-puang services confront a non-plan of vehicle routing problem, wasting both costs and time. Additionally, speeding up service time has resulted in driving against the flow of traffic that breaks the traffic rules, and may cause accidents. This research aimed to manage the vehicle routing of Rod Phum-puang service using the application of Travelling Salesman Problem (TSP). Rod Phum-puang service routing's solving methods were determined by the saving algorithm, the nearest neighbor algorithm, and the Microsoft Excel Solver in Nong Bua Sala Sub-district, using Nakhon Ratchasima Province as a case study. The scope of this research included: 1) providing service at all service stops, 2) compliance with traffic rules, and 3) less total distance after vehicle routing. The Geo-tracker Application collected the route information about distance, service stops, and location coordinates revealing 45 nodes with the total distance about 31.24 km starting from Prapa Fresh Market. Then, the Microsoft Excel Solver showed the shortest distance of the Rod Phum-puang service route, with the decrease at 18.85% compared to the original route. In contrast, the nearest neighbor algorithm, and the saving algorithm starting from Prapra Fresh Market or Suranakhon Market showed an increasing distance of about 0.58%, 9.99%, and 8.77%, respectively. These results can be applied to transportation works running around nodes (milk run) such as school buses or staff shuttle to increase transportation efficiency.


Keywords



[1] Thais PBS News. (2021, Junuary). Rod Phumpuang double sales after the people stayed at home to stop COVID-19. [Online] (in Thai). Available: https://news.thaipbs.or.th/content/ 290077

[2] E. Osaba, X. S. Yang, and J. D. Ser, “Traveling salesman problem: a perspective review of recent research and new results with bio-inspired metaheuristics,” in Nature-Inspired Computation and Swarm Intelligence Algorithms, Theory and Applications, 1st ed. London, UK: Academic Press, 2020, pp. 135–164.

[3] J. Pekar, I. Brezina, J. Kultan, I. Ushakova, and O. Dorokhov, “Computer tools for solving the traveling salesman problem,” Development Management, vol. 18, no. 1, pp. 25–39, 2020.

[4] W. Y. Liu, C. C. Lin, C. R. Chiu, Y. S. Tsao, and O. Wang, “Minimizing the carbon footprint for the time-dependent heterogeneous-fleet vehicle routing problem with alternative paths,” Sustainability, vol. 6, pp. 4658–4684, 2014.

[5] R. Pitacaso, Metaheuristic to solve the problems of production planning and logistics management, 1st ed. Bangkok: Technology Promotion Association (Thailand-Japan), 2011, pp. 1–17 (in Thai).

[6] K. Jit-eua, “Vehicle routing problem with stochastic demand,” Navaminda Kasatriyadhiraj Royal Air Force Academy, vol. 13, no. 13, pp. 19–24, 2017 (in Thai).

[7] T. Pichpibul and R. Kawtummachai, “A heuristic approach based on Clarke-Wright algorithm for open vehicle routing problem,” The Scientific World Journal, vol. 2013, 2013.

[8] G. Kizilateş and F. Nuriyeva, “On the nearest neighbor algorithms for the traveling salesman problem,” in Proceedings CCSEIT-2013, in Advances in Computational Science, Engineering and Information Technology, 2013, pp. 111–118.

[9] J. Vasilev, “Solving the traveling salesman problem with the alldifferent constraint in MS excel,” in Proceedings ICAICTSEE-2015, 2015, pp. 420–423.

[10] S. Winyangkul, N. Jeenaboonroing, P. Ananaue, N. Chaiwongsakda, P. Kuntawong, N. Muak-Kreua, and T. Jantapoon, “An application of the travelling salesman problem case study: Routing for streetcar tour of the Chiang Rai Municipality,” Industrial Technology Lampang Rajabhat University Journal, vol. 7, no. 12, pp. 85–97, 2014 (in Thai).

[11] W. Sawangyat, “Three alternative approaches to design travelling route case study Ayutthaya,” Journal of Rangsit Graduate Studies in Business and Social Sciences, vol. 4, no. 2, pp. 64–77, 2018 (in Thai).

[12] S. Suksee and T. Meejarern, “Minimization of transportation cost by applying the vehicle routing problem: Case study of car accessory company,” Kasem Bundit Engineering Journal, vol. 9, no. 1, pp. 69–84, 2019 (in Thai).

[13] P. Saelee, W. Wijitpongsa, and H. Puangyam, “The case study of “Ratsamee 2015 Limited Partnership”: A vehicle routing problem solved using linear programming,” Industrial Technology Lampang Rajabhat University Journal, vol. 10, no. 1, pp. 48–59, 2017 (in Thai).

[14] A. Lateh, S. Suthammanon, N. Sirivongpisal, and M. Tehyo, “Solving a vehicle routing problem with time window for transportation service planning for elderly people: A case study of Hatyai District Songkhla Province,” Princess of Naradhiwas University Journal, vol. 11, no. 2, pp. 117–131, 2019 (in Thai).

[15] K. Jitrpornsap and K. Sangdee, “Improvement of the Transportation Route of Ready-To-Drink Dairy Products in Bag Form: Case Study of Pamala Transport Agent in Nakhon Si Thammarat Province,” in Proceedings North Bangkok University National Conference Academic Year 2020, 2020, pp. 141–153 (in Thai).

[16] K. Sueni, “The Routes Transportation by Comparison between Using the Saving Algorithm and the Nearest Neighbor Algorithm,” Economics and Business Administration Journal Thaksin University, vol. 12, no. 2, pp. 1–14, 2020 (in Thai).

[17] J. Gao, F. Gu, P. Hu, Y. Xie, and B. Yao, “Automobile chain maintenance parts delivery problem using an improved ant colony algorithm,” Advances in Mechanical Engineering, vol. 8, no. 9, pp. 1–13, 2016.

[18] T. Karthya and S. Priyanka, “Comparative Analysis of the optimal solutions of Travelling Salesman Problem,” in Proceedings 11th National Conference on Mathematical Techniques and Applications, 2019, pp. 0200301–0200307.

[19] F. Carrabs, R. Cerulli, and A. Sciomachen “An exact approach for the grocery delivery problem in urban areas,” Soft Computing, vol. 21, no. 9, pp. 2439–2450, 2017.

[20] Z. Hashim and W.R. Ismail, “Self-drive tourism route in terengganu: An application of goal programming model,” WR Ismail. Sains Humanika, vol. 9, no. 1–5, pp. 51–57, 2017.

Full Text: PDF

DOI: 10.14416/j.kmutnb.2022.09.005

ISSN: 2985-2145