מתמטיקה בדידה בעת הטמעת מערכת WMS: מקבץ קבוצות של סחורות במחסן

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

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

צוואר בקבוק בתהליכים

בשנת 2018 השלמנו פרויקט ליישום WMS-מערכות במחסן של חברת "בית המסחר "LD" בצ'ליאבינסק. הטמענו את המוצר "1C-Logistics: Warehouse Management 3" עבור 20 מקומות עבודה: מפעילים WMS, מחסנאים, נהגי מלגזות. המחסן הממוצע הוא כ-4 מ"ר, מספר התאים הוא 2 ומספר מק"ט הוא 5000. המחסן מאחסן שסתומים כדוריים מייצור עצמי בגדלים שונים החל מ-4500 ק"ג ועד 1 ק"ג. המלאי במחסן מאוחסן בקבוצות, שכן יש צורך בבחירת סחורה לפי FIFO.

בעת תכנון מערכות אוטומציה של תהליכי מחסן, עמדנו בפני הבעיה הקיימת של אחסון מלאי לא אופטימלי. הספציפיות של עגורני אחסון ואגירה הם כאלה שתא אחסון יחידה אחד יכול להכיל רק פריטים מאצווה אחת. המוצרים מגיעים למחסן מדי יום וכל הגעה היא אצווה נפרדת. בסך הכל, כתוצאה מפעילות של חודש אחד במחסן, נוצרות 1 אצוות נפרדות, למרות העובדה שכל אחת מהן צריכה להיות מאוחסנת בתא נפרד. מוצרים נבחרים לרוב לא במשטחים שלמים, אלא בחלקים, וכתוצאה מכך, באזור בחירת החלקים בתאים רבים נצפית התמונה הבאה: בתא בנפח של יותר מ-30 מ"ק יש כמה חתיכות של עגורנים תופסים פחות מ-1-3% מנפח התא.

איור 1. תמונה של כמה חלקי סחורה בתא

ברור שקיבולת האחסון אינה מנוצלת בצורה מיטבית. כדי לדמיין את קנה המידה של האסון, אני יכול לתת נתונים: בממוצע, ישנם בין 1 ל-3 תאים של תאים כאלה בנפח של יותר מ-100 מ"ק עם איזונים "זעירים" בתקופות שונות של פעולת המחסן. מכיוון שהמחסן קטן יחסית, בעונות העמוסות במחסן גורם זה הופך ל"צוואר בקבוק" ומאט מאוד את תהליכי המחסן.

רעיון לפתרון בעיה

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

איור 2. תכנית לדחיסת שאריות בתאים

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

תהליך פתרון בעיה כזו מחולק ל-2 שלבים:

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

במאמר הנוכחי נתמקד בשלב הראשון של האלגוריתם, ונשאיר את הסיקור של השלב השני למאמר הבא.

חפש מודל מתמטי של הבעיה

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

מכיוון שברור מהניסוח העסקי של הבעיה נובע שאנו עוסקים בקבוצות, ננסח בעיה כזו במונחים של תורת הקבוצות.

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

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

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

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

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

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

כאשר משתמשים באלגוריתמים כאלה כדי לפתור את הבעיה הנידונה, עלול להיווצר מצב כמו באיור 3.

איור 3. יישום אלגוריתמי אשכולות לבעיה הנפתרת

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

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

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

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

ניתן למצוא ניתוח מפורט של בעיה זו כאן и כאן. ניתן למצוא אפשרויות אחרות ליישום מעשי של בעיית הכיסוי והשינויים שלה כאן.

אלגוריתם לפתרון הבעיה

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

1. מסדרים קבוצות מסט בסדר יורד של התאריכים שלהם.
2. מצא את תאריכי האצוות המינימליים והמקסימליים.
3. לכל יום מהתאריך המינימלי למקסימום, מצא את כל הקבוצות שהתאריכים שלהן שונים לא יותר מ (אז הערך עדיף לקחת את המספר הזוגי).

ההיגיון של ההליך ליצירת משפחה של סטים при ימים מוצג באיור 4.

איור.4. יצירת תת-קבוצות של מפלגות

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

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

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

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

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

הטמעה והטמעה של האלגוריתם

אלגוריתם זה יושם בשפה 1S ונכלל בעיבוד חיצוני בשם "דחיסת שאריות" שהיה מחובר אליו WMS-מערכת. לא הטמענו את האלגוריתם בשפה C ++ ולהשתמש בו מרכיב Native חיצוני, וזה יהיה נכון יותר, מכיוון שמהירות הקוד נמוכה יותר C + + פעמים ובדוגמאות מסוימות אפילו גבוה פי עשרות מונים מהמהירות של קוד דומה 1S. על הלשון 1S האלגוריתם יושם כדי לחסוך זמן פיתוח וקלות איתור באגים בבסיס הייצור של הלקוח. התוצאה של האלגוריתם מוצגת באיור 5.

איור.5. עיבוד ל"דחיסה" של שאריות

איור 5 מראה כי במחסן שצוין, היתרות השוטפות של סחורות בתאי אחסון מחולקות לאשכולות, שבתוכם תאריכי אצוות הסחורות שונים זה מזה ב-30 ימים לכל היותר. מאחר והלקוח מייצר ומאחסן במחסן שסתומי כדור מתכת, שחיי המדף שלהם מחושבים בשנים, ניתן להזניח הפרש תאריכים שכזה. שים לב כי עיבוד כזה משמש כיום באופן שיטתי בייצור, ובמפעילים WMS לאשר את האיכות הטובה של אשכול אצווה.

מסקנות והמשך

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

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

הכין את הכתבה
רומן שנגין, מתכנת מחלקת הפרויקטים,
חברת BIT הראשונה, צ'ליאבינסק

מקור: www.habr.com