[[alternative]]Solving the reverse auction problem by bi-level distributed programming and genetic algorithm

碩士[[abstract]]本研究之目的在針對B2B電子商務環境中一個封閉式、多重議題且為一對多的逆向拍賣(Reverse auction)機制，應用分散式雙層規劃(Bi-level distributed programming)同時考量買方和供應商的利益。為上層買方決定分配給各個供應商的採購數量，並為下層供應商制定適當的投標決策，並結合遺傳演算法做為最佳化搜尋工具，期望可以最小化買方的平均單位競標價格或是交付延遲時間。 模型中包含一標單產生模型，供應商會根據買方所指定的交付時間和所分配到的需求數量，利用主生產排程(MPS)和可允諾量(ATP)存貨的資訊來找出一個最小總生產成本的生產計畫並依此計算其單位成本和競標價格；對於供應商決定競標價格以及買方評估供應商群標單方面則是使用模糊理論的模糊決策方法，以便供應商在決定價格時，能夠同時滿足獲利以及合理定價的目標。本研究最後的實驗以驗證研究目的為主，設定不同的實驗參數，以電腦模擬進行實驗並評估本方法之績效。[[abstract]]This study formulates a model, which applies the bi-level distributed programming to solve a sealed-bid, multiple-issue reverse auction problem that can achieve the objectives of buyer and suppliers simultaneously. This model includes a bid construction model. According to the buyer’s demand, Supplier will find out a production plan based on the master production schedule (MPS) and available-to-promise (ATP) inventory that produces the lowest total production cost. This study also employs the max-min decision approach for the decision making of bidding price on supplier side and the evaluation of suppliers’ bid on buyer side. So suppliers can fulfill the objectives of profit and reasonable price when they make the decision of bidding. A genetic algorithm is developed to solve the model. Through the different parameters setting and computer simulation, the purpose of experiments is to evaluate the performance of the proposed approach and verify the research objective.[[tableofcontents]]III 目錄 第一章 緒論...............................................................................................1 1.1 研究背景與動機...........................................................................1 1.2 研究目的.......................................................................................2 1.3 研究步驟與流程...........................................................................3 第二章 文獻探討......................................................................................5 2.1 電子商務(Electronic Commerce, EC)定義與交易方式.............5 2.2 逆向拍賣(Reverse Auction) .........................................................7 2.3 模糊理論(Fuzzy Logic) ............................................................11 2.3.1 模糊集合與歸屬函數.......................................................12 2.3.2 模糊多目標規劃...............................................................12 2.4 遺傳演算法(Genetic Algorithm ,GA) ........................................13 第三章 研究方法....................................................................................16 3.1 逆向拍賣決策模型的建立........................................................16 3.1.1 模型假設...........................................................................16 3.1.2 變數說明...........................................................................16 3.1.3 模型目標函式...................................................................19 3.2 遺傳演算法.................................................................................27 3.2.1 染色體編碼.......................................................................28 3.2.2 適應性函數.......................................................................28 3.2.3 演算法流程.......................................................................29 3.2.3.1 遺傳演算法流程.....................................................31 3.2.3.2 調整染色體.............................................................35 第四章 實驗與模擬分析........................................................................40 4.1 實驗一.........................................................................................43 4.1.1 實驗參數設計...................................................................43 4.1.2 實驗結果與分析...............................................................44 4.2 實驗二.........................................................................................45 4.2.1 實驗參數設計...................................................................46 4.2.2 實驗結果與分析...............................................................47 4.3 實驗三.........................................................................................51 4.3.1 實驗參數設計...................................................................52 4.3.2 實驗結果與分析...............................................................53 4.4 實驗四.........................................................................................54 4.4.1 實驗參數設計...................................................................55 4.4.2 實驗結果與分析...............................................................56 4.5 實驗五.........................................................................................59 4.5.1 實驗參數設計...................................................................60 4.5.2 實驗結果與分析...............................................................61 第五章 結論與建議................................................................................63 參考文獻...................................................................................................66 圖目錄 圖1-1 研究流程架構圖.............................................................................4 圖2-1 逆向拍賣流程(Cheng, 2008)........................................................10 圖2-2 歸屬函數中模糊目標、模糊限制和模糊決策關係圖...............13 圖3-1 買方對平均單位競標價格( p )的歸屬函數................................21 圖3-2 買方對交付時間延遲( d )的歸屬函數.........................................22 圖3-3 第i 個供應商認為買方最高和最低可以接受的平均單位競標價 格.......................................................................................................24 圖3-4 第i 個供應商對利潤( i π )的歸屬函數.........................................27 圖3-5 染色體範例...................................................................................28 圖3-6 遺傳演算法流程...........................................................................29 圖3-7 二元競賽流程..............................................................................32 圖3-8 字罩交配範例...............................................................................33 圖3-9 單點突變範例...............................................................................34 圖3-10 當最低分配量為2，突變後違反需求分配量限制之範例......36 圖3-11 染色體經交配後違反買方總需求量(Q)限制之範例..............37 圖3-12 調整染色體流程.........................................................................39 圖4-1 不同供應商數量之平均單位競標價格.......................................48 圖4-2 不同供應商數量之平均單位競標價格歸屬度...........................49 圖4-3 不同供應商數量之交付日期.......................................................49 圖4-4 不同供應商數量之交付日期歸屬度...........................................50 圖4-5 不同供應商數量之最終解α 值...................................................50 圖4-6 不同供應商數目之演算法所耗費時間.......................................51 圖4-7 不同延遲上限及供應商數量，平均單位競標價格之變化.......54 圖4-8 不同最低分配量及供應商數量，平均單位競標價格歸屬度之變 化.......................................................................................................58 圖4-9 不同最低分配量及供應商數量，交付時間歸屬度之變化.......58 圖4-10 不同最低分配量及供應商數量，獲選供應商數量之變化.....59 圖4-11 變動訂購成本下，平均單位競標價格歸屬度之變化.............62 圖4-12 變動訂購成本下，最終解中獲選供應商數目之變化.............62 表目錄 表2-1 電子商務交易型態分類(Liang and Hwang, 1998) .......................7 表4-1 每期正規產能產生方式...............................................................41 表4-2 環境設定.......................................................................................42 表4-3 實驗一之遺傳演算法參數設定...................................................44 表4-4 實驗一之買方參數設定...............................................................44 表4-5 Cheng (2009)以最佳化方法所得之最終解.................................45 表4-6 實驗一之三十次最終解之平均結果...........................................45 表4-7 實驗二之遺傳演算法參數設定...................................................47 表4-8 實驗二之買方參數設定...............................................................47 表4-9 實驗二之遺傳演算法參數設定...................................................52 表4-10 實驗二之買方參數設定.............................................................53 表4-11 實驗四之遺傳演算法參數設定.................................................56 表4-12 實驗四之買方參數設定.............................................................56 表4-13 實驗五之遺傳演算法參數設定.................................................61 表4-14 實驗五之買方參數設定.............................................................61[[note]]學號: 696631455, 學年度: 9