考量旅行時間可靠度之車輛途程問題─螞蟻族群演算法之應用

Abstract

由於路網往往受到交通阻塞、違規停車或意外事故等因素影響，因此旅行時間並非是恆定不變的，故有學者開始研究考量隨機旅行時間之車輛途程問題。然而，考量隨機旅行時間車輛途程模式只能得到單一最佳路徑，無法有效反應規劃者需求，故本研究乃導入可靠度工程理論觀念，將路段旅行時間之不確定性轉換為「時窗可靠度」的概念，再結合傳統車輛途程模式，構建一「模糊多目標的車輛途程可靠度模式」，求解總旅行成本最小及總服務失敗機率最小(可靠度最大)之最佳路徑。鑑於螞蟻族群演算法(Ant Colony System)在VRP 相關問題求解績效已獲得驗證，故本研究亦採用此演算法求解本研究模式。 本研究乃以小規模路網與大規模路網測試本研究模式：小規模路網乃是由10 個節點所組成，當同時以本研究模式與軟時窗之車輛途程模式求解小規模路網，發現本模式所求得的路徑，其服務失敗機率為5.8%，而軟時窗模式之服務失敗機率則為0.33%，表示本模式結果能提供較可靠之指派路徑。同時由敏感度分析可知，(1)當要求之時窗可靠度水準增加，指派路徑會改變以提供更好的服務，而總旅行成本會隨之增加；(2)當個別顧客之時窗可靠度水準提高時，指派路徑會改變以提高其時窗可靠度；(3)當路段之旅行時間標準差變大時，會導至原路徑的旅行成本提高而使得指派路徑發生改變，以尋求準確性更高的路段。大規模路網乃是採用Solomon 所提出的R111 標竿範例，研究發現本研究模式可依不同之時窗可靠度水準，提供其最佳之路徑。

Since the traffic conditions are affected by many factors such as congestion, illegal parking and incidents, travel time on urban network is often uncertain. The uncertainty of travel time begins to be taken into consideration by some researches on vehicle routing problems. That’s so called stochastic vehicle routing problems (SVRP). However, SVRP could only provide an optimal route without further considering the different degree of punctuality required by different customers. Based on the theory of reliability engineering, this research proposes a vehicle routing model with time - window reliability (RTW- VRP) to find an optimal route which has the minimum travel cost and the minimum service failure (i.e. the maximum reliability). Besides, due to the proven excellent performance of Ant Colony System (ACS) in solving vehicle routing problems, this study employs ACS algorithm to solve RTW- VRP. Two examples, one small- scale network with 10 nodes and another large-scale network with 100 nodes (the Solomon’s R111 example), are experimented to validate the RTW- VRP model. The results of small-scale network show that the probabilit ies of service failure for the proposed RTW- VRP model and VRP model with soft time window (STW- VRP) are 5.8% and 30.33%, respectively. It implies that RTW- VRP model can provide a more reliable route. The results of sensitivity analysis also indicate that the model will provide an optimal route with better service reliability as the required reliability level getting stricter and an optimal route with more stable travel time as variance of travel time enlarging. The results of large-scale network also demonstrate that the RTW- VRP model can provide appropriate routes for different required reliability level.