第一組第二次

藥品配送網(wǎng)絡(luò)研究

組員：演講人：目錄問題一的問題分析與模型求解問題一的結(jié)果分析問題二的問題分析與模型求解問題二的結(jié)果分析問題三的問題分析與模型建立與求解問題三的結(jié)果分析本次題目求解的改進(jìn)與缺乏一、問題一的問題分析與模型求解1.1、問題的理解與分析題目：

建立合理的數(shù)學(xué)模型，討論車輛往各藥品配送中心分配的最優(yōu)方案；1.首先得考慮每個配送中心對于周邊感染區(qū)的總體的藥品供給能力和范圍，并將其作為各配送中心的重要性指標(biāo)來分配車輛.2.利用K均值聚類分析的方法將感染區(qū)按到3個配送中心的距離劃分給每個配送中心.3.采用秩和比綜合評價法，在評價指標(biāo)的設(shè)置上結(jié)合題目所給的調(diào)查數(shù)據(jù)，將每個配送中心周邊區(qū)域的感染區(qū)一些相關(guān)特征值平均數(shù)以及各配送中心的最大儲存量作為這3個配送中心的重要性評價指標(biāo).問題假設(shè)假設(shè)3個藥品配送中心收到感染區(qū)發(fā)出的藥品求助的時間忽略不計，記為0.假設(shè)藥品運輸車輛收到通知后馬上出發(fā)，準(zhǔn)備時間為0.假設(shè)藥品運輸車在運輸?shù)耐局胁粫l(fā)生意外事故，如車輛出現(xiàn)故障.假設(shè)車輛在各出發(fā)點及各到達(dá)點間均按直線行駛，各路線的路況相同，且每輛車的在運輸途中的平均速度相同，都為5.2kM/h.1.2、模型的建立與求解

1.K均值聚類劃分配送中心的配送區(qū)域2.秩和比綜合評價法求配送中心的權(quán)重3.建立目標(biāo)規(guī)劃模型分配車輛K均值聚類劃分配送中心的配送區(qū)域在n維歐氏空間中聚類，本文將以組內(nèi)的相似度為依據(jù),采用歐氏距離作為判斷相似度的標(biāo)準(zhǔn),即距離越近相似度越大,距離越遠(yuǎn)相似度越小.設(shè)聚類的數(shù)目為k那么分組的數(shù)目為k組.設(shè)n個點的集合,將聚為k類，那么有

其中代表聚類分析中心.按照K均值聚類算法的步驟，對98個感染區(qū)域聚類如下：1〕以3個配送中心為初始聚類中心，k=3；2〕將98個感染區(qū)的點按如下方式聚類:對點當(dāng)且僅當(dāng)才歸為聚類3〕計算新的聚類中心其中

為聚類中的元素個數(shù);4〕如果各個聚類不再改變,那么終止;否那么轉(zhuǎn)(2).5〕輸出聚類的結(jié)果流程圖秩和比綜合評價法求配送中心的權(quán)重一、秩和比綜合評價法原理及步驟編秩計算秩和比

計算概率單位

計算直線回歸方程

分檔排序二、秩和比法求各藥品配送中心的權(quán)重1.秩和比評價指標(biāo)確實定以3個配送區(qū)域內(nèi)的感染區(qū)的總體對于配送中心的需求程度以及配送中心自身的最大儲存量為評價指標(biāo)，來為下一步利用秩和比法確定各藥品配送中心的重要性程度做準(zhǔn)備.將各配送區(qū)域內(nèi)的感染區(qū)的藥品需求量、藥品到達(dá)最遲時間、點內(nèi)距離、配送車輛最少停留時間的平均數(shù)作為總體來衡量該藥品配送中心的評價指標(biāo)2.各藥品配送中心的權(quán)重經(jīng)過秩和比排序，我們可以得到3個配送中心的在車輛分配時的權(quán)重值，即分別為1/3、3/10、11/30.建立目標(biāo)規(guī)劃模型分配車輛目標(biāo)函數(shù)：

約束條件：使每個配送中心分配到車輛的總?cè)萘勘M量到達(dá)其最大儲存量，即使這兩者的方差在加權(quán)〔權(quán)重值為〕的條件下最小化分配到藥品配送中心的車輛總?cè)萘坎怀^配送中心的最大藥品儲存量，否那么會造成資源浪費的現(xiàn)象各類車輛數(shù)量限制利用Lingo求解目標(biāo)函數(shù)得到分配到3個藥品配送中心的具有120件和150件容量的2種藥品運輸車輛的個數(shù)分別為：0、3；2、1；3、1二、問題二的問題分析與模型求解2.1、問題的理解與分析對于多中心配送路線和車輛調(diào)度問題，一般是先把需求源按距離分配到車場〔即藥品配送中心〕，然后轉(zhuǎn)化成多個單車場車輛路徑問題的求解.車輛路徑問題是個NP-hard問題，通過處理后可以轉(zhuǎn)化為求解最優(yōu)排列的問題，蟻群算法在求解路徑尋優(yōu)問題上具有明顯優(yōu)勢.因此可以在第一問劃分了配送區(qū)域的根底上，利用蟻群算法分別求解每個配送中心的車輛配送方案，以使得在最大程度上滿足配送區(qū)域內(nèi)的感染區(qū)域的需求量的前提下，藥品運輸車輛運輸?shù)穆窂阶疃蹋?車輛路徑問題目標(biāo)模型的建立2.2、模型的建立與求解對單車廠〔配送中心〕多車型滿載車輛調(diào)度問題，我們可以建立多目標(biāo)規(guī)劃模型如下：總費用最小為目標(biāo)車輛的運量不大于車輛的容量車對每個感染區(qū)只訪問一次車的路線是個回路所有車輛所經(jīng)過點的數(shù)量不超過感染區(qū)的數(shù)量要滿足感染區(qū)的最晚時間蟻群算法求解每個配送區(qū)域的車輛調(diào)配問題蟻群算法求解車輛路徑算法如下：〔1〕初始化數(shù)據(jù)〔2〕設(shè)置終止條件，當(dāng)不滿足終止條件時循環(huán)進(jìn)行以下三個步驟，直到終止條件得到滿足.〔3〕構(gòu)造路徑〔4〕更改路徑〔5〕更改信息素其中，s表示節(jié)約量，c表示本錢，o表示配送中心，i，j表示感染區(qū).1.采用節(jié)約螞蟻系統(tǒng)構(gòu)造路徑；計算每兩個感染區(qū)間的節(jié)約量，表示合并兩個感染區(qū)到一條路徑上能夠節(jié)約的本錢計算轉(zhuǎn)移概率

，表示螞蟻在到達(dá)感染區(qū)i之后選擇感染區(qū)j的可能性大小最后，讓螞蟻根據(jù)所求的概率分兩個階段進(jìn)行路徑搜索；第一個階段從起點感染區(qū)搜索配送中心；第二個階段從送中心搜索起點感染區(qū)、選擇感染區(qū)其中

表示信息素；

表示節(jié)約量；

α

、

β

表示兩個參數(shù)，分別用來表示信息素和節(jié)約量的重要性.2.采用2-opt局部搜索算法提高解的性能.在螞蟻完成路徑構(gòu)造之后，對每條路徑采用2-opt算法提高解的性能；不斷交換兩條邊，直到不能提高解的性能為止.3.更新信息素在所有的螞蟻完成路徑構(gòu)造之后，根據(jù)公式對信息素進(jìn)行更新.4.如果存在指令，不滿足容量限制，那么認(rèn)為在當(dāng)前不能將循環(huán)體成功調(diào)度，重新開始調(diào)度.蟻群算法求解的結(jié)果2.3、結(jié)果分析

三、問題三的問題分析與模型求解3.1、問題的理解與分析從問題二的結(jié)果得知當(dāng)總的藥品運輸車輛只有10輛時，每個配送區(qū)域都存在局部感染區(qū)沒有被運送到，此時我們需要增加車輛以滿足所有感染區(qū)藥品的需求.在問題一求得的每個配送中心的不同型號車輛數(shù)的前提下，在3個配送區(qū)域增加車輛，每增一輛車后，利用問題二的求解方法求出現(xiàn)有車輛的最優(yōu)路徑方案.假設(shè)仍有局部感染區(qū)沒有藥品輸送，那么再添加一輛車，直到所有的感染區(qū)的藥品需求到達(dá)滿足.由于條件所給的每種車型在費用上沒有任何區(qū)別，因此在增加車輛型號的選擇上，我們優(yōu)先選擇容量為150件的車進(jìn)行藥品配送.3.2、模型的建立與求解通過問題二的求解，我們可以從圖中可以看出，在只有10輛藥品運輸車的情況下，在3個配送區(qū)域內(nèi)都仍有局部感染區(qū)的藥品需求量得不到滿足，因此我們需要增加藥品運輸車.由題目所給的條件下可知120件容量和150件容量的藥品運輸車在運輸費用上沒有任何差異.在問題二中存在每種車型的數(shù)量限制，而在此題中，在現(xiàn)有的5輛120件容量和5輛150件容量的車輛數(shù)的前提上，對新增的不同型號車輛數(shù)沒有任何限制，因而在需要增加車輛時，我們只考慮增加150件容量的藥品運輸車.在問題二中利用蟻群算法求解給定運輸不同型號車輛的數(shù)量的條件下的車輛運輸?shù)淖顑?yōu)路徑，可以做出如下改進(jìn)：〔1〕分別判斷每個配送區(qū)域是否存在感染區(qū)未到達(dá)藥品需求量，即在原車輛配送路徑中是否存在沒有經(jīng)過的感染區(qū)域.假設(shè)不存在，那么結(jié)束算法，無需新增藥品運輸車輛；〔2〕假設(shè)存在，那么給該配送中心增加一輛150件容量的藥品運輸車；〔3〕在新增車輛后，假設(shè)全部車輛能滿載那么滿載，假設(shè)當(dāng)滿載時超過配送中心的最大存儲量那么新增車輛只需裝載配送中心的剩余的存儲藥品；〔4〕利用問題二中蟻群算法求解最優(yōu)的車輛運輸路徑，回到〔1〕.于此同時，我們結(jié)合問題一可知，每個配送中心的120件容量