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

יום ד', 05/12/2018 - 00:05
Speaker: 
Place: 
Abstract: 

הקמפוסים של אוניברסיטת ג'יין בהודו (Jain University) פרושים בכל רחבי בנגלור רבתי. האוניברסיטה הציעה לסטודנטים ולחברי הסגל שירות הסעות בין המחלקות, כיתות הלימוד והמעונות בעזרת עשרה אוטובוסים. מסלולי האוטובוסים נקבעו על ידי אנשי האוניברסיטה והנהגים באופן ידני. בסקר שנערך ב 2010 בין משתמשי השירות עלתה תמונה של חוסר שביעות רצון מזמני ההמתנה, אורך הנסיעות וזמינות האוטובוסים. בעקבות הסקר תוכננו מסלולי ההסעות מחדש ע"י חבר סגל מהמחלקה להנדסה בשיתוף עם שני מתמטיקאים. לאחר השינוי נדרשו רק שבעה אוטובוסים, זמני ההמתנה התארכו מעט אך זמני הנסיעה התקצרו משמעותית ושביעות רצון הנוסעים עלתה. איך יתכן שהתכנון המקורי היה רחוק כל כך מתכנון מיטבי?

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