גישה חדשנית לתזמון מוניות עצמאיות המבוססת על שידוך יציב (תורת המשחקים) A novel approach to independent taxi scheduling problem based on stable matching

גישה חדשנית לתזמון מוניות עצמאיות המבוססת על שידוך יציב

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

1.הקדמה

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

ניתן באופן כללי לסווג שירותי מוניות לשלוש קטגוריות: עצירת רחוב (street hailing), תחנת מוניות (taxi stand), והזמנה מראש (booking). עצירת מונית ברחוב היא שיטה נפוצה להזמנת מונית, בעיקר בערים קטנות בהן השירות מתנהל בקנה מידה קטן יחסית. עצירה ברחוב היא שיטה פשוטה שאינה דורשת ציוד או מערכת יקרה. עם זאת, כפי שנדגים בהמשך, עצירת רחוב גורמת למספר בעיות, הכוללות ניצול גרוע של השירות, זמן המתנה ארוך עבור הנוסעים, בעיות בטיחות בכביש, ועיכוב התנועה. לתחנת מוניות יש מספר קטן יותר של בעיות, אך הן יכולות לשרת רק מספר קטן יחסית של נוסעים, במספר מקומות קבועים, כמו לדוגמא מרכזי ערים, תחנות רכבת/אוטובוס, נמלי תעופה וכדומה. הזמנת מונית מראש נחשבת כשיטה המתקדמת והיעילה ביותר לשימוש במוניות, אך היא אינה מעשית כאשר קיים מספר גדול של נהגים עצמאיים. ההזמנה יכולה להתבצע באמצעות השיטה המסורתית של שיחת טלפון, או באמצעות טכנולוגיית תקשורת אחרת (לדוגמא באמצעות אתר אינטרנט, או באמצעות הודעת טקסט). ההזמנה מתבצעת דרך מרכז שירות האוסף את כל פרטי הנוסעים ומתאם באופן מרוכז את הגעת המוניות. מערכת השילוח מסתמכת לעתים קרובות על מכשירי GPS וציוד תקשורת אלחוטי. היתרון של מערכת הזמנה כמו זו הוא שבקשות הנוסעים הן ברורות וידועות מראש. אחד החסרונות שלה הוא שמערכת כזו היא יקרה, ולכן מתאימה רק לחברות מוניות גדולות. בנוסף, המערכת מסתמכת על אמון הדדי בין הנהגים לנוסעים, כלומר על ההבנה כי אף אחד מהצדדים לא יפספס את הפגישה שנקבעה. למרבה הצער, במציאות, אי-הגעה כזו מתרחשת לעתים קרובות במדינות רבות.

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

קיימים מספר פרויקטים מחקריים וחידושים טכנולוגיים בתחום מערכות ההזמנה מראש, שלרוב מכונות בקיצור Dial-A-Ride Problem או DARP, השייכת באופן כללי לקטגוריה הקלאסית הנרחבת של בעיית ניתוב כלי רכב (vehicle routing problem) או כבעיית תיקון נסיעה (traveling repair problem). בנושא זה פותחו מספר אלגוריתמים מקוונים (on-line) שהשתמשו בתכנון ליניארי, היוריסטיקה, ומטא-היוריסטיקה. מערכות GPS ומערכות מידע גיאוגרפי (GIS) משמשות מערכות הזמנת מוניות בערים רבות, על מנת לשפר את יעילות השירות שלהן. לדוגמא, מערכת מיקום רכב והזמנת מונית אוטומטית על בסיס GPS  שיפרה באופן ניכר את האיכות והיעילות של שירותי המוניות בסינגפור. ברגע שהזמנת המונית מתקבלת במערכת, מרכז השילוח יאותת למוניות הנמצאות בטווח של 10 ק”מ מהנוסע. אם אחד מהנהגים מקבל את הנסיעה, הוא יכול לסמן זאת לסדרן הנמצא בתחנה באופן פשוט, באמצעות לחיצה על כפתור המותקן במונית. ברגע שהנסיעה נקבעה, מספר המונית וזמן ההגעה המשוער יישלחו מיידית ללקוח.

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

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

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

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

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

2. מערכת חדשה לעצירות רחוב

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

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

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

2) מטרתה העיקרית של כל מונית היא למצוא את הנוסע הבא בזמן האפשרי הקצר ביותר.

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

4) מיקום הנוסעים והמוניות מתקבל אוטומטית דרך מערכת ה-GPS ונמסר לשרת באמצעות התוכנה הנמצאת אצל הלקוח.

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

איור 1: משמאל לימין – טלפון נייד לקוח (תקשורת, GPS, ממשק) > הזמנת מונית > שרת (תקשורת, מיקום, תמיכה בהחלטות, ממשק) > טלפון נייד מונית (תקשורת, GPS, ממשק). למטה – מסד נתונים (database).

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

3. מודל משחק תיאורטי

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

הבה נקבע כי Ti (i = 1, …, n) מייצג את המוניות, Pj (j = 1, …, m) מייצג את הנוסעים, ו-Tij מסמל את הזמן הצפוי שבו מונית Ti תגיע לנוסע Pj. נקבע בנוסף כי Eij מייצג את ההעדפה של מונית Ti כלפי נוסע Pj. במאמר זה אנו מציגים מערכת עצירת רחוב חישובית, בניגוד למערכת הזמנה מראש, ואנו מניחים כי נהגי המוניות אינם מקבלים מידע לגבי היעד של אף אחד מהנוסעים. הנהגים יכולים, לפיכך, להסתמך רק על מידע ה- tij לגבי העדפות הנוסע ולכן יעדיפו נוסעים הנמצאים קרוב אליהם. לפיך אנו מניחים כי Eij נקבע באופן מוחלט על ידי tij והוא בעל קורלציה שלילית עם tij. עבור הניסויים המתוארים במאמר זה, אנו מניחים כי Eij מוגדר באופן הבא, על מנת לענות על דרישות אלו: (משוואה (1) בעמ’ 3 מימין, סוף פסקה שנייה).

היכולת של מונית A לקחת נוסע שהוקצה למונית B מסתמכת על כך שגם הנוסע ירצה בכך וגם כי מונית A מסוגלת להגיע לנוסע לפני מונית B. אנו מניחים כי לנוסע אין כל העדפה כלפי המוניות מלבד הרצון באיסוף מהיר ככל האפשר, כך ששני גורמים אלו יכולים להיחשב כזהים במקרה זה. העדפת הנוסע, המייצגת את יכולתו של נהג מסוים לקחת נוסע זה מנהג אחר, יכולה לפיכך להיקבע באמצעות ההנחה כי העדפת הנוסע Pj כלפי מונית Ti היא בעלת קורלציה שלילית עם tij. מונית A יכולה לפיכך לקחת את נוסע Pj ממונית B רק כאשר tAj < tBj , כלומר, אם היא מסוגלת להגיע לנוסע קודם.

איור 2: אלגוריתם תזמון. מלמעלה למטה – התחלה > השרת מחלק את מפת העיר לאזורים קטנים יותר על בסיס הדרישות > (צד שמאל) מוניות ריקות שולחות מידע לגבי מיקום וסטאטוס לשרת באופן חוזר, (צד ימין) הנוסעים שולחים מידע לגבי מיקומם לשרת באופן חוזר > השרת מקבל מידע מהלקוחות (מוניות ונוסעים), מעדכן את מסד הנתונים, ואז משדר, עבור כל אזור, את המידע לגבי כל המוניות והנוסעים חזרה ללקוחות > המתנה לחלון התזמון הבא tw > חישוב שידוך נוסע-מונית יציב ושליחת התוצאות חזרה לכל לקוח > הלקוחות מקבלים הקצאות ושולחים משוב לשרת. השרת מעדכן את תיעודי מסד הנתונים התואמים, ושולח סטאטוסים מעודכנים לגבי הנוסעים והנהגים חזרה ללקוחות > האם נותרו נוסעים ללא תזמון? > T – חזרה לצעד 3, F – סיום.

אם אנחנו מגדירים את העדפת הנהג (Eij) כניקוד של שותף אחד ואת העדפת הנוסע כניקוד של השותף השני, אז בעיית הזיווג של נוסע-מונית יכולה להיחשב כווריאציה של בעיית הנישואים היציבים (stable marriage problem). בעיית הנישואים היציבים מתייחסת למצב שבו יש n גברים ו-n נשים, שכל אחד מהם דירג את כל בני המין השני כמספר מסוים בין 1 ל-n, לפי סדר העדפה. המטרה היא למצוא זיווגי אישה-גבר כך שלא יישארו שני אנשים משני המינים המנוגדים ששניהם מעדיפים זה את זה על פני בן הזוג הנוכחי שלהם. אלגוריתם גייל-שייפלי פותח על מנת לפתור בעיה זו בזמן פולינומיאלי. אלגוריתם זה כולל מספר “סיבובים”. בכל סיבוב, כל גבר בלתי מזווג “מציע” לאישה המועדפת עליו ביותר, שלה טרם הציע בעבר. לאחר מכן האישה שוקלת את כל ההצעות שניתנו לה, בוחרת את בן הזוג המועדף עליה ומזווגת אליו, תוך אפשרות ל”שדרוג” של זיווגה הנוכחי. תהליך זה ממשיך עד שלא נותרים עוד גברים ללא זיווג. אלגוריתם גייל-שייפלי מבטיח שידוך יציב.

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

עבור בעיית תזמון המוניות בה אנו עוסקים כאן, בהינתן ההגדרה של {Eij} והקורלציה הנובעת מכך בין שני הדירוגים, ניתן לפשט את אלגוריתם גייל-שייפלי. אנו מאמצים אלגוריתם שראשית כל ממיין את כל האלמנטים במטריקס ההעדפה {Eij} בסדר יורד, ולאחר מכן שוקל כל פריט בתורו, מהראשון לאחרון. עבור כל אלמנט Eij, אם גם מונית i וגם נוסע j טרם קיבלו הקצאה אזי i יוקצה ל-j ו-(i,j) יהפוך להיות חלק מהשידוך היציב. סיבוכיות הזמן של האלגוריתם המוצע הינה O(mn X log (mn)) מכיוון שהמיון הינו האלמנט האיטי ביותר. קל מאוד לוודא כי השידוך היציב הוא שיווי משקל נאש, מכיוון שהנוסעים היחידים אליהם הנהג יכול להחליף באופן שיהיה עדיף עבורו כבר קיבלו הקצאה למונית יותר קרובה אליהם.

חייב להתקיים לפחות שידוך יציב אחד (שיווי משקל נאש) בהינתן מטריקס ההעדפה {Eij} , כל עוד כל ה- {Eij} הם עצמאיים. האלגוריתם המוצע ימצא לפחות שידוך אחד כזה. עם זאת, אפילו כאשר ניתן להבטיח שידוכים יציבים, האלגוריתם ימצא רק שידוך אחד כזה בכל פעם. כאשר קיימים מספר נוסעים קרובים שעבורם זמן נסיעת המונית הוא זהה, האלגוריתם חייב לקבל החלטה לגבי איזה נוסע עליו להקצות לאותה מונית. קומבינציות שונות של בחירות בין זמני נסיעה זהים יובילו לשידוכים שונים. לכן, ייתכן ויתקיים מספר גדול של שידוכים יציבים עבור בעיה נתונה, שבה קיימות מספר מוניות עם זמני נסיעה זהים עבור הנוסעים. איור 3(a) מציג דוגמא של מקרה כזה, עבור בעיית שני נוסעים-שתי מוניות. בדוגמא זו, ניתן להקצות את מונית T1 לנוסע P1 או לנוסע P2 ,דבר שיוביל לשידוך יציב בשני המקרים. לעומת זאת, הקצאה בעלות כוללת נמוכה יותר תהיה הקצאה של מונית T1 לנוסע P2 יותר מאשר הקצאה של T1 לנוסע P1, בשל הבדלי זמן הנסיעה עבור מונית T2.

איור 3(a): דוגמא לבעיה עם שידוכים יציבים רבים. בלי קשר לשאלה לאיזה נוסע (P1 או P2) תוקצה מונית T1 , מונית T2 תוקצה לנוסע השני וכך יישמר השידוך היציב. איור 3(b) מציג בעיה שבה הפתרון החברתי האופטימאלי אינו שידוך יציב. הפתרון החברתי האופטימאלי מקצה את מונית T1 לנוסע P2 ואת מונית T2 לנוסע P1, עם זמן כולל של 4 יחידות. עם זאת, פתרון זה אינו יציב מכיוון שמונית T1 יכולה להחליף לנוסע P1 , עבור התועלת של הנהג והנוסע כאחד.

מבין כל השידוכים השונים של מונית-נוסע, השידוך עם ה-POA הגבוה ביותר הוא קורץ במיוחד מפני שהוא ממקסם את התגמול החברתי. עם זאת, שידוך אופטימאלי זה (עלות כוללת/זמן המתנה הנמוכים ביותר) עלול להיות בלתי יציב. לדוגמא, הבה נבחן את בעיית שתי המוניות-שני הנוסעים המוצגת באיור 3(b). במצב זה, השידוך האופטימאלי הוא לשדך את מונית T1 עם נוסע P2 ואת מונית T2 עם נוסע P1. אך שידוך זה אינו יציב מפני שמונית T1 יכולה להחליף לנוסע P1 הקרוב אליה יותר וכך לצמצם את העלויות שלה. מכיוון שאנו מתייחסים למצב זה כמשחק לא-שיתופי, רק שידוכים יציבים יכולים להוות פתרונות תקפים ואנו מתייחסים רק להבדלים ב-POA בין השידוכים היציבים, ובמיוחד להבדלים בין השידוך היציב הנוכחי לאופטימאלי.

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

4. דוגמאות חישוביות

בחלק זה, אנו יוצרים הדמיה של בעיית תזמון המוניות בתוך שטח מרובע של 50 ק”מ X 50 ק”מ. המוניות והנוסעים יופיעו, ברוב המקרים, באזורי איסוף פופולאריים כמו מרכזים עסקיים, נמלי תעופה, תחנות רכבות וכדומה. המיקום של הנוסעים והמוניות מפוזר בקירוב באזורים אלו לפי התפלגות פואסון (Poisson). בהדמיות אלו, המרחק בין המונית לנוסע נקבע באמצעות המרחק האוקלידי (Euclidean) בין המיקומים שלהם. המרחקים נשקלו בדיוק של 0.15 ק”מ, כך ששני מרחקים שונים הוגדרו כזהים כאשר ההבדל ביניהם היה פחות מ-0.15 ק”מ.

4.1 שידוך יציב אופטימאלי

בחלק זה נתאר את ההדמיה שיצרנו על מנת להשוות את השידוכים היציבים שנוצרו באמצעות אלגוריתם גייל-שייפלי המופשט לשידוך היציב האופטימאלי, שהוא השידוך היציב בעל מרחק האיסוף הכולל המינימאלי ביותר. ההדמיה כוללת פתרון של בעיית תזמון מוניות עם 1000 מוניות ו-1000 נוסעים באמצעות האלגוריתם גייל-שייפלי המופשט שתואר מעלה. המיקום של המוניות והנוסעים מוצג באיור 4. קיימות 3 נקודות איסוף פופולאריות בשטח ההדמיה. השטח מחולק ל-333 X 333 אזורי משנה, שכל אחד מהם הוא בגודל ריבוע של 0.15 ק”מ X 0.15 ק”מ. כל המיקומים מוגדרים לאחר מכן במונחים של אזורי המשנה. אזור המשנה המרכזי עבור כל אחת מ-3 נקודות האיסוף נקבע באופן רנדומאלי באמצעות התפלגות רנדומאלית אחידה עבור קואורדינאטות X ו-Y. הנוסעים והמוניות מוקצים לאחר מכן לנקודות האיסוף באופן רנדומאלי באמצעות התפלגות אחידה והמיקום באזורי המשנה עבור כל מונית ונוסע נקבע באמצעות התפלגות פואסונית, כאשר λ = 70, 35, 35 בהתאמה, על מנת לקבוע את ערכי X ו-Y של קיזוז אזור המשנה מנקודת האיסוף אליו הם הוקצו.

איור 4: התפלגות של 1000 מוניות ו-1000 נוסעים בתוך שטח ריבועי (המוניות מסומנות ב-X והנוסעים מסומנים בנקודות).

איור 5: שידוך יציב אופטימאלי של 1000 מוניות ו-1000 נוסעים. (a) המרחק לנוסע של 1000 מוניות. (b) הסטטיסטיקה של מספר המוניות בהתאמה למרחק הנסיעה.

השידוך היציב האופטימלי עבור 1000 זיווגים של מוניות ונוסעים, חושב באמצעות חיפוש כוח-גס (brute force) בהטמעה שביצענו, והמרחקים בין המוניות והנוסעים מוצגים באיור 5(a), מסודרים לפי הקטן ביותר עד הגדול ביותר. המרחק הקטן ביותר הוא 0, והגדול ביותר הוא 64.9 ק”מ. איור 5(b) מראה את מספר המוניות הנופלות בגדר מספר טווחי מרחק שונים. האיור מראה כי רוב המוניות המתוזמנות נוסעות מרחק קטן בלבד לצורך איסוף הנוסעים, בעוד שמספר קטן של מוניות נאלצות לנסוע מרחק גדול (יותר מ-14 ק”מ). זמן החישוב הדרוש לצורך השידוך היציב הטוב ביותר תלוי במספר מצבי שיווי המשקל (שידוכים יציבים) הקיימים בבעיית תזמון נתונה. במקרה הטוב ביותר, סיבוכיות הזמן היא O(mn X log(mn)) כאשר קיים רק שידוך יציב אחד. במקרה הגרוע ביותר, סיבוכיות הזמן יכולה לעלות ל- O(nm). במקרה של הבעיה המוצגת באיור 5, זמן החישוביות עבור פתרון שידוך יציב לא-אופטימאלי היה 0.4 שניות על PC עם CPU אינטל כפול של 2.66 GHz, בעוד שזמן החישוביות הנדרש להשיג את הפתרון היציב האופטימאלי באמצעות חיפוש כוח-גס היה 24.5 דקות.

איור 6: השוואה בין השידוך היציב האופטימאלי (קו אדום) לשידוך יציב לא-אופטימאלי (קו כחול).

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

על מנת לחקור את השפעת מספר המוניות ואת הגדרת המקדמים הפואסונים על הפער בין השידוך היציב האופטימאלי לבין השידוך היציב הלא-אופטימאלי, ביצענו סדרה של הדמיות על אזור מדומה ריבועי של 100 ק”מ X 100 ק”מ. מספר המוניות נקבע כזהה למספר הנוסעים. הנוסעים והמוניות מפוזרים באופן רנדומאלי, לפי התפלגות פואסונית. חישבנו את השידוך היציב האופטימאלי עם מספרים שונים של מוניות (מ-100 עד 1000) ופרמטרים פואסוניים שונים λ (מ-30 עד 700). איור 7 מראה את מרחק הנסיעה הממוצע של המוניות בפתרון היציב האופטימאלי ובפתרון היציב הלא-אופטימאלי, בהינתן התפלגות פואסונית שבה λ = 70. בנוסף מוצגת השוואת תוצאות של פתרון יציב אופטימאלי מתוקן ופתרון יציב מתוקן, המתעלם ממוניות שמרחק הנסיעה שהוקצה להן ≥ 50 ק”מ. יש לציין כי נהגי המוניות אינם חייבים לאסוף נוסעים, והסבירות שהם יאספו נוסעים יורדת ככל שמרחק הנסיעה עולה. איור 8 מראה את ההשפעה של פרמטרי פואסון שונים עבור מספר קבוע של מוניות (200). מרחק הנסיעה הממוצע בשידוך הוא קטן כאשר ההתפלגות של הנוסעים והמוניות היא ממורכזת (ערכי λ הם נמוכים). מצד שני, מרחק הנסיעה הממוצע הוא גבוה כאשר הנוסעים והמוניות הם מפוזרים. ניתן לראות כי ההבדל בין הפתרונות המתוקנים הוא מוגבל מאוד בשני האיורים.

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

איור 8: ההשפעה של מקדמי פואסון על מרחק הנסיעה הממוצע של המוניות.

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

לשם השוואה, פותחה אסטרטגיית “כל הקודם זוכה” (first come first serve, FCFS), שבה הנוסעים מוקצים למוניות לפי סדר ההזמנה שלהם, וכל נוסע הוקצה למונית הקרובה אליו ביותר. אלגוריתם FCFS הוא “הוגן” עבור הנוסעים אך הוא מגדיל את מרחק הנסיעה הפנוי (כלומר ללא נוסעים) הממוצע עבור הנהגים, בהשוואה לשידוך היציב האופטימאלי שבו הנהגים משתפים פעולה על מנת לצמצם את מרחק הנסיעה הפנוי. איור 9 מציג השוואה זו בין אסטרטגיית ה-FCFS מול השידוך היציב האופטימאלי.

איור 9: השוואה בין השידוך היציב האופטימאלי לבין אסטרטגיית ה-FCFS. הקו המקוטע מסמל את התוצאות של FCFS.

4.2 אלגוריתמים לתזמון דינאמי

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

1) FCFS. המונית הפנויה הקרובה ביותר תוקצה מיידית, ברגע שההזמנה מתבצעת.

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

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

האלגוריתם קודד באמצעות Visual C++ והניסויים הורצו על PC עם CPU אינטל כפול 2.66 GHz ו-3.25 RAM. התוצאות של הדמיה זו מוצגות בטבלה 1. באסטרטגיה 1, קיים עיכוב בין רגע ההזמנה של הלקוח לתזמון השירות בפועל (5 דקות במקרה הגרוע ביותר). למרות שמרחק הנסיעה הפנוי הממוצע של המוניות יורד בהשוואה ל-FCFS, החיסכון בזמן ההמתנה של הלקוח אובד בגלל העיכוב בתזמון. אסטרטגיה 2 מציגה את זמן ההמתנה הקצר ביותר עבור הנוסעים, בהשוואה לאסטרטגיות האחרות.

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

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

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

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

ככל שהערך של tw קטן יותר, כך הזמנת השירות תיענה מהר יותר. במקרים קיצוניים, אסטרטגיות 1 ו-2 הופכות ל-FCFS כאשר tw = 0. עם זאת, איכות הפתרונות תהיה נמוכה כתוצאה מכך. מצד שני, הסבירות כי מוניות יוקצו לנוסע הקרוב ביותר תהיה גבוהה יותר כאשר tw הוא גבוה יותר, אך זמן ההמתנה של הנוסעים יהיה ארוך יותר במקרה כזה. אסטרטגיה 2 היא למעשה מעין איזון בין אסטרטגיה 1 ל-FCFS. אסטרטגיה 2 תהפוך ל-FCFS כאשר Iw -> ∞ ולאסטרטגיה 1 כאשר Iw -> 0.

איור 10: זמן ההמתנה של הנוסעים (נוסעים עם זמן המתנה של מעל 14 דקות אינם מוצגים)

איור 11: מרחק הנסיעה של 5000 המוניות.

איור 12: מרחק הנסיעה הפנוי של 5000 המוניות.

5. סוגיות הטמעה מעשיות

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

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

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

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

איור 13: דוגמא לבעיה שבה לשתי מוניות יש זמן הגעה זהה לנוסע.

6. מסקנות וכיווני מחקר אפשריים בעתיד

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

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

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