วิธีการฮิวริสติกสำหรับปัญหาการรับและส่งพัสดุภายในวันทำการเดียวกัน

Abstract

งานวิจัยนี้มุ่งเน้นการพัฒนาแบบจำลองทางคณิตศาสตร์ และวิธีการฮิวริสติกสำหรับปัญหาการรับและส่งพัสดุภายในวันทำการเดียวกัน (Deterministic SDPD) โดยปัญหาดังกล่าวจัดเป็นปัญหาการจัดเส้นทางเดินรถรูปแบบหนึ่ง ซึ่งรถสามารถเดินทางออกจากท่ารถได้ตามรอบรถ (wave) ที่กำหนดเท่านั้น นอกจากนี้เวลาการปรากฏ (arrival time) ของคำสั่งของลูกค้าทั้งหมดเป็นข้อมูลที่ทราบล่วงหน้าตั้งแต่ต้นวันทำการ ทั้งนี้คำสั่งของลูกค้าหนึ่งๆ จะประกอบไปด้วยจุดรับ และจุดส่งพัสดุที่แตกต่างกัน และไม่จำเป็นต้องถูกมอบหมายให้อยู่ในรอบรถเดียวกัน แต่จำเป็นต้องจัดส่งพัสดุให้ทันภายในวันทำการ หากเลือกที่จะรับพัสดุของคำสั่งนั้นๆ ผู้วิจัยได้ทำการศึกษาผลกระทบของการเพิ่มจำนวนรอบรถในวันทำการที่มีต่อประสิทธิภาพของการหาคำตอบด้วยวิธีแม่นตรง (exact method) บนกลุ่มตัวอย่างที่สุ่มสร้างขึ้นจำนวน 40 ตัวอย่าง โดยผู้วิจัยพบว่า การเพิ่มขึ้นของจำนวนรอบรถในวันทำการส่งผลให้ประสิทธิภาพการหาคำตอบด้วยวิธีแม่นตรงลดลงอย่างมาก ผู้วิจัยจึงได้ทำการพัฒนาฮิวริสติก Adaptive Large Neighborhood Search (ALNS) สำหรับปัญหาดังกล่าว ซึ่งเมื่อเปรียบเทียบกับวิธีการหาคำตอบแบบแม่นตรงแล้ว ผู้วิจัยพบว่า คำตอบที่ได้จาก ALNS ส่วนใหญ่มีคุณภาพเทียบเท่า หรือดีกว่าคำตอบที่ได้จากวิธีแม่นตรงภายใต้กรอบเวลาในการหาคำนวณที่จำกัด แต่กลับใช้เวลาในการหาคำตอบต่ำกว่ามาก