《应用基因演算法於供应鍊配销设计之多目标最佳化.doc》由会员分享，可在线阅读，更多相关《应用基因演算法於供应鍊配销设计之多目标最佳化.doc（10页珍藏版）》请在金锄头文库上搜索。
1、應用基因演算法於供應鍊配銷設計之多目標最佳化李威昂1 黃志剛21國立雲林科技大學工業工程與管理研究所碩士生雲林縣斗六市大學路三段123號g9521709yuntech.edu.tw2國立雲林科技大學工業工程與管理研究所教授雲林縣斗六市大學路三段123號摘要：本研究主要在探討供應鏈下配銷最佳化之多目標問題（Multi-objective Problem, MOP），建立一個三目標式之配銷中心供給顧客多項產品的數學模型，此模型考慮成本最小化的配銷中心場址選擇、最佳配給決策、平均各配給中心利用率與達到最大化的服務水準；求解此一多目標數學模型，使用基因演算法（Genetic Algorithm）搜尋多
2、目標柏拉圖邊境最佳解（Pareto Front Optima），多目標之權重處理採用權重平均（Weight-sum）技術決定，在基因演化過程中利用與以往不同的方式進行配給決策，並加入菁英策略（Elite Policy）改善演化績效；最後提出一個數值範例驗證，並對配銷中心設廠數目與產品單位運費作敏感度分析，以確認成效。關鍵字：多目標問題、廠址選擇、柏拉圖最佳解、基因演算法1. 緒論供應鏈是一個由多個上、中、下游廠商所連結形成的一個網路，彼此透過一系列的活動與程序來提供產品或服務給顧客。近年來因為各業市場趨向全球化，各業間的競爭激烈，企業為了提升顧客服務，降低成本提升競爭力，所以逐漸重視供應鏈管理
3、（Supply Chain Management, SCM）。根據Simchi-Levi, Kaminsky, & Simchi-Levi（1999）表示，供應鏈管理是利用一連串有效率的方法，來整合供應商、製造商、倉庫和商店，使得商品能以正確的數量生產，並在正確的時間配送到正確的地點，良好的供應鏈管理可以達到一個令人滿意的服務水準，並使得整體系統成本最小化。而供應鏈管理從長期規劃選擇良好的廠址，到短期的配給策略與最終的提升顧客的服務水準，都是倚賴一個良好的供應鏈網設計；本研究主要探討下游供應鏈配銷中心（Distribution Center, DC）到零售商或顧客此一階段的供應網設計，利用一多
4、目標數學模型，達到最佳配送中心的場址選擇、多樣產品之配給決策與服務水準三項目標式。1.1 供應鍊管理與設計Sunil &Peter （2006）提出，近年來供應鏈管理的主要關鍵議題大略可分為四個層級，（1）策略層級針對企業需求型態下，規劃與設計分佈各地的生產工廠、倉庫的數量、設廠地點、容量或產能以及在SC物流網路中原料的流動，使總生產成本、存貨成本、運輸成本最小化；（2）戰術層級採購、生產、存貨、運輸決策以及顧客關係管理決策等；（3）作業層級短期決策，包括生產排程規劃、運輸路程與卡車載量的規劃；（4）交易處理作業日常交易流程之規劃，例如：訂單的履行流程能有效、正確、快速地完成，以降低處理週期、
5、成本及提升顧客服務水準；供應鏈設計囊括所有層級，也是供應鏈管理中範圍最廣泛的一部分，規劃結果好壞將影響整個供應鏈運作績效。過去關於供應鏈設計的研究眾多，從規劃生產單一產品到多產品、線性數學模型設計到隨機非線性的模式，利用量化的數學模型達成最佳化供應鏈網的設計。規畫模型的目標方程式包含：供應鏈的生產成本最小化，例如：Gen & Syarif（2005）、Sabri & Beamon（2000）與Vidal & Goetschalckx （1997）；設廠成本最小化、配送成本最小化、最大化銷售數量，例如：Sabri et al.（2000）；利潤最大化、顧客滿意度最大化，例如：Fulya, Mit
6、suo, 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
7、 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）與Gen
8、gui et al.（2003）。本研究將以上述三類型的設計考量作為數學模型之目標方程式，即（1）利用中位問題（P-median）的技術，搜尋未知的配銷中心設廠位址，以獲得最佳廠址。並利用配銷中心與顧客間的配送距離作為配送各顧客產品需求之條件，以此方式作為配送決策；（2）將各配銷中心之利用率均衡化，利用平方差（Mean Square Error, MSE）的公式計算各配銷中心利用率的差異，並將其最小化；（3）最大化服務水準，利用配銷中心運送產品到顧客間的距離衡量是否滿足顧客服務水準，若是配送距離在一固定距離內，則可在顧客要求的時間內將產品送達。1.2 多目標問題處理David, David,
9、& Gary（2002）表示多目標問題亦稱多尺度（Multi-criteria）、或多向量（Multi-vector）最佳化問題，以多個決策變數向量滿足限制式，並且最佳化目標方程式，而此目標方程式乃利用數學方程式來表達其欲達成目標之績效尺度，通常要是同時有多個目標方程式，各目標方程式將會相互影響，此類問題則稱為多目標問題。在供應鏈設計之問題中，可以同時考量多個目標以最佳化供應鏈網設計，例如：Sabri et al.（2000）同時考量策略與作業層次的問題，將不確定性產品之採購與交貨策略設計為目標式求解。所謂的多目標最佳化則是取得一個同時滿足多個目標方式之柏拉圖最佳解集合（Pareto-opti
10、ma Solutions），其意義乃指一個多目標問題通常包含許多個目標，對於每一個目標而言，可以用一個向函表示，而每一個向函則又由許多個所組成，其定義為： 其中:為決策向，為空間，稱目標向，為目標空間。在此解集合內，沒有任何一個解可以在對所有的目標函上皆優於其他的解，則可稱這個解集合為柏拉圖最佳解集合或柏拉圖邊境解（Pareto-frontier Solutions），其中每一個解又可稱為被支配解（Non-dominated Solution），如圖1所示。圖1 柏拉圖邊境解求解多目標最佳化問題的方法，一般可分為四類：（1）傳統數學法；（2）透過各種轉換函數合併成單一目標；（3）模糊多屬性決策
11、法；（4）多目標演化演算法。本研究使用合併多目標的方式進行求解。合併多目標必須先給予個目標式適當的權重，權重評定方式有利用主觀意見的德爾菲法、問卷調查法等，也有較客觀、科學的權重總合技術，例如學者Murata & Ishibuchi（2000）提出的柏拉圖邊境點求解方式；Zhou et al.（1999）提出產生最佳點（Ideal Point）的方式。過去多目標供應鏈網設計問題研究顯示，Murata et al.（2000）提出的方法求解效果良好，比最佳點方式求得更多柏拉圖邊境解，係利用產生亂數的方式決定各目標式的權重，搜尋邊境解時，能讓變數向量平均向柏拉圖邊境散開，求得較多邊境解，本研究即採
12、用此種技術產生目標式權重。1.3 基因演算法基因演算法是利用物競天擇、適者生存生物繁衍原理之演算法，利用隨機的搜尋方式，不斷繁衍出較佳的可行解，可用於求解NP-hard的複雜問題。首先將欲求解的問題變數編碼（Encoding）成一定長度的染色體，設定母體染色體的大小為，再選擇設定交配（Crossover）機率、突變（Mutation）機率與適合度函數（Fitness Function）以評定染色體的好壞。利用交配、突變、選擇歷代（Selection Mechanism）之機制不斷繁衍出更好的染色體，取得適合度高的變數值。Alexandra, Jeremy & Ashutosh（2007）表示基
13、因演算法對於求解多目標問題之效果良好，與其他多目標問題處理技術相較有下列優點：（1） 處理複雜問題時，比起非演化求解方式較不易受變數間相互關係的影響。（2） 在一次演化過程中，可同時求解多個變數、處理多個相關的因子。（3） 可求得多區域最佳解，避免落入區域最佳解。（4） 適用多目標、各目標式相互影響之問題，可求得柏拉圖最佳解集合。（5） 可獲得良好的柏拉圖邊境解集合。Fulya et al.（2006）也使用基因演算法求解多目標供應鏈網設計，結果顯示基因演算法求解優於模擬退火法（Simulated Annealing Algorithm），基因演算法求得的柏拉圖邊境解品質與數量皆較佳。基於上述
14、文獻整理後，訂定本研究步驟，列點如下：（1） 建立多目標下游供應鏈網之數學模型，考慮廠址選擇、配給策略、配銷中心使用率與服務水準，四項供應鏈設計之重要決策。於第2節中詳述。（2） 應用基因演算法於本數學模型求解，介紹染色體編碼、交配、突變與繁衍之機制。於第3節中詳述。（3） 以一36之配銷中心與顧客間關係的數值範例，最後進行配銷中心產能限制與產品單價變動之敏感度分析。於第4節中詳述。（4） 完成結論與後續研究建議。2. 多目標數學模型2.1 模型假設（1） 每位顧客的各項產品需求數量已知。（2） 必須設立的配銷中心數量已知。（3） 每個配銷中心的各類產品最大年配送量相同。（4） 每個顧客的單一
15、產品項由同一個配銷中心配送服務。2.2 符號定義（1） 模型下標索引顧客編號配銷中心編號產品種類編號（2） 模型變數從配銷中心運送產品到顧客的數量（決策變數）配銷中心運送產品給顧客其他狀況（決策變數）由公式計算從配銷中心到顧客的歐基理德直線距離，為配銷中心座標（決策變數），為顧客座標（已知）（3） 模型參數單一配銷中心每年所能供應產品的最大數量（已知）單位產品的單位距離運費（已知）總共需設置幾個配銷中心；由每項產品需求量總和與單一配銷中心每年所能配送該產品最大量代入公式：無條件向上進位為整數求得，即須設廠配銷中心數量（已知）顧客對產品的需求量（已知）配銷中心的設立成本（已知）滿足服務水準要求配送距離（已知）在服務水準內配送距離為以下的顧客集合，在不同情況下，由決策者自行依照實際狀況訂定配送中心與顧客間的配送距離數值，以該批產品配送決定是否屬於此集合（未知）2.3 數學模型（1） 目標方程式：(1)(2)(3)（2） 限制式Subject to(4)(5)(6)(7)(8)目標方程式 (1) 為最小化供應成本，包含設立配銷中心成本與運送成本與數量之決定，
