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

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

מגבלות חיפוש

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

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

שם	Type	ברירת המחדל	תיאור
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, אבל קשתות מועלות תחילה באמצעות בורר מבוסס-השוואה, בעל עדיפות גבוהה יותר ל-ARC המוגבל ביותר. כדי להקצות בורר למודל הניתוב, צריך להשתמש בשיטה ArcIsMoreConstrainedThanArc().
EVALUATOR_STRATEGY	בדומה ל-PATH_CHEAPEST_ARC, רק עלויות של קשת מחושבות באמצעות הפונקציה שהועברה אל SetFirstSolutionEvaluator().
SAVINGS	אלגוריתם חיסכון (Clarke & Wright). קלארק, ג'י. ורייט, ג'יי וו. "תזמון כלי רכב מתחנת דיפו מרכזית למספר נקודות מסירה" , מחקר תפעולי, כרך 12, 1964, עמ' 568-581.
SWEEP	אלגוריתם מטאטא (וורן והולידיי). אזכור אנתוני רן ולוח הזמנים של כלי הרכב אלן הולידיי ממחסן אחד או יותר למספר נקודות תפעוליות של נקודות מסירה מחקר רבעוני (1970-1977), כרך 23, 3 (1 בספטמבר) 1972), עמ' 333-344.
CHRISTOFIDES	האלגוריתם של כריסטופדים (הוא למעשה וריאציה של האלגוריתם של ChristoTrustes באמצעות התאמה מקסימלית במקום התאמה מקסימלית. זה לא מבטיח שהגורם המשוער הוא 3/2 של קירבה לאיש מכירות שנוסע). פועל במודלים כלליים של ניתוב רכב על ידי הרחבת נתיב עד שלא ניתן להוסיף לו צמתים. אזכור של ניקו כריסטופידס, ניתוח המקרה הגרוע ביותר של היוריסטיקה חדשה לבעיית אנשי המכירות המטיילים, דוח 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	מחברים באופן קבוע שני צמתים שמייצרים את קטע המסלול הזול ביותר.
LOCAL_CHEAPEST_ARC	בחרו את הצומת הראשון עם חליפין ללא חיבור, וחברו אותו לצומת שייצור את קטע המסלול הזול ביותר.
FIRST_UNBOUND_MIN_VALUE	בחרו את הצומת הראשון עם חליפין ללא גבולות וחברו אותו לצומת הזמין הראשון. היא מקבילה לשיטה CHOOSE_FIRST_UNBOUND בשילוב עם ASSIGN_MIN_VALUE (cf.trains_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. Simuling Annealing).
TABU_SEARCH	משתמשת בחיפוש Tabu כדי לצאת מ-Minima מקומי (cf. חיפוש טאבו).
GENERIC_TABU_SEARCH	משתמשת בחיפוש בכרטיסיות כדי למצוא ערך שוויוני של פתרון, כדי לסמן בתו בריחה מסביבה מקומית.

בקרת ריבוי

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