動態共乘之兩階段乘客搜尋架構

Two-phase Passenger Search Framework for Dynamic Ridesharing

黃御涵(Yu-Han Huang)

指導教授 ： 吳宜鴻

中原大學/電機資訊學院/資訊工程研究所/碩士(2015年)

https://doi.org/10.6840/cycu201500603

摘要

現今在道路上的車輛以自用客車居多，但其乘客佔位數並不高，不僅造成交通壅塞及空氣汙染的問題，也徒增車輛駕駛的支出費用。在環保與經濟的雙重需求下，共乘是一個有效減輕負擔的解決之道。智慧型行動裝置的普及有助於實現共乘，近年來國內外開始出現透過行動裝置進行共乘的應用系統及研究分析，顯示此一主題的發展潛力。本論文以輔助駕駛快速搜尋乘客為主要目標，在駕駛開始行程後，持續搜尋適合共乘的對象，並以浮動分攤計價的方式計算每位乘客和駕駛各自應該支付的費用，前提是駕駛和乘客支出均不得超過各自的原始成本，讓兩者皆有所獲。搜尋程序規劃為每次幫一位駕駛找一位最適合共乘的對象，配對共乘之後便在乘客上車或下車點繼續搜尋下一位乘客；一旦搜尋失敗，便立即結束搜尋程序。實驗顯示，我們的方法比暴力法更快速找到乘客，仍能保證駕駛和乘客支出不會超過原始成本，而且平均載客數和平均節省成本都近似於費時的暴力法；此外，分析整個系統的總排碳量節省比例，我們的方法只花費比較短的時間，表現就和暴力法在伯仲之間。

關鍵字

動態共乘 ； 乘客搜尋 ； 浮動分攤計價

並列摘要

Nowadays most of the motor vehicles on roads are private cars and the number of occupied seats on each car is not high. It results in not only the overheads of traffic jam and air pollution but also the increase of driver costs. From the aspects of environment protection and economics, ridesharing is an effective way to reduce both overheads. The prevalence of intelligent mobile devices helps the promotion of ridesharing services. In recent years ridesharing systems based on mobile devices and related studies have been started to demonstrate the potential of this subject. This thesis mainly aims at helping drivers quickly find their passengers. After the driver starts a trip, the proposed approach continuously searches proper candidates for ridesharing and calculate the cost for each participant based on the floating-share payment scheme. The constraint is that drivers and passengers cannot pay more than their original costs and both receive profits in ridesharing. The procedure attempts to find one best passenger for every driver. As the passenger gets on or gets off the car, the search of the next passenger immediately starts. On the other hand, the procedure immediately stops if nothing is found. Experiments show that our approach is faster than the brute-force approach under the cost constraint. Moreover, on the number of ridesharing participants and the saving of driver costs our approach is close to the time-consuming approach. In addition, on the saving of total carbon emissions, our time-saving approach compares closely with the brute-force approach.

並列關鍵字

dynamic ridesharing ； passenger search ； floating-share payment

參考文獻

[2]余泉慶，「共乘系統之轉乘路徑規劃方法」，碩士論文，中原大學資訊工程所，2011.

[3]周宛儒，「週期共乘之索引及配對技術」，碩士論文，中原大學資訊工程所，2012.

[5]陳泓翰，「合理計費機制之汽車共乘系統及乘客搜尋技術」，碩士論文，中原大學資訊工程所，2010.

[8]鐘政達，「動態共乘系統之乘客搜尋」，碩士論文，中原大學通訊工程碩士學位學程，2013.

[9]嚴傑，「共乘系統之乘客搜尋技術」，碩士論文，中原大學資訊工程所，2011