以粒子演算法求解具料品替代特性之兩階生產配送網路規劃問題

A Particle Swarm Algorithm for the Two-stage Production-distribution Network Planning with Item Substitutions

吳美瑩(Mei-Ying Wu)

指導教授 ： 陳宏益

朝陽科技大學/資訊學院/資訊管理系/碩士(2011年)

摘要

過去學者提出一具有料品替代策略的兩階供應鏈規劃模型(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.

並列關鍵字

particle swarm optimization algorithm(PSO) ； item substitution strategy ； supply chain ； production-distribution network

參考文獻

1. 陳淑珍，（2010），“具有料品替代策略的兩階段供應鏈生產-配送網路設計”，碩士論文，台中朝陽科技大學。

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.