過去學者提出一具有料品替代策略的兩階供應鏈規劃模型(Production-Distribution Integer Model with Item Substitution Strategy，PDISS )，此模型希望找到最佳的替代品組合，使得供應鏈的總利潤最大化。現有針對 PDISS 模型的啟發式演算法在求解品質上並不佳也極不穩定。原因之一是這些啟發式演算法，不易做出生產產品的決策，即使供應鏈的供給大於需求，因而導致過多的缺貨損失。
本研究提出一粒子演算法求解PDISS模型的最佳解。利用粒子演算法的優點：記憶性和快速收斂，經過迭代演化後搜尋到空間中的最佳解。此粒子演算法第一步為初始化粒子速度和位置，第二步是將粒子速度和位置評估適應值（Fitness value），第三步則以更新粒子速度和位置反覆修正以達到最佳解，第四步將最佳解轉換成二進制變數，進而表示成替代產品或零件替代的決策。在轉換的過程中，本研究提出兩種轉換機制用以將粒子位置轉成替代決策。之後，回到第二步反覆迭代，以找出 PDISS 模型的最佳解。
在績效評估上，設置大、中、小三種供應鏈規模，以瞭解所提出之粒子演算法在不同大小問題下的績效。評估的績效指標可分為二項：啟發解品質和執行效率。
實驗後，以啟發解品質方面，大供應鏈GAP最佳値為10.58%，最差値為14.26%；中供應鏈GAP最佳値為4.40%，最差値為4.98%；小供應鏈GAP最佳値為9.30%，最差値為9.56%。而在執行時間方面，大供應鏈IMP最佳値為82.743，最差値為39.086；中供應鏈IMP最佳値為1.64，最差値為0.693；小供應鏈IMP最佳値為0.006，最差値為0.003。

A Production-Distribution Integer Model with Item Substitution Strategy（PDISS）has been proposed in the supply chain literature. The model aims to find optimization combinations of item substitutions in order to maximize the total profit on supply chain. Existing heuristic algorithms for the PDISS model have lots rooms to improve in terms of the solution quality and the stability of the solution quality. The main reason that leads to poor solution quality for existing heuristic algorithm is that the algorithms often decide not to produce products even though the supply over the demand, which leads to excessive stock out penalty.
This study proposes a Particle Swarm Optimization（PSO）algorithm to solve PDISS model. PSO algorithms feature with memorization and fast convergence to iteratively search optimal solution in problem space. The first step of the proposed PSO is to initializes the velocity and position of each particle. The second step is to evaluate each particle’s fitness according to its position in the problem space. The third step updates velocity and position of each particle considering the global and personal best positions. The fourth step converts each particle’s position to a solution in the problem space that represents decisions for substituting products and components. In this step, this study proposes two mechanisms for the conversion. After the step four, the PSO algorithm goes back to step two and iterate until a stop condition is met.
Three sizes of supply chain are established for evaluating the proposed PSO algorithm. Two performance indexes are considered: the solution quality, and the computation time. The optimal solutions of the PDISS problem instances will be used as benchmarks for obtaining the performance indexes. Lingo optimization software will be used to solve the PDISS problem instances.
Experiment results showed that the best GAP value was 10.58% and the worst value was 14.26% for the large supply chain; the best GAP value was 4.40% and worst value was 4.98% for the middle supply chain; the best value was 9.30% and worst value was 9.56% for the small supply chain. As for the computation time, the best IMP value was 82.743 and worst value is 39.086 in
III
the large supply chain for the large supply chain; the best value was 1.64 and worst value was 0.693 for the middle supply chain; the best value was 0.006 and worst value was 0.003 for small supply chain.

摘要 I
Abstract II
致謝 IV
目錄 V
表目錄 IX
圖目錄 XI
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 論文架構 2
第二章 文獻回顧 5
2.1 具有料品替代策略的兩階供應鏈整數規劃（PDISS）模型 6
2.2 粒子演算法（PSO）背景 8
2.3 慣性權重相關文獻 10
2.4 利用粒子演算法（PSO）解離散問題相關文獻 11
2.5 粒子速度更新與轉換機制相關文獻 11
2.5.1 粒子速度更新 12
2.5.2 轉換機制 15
2.6 粒子參數設定 18
2.7 結論 19
第三章 研究方法 21
3.1 粒子演算法（PSO）架構 21
3.2 粒子位置與替代決策之對映關係 24
3.3 更新粒子速度和粒子位置 25
3.4 轉換機制 26
3.4.1 粒子位置之轉換 26
3.4.2 單一替代限制規則檢查與遵守 27
3.5 適應值評估機制 28
第四章 實驗設計及績效評估 29
4.1 績效評估之環境 29
4.2 實驗結果 33
4.2.1 啟發解品質績效 33
4.2.2 計算時間績效 39
4.2.3 影響啟發解績效之因素 44
4.3 演算法評估比較 54
4.3.1 啟發解品質比較 54
4.3.2 執行時間比較 57
4.4 結論 60
第五章 結論與未來研究方向 62
5.1 結論 62
5.2 未來研究方向 63
參考文獻 64
附錄（一） 68
1.1 環境假設 68
1.2 數學符號定義 69
1.2.1 下標定義 69
1.2.2 參數定義 70
1.2.3 決策變數定義 71
1.3 具有料品替代策略的兩階供應鏈整數規劃（PDISS）模型 71
1.3.1 目標函數 74
1.3.1.1 總銷售收入 74
1.3.1.2 零件訂購總成本 74
1.3.1.3 零件運輸總成本 75
1.3.1.4 零件存貨總成本 75
1.3.1.5 產品製造總成本 76
1.3.1.6 產品運輸總成本 77
1.3.1.7 總缺貨損失 77
1.3.1.8 目標函數總利潤最大化 78
1.3.2 限制式 78
1.3.2.1 供應商限制式 78
1.3.2.2 裝配廠限制式 79
1.3.2.3 配銷中心限制式 81
1.3.2.4 替代限制式 83


表目錄
表3.1.1定義符號 24
表4. 1供應鏈範圍大小定義 30
表4. 2參數的設定範圍 31
表4. 3轉換機制分類 32
表4. 4 大供應鏈、單一門檻範圍之GAP 34
表4. 5大供應鏈、多門檻間隔之GAP 35
表4. 6中供應鏈、單一門檻範圍之GAP 36
表4. 7中供應鏈、多門檻間隔之GAP 37
表4. 8小供應鏈、單一門檻範圍之GAP 38
表4. 9小供應鏈、多門檻間隔之GAP 39
表4. 10大供應鏈、單一門檻範圍之IMP 40
表4. 11大供應鏈、多門檻間隔之IMP 41
表4. 12中供應鏈、單一門檻範圍之IMP 41
表4. 13中供應鏈、多門檻間隔之IMP 42
表4. 14小供應鏈、單一門檻範圍之IMP 43
表4. 15小供應鏈、多門檻間隔之IMP 44
表4. 16啟發解品質變異數分析 45
表4. 17 供應鏈對啟發解品質的多重比較 47
表4. 18 大供應鏈與單一門檻之80與100粒子個數GAP 48
表4. 19啟發解執行時間變異數分析 49
表4. 20供應鏈對啟發解執行時間的多重比較 51
表4. 21粒子個數大小對啟發解執行時間的多重比較 52
表4. 22大供應鏈中演算法比較之結果 55
表4. 23中供應鏈中演算法比較之結果 56
表4. 24小供應鏈中演算法比較之結果 57
表4. 25大供應鏈中演算法比較之結果 58
表4. 26中供應鏈中演算法比較之結果 59
表4. 27小供應鏈中演算法比較之結果 60

圖目錄
圖1. 1論文架構圖 4
圖2. 1文獻回顧 6
圖3.1.1架構流程 22
圖4. 1供應鏈對啟發解品質的影響 46
圖4. 2供應鏈大小對啟發解執行時間的影響 50
圖4. 4供應鏈大小*粒子個數大小對啟發解執行時間的影響 53
附錄（一）圖1. 1生產-配送網路圖 68

1.陳淑珍，（2010），“具有料品替代策略的兩階段供應鏈生產-配送網路設計”，碩士論文，台中朝陽科技大學。
2.崔紅梅和朱慶保，（2007），“微粒群算法參數選擇及收斂分析”，計算機工程與運用，Vol.23，pp.89-91.。
3.Ai, T. J. & Kachitvichyanukul, V. (2009), “A Particle Swarm Optimization for the Vehicle Routing Problem with Simultaneous Pickup and Delivery”, Computers and Operations Research., Vol.36, pp.1693-1702.
4.Anghinolfi, D. & Paolucci, M. (2009), “A New Discrete Particle Swarm Optimization Approach for the Single-machine Total Weighted Tardiness Scheduling Problem with Sequence-dependent Setup Times.”, European Journal of Operational Research., Vol.193, pp.73-85.
5.Angeline, Peter J. (1998), “Using Selection to Improve Particle Swarm Optimization”, The 1998 IEEE International Conference on, pp.84 - 89.
6.Clerc, M. (1999), “The Swarm and the Queen: Towards a Deterministic and Adaptive Particle Swarm Optimization.”, Proc. of 1999 Congress on Evolutionary Computation., pp.1951 - 1957.
7.Davis, L. D. (1991), Handbook of Genetic Algorithms, Van Nostrand Reinhold..
8.He, S.; Wua, Q.; Wena, J.; Saunders, J. & Paton, R. (2004), “A Particle Swarm Optimizer with Passive Congregation.”, BioSystems, Vol.78, pp.135-147.
9.Jin, Y.-X.; Cheng, H.-Z.; yong Yan, J. & Zhang, L. (2007), “New Discrete Method for Particle Swarm Optimization and its Application in Transmission Network Expansion Planning.”, Electric Power Systems Research, Vol.77, pp.227-23.
10.Kennedy, J. & Eberhar, R. C. (1995), “Particle Swarm Optimization.”, Proc. IEEE International Conference on Neural Networks., pp.1942-1948.
11.Kennedy, J. & Eberhar, R. C. (1995), “A New Optimizer Using Particle Swarm Theory.”, Proceedings Sixth International Symposium on Micro Machine and Human Science,, Japan.
12.Kennedy, J. & Eberhart, R. C. (1997), “A Discrete Binary Version of The Particle Swarm Algorithm.”, Proc. of 1997 IEEE International Conference on Computational Cybernetics and Simulation,, pp.4104-4108.
13.Kong, M. & Tian, P. (2006), “Apply the Particle Swarm Optimization to the Multidimensional Knapsack Problem.”, Lecture Notes in Computer Science, Vol:4029, pp.1140-1149.
14.Liang, Y.; Shi, X.; Leeb, H.; Lu, C. & Wang, Q. (2007), “Particle Swarm Optimization-based Algorithms for TSP and Generalized TSP.”, Information Processing Letters, Vol.103, pp.169-176.
15.Liao, C.-J.; Tseng, C.-T. & Luarn, P. (2007), “A Discrete Version of Particle Swarm Optimisation for Flowship Seheduling Problems.”, Computers & Operations Research, Vol.34, pp.3099-3111.
16.Marinakis, Y.; Marinaki, M. & Dounias, G. (2010), “A Hybrid Particle Swarm Optimization Algorithm for The Vehicle Routing Problem.”, Engineering Applications of Artificial Intelligence, Vol.23, pp.463-472.
17.Parrish, J. & Hamner, W. (1997), “Animal Groups in Three Dimensions.”, Cambridge University Press, Cambridge, UK.
18.Pongchairerks, P. & Kachitvichyanukul, V. (2009), “A two-level Particle Swarm Optimisation algorithm on Job-Shop Scheduling Problems.”, International Journal of Operational Research, Vol. 4, pp. 390 - 411.
19.Sahu, H.; Mahapatra, S.; Sirikasemsuk, K. & Panigrahi, D. (2010), “A Discrete Particle Swarm Optimization Approach for Classification of Indian Coal Seams with Respect to Their Spontaneous Combustion Susceptibility.”, Fuel Processing Technology,, No of Pages 7.
20.Sha, D. & Hsu, C.-Y. (2006), “A Hybrid Particle Swarm Optimization for Job Shop Scheduling Problem.”, Computers & Industrial Engineering, Vol.51, pp.791-808.
21.Sha, D. Y.; Lin, H.-H. & Hsu, C.-Y. (2010), “A Modified Particle Swarm Optimization for Multi-objective Open Shop Scheduling.”, Proc. of the International MultiConference of Engineers and Computer Scientists, 3.
22.Shi, Y. H. & Eberhart, R. C. (2001), “Tracking and Optimizing Dynamic Systems with Particle Swarms.”, Proc. of the 2001 Congress on Evolutionary Computation,, pp.94-100.
23.Shi, Y. H. & Eberhart, R. C. (2000), “Comparing Inertia Weights and Constriction Factors in Particle Swarm Optimization.”, Proc. of the 2000 Congress on Evolutionary Computation, Vol. 1, pp. 84-88.
24.Shi, Y. H. & Eberhart, R. C. (1999), “Empirical Study of Particle Swarm Optimization.”, Proc. of the 1999 Congress on Evolutionary Computation, Vol.3, pp.1945-1950.
25.Shi, Y. H. & Eberhart, R. C. (1998), “A Modified Particle Swarm Optimizer.”, Proc. of 1998 IEEE International Conference on Evolutionary Computation, pp.69-73.
26.Shi, Y. H. & Eberhart, R. C. (1998), “Parameter Selection in Particle Swarm Optimization.”, Proc. EP98: The 7 th Ann. Conf. on Evolutionary Programming, pp.591 - 600.
27.Shi, Y. H. & Eberhart, R. C. (1998), “Comparison between Genetic Algorithms and Particle Swarm Optimization.”, Proc. of 1998 Annual Conference on Evolutionary Programming.
28.Tasgetiren, M. F.; Liang, Y.-C.; Sevkli, M. & Gencyilmaz, G. (2007), “A Particle Swarm Optimization Algorithm for Makespan and Total Flowtime Minimization in the Permutation Flowshop Sequencing Problem.”, European Journal of Operational Research, Vol.177, pp.1930-1947.
29.Unler, A. & Murat, A. (2010), “A Discrete Particle Swarm Optimization Method for Feature Selection in Binary Classification Problems.”, European Journal of Operational Research Vol.206, pp.528-539.
30.Wu, B.; Zhao, Y.; Ma, Y.; Dong, H. & Wang, W. (2004), “Particle Swarm Optimization method for Vehicle Routing Problem.”, Intelligent Control and Automation, WCICA 2004. Fifth World Congress on, Vol.3, pp.2219 - 2221.
31.Yang, Q.; Sun, J.; Zhang, J. & Wang, C. (2006), “A Hybrid Discrete Particle Swarm Algorithm for Hard Binary CSPs.”, Lecture Notes in Computer Science, Vol.4222, pp.184-193.
32.Zheng, Y.-l.; Ma, L.-h.; Zhang, L.-y. & Qian, J.-x. (2003), “Empirical Study of Particle Swarm Optimizer with an Increasing Inertia Weight.”, Proc. of IEEE Congress on Evolutionary Computation 2003(CEC 2003),, pp.221-226.