Chulalongkorn University Theses and Dissertations (Chula ETD)

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

Other Title (Parallel Title in Other Language of ETD)

Algorithm for multi-depot pickup and delivery problem with full truckload

Year (A.D.)

2006

Document Type

Thesis

First Advisor

สีรง ปรีชานนท์

Second Advisor

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

Faculty/College

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

Degree Name

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

Degree Level

ปริญญาโท

Degree Discipline

วิศวกรรมอุตสาหการ

DOI

10.58837/CHULA.THE.2006.1545

Abstract

งานวิจัยนี้พิจารณาปัญหาการจัดส่งสินค้าที่รู้จักกันในชื่อ ปัญหาการรับและส่งสินค้าแบบเต็มความจุ (Full-Truck-Load Pickup and Delivery Problem) กล่าวคือ เมื่อรถบรรทุกทำการรับสินค้าจากจุดรับหนึ่งแล้ว รถบรรทุกคันดังกล่าวจะต้องไปส่งสินค้ายังจุดส่งอันเป็นที่หมายของสินค้าที่กำลังบรรทุกอยู่ก่อนที่จะไปรับสินค้าที่จุดรับอื่นได้ โดยที่คำสั่งส่งสินค้าหนึ่งนอกจากจะระบุถึงจุดรับและจุดส่งสินค้าจำนวนเที่ยวในการรับและส่งสินค้าแล้ว อาจจะรุบุเวลาในการรับและส่งสินค้าอีกด้วย ซึ่งปัญหารูปแบบนี้ผู้วางแผนการจัดส่งต้องตัดสินใจว่าจะทำการจัดส่งแต่ละคำสั่งส่งสินค้าอย่างอย่าง ใช้รถบรรทุกที่ประจำอยู่ที่จุดจอดรถบรรทุกใด และมีลำดับในการไปรับและส่งสินค้าต่างๆ อย่างไร ให้สามารถจัดส่งสินค้าทั้งหมดได้ภายในกรอบเวลาของคำสั่งส่งสินค้านั้น และไม่ละเมิดข้อจำกัดในเรื่องความสามารถในการบรรทุกและระยะทางสูงสูดในการจัดส่งของรถบรรทุกแต่ละเส้นทาง เพื่อให้ได้ค่าใช้จ่ายรวมในการจัดส่งสินค้าต่ำที่สุดโดยในรายละเอียดของปัญหาที่เราพิจารณานั้นจะกำหนดให้จุดรับสินค้าแต่ละจุดเป็นจุดจอดรถบรรทุกที่มีจำนวนรถบรรทุกจำกัดด้วย และในหนึ่งเส้นทางของการจัดส่งสินค้ารถบรรทุกที่ถูกใช้ในการจัดส่งจะต้องกลับมาจอดยังจุดจอดรถเดิมของรถบรรทุกคันนั้นๆ ซึ่งรถบรรทุกแต่ละคันจะมีความสามารถในการบรรทุกได้เท่ากัน และคำสั่งส่งสินค้าแต่ละคำสั่งจะถูกส่งโดยรถบรรทุกคันใดก็ได้ โดยในงานวิจัยนี้ได้นำเสนอขั้นตอนวิธีการแก้ปัญหาโดยจำลองปัญหาให้อยู่ในรูปของแบบจำลองทางคณิตศาสตร์ที่มีพื้นฐานมาจากลักษณะปัญหาการแบ่งห้อง (Set Partitioning Problem) และใช้เทคนิคการก่อกำเนินสดมภ์ (Column Generation) ในการเพิ่มตัวแปรตัดสินใจให้แบบจำลองคณิตศาสตร์ ซึ่งขั้นตอนวิธีที่นำเสนอนี้มีรายละเอียดที่แตกต่างจากเทคนิคการแก้ปัญหาที่นิยมใช้กันอย่างแพร่หลาย และสามารถยืนยันว่าคำตอบที่ได้เป็นคำตอบที่ดีที่สุดในขอบเขตปัญหาที่เราพิจารณา ซึ่งจากการทดสอบแก้ปัญหากับชุดข้อมูลที่ได้สังเคราะห์ขึ้นพบว่า ให้ผลลัพธ์เป็นที่น่าพอใจทั้งในแง่ของเวลาที่ใช้ในการหาคำตอบ และคำตอบที่ได้ไม่ผิดไปจากเงื่อนไขที่กำหนดขึ้น

Other Abstract (Other language abstract of ETD)

In this research, we consider problem called Full-Truck-Load Pickup and Delivery Problem which the problem characteristic can be describe that, each load has to be transported by one vehicle from its sets of origins (Factory) to its sets of destinations (Customer) without any transshipment at other locations. Each transportation request (Order) specifies the size of the load to be transported, the locations where it is to be pick up and the destinations where it is to be delivered. In some case its will specify the time window that vehicle should pickup after and deliver before. The planner must construct a set of route in order to satisfy transportation requests to obtain the minimum cost. Each route must specify sequence of pickup-delivery transportation request and the depot of vehicle use in that route. All transportation requests must send within time window constraint and not to violate capacity of each vehicle and maximum distance in each route. Each factory is the depot that has a limited number of vehicle. At the end of each route the vehicle must come back to its depot. All trucks have same capacity and same type. We introduce new algorithm for solve this problem. It’s base on set partitioning problem with column generation technique. The algorithm is nearly related to the well known approach but has the different in description and guarantees optimality. The result shows impressive compute time and no infeasible solution.

Link to Full Text

Share

COinS