360 Via

פודקאסט מספר 360 של רברס עם פלטפורמה - אורי ורן פותחים את 2019 עם גיא ואודי מחברת Via לשיחה בעיות תנועה, סוכנים נוסעים ותכנות לינארי בשלמים (יותר כיף ממה שזה נשמע). לפני הכל, חדשות מרגשות - כנס רברסים השביעי (Reversim Summit 2019) יוצא לדרך! 17-16 ביוני 2019 - עדכנו ביומן ספונסרים יתקבלו בברכה - אם החברה שלכם רוצה להיות בשורה הראשונה בכנס, זה הזמן לתפוס מקום. וגם אתם - ה Call for Papers נפתח! - בואו ספרו על משהו מעניין שעשיתם או למדתם וחושבים שכדאי לשתף - הגשות עד סוף פברואר (28/2) אז Via - השיחה תעסוק גם בצד העסקי וגם בצד האלגרוריתמי, ובשביל זה גיא ואודי כאן -  גיא מנהל את פהעילות העסקית של Via בישראל, מגיע מרקע של ניהול פרויקטים והיום ב-Via מתרכז בהשקת השירות בישראל - במהרה בימינו (שמעתם כאן לראשונה. בערך). אודי -  מתימטיקאי, 15 שנים בתחום, מנהל קבוצת אלגוריתמים ב-Via (הרחבה על אלגוריתמים בהמשך, יש למה לחכות עם הספר של קורמן) אז מהו המוצר של Via? חברה טכנולוגית שפיתחה מערכת לתחבורה ציבורית חכמה האלגורתים יודע  לאסוף ולחבר אנשים על מנת לשתף נסיעה על אותו רכב - בכ-30 ערים בעולם, כשנוסע מזמין נסיעה האפלקיציה מנחה אותו להגיע לנקודת העלייה (פינת הרחוב הקרובה למשל), ומאפשרת לחלוק את הנסיעה עם עוד אנשים איך זה נראה? מיניבוס, לרוב של מפעיל קיים או של העירייה, או מונית גדולה שבאה ואוספת ומסיעה באיזור מוגדר. המוצר יודע גם לספק מערכת למפעיל קיים - טאבלט עבור הנהג שמקבל הנחיות נסיעה והורדת / העלאת נוסעים (יש גם אפליקציות לנוסעים, מפעילי נסיעה וכו’) - וגם להפעלה עצמאית ע”י Via (אמסטרדם, לונדון ועוד) מכירים Uber, Gett וכו’? אז מעיין שילוב של Uber ואגד עם אלמנט של On-Demand והרבה טכנולוגיה. בישראל יש פיילוט עם חברת דן שמובל ע”י משרד התחבורה והאוצר - נדבך נוסף לשירות של דן בתל אביב, רמת גן וגבעתיים. מיניבוסים של דן עם חוויית שירות מלאה של Via, שיסעו במרחב פוליגון מסויים (תמיד רציתם לנסוע בפוליגון? הנה זה בא); ממוקד באיזורי התעסוקה ותחנות הרכבת - במטרה להוריד את הרכבים הפרטיים מהכביש עד כמה שניתן - הרכב הפרטי מוגדר כמתחרה האמיתי. מזמינים נסיעה, קובעים יעד - ונוסעים עם עוד אנשים (קצת דומה ל- UberPool) בישראל יש כזה כבר? אין סיבה שלא כל האוטובוסים יעבדו ככה, במקום לעבוד עם תחנות וזמנים קשיחים בהינתן שאנחנו יודעים איפה כל נוסע נמצא (אם הוא רוצה ובוחר לשתף נקודת מוצא ויעד), אין סיבה לא “לדבר” עם אמצעי תחבורה אחרים. עם או בלי Via - זה משהו שכבר קורה. לדוגמא - נוסעים ב-Via, יורדים ליד תחנה של אופניים שיתופיים וממשיכים איתם לרכבת עוד נדבך - רכב חשמלי קצת פחות PR מהרכב האוטונומי לאחרונה ועדיין מהפכה ענקית - Via מנהלת צי כזה בברלין. גם ירוק יותר וגם מאפשר לנהל את צריכת האנרגיה של הרכבים כך שהנוסע אדיש למצב הסוללה עוד יותר קריטי בוואן של 8-10 מקומות. רגע - כשמישהו נכנס לאוטובוס היום, המסלול קבוע והוא יודע לאן נוסעים ומתי מגיעים, בערך. עם Via הנוסע לא באמת יודע מה יהיה המסלול מקביל היום למצב בו אתה היום נוסע במונית, נתקע בפקק - ומחליט לרדת ולהמשיך ברגל.  המערכת יודעת לחשב מקרים כאלה בזמן אמת ולהגיד מתי כדאי לקום ולהמשיך ברגל - בכל פעם תתקבל תוצאה אחרת בהתאם למצב הנתון. הסתיים משחק כדורגל? שכונה חדשה אוכלסה מאז שנקבע המסלול של הקו? רכבת תחתית כבר נבנית (15-20 שנה וזה כאן)? המערכת של Via מגיבה בזמן אמת. החשש מאוד רלוונטי, והאחריות של מוצר היא שזה לא יקרה - שהדרך תיהיה היעילה ביותר עם העיקופים המינימליים - על מנת שהלקוח יחזור וישתמש במוצר כי החווייה טובה. התשלום - גמיש לגמרי, נקבע יחד עם המפעיל (מרחק, זמן וכו’) - יקר מתחבורה ציבורית אבל זול ממונית ספשייל. מחזיר לניגוד האינטרסים בין תשלום לפי זמן לבין המסלול היעיל ביותר - ולאותה תשובה של מחוייבות ארוכת טווח ללקוחות חוזרים ולא ניסיון למקסם רווח במפגש יחיד. מעבר לזה - הניסיון התפעולי מאפשר לפתח מוצרים לשיפור חוויית משתמש - תמרוץ נהגים, למשל הנהגים הם גם לקוחות, שמעודדים אותם לאסוף כמה שיותר נוסעים ולחזור ולהפעיל את השירות גם מחר. אם הנהג נתקע צריך לספק לו רכב אחר, למשל. הנהג יכול להתערב באלגוריתם- לא לקבל נוסע למשל? בקצרה - לא. אין 100% שליטה (לא, אסור לחשמל נהגים סוררים), אבל בגדול המשוב מהנהגים מאוד חיובי. ברלין, ניו-יורק - איפה עוד? סידני, לונדון, אמסטרדם - וגם בערים קטנות זה עובד לא פחות טוב לא - כרכור עדיין לא, אבל Milton Keynes באנגליה או מחוז קנט דרומית ללונדון דווקא כן  וגם פחות סטנדרטי - Via מפעילה את השאטלים של הרווארד, גם סוג של עיר לא קטנה. עוד דוגמא - Arlington בטקסס - העיר הגדולה ביותר בארה”ב ללא תחבורה ציבורית ראוייה (400 אלף תושבים). היה קו אחד. ראש העיר ביטל גם אותו ועכשיו Via אחראית על התחבורה הציבורית החברה אמריקאית, הוקמה ע”י שני יזמים ישראלי - אורן שובל ודניאל רמות אורן נסע במונית שירות בתל אביב, שמע את השיחה של הנהג עם הסדרן והניח שב-2012 אפשר לעשות את זה טוב יותר, פנה לחבר שלו דניאל שישב בניו-יורק - ושם גם נפתחה האופרציה הראשונה. מרכז הפיתוח בתל אביב עם כ-200 מהנדסים, אופרציה בכל העולם. נגענו בכל מיני בעיות שקשורות באלגוריתמים, הגיע הזמן לחזור לזה קצת אנחנו רוצים לשמור על הלקוחות מרוצים, ושגם הנהג יהיה מרוצה, ולהתאים את הרכבים החשמליים . . . הרבה אילוצים ובעיות אופטימיזציה. למשל, עליתי על רכב - התשובה ל-”מתי אגיע ליעד?” לא ברורה לגמרי וזה רק מסתבך, כי צריך להגדיר מהו בעצם “עיקוף” - פילוסופית, אולי זו הדרך הכי טובה ואתה לא יודע וזה רק נראה כמו עיקוף, אז האם זה באמת עיקוף? זן ואומנות אחזקת האופנוע מעולם לא היה רלוונטי יותר. ונניח שהגדרנו עיקןף - מהו “עיקוף סביר”? וזה רק אתגר אחד. ועוד אחד - לאן הרכבים נוסעים כשהאגם קפוא (או סתם נגמרת הנסיעה במהלך היום)? הרכב ריק ועכשיו מה? אפשר לעמוד במקום (לא תמיד באמת אפשר); אפשר ללכת לשתות משהו; אפשר לנסות להגיע לאן שצפויים להיות בו נוסעים; ויש עוד ל-Via יש את המידע והדרך לחזות לאן לנהג כדאי לנסוע, גם כשהוא לא יודע לחזות בעצמו עוד גרסא של השאלה הזו - על הנהג להיות זמין בשעת פתיחת השירות בבוקר, אבל איפה להמתין?  נניח שיש N נקודות אפשריות (כן, הגענו לשלב הזה בשיחה), ונניח אפילו שאנחנו יודעים בדיוק איפה צפויים לעמוד הלקוחות מי שצריך הסעה ב-6:00 רוצה שהיא תיהיה שם, אין לו סבלנות לחכות (היה מעדיף אפילו להזמין קודם - ואם עשה כך אז אני יודע איפה הוא צפוי להיות) בסינגפור Via מימשה את הפי’צר הזה בדיוק אז איפה הנהג צריך לחכות על מנת להביא למינימום את משך ההמתנה הצפוי? פתרון אחר בתכנות לניארי הוא להניח יש מספר מסויים של נקודות העיר, ושאנחנו יודעים מה הזמן הצפוי להגעה מכל נקודה לכל נקודה - וסכום הזמנים של כל נסיעה שתקרה בפועל הוא משך זמן הנסיעה הצפוי וזו הפונקציה שאנחנו רוצים להביא למינימום. בעיית הסוכן הנוסע היא עדיין בעיית NP קשה, ו P<>NP נכון לזמן הקלטת הפרק, והסוכן עדיין נוסע. אולי ב-Via, אבל נוסע. יותר מזה - זה לא סוכן בודד, ויש המון תלויות בין הרכבים לנוסעים ולקשרים בינהם. אז יש לנו N רכבים ו-M נוסעים - ו-N x M משתנים - וגם הם (הנה זה בא) בוליאנים (0 או 1 - אי אפשר לאסוף חצי נוסע עם רבע רכב, וגם אם אפשר זה לא יראה טוב) - והאילוצים כולם לינאריים. ויש גם את עניין היעד שהוא גם אילוץ ויש עוד פילוסופיה - האם הממוצע עונה על הדרישה? - 100 נוסעים המתינו דקה והנוסע ה-101 המתין שעה - האם זה מצב קביל? צריך להגדיר האם זה הוגן באינטרנט מסתכלים על אחוזונים (95% מקבלים שירות טוב), וזה אפשרי גם ברמת המוצר, כשאפשר להוסיף תיקונים - אם אני יודע מראש שאני עומד לאחר אני יכול לשלוח לנוסע הודעת התנצלות, אולי עם פיצוי (“הנסיעה עלינו”, “תחזיק מעמד” וכו’) - אני יודע לטפל ולהגיב בזמן אמת  מי אמר עמוד אינטרנט שמציג ספינר כשהוא איטי? אפשר להציב חסמים ולהגיד שמעל זמן תגובה מסויים אנחנו לא מעוניים לתת את השירות כי הוא יהיה שירות לא טוב, ואנחנו בוחרים להגיד “לא” מאשר לתת שירות בכזו רמה. רגע, מכל זה - מה זה בכלל תכנות ליניארי? שיטה לפתרון בעיה שאותה ניתן לתאר באמצעות אוסף של משוואות ליניאריות (לא ראיתם את זה בא?) האילוצים מיוצגים כאי-שיוויונות לינאריים (X+Y>4, כאלה) - משוואות ממעלה גבוהה יותר יהיו הרבה יותר מסובכות לפתרון, אילוצים לינאריים יחסית קל לפתור בזמן סביר עוד משהו - הפתרון למשוואות ליניאריות לרוב יהיה רציף, ולנו יש משתנים בוליאניים (0 או 1), ולא סביר לאסוף חצי נוסע (הוא עלול להגיב לא טוב אם ננסה). אל דאגה - יש פתרון! הבעיה הזו שקולה לקבוצת בעיות הידועה בשם Transportation Problems דווקא לא בהקשר של תחבורה אלא יותר של הובלת מסעות וכאן יש תכונה (של מטריצות) שמכונה יוני-מודולאריות (Unimodular) - ובלי להיכנס יותר מדי ל-PTSD מאלגברה א’ זה מבטיח שהתוצאה תיהיה גם בשלמים. כן, זה עובד. האם הבעיה נפתרת בכל פעם מחדש, או שבכל עיר נקודות האיסוף קבועות פחות או יותר? את הבעיה אנחנו פותרים כל הזמן, וזו נגזרת של בעיית ה-”לאן הרכבים נוסעים כשהם מתרוקנים?” שהזכרנו קודם בהינתן שאנחנו יודעים מהי התמונה הכוללת של היצע וביקוש, אפשר ליצור מערכת אופטימלית ברמת המכלול. כשיש שירותים שפעילים 24/7 זה פחות רלוונטי, אבל כשיש שעת התחלה וסיום זה בדיוק מה ש-Via עושים. מה לגבי חוסר איזון? בבוקר יש תנועה מהעיר אל איזורי התעסוקה, עד ש”העיר ריקה ממכוניות” וכולם יסיימו את הנסיעה באיזורי התעסוקה. ובערב הפוך . . . בהנחה שכולם משתמשים ב-Via, אפשר לחכות במקום . . . מעבר לזה זה כבר איזון של השוק. המערכת מתפתחת לענות על אתגרים של היצע וביקוש הרבה יותר נוסעים מעדיפים את השירות דווקא בערב - בבוקר התנועה יחסית קבועה בשעה קבועה, אבל אחרי העבודה מגוון האפשרויות הרבה יותר גדול, והתועלת של שירות כמו Via גדלה. מתי נסיעה מסתיימת? כשכולם יורדים, כולם הגיעו לעבודה ואף אחד עדיין לא רוצה לחזור המערכת מפנה את הרכב למקום שבו צפוי הביקוש הבא (בהתאם למערכת כולה) כשיש רכב אוטונומי, הנסיעה אף פעם לא נגמרת - מתקיים עכשיו ניסוי באוסטרליה שבו Via בוחנת בדיוק את זה השלב הבא - נוסעים אוטונומיים שיסעו ברכבים עם נהגים אמיתיים? איך מבטיחים הוגנות לנהג? ובכן - מתייחסים אליהם כאל לקוחות . . . הנוסע מחכה 3 דקות ונוסע עוד 20 דקות, בעוד שהנהג הוא הפנים של השירות כל הזמן מובילים אותו לנקודת מנוחה כשצריך, מספקים תמריצים לעבודה טובה וכו’ (השכר שונה בהתאם לביצוע). האם קורה שנהגים חורגים מהמסלול? כן . . . יש בקרה ותגמול, וחישוב מסלול מחדש כשצריך חשוב שהנהג יעקוב אחרי המסלול כפי שנקבע, כי אפליקציה כמו Waze למשל תנחה אותו למסלול הקצר ביותר, בעוד Via תחפש מסלול אולי קצת יותר ארוך אבל עם סיכוי לאסוף עוד נוסעים יש גם התחשבות באירועים נקודתיים (הסתיים קונצרט והדרך כבר לא כל כך קצרה וכו’) ועוד נקודה - לא בבהכרח צריך להגיע לנקודה המדוייקת: אפשר להגיד לנוסע לרדת וללכת ברגל את 50 המטרים האחרונים, ולא להשקיע עוד 20 דקות בלהקיף את הבלוק או להיתקע בפקק כדי להיכנס לרחוב חד-סטרי מהכיוון הנכון כדי להגיע לנקודה המדוייקת. עוד נושאים לסיום? מתרגשים מכך שהשירות מגיע לישראל (גם כאן) - מרכז הפיתוח יוכל להרגיש את המוצר באופן יומיומי ב-Via מגייסים - מפתחים, אלגוריתמאיות, Data Scientists . . . הפתרון האידיאלי - לצאת לפריפריה! הכי טוב :-) הקובץ נמצא כאן, האזנה נעימה ותודה רבה לעופר פורר על התמלול