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

Abstract

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