車輛排程問題和日常生活息息相關。在數學上車輛排程問題是一個NP-hard的問題，要正確的求解並不容易。實務上經常以人工進行車輛排程，但往往費時、費力，且無法達到最佳化。由於問題的複雜度以及多樣性，此類問題仍然是許多學者研究的對象。且目前的文獻大多只能求解小規模問題，這對模式的實用性有很大的限制。

　　本研究以最小化總旅行距離為目標式，使用軟式時間窗限制，以設定時間窗懲罰值的方式，求解含時間窗限制之車輛排程問題。求解時以先分群再排路線的求解策略產生起始可行解，再以交換客戶點的方式反覆搜尋更佳的可行解。交換客戶點時則利用配對問題有效率的擴大鄰近搜尋的範圍，以達成廣域搜尋之效果。其中配對問題是以successive shortest path algorithm反覆使用標籤設定法求解最短路徑。演算法使用含時間窗之最便宜插入法以簡化求解配對問題時的TSP子問題，並每隔數十回合以門檻接受法重新求解每條路線的TSP問題，以大幅節省求解時間同時確保求解品質。

　　測試部份，分別測試Solomon的題庫測試例，和一自行產生之與實際情況相似之大規模範例，並找出較好的參數，和題庫的已知結果作比較及驗證，以模擬測試此方法的正確性及演算效能。由模式驗證的結果可知，本研究提出之最佳化模式，在求解時間和求解品質上均有優良的表現。在Solomon的題庫測試例中，更有多個結果相同或超越已知最佳解。並能有效率的求解大規模範例。

　　The Vehicle Routing Problem is a basic problem that appears in many real-world problems. With a Very Large-Scale Neighborhood Search apprach, this research considers Vehicle Routing Problem with soft time window constrains, and has multiple objectives in that the optimization goal is to minimize not only travel distance but also total delay. The heuristic constructs an assignment problem to efficiently discover good ways to improve a feasible solution by exchanging customs between routes, and solve the assignment problem with the successive shortest path algorithm. The shortest path problems are solved with the Label setting algorithm. The heuristic needs to solve Traveling Salesman Problems as subproblems at various stages of the process. Different algorithms, including the Threshold Accepting approach and Chepaest Insertion approach, are used in these stages to maintain a good balance between accuracy and CPU time.

　　The proposed heuristic is tested with a number of instances, including some benchmark instances found in Solomon (1987). The heuristic performed very well and exceeded previous results for some benchmark instances.

1.Ahuja, R. K., Magnanti, T. L., Orlin, J. B., Network Flows, Prentice Hall, New Jersey (1993).

2.Ahuja, R. K., Ergun, O., Orlin, J. B., Punnen, A. P., A survey of very large-scale neighborhood search techniques, Discrete Applied Mathematics 123, pp.75-102 (2002).

3.Angelelli, E., Speranza, M. G., The periodic vehicle routing problem with intermediate facilities, European Journal of Operational Reasearch 137, pp.233-247 (2002).

4.Bachem, A., Hochstattler, W., Malich, M., The simulate trading heuristic for solving vehicle routing problems, Discrete Applied Mathematics 65, pp.47-72 (1996).

5.Baker, B. M., Ayechew, M. A., A genetic algorithm for the vehicle routing problem, Computers & Operations Research 30, pp.787-800 (2003).

6.Barbarosoglu, G., Ozgur, D., A tabu search algorithm for the vehicle routing problem, Computers & Operations Research 26, pp.255-270 (1999).

7.Beasley, J. E., Route-first cluster-second methods for vehicle routing, Omega 11, pp.403-408 (1983).

8.Bell, J. E., McMullen, P. R., Ant colony optimization techniques for the vehicle routing problem, Advanced Engineering Informatics 18, pp.41-48 (2004).

9.Bent, R., Hentenryck, P. V., A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows, Computers & Operations Research 33, pp.875-893 (2006).

10.Belenguer, J. M., Benavent, E., A cutting plane algorithm for the capacitated arc routing problem, Computers & Operations Research 30, pp.705-728 (2003).

11.Bodin, L., Golden, B. L., Assad, A., Ball, M., Routing and Scheduling of Vehicles and Crews, Comput. & Ops Res. Vol. 10, No.2, pp.63-211 (1983).

12.Braysy, O., Gendreau, M., Vehicle Routing Problem with Time Windows, Part II: Metaheuristics, Transportation Science Vol.39, No.1, February, pp.119-139 (2005).

13.Breedam, A. V., Improvement heuristics for the Vehicle Routing Problem based on Simulated Annealing, European Journal of Operational Research 86, pp.480-490 (1995).

14.Clark, G., Wright, J., Scheduling of vehicles from a central depot to a number of delivery points, Ops. Res. 12, pp.568-581 (1964).

15.Cordeau, J.-F., Gendreau, M., Hertz, A., Laporte, G., Sormany, J.-S., New Heuristics for the Vehicle Routing Problem, Les Cahiers du GERAD G-2004-33, (2004).

16.Crino, J. R., Moore, J. T., Barnes, J. W., Nanry, W. P., Solving the Theater Distribution Vehicle Routing and Scheduling Problem using Group Theoretic Tabu Search, Mathematical and Computer Modelling 39, pp.599-616 (2004).

17.Dorigo, M., Maniezzo, V., Colorni, A., Positive feedback as a search strategy, Technical Report, Dip.Elettronica, Politecnico di Milano, pp. 91-106 (1991).

18.Dorigo, M., Maniezzo, V., Colorni, A., The ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man and Cybernetics, Part B, 26(1), pp.29-42 (1996).

19.Dueck, G., Scheuer, T., Threshold Accepting: A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing, Journal of Computational Physics, V 90, pp.161-175 (1990).

20.Fahrion, R., Wrede, M., On a principle of chain exchange for vehicle routing problems (I-VRP), J. Oper. Res. Soc., pp.821-827 (1990).

21.Fisher, M. L., Jaikumar, R., A generalized assignment heuristic for the vehicle routing problem, Networks 11, pp.109-124 (1981).

22.Gendreau, M., Guertin, F., Potvin, J.Y., Seguin, R., Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries, CRT-98-10 (1998).

23.Gillett, B. E., Miller, L. R., A heuristic algorithm for vehicle dispatch problem, Operations Research 22, pp.340-349 (1974).

24.Glover, F., Tabu Search, Part I, ORSA Journal on Computing, 1, pp.190-209 (1989).

25.Glover, F., Tabu Search, Part II, ORSA Journal on Computing, 2, pp.4-32 (1990).

26.Glover, F., Ejection chains, reference structures, and alternating path algorithms for the traveling salesman problem, Research report, University of Colorado-Boulder, Graduate School of Business, 1992, A short versionappeared inDiscrete Appl. Math. 65, pp.223-253 (1996).

27.Goldberg, D. E., Genetic Algorithm in search, Optimization, and Machine Learning, Addison-Wesley Publishing Company (1989).

28.Golden, B., A statical approach to the TSP, Network 7, pp.209-225 (1977).

29.Kirpatrick, S., Gelatt, C. D., Jr., M.P. Vecchi, Optimization by Simulated Annealing, Science 220, pp.671-680 (1983).

30.Ho, S. C., Haugland, D., A tabu search heuristic for the vehicle routing problem with time windows and split deliveries, Computers & Operations Research 31, pp.1947-1964 (2004).

31.Hong, S. C., Park, Y. B., A heuristic for bi-objective vehicle routing with time window constraints, Int. J. Production Economics 62, pp.249-258 (1999).

32.Lin, S., Computer solutions of the traveling salesman problem, Bell System Tech. J. 44, pp.2245-2269 (1965).

33.Lin, S., Kernighan, B., An effective heuristic algorithm for the traveling salesman problem, Oper. Res. 21, pp.498-516 (1973).

34.Mazzeo, S., Loiseau, I., An Ant Colony Algorithm for the Capacitated Vehicle Routing, Electronic Notes in Discrete Mathematics 18, pp.181-186 (2004).

35.Moscato, P., Cotta, C., A gentle introduction to memetic algorithms, In: Glover F., and Kochenberger G.A. (eds), Handbook of Metaheuristics, Kluwer Boston, pp.105-144 (2003).

36.Naddef, D., Rinaldi, G., Branch-and-cut algorithms for the capacitated VRP, In: Toth, P. and Vigo, D. (eds), The Vehicle Routing Problem pp.53-84, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia (2002).

37.Nanry, W. P., Barnes, J. W., Solving the pickup and delivery problem with time windows using reactive tabu search, Transportation Research Part B 34, pp.107-121 (2000).

38.Or, I., Traveling Salesman-Type Combinatorial Problems and their Relation to the Logistics of Regional Blood Banking, Ph.D. Thesis, Northwestern University, Evanston, IL (1976).

39.Prins, C., A simple and effective evolutionary algorithm for the vehicle routing problem, Computers & Operations Research 31, pp.1985-2002 (2004).

40.Ralphs, T. K., Parallel branch and cut for capacitated vehicle routing, Parallel Computing 29, pp.607–629 (2003).

41.Rego, C., Roucairol, C., A parallel tabu search algorithm using ejection chains for the vehicle routing problem, in: I.H. Osman, J.P. Kelly (Eds.), Meta-Heuristics: Theory and Applications, Kluwer Academic Publishers, Dordrecht (1996).

42.Rego, C., A subpath ejection method for the vehicle routing problem, Management Sci. 44, pp.1447-1459 (1998).

43.Rosenkrantz, D., Sterns, R., Lewis, P., An analysis of several heuristics for the traveling salesman problem, SIAM J. Comp. 6, pp.563-581 (1977).

44.Russell, R. A., Chiang, W. C., Scatter search for the vehicle routing problem with time windows, European Journal of Operational Research 169, pp.606-622 (2006).

45.Salhi, S., Sari, M., A multi-level composite heuristic for the multi-depot vehicle fleet mix problem, European Journal of Operational Research 103, pp.95-112 (1997).

46.Secomandi, N., Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands, Computers & Operations Research 27, pp.1201-1225 (2000).

47.Solomon, M. M., Algorithms for The Vehicle Routing and Scheduling Problums with Time Window Constraints, Operation Research Vol.35, No.2, pp. 254-265 (1987).

48.Tan, K. C., Lee, L. H., Ou, K., Artificial intelligence heuristics in solving vehicle routing problems with time window constraints, Engineering Applications of Artificial Intelligence 14, pp.825-837 (2001).

49.Thompson, P. M., Psaraftis, H. N., Cyclic transfer algorithms for multivehicle routing and scheduling problems, Oper. Res. 41 (1993).

50.Toth, P., Vigo, D., Models, relaxations and exact approaches for the capacitated vehicle routing problem, Discrete Applied Mathematics 123, pp.487-512 (2002).

51.Xu, J., Kelly, J. P., A network flow-based tabu search heuristic for the vehicle routing problem, Transportation Science 30, pp.379-393 (1996).

52.吳致昀，「多車次車輛路線問題之研究」，國立成功大學工業管理學系碩士論文 (2000)。

53.顏成佑，「基因演算法解算軟性時窗車輛途程問題之研究」，元智大學工業工程研究所碩士論文 (2000)。

54.陳契伸，「硬性/軟性時窗限制之車輛途程問題研究」，中原大學工業工程研究所碩士論文 (2001)。

55.韓復華、楊智凱、卓裕仁，「應用門檻接受法求解車輛路線問題之研究」，運輸計劃季刊，第26卷，第2期，頁253-280 (1997)。

56.吳泰熙、黃金智、楊懿淑，「以禁忌搜尋演算法求解確定型及隨機型多車種車輛途程問題」，工業工程學刊，第18卷，第2期，頁102-112 (2001)。

57.http://www.iwr.uni-heidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html

58.http://neo.lcc.uma.es/radi-aeb/WebVRP/index.html?/algorithms/improvement.html