摘要
共乘機制在今日被視為一個能有效減少能源消耗與碳排放的策略，而且使人們可以與他人分攤旅途花費；目前大多數的共乘系統僅提供使用者一份共乘候選者的清單，費時的談判經常降低一般人參與共乘的意願。我們提出了一個根據路線和計價方案將使用者分為共乘組合的新穎作法，按照我們採用的計價方案，相同旅途的同車乘客和駕駛將要一起平均分攤旅途的花費，從一名駕駛的觀點，我們的目標是找到一群乘客使駕駛所得到的分攤費用最多。為了線上系統所需的迅速回應，我們的作法著眼於找出近似最佳的共乘組合，意即盡量填滿整條路線上座位的一群乘客。基於各種不同的參數設定，並以駕駛所節省的花費總計作為衡量標準，實驗結果顯示我們的作法與先前方法相比，在效率上雖然略遜一籌，卻能得到品質較佳的答案。
並列摘要
Ridesharing has the great opportunity to reduce the consumption of energy and the emission of harmful gases, and to let people share the traffic costs with others. Most of the current ridesharing systems simply provide a number of candidates for users to choose. Time-consuming negotiation often discourages people from ridesharing. We propose a novel approach that assigns users to form ridesharing groups according to their routes and payments. Under our payment scheme, the passengers who share rides on the same route will equally share the expense with the driver. Given a driver, our goal is to find a group of passengers who will pay the driver the most. For the prompt response to an online system, our approach aims for the near-optimal group, where the available seats on the entire route are occupied by passengers as many as possible. Compared with the previous methods, the experiment results show that our approach incurs a little overhead but obtains answers of better quality, measured by the total saving of the driver, under various parameter settings.