אפשרויות ניתוב

בקטע הזה מתוארות חלק מהאפשרויות של פותר הבעיות בניתוב.

מגבלות חיפוש

מגבלות החיפוש מסיימים את הפותר לאחר שהוא מגיע למגבלה שצוינה, למשל משך הזמן המקסימלי או מספר הפתרונות שנמצאו. אפשר להגדיר חיפוש דרך פרמטרי החיפוש של הפותר. צפייה דוגמה למגבלות זמן.

בטבלה הבאה מתוארות מגבלות החיפוש הנפוצות ביותר.

שם	סוג	ברירת מחדל	תיאור
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. & רייט, ג'. וו. "תזמון רכבים מתחנה מרכזית למספר נקודות משלוח" , מחקר תפעול, כרך 12, 1964, pp. 568-581.
SWEEP	אלגוריתם סריקה (Wren ו-Holliday). הפניה לאנתוני רן & אלן הולידיי – תזמון מחשבים של כלי רכב מתחנה אחת או יותר למספר נקודות מסירה תפעוליות מחקר רבעוני (1970-1977), כרך 23, מס' 3 (ספטמבר, 1972), עמודים 333-344.
CHRISTOFIDES	אלגוריתם כריסטופידס (הוא למעשה וריאנט של אלגוריתם כריסטופידס משתמש בהתאמה מקסימלית במקום במקסימום התאמה, והיא לא מבטיחה את הגורם השלישי או שניים של הקירוב אנשי מכירות בתחום הנסיעות). פועלת על מודלים גנריים של ניתוב רכבים הרחבת נתיב עד שלא ניתן להוסיף אליו צמתים. הזכר את ניקוס כריסטופידס, ניתוח המקרה הגרוע ביותר של היוריסטיקה חדשה בעיית אנשי המכירות לנסיעות, דוח 388, בית הספר ללימודי לתואר שני לתעשייה ניהול, CMU, 1976.
ALL_UNPERFORMED	הגדרת כל הצמתים כלא פעילים. מוצא פתרון רק אם הצמתים הן אופציונליות (זהו רכיב של מגבלת מעבר עם עלות עונשית סופית).
BEST_INSERTION	לפתח פתרון באופן חזרתי על ידי הוספת הצומת במיקום הזול ביותר שלו; עלות ההכנסה מבוססת על פונקציית העלות של מודל הניתוב. החל מ-2/2012, התכונה פועלת רק במודלים עם צמתים אופציונליים (עם עלויות קנס סופיות).
PARALLEL_CHEAPEST_INSERTION	לפתח פתרון באופן חזרתי באמצעות הכנסת הצומת הזול ביותר במיקום הזול ביותר; עלות ההכנסה מבוססת על את פונקציית Arc cost. הוא מהיר יותר מ-BEST_INSERTION.
LOCAL_CHEAPEST_INSERTION	כדי לפתח פתרון באופן חזרתי על ידי הוספת כל אחד מהפתרונות הצומת במיקום הזול ביותר שלו; עלות ההכנסה מבוססת על קשת של פונקציית העלות. שונה מ-PARALLEL_CHEAPEST_INSERTION בצומת נבחרו להכנסה; כאן המערכת מתייחסת לצמתים לפי הסדר שלהם במהלך היצירה. הוא מהיר יותר מ-PARALLEL_CHEAPEST_INSERTION.
GLOBAL_CHEAPEST_ARC	לחבר באופן איטרטיבי שני צמתים שמייצרים את קטע המסלול הזול ביותר.
LOCAL_CHEAPEST_ARC	בוחרים את הצומת הראשון עם עוקב עוקב ו לחבר אותו לצומת שיוצר את קטע המסלול הזול ביותר.
FIRST_UNBOUND_MIN_VALUE	בחירת הצומת הראשון עם עוקב עוקב ומחברים אותו לצומת הזמין הראשון. היא מקבילה האסטרטגיה CHOOSE_FIRST_UNBOUND משולבת עם ASSIGN_MIN_VALUE (cf. אילוץ_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. חיפוש מקומי מודרך) בדרך כלל זה המטאוריסטי היעיל ביותר לניתוב רכבים.
SIMULATED_ANNEALING	משתמשת בסימולציה של חיפוי כדי להתחמק ממינימום מקומי (cf. Simulated Annaling).
TABU_SEARCH	משתמש בחיפוש טאבו כדי לבלוט ערך מינימום מקומי (cf. חיפוש בכרטיסיות).
GENERIC_TABU_SEARCH	משתמש בחיפוש טאבו על הערך האובייקטיסטי של הפתרון, כדי לסמן בתו בריחה (escape) מיקום מקומי מינימום.

בקרת הפצה

שם	סוג	ברירת מחדל	תיאור
use_full_propagation	בוליאני	true	שימוש באילוצים בהפצה מלאה במודל הניתוב (במקום בהפצה אור בלבד). מסך מלא ההפצה נחוצה רק כשמשתמשים בחיפוש עומק הראשון או במודלים שדורשות הפצה חזקה כדי להשלים את הערך של משתנים. שינוי ההגדרה ל-True יאט את החיפוש ברוב המקרים, ולהגדיל את צריכת הזיכרון בכל המקרים.