מידול מתמטי, פתרון והדמיה באמצעות PuLP ו- VeRoViz
עם הצמיחה המהירה של קניות מקוונות, חברות מתמודדות עם דרישות הולכות וגדלות למשלוח מהיר ובעלות נמוכה. משלוח מייל אחרון הכוונה לשלב הסופי של שרשרת האספקה, בו חבילות מועברות ממחסן עד לפתחו של הלקוח. מדובר בבעיה טקטית מורכבת הכוללת קביעה משותפת כיצד להקצות חבילות למשאיות וכיצד לנתב את המשאיות ללקוחות. זו גם בעיה מאוד יקרה, עם הערכות אחרונות הצבת משלוח מייל אחרון ב-53% מעלות המשלוח הכוללת. זה מדגיש את הצורך לייצר תוכניות אספקה יעילות.
הצורה הקלאסית של בעיה זו כרוכה במחסן בודד (בדרך כלל מחסן) שממנו נטענות כל המשאיות ונשלחות החוצה במשלוחיהן. גרסה מורכבת יותר כוללת מחסנים מרובים בסמיכות זה לזה - למשל, כאשר רשתות קמעונאיות מספקות ממקומות חנויות. במקרה זה, לקוח נתון עשוי לקבל שירות על ידי יותר ממחסן אחד, ולכן על החברה לקבוע גם אילו מחסנים ישלחו לאיזה לקוחות. לפעמים לאף מחסן אחד לא יהיו כל הפריטים בהזמנת לקוח זמינים, מה שמחייב את ההזמנה לפצל בין מספר מחסנים.
להלן נדון כיצד ליצור מודל ולפתור את צורת הבעיה המורכבת יותר הזו באמצעות מחסנים תכנות מספרים שלמים (IP). לבעיה זו יש את ההיבטים הבאים:
- יש סט של משאיות, מחסנים, לקוחות ומוצרים.
- כל לקוח הזמין כמות מסוימת של כל מוצר, ולכל מחסן יש כמות מסוימת של כל מוצר זמין.
- כל משאית מבוססת בדיוק במחסן אחד (כלומר, המסלול שלה תמיד מתחיל ומסתיים בבסיסה). יתרה מכך, משאיות אינן חייבות להיות זהות - לכל משאית עשויה להיות קיבולת נפח שונה ועלות למייל.
המטרה היא לקבוע בו זמנית 1) את המוצרים שיישלחו מכל מחסן לכל לקוח, 2) כיצד להקצות חבילות למשאיות, ו-3) כיצד לנתב כל משאית ללקוחותיה, והכל באופן שישיג את הסכום הנמוך ביותר עלות משלוח אפשרית.
ניישם ונפתור מודל IP עם מוֹך ואת השימוש VerRoViz כדי לדמיין את מסלולי המשאית. כדי להתחיל, אנו מייבאים את הספריות הדרושות:
תרחיש לדוגמה
לחברת רהיטים יש שני מחסנים באזור פרדריקסבורג, וירג'יניה עם שמונה הזמנות של לקוחות שיסופקו. הנתונים והמפה מוצגים להלן. הערה: השמיים nodesArray המשתנה הוכן עם כלי סקיצה של VeRoViz, המאפשר יצירה גרפית של נתוני מיקום וייצוא לפייתון.
מודלים את הבעיה
אמנם ישנן מספר דרכים שניתן לגשת לבעיה זו, אך אנו נבנה ונפתור מודל תכנות של מספרים שלמים. זה נותן מפרט מתמטי מדויק של הבעיה ומאפשר לפתור מופעי בעיה בגודל בינוני בצורה אופטימלית באמצעות פותרי מדף (אם כי מעבר לתחום שלנו, מופעים גדולים יותר לרוב לא ניתנים לפתרון מהיר עם פותרי מדף ודורשים במיוחד -אלגוריתמי פתרונות מעוצבים). נתחיל בתשומות המודל:
לאחר מכן, אנו מגדירים את משתני ההחלטה שלנו:
לבסוף, אנו מגדירים את מודל האופטימיזציה:
במודל זה, הפונקציה האובייקטיבית (1) שאנו רוצים למזער היא פשוט הסכום של כל עלויות הנסיעה שנגרמו. אילוצים ב-(2) מבטיחים שלכל מיקום, אם משאית מסוימת מגיעה למקום, אז המשאית גם יוצאת. אילוצים ב-(3) מבטיחים שאף משאית לא תצא ממחסן שאינו הבסיס שלה. אילוצים ב-(4) מבטיחים שכל לקוח מקבל את כל המוצרים שהוא הזמין. אילוצים ב-(5) מבטיחים שלא יתרחשו תת-מעגלים בשום מסלול. מכיוון שלקבוצה של מיקומים היוצרים מעגל יהיה אותו מספר קצוות כמו צמתים, אנו מונעים זאת מלהתרחש בכל תת-קבוצה אפשרית של לקוחות לכל משאית. אילוצים ב-(6) מבטיחים שלכל מחסן ומוצר, סך כל היחידות של המוצר שהועמסו על משאיות ונשלחו ללקוחות מאותו מחסן לא יעלה על הזמינות במחסן. אילוצים ב-(7) מבטיחים שלא יועמסו יחידות של כל מוצר על משאית ונשלחות ללקוח אלא אם המשאית מבקרת את הלקוח. אילוצים ב- (8) מבטיחים שלכל משאית, הנפח הכולל של המוצרים שהועמסו על הסיפון אינו חורג מהיכולת שלה. לבסוף, אילוצים ב- (9-10) מציינים את התחומים עבור משתני ההחלטה (בינאריים עבור x משתנים; מספר שלם לא שלילי עבור ה u משתנים).
לנוחות ושימוש חוזר, ניצור פונקציית Python לבניית מופעים של מודל זה עבור נתוני קלט ספציפיים באמצעות מוֹך:
פתרון בעיית התרחיש לדוגמה
כעת, לאחר שגובשנו את המודל, נוכל להשתמש בו כדי למצוא פתרון אופטימלי לתרחיש שלנו. להלן אנו משתמשים בפותר CBC הכלול ב- מוֹך. זה עשוי לקחת 15-45 שניות כדי למצוא פתרון אופטימלי. אם יש לך גישה לחזקים יותר CPLEX פותר, אתה יכול להשתמש בשורות המוערות במקום כדי לקבל פתרון הרבה יותר מהר.
הפעלת זה נותן לנו את הודעת הפלט הבאה:
חילוץ וצפייה במסלולי המשאית
כעת עלינו לחלץ את מסלולי המשאית ממשתני ההחלטה במודל שנפתר. עבור כל משאית, אנו רוצים לדעת את העצירות שלה ואיזה מוצרים לספק בכל תחנה. כדי לקבל מידע זה, עלינו לנפות את משתני ההחלטה שאינם אפס.
זה בונה את מסלולי המשאית הבאים:
שימו לב שללקוח C1 מבקרים שתי משאיות (T2 ו-T4) - לפיכך, הזמנה מפוצלת. בהתחשב בדרישות ובמשאבים הזמינים של הלקוחות בו זמנית, זו מתבררת כהחלטה אופטימלית. זה עשוי להיות נחוץ גם כאשר, למשל, הזמנה מכילה קבוצה של פריטים שלא נמצאו באף מחסן בודד.
הדמיה של מסלולי המשאית
כשלב האחרון שלנו, אנו משתמשים VerRoViz כדי ליצור הדמיה יפה למסלולי המשאית:
סיכום
למרות וריאציות רבות על בעיה זו אפשריות, דוגמה זו ממחישה כיצד אנו יכולים ליצור מודל ולפתור בעיה כזו באמצעות תכנות מספרים שלמים. זה גם מראה כיצד ניתן להשתמש ב-Python כדי להדביק יחד רכיבים רבי עוצמה כגון מוֹך ו VerRoViz כדי ליצור מערכות תמיכה החלטות שימושיות במהירות. משלוח שמח!
ניתן לראות את קוד המקור במחברת כאן או הורדה כאן.
משלוח מייל אחרון ממספר מחסנים בפייתון פורסם מחדש ממקור https://towardsdatascience.com/last-mile-delivery-from-multiple-depots-in-python-26c4325407b4?source=rss—-7f60cf5620c9—4 דרך https:// richtingdatascience.com/feed
<!–
->
