גישה חדשנית לתזמון מוניות עצמאיות המבוססת על שידוך יציב (תורת המשחקים) 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). עצירת מונית ברחוב היא שיטה נפוצה להזמנת מונית, בעיקר בערים קטנות בהן השירות מתנהל בקנה מידה