| 摘要: | 中型車共乘運輸系統係是針對尖峰時間道路擁擠所發展出的方案之一。然而，無論是何種操作型態，皆僅執行配對作業，並不包含路徑指引，而路徑之選擇是由駕駛人依經驗行駛，且通訊技術日新月異，傳統配對方式已不適用故中型車共乘問題實有研究之必要性。
據此，在假設顧客出現時間為不定期情形下，與共乘車輛係採用先接後送的作業方式下，本研究考慮系統使用者之時間窗限制、地理距離限制、車輛之最小與最大容量等限制下，以最小車輛旅行時間為目標，建構中型車共乘問題之數學模式。
本研究係採用靜態模式動態應用之解題方式，以定期預約需求為主，即時需求為輔，採二階段解題方法解題。第一階段為求解預約需求下之路徑規劃，利用改良式的k階均值演算法進行乘客的指派作業，再利用考量時窗限制順序之蟻群演算法或門檻接受法結合噪音擾動法進行共乘車輛的路線規劃；第二階段為求解即時需求下之路徑規劃，利用新需求位置距各駕駛者位置的距離遠近，判斷接送新需求的共乘車輛，並利用插入法將新需求者插入路線中，再利用1-1節點交換與門檻接受法改善共乘車輛路徑。
在測試例題部分，就預約需求而言，利用叢聚、均勻，以及走廊型的節點位置佈設的測試例題，就即時需求而言，採5個固定節點位置，並依均勻分佈、常態分佈，以及卜氏分布的節點出現時間的測試例題，用以測試、分析演算法的解題績效。
案例測試結果發現：在預約需求下，無論在解題績效或速度上，蟻群搜尋法皆較門檻接受法結合噪音擾動法為優；證實參數不具有轉移性；適當的增加車隊規模有助於降低系統總旅行時間與個人旅行時間；系統內績效值並不會因目標式改變而有顯著改變。在即時需求下，解題時間皆在30秒內，且以乘客出現時間呈卜氏分配之績效值表現最為優異。
With vanpooling emerging as a viable potential policy for reducing private car in congested area, the vigorous study on the vanpooling problem is critical for its success. However, in the current practice, the supervisors of the vanpool program usually focus on the assignment of the patronages to the vans, but not on the routes taken. In practice, the routes are determined by driver’s experiences. With the rapid development in communication technology, we should be able to perform the van pooling program more effectively with these techniques.
To deal with the vanpooling program in this paper, we assume the customer appearance is uncertain, and the basic principle of the vanpooling’s operation is pick-up first drop-off second. With the constraints of the customer’s time and distance, and the maximum and minimum van capacity, the purpose of this study is to determine a set of m minimum travel time vehicle routes capable of accommodating as many users as possible, under these constraints.
A static solution procedure is developed in this study with preset demand as core, and some real time demand will be served too. A two-phase solution procedure is adopted in the study. In the first phase, route structure is determined based on the preset demand. A revised ant colony optimization (ACO) and the meta-heuristic of combining the threshold accepting and noising method (TA&NM) are used to construct the route structure. For the real time demands, based on their locations and the existing set of routes, a threshold accepting method (TA) is adopted to adjust the current set of routes to serve these demands in the second phase. With the incorporation of these meta-heuristics, the proposed solution procedure should provide a robust route structure and patronage assignment for the vanpooling program. .
A series of case studies with different characteristics such as demand density, demand size were used to test the solution capability of the proposed algorithms. Several versions of revised algorithms were developed in these studies. Based on the result of the case studies, an ACO was identified as the most suitable solution procedure for the problem addressed in this study. The proposed procedure can be used to develop a suitable vanpool problem with real-time demand information. |
