臺灣博碩士論文加值系統

隨著產業的競爭日益激烈，企業無不盡可能地滿足顧客的種種需求以爭取訂單及穩定客源。企業必須有效地協調生產與配送流程以減少營運成本，且同時快速地反應顧客需求，以達到整體最佳化。然而先前學者研究並未考慮整合因素，使得未充分地善用企業有限資源，因此在產品配送方面大都採一對一直接往返配送的方式。除此之外，成本計算上則是直接依據顧客之需求量估算其配送成本，無法精準地計算出生產與配送兩階段之整合模式的總成本。為了改善先前研究缺失，本研究發展一具時窗限制的生產與配送問題之整合模式，以最小化總成本為目標。此外配送成本則是根據距離加以計算，取代過去研究以需求量為主的計算方式。最後嘗試以兩階段混合式演算法來求解此研究模式。實驗結果顯示，本研究之兩階段混合式演算法具有相當高的求解效能與效率。

With the competition in business, companies try their best to meet customers’ requirement in order to receive orders from them. To reduce the cost, companies need to effectively operate their processes of the production and distribution, and quickly respond to customers’ needs to reach the overall optimization for companies. However, previous researches didn’t take integration into consideration. They didn’t utilize limited resources well; therefore, the method of one-to-one product distribution was adopted. Moreover, the estimate of cost is on the basis of the amount of customers’ demands. The total cost of integration between production and distribution can’t be accurately calculated. In order to amend deficiency of previous researches, this study develops the integration model of production and distribution problem with time windows to minimize the total cost as the target. Besides, the estimate of the distribution cost is based on the distance to replace the previous research which is based on the estimate of demands. Finally, this research tries to adopt the integrated estimation of this two stages, production and distribution, as the research method. The final result reveals that the integrated method obtains highly effectiveness and efficiency.

目 錄

摘 要 I
Abstract II
誌 謝 III
目 錄 IV
圖表索引 VI
1. 緒論 1
1.1 研究背景 1
1.2 研究動機 2
1.3 研究目的 4
1.4 研究假設與限制 5
1.5 研究方法與流程 6
1.6 論文架構 6
2. 文獻探討 8
2.1 旅行銷售員問題(Traveling Salesman Problem，TSP) 8
2.1.1 問題描述 8
2.1.2 問題定義 8
2.1.3 TSP之相關求解演算法 10
2.2 具時窗限制之車輛途程問題(Vehicle Routing problem with time windows，VRPTW) 10
2.2.1 問題描述 11
2.2.2 問題定義 11
2.2.3 VRPTW之整數線性規劃模式 12
2.2.4 VRPTW之相關求解演算法 13
2.3 螞蟻演算法(Ant Colony System，ACS) 15
2.3.1 狀態轉換規則(state transition rule) 17
2.3.2 區域更新規則(local updating rule) 18
2.3.3 全域更新規則(global updating rule) 18
2.4 禁忌搜尋法(Tabu Search，TS) 19
2.5 結論 20
3. 研究模式 22
3.1 模式假設 22
3.2 符號定義說明 23
3.3 具有時窗限制的生產與配送兩階段之整合模式 24
4. 探索解 26
4.1 演算法之執行步驟 27
4.1.1 第一階段：生產問題之起始解(Ant Colony System) 27
4.1.2 第一階段：路徑規劃問題之起始解(Tabu Search) 28
4.1.3 第二階段：改善解之演算法(Tabu Search) 33
4.2 演算之流程圖 36
5. 實驗設計與分析 39
5.1 實驗設計 39
5.2 實驗分析 43
5.3 敏感度分析 51
6. 結論與建議 53
參考文獻 54
附 錄 67
附錄一、小問題資料 67
附錄二、大問題資料（size為25） 70
附錄三、大問題資料（size為50） 75
附錄四、大問題資料（size為75） 83
作者簡介 94

參考文獻
中文部份
[1]王永宏，運用遺傳演算法求解供應鏈產銷整合問題，國立成功大學工業管理研究所碩士論文，2003。
[2]李洪鑫，含時窗車輛途程問題各演算法適用範圍之探討，東海大學工業工程研究所碩士論文，2000。
[3]郭國基，物流中心指標建立與應用之研究，大葉大學事業經營研究所碩士論文，1995。
[4]陳沛喬，運用先進規劃排程觀念建立生產配銷模－以機車製造商為例，南台科技大學企業管理研究所碩士論文，2003。
[5]彭議慶，全球運籌管理中產銷協同之決策機制，國立清華大學工業工程管理研究所碩士論文，2003。
[6]劉珮伶，考慮產品配送下之多廠區訂單分配問題應用門檻值接受法，元智大學工業工程與管理研究所碩士論文，2004。
[7]蔣美鳳，流通業物流中心績效評估實證研究，台灣工業技術學院管理技術研究所工業管理學程碩士論文，1996。
[8]鐘正郎，全球運籌體系中生產與配送模式之整合研究，國立成功大學工業管理研究所碩士論文，2002。
英文部份
[1]Badeau P., Gendreau F.G.M., Potvin J.Y. and Taillard E., A parallel tabu search heuristic for the vehicle routing problem with time windows. 5(2):109-122, 1997.
[2]Bent R. and Hentenryck P.V., A two-stage hybrid local search for the vehicle routing problem with time windows. Transportation Science, in press.
[3]Bertsimas D. and Simchi-Levi D., The new generation of vehicle routing research: robust algorithms addressing uncertainty. Operations Research 44:286-304, 1996.
[4]Berger J., Barkaoui M. and Bräysy O., A route-directed hybrid genetic approach for the vehicle routing problem with time windows. Information Systems and Operations Research, 41:179-194, 2003.
[5]Berger J. and Barkaoui M., A parallel hybrid genetic algorithm for the vehicle routing problem with time windows. Computers and Operations Research, 31:2037-053, 2004.
[6]Blum C., Beam-ACO-hybridizing ant colony optimization with beam search: an application to open shop scheduling. Computers and Operations Research, 32:1565-1591, 2005.
[7]Bräysy O., Haslea G. and Dullaert W., A multi-start local search algorithm for the vehicle routing problem with time windows. European Journal of Operational Research, 159:586-605, 2004.
[8]Bullnheimer B., Hartl R.F. and Strauss C., Applying the ant system to the vehicle outing problem. in: Second Metaheuristics International Conference, MIC’97, Sophia-Antipolis, France, 1997.
[9]Bullnheimer B., Hartl R.F. and Strauss C., Applying the ant system to the vehicle outing problem. in: Voss S., Martello S., Osman I. H. and Roucairol C. (Eds.) Meta-heuristics: advances and trends in local search paradigms for optimization. Boston: Kluwer, 1999.
[10]Bullnheimer B., Hartl R.F. and Strauss C., An improved ant system algorithm for the vehicle routing problem. Annals of Operations Research, 89:319-34, 1999.
[11]Buera G.M.V., Woodruff L.D. and Olsonc T.R., Solving the medium newspaper production/distribution problem. European Journal of Operational Research, 115: 237-253, 1999.
[12]Caseau Y., Laburthe F. and Silverstein G., A metaheuristic factory for vehicle routing problems. in: Jaffar J.(Ed.), Principles and Practice of Constraint Programming-CP 99. in: Lecture Notes in Computer Science. Springer-Verlag, New York, pp.144-158, 1999.
[13]Chen X., Wan W. and Xu X., Modeling rolling batch planning as vehicle routing problem with time windows. Computers and Operations Research, 25(12):1127-1136, 1998.
[14]Chiang W.C. and Russell R.A., Simulated annealing metaheuristics for the vehicle routing problem with time windows. Annals of Operations Research, 63:3-27, 1996.
[15]Chiang W.C. and Russell R.A., A reactive tabu search metaheuristic for the vehicle routing problem with time windows. INFORMS Journal on Computing, 9:417-430, 1997
[16]Christofides N., Vehicle routing. in: Lawler E.L., Lenstra J.K., Kan A.H.G.R. and Shmoys D.B.(Eds.), The Traveling Salesman Problem: a guided tour of combinatorial optimization. Wiley, New York, pp.431-448, 1985.
[17]Colorni A., Dorigo M. and Maniezzo V., Distributed optimization by ants colonies. in: Varela F. and Bourgine P.(Eds.), First European Conference on Artificial Life, pp.134-142, 1991.
[18]Colorni A., Dorigo M., Maniezzo and V. Trubian M., Ant system for job-shop scheduling. JORBEL-Belgian Journal of Operations Research Statistics and Computer Science, 34(1):39-53, 1994.
[19]Cordone R. and Calvo R.W., A heuristic for the vehicle routing problem with time windows. Journal of Heuristics, 7:107-129, 2001.
[20]Czech Z. and Czarnas P., Parallel simulated annealing for the vehicle routing problem with time windows. in: Proceedings of 10th Euromicro Workshop on Parallel, Distributed and Network-Based Processing, Canary Islands, Spain, pp.376-383, 2002.
[21]Desrochers M., Desrosiers J. and Solomon M., A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 40(2):342-354, 1992.
[22]Dorigo M., Optimization, learning and natural algorithms. Ph.D. Thesis, Politecnico di Milano, Italy, 1992.
[23]Droigo M. and Gambardella L.M., Ant Colony System: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1):39-53, 1997a.
[24]Dorigo M. and Gambardella L.M., Ant colonies for the traveling salesman problem. BioSytem, 43:73-81, 1997b.
[25]Dorigo M. and Gambardella L.M., Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, pp.53-66, 1997c.
[26]Dorigo M., Maniezzo V. and Colorni A., The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man and Cybernetics, 1(26):29-41, 1996.
[27]Fisher M., Jornsten K.O. and Madsen, O.B.G. Vehicle routing with time windows: two optimization algorithms. Operations Research, 45:488-492, 1997.
[28]Fisher M.L., Optimal solution of vehicle routing problems using minimum k-tree. Operations Research, 42:626-642, 1994.
[29]Fisher M.L., Vehicle routing. in: Ball M.O., Magnanti T.L., Monma C.L. and Nemhauser G.L.(Eds.), Handbooks in Operations Research and Management Science, the Volume on Network Routing. North-Holland, Amsterdam, pp.1-33, 1995.
[30]Forsyth P. and Wren A., An ant system for bus driver scheduling. Proceedings of the Seventh International Workshop on Computer-Aided Scheduling of Public Transport. Boston, 1997.
[31]Gambardella L., Taillard E. and Agazzi G., MACSVRPTW: A multiple ant colony system for vehicle routing problems with time windows. in: Corne D., Dorigo M. and Glover F. (Eds.), New Ideas in Optimization. McGraw-Hill, London, pp.63-76, 1999.
[32]Gambardella L., Taillard E. and Dorigo M., Ant colonies for the QAP. Technical Report, IDSIA, Lugano, Switzerland, 97(4), 1997.
[33]Gambardella L.M., Taillard E.D. and Dorigo M., Ant colonies for the QAP. Journal of Operational Research Society, 50:167-176, 1999.
[34]Garcia B.L., Potvin J.Y. and Rousseau J.M., A parallel implementation of the tabu search heuristic for vehicle routing problems with time window constraints. Computers and Operations Research, 21(9):1025-1033, 1994.
[35]Gehring H. and Homberger J., Parallelization of a two-phase metaheuristic for routing problems with time windows. Asia-Pacific Journal of Operational Research, 18:35-47, 2001.
[36]George I., Manolis K. and Gregory P., A problem generator-solver heuristic for vehicle routing with soft time windows. Omega, 31:41-53, 2003.
[37]Gehring H. and Homberger J., A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows. in: Miettinen K., Mäkelä M.M. and Toivanen J.(Eds.), Proceedings of EUROGEN99––Short Course on Evolutionary Algorithms in Engineering and Computer Science, Reports of the Department of Mathematical Information Technology, No. A 2/1999, University of Jyväskylä, Finland, pp.57-64, 1999.
[38]Gilmore P.C. and Gomory R.E., Sequencing on a one-state variable machine: a solvable case of the traveling salesman problem. Operations Research, 12:655-679, 1964.
[39]Glover F, Kelley J.P. and Laguna M., Genetic algorithms and tabu search: Hybrids for optimization. Computers and Operations Research, 22:111-134, 1995.
[40]Hax A.C., and Candea D., Production and Inventory Management. prentice-Hall, Englewood Cliffs, NJ., 1984.
[41]Herer T.Y. and Levy R., The metered inventory routing problem, an integrative heuristic algorithm. International Journal of Production Economics, 51:69-81, 1997.
[42]Homberger J. and Gehring H., Two evolutionary metaheuristics for the vehicle routing problem with time windows. Information Systems and Operational Research-Special issue: Metaheuristics for Location and Routing Problems, 37:297-318, 1999.
[43]Homberger J.and Gehring H., A two-phase hybrid metaheuristic for the vehicle routing problem with time window. European Journal of Operational Research, 162:220-238, 2005.
[44]Hompson T.P.M. and Psaraftis H., Cyclic transfer algorithms for multi-vehicle routing and scheduling problems. Operations Research, 41:935-946, 1993.
[45]Hong Y., Zhenxin Y. and Cheng T.C.E., A strategic model for supply chain design with logical constraints: formulation and solution. Computers and Operations Research, 30:2135-2155, 2003.
[46]Ioannou G., Kritikos M. and Prastacos G., A greedy lookahead heuristic for the vehicle routing problem with time windows. Journal of the Operational Research Society, 52:523-537, 2001.
[47]Jayaraman V. and Pirkul H., Planning and coordination of production and distribution facilities for multiple commodities. European Journal of Operational Research, 133:394-408, 2001.
[48]Kallehauge B., Larsen J. and Madsen O.B.G., Lagrangian duality applied to the vehicle routing problem with time windows. Computers and Operations Research, 33:1464-1487, 2006.
[49]Kilby P., Prosser P. and Shaw P., Guided local search for the vehicle routing problem with time windows. in: Voss S., Martello S., Osman I.H. and Roucairol C.(Eds.), Meta-Heuristics-Advances and Trends in Local Search Paradigms for Optimization. Kluwer, Boston, pp.473-486, 1999.
[50]Kindt V. T., Monmarché N., Tercinet F. and Laügt D., An ant colony optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem. European Journal of Operational Research, 142:250-257, 2002.
[51]Kohl N., Desrosiers J., Madsen O.B.G., Solomon M.M. and Soumis F., 2-path cuts for the vehicle routing problem with time windows. Transportation Science, 33(1):101-331116, 1999.
[52]Kohl N., and Madsen O.B.G., An optimization algorithm for the vehicle routing problem with time windows based on Lagrangian relaxation. Operations Research, 45(3):395-406, 1997.
[53]Kolen A.W.J., Kan A.H.G.R. and Trienekens H.W.J.M., Vehicle routing with time windows. Operations Research, 35(2):266-331273, 1987.
[54]Kontoravdis G. and Bard J.F., Improved heuristics for the vehicle routing problem with time windows. Technical Report, Department of Mechanical Engineering, University of Texas, Austin, TX , 1994.
[55]Kontoravdis G. and Bard, J.F., A GRASP for the vehiclerouting problem with time windows. ORSA Journal on Computing, 7:10-23, 1995.
[56]Lau H.C., Sim M. and Teo K.M., Vehicle routing problem with time windows and a limited number of vehicles. European Journal of Operational Research, 148:559-569, 2003.
[57]Lee Y.H. and Kim S.H., Production-distribution planning in supply chain considering capacity constraints. Computers and Industrial Engineering, 43:169-190, 2002.
[58]Lenstra J. and Kan A.R., Complexity of vehicle routing and scheduling problems. Networks, 11:221-227, 1981.
[59]Li H., Lim A. and Huang J., Local search with annealing-like restarts to solve the VRPTW. European Journal of Operational Research, 150:115-127, 2003.
[60]Lin F.H.F and Shen S.Y., A route-neighborhood-based metaheuristic for vehicle routing problem with time windows. European Journal of Operational Research, 118:485-504, 1999a.
[61]Lin F.H.F. and Shen S.Y., An overview of a heuristic for vehicle routing problem with time windows. Computers and Industrial Engineering, 37:331-334, 1999b.
[62]Maniezzo V., Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem. INFORMS Journal on Computing, 11(4):358-369, 1999.
[63]Maniezzo V. and Colorni A., The ant system applied to the quadratic assignment problem. IEEE Transactions on Knowledge and Data Engineering, 11(5):769-778, 1999.
[64]McMullen R.P., An ant colony optimization approach to addressing a JIT sequencing problem with multiple objectives. Artificial Intelligence in Engineering, 15:309-317, 2001.
[65]Osman I.H., Vehicle routing and scheduling: application, algorithms and developments. Proceedings of the International Conference on Industrial Logistics, Rennes, France, 1993a.
[66]Osman I.H., Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problems. Annals of Operations Research, 42:421-451, 1993b.
[67]Osman I.H. and Christofides N., Capacitated clustering problem by hybrid simulated annealing and tabu search. International Transaction in Operational Research, 1(3):317-336, 1994.
[68]Osman I.H. and Kelly J.P., Meta-heuristics: An overview. in: Osman I.H. and Kelly J.P. (Eds.), Meta-Heuristics––Theory and Applications. Kluwer, Boston, pp.1-21, 1997.
[69]Potvin J.Y. and Bengio S., The vehicle routing problem with time windows-part II: genetic search. INFORMS Journal on Computing, 8:165-172, 1996.
[70]Potvin J.Y., Kervahut T., Garcia B.L. and Rousseau J.M., The vehicle routing problem with time windows-Part I: Tabu search. INFORMS Journal on Computing, 8:158-164, 1996.
[71]Potvin J. Y. and Rousseau J. M., A parallel route building algorithm for the vehicle routing and scheduling problem with time windows. European Journal of Operational Research, 66:331-340, 1993.
[72]Potvin J. Y. and Rousseau J. M., An exchange heuristic for routing problem with windows. Journal of the Operational Research Society, 46:1433-1446, 1995.
[73]Rochat Y. and Taillard E., Probabilistic diversification and intensification in local search for vehicle routing. Journal of Heuristics, 1:147-167, 1995.
[74]Rousseau L.M., Gendreau M. and Pesant G., Using constraint-based operators to solve the vehicle routing problem with time windows. Journal of Heuristics, 8:43-58, 2002.
[75]Russell R., Hybrid heuristics for the vehicle routing problem with time windows. Transportation Science, 29:156-166, 1995.
[76]Russell R.A., Hybrid heuristics for the vehicle routing problem with time windows. Transportation Science, 29:156-166, 1995.
[77]Russell A. R. and Chiang W.C., Scatter search for the vehicle routing problem with time windows. European Journal of Operational Research, 169:606-622, 2006.
[78]Savelsbergh M., Local search for routing problems with time windows. Annals of Operations research, 4:285-305, 1985.
[79]Schoonderwoerd R., Holland O., Bruten J. and Rothkrantz L., Ant-based load balancing in telecommunications networks. Adaptive Behavior, 5(2): 169-207, 1997.
[80]Schulze J. and Fahle T., Parallel algorithm for the vehicle routing problem with time window constraints. in: Beasley J.E., Sharaiha Y.M, (Eds.) Combinatorial Optimization: Recent Advances in Theory and Praxis. Special issue of Annals of Operations Research, 86:85-607, 1999.
[81]Shaw P., A new local search algorithm providing high quality solutions to vehicle routing problems. Working Paper, Department of Computer Science, University of Strathclyde, Glasgow, Scotland, 1997.
[82]Shaw P., Using constraint programming and local search methods to solve vehicle routing problems. in: Maher M. and Puget J.F. (Eds.), Principles and Practice of Constraint Programming-CP98. in: Lecture Notes in Computer Science. Springer-Verlag, New York, pp.417-431, 1998.
[83]Shyu S.J., Lin B.M.T. and Yin P.Y., Application of ant colony optimization for no-wait flowshop scheduling problem to minimize the total completion time. Computers and Industrial Engineering, 47: 181-193, 2004.
[84]Solimanpur M., Vrat P. and Shankar R., Ant colony optimization algorithm to the inter-cell layout problem in cellular manufacturing. European Journal of Operational Research, 157:592-606, 2004.
[85]Solomon M. M., Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35:254-265, 1987.
[86]Solomon M. M., Baker E. K., and Schaffer J. R., Vehicle routing and scheduling problems with time window constraints: Efficient implementations of solution improvement procedures. In Vehicle Routing: Methods and Studies, Eds B. L. golden and A. A. Assad, North-Holland, Amsterdam, pp.85-105, 1988.
[87]Stützle T. and Dorigo M., ACO algorithms for the quadratic assignment problem. in: Corne D., Dorigo M. and Glover F.(Eds.), New Ideas in Optimization. McGraw-Hill, 1999.
[88]Taillard E., 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, 31:170-186, 1997.
[89]Taillard E.D. and Gambardella L.M., Adaptive memories for quadratic assignment problem. Technical Report IDSIA-87-97, IDSIA, Lugano, Switzerland, 1997.
[90]Talbi E.G., Roux O., Fonlupt C. and Robillard D., Parallel ant colonies for the quadratic assignment problem. Future Generation Computer Systems, 17:441-449, 2001.
[91]Tan K.C., Lee L.H. and Ou K., Artificial intelligence heuristics in solving vehicle routing problems with time window constraints. Engineering Application of Artificial Intelligence, 14:825-837, 2001.
[92]Tan K.C., Lee L.H., Zhua Q.L. and Ou K., Heuristic methods for vehicle routing problem with time windows. Artificial Intelligence in Engineering, 15:281-295, 2001.
[93]Thangiah S.R. and Nygard K., School bus routing using genetic algorithms. Proceedings of the Applications of Artificial Intelligence X: Knowledge Based Systems, Orlando, 1992.
[94]Thangiah S.R., Osman I. and Sun, T. Hybridgenetic algorithm, simulatedannealin g andtabu search methods for vehicle routing problems with time windows. Technical report UKC/OR94/4, Institute of Mathematics andStatistics, University of Kent, Canterbury, UK, 1994.
[95]Thangiah S.R., Osman I.H., Vinayagaoorthy R. and Sun T., Algorithms for vehicle routing problems with time deadlines. American Journal of Mathematical and Management Science, 13(3&4):323-355, 1994.
[96]Thangiah S.R., Osman I.H. and Sun T., Hybrid genetic algorithms, simulated annealing and tabu search methods for vehicle routing problems with time windows. Technical Report UKC/OR94/4, Institute of Mathematics and Statistics, University of Kent, Canterbury, UK, 1995.
[97]Thangiah S.R., Potvin J.Y. and Sun T., Heuristics approaches to vehicle routing with backhauls and time windows. International Journal of Computers and Operations Research, 23(11):1043-1057, 1996.
[98]Thomas D.J. and Griffin P.M., Coordinated supply chain management. European Journal of Operational Research, 94:1-15, 1996.
[99]Verter V., and Dasci A., The plant location and flexible technology acquisition problem. European Journal of Operational Research, 136:366-382, 2002.
[100]Wang W., Richard Y.K. Fung and Chai Y., Approach of just-in-time distribution requirements planning for supply chain management. International Journal of Production Economics, 91:101-107, 2004.
[101]Ying K.C. and Liao C.J., An ant colony system for permutation flow-shop sequencing. Computers and Operations Research, 31:791-801, 2004.
[102]Zhou Z. and Liu Z., Intelligent ant-based algorithm with applications in dynamic routing optimization of telecommunication networks. Telecommunications Science, 14(11):10-13, 1998.