共乘系統之轉乘路徑規劃方法

共乘主要目的在於尋找相同旅遊需求的駕駛與乘客，讓駕駛可以載乘客抵達各自的目的地，而乘客則補貼駕駛部分花費，使雙方既節省旅途開支，又減少路上行駛的車輛。目前大部分的共乘系統限定駕駛路線必須包含乘客的起終點，然而實際的情況未必如此恰巧，人們因而失去共乘的機會。本論文提出於共乘系統中加入轉乘的機制，使乘客更容易經由共乘到達目的地，也盡量填滿駕駛路線上的空位。我們允許乘客選擇以最短時間或最少金額的轉乘路徑為目標，除了提出搜尋最佳答案的方法外，我們也設計各種策略找出不錯的第一組答案，並且進一步整合為可依乘客需求提早完成之近似最佳答案的搜尋方法，實驗結果顯示整合後的方法在答案品質及執行時間之間可取得平衡。

關鍵字

轉乘路徑；合用共乘；路徑規劃

並列摘要

Ridesharing aims at finding drivers and passengers with the same traveling needs. With ridesharing, a driver can take passengers to their respective destinations and passengers can share the expense. In this way, both kinds of users save their traveling costs, and the number of vehicles on the road is also reduced. Currently most of the ridesharing systems require that the route of a driver must contain the starting point and the destination of a passenger. However, in reality they do not necessarily coincide and accordingly people lose the opportunity of ridesharing. This paper proposes to add a mechanism of multi-hop transfer into the ridesharing system such that the passengers reach their destinations more easily and the available seats on the route are occupied as more as possible. We allow a passenger to choose as the goal between the multi-hop transfer path with the shortest travel time and the path with the lowest amount of payment. In addition to the ways of searching the optimal answer, we also design various strategies for finding the first answer of good quality. They are further integrated into an approach that searches the near-optimal answer with early termination based on the needs of passengers. Experiment results show that the approach after integration can balance between the quality of answer and execution time.

並列關鍵字

Multi-hop ； Routing ； Ridesharing

參考文獻

[4] 任芬傑, “運用最短路徑演算法與動態資訊進行大眾運輸行前旅次規劃,” 國立交通大學運輸科技與管理學系碩士論文, 2009.

[8] X. Xing, T. Warden, T. Nicolai, and O. Herzog, “SMIZE: A Spontaneous Ride-Sharing System for Individual Urban Transit,” Conference on Multi-Agent System Technologies Germany, pp. 165-176, 2009.

[12] M. Hua, and J. Pei, “Probabilistic Path Queries in Road Networks: Traffic Uncertainty Aware Path Selection,” Proceedings of the 13th International Conference on Extending Database Technology, pp. 347-358, 2010.

[1] 吳沛儒, “任務型共乘接駁計程車之規劃與設計,” 逢甲大學交通工程與管理學系碩士班碩士論文, 2004.