Chulalongkorn University Theses and Dissertations (Chula ETD)

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

Other Title (Parallel Title in Other Language of ETD)

Model and solution algorithms for truckload continuous move routing problem

Year (A.D.)

2006

Document Type

Thesis

First Advisor

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

Faculty/College

Faculty of Engineering (คณะวิศวกรรมศาสตร์)

Degree Name

วิศวกรรมศาสตรมหาบัณฑิต

Degree Level

ปริญญาโท

Degree Discipline

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

DOI

10.58837/CHULA.THE.2006.1379

Abstract

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

Other Abstract (Other language abstract of ETD)

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.

Link to Full Text

Share

COinS