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

Abstract

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