A branch and cut algorithm for the VRP with satellite facilities סיכום

אלגוריתם branch and cut עבור VRP באמצעות מתקני לווין

במאמר זה אנו עוסקים באספקה-מחדש של סחורות עבור לקוחות המתפלגים גיאוגרפית באזור השירות, בהקשר של בעיית ניתוב רכבים (VRP). ההנחה היא כי קיים צי רכבים במאגר מרכזי, וכאשר לנהג אוזלת הסחורה, הוא חייב לחזור למאגר למילוי-מחדש. ההיבט הייחודי אותו אנו חוקרים הוא בעיית מתקני-לווין, בהם הנהגים יכולים לחדש את הסחורה מבלי לחזור למאגר המרכזי (VRPSF). ה- VRPSF הינה חלק מבעיית ניתוב המלאי (IRP), שבה מספר גדול של צרכנים מסתמכים על ספק מרכזי, עם חלוקה של צרכנים לפי ימי השבוע וקביעת הניתוב למילוי הסחורה. המטרה היא לצמצם עלויות ובאותו זמן להבטיח כי אף לקוח לא נותר ללא סחורה. המאמר מציע תהליך לפתרון ה- VRPSF המשלב היוריסטיקות עם תיאוריה פוליהדרלית במסגרת של branch and cut (חתך הסתעפות). המטרה היא לזהות מקרי אי-שוויון תקף או חתכים בכל צומת של עץ החיפוש שאינם מבטלים נקודות integer באזור האילוץ הבסיסי, אך מספקים קירוב הדוק יותר של הקימור של הסט של כל הנקודות האפשריות. אספקט קריטי של האלגוריתם הוא הליך למציאת פתרונות מעשיים או גבול עליון הדוק. אנו מיישמים היוריסטיקת קלארק-רייט VRPSF מותאמת. כאשר מתקני-לווין משולבים במודל, בעיית-העל של הניתוב הופכת לרכיב המורכב ביותר של IRP, המערבת זמן, מסוגלות, והיכן ומתי למלא מחדש את הרכב. הבעיה הופכת לאסימטרית ומגבירה את הממדיות של הנוסחא.

המודל המתמטי

ה- VRPSF שלנו מוגדר על ידי I קבוע של n לקוחות עם ביקוש לא-שלילי ידוע עבור סחורה מסוימת. כל לקוח מקבל שירות על ידי אחד מתוך m רכבים הומוגניים הממוקמים בתחילה במאגר המרכזי. ל- I ולמאגר יש גרף מכוון G = (V, A) שבו סט הצמתים V תואם את סט הלקוחות I, המאגר 0, וסט של s ≥ 0 מתקני-לווין. הסט A ∈ V x V תואם את הקשתות בין הצמתים ב- V. המאגר ומתקני-הלוויין s מחזיקים כמות בלתי מוגבלת של הסחורה (לשם המודל, הצבנו גבול על מספר ביקורי המילוי-מחדש). ההבדל העיקרי בין המאגר לבין מתקני-הלוויין הוא כי המאגר הוא המקור והיעד הסופי של כל רכב. כל ביקור פוטנציאלי במתקן-לוויין מקבל צומת ייחודי (כולל טעינה-מחדש במאגר). לפיכך, מתקן α קשור בצמתים nα ב- V במקום בצומת 1 בלבד. בגרף הנוצר, המספר הכולל של צמתים ב- V (כולל המאגר) הינו + 1 . מסלול אפשרי של אחד הרכבים מתחיל במאגר, מוסר סחורה למספר מסוים של לקוחות, ממלא מחדש באחד ממתקני-הלוויין, ממשיך לקבוצה נוספת של לקוחות, ממלא מחדש שוב במתקן-לוויין, ובסופו של דבר חוזר למאגר. דרישת היתכנות נוספת היא כי רצף המשלוח יושלם ב- T שעות.

תוצאות

חוללנו 3 רמות של בעיות, לפי 15, 18 ו- 20 לקוחות, עם 0, 1, ו- 2 מתקני-לוויין בהתאמה. כל הלקוחות התפלגו באופן אחיד על רשת של 100 x 100. המאגר ממוקם אקראית בריבוע מרכזי של 40 x 40 ומתקני-הלוויין ממוקמים מחוץ לריבוע זה ב- 4 מיקומים אפשריים, בריבוע 10 x 10 בפינות של הרשת. הביקוש היומי של כל לקוח הוגדר בין  0 ו- 1/2 מהקיבולת של המשאית. הצי הינו הומוגני, ולכל רכב קיבולת של 200 יחידות (איור 1). כל מתקן-לוויין והמאגר יכולים לקבל 2 ביקורים במשמרת עבור טעינה מחדש. עבור כל ביקור, הוספו משתנים בינאריים n ו- O(n2) אילוצים למודל. טבלה 1 מציגה את התוצאות עבור 15 לקוחות. הוצב גבול של 3600 שניות CPU על כל אחד מ- 15 המקרים בטבלה 1. נמצא פתרון אופטימאלי ב- 9 מקרים, 6 מתוכם על ידי ההיוריסטיקה. ב- 9 המקרים האחרים, ההיוריסטיקה הייתה פחות מנקודת אחוז אחת מפתרון ה- integer המיטבי. הפער הממוצע בין הגבול העליון לתחתון היה 2.3%. בהיעדר מתקני-לוויין, הושגה אופטימאליות בכל 5 המקרים. כצפוי, רמת הקושי עלתה יחד עם s. בנוגע לעלויות, הירידה הממוצעת במרחק הנסיעה בכל הסטים הייתה 5.9%. מתכנן המערכת חייב להחליט האם התועלת הנובעת מהוספת מתקנים מספיקה בכדי לקזז את עלויות מחזור החיים שלהם. טבלה 2 מציגה מאפיינים נוספים הנוגעים לאלגוריתם, במקרה של 15 לקוחות. הנתונים מראים כי נוצרו כמה אלפי צמתים עבור מקרי הבעיות. מספר ה- LPs שנפתרו היה פרופורציונאלי למספר הצמתים שנבדקו. הטור האחרון, ΔLP, מספק אינדיקאציה טובה לגבי האפקטיביות של החיתוכים. גבול ה- LP התחתון עלה בממוצע ב- 25.2%. טבלאות 3-6 מציגות תוצאות של מקרי 18 ו- 20 לקוחות. לפי טבלה 3, 6 מתוך 15 מקרים נפתרו באופן אופטימאלי. בטבלה 5, 3 מתוך 15 מקרים נפתרו אופטימאלית. ניתן לראות כי ככל שמספר הלקוחות גדול יותר, כך הבעיה מסתבכת. טבלאות 4 ו- 6 מסכמות את המאפיינים עבור המקרים של 18 ו- 20 לקוחות. השיפור הממוצע מה- LP הראשון לאחרון היה 17.27 ו- 18.19%, בהתאמה.

דיון

אלגוריתם ה- branch and cut  שלנו כולל 4 רכיבים עיקריים: טרום-עיבוד, גבול עליון, זיהוי חתכים, ואנומורציה (שלבים 0-8). התוצאות מראות כי היוריסטיקת ה- CW המשופרת מספקת פתרונות אופטימאליים וכמעט-אופטימאליים כמעט בכל המקרים שנבחנו. מציאת מקרי אי-שוויון תקף היא המשימה העיקרית של האלגוריתם, ובמקרה שלנו ניסינו לזהות אילוצי אלימינציה והרמנו את מחזורים k  ו- k  בכדי לשפר את נוסחת ה- LP (איור 2 מציג דוגמא להרמה). מקרי אי-שוויון אלו חותכים פתרונות מקטע ומספקים ייצוג פוליהדרלי הדוק של האזור המעשי. כאשר לא נמצאים חיתוכים חדשים, האלגוריתם משמש לקביעת המשתנים. האלגוריתם פתר באופן אופטימאלי את רוב המקרים של 15 לקוחות, בתוך גבול 3600 השניות, אך רק כ- 40 ו- 20% מהמקרים של 18 ו- 20 לקוחות בתוך 7200 שניות. הפער בין הגבול העליון והתחתון היה תמיד פחות מ- 7%, ובממוצע פחות מ- 3%. בכדי להביא לשיפור נוסף, יש לזהות סוגים נוספים של אי-שוויון. מסרקים עובדים היטב עבור TSP, ואפשרות נוספת היא מציאת אי-שוויון הנובע ממסלולים עם צמתים שאינם יכולים להימצא על אותו נתיב בפתרון מעשי (כאשר ללקוחות יש חלון זמן קטן או ביקוש אינדיבידואלי גבוה).