Chulalongkorn University Theses and Dissertations (Chula ETD)

แบบจำลองและวิธีค้นหาเฉพาะแห่งขนาดใหญ่สำหรับปัญหาการจัดเส้นทางขนส่งสินค้าที่มีกรอบเวลา

Other Title (Parallel Title in Other Language of ETD)

Model and large scale neighbourhood search algorithms for vehicle routing problem with time-windows

Year (A.D.)

2008

Document Type

Thesis

First Advisor

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

Faculty/College

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

Degree Name

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

Degree Level

ปริญญาโท

Degree Discipline

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

DOI

10.58837/CHULA.THE.2008.1344

Abstract

ปัญหาการเดินรถเที่ยวเปล่าจัดเป็นปัญหาที่สำคัญในการวางแผนขนส่ง ระยะการเดินรถเที่ยวเปล่านี้สามารถลดลงได้ด้วยการควบรวมการขนส่งเข้าด้วยกัน เพื่อให้เกิดการเดินรถขนส่งสินค้าแบบกระจายสินค้าหลายจุด (Multi Drop Distribution) อย่างไรก็ดีการวางแผนการขนส่งสินค้าแบบกระจายสินค้าหลายจุดนั้นจะต้องมีการวางแผนการจัดส่งสินค้าที่ดี กล่าวคือ มีวิธีในการแก้ปัญหาการจัดเส้นทางการเดินรถ (vehicle Routing Problem) ที่มีประสิทธิภาพ การจัดเส้นทางการเดินรถชนิดมีกรอบเวลา คือการหาเส้นทางการเดินรถในการขนส่งสินค้าไปยังกลุ่มลูกค้าทั้งหมดที่มีค่าใช้จ่ายต่ำที่สุดโดยลูกค้าแต่ละรายมีกรอบเวลาในการรับสินค้าที่ชัดเจน เส้นทางเดินรถขนส่งสินค้าจะต้องคำนึงถึงข้อจำกัดด้านกรอบเวลาและความจุของยานพาหนะ ยิ่งไปกว่านั้นความยากของการจัดเส้นทางการเดินรถอีกประการหนึ่งคือมีข้อจำกัดจำนวนมากที่เกิดขึ้นเนื่องจากสภาพการทำงานจริง ดังนั้นงานวิจัยนี้มีจุดประสงค์เพื่อพัฒนาการขนส่งสินค้าและสร้างโปรแกรมคอมพิวเตอร์ โดยนำเสนอวิธีกำเนิดสดมภ์ที่เป็นวิธีการหาผลเฉลยที่ดีที่สุดและวิธีการค้นหาเฉพาะแห่งขนาดใหญ่เชิงความน่าจะเป็นวิธีฮิวริสติคที่มีประสิทธิภาพในการแก้ปัญหาการจัดเส้นทางการเดินรถ สามารถหาผลเฉลยที่ดีได้ในระยะเวลาการประมวลที่เหมาะสม พิจารณาผลลัพธ์ที่ได้จากแบบจำลองพบว่า สามารถลดระยะทางการเดินรถเที่ยวเปล่าได้ประมาณร้อยละ 68 ถึง 72 ยิ่งไปกว่านั้นยังสามารถลดค่าใช้จ่ายลงได้ประมาณร้อยละ 42 เปรียบเทียบกับการขนส่งที่ไม่มีการจัดการการเดินเที่ยวเปล่า

Other Abstract (Other language abstract of ETD)

The problem of excessive empty haul is a major problem in transportation planning. One of the solutions is to combine trips together to form a multi drop distribution. However, multi drop distribution planning is complicated and has to be efficiently managed. The objective of the vehicle routing with time windows (VRPTW) is to determine a set of feasible routings for goods delivery to a set of customers within prescribed time windows while minimizing cost. The routes must also satisfy time windows, truck capacity, and other operational constraints. We present a column generation based exact algorithm and an improvement heuristics for the problem based on an extension of Large-scale Neighborhood Search (LNS) and probability theory. The proposed algorithm can find near-optimal solutions within reasonable amount of computation time. The analysis of the model' results indicate that the model can reduce the percentages of empty haul distance by approximately 68 percent to 72 percent comparing the truckload operation without empty haul management. Moreover, using the algorithm can reduce transportation cost by approximately 42 percent.

Link to Full Text

Share

COinS