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

ส่วนนี้จะอธิบายตัวเลือกบางรายการสําหรับเครื่องมือแก้โจทย์การกําหนดเส้นทาง

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

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

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

ชื่อ	ประเภท	ค่าเริ่มต้น	คำอธิบาย
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. และ Wright, J.W. "การตั้งเวลายานพาหนะจากสถานีรถไฟกลางไปยังจุดนําส่งจํานวนหนึ่ง", ฝ่ายวิจัย, ฉบับที่ 12, 1964, หน้า 568-581
SWEEP	อัลกอริทึมการกวาด (Wren และ Holliday) อ้างอิงการกําหนดเวลาคอมพิวเตอร์ของ Anthony Wren และ Alan Holliday จาก Depot อย่างน้อย 1 แห่งไปยังจุดปฏิบัติการจํานวนหนึ่ง การวิจัย (1970-1977), ฉบับที่ 23, เลขที่ 3 (ก.ย., 1972), หน้า 333-344
CHRISTOFIDES	อัลกอริทึม Christofides (อันที่จริงอัลกอริทึมแบบต่างๆ ของ Christofides ใช้การจับคู่สูงสุดแทนการจับคู่สูงสุด ซึ่งไม่ได้รับประกันสัดส่วนประมาณ 3/2 ของพนักงานขายที่เดินทางแบบเมตริก) ทํางานได้บนโมเดลการกําหนดเส้นทางทั่วไปของรถ โดยขยายเส้นทางจนไม่สามารถแทรกโหนดได้ อ้างอิง Nicos Christofides การวิเคราะห์กรณีแย่ที่สุดของวิทยาการศึกษาปัญหาใหม่ของพนักงานขายที่ 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 (cf.constraint_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() เว้นแต่ว่าจะมีการเพิ่มประสิทธิภาพเครื่องในท้องที่ไม่สําเร็จ การเว้นเวลาเพิ่มเติมจะช่วยให้ปรับปรุงโซลูชันได้
3	ROUTING_FAIL: ไม่พบวิธีแก้ปัญหา
4	ROUTING_FAIL_TIMEOUT: ครบเวลาที่จํากัดแล้วก่อนที่จะหาทางแก้ไข
5	ROUTING_INVALID: โมเดล พารามิเตอร์โมเดล หรือแฟล็กไม่ถูกต้อง
6	ROUTING_INFEASIBLE: ปัญหาที่พิสูจน์แล้วว่าไม่สามารถดําเนินการได้

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

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

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

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

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