Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
การแก้ปัญหาการรับส่งสินค้าหลายคลังสินค้าแบบเปิดที่มีข้อจำกัดด้านความจุและระยะทางด้วยขั้นตอนวิธีการหาค่าเหมาะที่สุดแบบอาณานิคมมด
Year (A.D.)
2023
Document Type
Thesis
First Advisor
Teerapol Silawan
Second Advisor
Chawit Sakulyuenyong
Third Advisor
Prachya Rungtweesuk
Faculty/College
Faculty of Engineering (คณะวิศวกรรมศาสตร์)
Department (if any)
Department of Electrical Engineering (ภาควิชาวิศวกรรมไฟฟ้า)
Degree Name
Master of Engineering
Degree Level
Master's Degree
Degree Discipline
Electrical Engineering
DOI
10.58837/CHULA.THE.2023.886
Abstract
The recently occurring global pandemic caused the mobile delivery service business to grow rapidly. One of the important aspects of this issue is the problem of finding the route of the company’s couriers to reduce the cost of the operation and increase the total gain. This study aims to find a route that has the least cost while the couriers do not carry the packages over their capacity limits or exceed the maximum distance they can travel, and all requests are satisfied. The problem was defined as a Distance-constrained Multi Depot Open Pickup and Delivery Problem (DMDOPDP). A program simulating the problem was developed and Ant Colony Optimization (ACO) was used to tackle the problem. Thorough analyses of ACO were conducted to study the effects of distance constraint, workload balancing function, the number of agents, and initial pheromone. Additionally, steady-state pheromone and ACO parameters' influence on the algorithm progression were discussed comprehensively. The results showed that incorporating the penalty method, the proposed ACO algorithm provided more reliable results with computation time trade-off compared to the benchmarking methods, demonstrating the capability of this method on the problem. The relatively low time complexity outcomes and its flexibility suggested that the algorithm can be modified and scaled to be used in real-world application productions.
Other Abstract (Other language abstract of ETD)
เหตุการณ์โรคระบาดที่เกิดขึ้นทำให้ธุรกิจการขนส่งสินค้าทางไกลเติบโตขึ้นอย่างรวดเร็ว ส่วนหนึ่งที่สำคัญของธุรกิจด้านนี้ คือ ปัญหาการหาเส้นทางเดินรถของผู้ขนส่งสินค้า เพื่อลดต้นทุนในการเดินรถ และทำกำไรได้มากขึ้น วิทยานิพนธ์นี้มีจุดประสงค์เพื่อหาเส้นทางที่มีค่าใช้จ่ายในการดำเนินงานต่ำที่สุด ขณะที่ผู้จัดส่งไม่รับสินค้าเกินความจุหรือระยะทางสูงสุดที่ตนเองรับได้ และพัสดุทั้งหมดได้รับการจัดส่งไปยังปลายทางที่ถูกต้อง ปัญหาข้างต้นถูกให้คำจำกัดความไว้ว่าเป็น ปัญหาการรับและการส่งสินค้าแบบเปิดกรณีมีคลังสินค้าหลายแห่งที่มีข้อจำกัดทางความจุและระยะทาง โปรแกรมที่ใช้จำลองปัญหาถูกพัฒนาขึ้น และใช้ขั้นตอนวิธีอาณานิคมมดในการแก้ไขปัญหาดังกล่าว มีการวิเคราะห์อย่างละเอียดเพื่อศึกษาผลกระทบของการจำกัดระยะทาง ฟังก์ชันการปรับสมดุลภาระงาน จำนวนของมดจำลอง และฟีโรโมนเริ่มต้น นอกจากนี้ อิทธิพลของฟีโรโมนในสภาวะคงตัวและตัวแปรเสริมของขั้นตอนวิธีอาณานิคมมดที่มีต่อการทำงานของขั้นตอนวิธีได้มีการอธิบายอย่างละเอียด ผลการศึกษาพบว่าเมื่อนำวิธีการลงโทษเข้ามาใช้ ขั้นตอนวิธีอาณานิคมมดที่เสนอนั้นให้ผลลัพธ์ที่ผ่านเงื่อนไขได้ดีกว่าวิธีที่นำมาเปรียบเทียบ แสดงถึงศักยภาพของวิธีนี้ในการแก้ไขปัญหาที่ได้ตั้งไว้ ความซับซ้อนด้านเวลาที่ต่ำและความยืดหยุ่นของขั้นตอนวิธีบ่งบอกถึงความสามารถในการถูกปรับแต่งและขยายขนาดเพื่อนำไปใช้อุตสาหกรรมจริงได้
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Indravattana, Teerawat, "Solving multi-depot open pickup and delivery problem with capacity and distance restrictions by ant colony optimization algorithm" (2023). Chulalongkorn University Theses and Dissertations (Chula ETD). 11955.
https://digital.car.chula.ac.th/chulaetd/11955