禁制搜尋法於軟性時窗限制之車輛途程問題研究

A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Window Constraints

敖君瑋(Chun-Wei Ao)

指導教授 ： 胡黃德

元智大學/工程學院/工業工程與管理學系/碩士(1998年)

摘要

物流中心在商品流通的過程中，為滿足客戶的配送需求及追求合理的運輸成本，必須快速地做出最佳配送路線的決策。以往時窗限制之車輛途程問題，只需考慮車輛的載重、全程時間以及各顧客點時窗的限制，以最小的運輸成本來安排車輛配送的路徑。然而在交通流量愈來愈大的今日，商品於時窗限制內準時配送將愈來愈難，因此將違反時窗限制的拒收處分，以合理的處罰成本取而代之，即為軟性時窗限制之車輛途程問題。本研究針對軟性時窗限制的考量，並利用最鄰近法、掃描法及節省法來求得初始解，再以數種不同搜尋規則之禁制搜尋法來改善初始解。最後本研究利用Solomon之車輛途程硬性時窗的題庫 (Solomon, 1987) 進行測試，以三種初始解利用禁制搜尋法改善後，發現以最鄰近法所建構的初始途程經改善後最佳。同時，以所得之最佳解與歷年來使用相同題庫所出版的最佳解相互比較，結果發現本研究對於題型R2及RC2的改善有較佳的結果。

關鍵字

禁制搜尋法 ； 時窗 ； 車輛途程問題

並列摘要

The distribution center has to make optimal daily vehicle routing decisions to satisfy the customers’ demands and search for the reasonable transportation cost during the business flow process. Previous vehicle routing problem with time windows (VRPTW) only considers the vehicle capacity, total available time and customer’s time window constraints, and the search for the best vehicle routing decisions is based on the minimum transportation cost. However, as the traffic flow grows, the on-time delivery is getting difficult to achieve under the time constraints. Hence, the vehicle routing problem with soft time windows (VRPSTW) emerges as the penalty cost approach substitutes the reject acceptance, which violates the time window constraints. This study dealt with the VRPSTW, and utilized nearest-neighbor, sweep, and saving methods to find the initial solution. Then, the tabu search rules were utilized to improve the initial solutions. The approach was tested by the data sets of Solomon’s (1987) vehicle routing problem. The results show that the use of nearest-neighbor method as initial solution performs best in getting the best improved solutions. This approach also performs best in data sets of R2 and RC2 then previous solution.

並列關鍵字

Tabu Search ； Time Window ； Vehicle Routing Problems

參考文獻

廖亮富，「含時窗限制多部車車輛途程問題解算之研究」，元智大學工業工程所，碩士論文，1998.

Balakrishnan, N., “Simple Heuristics for the Vehicle Routeing Problem with Soft Time Windows”, Journal of the Operational Research Society, 1993, Vol. 44, pp. 297-287.

Beasley, J., “Route First-Cluster Second Methods for Vehicle Routing”, Omega, Vol. 118, pp. 403-408.

Bowerman, R., P. Calamai and G. Hall, “The Spacefilling Curve with Optimal Partitioning Heuristic for the Vehicle Routing Problem,” European Journal of Operational Research, 1994, Vol. 76., pp.128-142.

Clark, G. and J. Wright, “Scheduling of Vehicles from a Central Depot to Number of Delivery Points”, Operation Research, 1964, Vol. 12, pp. 568-581.