多群轉乘的合夥用車系統

Abstract

交通運輸和上下班通勤已經成為我們日常生活中不可或缺的一部份。個人駕駛私人用車，由於時間容易掌握，且路線可由自己決定，是最常被人們使用的移動方式。也因為如此，車輛總數不斷上升，並讓交通問題日益嚴重。大眾運輸系統是一種解決上述問題的手段。但不幸的是，它並無法提供多樣化的路線自由和彈性，也沒辦法像私用車一樣舒服，甚至會有誤點的可能。合夥用車是一個創新的傳輸概念，利用駕駛和多個乘客分享私用車，減低車輛的使用數目，提高使用效率。它同時有著個人駕駛的路線彈性，又有大眾運輸系統解決交通管理問題的能力，故近幾年出現越來越多合夥用車的服務平台。但這些平台都有著根本上的一些限制，包括使用者要依據相同目的地分群、且用戶需要有駕照或者車子。這些限制使得某些用戶進入規劃系統後，沒有辦法被分配到已存在的合夥用車群集內，形成孤立用戶，必須自行開車。故在此篇論文中，我們針對未分到群集內的孤立用戶，提出一個進一步處理的方法，盡可能的讓所有使用者都能夠受益。作法是透過幾何上的費馬點問題，規劃出中繼點，並利用自訂的配對成本函式找出一個中繼群，中繼群將孤立用戶先載到此中繼點，再利用一個有相同目的地的目標群將此孤立點載到終點。透過效能分析跟實驗模擬，我們證明我們的方法能夠進一步的降低總運輸成本和車輛使用數量。最後，我們將此實作成一個Web服務系統，在此系統中，使用者可以依照喜好輸入起終點和出席日。系統接收到需求後，會到已建立的使用者和群集資料庫內搜尋是否有適合此用戶的合夥用車群集，並將使用旅行商問題演算法規劃後的路徑回傳給此用戶。

Daily commute has become an integral part of our lives. Due to convenience and time saving, driving a personal car is the most common way people use to commute. Consequently, the number of vehicles rapidly increases, which create severe traffic congestion problem in major cities around the world. Public transportation system, however can ease the pain for the drivers stuck in the traffic. Nevertheless, it’s not as timing, flexible and comfort as one's own car. Carpooling is an innovative transport services which reduce the number of vehicle usage by sharing use of a private car with other passengers. Carpooling not only has variety routes to choose for users, but also can relieve severe traffic congestion. As a result, more and more carpooling service platforms available recently. However, carpooling has some fundamental constraints, such as limit number of passengers, and carpooling cost function. These constraints cause some users could not join any carpooling group and need to drive alone. In this paper, we focus on these isolate users and try to design a further scheduling algorithm to reduce the number of isolate users. We propose that an isolate driver could moves to a destination by joining a carpool to a preselected transfer point, then taking another carpool to the destination. In other words, an isolate driver moves to destination by multi-pool transferring. We find a transfer point by mapping real world coordinate points to Fermat point problem, and find a transfer carpool and a target carpool by our cost function. We prove that our algorithm can reduce total traveling cost and the number of vehicles used through simulation. Finally, we implement our method into a Web-based carpool service system. Users can send their requests including their sources, destinations and schedules though our web interface. Our carpool system will check database to find a carpool, and return the routes which are scheduled by well-known travelling salesman algorithm to user.