מתחת למכסה המנוע: אלגוריתם התאמת הנסיעות המתקדם של Quiki

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

האתגר: ניתוב מרובה כלי רכב ומרובה בקשות

#

האלגוריתם שלנו מתמודד עם שלושה אתגרים עיקריים בשיתוף נסיעות:

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

מרכיבים עיקריים של האלגוריתם

#

1. גרף בקשה-רכב (RV) זוגי

#

השלב הראשון כולל חישוב:

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

2. גרף בקשה-נסיעה-רכב (RTV)

#

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

3. הקצאה אופטימלית

#

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

המודל המתמטי

#

האלגוריתם שלנו משתמש במודל מתמטי מתוחכם כדי לייצג את בעיית שיתוף הנסיעות:

• בקשות (R): כל בקשה r מוגדרת על ידי מוצא (o_r), יעד (d_r), זמן בקשה (t_r^r), וזמן איסוף מאוחר ביותר מקובל (t_r^pl).
• כלי רכב (V): כל רכב v מאופיין על ידי מיקומו הנוכחי (q_v), הזמן הנוכחי (t_v), והנוסעים הנוכחיים (P_v).
• אילוצים (Z): כוללים זמן המתנה מקסימלי, עיכוב נסיעה מקסימלי, וקיבולת רכב.

תהליך האופטימיזציה

#

1. פונקציית עלות: אנו ממזערים פונקציית עלות C(Σ) המתחשבת בעיכובי נסיעה עבור כל הנוסעים והבקשות המוקצות, בתוספת קנס עבור בקשות שלא הוקצו.

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

3. אופטימיזציה הדרגתית: בהינתן האופי ה-NP-קשה של הבעיה, אנו משתמשים בגישה הדרגתית למציאת פתרונות תת-אופטימליים במהירות, אותם ניתן לשפר עם הזמן.

תכונות מתקדמות

#

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

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

3. יכולת הרחבה: הגישה שלנו מתוכננת להתרחב ביעילות עם מספר גדל של כלי רכב ובקשות.

השפעה בעולם האמיתי

#

אלגוריתם מתקדם זה מאפשר ל-Quiki:

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

פיתוחים עתידיים

#

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

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

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

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