應用VNS演算法求解撥召服務結合貨物運送之研究

Abstract

隨著人口結構的改變，我國已從高齡化社會正式進入高齡社會，並將在2026年邁入超高齡社會。因此政府積極推動「長期照顧計畫2.0」以因應逐年增加的長照需求，其中長照交通接送則為提供年長者在就醫、復健之撥召運輸服務。該長照運輸服務的特色是車輛路線與班表具有一定的彈性，且需求皆有時窗的限制以確保服務品質。本研究以長照交通接送服務為研究對象，依據撥召運輸特性，並考量民眾生活日常需求，引入客貨混載營運模式，建構撥召服務結合貨物運送之途程問題模型，在最小營運成本目標並有一定服務品質條件下，求解最小派遣車輛數。 本研究在求解大規模問題時是應用VNS演算法，共設計六種鄰域結構，並加入模擬退火演算法之劣解接受機制來增加求解的廣度。研究中首先建立兩個模擬案例，用以驗證本研究VNS演算法求得的解與精確解間之誤差能控制於5%內。實例分析的部分是以台中市區與梨山偏鄉作為驗證案例，並收集實際一週需求資料進行車輛派遣的規劃，結果顯示VNS演算法多能在3分鐘內完成求解；本研究進一步比較「客貨混載」與「客貨分載」模式的績效，客貨混載模式在營運成本、共乘率與派遣車輛數等面向皆優於單一客載模式。整體而言，研究分析結果顯示本研究建立之客貨混載模型及其求解方法能夠有效協助長照車隊之途程規劃，提升車輛有限運能與營運效率，增加長照行動服務之社會福祉。

With the change of population structure, Taiwan has formally entered the aging society, and will enter the super-aged society in 2026. Therefore, the government has implemented Long-Term Care Plan 2.0 to respond to the increasing demand for long-term care in recent years. Long-Term Care Transportation Service provides the elderly with medical treatment or rehabilitation transportation service. Its service features consisted of flexibility on the routing and scheduling, and the service quality is ensured by the time window. This study aims on long-term care bus with considering the full functions of medicine care and daily living needs. According to the dial-a-ride characteristics and the combined passenger-cargo operation mode, a combined passenger-cargo dial-a-ride problem model is developed with the objective of minimizing fleet size under the minimum operating cost and specific service quality. In this study, VNS algorithm applied for the optimization model, a total of six neighborhood structures are designed, and the poor solution acceptance mechanism of SA algorithm is also established. Two simulation cases are established to verify the differences between VNS algorithm and exact solution can be controlled within 5%. The part of the case study, one week is used as the verification length in Taichung City and Lishan. The results show that VNS algorithm can solve the problems within 3 minutes. This study further explores the combined passenger-cargo mode, and the results show that the combined passenger-cargo mode is superior to the original mode in terms of total cost, carpooling rate, and the number of vehicles. It has been shown that combined passenger-cargo mode and the method established in this study can effectively assist the vehicle fleet planning, improve the utilization of vehicle capacity, and also increase the social welfare.