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

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

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

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

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

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

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

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

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

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

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

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

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

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

נכתב בשיתוף רשות החדשנות

מקורות

[1] אלגוריתם דייקסטרה

[2] פקקים

[3] פרדוקס בנס

[4] ביג דאטה