应用基因演算法於供应鍊配销设计之多目标最佳化.doc

應用基因演算法於供應鍊配銷設計之多目標最佳化李威昂1 黃志剛21國立雲林科技大學工業工程與管理研究所碩士生雲林縣斗六市大學路三段123號.tw2國立雲林科技大學工業工程與管理研究所教授雲林縣斗六市大學路三段123號摘要：本研究主要在探討供應鏈下配銷最佳化之多目標問題（Multi-objective Problem, MOP），建立一個三目標式之配銷中心供給顧客多項產品的數學模型，此模型考慮成本最小化的配銷中心場址選擇、最佳配給決策、平均各配給中心利用率與達到最大化的服務水準；求解此一多目標數學模型，使用基因演算法（Genetic Algorithm）搜尋多目標柏拉圖邊境最佳解（Pareto Front Optima），多目標之權重處理採用權重平均（Weight-sum）技術決定，在基因演化過程中利用與以往不同的方式進行配給決策，並加入菁英策略（Elite Policy）改善演化績效；最後提出一個數值範例驗證，並對配銷中心設廠數目與產品單位運費作敏感度分析，以確認成效。關鍵字：多目標問題、廠址選擇、柏拉圖最佳解、基因演算法1. 緒論供應鏈是一個由多個上、中、下游廠商所連結形成的一個網路，彼此透過一系列的活動與程序來提供產品或服務給顧客。近年來因為各業市場趨向全球化，各業間的競爭激烈，企業為了提升顧客服務，降低成本提升競爭力，所以逐漸重視供應鏈管理（Supply Chain Management, SCM）。根據Simchi-Levi, Kaminsky, & Simchi-Levi（1999）表示，供應鏈管理是利用一連串有效率的方法，來整合供應商、製造商、倉庫和商店，使得商品能以正確的數量生產，並在正確的時間配送到正確的地點，良好的供應鏈管理可以達到一個令人滿意的服務水準，並使得整體系統成本最小化。而供應鏈管理從長期規劃選擇良好的廠址，到短期的配給策略與最終的提升顧客的服務水準，都是倚賴一個良好的供應鏈網設計；本研究主要探討下游供應鏈配銷中心（Distribution Center, DC）到零售商或顧客此一階段的供應網設計，利用一多目標數學模型，達到最佳配送中心的場址選擇、多樣產品之配給決策與服務水準三項目標式。1.1 供應鍊管理與設計Sunil &Peter （2006）提出，近年來供應鏈管理的主要關鍵議題大略可分為四個層級，（1）策略層級針對企業需求型態下，規劃與設計分佈各地的生產工廠、倉庫的數量、設廠地點、容量或產能以及在SC物流網路中原料的流動，使總生產成本、存貨成本、運輸成本最小化；（2）戰術層級採購、生產、存貨、運輸決策以及顧客關係管理決策等；（3）作業層級短期決策，包括生產排程規劃、運輸路程與卡車載量的規劃；（4）交易處理作業日常交易流程之規劃，例如：訂單的履行流程能有效、正確、快速地完成，以降低處理週期、成本及提升顧客服務水準；供應鏈設計囊括所有層級，也是供應鏈管理中範圍最廣泛的一部分，規劃結果好壞將影響整個供應鏈運作績效。過去關於供應鏈設計的研究眾多，從規劃生產單一產品到多產品、線性數學模型設計到隨機非線性的模式，利用量化的數學模型達成最佳化供應鏈網的設計。規畫模型的目標方程式包含：供應鏈的生產成本最小化，例如：Gen & Syarif（2005）、Sabri & Beamon（2000）與Vidal & Goetschalckx （1997）；設廠成本最小化、配送成本最小化、最大化銷售數量，例如：Sabri et al.（2000）；利潤最大化、顧客滿意度最大化，例如：Fulya, Mitsuo, Lin, & Turan（2006）與Gengui, Hokey, & Mitsuo（2003）；前置期最小化等。設廠成本最小化之規畫通常都是由已知的、可能設廠的位址，相互比較遴選，從中挑出最佳的廠址，例如：Amiri（2006）、Fulya et al.（2006）、Gengui et al.（2003）、Hong, Zhenxin, Edwin（2003）、Pirkul & Jayaraman（1998）、Sabri et al.（2000）與Vidal et al.（1997）。廠址決定後，可再進一步計算各配銷中心與顧客間配送產品的數量，例如：Amiri（2006）、Fulya et al.（2006）、Hong et al.（2003）、Jayaraman & Ross（2003）、Pirkul et al.（1998）、Shing-Hwang, Chih-Chin, & Chih-Hung（2007）與Vidal et al.（1997）。Fulya et al.（2006）之目標式則是考量產能利用率之問題，是以平均各製造工廠與配銷中心產能使用為目標；此外，最末端的服務水準之設計，在此類型的目標方程式設計，則是以最大化補給率、最小化顧客需求反應時間、產品前置期最小化或以限制某一固定運送距離作為滿足服務水準之條件，例如：Fulya et al.（2006）與Gengui et al.（2003）。本研究將以上述三類型的設計考量作為數學模型之目標方程式，即（1）利用中位問題（P-median）的技術，搜尋未知的配銷中心設廠位址，以獲得最佳廠址。並利用配銷中心與顧客間的配送距離作為配送各顧客產品需求之條件，以此方式作為配送決策；（2）將各配銷中心之利用率均衡化，利用平方差（Mean Square Error, MSE）的公式計算各配銷中心利用率的差異，並將其最小化；（3）最大化服務水準，利用配銷中心運送產品到顧客間的距離衡量是否滿足顧客服務水準，若是配送距離在一固定距離內，則可在顧客要求的時間內將產品送達。1.2 多目標問題處理David, David, & Gary（2002）表示多目標問題亦稱多尺度（Multi-criteria）、或多向量（Multi-vector）最佳化問題，以多個決策變數向量滿足限制式，並且最佳化目標方程式，而此目標方程式乃利用數學方程式來表達其欲達成目標之績效尺度，通常要是同時有多個目標方程式，各目標方程式將會相互影響，此類問題則稱為多目標問題。在供應鏈設計之問題中，可以同時考量多個目標以最佳化供應鏈網設計，例如：Sabri et al.（2000）同時考量策略與作業層次的問題，將不確定性產品之採購與交貨策略設計為目標式求解。所謂的多目標最佳化則是取得一個同時滿足多個目標方式之柏拉圖最佳解集合（Pareto-optima Solutions），其意義乃指一個多目標問題通常包含許多個目標，對於每一個目標而言，可以用一個向函表示，而每一個向函則又由許多個所組成，其定義為： 其中:為決策向，為空間，稱目標向，為目標空間。在此解集合內，沒有任何一個解可以在對所有的目標函上皆優於其他的解，則可稱這個解集合為柏拉圖最佳解集合或柏拉圖邊境解（Pareto-frontier Solutions），其中每一個解又可稱為被支配解（Non-dominated Solution），如圖1所示。圖1 柏拉圖邊境解求解多目標最佳化問題的方法，一般可分為四類：（1）傳統數學法；（2）透過各種轉換函數合併成單一目標；（3）模糊多屬性決策法；（4）多目標演化演算法。本研究使用合併多目標的方式進行求解。合併多目標必須先給予個目標式適當的權重，權重評定方式有利用主觀意見的德爾菲法、問卷調查法等，也有較客觀、科學的權重總合技術，例如學者Murata & Ishibuchi（2000）提出的柏拉圖邊境點求解方式；Zhou et al.（1999）提出產生最佳點（Ideal Point）的方式。過去多目標供應鏈網設計問題研究顯示，Murata et al.（2000）提出的方法求解效果良好，比最佳點方式求得更多柏拉圖邊境解，係利用產生亂數的方式決定各目標式的權重，搜尋邊境解時，能讓變數向量平均向柏拉圖邊境散開，求得較多邊境解，本研究即採用此種技術產生目標式權重。1.3 基因演算法基因演算法是利用物競天擇、適者生存生物繁衍原理之演算法，利用隨機的搜尋方式，不斷繁衍出較佳的可行解，可用於求解NP-hard的複雜問題。首先將欲求解的問題變數編碼（Encoding）成一定長度的染色體，設定母體染色體的大小為，再選擇設定交配（Crossover）機率、突變（Mutation）機率與適合度函數（Fitness Function）以評定染色體的好壞。利用交配、突變、選擇歷代（Selection Mechanism）之機制不斷繁衍出更好的染色體，取得適合度高的變數值。Alexandra, Jeremy & Ashutosh（2007）表示基因演算法對於求解多目標問題之效果良好，與其他多目標問題處理技術相較有下列優點：（1） 處理複雜問題時，比起非演化求解方式較不易受變數間相互關係的影響。（2） 在一次演化過程中，可同時求解多個變數、處理多個相關的因子。（3） 可求得多區域最佳解，避免落入區域最佳解。（4） 適用多目標、各目標式相互影響之問題，可求得柏拉圖最佳解集合。（5） 可獲得良好的柏拉圖邊境解集合。Fulya et al.（2006）也使用基因演算法求解多目標供應鏈網設計，結果顯示基因演算法求解優於模擬退火法（Simulated Annealing Algorithm），基因演算法求得的柏拉圖邊境解品質與數量皆較佳。基於上述文獻整理後，訂定本研究步驟，列點如下：（1） 建立多目標下游供應鏈網之數學模型，考慮廠址選擇、配給策略、配銷中心使用率與服務水準，四項供應鏈設計之重要決策。於第2節中詳述。（2） 應用基因演算法於本數學模型求解，介紹染色體編碼、交配、突變與繁衍之機制。於第3節中詳述。（3） 以一36之配銷中心與顧客間關係的數值範例，最後進行配銷中心產能限制與產品單價變動之敏感度分析。於第4節中詳述。（4） 完成結論與後續研究建議。2. 多目標數學模型2.1 模型假設（1） 每位顧客的各項產品需求數量已知。（2） 必須設立的配銷中心數量已知。（3） 每個配銷中心的各類產品最大年配送量相同。（4） 每個顧客的單一產品項由同一個配銷中心配送服務。2.2 符號定義（1） 模型下標索引顧客編號配銷中心編號產品種類編號（2） 模型變數從配銷中心運送產品到顧客的數量（決策變數）配銷中心運送產品給顧客其他狀況（決策變數）由公式計算從配銷中心到顧客的歐基理德直線距離，為配銷中心座標（決策變數），為顧客座標（已知）（3） 模型參數單一配銷中心每年所能供應產品的最大數量（已知）單位產品的單位距離運費（已知）總共需設置幾個配銷中心；由每項產品需求量總和與單一配銷中心每年所能配送該產品最大量代入公式：無條件向上進位為整數求得，即須設廠配銷中心數量（已知）顧客對產品的需求量（已知）配銷中心的設立成本（已知）滿足服務水準要求配送距離（已知）在服務水準內配送距離為以下的顧客集合，在不同情況下，由決策者自行依照實際狀況訂定配送中心與顧客間的配送距離數值，以該批產品配送決定是否屬於此集合（未知）2.3 數學模型（1） 目標方程式：(1)(2)(3)（2） 限制式Subject to(4)(5)(6)(7)(8)目標方程式 (1) 為最小化供應成本，包含設立配銷中心成本與運送成本與數量之決定，式(2) 為平均所有配銷中心利用率，最小化各配銷中心利用率之平方差，使每個配銷中心利用率相同，式(3) 最大化服務水準，設定一固定配送距離作為是否滿足服務水準之衡量，所有配銷中心與顧客間的配送量中，若配送距離小於設定的距離即屬於集合，亦即代表該次配送服務是滿足顧客服務水準要求的服務，將最大化屬於此集合的配送量。限制式 (4) 使每位顧客的同一項產品需求皆由同一個配銷中心配送，式(5) 限制被設立配銷中心之各類產品的最大配送量大於顧客需求量，式(6) 使每位顧客的所有產品需求量皆可被滿足，式(7) 為決定配銷中心服務哪位顧客與產品的二元整數限制，式(8) 為配送量的非負限制式。3. 基因演算求解法（1）（2）（3）3.1 目標方程式權重計算應用合併的方式求解多目標方程式，必須先將各目標式標準化，利用式 (9)：(9)其中：如式 (1)、式 (2) 、式 (3)。再訂定各目標式適當的權重，將目標式轉換成下列型式：其中：為目標式編號，為該目標式權重。權重決定方式，乃採用學者Murata et al.（1999）提出的亂數決定之方式，以平均求得柏拉圖邊境解，其公式如式 (10)： (10)其中：如式 (1)、式 (2) 、式 (3)，為第個目標式相對應的亂數值。亂數決定後即可帶入演算法求解，採用基因演算法進行柏拉圖邊境解搜尋。3.2 染色體編碼染色體編碼乃利用配銷中心座標作為編碼值，搜尋範圍為與，單一配銷中心就有兩個10進位的編碼，分別代表該配銷中心軸座標軸與軸座標，每個配銷中心的與軸座標個數即為染色體之長度，例：圖2配銷中心座標 (13, 84)。1384圖2 染色體編碼3.3 適合度函數計算各隨機產生的配銷中心座標與已知的顧客座標間的距離，在依大小排列作為配銷中心配送優先順序的考量，即可得到，以此作為配送決策；此外，訂定滿足服務水準之限定配送距離，以產生集合，將、代入適合度函數。最後再將隨機產生的三個權重、個別與目標式 (1)、式(2)、式(3) 相乘，得到合併的目標式，如式 (11)：(11)染色體0909692811458染色體1138423013345二元亂數001100染色體0909623011458染色體1138492813345染色體0909692811458YNNNNN099亂數30-染色體0309623811458圖3 染色體交配圖4 染色體突變圖5 本研究基因演算法演化流程3.4 交配染色體交配之機制經測試後，採最佳交配率0.9，再隨機產生交配機率亂數，若小於0.6則依序將染色體倆倆配對，其中交配方式是隨機產生二元整數變數，二元變數為零即採用染色體0的配銷中心或座標，否則採用染色體1的配銷中心或座標，範例如圖3。3.5 突變染色體突變再經過測試後，乃採0.3為最佳突變率，先產生一隨機突變機率亂數，若小於突變率則再產生一亂數其範圍為染色體與座標個數，以決定要讓哪個座標值突變，突變方式是產生隨機亂數取代原座標軸座標，範例如圖4。3.6 演化機制本基因演算法演化過程，初始乃利用亂數產生條染色體，再由俄羅斯輪盤（Roulette Wheel Selection）抽出大小為的染色體個數加入生長池內（Evolving Pool），經過交配與突變之機制，讓這些基因互相競爭生長。其中合併目標式之三項權重在每代繁衍都會不斷改變，以求得平均的柏拉圖邊境解。此外本基因演算法加入菁英策略之觀念，每代繁衍都將目前菁英池內的條菁英解（Elitism Solution）複製2條到生長池內，隨機取代生長池內2條染色體，若是在繁衍過程中搜尋到對各目標方程式較佳的染色體，則將菁英解更新，置換原本的菁英染色體，繼續繁衍不斷蒐集柏拉圖邊境解，直到繁衍20000代為止。整體流程如圖5所示。. 數值範例與敏感度分析本研究使用Simscript.5軟體為基因演算法程式介面，在Intel Pentium4 2.6GB CPU、1GB DDR533 RAM工作平台上操作。4.1 範例求解與分析4.1.1 環境設定a. 搜尋範圍為X與Y軸099之9999平面內；已知六位顧客座標位置，與其三種產品個別之需求量，相關資料整理如表1。b. 各項單位產品之單位距離運送費用為、。.9.10.11.c. 滿足服務水準之距離為搜尋範圍內最長歐基里德直線距離除與配銷中心數量。d. 每個配銷中心各產品的最大配給量為、，設廠成本為。e. 由產品需求量與配銷中心最大年配給量，代入公式（無條件進位），求得所以需配置三個配銷中心。f. 基因演算法內部設定為生長池之染色體大小，交配率，突變率，菁英解數目為3條，每代複製6條菁英解到生長池，取代生長池內染色體，繁衍20000代。g. 每代演化目標式權重由3.1節公式計算。4.1.2多目標方程式標準化使用基因演算法測試三目標方程式之最小值與最大值，測試結果如表2。表1 顧客座標與產品需求量表2 多目標方程式標準化測試編號座標產品需求量1315888 92 99 2894115 91 112 38120106 106 109 412090 97 96 53353113 92 80 6338497 104 112 總計-609 582608編號最小值最大值112096085171820.00260.3703014.1.3範例結果分析求解結果得到五組柏拉圖邊境解，各目標函數值與疊代（Iteration）次數如表3。在達到供應成本最低時（疊代17105次），其服務水準仍可維持在接近95；在各配銷中心利用率達均方差最小時，相對的供應成本就非常高、服務水準也只能達到約83；而在服務水準達到最大值百分之百的時候，可各別求得不錯的供應成本或配銷中心利用率均方差。五組邊境解中，有四組各別達到目標方程式最佳值，疊代第0、8次時，達到第三個目標方程式的最佳值；第126次時，達到第二個目標方程式的最佳值；第17105次時，達到第一個目標方程式的最佳值，三個配銷中心的位置設立地點就坐落於顧客1、3、4的位置上，如圖6。其中第17105、126、8次疊代配銷中心與顧客間最佳配送量與最佳的配銷中心座標如表4、5、6。表3 五組柏拉圖邊境解表4 第17105次疊代之最佳配給決策疊代目標方程式02412870.0370181587390.1832191577020.17600.95001264486250.00260.8260171051209610.19870.9460DC ()座標產品()顧客 ()總計1234561(01,20)1909718729797396962(81,20)111510622129110619731121092213(31,58)1881132012929010428639980112291總計279318321283283313表6 第8次疊代之最佳配給決策表5 第126次疊代之最佳配給決策DC ()座標產品()顧客 ()總計1234561(01,24)19011320329790187396801762(85,20)111510622129110619731121092213(23,69)18897185292104196399112211總計279318321283283313DC ()座標產品()顧客 ()總計1234561(47,36)1881064912921061983991092082(46,11)111590205291971883112962083(54,44)111397210290104194380112192總計279318321283283313圖6 顧客與配銷中心位置圖4.2 敏感度分析考慮與上述數值範例同樣的環境設定下，敏感度分析將考慮下列兩種變化：（1）改變配銷中心的設廠數目限制，分析目標函數值的變動狀況；（2）在單位產品的單位運費增加或減少時，對配銷中心設廠位置與配送決策的影響。在（1）改變配銷中心的設廠數目限制狀況，經過測試後，結果顯示當設立六間配銷中心時，可得到最低的目標函數值，如表7；由此也可證明，在原本的環境設定下，設立六間配銷中心可降低運送成本而使供應成本減少到30000元，各配銷中心的利用率也會更接近，其利用率均方差降到0.02173，也可達到最大的服務水準。表7 配銷中心設廠數改變之最佳供應成本DC個數目標方程式4625810.1507215336110.1231316300000.0217317350000.127861在（2）採取兩種方案與原方案做比較，方案A：單位產品的單位運費增加為產品1為30元、產品2為60元、產品3為90元（、），方案B：單位產品的單位運費減少為為產品1為0.3元、產品2為0.6元、產品3為0.9元（、）。方案A求解結果顯示，其配銷中心的設廠位置幾乎與原方案相同，唯有原本在（81, 20）位置的配銷中心往右下方移動到（83, 16）顧客2與顧客3的中間，沒有坐落在與顧客3同一個位置，但其配送決策則和原方案相同，詳細數據如表8。方案B求解結果顯示，其最佳設廠位置與配給決策和原方案的結果一樣，證明了不管產品單位運費上升或下降，其配銷中心設廠位置與配給決策都已達最佳，詳細數據如表9。表8 方案A之最佳配給決策表9 方案B之最佳配給決策DC ()座標產品()顧客 ()總計1234561(31,58)18811320129290104286399801122912(83,16)111510622129110619731121092213(01,20)190971872979739696總計279318321283283313DC ()座標產品()顧客 ()總計1234561(82,18)111510622129110619731121092212(01,20)1909718729797396963(31,58)1881132012929010428639980112291總計2793183212832833135. 結論下游供應鏈設計在搜尋配銷中心最佳位置時，必須考量到設廠成本與運送費用的考量，以保長期的營運收益，經由本研究模式及基因演算法求解，利用配銷中心與顧客間的距離作為配給決策的準則，可在一固定範圍內搜尋到最佳的設廠位置與配送決策，並且皆可達到極高的服務水準，唯有各配銷中心之利用率會明顯有差異，若要讓各配銷中心的利用率相近，則將造成供應成本的提升。在經過敏感度分析後，更可決定需要增設配銷中心的數目，以避免產品運費造成供應成本過高，衡量運費與設廠的最佳平衡點。此外，也可證明設廠位置與配銷策略是否達到最佳。在未來研究方面，可將本篇數學模型延伸為多階的供應鏈網，並加入產品需求的不確定，做更廣泛的應用。致 謝本研究之完成，感謝國科會（計畫編號：NSC 96-2221-E-224-008）的部分經費補助，謹此致謝。參考文獻1.Amiri, A. (2006). Designing a distribution network in a supply chain system: formulation and efficient solution procedure. European Journal of Operational Research, 171(2), 567576.2.Alexandra, M. B., Jeremy, R., & Ashutosh, T. (2007). An interaction genetic algorithm-based framework for handling qualitative criteria in design optimization. Computers in Industry, 58, 279291.3.David, A., David, A., & Gary, B. (2002). Evolutionary algorithms for solving multi-objective problems. New York: Kluwer Academic/ Plenum Publishers.4.Fulya, A., Mitsuo, G., Lin, L., & Turan, P. (2006). A genetic algorithm approach for multi-objective optima- zation of supply chain networks. Computers & Industrial Engineering, 51, 197216.5.Gen, M., & Syarif, A. (2005). Hybrid genetic algorithm for multi-time period production/distribution planning. Computers and Industrial Engineering, 48(4), 799809.6.Gengui Z., Hokey M., & Mitsuo G. (2003). A genetic algorithm approach to the bi-criteria allocation of customers to warehouses. Int. J. Production Economics, 86, 3545.7.Hong, Y., Zhenxin, Y., Edwin, C. T.C. (2003). Astrategic model for supply chain design with logical constraints: formulation and solution. Computers & Operations Research, 30, 21352155.8.Jayaraman, V., & Ross, A. (2003). A simulated annealing methodology to distribution network design and management. European Journal of Operational Research, 144, 629645.9.Murata, T., Ishibuchi, H.