以禁忌搜尋法求解週期性車輛途程問題

Tabu Search Heuristic for Period Vehicle Routing Problem

李俊穎(Jun-ying Lee)

指導教授 ： 邱素文

大同大學/經營設計學院/資訊經營學系所/碩士(2004年)

摘要

傳統車輛途程問題(Vehicle Routing Problem, VRP)中，車隊中的車輛從場站(depot)出發，在考慮容量與行駛距離的限制下，服務顧客後並返回場站，其求解目標是希望能在滿足所有顧客需求的前提之下，設計出成本最小的最佳配送路徑。本研究所探討的週期性車輛途程問題(Period Vehicle Routing Problem, PVRP)，除了與傳統車輛途程問題擁有相同的限制與目標外，還加入了週期性配送的概念，因此在考慮車輛途程的同時，也必須分配服務顧客的時間，解題複雜度較傳統的車輛途程問題更高。
車輛途程問題的求解複雜度屬於NP-hard，若想得到大型車輛途程問題的最佳路徑，需要花費極高的成本與時間，因此近年來多數研究皆致力於發展啟發式演算法求解車輛途程問題，以期能在有限的成本與時間下，找出最佳路徑或近似最佳路徑。由於一般啟發式演算法容易發生無法跳脫局部最佳解的情形，造成求解效率有餘，而求解品質低落的情形，因此本論文在求解複雜的週期性車輛途程問題時，加入禁忌搜尋法的概念，希望能兼顧求解效率與品質。本論文利用Linear programming 以及Savings演算法進行初始路徑的求解，再以初始路徑為基礎，使用Modified One-point movement演算法尋求更低成本的改善解，並在求取改善解的同時，導入禁忌搜尋法，利用禁忌搜尋法的特性，改善傳統啟發式演算法過早陷入區域最佳解的情形，找到更高品質的可行解。

關鍵字

車輛途程問題 ； 週期性車輛途程問題 ； 禁忌搜尋法 ； 節省法

並列摘要

The Vehicle Routing Problem (VRP) under capacity and distance restrictions involves the design of minimum cost delivery routes for a fleet of vehicles, originating and terminating at a central depot, which serves a set of customers. This thesis present Tabu search algorithm for the Period Vehicle Routing Problem, the problem not only designs vehicle routes to meet required service levels for customers but also minimize distribution costs over a given several day period of time .
The VRP belongs to the class of NP-hard problems, and polynomial time algorithms for finding optimal solutions are unlikely to exist. Hence, there have been few attempts to solve it optimally among an exact algorithm based on branch and bound procedures. The branch and bound approach address small VRP adequately up to 50 customers with 8 vehicles, the approach to solve big VRP must spend the maximum of greatest time and cost. Due to limited success of exact methods, considerable attention and research effort have been devoted to the development of efficient heuristics algorithm which can provide near optimal solutions for large-sized problems in limited time. But heuristic algorithm yielding solutions whose quality often not good enough. In this thesis, applied linear programming and Savings procedure to find an initial feasible solution of PVRP, then use Tabu search to improve the One-point movement algorithm, finding improved solutions whose quality significantly surpasses that obtained by traditional heuristics.

並列關鍵字

One-point Movement ； Period Vehicle Routing Problem(PVRP) ； Savings ； Tabu Search (TS) ； Vehicle Routing Problem (VRP)

參考文獻

1. Clarke, G.. and Wright, J. W. (1964), “Scheduling of vehicles from a central depot to a number of deliver points”, Operations Research, 12, 568-581

3. Christofides, N. and Beasley, J .E. (1984), “The period routing problem”, Networks, 14, 237-256

4. Chao, I.M., Golden, B.L. and Wasil, E. (1995), “An improved heuristic for the period vehicle routing problem”, Networks, 26, 25-44

5. Cordeau, J.F., Gendreau, M. and Laporte, G. (1997), “A Tabu search heuristic for period and multi-depot vehicle routing problems”, Networks, 30, 105-119

6. Fisher, M. L. and Jaikumar, R. (1981), “A Generalized Assignment Heuristic for Vehicle Routing”, Networks, 11, 109-124