Traveling Salesman Problem in Warehouse by using Hill Climbing and Simulated Annealing algorithms on Microsoft Excel

Abstract

Order Picking is one operation in the warehouse, that has been using 55-65% of the warehouse’s total cost [1]. Therefore, increasing the efficiency of this process will help to reduce time-consuming and reduce the total cost of the entire warehouse. This problem is also known as the Traveling Salesman Problem which is an NP-Hard problem. This research uses the Hill Climbing Algorithm to solve the problem due to its simplicity, fast and cheap and uses the Simulated Annealing Algorithm because it's quite a simple method and also there is a chance that the result will be Global. This program works on Microsoft Excel. In this research the scope is set by , the number of positions of shelves is set by 5, 10, 15, 20 and 30.The number of running-time of the Hill Climbing Algorithm is as same as a number of running-times of the Simulated Annealing Algorithm. For Simulated Annealing Algorithm is set of Initial T is 10, 50, 100, 250 and 500 and set the rate of cooling (alpha) at 0.5 and 0.99. The results show when the running-time increase the result of Simulated Annealing Algorithm have a better solution than Hill Climbing Algorithm. The results also show that the initial T, the rate of cooling (alpha) affects the result, which, if increased, results in better results. But the working time is longer as well

การหยิบสินค้าเป็นหนึ่งการดำเนินการในคลังสินค้าที่ใช้ต้นทุนสูงถึงร้อยละ 55-65 ของต้นทุนทั้งหมดในคลังสินค้า [1] ดังนั้นการเพิ่มประสิทธิภาพของกระบวนการนี้จะช่วยลดเวลาและลดต้นทุนโดยรวมของคลังสินค้าทั้งหมด ปัญหานี้เป็นที่รู้จักกันว่าปัญหาพนักงานขายเดินทางซึ่งเป็นปัญหา NP-Hard การวิจัยครั้งนี้ใช้ขั้นตอนวิธีการปีนเขาเพื่อแก้ปัญหา เนื่องจากความเรียบง่ายรวดเร็ว และราคาถูกและใช้ขั้นตอนวิธีการจำลองการอบเหนียว เนื่องจากมันเป็นวิธีการที่ง่ายและมีโอกาสที่ผลลัพธ์จะเป็นคำตอบที่ดีที่สุด โปรแกรมนี้ทำงานบนไมโครซอฟท์ เอกซ์เซล ในการวิจัยนี้กำหนดขอบเขตโดยจำนวนตำแหน่งของชั้นวางสินค้าถูกกำหนดไว้ที่ 5,10,15, 20 และ 30 จำนวนรอบการทำงานของขั้นตอนวิธีการปีนเขาเท่ากันกับจำนวนรอบการทำงานของขั้นตอนวิธีการจำลองการอบเหนียว สำหรับขั้นตอนวิธีการจำลองการอบเหนียวค่าเริ่มต้นของอุณหภูมิ คือ 10, 50,100, 250 และ 500 และกำหนดอัตราการลดลงของอุณหภูมิ (อัลฟา) ที่ 0.5 และ 0.99 ผลลัพธ์แสดงขึ้นเมื่อเวลาทำงานเพิ่มผลลัพธ์ของขั้นตอนวิธีการจำลองการอบเหนียวมีวิธีแก้ปัญหาที่ดีกว่าขั้นตอนวิธีการปีนเขา ผลลัพธ์ยังแสดงว่าค่าเริ่มต้นของอุณหภูมิ อัตราการลดลงของอุณหภูมิ (อัลฟา) มีผลต่อผลลัพธ์ซึ่งหากเพิ่มขึ้นจะส่งผลให้ผลลัพธ์ที่ได้ดีขึ้น แต่เวลาทำงานก็นานขึ้นเช่นกัน