แบบจำลองและขั้นตอนวิธีการแก้ปัญหาการจัดเส้นทางการขนส่งแบบเต็มคันรถอย่างต่อเนื่อง

Model and solution algorithms for truckload continuous move routing problem

Name: ยศศิริ อดุลยศักดิ์

ThaSH: เส้นทางรถบรรทุก

ThaSH: การขนส่งด้วยรถบรรทุก

ThaSH: แบบจำลองทางคณิตศาสตร์

ThaSH: การขนส่งสินค้า

Abstract: ปัญหาการเดินรถเที่ยวเปล่าเป็นปัญหาที่สำคัญในการวางแผนและดำเนินงานของการขนส่งแบบเต็มคันรถ ที่มีลักษณะการขนส่งสินค้าจากจุดเริ่มต้นตรงไปยังจุดปลายทางโดยไม่มีการแวะรับ-ส่งสินค้า ในระหว่างเส้นทางการขนส่ง ระยะทางเดินรถเที่ยวเปล่าที่เกิดขึ้นนั้น สามารถลดลงได้โดยใช้การควบรวมรอบการขนส่งตั้งแต่ 2 รอบหรือมากกว่า เพื่อให้เกิดเส้นทางการขนส่งที่ต่อเนื่อง งานวิจัยนี้มีวัตถุประสงค์เพื่อพัฒนาแบบจำลองทางคณิตศาสตร์ และขั้นตอนวิธีการแก้ปัญหาการเดินรถขนส่งแบบเต็มคันรถอย่างต่อเนื่อง สำหรับโครงข่ายการขนส่งขนาดใหญ่ที่มีความซับซ้อนสูงในด้านต่างๆ ได้แก่ ความเข้ากันได้ของประเภทรถและสินค้า ค่าใช้จ่ายที่ขึ้นอยู่กับแต่ละลักษณะการเดินรถและกรอบเวลา ผู้วิจัยได้ใช้แบบจำลองการเดินรถขนส่งแบบเต็มคันรถอย่างต่อเนื่อง ที่มีโครงสร้างจากแบบจำลองการแบ่งห้อง (Set Partitioning Formulation) โดยขั้นตอนวิธีการในการแก้ปัญหาถูกพัฒนาขึ้นใน 2 รูปแบบคือ การแก้ปัญหาแบบแม่นตรงโดยใช้เทคนิคการก่อกำเนิดสดมภ์เข้าช่วยในการแก้ปัญหา (Exact Column-generation-based Branch-and-bound Algorithm) และวิธีฮิวริสติก (Heuristic) ผลลัพธ์ที่ได้สามารถลดระยะทางการเดินรถเที่ยวเปล่าได้ระหว่าง 30% ถึง 42% โดยเมื่อปัญหามีขนาดใหญ่ขึ้นแบบจำลองดังกล่าวสามารถลดสัดส่วนการเดินรถเที่ยวเปล่าได้มากขึ้น แต่ในอัตราที่ต่ำลง นอกจากนี้ผลที่ได้จากทั้งสองขั้นตอนวิธีการแก้ปัญหานั้น แสดงถึงความแตกต่างเพียงเล็กน้อยของค่าใช้จ่ายที่ลดลงได้ โดยที่วิธีแม่นตรงนั้นจะได้ผลเฉลยที่ใกล้เคียงผลเฉลยที่ดีที่สุดมากกว่าวิธีฮิวริสติก แต่จะใช้เวลาในการแก้ปัญหานานกว่า ในการตัดสินใจในการเลือกรูปแบบวิธีการแก้ปัญหานั้น จะต้องพิจารณาถึงความคุ้มค่าของเวลาที่ลดลง ในการหาค่าคำตอบเปรียบเทียบกับผลเฉลยที่ดีขึ้นของทั้ง 2 รูปแบบขั้นตอนการแก้ปัญหา.

Abstract: The problem of excessive empty backhaul distances is a major challenge in the planning and operation of truckload transportation, in which goods are picked up from an origin and delivered to a destination without mid-route pickups or deliveries. The empty backhaul distances can be reduced by combining two or more truckload trips together to form a sequence of continous move truckload trips. The objectives of this research are to develop a truckload continuous move optimization model and solution algorithms of this problem for large-scale transportain network, incorporating major operational complexities, namely, fleet-commodity compatility, trip-based cost function, and time windows. We present a Continuous Move Optimization Model (CMO), which is based on the set partitioning formulation. We develop two solution approaches -- an exact column-generation-based branch-and-bound algorithm and a heuristic algorithm -- which yield significant empty haul distance reduction under relatively short runtimes, and provide a comparison study measuring the effectiveness and applicability of the two methods. The results show substantial reduction in empty haul distances, ranging from 30% to 42%. Our findings indicate that as problems become larger, empty haul reduction increases but at a decreasing rate. The comparison between the branch-and-bound with column generation approach and the heuristic shows better cost savings with the former and markedly better runtimes with the latter.

จุฬาลงกรณ์มหาวิทยาลัย. สถาบันวิทยบริการ

Address: กรุงเทพมหานคร (Bangkok)

Email: cuir@car.chula.ac.th

Name: มาโนช โลหเตปานนท์

Role: ที่ปรึกษา

Created: 2554-02-16

Modified: 2554-02-16

Created: 2549

Issued: 2554-02-16

วิทยานิพนธ์/Thesis

application/pdf

tha

DegreeName: วิทยาศาสตรมหาบัณฑิต

Level: ปริญญาโท

Descipline: วิศวกรรมโยธา

Grantor: จุฬาลงกรณ์มหาวิทยาลัย

©copyrights จุฬาลงกรณ์มหาวิทยาลัย

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	yossiri.pdf	2.41 MB	856	2024-12-23 09:50:52

ใช้เวลา

0.019997 วินาที