מערכת תוכנה למציאת מסלול בתחבורה ציבורית ולשיפורו

מאת: אראל

אל: תחרות רעיונות בטכניון

קוד: תוכנת מסלולים

  • הקדמה

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

  • תיאור כללי

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

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

בהמשך אפרט יותר לגבי כל אחד מהרכיבים.

  • רכיב מציאת המסלול

קלט

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

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

דוגמא לקלט:

פלט

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

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

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

אם המשתמש היה דורש לצאת מקרית-חיים אחרי השעה 10:30, ולהגיע לכפר-סבא לפני 12:00, אבל לא מוכן לשלם יותר מ50 ש"ח, המערכת הייתה מודיעה שאין מסלול שעומד בדרישות, אך מציעה את שני המסלולים הנ"ל בתור מסלולים שעומדים בחלק מהדרישות.

פרמטרים ואפשרויות נוספות

מלבד פרמטרי המהירות והעלות, ניתן להכליל פרמטרים כמו:

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

פרטי מימוש

  • רכיב שיפור המסלול

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

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

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

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

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

פרטים נוספים

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

  • שיקולים כלכליים

  • סיכום

תגובות ישנות

נשלח על-ידי דורון סער ב12:45:29  30.03.2003:


האם מערכת תוכנה כזאת כבר קיימת?
אשמח להעזר בכותב התוכנה באתר שלנו:
מודיעין תחבורה ציבורית -  www.otobusim.com

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




נשלח על-ידי דורון סער ב21:27:49  04.08.2003: בואו נתחיל בקטן; דרושה עזרה באתר "אוטובוסים":


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

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


נשלח על-ידי יבגני מקסימוב   ב03:24:08  18.08.2003, בתגובה:


אני רואה 2 אפשרויות להמשך פיתוח האתר:

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

2. אתר כמו שאתה מתאר, יוכל לספק מידע מדוייק, אך בתנאי שהמסלול הנבחר יהיה קטן מאוד. למה? פה נכנסת בעיית הסוכן הנוסע, נניח, לדוגמא, שהמסלול צריך לעבור ב6 תחנות (שונות ופעם אחת בלבד בכל תחנה, כמובן). אם ניקח, לדוגמא, עיר ובא 6 תחנות, מייד ניווח כי ישנם 120 מסלולים העונים על הדרישה (5*4*3*2*1) או !(N-1), כאשר N מייצג את מס התחנות. פה זה מתחיל להסתבך, לכאורה, לבחור את המסלול הטוב ביותר מבין 120 המוצאים יקח למחשב מודרני לא יותר מכמה אלפיות השנייה. אם נשתמש במחשב המסוגל לבדוק מיליון מסלולים בשנייה - יקח לו 8 אלפיות השנייה להציג את המסלול הקצר ביותר.

פה זה מתחיל להסתבך, מה אם יש 7 תחנות? או 11? או 13? או 18? (מתוך אותן ה 10000):

(11-1)! = 3628800, כלומר המחשב הנתון יבצע את החישוב תוך 3.6 שניות.

(13-1)! = 479,001,600 - בערך 8 דקות - זה כבר לא מתקבל על הדעת.

(16-1)! = 1,307,674,368,000 מסלולים שונים! כלומר למחשב הנ"ל יקח לא פחות מאשר 15 יום לחישוב המסלול הטוב ביותר(!)

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

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



נשלח על-ידי אראל ב20:38:28  24.08.2003, בתגובה:


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


נשלח על-ידי רחל ב13:39:48  20.11.2003, בתגובה:


בתחנות ה"מטרו" וה"underground" כמדומני שקיימת מערכת שמאפשרת הזנת יעד וצפיה במסלול המבוקש.
בהצלחה!


נשלח על-ידי ניר אלפסי (212.179.217.131) ב02:12:45  02.03.2004,

בתגובה ל: ''בעיית הסוכן הנוסע'' או, זה לא מעשי שנשלח על-ידי יבגני מקסימוב ב03:24:08  18.08.2003:


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








תגובות