แนวทางใหม่ในการแก้ปัญหาพนักงานขายการเดินทาง ซึ่งเป็นหนึ่งในคำถามที่ยากที่สุดในวิทยาการคอมพิวเตอร์ มีประสิทธิภาพเหนือกว่าแนวทางปัจจุบันอย่างมาก
คำถามเชิงทฤษฎีที่ฉาวโฉ่ซึ่งสร้างความสับสนให้กับนักวิจัยมาเป็นเวลา 90 ปี ปัญหาพนักงานขายการเดินทางยังมีความเกี่ยวข้องกับอุตสาหกรรมในปัจจุบันอีกด้วย โดยพื้นฐานแล้วคำถามเกี่ยวกับวิธีที่ดีที่สุดในการรวมชุดของงานเพื่อให้สามารถดำเนินการได้อย่างรวดเร็วและมีประสิทธิภาพมากที่สุด การค้นหาวิธีแก้ไขปัญหาที่ดีสามารถช่วยปรับปรุงภาคส่วนต่างๆ เช่น การขนส่งและโลจิสติกส์ได้อย่างมาก
นักวิจัยจากมหาวิทยาลัยเคมบริดจ์ได้พัฒนาวิธีการแก้ปัญหาแบบไฮบริดที่ขับเคลื่อนด้วยข้อมูล ซึ่งไม่เพียงแต่สร้างโซลูชันคุณภาพสูงเท่านั้น แต่ยังมีอัตราที่เร็วกว่าวิธีอื่นๆ ที่ล้ำสมัยอีกด้วย ผลลัพธ์ของพวกเขา จะถูกนำเสนอในสัปดาห์นี้ที่การ ประชุมนานาชาติ ว่า ด้วยการนำเสนอ การเรียนรู้
ดร.อแมนดา โปรรอก จากภาควิชาวิทยาการคอมพิวเตอร์และเทคโนโลยีแห่งเคมบริดจ์ ซึ่งเป็นผู้นำการวิจัยกล่าวว่า “ความสำคัญของระบบลอจิสติกส์ทั่วโลกถูกนำกลับมาหาเราในช่วงการระบาดใหญ่ “เราพึ่งพาโครงสร้างพื้นฐานประเภทนี้อย่างสูงเพื่อให้มีประสิทธิภาพมากขึ้น และโซลูชันของเราสามารถช่วยในเรื่องนั้นได้ เนื่องจากมีเป้าหมายทั้งด้านลอจิสติกส์ในคลังสินค้า เช่น การกำหนดเส้นทางของหุ่นยนต์รอบคลังสินค้าเพื่อรวบรวมสินค้าสำหรับการจัดส่งและนอก เช่น การกำหนดเส้นทางสินค้าสู่ผู้คน”
ปัญหาพนักงานขายการเดินทางเกี่ยวข้องกับคนขับรถส่งของที่ต้องโทรตามจำนวนเมืองที่กำหนดไว้ เช่น 20, 50 หรือ 100 ซึ่งเชื่อมต่อกันด้วยทางหลวงทั้งหมดในการเดินทางครั้งเดียว ความท้าทายคือการหาเส้นทางที่สั้นที่สุดที่โทรไปยังแต่ละปลายทางเพียงครั้งเดียวและค้นหาได้อย่างรวดเร็ว
“มีสององค์ประกอบหลักของปัญหา เราต้องการสั่งหยุด และเราต้องการทราบค่าใช้จ่ายในการเดินทางจากจุดหนึ่งไปอีกจุดหนึ่งตามลำดับเวลาหรือระยะทาง” Prorok กล่าว
ยี่สิบปีที่แล้ว เส้นทางจากโกดังไปยังจุดหมายปลายทางอาจได้รับการแก้ไขล่วงหน้า แต่ด้วยความพร้อมใช้งานของข้อมูลการจราจรแบบเรียลไทม์ในปัจจุบัน และความสามารถในการส่งข้อความไปยังคนขับเพื่อเพิ่มหรือลบสถานที่จัดส่งได้ทันที เส้นทางอาจมีการเปลี่ยนแปลงในระหว่างการเดินทาง แต่การลดความยาวหรือระยะเวลาให้เหลือน้อยที่สุดยังคงเป็นกุญแจสำคัญ
มักมีค่าใช้จ่ายที่เกิดจากการรอวิธีแก้ปัญหาที่เหมาะสมหรือกำหนดเวลาตายตัวที่ต้องตัดสินใจ ตัวอย่างเช่น คนขับไม่สามารถรอเพื่อคำนวณโซลูชันใหม่ได้ พวกเขาอาจพลาดการส่งมอบ หรือสภาพการจราจรอาจเปลี่ยนแปลงอีกครั้ง
และนั่นคือเหตุผลที่มีความจำเป็นทั่วไป ทุกเวลาอัลกอริธึมการปรับให้เหมาะสมที่สุดแบบผสมผสาน ที่สร้างโซลูชันคุณภาพสูงภายใต้เวลาการคำนวณที่จำกัด
วิธีการแบบผสมที่พัฒนาโดยเคมบริดจ์ทำสิ่งนี้โดยการรวมโมเดลการเรียนรู้ของเครื่องที่ให้ข้อมูลเกี่ยวกับเส้นทางที่ดีที่สุดก่อนหน้านี้และเครื่องมือ ‘อภิธานศัพท์’ ที่ใช้ข้อมูลนี้เพื่อประกอบเส้นทางใหม่
Ben Hudson ผู้เขียนคนแรกของหนังสือพิมพ์กล่าวว่า “เราต้องการหาแนวทางแก้ไขที่ดีได้เร็วกว่านี้ “ถ้าฉันเป็นคนขับรถให้กับบริษัทจัดส่ง ฉันต้องตัดสินใจว่าจุดหมายต่อไปของฉันจะเป็นอย่างไรในขณะที่ฉันกำลังขับรถอยู่ ฉันไม่สามารถรอวิธีแก้ปัญหาที่ดีกว่านี้ได้ นั่นเป็นเหตุผลว่าทำไมในการวิจัยของเรา เราจึงมุ่งเน้นไปที่การแลกเปลี่ยนระหว่างเวลาที่ใช้ในการคำนวณและคุณภาพของโซลูชันที่เราได้รับ”
ในการทำเช่นนี้ Hudson ได้คิดค้นอัลกอริธึม Guided Local Search ที่สามารถแยกเส้นทางจากเมืองหนึ่งไปยังอีกเมืองหนึ่งที่อาจมีค่าใช้จ่ายสูง ในเวลาหรือระยะทาง จากเส้นทางที่มีต้นทุนน้อยกว่าที่จะรวมไว้ในการเดินทาง สิ่งนี้ทำให้นักวิจัยสามารถระบุโซลูชันคุณภาพสูง แทนที่จะเป็นวิธีที่เหมาะสมที่สุดได้อย่างรวดเร็ว
พวกเขาทำเช่นนี้โดยใช้การวัดสิ่งที่พวกเขาเรียกว่า ‘ความเสียใจทั่วโลก’ – ค่าใช้จ่ายในการบังคับใช้การตัดสินใจหนึ่งครั้งที่สัมพันธ์กับต้นทุนของโซลูชันที่เหมาะสมที่สุด – ของแต่ละเส้นทางจากเมืองสู่เมืองในอัลกอริธึม Guided Local Search พวกเขาใช้แมชชีนเลิร์นนิงเพื่อประมาณ ‘ความเสียใจ’ นี้
“เราทราบวิธีแก้ปัญหาที่ถูกต้องสำหรับชุดของปัญหาเหล่านี้แล้ว” ฮัดสันกล่าว “ดังนั้นเราจึงใช้เทคนิคแมชชีนเลิร์นนิงเพื่อลองเรียนรู้จากโซลูชันเหล่านั้น จากข้อมูลดังกล่าว เราพยายามเรียนรู้ปัญหาใหม่ สำหรับเมืองชุดใหม่ในสถานที่ต่างๆ ซึ่งเส้นทางระหว่างเมืองมีแนวโน้มดี
“เมื่อเรามีข้อมูลนี้ มันก็จะดึงข้อมูลไปยังส่วนถัดไปของอัลกอริทึม – ส่วนที่ดึงเส้นทางจริงๆ มันใช้ข้อมูลเพิ่มเติมเกี่ยวกับเส้นทางที่ดีที่อาจจะสร้างทางออกที่ดีได้เร็วกว่าที่เคยทำอย่างอื่น”
ผลลัพธ์ที่ได้นั้นน่าประทับใจ การทดลองของพวกเขาแสดงให้เห็นว่าแนวทางไฮบริดที่ขับเคลื่อนด้วยข้อมูลมาบรรจบกันเป็นโซลูชันที่เหมาะสมที่สุดในอัตราที่เร็วกว่าวิธีการที่ใช้การเรียนรู้เป็นพื้นฐานสามวิธีล่าสุดสำหรับปัญหาพนักงานขายการเดินทาง
โดยเฉพาะอย่างยิ่ง เมื่อพยายามแก้ปัญหาเมื่อมีเส้นทาง 100 เมือง วิธีของ Cambridge ได้ลดช่องว่างความเหมาะสมเฉลี่ยจาก 1.534% เป็น 0.705% ซึ่งเป็นการปรับปรุงสองเท่า เมื่อทำการสรุปจากเส้นทางปัญหา 20 เมืองไปยังเส้นทางปัญหา 100 เมือง วิธีการลดช่องว่างที่เหมาะสมที่สุดจาก 18.845% เป็น 2.622% ซึ่งเป็นการปรับปรุงเจ็ดเท่า
“บริษัทขนส่งหลายแห่งใช้วิธีการกำหนดเส้นทางในชีวิตจริง” ฮัดสันกล่าว “เป้าหมายของเราในการวิจัยนี้คือการปรับปรุงวิธีการดังกล่าวเพื่อให้พวกเขาผลิตโซลูชั่นที่ดีขึ้น – โซลูชั่นที่ส่งผลให้มีระยะทางที่น้อยลงในการเดินทาง ดังนั้นจึงลดการปล่อยคาร์บอนและลดผลกระทบต่อสิ่งแวดล้อม”
Amanda Prorok เป็นเพื่อนของ Pembroke College, Cambridge
อ้างอิง:
Benjamin Hudson et al. ‘ กราฟ Neural Network Guided Local Search สำหรับปัญหาพนักงานขายที่เดินทาง ‘ บทความที่นำเสนอในการประชุมนานาชาติว่าด้วยการเรียนรู้การเป็นตัวแทน : https://iclr.cc/virtual/2022/calendar
