應用塔布搜尋法於含軟性時窗限制之動態需求撿取配送途程規劃問題

Solving the Dynamic Pickup and Delivery Problem with Soft Time Windows using Tabu Search

盧步雲(Pu-Yun Lu)

指導教授 ： 王福琨 ； 杜志挺

中原大學/工學院/工業工程研究所/碩士(2002年)

https://doi.org/10.6840/cycu200200332

摘要

近年來由於通訊技術的進步，使得動態車輛途程系統的即時資訊取得更加容易，加之網路技術的進步，決策的反應速度需求愈來愈快，需要動態模式提供較佳的反應速度。文獻上已有很多關於車輛途程問題的研究，但是大部份的研究是針對輸入資料事先已知的靜態問題。本論文中針對一個含軟性時窗之動態撿取配送問題加以研究分析。撿取配送問題是指在不能違反容量和時窗的限制下，以數輛車來滿足一些顧客的撿取或配送的需求。本論文調整一個解靜態途程的塔布演算法，來解動態問題。為了快速回應的需求，提出一個階段式求解法來解決含軟性時窗之動態撿取配送問題。以模擬的方法探討軟性時窗和硬性時窗之績效，和有無使用塔布演算法之差別。為了證實本研究解法之效率，模擬資料是以Solomon的基本測試例題來產生。最後實驗結果証實本研究之二階段解法是有效的。

關鍵字

塔布搜尋法 ； 動態車輛途程問題 ； 軟性時窗

並列摘要

Recently, the improvement of both telecommunication and network technologies require quick respond toward the vehicle dispatching decision-making. In the past, the studies vehicle routing problems mainly focused on the static problems instead of dynamic problems. However, the new trend has moved the focal points from the static to the dynamic arena. Some profound studies using general heuristic algorithms, such Tabu search in solving dynamic vehicle problems (DVRP). This study first argues that although the approach can produce satisfactory results most of time, the general heuristics, by natural, cannot respond to the fast change environment well. Therefore, this study proposes a stepwise approach including simply heuristics, such Insertion algorithm, K-opt algorithm and Best Fit algorithm, and general heuristic, e.g. Tabu search. In the stepwise approach, the simple heuristics react the change quickly while the general heuristic is responsible for improving the solution when needed. The momentum value caused by the event change will determine when is the time Tabu search should be triggered. The standard problem form Solomon will be used for illustration.

並列關鍵字

Soft Time Windows ； Dynamic Vehicle Routing Problem ； Tabu Search

參考文獻

Baker, E., 1983, An Exact Algorithm for the Time Constrained Traveling Salesman Problem. Operations Research, 31, 938-945.

Barbarosoglu, G. and Ozgur, D., 1999, A tabu search algorithms for the vehicle routing problem. Computers & Operations Research , 26 , 255-270.

Bertsimas, D.J. and van Ryzin, G., 1991, A stochastic and dynamic vehicle routing problem in the Euclidean plane. Operations Research, 39, 601-615.

Bertsimas, D. J. and van Ryzin, G., 1993, Stochastic and dynamic vehicle routing in the Euclidian plane with multiple capacitated vehicles. Operations Research, 41, 60-76.

Clarke, G. and Wright, W.J., 1964, Scheduling of vehicles from a central depot to a number of delivery points. Operation Research, 12, 568-581.