פוסטר מצגת

מוטיבציה לפרויקט

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

סקירת ספרות

בסקר הספרות חקרנו פתרונות ובחנו מידע בתחומים: מודלים לאופטימיזציה, תחום ההסעות וסוגי פתרונות אפשריים. אחד המחקרים שמצאנו הוא TSP – בעיית הוסכן הנוסע. הנהג שלנו (הסוכן) עובר בN ערים כאשר הנהג מבקר בכל עיר בדיוק פעם אחת והמסלול מתחיל ומסתיים בנק' המקור כאשר פונקצית המטרה היא – מינימום מרחק / זמן נסיעה בכל הערים. בעיית הסוכן הנוסע מתחלקת ל2 – סימטרית ואסימטרית. סימטרית – המרחק בין הנקודות זהה גם למרחק בכיוון ההפוך, אסימטרית – המרחק בין הנקודות אינו זהה במרחק בכיוון ההפוך – בדומה למקרה שלנו. חקרנו גישות לפתרון בעיה מסוג זה ומצאנו את אלגוריתם חמדני – אלגוריתם זה מתבסס על היוריסטיקה בה בוחרים את האפשרות הטובה ביותר הנראת לעין בשלב הנוכחי מבלי לקחת חשבון את ההשפעה של הצד הבא על המשך המסלול. שיטה נוספת שמצאנו היא שיטת השכן הקרוב ביותר. בשיטה זו כל "נהג" יפנה אל הנקודה הבאה הקרובה ביותר אשר עדיין לא ביקר בה עד שיבקר בכל הנקודות. לאחר בדיקת המסלול הראשוני עלינו לבדוק את כלל המסלולים האפשריים אך בכל איטרציה מנקודת התחלה שונה.

מתודולוגיה

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

ממצאים

מתוך 36 מסלולים – נמצאו 29 מסלולים שבהם נמצא שיפור בזמנים, 4 קווים בהם לא נמצא שיפור ו3 מסלולים בהם המסלול הקיים הוא המסלול האופטימלי. הזמן הממוצע שנחסך בכל מסלול הוא 6 דקות , בסה"כ נחסכו בכל המסלולים כ-223 דקות. מתוך 36 מסלולים – נמצאו 23 מסלולים שבהם נמצא שיפור במרחק, מסלול 1 בו לא נמצא שיפור ו12 מסלולים בהם המסלול שנמצא ארוך יותר מהמסלול הקיים מבחינת מרחק. ק"מ ממוצע שנחסך בכל מסלול: 2.75 ק''מ, בסה"כ נחסכו בכל המסלולים 98.9 ק"מ. בקו מספר 25 ישנם 5 נקודות. בקו זה ביצענו את חישוב המסלול האופטימלי – 5! אפשרויות. עפ"י החישוב באופטימלי מצאנו שניתן לחסוך 4 דקות לאומת המסלול הקיים ואילו עפ"י עיקרון השכן הקרוב יותר והחמדני לא מצאנו שיפור. מכיוון שבעיית TSP היא בעיית NP, לא חישבנו את הפתרון האופטימלי עבור כל המסלולים עקב אילוצי זמן, יכולת חישוב, וחוסר במידע עבור קיבולת הרכבים. לכן השתמשנו באלגוריתמים – השכן הקרוב ביותר והחמדני.

סיכום

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