以巨集啟發式演算法求解即時資訊下之中型車共乘問題

A Study on the Meta-Heuristic Solution Method for the Van Pooling Problem with Real Time Information

楊淑芳(Shu-Fang Yang)

指導教授 ： 邱顯明

淡江大學/管理學院/運輸管理學系碩士班/碩士(2006年)

https://doi.org/10.6846/TKU.2006.00281

摘要

中型車共乘運輸系統係是針對尖峰時間道路擁擠所發展出的方案之一。然而，無論是何種操作型態，皆僅執行配對作業，並不包含路徑指引，而路徑之選擇是由駕駛人依經驗行駛，且通訊技術日新月異，傳統配對方式已不適用故中型車共乘問題實有研究之必要性。
據此，在假設顧客出現時間為不定期情形下，與共乘車輛係採用先接後送的作業方式下，本研究考慮系統使用者之時間窗限制、地理距離限制、車輛之最小與最大容量等限制下，以最小車輛旅行時間為目標，建構中型車共乘問題之數學模式。
本研究係採用靜態模式動態應用之解題方式，以定期預約需求為主，即時需求為輔，採二階段解題方法解題。第一階段為求解預約需求下之路徑規劃，利用改良式的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.

並列關鍵字

Meta-Heuristic Solution Method ； Real-Time Information ； Van pool

參考文獻

23. 彭百君，中原大學 電機工程學系碩士論文，「直接空調負載控制曲線自動化分類系統」，中華民國93年7月。

25. 馮正民、邱裕鈞，「研究方法分析」，建都文化事業股份有限公司，中華民國93年6月。

16. 許晉嘉，國立成功大學 交通管理科學研究所碩士論文，「宅配業貨物配送路線規劃問題之研究」，中華民國92年。

30. 羅敏華，私立元智大學 工業工程與管理研究所，「蟻群最佳化演算法於載重限制車輛途程問題的研究」，中華民國92年7月。

33. Bernhard Fleischmann, Stefan Gnutzmann, Elke Sandvoβ(2004), “Dynamic Vehicle Routing Based on Online Traffic Information”, Transportation Science, Vol. 38, No.4, pp.420-433.