Chulalongkorn University Theses and Dissertations (Chula ETD)

การกำหนดเส้นทางเดินรถแบบพลวัต

Other Title (Parallel Title in Other Language of ETD)

Dynamic scheduling for vehicle routing problems

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.1568

Abstract

งานวิจัยนี้พิจารณาปัญหาการกำหนดเส้นทางเดินรถแบบพลวัต ที่มีข้อจำกัดด้านระยะเวลารับประกัน และความจุของรถขนส่ง โดยปัญหาในงานวิจัยนี้จะแตกต่างจากปัญหาการจัดเส้นทางเดินรถแบบดั้งเดิม เนื่องจากเป็นปัญหาในการกำหนดทั้งเวลาออกรถและเส้นทางในการจัดส่งสินค้าที่เหมาะสม โดยที่ข้อมูลของจุดรับสินค้าจะทยอยทราบหลังจากเริ่มขั้นตอนในการหาคำตอบ ทำให้ต้องมีการวางแผนจัดเส้นทางมากกว่าหนึ่งครั้ง ดังนั้นจึงจำเป็นต้องนำเอาการกำหนดเส้นทางเดินรถแบบพลวัตมาใช้เพื่อตอบสนองกับข้อมูลที่ทยอยเข้ามาในระบบ ฮิวริสติกที่นำเสนอจะทำงานในรูปแบบของการวนซ้ำหาคำตอบในสามขั้นตอน คือ กระบวนการจัดเตรียมข้อมูลกระบวนการจัดเส้นทาง และกระบวนการกำหนดเวลาออกรถ โดยในกระบวนการจัดเตรียมข้อมูลจะทำหน้าที่จัดเตรียมข้อมูลสำหรับอีกสองกระบวนการในขั้นถัดไป ในขั้นตอนถัดมาคือกระบวนการจัดเส้นทางจะทำหน้าที่สร้างเส้นทางที่เหมาะสมโดยใช้ insertion heuristic และ GRASP โดยในการสร้างเส้นทางนั้นมีสองแนวทางคือ แนวทางแรกพิจารณาจัดเส้นทางครั้งละหนึ่งเส้นทาง และแนวทางที่สองพิจารณาจัดเส้นทางครั้งละมากกว่าหนึ่งเส้นทาง และขั้นตอนสุดท้ายคือกระบวนการกำหนดเวลาออกรถจะทำหน้าที่กำหนดเวลาออกรถที่เหมาะสม การทดสอบความสามารถของฮิวริสติกที่นำเสนอ จะทดสอบกับปัญหาที่ดัดแปลงจากปัญหาของ Solomon ซึ่งผลจากการทดสอบพบว่าคำตอบที่ได้จากฮิวริสติกมีความแตกต่างจากขอบเขตล่างโดยเฉลี่ย 7.23% 11.54% และ 17.89% สำหรับปัญหาขนาด 25 จุดรับ 50 จุดรับ และ 100 จุดรับ ตามลำดับ

Other Abstract (Other language abstract of ETD)

This research considers dynamic scheduling in a vehicle routing problem (VRP) with guaranteed service time and capacitated vehicle. Unlike the classic VRP, VRP with dynamic scheduling determines both dispatching time and an appropriate routing for each vehicle. When the information of all customer demand cannot be known at the same time, planning on vehicle routing must be done more than once. Therefore dynamic scheduling is needed in order to cope with continued information. The proposed heuristic works in three-step iterative manner: data preparation step, route establishing step, and vehicle dispatching step. The data preparation step arranges essential information to the next two steps. In route establishing step, an appropriate route is determined under insertion heuristic and GRASPS heuristic. Routes are established under two concepts: one route establishing at a time and more than one route establishing at a time. Finally, the dispatching time is determined in the third step. Solomon test problems are used in the computational experiment for heuristic testing. The results show that the heuristic yields 7.23%, 11.54% and 17.89% average gap from the lower bound for 25-cumtomer node, 50-customer node, and 100-customer node consecutively.

Link to Full Text

Share

COinS