作為 Quiki 的技術顧問，我很高興能分享我們平台最關鍵組件之一的見解：先進的搭乘配對演算法。這個複雜的系統旨在即時解決複雜的多車輛、多請求路線規劃問題，確保高效且最佳的共乘體驗。
挑戰：多車輛、多請求路線規劃#
我們的演算法解決了三個主要的共乘挑戰：
- 計算多個搭乘請求到多個具有特定容量的車輛的最佳分配。
- 允許持續運作並將新進請求分配給車隊。
- 實現車隊的重新平衡以有效滿足需求。
演算法的關鍵組件#
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）：包括最長等待時間、最長行程延遲和車輛容量。
最佳化過程#
成本函數：我們最小化成本函數 C(Σ)，該函數考慮所有乘客和已分配請求的行程延遲，加上未分配請求的懲罰。
限制條件滿足：演算法確保滿足所有限制條件，包括最長等待時間、行程延遲和車輛容量。
增量最佳化：鑑於問題的 NP-hard 性質，我們使用增量方法快速找到次優解，並可隨時間改進。
進階功能#
持續運作：演算法可以即時處理新進請求，持續更新分配。
車隊重新平衡：我們實施了一個系統，將閒置車輛重新平衡到有未處理請求的區域，最小化整體等待時間。
可擴展性：我們的方法設計為可隨車輛和請求數量的增加而有效擴展。
實際影響#
這個先進的演算法使 Quiki 能夠：
- 最大化車輛利用率並減少空車行程。
- 最小化乘客等待時間和行程延遲。
- 快速適應即時變化的需求模式。
- 提供更高效且具成本效益的共乘服務。
未來發展#
隨著我們持續改進演算法，我們正在探索幾個令人興奮的方向：
- 機器學習整合：納入預測模型以預測需求模式。
- 動態定價：基於即時供需實施浮動定價模型。
- 多模式整合：擴展演算法以納入其他交通模式，實現真正整合的都市移動解決方案。
Quiki 核心的複雜搭乘配對演算法不僅是技術奇蹟；它是解鎖更高效、可持續和用戶友好的都市交通的關鍵。隨著我們為 Quiki 的推出做準備，我們很興奮能看到這項技術如何改變人們在城市中移動的方式。
請持續關注更多更新，我們將繼續創新並推動共乘技術的可能性界限！