Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
A heuristic approach for the same-day pickup and delivery problem
Year (A.D.)
2019
Document Type
Thesis
First Advisor
พิศิษฎ์ จารุมณีโรจน์
Faculty/College
Faculty of Engineering (คณะวิศวกรรมศาสตร์)
Department (if any)
Department of Industrial Engineering (ภาควิชาวิศวกรรมอุตสาหการ)
Degree Name
วิศวกรรมศาสตรมหาบัณฑิต
Degree Level
ปริญญาโท
Degree Discipline
วิศวกรรมอุตสาหการ
DOI
10.58837/CHULA.THE.2019.1329
Abstract
งานวิจัยนี้มุ่งเน้นการพัฒนาแบบจำลองทางคณิตศาสตร์ และวิธีการฮิวริสติกสำหรับปัญหาการรับและส่งพัสดุภายในวันทำการเดียวกัน (Deterministic SDPD) โดยปัญหาดังกล่าวจัดเป็นปัญหาการจัดเส้นทางเดินรถรูปแบบหนึ่ง ซึ่งรถสามารถเดินทางออกจากท่ารถได้ตามรอบรถ (wave) ที่กำหนดเท่านั้น นอกจากนี้เวลาการปรากฏ (arrival time) ของคำสั่งของลูกค้าทั้งหมดเป็นข้อมูลที่ทราบล่วงหน้าตั้งแต่ต้นวันทำการ ทั้งนี้คำสั่งของลูกค้าหนึ่งๆ จะประกอบไปด้วยจุดรับ และจุดส่งพัสดุที่แตกต่างกัน และไม่จำเป็นต้องถูกมอบหมายให้อยู่ในรอบรถเดียวกัน แต่จำเป็นต้องจัดส่งพัสดุให้ทันภายในวันทำการ หากเลือกที่จะรับพัสดุของคำสั่งนั้นๆ ผู้วิจัยได้ทำการศึกษาผลกระทบของการเพิ่มจำนวนรอบรถในวันทำการที่มีต่อประสิทธิภาพของการหาคำตอบด้วยวิธีแม่นตรง (exact method) บนกลุ่มตัวอย่างที่สุ่มสร้างขึ้นจำนวน 40 ตัวอย่าง โดยผู้วิจัยพบว่า การเพิ่มขึ้นของจำนวนรอบรถในวันทำการส่งผลให้ประสิทธิภาพการหาคำตอบด้วยวิธีแม่นตรงลดลงอย่างมาก ผู้วิจัยจึงได้ทำการพัฒนาฮิวริสติก Adaptive Large Neighborhood Search (ALNS) สำหรับปัญหาดังกล่าว ซึ่งเมื่อเปรียบเทียบกับวิธีการหาคำตอบแบบแม่นตรงแล้ว ผู้วิจัยพบว่า คำตอบที่ได้จาก ALNS ส่วนใหญ่มีคุณภาพเทียบเท่า หรือดีกว่าคำตอบที่ได้จากวิธีแม่นตรงภายใต้กรอบเวลาในการหาคำนวณที่จำกัด แต่กลับใช้เวลาในการหาคำตอบต่ำกว่ามาก
Other Abstract (Other language abstract of ETD)
This research focuses on the development of an Integer Programming (IP) model and a Heuristic approach for the Deterministic Same-day Pickup and Delivery Problem (Deterministic SDPD), where a vehicle is allowed to leave the depot at specific time periods, called waves, and order arrivals are known in advance. Moreover, each customer order comprises of a pair of services - namely pickup and delivery - not necessarily be completed in the same wave but has to be delivered by the end of the day if the request has been accepted and picked. We explored how numbers of daily dispatch waves affected the IP optimization performance on 40 randomly generated instances. We found that, by increasing the numbers of daily dispatch waves, the IP optimization performance dropped tremendously as expected. Therefore, an Adaptive Large Neighborhood Search (ALNS) heuristic is proposed. When compared to the results from the IP solver, most ALNS solutions are equal or better in terms of solution quality; but, with tractable computational time.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
ศรีตระกูล, วิชญะ, "วิธีการฮิวริสติกสำหรับปัญหาการรับและส่งพัสดุภายในวันทำการเดียวกัน" (2019). Chulalongkorn University Theses and Dissertations (Chula ETD). 9705.
https://digital.car.chula.ac.th/chulaetd/9705