中文摘要
隨著網際網路的快速發展，二十一世紀已經成為一個數位化與全球化的時代，企業的經營環境發生巨大的改變；為了快速回應消費者之需求和增加供應鏈系統整體之綜效，個別企業必須與其供應商和顧客進行有效地協調與整合；因此，供應鏈管理被廣泛地研究；其中，配銷批量的決定和車輛途程的安排是一個多階層供應鏈系統中兩項重要的作業。
本論文提出三個研究議題來詳細探討多階層供應鏈配銷批量和車輛途程的問題。第一個議題建構一個多階層供應鏈時變需求配銷批量之混合整數規劃模式，同時發展一個以基因演算法為基礎的兩階段啟發式解法；其中，採用合併多期需求訂購策略，而非過去大部分文獻採用之批對批訂購策略；實驗結果顯示兩階段啟發式解法與最佳解法比較，展現良好的求解績效；也發現合併多期需求訂購策略優於批對批訂購策略；此外，從第三個實驗獲得許多重要的觀察與管理上的應用；同時經由實務個案研究，展現兩階段啟發式解法優越的實用性。第二個議題發展一個能有效求解複雜多物流中心考慮時間窗車輛途程問題之兩階段啟發式解法，過去文獻所忽略的等待時間被考慮；透過第一個實驗驗證考慮等待時間是必要的，且其對總配送時間和車輛使用總數有顯著地影響；第二個實驗發現當求解窄時間窗和低容量比的例題時，兩階段啟發式解法優於萬用搜尋法；反之，則後者表現較好；此外，實務個案應用結果顯示本論文兩階段啟發式解法優於個案公司現行的方法。最後一個議題建構一個能同時決定多階層供應鏈系統配銷數量和車輛途程之混合整數規劃模式，並發展一個有效的兩階段啟發式解法以求解大型問題。其中，第一階段提出三個重要的準則，以獲得好的初始可行解；第二階段則利用最佳搜尋法與最小堆疊性質，改善初始解的品質。另外，兩階段啟發式解法優越之求解績效透過兩個實驗被驗證。
總之，本論文提出的三個啟發式解法與最佳解法相比是比較簡單的方法，適合實務應用；因此，物流業在設計電腦輔助車輛途程系統時，可考慮這些啟發式解法。

The 21st century has become a digitalization and globalization era and the environment in which businesses operate has dramatically changed due to the rapid development of Internet. A company should efficiently coordinate and integrate with its up-stream members (i.e., suppliers) and down-stream members (i.e., customers) to quickly response the consumer needs and increase the synergy of operating the supply chain as a whole. Consequently, the research on supply chain management is received considerable attention. Determining distribution lot-sizes and scheduling vehicle routes are two important activities in a multi-echelon supply chain.
For this reason, this dissertation is to determine three research topics to explore the distribution lot-sizing and vehicle routing problems for multi-echelon supply chains. The first topic is to formulate a novel mixed-integer programming distribution lot-sizing model with time-varying demand, and then develop an efficient two-phase heuristic method based on the genetic algorithm, in which a combined multi-period demand ordering policy, rather than the lot-for-lot ordering policy appeared in the literature, is adopted. The experimental results indicate that the good performance of the proposed method has been verified through a comparison with the optimal solution method. It is also shown that the performance of the proposed combined multi-period demand ordering policy is superior to that of the lot-for-lot ordering policy. Additionally, several important findings and managerial implications can be observed from the results of the third experiment. The real-life usefulness of the proposed method is demonstrated by a practical application. The second topic is to develop a two-phase heuristic method that can be used to solve efficiently the intractable multi-depot vehicle routing problem with time windows. The waiting time that was ignored by previous researchers is considered in this dissertation. The necessity of this consideration is verified through an experiment, and the results indicate that the waiting time has a significant impact on the total distribution time and the number of vehicles used. The results of another experiment reveal that the proposed heuristic method can obtain a better solution in the case of narrow time windows and low capacity ratio, while the proposed meta-heuristic method outperforms the proposed heuristic method, provided that wide time windows and high capacity ratio are assumed. In addition, the results of a practical application show that the proposed heuristic method is superior to the current method adopted by the case company. The third topic is to formulate a novel mixed-integer programming model to determine the multi-echelon distribution quantities and vehicle routes simultaneously, and then develop an efficient two-phase heuristic method for solving large-scale problems. Three important criteria are proposed and used to generate a good initial solution in the first-phase heuristic. The second-phase heuristic based on best-first search method and min-heap property is developed to improve the initial solution. The excellent performance of the proposed two-phase heuristic method is verified through two experiments.
In summary, the three proposed heuristic methods are suitable for practical application since these methods are simpler than the optimal solution method. Therefore, they can be considered in developing of a computer-aided vehicle routing system for a logistics business.

參考文獻
1. 王俊傑撰，邱煥能指導，多物流中心車輛可重覆使用之途程問題研究，國立台灣科技大學工業管理研究所碩士論文，民國89年。
2. 邱煥能和翁昭祺，「兩階段分配系統存貨水準訂定之研究」，管理科學學報，第十三卷，第三期，第517∼549頁，民國85年。
3. 邱煥能、黃浩良、葉淑君，「中心與衛星廠JIT供應鏈存貨整合模式之研究」，中國工業工程學會工業工程學刊，第十七卷，第三期，第301∼312頁，民國89年。
4. 曾俊彥撰，邱煥能指導，多階層供應鏈間斷期變動需求配銷批量模式之研究，國立台灣科技大學工業管理研究所碩士論文，民國91年。
5. 黃敏華撰，邱煥能指導，應用螞蟻演算法於多階層供應鏈配送批量和車輛途程之訂定，國立台灣科技大學工業管理研究所碩士論文，民國92年。
6. Atkinson, J.B., “A greedy look-ahead heuristic for combinational optimization: an application to vehicle scheduling with time windows,” Journal of the Operational Research Society, Vol. 45, No. 6, pp.673-684 (1994).
7. Balinski, M. and Quandt, R., “On an integer program for a delivery problem,” Operations Research, Vol. 12, No. 2, pp.300-304 (1964).
8. Beasley, J., “Route first-cluster second methods for vehicle routing,” Omega, Vol. 11, No. 4, pp.403-408 (1983).
9. Berger, J., Barkaoui, M. and Braysy, O., “A route-directed hybrid genetic approach for the vehicle routing problem with time windows,” INFOR, Vol. 41, No. 2, pp.179-194 (2003).
10. Blackburn, J. D., Time-Based Competition, Burr Ridge, IL: Business One Irwin (1991).
11. Bramel, J. and Simchi-Levi, D., “A location based heuristic for general routing problems,” Operations Research, Vol. 43, No. 4, pp.649-660 (1995).
12. Bullnheimer, B., Hartl, R.F., and Strauss, C., “An improved ant system algorithm for the vehicle routing problem,” Annals of Operations Research, Vol. 89, No. 0, pp.319-328 (1999).
13. Burns, L. D., Hall R.W., Blumenfeld D. E., and Daganzo, C. F., “Distribution strategies that minimize transportation and inventory costs,” Operations Research, Vol. 33, No. 3, pp.469-490 (1985).
14. Caseau, Y. and Laburthe, F., “Heuristics for large constrained vehicle routing problems,” Journal of Heuristics, Vol. 5, No. 3, pp. 281-303 (1999).
15. Chandra P. and Fisher M. L., “Coordination of production and distribution planning,” European Journal of Operational Research, Vol. 74, No. 3, pp. 503-517 (1994).
16. Chiu, H. N., “A cost saving technique for solving capacitated multi-stage lot-sizing problems,” Computers & Industrial Engineering, Vol. 24, No. 3, pp. 367-377 (1993).
17. Chiu, H. N., “Discrete time-varying demand lot-sizing models with learning and forgetting effects,” Production Planning & Control, Vol. 8, No. 5, pp. 484-493 (1997).
18. Chiu, H. N., Chen, H. M. and Weng, L. C., “Deterministic time-varying demand lot-sizing models with learning and forgetting in setups and production,” Production and Operations Management, Vol. 12, No. 1, pp. 120-127 (2003).
19. Chiu, H. N. and Huang, H. L., “A multi-echelon integrated JIT inventory model using the time buffer and emergency borrowing policies to deal with random delivery lead times,” International Journal of Production Research, Vol. 41, No. 13, pp. 2911-2931 (2003).
20. Chiu, H. N., Lee, Y. S. and Tseng, C. Y., “Distribution lot-Sizing models for arborescent supply chains with discrete-period variable demand,” Production Planning & Control, Vol. 14, No. 7, pp.634-646 (2003).
21. Christofides, N., “Vehicle scheduling and routing,” Presented at the 12th International Symposium on Mathematical Programming, Cambridge, MA (1985).
22. Christofides, N., Mingozi, A. and Toth, P., “The vehicle routing problem.” In: Christofides, N., Mingozi, A., Toth, P. and Sandi, C. (Eds.), Combinatorial Optimization, pp.318-338, Wiley, New York (1978).
23. Chiang, W.C. and Russell, R.A., “Simulated annealing metaheuristics for the vehicle routing problem with time windows,” Annals of Operations Research, Vol. 63, No. 1, pp.3-27 (1996).
24. Chiang, W.C. and Russell, R.A., “A reactive tabu search metaheuristic for the vehicle routing problem with time windows,” INFORMS Journal on Computing, Vol. 9, No. 4, 417-430 (1997).
25. Clark, A. J., “An informal survey of multi-echelon inventory theory,” Naval Research Logistics, Vol. 19, No. 4, pp.621-650 (1972).
26. Clark, A. J. and Scarf, H., “Optimal policies for a multi-echelon inventory problem,” Management Science, Vol. 6, No.1, pp.475-490 (1960).
27. Clark, G. and Wright, J. W., “Scheduling of vehicles from a central depot to a number of delivery points,” Operations Research, Vol. 12, No. 4, pp.568-581 (1964).
28. Cohen, M. A. and Lee, H. L., “Strategic analysis of integrated production-distribution system: Model and method,” Operations Research, Vol. 36, No. 2, pp.216-228 (1988).
29. Cordeau, J., Gendreau, M. and Laporte, G., “A tabu search heuristic for periodic and multi-depot vehicle routing problems,” Networks, Vol. 30, No. 2, pp.105-119 (1997).
30. Cordeau, J., Laporte, G. and Mercier, A., “A unified tabu search heuristic for vehicle routing problems with time windows,” Journal of the Operational Research Society, Vol. 52, No. 8, pp.928-936 (2001).
31. Cordeau, J., Desaulniers, G., Desrosiers, J., Solomon, M. M. and Soumis, F., “The VRP with time windows. In Toth, P. and Vigo, D. (Eds.): The vehicle routing problem, SIAM Monographs on discrete mathematics and applications,” pp.157-194, SIAM, Philadelphia (2001).
32. Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein,C., Introduction to algorithms, 2nd Edition, pp. 127-142, The MIT Press, Cambridge, Massachusetts London, England (2001).
33. Deuermeyer, B.L., and Schwarz, L.B., “A model for analysis of system service level in warehouse-retailer distribution systems: The identical retailer case. Multi-level production/inventory control systems: theory and Practice (Edited by Schwarz, L.B.),” TIMES Studies in the Management Science, 16, pp.163-193, North-Holland, Amsterdam (1981).
34. Desrosiers, J., Dumas, Y., Solomon, M. M. and Soumis, F., “Time constrained routing and scheduling. In Ball, M.O., Magnanti, T.L., Monma, C.L. and Nemhauser, G.L. (Eds.),” Handbooks in Operations Research and Management Science 8: Network Routing, pp.35-139, Elsevier Science Publishers, Amsterdam (1995).
35. Dorigo, M., and Gambardella, L. M., “Ant colonies for traveling salesman problem,” BioSystems, Vol. 43, No. 2, pp.73-81 (1997).
36. Eftekharzadeh, R., “A comprehensive review of production lot-sizing,” International Journal of Physical Distribution & Logistics Management, Vol. 23, No. 1, pp.30-40 (1993).
37. Eilon, S. Watson-Gandy, C.D.T. and Christofides, N., Distribution Management: Mathematical Modeling and Practical Analysis, Griffin, London (1971).
38. Erkip, N., Hausman, W., and Nahmias, S., “Optimal centralized policies in multi-echelon inventory systems with correlated demands,” Management Science, Vol. 36, No. 3, pp.381-392 (1990).
39. Fisher, M.L. and Jaikumar, R., “A generalized assignment heuristic for vehicle routing,” Networks, Vol. 11, No. 2, pp.109-124 (1981).
40. Gambardella, L.M., Taillard, É. and Agazzi, G., “MACS-VRPTW: A multiple ant colony system for vehicle routing problem with time windows,” Technical Report IDSIA-06-99, Lugano, Switzerland (1999).
41. Gambardella, L.M. and Dorigo, M., “Solving symmetric and asymmetric TSPs by ant colonies,” ICEC96, Proceedings of the IEEE Conference on Evolutionary Computation, pp.622-627, Nagoya, Japan (1996).
42. Gendreau, M. Hertz A. and Laporte, G., “A tabu search heuristic for the vehicle routing,” Management Science, Vol. 40, No. 10, pp.1276-1290 (1994).
43. Ghaziri, H. (eds. Osman, I. and Kelly, J.), “Supervision in the self-organizing feature map: Application to the vehicle routing problem,” In Meta-Heuristics: Theory and Applications, Kluwer, Boston (1996).
44. Gillett, B.E. and Miller, L.R., “A heuristic algorithm for the vehicle routing dispatch problem,” Operations Research, Vol. 22, No. 2, pp.340-349 (1974).
45. Giosa, I.D., Tansini, I.L. and Viera, I.O., “New assignment algorithms for multi-depot vehicle routing problem,” Journal of the Operational Research Society, Vol. 53, No. 9, 977-984 (2002).
46. Goldberg, D. E., Genetic Algorithms in Search Optimization and Machine Learning, Addison-Wesley, New York (1989).
47. Golden, B.L. and Assad, A.A., “Perspectives on vehicle routing: Exciting new developments,” Operations Research, Vol. 34, No. 5, pp.803-809 (1986).
48. Haq, A. N., Vrat, P., and Kanda, A., “An integrated production-inventory-distribution model for manufacture of urea: a case,” International Journal of Production Economics, Vol. 25, No. 1, pp.39-49 (1991).
49. Hinojosa, Y., Puerto, J. and Fernandez, F. R., “A multiperiod two-echelon multicommodity capacitated plant location problem,” European Journal of Operational Research, Vol. 123, No. 2, pp. 271-291 (2000).
50. Hwang, H. S., “An improved model for vehicle routing problem with time constraint based on genetic algorithm,” Computers & Industrial Engineering, Vol. 42, No. 3, pp.361-369 (2002).
51. Ioannou, G., Kritikos, M., & Prastacos, G., “A greedy look-ahead heuristic for vehicle routing problem with time windows,” Journal of the Operational Research Society, Vol. 52, No. 5, 523-537 (2001).
52. Laporte, G., Mercure, H. and Nobert, Y., “An exact algorithm for the asymmetrical capacitated vehicle routing problem,” Networks, Vol. 16, No. 1, pp.33-46 (1986).
53. Luger, G. F., Artificial Intelligence: Structers and Strategies for Complex Problem Solving, 4th Edition, pp.127-138, Addison-Wesley (2002).
54. Melachrinoudis, E. and Min, H., “The dynamic relocation and phase-out of a hybrid, two-echelon plant/warehousing facility: a multiple objective approach,” European Journal of Operational Research, Vol. 123, No. 1, pp. 1-15 (2000).
55. Mohamed, Z. M., “An integrated production-distribution model for multi-national company operating under varying exchange rates,” International Journal of Production Economics, Vol. 58, No. 1, pp. 81-92 (1999).
56. Orlicky, J. A., Plossl, G. W., and Wright, O. W., Material Requirements Planning, McGraw-Hill, New York (1975).
57. Osman, I., “Meta-strategy simulated annealing and tabu search algorithms for the vehicle routing problem,” Annals of Operations Research, Vol. 41, No. 4, pp.421-451 (1993).
58. Potvin, J. Y. and Bengio, S.,” The vehicle routing problem with time windows part Ⅱ: Genetic search,” INFORMS Journal on Computing, Vol. 8, No. 2, pp.165-172 (1996).
59. Potvin, J. Y., and Rousseau, J. M., “A parallel route building algorithm for the vehicle routing problem with time windows,” European Journal of Operational Research, Vol. 66, No. 3, pp.331-340 (1993).
60. Potvin, J. Y. and Rousseau, J. M., “An exchange heuristic for routing problems with time windows,” Journal of the Operational Research Society, Vol. 46, No. 12, pp.1433-1446 (1995).
61. Renaud, J., Laporte, G., and Boctor, F., “A tabu search heuristic for the multi-depot vehicle routing problem,” Computer and Operations Research, Vol. 23, No. 3, pp.229-235 (1996).
62. Russell, R.A., “Hybrid heuristic for the vehicle routing problem with time windows,” Transportation Science, Vol. 29, No. 2, pp.156-166 (1995).
63. Schwarz, L.B., “Multi-level production/inventory control systems: theory and practice,” TIMES Studies in the Management Science, 16, North-Holland, Amsterdam (1981).
64. Skok, M., Skrlec, D. and Krajcar, S., “The genetic algorithm method for solving multiple depot capacitated vehicle routing problems,” 4th International Conference on Knowledge-Based Intelligent Engineering Systems & Allied Technologies, pp.520-526, Brighton, UK (2000).
65. Solomon, M. M., “Algorithms for the vehicle routing and scheduling problems with time window constraints,” Operations Research, Vol. 35, No. 2, pp.254-265 (1987).
66. Solomon, M. M. and Desrosiers, J., “Time window constrained routing and scheduling problems,” Transportation Science, Vol. 22, No. 1, pp. 1-13 (1988).
67. Speranza, M. G., and Ukovich, W., “Minimizing transportation and inventory costs for several products on a single link,” Operations Research, Vol. 42, No. 5, pp.879-894 (1994).

68. Svoronos, A., and Zipkin, P., “Estimating the performance of multi-level inventory systems,” Operations Research, Vol. 36. No. 1, pp.57-72 (1988).
69. Van Roy, T. J., “Multi-level production and distribution planning with transportation fleet optimization,” Management Science, Vol. 35. No. 12, pp.1443-1453 (1989).
70. Taillard, É., Badeau, P., Gendreau, M., Guertin, F. and Potvin, J.Y., “A tabu search heuristic for the vehicle routing problem with soft time windows,” Transportation Science, Vol. 31, No. 2, pp.170-186 (1997).
71. Wagner, H. M., and Whitin, T. M., “Dynamic version of the economic lot size model,” Management Science, Vol. 5, No. 1, pp.89-96 (1958).
72. Whybark, D. C. and Williams, J. G., “Material requirements planning under uncertainty,” Decision Sciences, Vol. 7, No. 4, pp.595-606 (1976).