含時窗限制多部車車輛途程問題解算之研究

The Research of the Solution of Multi-Vehicle Routing Problems with Time Windows

廖亮富(Liang-Fu Liao)

指導教授 ： 徐旭昇 博士

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

摘要

車輛途程問題（VRP）屬於NP-Hard問題，而此類型之問題在找尋最佳
解之情況下，必須花費十分冗長的運算時間；因此，為了要迅速得到與最
佳解差異不大的近似解，一般都會採用啟發法來求解。本研究將同時考慮
任務節點及任務網枝，並於車輛行走時有總時間之限制，而任務節點及任
務網枝有個別時窗之限制；如此之考慮條件，可使得本研究更加符合實際
車輛途程之應用。

本研究之啟發式解算，可分為兩個階段：初始解及尋優改善。初始解
以「最鄰近法」及「掃描法」求得，尋優改善以「塔布搜尋法」求得，如
此便可得到一個的近似解；在尋優改善時，並提出數種交換法（如：swap
、2-opt* exchange及insert），針對任務來進行交換改善之比較。最後
本研究之啟發解與「門檻值接受法」所求得之結果，並且以「幹枝界限法
」求得一個下限解做為基準相互比較，以瞭解本研究之實際成效。

關鍵字

車輛途程問題 ； 最鄰近法 ； 掃瞄法 ； 塔布搜尋法 ； 交換法 ； 幹枝界限法 ； 門檻值接受法

並列摘要

The vehicle routing problem (VRP) is a kind of NP-Hard problem.It
takes a lot of operational time to find optimal solutions of VRP.
All known algorithms for solving these problems require a number
of computations which grow exponentially with the size of the
problem. Therefore most of the research into solving vehicle
routing problems has been concerned with finding heuristics that
provide good solutions to the VRP. In this paper we consider the
Multi-Vehicle Routing Problem with Time Windows (VRPTW) which is
a generalization of the VRP.

In this paper, the heuristic method is composed of two phases:
initial solution and improvement algorithm. The initial solution
can be obtained by "nearest neighbor procedure" and "scan algorithm".
The improvement algorithm is obtained by "Tabu research". Therefore,
we can obtain an approximate solution. Besides, we propose many
exchange methods (such as swap, 2-opt* exchange and insert) to deal
with different missions and compare their difference. We compare
with the results of "Threshold Accepting" and the heuristic solution
of this paper, and use "Branch and Bound" to obtain a lower bound
of the optimum value as a comparing basis. Therefore, we can realize
the effects of this paper.

並列關鍵字

Vehicle routing problem ； Nearest neighbor procedure ； Scan algorithm ； Tabu sesearch ； exchange method ； Branch and Bound ； Threshold Accepting

參考文獻

1. 陳功欽，「一般性車輛途程之探討」，私立元智工學院，碩士論文，民國85年6月。

2. 徐明輝，「多部車一般性車輛途程解算法之研究」，私立元智工學院，碩士論文，民國86年6月。

4. Araque, J. R., G. Kudva, T. L. Morin and J. F. Pekny, "A Branch-and-cut Algorithm for vehicle routing Problems," Annals of Operations Research, Vol. 50, pp.37-60, 1994.

5. Ball, M. and M. Magazine, "The Design and Analysis of Heuristics," Networks, Vol.11., 1981, pp. 215-219.

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