Applying Ant Colony Optimization in Solving Vehicle Routing Problem with Stochastic Travel Times

[[abstract]]傳統的車輛途程問題Vehicle Routing Problem(VRP)屬於網路最佳化問題之一。VRP目的是滿足顧客的需求，並在條件限制下，將達到成本最小化或利潤最大化等目的。而本研究將車輛途程問題中的旅行時間設定為隨機旅行時間，係指物流業者在運送旅途中將面臨速限限制以及車潮等符合現實生活中運送時間難以掌控的相關困難點，因此，本研究將路況的不確定性及車潮眾多之時間點條件納入研究中的限制條件。??本研究將依顧客所指定時間將物品準確送達至顧客端時間點，為考量真實生活中物流業者在旅程過程中，每趟旅程行時間會依照實際交通量而有所不同，建置一套車輛路徑規劃系統，配送時間設定為八小時，八小時加以細分為五個時區，而每時區會因不同時段之交通量造成旅行時間的改變，故影響配送路線的規劃。本研究以蟻群演算法之架構，考慮在每趟收送貨過程中可能會因路況的不確定性因而延誤服務顧客，而產生懲罰成本，故本研究將期望懲罰參數γ設定為本研究的主要變數，(α,β)則參考以往文獻所提出的最佳解為(1,2)，運算每趟旅程成本及時間，計算結果發現(α,β)為(1,2)，γ=3會產生較多組最佳解，其中又以範例C204為最佳解案例，另外再將範例C204設定為傳統車輛路徑問題求解，將兩者所產生的結果相互比較。本研究結果係為更貼近現實生活中物流業者在配送過程中所可能產生的問題，故可提供給業界做為實際車輛路徑規劃參考。[[abstract]]A carrier has difficulties on controlling the delivery time because of complex and dynamic traffic conditions. It is essential to take the uncertainty of the traffic into account so that the vehicle dispatching can be well planned.??The time window constraint for each customer is considered in this research.?The travel time of one link is varying because of various traffic flow. The delivery time is set to be 8 hours, which is divided into 5 time zones in this research. Each time zone has a different travel time function for each link. This function is used to calculate the link travel time for different entering time.The Ant Colony Optimization method is employed to solve this VRP with dynamic link travel time. A parameter γ is set to reflect the influence of uncertainty of traffic during distributing and will be used to help in improving the routing process. The output results indicated that the solving process can yield a good solution while (α,β) is equal to (1, 2) and γ=3. The contribution of this study is to take the traffic situation into consideration and figure out how the dispatching can response for that. It is expected to be a valuable reference of the practical vehicle route planning for the industry