整合遺傳演算法與粒子群最佳化演算法於二階線性規劃問題之應用－以供應鏈之配銷模型為例

Integration of Genetic Algorithm and Particle Swarm Optimization for Bi-level Linear Programming－ A Case Study on Supply Chain Distribution Model

韓永祥(Yung-Shian Han)

指導教授 ： 郭人介

國立臺北科技大學/管理學院/工業工程與管理研究所/碩士(2008年)

https://doi.org/10.6841/NTUT.2008.00334

摘要

二階線性規劃擁有階層式的關係，所以許多研究將其應用在組織上下階層關係的最佳決策模式，這種階層式的決策問題可以經由多階的數學規劃來進行模擬。希望利用供應鏈體系的串聯，可以得到最佳的資源分配，以達到降低生產、存貨以及配送等成本，增加供應鏈效率和協調的目標。
粒子群最佳化演算法具有模仿生物群體依賴相似特性之群體智慧的概念方法及粒子經驗交換及傳承世代之演算模式，其利用粒子族群具有探測與開發的特色，可用於搜尋全域的最佳解。而遺傳演算法則是模擬生物在環境中遺傳以及進化過程而形成的一種全域最佳化演算法，利用「選擇」、「交配」及「突變」。透過此三個操作過程的演化，達到「適者生存」。本研究利用遺傳演算法中的交配以及突變的演算流程，導入粒子群最佳化演算法以改善提前掉進區域解的缺點，有效結合遺傳演算法全域搜尋的特性和粒子群最佳化演算法局部的搜尋能力，在有效避免提前收歛的同時，提高求解問題的精確度。
本研究利用四個例題來驗證求解的可行性，結果說明了本研究所提出的方法較遺傳演算法以及粒子群最佳化演算法來的優異。並且將二階規劃應用在供應鏈當中，藉由整合遺傳演算法與粒子群演算法來求取最佳解，從中了解製造商與供應商之間的存貨關係，結果顯示改良式粒子群最佳化演算法比遺傳演算法以及粒子群最佳化演算法具有更優異的表現。

關鍵字

二階規劃 ； 線性規劃 ； 供應鏈 ； 粒子群最佳化演算法 ； 遺傳演算法

並列摘要

Bi-level linear programming problems have the hierarchical relationship between upper and lower levels. Thus, many researches applied it to make the best decision with the upper-and-lower hierarchical relationships in the organizations. Basically, the hierarchical decision problems can be simulated by multi-level mathematical programming. This research attempts to use collaboration function of supply chain systems to obtain the best resource distribution. This can result in reducing production, inventory and distribution costs and increasing the efficiency and the coordination of supply chain partners.
Particle Swarm Optimization (PSO) method can mimic cooperation between individuals in the same group by using swarm intelligence and exchange experiences from generation to generation. There are some advantages to exploit and explore the hyperspace global optimum with PSO method, especially the fast convergence. On the other hand, Genetic algorithm (GA) is a global optimization algorithm by mimic heredity and process of evolution in environment. It uses three operating process that are selection, crossover and mutation to be survival of the fittest. Because of the characteristics of GA and PSO, this research attempts to improve the drawback of falling into the local solution by making use of the crossover and mutation of algorithm process into PSO. Moreover, it can effectively integrate the characteristic of global search in GA and the capability of local search in PSO to avoid converging ahead of time and to raise the accuracy of problem solving.
Four problems adopted from the references are used to testify the proposed methods’ feasibility. The results demonstrate that the proposed method is able to provide better performance than GA and PSO. In addition, this research also employs the proposed method which integrates both GA and PSO to solve the bi-level linear programming problem in the supply chain. The main purpose is to collaboratively arrange the inventory between suppliers and manufacturing center. The experimental results show that the proposed method also has better performance than GA and PSO.

並列關鍵字

bi-level programming ； linear programming ； supply chain ； PSO ； GA

參考文獻

[5]邱宇婷，應用粒子群最佳化演算法於關聯法則資料探勘之研究，國立台北科技大學工管所，碩士論文，2006。

[7]祝志堅，資訊網路應用對供應鏈管理影響之探討：以零售服務業為例，碩士論文，元智大學管理研究所，1998。

[9]葉思緯，應用粒子群最佳化演算法於多目標存貨分類之研究，碩士論文，元智大學工業工程與管理學系，桃園，2004。

[10]葉麗雯，供應商產能有限及價格折扣下多產品多供應商最佳化採購決策，碩士論文，元智大學工業工程與管理學系，桃園，2002。

[12]廖慧凱，道路災害搶修與緊急物流配送問題之探討，碩士論文，國立中央大學土木工程所，2006。