ตัวเลือกการกําหนดเส้นทาง

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

ขีดจำกัดการค้นหา

ขีดจํากัดการค้นหาจะสิ้นสุดเครื่องมือแก้โจทย์หลังจากถึงขีดจำกัดที่ระบุ เช่น ระยะเวลาสูงสุด หรือจำนวนโซลูชันที่พบ คุณตั้งค่าการค้นหาได้ โดยใช้พารามิเตอร์การค้นหาของโปรแกรมแก้โจทย์ โปรดดู การจำกัดเวลาเป็นตัวอย่าง

ตารางต่อไปนี้อธิบายขีดจำกัดการค้นหาที่พบบ่อยที่สุด

ชื่อ	ประเภท	ค่าเริ่มต้น	คำอธิบาย
solution_limit	int64	kint64max	จำกัดจำนวนโซลูชัน ในระหว่างการค้นหา
time_limit.seconds	int64	kint64max	จำกัดเวลาที่ใช้ หน่วยเป็นวินาที : ในการค้นหา
lns_time_limit.seconds	int64	100	จำกัดเวลาเป็นวินาทีสำหรับ : การค้นหาที่สมบูรณ์สำหรับเพื่อนบ้านการค้นหาในท้องถิ่นแต่ละราย

กลยุทธ์โซลูชันแรก

กลยุทธ์โซลูชันแรกคือวิธีที่เครื่องมือแก้โจทย์ใช้เพื่อหาเงื่อนไขเริ่มต้น โซลูชัน ตารางต่อไปนี้แสดงตัวเลือกสำหรับ first_solution_strategy

ตัวเลือก	คำอธิบาย
AUTOMATIC	ให้เครื่องมือแก้โจทย์ทราบว่าจะใช้กลยุทธ์ใดตาม โมเดลที่กำลังแก้อยู่
PATH_CHEAPEST_ARC	เริ่มต้นจากเส้นทาง "เริ่มต้น" ให้เชื่อมต่อโหนดกับ โหนดที่สร้างส่วนของเส้นทางที่ถูกที่สุด แล้วต่อขยายเส้นทางโดย การทำซ้ำในโหนดสุดท้ายที่เพิ่มลงในเส้นทาง
PATH_MOST_CONSTRAINED_ARC	คล้ายกับ PATH_CHEAPEST_ARC แต่เส้นโค้งจะ ประเมินด้วยตัวเลือกที่อิงตามการเปรียบเทียบ ซึ่งจะสนับสนุน ที่โค้งมนก่อน ในการกำหนดตัวเลือกให้กับโมเดลการกำหนดเส้นทาง ให้ใช้ ArcIsMoreConstrainedThanArc()
EVALUATOR_STRATEGY	คล้ายกับ PATH_CHEAPEST_ARC ยกเว้นต้นทุนของเส้นโค้ง ได้รับการประเมินโดยใช้ฟังก์ชันที่ส่งไปยัง SetFirstSolutionEvaluator()
SAVINGS	อัลกอริทึมการออมเงิน (Clarke &Wright) การอ้างอิง Clarke, G. & ไรต์, J.W. "การกำหนดยานพาหนะจาก Central Depot ไปยังจุดนำส่งจำนวนหนึ่ง" , การวิจัยเชิงปฏิบัติการ, ฉบับ 12, 1964, หน้า 568-581
SWEEP	อัลกอริทึมการกวาด (Wren และ Holliday) อ้างอิง Anthony Wren และ การจัดตารางยานพาหนะโดย Alan Holliday คอมพิวเตอร์ จาก Depot อย่างน้อย 1 แห่งไปยังจุดนำส่งที่ใช้งานได้ Research รายไตรมาส (1970-1977), ฉบับ 23, ฉบับที่ 3 (ก. ย., 1972) หน้า 333-344
CHRISTOFIDES	อัลกอริทึม Christofides (ซึ่งเป็นตัวแปรของ อัลกอริทึม Christofides ใช้การจับคู่สูงสุดแทนการใช้การจับคู่สูงสุด ซึ่งไม่ได้รับประกันถึงปัจจัย 3/2 ของการประมาณค่า เมตริกการท่องเที่ยวของพนักงานขาย) ใช้ได้กับการกำหนดเส้นทางยานพาหนะทั่วไปโดย ขยายเส้นทางจนกว่าจะไม่สามารถแทรกโหนดได้ อ้างอิงจาก Nicos Christofides, การวิเคราะห์แบบ Worst-case of a new heuristic for ปัญหาพนักงานขายขณะเดินทาง, รายงาน 388, บัณฑิตวิทยาลัยอุตสาหกรรม บริหาร, CMU, 1976
ALL_UNPERFORMED	ทำให้โหนดทั้งหมดไม่ทำงาน ค้นหาวิธีแก้ปัญหาในกรณีที่โหนดเท่านั้น ไม่บังคับ (เป็นองค์ประกอบของข้อจำกัดการแยกที่มีค่าโทษแน่นอน)
BEST_INSERTION	สร้างโซลูชันซ้ำโดยการแทรกโซลูชันต้นทุนต่ำที่สุด โหนดที่ตำแหน่งที่ถูกที่สุด ต้นทุนของการแทรก ขึ้นอยู่กับ ฟังก์ชันต้นทุนของโมเดลการกำหนดเส้นทาง เริ่มตั้งแต่วันที่ 2/2012 ใช้ได้กับโมเดลที่มี โหนดที่ไม่บังคับ (พร้อมค่าปรับตามขีดจำกัด)
PARALLEL_CHEAPEST_INSERTION	สร้างโซลูชันซ้ำๆ โดยการแทรกฟิลด์ โหนดที่ถูกที่สุดในตำแหน่งที่ถูกที่สุด ต้นทุนของการแทรก ขึ้นอยู่กับ ฟังก์ชันต้นทุนโค้ง เร็วกว่า BEST_INSERTION
LOCAL_CHEAPEST_INSERTION	สร้างโซลูชันซ้ำโดยแทรกแต่ละโซลูชัน โหนดที่ตำแหน่งที่ถูกที่สุด ค่าใช้จ่ายในการแทรกจะขึ้นอยู่กับกราฟ ฟังก์ชันต้นทุน แตกต่างจาก PARALLEL_CHEAPEST_INSERTION ตามโหนด สำหรับการแทรก ที่นี่จะได้รับการพิจารณาตามลำดับ งานสร้างสรรค์ เร็วกว่า PARALLEL_CHEAPEST_INSERTION
GLOBAL_CHEAPEST_ARC	เชื่อมต่อ 2 โหนดที่เหมือนกันซึ่งสร้างฟิลด์ ส่วนของเส้นทางที่ถูกที่สุด
LOCAL_CHEAPEST_ARC	เลือกโหนดแรกที่มีตัวสืบทอดที่ไม่มีการเชื่อมโยง เชื่อมต่อกับโหนดซึ่งสร้างส่วนของเส้นทางที่ถูกที่สุด
FIRST_UNBOUND_MIN_VALUE	เลือกโหนดแรกที่มีตัวสืบทอดที่ไม่มีการเชื่อมโยง และเชื่อมต่อกับโหนดแรกที่ใช้ได้ ซึ่งเทียบเท่ากับ รวมกลยุทธ์ CHOOSE_FIRST_UNBOUND กับ ASSIGN_MIN_VALUE (เช่น Controls_solver.h)

สถานะการค้นหา

คุณแสดงสถานะการค้นหาได้โดยใช้เมธอด status ของโมเดลการกำหนดเส้นทาง นี่คือโค้ด Python สำหรับพิมพ์สถานะการค้นหา

print("Solver status: ", solver.status())

วิธีนี้จะพิมพ์จำนวนเต็มที่มีความหมายต่อไปนี้

ค่า	คำอธิบาย
0	ROUTING_NOT_SOLVED: ปัญหายังไม่ได้รับการแก้ไข
1	ROUTING_SUCCESS: แก้ไขปัญหาเรียบร้อยแล้ว
2	ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED: แก้ปัญหาแล้ว สำเร็จแล้วหลังจากเรียก RoutingModel.Solve() ยกเว้นในกรณีที่ ยังไม่ถึง Optimum การสละเวลาให้มากขึ้นจะช่วยให้ โซลูชัน
3	ROUTING_FAIL: ไม่พบวิธีแก้ปัญหา
4	ROUTING_FAIL_TIMEOUT: หมดเวลาก่อนที่จะค้นหาวิธีแก้ปัญหา
5	ROUTING_INVALID: โมเดล พารามิเตอร์โมเดล หรือแฟล็กไม่ถูกต้อง
6	ROUTING_INFEASIBLE: พิสูจน์แล้วว่าโจทย์นี้เป็นไปได้

ตัวเลือกการค้นหาในท้องถิ่น

ตารางต่อไปนี้แสดงตัวเลือกสำหรับกลยุทธ์การค้นหาในท้องถิ่น (หรือที่เรียกว่า metaheuristics) ดูการเปลี่ยนกลยุทธ์การค้นหา เพื่อดูตัวอย่างการตั้งค่าตัวเลือกเหล่านี้

ตัวเลือก	คำอธิบาย
AUTOMATIC	ให้เครื่องมือแก้โจทย์เลือกเมตาฮิวริสติก
GREEDY_DESCENT	ยอมรับการค้นหาเพื่อนบ้านในท้องถิ่นที่ปรับปรุง (ลดต้นทุน) จนถึงท้องถิ่น ถึงจำนวนขั้นต่ำแล้ว
GUIDED_LOCAL_SEARCH	ใช้การค้นหาในเครื่องแบบมีคำแนะนำเพื่อหลีกหนีค่าต่ำสุดของในเครื่อง (เช่น การค้นหาในท้องถิ่นที่แนะนำ) ระบบนี้มักจะเป็นกลไกควบคุมการทรงตัวที่มีประสิทธิภาพมากที่สุดสำหรับการกำหนดเส้นทางของยานพาหนะ
SIMULATED_ANNEALING	ใช้การหลอมเหลวจำลองเพื่อหลีกหนีจากความละเอียดต่ำสุดในเครื่อง (cf. การจำลองการอบเหนียว)
TABU_SEARCH	ใช้การค้นหา Tabu เพื่อหลีกหนีค่าขั้นต่ำในเครื่อง (cf. Tabu Search)
GENERIC_TABU_SEARCH	ใช้การค้นหาแบบ Tabu กับค่าวัตถุประสงค์ของโซลูชันเพื่อให้สอดคล้องกับท้องถิ่น ขนาดเล็กสุด

การควบคุมการเผยแพร่

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