Please use this identifier to cite or link to this item: http://cuir.car.chula.ac.th/handle/123456789/14522
Title: แบบจำลองและขั้นตอนวิธีการแก้ปัญหาการจัดเส้นทางการขนส่งแบบเต็มคันรถอย่างต่อเนื่อง
Other Titles: Model and solution algorithms for truckload continuous move routing problem
Authors: ยศศิริ อดุลยศักดิ์
Advisors: มาโนช โลหเตปานนท์
Other author: จุฬาลงกรณ์มหาวิทยาลัย. คณะวิศวกรรมศาสตร์
Advisor's Email: Manoj.L@Chula.ac.th
Subjects: เส้นทางรถบรรทุก
การขนส่งด้วยรถบรรทุก
แบบจำลองทางคณิตศาสตร์
การขนส่งสินค้า
Issue Date: 2549
Publisher: จุฬาลงกรณ์มหาวิทยาลัย
Abstract: ปัญหาการเดินรถเที่ยวเปล่าเป็นปัญหาที่สำคัญในการวางแผนและดำเนินงานของการขนส่งแบบเต็มคันรถ ที่มีลักษณะการขนส่งสินค้าจากจุดเริ่มต้นตรงไปยังจุดปลายทางโดยไม่มีการแวะรับ-ส่งสินค้า ในระหว่างเส้นทางการขนส่ง ระยะทางเดินรถเที่ยวเปล่าที่เกิดขึ้นนั้น สามารถลดลงได้โดยใช้การควบรวมรอบการขนส่งตั้งแต่ 2 รอบหรือมากกว่า เพื่อให้เกิดเส้นทางการขนส่งที่ต่อเนื่อง งานวิจัยนี้มีวัตถุประสงค์เพื่อพัฒนาแบบจำลองทางคณิตศาสตร์ และขั้นตอนวิธีการแก้ปัญหาการเดินรถขนส่งแบบเต็มคันรถอย่างต่อเนื่อง สำหรับโครงข่ายการขนส่งขนาดใหญ่ที่มีความซับซ้อนสูงในด้านต่างๆ ได้แก่ ความเข้ากันได้ของประเภทรถและสินค้า ค่าใช้จ่ายที่ขึ้นอยู่กับแต่ละลักษณะการเดินรถและกรอบเวลา ผู้วิจัยได้ใช้แบบจำลองการเดินรถขนส่งแบบเต็มคันรถอย่างต่อเนื่อง ที่มีโครงสร้างจากแบบจำลองการแบ่งห้อง (Set Partitioning Formulation) โดยขั้นตอนวิธีการในการแก้ปัญหาถูกพัฒนาขึ้นใน 2 รูปแบบคือ การแก้ปัญหาแบบแม่นตรงโดยใช้เทคนิคการก่อกำเนิดสดมภ์เข้าช่วยในการแก้ปัญหา (Exact Column-generation-based Branch-and-bound Algorithm) และวิธีฮิวริสติก (Heuristic) ผลลัพธ์ที่ได้สามารถลดระยะทางการเดินรถเที่ยวเปล่าได้ระหว่าง 30% ถึง 42% โดยเมื่อปัญหามีขนาดใหญ่ขึ้นแบบจำลองดังกล่าวสามารถลดสัดส่วนการเดินรถเที่ยวเปล่าได้มากขึ้น แต่ในอัตราที่ต่ำลง นอกจากนี้ผลที่ได้จากทั้งสองขั้นตอนวิธีการแก้ปัญหานั้น แสดงถึงความแตกต่างเพียงเล็กน้อยของค่าใช้จ่ายที่ลดลงได้ โดยที่วิธีแม่นตรงนั้นจะได้ผลเฉลยที่ใกล้เคียงผลเฉลยที่ดีที่สุดมากกว่าวิธีฮิวริสติก แต่จะใช้เวลาในการแก้ปัญหานานกว่า ในการตัดสินใจในการเลือกรูปแบบวิธีการแก้ปัญหานั้น จะต้องพิจารณาถึงความคุ้มค่าของเวลาที่ลดลง ในการหาค่าคำตอบเปรียบเทียบกับผลเฉลยที่ดีขึ้นของทั้ง 2 รูปแบบขั้นตอนการแก้ปัญหา.
Other 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.
Description: วิทยานิพนธ์ (วศ.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2549
Degree Name: วิศวกรรมศาสตรมหาบัณฑิต
Degree Level: ปริญญาโท
Degree Discipline: วิศวกรรมโยธา
URI: http://cuir.car.chula.ac.th/handle/123456789/14522
Type: Thesis
Appears in Collections:Eng - Theses

Files in This Item:
File Description SizeFormat 
yossiri.pdf2.47 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.