Improving column generation method for solving large scale logistics problems

Improving column generation method for solving large scale logistics problems
(การพัฒนาวิธีคอลัมน์เจนเนอร์เรชันเพื่อใช้ในการแก้ปัญหาในภาคอุตสาหกรรมโลจิสติกส์ที่มีขนาดใหญ่และซับซ้อน)
 

ปัญหาที่ทำการวิจัยและความสำคัญของปัญหา

          ปัจจุบัน โลจิสติกส์ได้เข้ามาบทบาทที่สำคัญภายในประเทศไทยเป็นอย่างมาก เพราะโลจิสติกส์นั้นนำมาสู่การจัดการที่มีประสิทธิภาพ ด้วยผลกำไรที่มากขึ้น หรือต้นทุนในการดำเนินการที่ลดลง โดยทั่วไป ปัญหาการจัดการโลจิสติกส์ เป็นปัญหาการตัดสินใจที่มีขนาดใหญ่ ซึ่งหมายถึง ตัวแปรในการตัดสินใจมีเป็นจำนวนมาก รวมทั้งตัวแปรการตัดสินใจเหล่านั้นยังมีความสัมพันธ์ที่ซับซ้อน ทั้งในรูปแบบความสัมพันธ์ระหว่างตัวแปรการตัดสินใจด้วยกันเอง (Decision variables) และระหว่างตัวแปรการตัดสินใจกับเงื่อนไขของ ปัญหา (Operational constraints) เมื่อปัญหาการตัดสินใจมีขนาดใหญ่และมีความสลับซับซ้อน การหาคำตอบที่ดีที่สุด (Optimal solution) นั้นมีความเป็นไปได้ยากมาก หรืออาจเป็นไปไม่ได้เลย และเป็นเรื่องที่ท้าทายต่อ วิศวกร, นักวางแผนการขนส่งและโลจิสติกส์ หรือนักวิทยาการคอมพิวเตอร์ ที่ได้พยามคิดค้นขั้นตอนวิธีทางคอมพิวเตอร์ หรืออัลกอริทึมมาใช้ในการหาคำตอบที่ดีที่สุดของปัญหาการตัดสินใจดังกล่าว (ณกร 2548)

          โดยทั่วไป ในทางปฏิบัติ ปัญหาการตัดสินใจในอุตสาหกรรมการขนส่งและโลจิสติกส์ที่มีขนาดใหญ่และมีความซับซ้อน (Large-scale logistics problems) จะอาศัยขั้นตอนวิธีทางคอมพิวเตอร์ที่เรียกว่า"ฮิวริสติกส์" มาใช้ในการหาคำตอบของการตัดสินใจ แม้ว่าวิธีฮิวริสติกส์จะสามารถหาคำตอบที่มีคุณภาพดีได้ภายในระยะเวลาอันรวดเร็ว หรือภายในระยะเวลาจำกัด (Good enough fast enough solution) อย่างไรก็ตาม คำตอบที่ได้ก็ไม่ได้ถูกประกันว่า เป็นคำตอบของตัดสินใจที่ดีที่สุด อีกแนวทางหนึ่งในการแก้ปัญหาการตัดสินใจ คือการใช้วิธี Exact (หรือ Optimization method) เพื่อที่จะหาคำตอบที่ดีที่สุดของการตัดสินใจ และประกันการพบคำตอบที่ดีที่สุดในทุกๆครั้งของการรันโปรแกรม อย่างไรก็ตาม ข้อจำกัดที่สำคัญที่สุดของวิธีนี้ คืออัลกอริทึมจะใช้เวลาในการค้นหาคำตอบที่ดีที่สุดเป็นเวลานานมาก (NP-hard problem) จึงทำให้ วิธีดังกล่าวไม่สามารถนำไปใช้ในทางปฏิบัติ ในการแก้ปัญหาการตัดสินใจที่มีขนาดใหญ่และซับซ้อนได้

          ในการศึกษานี้ ผู้วิจัยจะทำการวิเคราะห์และออกแบบขั้นตอนทางคอมพิวเตอร์ (หรืออัลกอริทึม) โดยทั้งนี้ผู้วิจัยได้เลือกวิธี Exact ที่มีชื่อว่า คอลัมน์เจ็นเนอร์เรชัน (Column generation method) มาทำการพัฒนา ปรับปรุง หรือแม้กระทั่งสร้างเป็นองค์ความรู้ใหม่ เพื่อให้สามารถหาคำตอบที่ดีที่สุด (Optimal solution) ของปัญหาโลจิสติกส์ที่มีขนาดใหญ่และซับซ้อนได้อย่างมีประสิทธิภาพ โดยในการศึกษานี้จะใช้ปัญหาการจัดตารางเวลาและเส้นทางสำหรับยานพานะ (Vehicle routing problem) ซึ่งเป็นปัญหาที่มีความสำคัญมากที่สุดในปัญหาด้านการจัดการโลจิสติกส์ของประเทศ มาใช้เป็นกรณีศึกษา

วัตถุประสงค์

  1. เพื่อศึกษา ออกแบบและพัฒนา หรือแม้กระทั่งสร้างองค์ความรู้ใหม่ ในการนำวิธีคอลัมน์เจ็นเนอร์เรชันมาใช้ในการแก้ปัญหาการตัดสินใจในอุตสาหกรรมโลจิสติกส์ที่มีขนาดใหญ่และซับซ้อน
  2. เพื่อสามารถนำวิธีคอลัมน์เจ็นเนอร์เรชันมาประยุกต์ใช้กับปัญหาการจัดเส้นทางยานพานะ เพื่อช่วยให้บริษัทในอุตสาหกรรมขนส่งลดต้นทุนในการขนส่ง เพิ่มระดับของการให้บริการกับลูกค้า
  3. เพื่อใช้เป็นต้นแบบในการพัฒนาวิธีคอลัมน์เจ็นเนอร์เรชันอย่างต่อเนื่อง และสามารถนำไปประยุกต์ใช้กับปัญหาอื่นๆในภาคอุตสาหกรรมการขนส่งและโลจิสติกส์

การเชื่อมโยงกับนักวิจัยที่เป็นผู้เชี่ยวชาญในสาขาวิชาที่ทำการวิจัย

          ในโครงการวิจัยนี้ มุ่งเน้นในการพัฒนาองค์ความรู้ใหม่ ซึ่งจะต้องอาศัยความรู้ขั้นพื้นฐานที่จำเป็นของผู้ทำการวิจัย ผนวกกับความรู้ และประสบการณ์ ของนักวิจัยท่านอื่นๆ ซึ่งเป็นผู้เชี่ยวชาญในสาขาวิชาที่เกี่ยวข้องทั้งในประเทศและต่างประเทศ โดยในขั้นพื้นฐาน ผู้วิจัยจะทำการปรึกษา และแลกเปลี่ยนข้อคิดเห็นกับอาจารย์ที่ปรึกษาวิทยานิพนธ์ของผู้วิจัย ทั้งในระดับปริญญาโทและเอก รวมทั้งผู้เชี่ยวชาญในหัวข้อเรื่องที่ทำการวิจัยภายในประเทศที่จะได้มีโอกาส แลกเปลี่ยนทัศนะและความเห็น ในการประชุมทางวิชาการ หรือในวงการภาคการศึกษา นอกจากนี้ ผู้วิจัยยังสามารถได้รับข้อคิดเห็นและข้อเสนอแนะของผู้เชี่ยวชาญชาวต่างประเทศที่เป็น Peer review จากการส่งบทความเพื่อตีพิมพ์ลงในวารสารต่างประเทศ

ขอบเขตของการวิจัย

          ในโครงการวิจัยนี้ ผู้วิจัยจะทำการศึกษาขั้นตอนวิธีทางคอมพิวเตอร์ โดยเฉพาะอย่างยิ่งวิธีคอลัมน์เจนเนอร์เรชัน มาใช้ในการหาคำตอบที่ดีที่สุดของปัญหาการตัดสินใจในอุตสาหกรรมโลจิสติกส์ที่มีขนาดใหญ่และซับซ้อน โดยทั้งนี้ จะเลือกปัญหาการจัดเส้นทางสำหรับยานพาหนะ (Vehicle routing problem) เป็นตัวอย่างศึกษา หลังจากนั้น ผู้วิจัยจะทำการวิเคราะห์ ออกแบบ และพัฒนาวิธีคอลัมน์เจนเนอร์เรชัน หรือแม้กระทั่งสร้างองค์ความรู้ใหม่โดยมีพื้นฐานจากวิธีคอลัมน์เจนเนอร์เรชัน มาใช้ในการแก้ปัญหาการจัดเส้นทางสำหรับยานพาหนะ วิธีคอลัมน์เจนเนอร์เรชันที่ได้พัฒนาขึ้น จะถูกเปรียบประสิทธิภาพกับวิธีหรืออัลกอริทึมอื่นๆที่มีอยู่ในปัจจุบัน โดยจะใช้ปัญหาการจัดเส้นทางสำหรับยานพาหนะที่มีอยู่ในฐานข้อมูลการวิจัยที่เป็นที่ยอมรับของต่างประเทศเป็นแหล่งข้อมูลอ้างอิง (Benchmark) นอกจากนี้ ผลจากการวิจัยจะถูกนำไปประยุกต์ใช้สำหรับปัญหาการจัดเส้นทางสำหรับยานพาหนะในภาคอุตสาหกรรมการขนส่งจริง เพื่อช่วยให้บริษัทสามารถลดค่าใช้จ่ายในการดำเนินการขนส่งสินค้า หรือต้นทุนโลจิสติกส์ลงได้

ประโยชน์ที่คาดว่าจะได้รับ
 

          ภายหลังจากโครงการวิจัยแล้วเสร็จ วิธีคอลัมน์เจ็นเนอร์เรชันที่พัฒนาขึ้นจะช่วยเพิ่มประสิทธิภาพในการหาคำตอบที่ดีที่สุด (Optimal solution) ของปัญหาการตัดสินในใจในภาคอุตสาหกรรมโลจิสติกส์ที่มีขนาดใหญ่และซับซ้อน

<< Back