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

Speaker
ד"ר שימי הבר
Date
05/12/2018–05 - 16:00 - 00:05Add to Calendar 2018-12-05 00:05:00 2018-12-05 16:00:00 פירוק גרפים למעגלים ותכנון מסלולי נסיעה הרצאה שניה בסגרה מה עושים עם זה הקמפוסים של אוניברסיטת ג'יין בהודו (Jain University) פרושים בכל רחבי בנגלור רבתי. האוניברסיטה הציעה לסטודנטים ולחברי הסגל שירות הסעות בין המחלקות, כיתות הלימוד והמעונות בעזרת עשרה אוטובוסים. מסלולי האוטובוסים נקבעו על ידי אנשי האוניברסיטה והנהגים באופן ידני. בסקר שנערך ב 2010 בין משתמשי השירות עלתה תמונה של חוסר שביעות רצון מזמני ההמתנה, אורך הנסיעות וזמינות האוטובוסים. בעקבות הסקר תוכננו מסלולי ההסעות מחדש ע"י חבר סגל מהמחלקה להנדסה בשיתוף עם שני מתמטיקאים. לאחר השינוי נדרשו רק שבעה אוטובוסים, זמני ההמתנה התארכו מעט אך זמני הנסיעה התקצרו משמעותית ושביעות רצון הנוסעים עלתה. איך יתכן שהתכנון המקורי היה רחוק כל כך מתכנון מיטבי? למעשה מדובר בבעיית פירוק של גרף למעגלים תחת אילוצים והיא הכללה של בעיית הסוכן הנוסע. בעיות תכנון מסוג זה ידועות כקשות במיוחד ועם זאת הן שימושיות ביותר. האסטרטגיות לפתרון כוללות מרכיבים מהסתברות, קומבינטוריקה, גיאומטריה, אופטימיזציה ועוד.   חדר הסמינריונים מספר 201, בניין 216 (מתמטיקה) אוניברסיטת בר-אילן - המחלקה למתמטיקה mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
חדר הסמינריונים מספר 201, בניין 216 (מתמטיקה)
Abstract

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

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

 

תאריך עדכון אחרון : 04/12/2018