งานเพิ่มประสิทธิภาพที่พบบ่อยที่สุดงานหนึ่งคือการกำหนดเส้นทางยานพาหนะ โดยเป้าหมายคือการค้นหาเส้นทางที่ดีที่สุดสำหรับยานพาหนะที่เดินทางไปยังสถานที่หนึ่งๆ โดยปกติ "ดีที่สุด" หมายถึงเส้นทางที่มีระยะทางรวมหรือค่าใช้จ่ายน้อยที่สุด ต่อไปนี้เป็นตัวอย่างของปัญหาการกำหนดเส้นทาง
- บริษัทจัดส่งพัสดุแห่งหนึ่งต้องการกำหนดเส้นทางสำหรับให้คนขับในการจัดส่งพัสดุ
- บริษัทเคเบิลทีวีต้องการกำหนดเส้นทางสำหรับช่างเทคนิคในการโทรรับบริการในที่พักอาศัย
- บริษัทให้บริการร่วมเดินทางต้องการกำหนดเส้นทางสำหรับรับและส่งผู้โดยสาร
ปัญหาการกำหนดเส้นทางที่มีชื่อเสียงที่สุดคือปัญหาเกี่ยวกับการเดินทางของพนักงานขาย (TSP): ค้นหาเส้นทางที่สั้นที่สุดสำหรับพนักงานขายที่ต้องการไปพบลูกค้า ณ ตำแหน่งต่างๆ และเดินทางกลับไปยังจุดเริ่มต้น โดย TSP อาจแสดงเป็นกราฟ ซึ่งโหนดจะสัมพันธ์กับสถานที่ และขอบ (หรือส่วนโค้ง) แสดงถึงการเดินทางโดยตรงระหว่างสถานที่ ตัวอย่างเช่น กราฟด้านล่างแสดง TSP ที่มีเพียง 4 ตำแหน่ง ซึ่งมีป้ายกำกับ A, B, C และ D ตัวเลขข้างขอบที่เชื่อมต่อกับตำแหน่ง 2 ตำแหน่งจะหมายถึงระยะทางระหว่างตำแหน่ง 2 แห่ง
การคำนวณระยะทางของเส้นทางทั้งหมดที่เป็นไปได้ คุณจะเห็นได้ว่าเส้นทางที่สั้นที่สุดคือ ACDBA ซึ่งมีระยะทางรวมคือ 35 + 30 + 15 + 10 = 90
ปัญหาจะหนักขึ้นเมื่อมีจำนวนสถานที่มากกว่านั้น ในตัวอย่างข้างต้น มีเพียง 6 เส้นทาง แต่ถ้ามีสถานที่ 10 แห่ง (ไม่นับจุดเริ่มต้น) จำนวนเส้นทางจะเป็น 362880 สำหรับสถานที่ 20 แห่ง จำนวนจะพุ่งไปที่ 2432902008176640000 การค้นหาเส้นทางทั้งหมดที่เป็นไปได้อย่างครอบคลุมเป็นการรับประกันว่าจะได้เส้นทางที่สั้นที่สุด แต่การค้นหานี้คำนวณได้ยากสำหรับทุกๆ ชุด ยกเว้นสถานที่ขนาดเล็ก สำหรับปัญหาที่ใหญ่ขึ้น อาจต้องมีเทคนิคการเพิ่มประสิทธิภาพเพื่อค้นหาพื้นที่โซลูชันอย่างมีชั้นเชิง และค้นหาโซลูชันที่ทำงานได้ดีที่สุด (หรือเกือบเหมาะสมที่สุด)
เวอร์ชันทั่วไปกว่าของ TSP คือปัญหาการกำหนดเส้นทางรถ (VRP) ซึ่งมียานพาหนะหลายคัน ในกรณีส่วนใหญ่ VRP จะมีข้อจำกัด เช่น ยานพาหนะอาจมีขีดจำกัดสำหรับน้ำหนักหรือปริมาณสูงสุดของสิ่งของที่บรรทุกได้ หรือคนขับอาจต้องไปยังสถานที่ต่างๆ ในกรอบเวลาที่ระบุตามที่ลูกค้าร้องขอ
เครื่องมือ "หรือ" ช่วยแก้ปัญหา VRP ได้หลายประเภท ซึ่งรวมถึง
- ปัญหาเกี่ยวกับการเดินทางของพนักงานขาย เป็นปัญหาการกำหนดเส้นทางคลาสสิกที่มียานพาหนะเพียง 1 คัน
- ปัญหาการกำหนดเส้นทางพาหนะ ภาพรวมของ TSP ที่มียานพาหนะหลายคัน
- VRP ที่มีข้อจำกัดด้านความจุ ซึ่งยานพาหนะมีความจุสูงสุดของสิ่งของที่บรรทุกได้
- VRP ที่มีกรอบเวลา ซึ่งยานพาหนะต้องไปยังสถานที่ในช่วงเวลาที่กำหนด
- VRP ที่มีข้อจำกัดทรัพยากร เช่น พื้นที่หรือบุคลากร ที่จะโหลดยานพาหนะที่ Depot (จุดเริ่มต้นของเส้นทาง)
- VRP ที่มีการหลุดออกไป ซึ่งไม่จำเป็นต้องนำยานพาหนะไปยังทุกสถานที่ แต่ต้องจ่ายค่าปรับเมื่อออกไปจากการเข้าชมแต่ละครั้ง
ข้อจำกัดในการแก้ปัญหาเกี่ยวกับการกำหนดเส้นทางรถ
ปัญหาการกำหนดเส้นทางยานพาหนะนั้นแก้ไขได้ยาก นั่นคือระยะเวลา ที่ใช้ในการแก้ปัญหาจะเพิ่มขึ้นทวีคูณตามขนาดของปัญหา สำหรับปัญหาขนาดใหญ่พอ อาจใช้เวลา OR-Tools (หรือซอฟต์แวร์การกำหนดเส้นทางอื่นๆ) ปีเพื่อหาวิธีแก้ปัญหาที่ดีที่สุด ด้วยเหตุนี้ บางครั้ง OR-Tools จะแสดงโซลูชันที่ดีแต่ยังไม่มีประสิทธิภาพ เปลี่ยนตัวเลือกการค้นหาสำหรับเครื่องมือแก้โจทย์คณิตเพื่อหาวิธีแก้ปัญหาที่ดีกว่า ดูการเปลี่ยนกลยุทธ์การค้นหา สำหรับตัวอย่าง