城市物流配送方案優(yōu)化模型-數(shù)學(xué)建模.docx

天津大學(xué)數(shù)學(xué)建模選拔賽 題 目 城市物流配送方案優(yōu)化設(shè)計 摘 要所謂物流配送就是按照用戶的貨物（商品）訂貨要求和物流配送計劃，在物流配送節(jié)點進(jìn)行存儲、分揀、加工和配貨等作業(yè)后，將配好的貨物送交收貨人的過程。本文就如何設(shè)計該城市的配送方案和增設(shè)新的配送網(wǎng)點并劃分配送范圍展開討論。第一問中，首先，在設(shè)計合理的配送方案時，我們要知道評價一個配送方案的優(yōu)劣需考慮哪些指標(biāo)。根據(jù)層次分析法所得各指標(biāo)的權(quán)重及各因素之間關(guān)系可知：合理的配送方案需要優(yōu)化貨車的調(diào)度以及行駛路線。然后，根據(jù)該城市的流配送網(wǎng)絡(luò)路網(wǎng)信息以及客戶位置及需求數(shù)據(jù)信息，用EXCEL進(jìn)行數(shù)據(jù)統(tǒng)計并用matlab繪制物流信息圖，在圖中可以清晰地看出客戶位置密集和稀疏的區(qū)域。之后，我們運用雷達(dá)圖分割法將城市分為20個統(tǒng)籌區(qū)（以及100個二級子區(qū)域）。接著，我們針對一個二級子區(qū)域分析貨車行駛的最佳路線。利用聚類分析和精確重心法在二級子區(qū)域N1中設(shè)置了7個卸貨點，該目標(biāo)區(qū)域內(nèi)的用戶都將在該區(qū)域的卸貨點取貨。我們利用圖論中的Floyd算法和哈密爾頓圈模型求解往返最短路線問題，得知最短路線為 ，最短路程為84.4332KM，最短運貨用時為2.11小時。最后，根據(jù)用戶位置和需貨量，計算出貨車數(shù)量和車次，并給出了其中一種合理的針對整個城市的貨車調(diào)度配送方案。 第二問中，我們建立了多韋伯模型，通過非線性0-1規(guī)劃，確定了城市增加的5個分配中心的位置以及各自的分配送范圍。配送中心位置結(jié)果如下：配送中心編號經(jīng)度緯度3108.056801526.717164454108.67965126.96689015108.689218525.97394826109.211669326.895898637109.174977326.1636702原配送中心107.97255461516226.6060305362822關(guān)鍵詞：層次分析法 聚類分析 精確重心法 Floyd算法 哈密爾頓圈 多韋伯模型評閱編號 （由組委會填寫）一問題重述配送是指在經(jīng)濟合理區(qū)域范圍內(nèi)，根據(jù)客戶要求，對物品進(jìn)行揀選、加工、包裝、分割、組配等作業(yè)，并按時送達(dá)指定地點的物流活動，即按用戶定貨要求，在配送中心或其它物流結(jié)點進(jìn)行貨物配備，并以最合理方式送交用戶。配送是從用戶利益出發(fā)、按用戶要求進(jìn)行的一種活動，因此，在觀念上必須明確“用戶第一”，把用戶利益作為設(shè)計配送方案時首先要考慮的問題。城市的配送系統(tǒng)不但要考慮企業(yè)自身和用戶的利益，也應(yīng)從公眾利益出發(fā)，盡量減少交通擁擠和廢物排放。這無疑更增加了配送系統(tǒng)管理的難度，有效解決該問題對于改善城市出行環(huán)境和提高企業(yè)服務(wù)水平具有重要意義?；谝陨媳尘?，為某企業(yè)設(shè)計其配送方案，建立數(shù)學(xué)模型分析如下問題：（1）假設(shè)該公司在整個城區(qū)僅有一個配送中心（107.972554615162，26.6060305362822）。附件1中給出了企業(yè)顧客位置和需求數(shù)據(jù)。附件2為配送網(wǎng)絡(luò)路網(wǎng)信息。由于顧客需求為平均量，為克服需求高峰車輛不夠的情況，實際中通常對每輛車的裝載量進(jìn)行限制，實際載貨量為規(guī)定滿載量的70%。司機工作時間為每天8小時。不考慮車輛數(shù)量限制，請為企業(yè)設(shè)計合理的配送方案。（每件產(chǎn)品規(guī)格：長：27.5CM，寬：9CM，厚：5CM）。配送用車請參考實際貨車規(guī)格自己選定。（2）適當(dāng)增加配送中心數(shù)量，能降低配送成本，假設(shè)計劃增設(shè)5個配送中心，請為各配送網(wǎng)點劃分配送范圍。二、問題背景和問題分析2.1問題背景所謂物流配送就是按照用戶的貨物（商品）訂貨要求和物流配送計劃，在物流配送節(jié)點（倉庫、商店、貨物站、物流配送中心等）進(jìn)行存儲、分揀、加工和配貨等作業(yè)后，將配好的貨物送交收貨人的過程，城市物流配送是指在城市范圍內(nèi)進(jìn)行的物流配送業(yè)務(wù)活動，城市物流配送系統(tǒng)的服務(wù)對象歸類為：政府、工業(yè)、商業(yè)、農(nóng)業(yè)、大眾客戶。城市物流配送已隨客戶需求變化從“少品種、大批量、少批次、長周期”向“多品種、小批量、多批次、短周期”轉(zhuǎn)變。隨著中國城市化進(jìn)程的進(jìn)一步加快，不管是從城市經(jīng)濟發(fā)展，還是從城市空間結(jié)構(gòu)、城市交通運輸布局及城市基礎(chǔ)設(shè)施建設(shè)來考慮，每個城市都面臨一個對原有的物流配送系統(tǒng)進(jìn)行改造、建立新的物流配送系統(tǒng)的問題，這就是城市物流配送系統(tǒng)優(yōu)化提出的原因。12.2問題分析對于第一問，為了得到最優(yōu)的配送方案，我們著重從貨車的調(diào)度和貨車的行走路線進(jìn)行設(shè)計。首先我們需要對城市進(jìn)行分區(qū)，并設(shè)計貨車在所有區(qū)域內(nèi)進(jìn)行統(tǒng)籌調(diào)度的方法。然后，我們針對某一個小的區(qū)域，運用圖論的知識，尋找貨車運送完全部貨物的最短路線，實現(xiàn)用戶、社會和公司總體利益的最大化。對于第二問，我們需要找到五個新增配送中心的位置并且劃分各個配送網(wǎng)點的配送范圍。這是一個典型的多韋伯問題。期間我們不但要注意使得配送中心到用戶的距離之和最短。同時也要滿足配送中心盡量偏重用戶需求量大的地區(qū)的要求。三、模型假設(shè)1. 建立基本模型時，所有配送用車規(guī)格（小型貨車）相同。2.送貨時配送用車均以40KM/h的速度勻速行駛。(偏遠(yuǎn)地區(qū)交通環(huán)境良好，速度可適當(dāng)提高)3.送貨時無極端天氣以及交通擁擠、交通事故、道路修理等影響送貨的情況發(fā)生。4.不存在用戶不取貨以及退貨的情況。5.貨物在包裝、囤積和運輸過程中沒有破損。6.基本模型中我們只要求貨物在訂貨周期內(nèi)送達(dá)即可，即達(dá)到此要求則可實現(xiàn)用戶的滿意度為滿分。7.在第一問中，我們選取一個子區(qū)域進(jìn)行精確分析，以其為樣本估計整個城市的情況，樣本具有普遍性。4、 符號約定xi：用戶位置的經(jīng)度值。yi：用戶位置的緯度值。x0：配送中心的經(jīng)度值。y0：配送中心的緯度值。i，j：用戶位置編號。 ：用戶相對于配送中心的方位角。L：用戶距離配送中心的距離。Dij：任意兩個用戶位置之間的距離。C：哈密爾頓圈。V：哈密爾頓圈中的邊。M：某一區(qū)域一周之內(nèi)需要的車次數(shù)。Q：某一區(qū)域一周之內(nèi)的需貨量。N：一輛貨車每日行駛車次數(shù)。T：一輛貨車行駛一個車次所需時間。W：評定配選方案是否最優(yōu)的的指標(biāo)。 ：判斷矩陣的最大特征值；：判斷矩陣的一致性指標(biāo)； Zm:“招聘效益最大化”數(shù)值。五、模型的建立與求解5.1 對問題一的求解問題一中，需要考慮用戶需求，公司利益，環(huán)境影響等多個方面的問題，給出最佳的配送方案。5.1.1 數(shù)據(jù)預(yù)處理1、我們已知，每件產(chǎn)品規(guī)格：長：27.5CM，寬：9CM，厚：5CM），體積為1237.5CM3。根據(jù)實際情況，我們選定貨車箱為長3M，寬1.8CM，高1.8M的東風(fēng)小型貨車，體積為9.72M3。由題目可知實際中通常對每輛車的裝載量進(jìn)行限制，為規(guī)定滿載量的70%，所以實際載物體積為6.804M3，可載5180箱貨物。（據(jù)計算，貨物合理布局后可在貨車中全部安放。）2、 對于表中空白數(shù)據(jù)，預(yù)先進(jìn)行處理：訂貨周期空白默認(rèn)為一周，訂貨量空白默認(rèn)為0，訂貨時間空白默認(rèn)為周六訂貨，此部分?jǐn)?shù)據(jù)少，不影響最后結(jié)果。道路ID空白對結(jié)果無影響，故不考慮。5.1.2 設(shè)計評定配送方案的指標(biāo) 倘若想要設(shè)計一個最優(yōu)的配送方案，需要知道哪些指標(biāo)應(yīng)該重點考慮，而那些可以在基本模型中忽略。只有首先通過層次分析法2計算出各指標(biāo)的權(quán)重，我們才能做出一個合理度較高的優(yōu)化方案。一、層次分析法設(shè)定各指標(biāo)權(quán)重 由題意，評價一個配送方案的是否合理主要可從用戶利益，公司收益，社會利益三個方面來考慮。1、 用戶利益主要由送貨時間與“卸貨點”到用戶實際位置間的距離決定。*“卸貨點”：貨車的卸車地點，用戶可以到“卸貨點”來取貨，多個用戶可以共用一個“卸貨點”。2、 公司收益主要由倉庫積壓程度，需要擁有的車輛數(shù)，每天發(fā)出的車次數(shù)，車輛的總行駛距離即耗油數(shù)決定。3、 社會利益主要由所有車輛行駛的總公里數(shù)，每天發(fā)出的車次數(shù)，動用的貨車種類決定。因為這三個量會影響污染的程度和交通擁擠的程度。 這是一個多目標(biāo)決策問題。我們運用層次分析法確定各因素在評價方案優(yōu)劣時所占的權(quán)重。具體分層如圖所示：模型合理度評價A用戶利益 B1公司利益 B2社會利益 3目標(biāo)層 準(zhǔn)則層 到貨時間C1卸貨點與用戶間實際距離C2倉庫積壓程度C3需要擁有的車輛數(shù)C4每天發(fā)出的車次數(shù)C5車輛的總行駛距離C6車輛行駛的總公里數(shù)C7每天發(fā)出的車次數(shù)C8動用的貨車種類C9 對同一層次的各個元素關(guān)于上一層次中某一準(zhǔn)則的重要性進(jìn)行兩兩比較，構(gòu)造兩兩比較判斷矩陣。在構(gòu)造兩兩比較判斷矩陣的過程中，按19比例標(biāo)度對重要性程度進(jìn)行賦值。下表給出19標(biāo)度的含義:標(biāo)度含義1表示兩個元素相比，具有同樣重要性3表示兩個元素相比，前者比后者稍重要5表示兩個元素相比，前者比后者明顯重要7表示兩個元素相比，前者比后者強烈重要9表示兩個元素相比，前者比后者極端重要2，4，6，8表示上述相鄰判斷的中間值倒數(shù)若元素I和元素j的重要性之比為aij，那么元素j和元素I的重要性之比為1/aij根據(jù)上述給出的標(biāo)度含義表，對于任何一個準(zhǔn)則，幾個被比較元素通過兩兩比較就可以得到一個判斷矩陣： （1） 其中，就是與相對于的重要性的比例標(biāo)度。 根據(jù)得到的判斷矩陣，我們采用“特征根法”來求解判斷矩陣中被比較元素的排序權(quán)重向量。若矩陣的最大特征值對應(yīng)的特征向量是，將所得到的經(jīng)歸一化后就是要求的權(quán)重向量。 設(shè)表示第層上個元素相對于總目標(biāo)的排序權(quán)重向量，用表示第層上個元素對第層上第個元素為準(zhǔn)則的排序權(quán)重向量，其中不受元素支配的元素權(quán)重取為零。那么第層上元素對目標(biāo)的總排序為： （2） 對于本模型依據(jù)上述的層次分析方法，計算得到如下各個層次下的判斷矩陣和其對應(yīng)的排序權(quán)重向量、一致性指標(biāo)：表1 目標(biāo)層判斷矩陣合理度A用戶利益B1公司收益B2社會效益B3用戶利益B1157公司收益B21/512社會效益B31/71/21CI=0.0071，CR=0.012，RI=0.58,此步驟中應(yīng)注意“用戶第一”的原則。表2準(zhǔn)則層B1的判斷矩陣用戶利益B1取貨距離C1到貨時間C2取貨距離C1 11/2到貨時間C221CI=0，CR=0，RI=0,表3 準(zhǔn)則層B2的判斷矩陣公司收益B2倉庫存貨量C3車輛數(shù)C4出車次數(shù)C5總油耗C6倉庫存貨量C311/31/41/7車輛數(shù)C4311/21/4出車次數(shù)C54211/3總油耗C67431CI=0.019，CR=0.021，RI=0.9,表4 準(zhǔn)則層B3的判斷矩陣社會效益B3出車種類C7擁擠程度C8總公里數(shù)C9出車種類C7111/2車輛數(shù)C8111/2總公里數(shù)C9221CI=0，CR=0，RI=0.58,表5 各指標(biāo)權(quán)重指標(biāo)取貨距離到貨時間倉庫存量車輛數(shù)出車次數(shù)總油耗擁擠程度出車種類總公里數(shù)W0.2343680.4687350.0115100.0271530.0443180.1053760.0271330.0271330.054273根據(jù)多層一致性指標(biāo)的計算方法 (3) 利用上面求得的各個層次的一致性比例，得到，符合遞階層次結(jié)構(gòu)在3層水平以上的所有判斷具有整體滿意一致性的標(biāo)準(zhǔn)，即所得的排序權(quán)重向量是合理的。二、運貨方案評價指標(biāo)的量化 由于各評價指標(biāo)單位不同，難于統(tǒng)一，我們采用分項計分制，并在計算總分時利用向量的單位化將單位統(tǒng)一，從而求得該待評價方案的總分。向量單位化的公式如下： （4） 其中，是維向量的長度。具體的評分細(xì)則如下：1、用戶利益部分用戶部分采用罰函數(shù)進(jìn)行計算。罰函數(shù)將有約束最優(yōu)化問題轉(zhuǎn)化為求解無約束最優(yōu)化問題: 其中M為足夠大的正數(shù), 起懲罰作用, 稱之為罰因子, F(x, M )稱為罰函數(shù). 即在規(guī)定時間（本處理解為一個訂貨周期內(nèi)）收到貨則用戶滿意度為1，記一分，超出規(guī)定時間后滿意度遞減。罰函數(shù)定義為0 tt0 卸貨點距用戶實際位置距離總和每一米記一分。 2、公司部分公司效益部分同樣采用計分制。倉庫存貨量方面，以產(chǎn)品件數(shù)為單位，倉庫每存有一件存貨，記一分。擁有車輛數(shù)方面，公司每擁有一輛貨車（無論是什么型號的貨車），記一分。出車次數(shù)方面，公司每派出一輛送貨車記一次分，大貨車記三分，中貨車記兩分，小貨車記一分。總油耗方面，由于總路程可間接表明總油耗，故大貨車每行駛一公里記四分，中貨車每行駛一公里計二分，小貨車每行駛一公里計一分。3、社會效益部分社會效益部分同樣采用計分制。鑒于貨車行駛會消耗能源，排放尾氣，造成擁堵，而運輸公司擁有的車數(shù)越多，城市交通擁擠越嚴(yán)重。故在車數(shù)方面，公司每擁有一輛貨車記一分。而大貨車對環(huán)境造成的破壞最大，所以在出車種類方面，每動用一次大貨車計五分，中貨車記三分，小貨車記一分。大貨車每行駛一公里計四分，中貨車每行駛一公里記二分，小貨車記一分。根據(jù)上述評分規(guī)則計算出分項得分，將分項得分歸一化后乘以各分項權(quán)重值即得總分，總分越低則方案的整體合理度最高。由此，我們可算出任何一個配送方案的合理度，從而比較得出最優(yōu)的配送方案。根據(jù)各指標(biāo)的權(quán)重可以得到結(jié)論。配送方案設(shè)計應(yīng)著重注意車輛調(diào)度和總行駛路程最短的問題。5.1.3 利用matlab繪制物流網(wǎng)絡(luò)圖圖1 某城市物流網(wǎng)絡(luò)圖 注：其中藍(lán)色線條代表可行駛的物流道路，黑色標(biāo)記代表所有的用戶位置，紅色標(biāo)記為配送中心的位置。從圖中可以看出，該城市的配送中心位于城市的西北部，且西北部的用戶密集，交通發(fā)達(dá)，為市中心鬧市區(qū)。而東南部用戶和道路稀疏，為市郊。在分配車輛時應(yīng)考慮這些問題。5.1.4利用雷達(dá)圖分割法給用戶位置粗略分區(qū)數(shù)據(jù)預(yù)處理：在Microsoft Excel 工作表中將來源于該城市的用戶位置中的信息進(jìn)行整理，計算出各點對于配送中心的方位角和距離。以配送中心的位置（x0，y0）為圓心，利用各用戶位置的坐標(biāo)(xi，yi)，算出它們相對于配送中心位置(107.972554615162,26.6060305362822)的方位角和距離L。當(dāng)xi107.972554615162時， 當(dāng)xi26.6060305362822時， +180o當(dāng)xi107.972554615162,yi0dij=dji（對稱性）dijdik+dkj（三角不等式）2.Euclidian 距離 歐氏距離（ Euclidean distance）也稱歐幾里得距離是一個通常采用的距離定義，它是在m維空間中兩個點之間的真實距離。 在二維和三維空間中的歐式距離的就是兩點之間的距離，二維的公式是 d=sqrt(x1-x2)2+(y1-y2)2) （8）轉(zhuǎn)化為本題中的經(jīng)緯度計算為： （9） （i,j=1,2,3112） 其中i,j為兩個不同的用戶位置， Dij為ij兩個用戶位置之間的距離。 在matlab中將距離相近的點聚類，將區(qū)域中的112個用戶分散到7個區(qū)域中。具體結(jié)構(gòu)詳見excel表格。二、精確重心法4確定卸貨點位置 重心法是將物流系統(tǒng)的需求點看成是分布在某一平面范圍內(nèi)的物體系統(tǒng)，各點的需求量和資源量分別看成是物體的重量，物體系統(tǒng)的重心將作為物流網(wǎng)點的最佳設(shè)置點，利用確定物體中心的方法來確定物流網(wǎng)點的位置。 本題中我們希望每個卸貨點區(qū)域中，卸貨點到所有用戶位置的距離之和D總最短。 D總= （10）注：(xi,yi)為每個用戶的位置，（xs,ys）為卸貨點位置，n為該卸貨點覆蓋區(qū)域的用戶數(shù)量。 精確中心法目標(biāo)函數(shù)為雙變量系統(tǒng)，分別對xS和yS求偏導(dǎo)，并令島數(shù)為零，求得隱含最優(yōu)解的等式為： （11） （12） （13）1、 Excel規(guī)劃求解 1.在Excel中輸入數(shù)據(jù)，并且假設(shè)原點坐標(biāo)為（1，1）， 以 覆蓋區(qū)3為例，在K1中輸入“=SQRT(111*($B$1-B9)2+(99.25*($C$1-C9)2)”，并將右下角的十字光標(biāo)下拉復(fù)制公式。2.規(guī)劃求解，利用excel工具欄中的加載宏“規(guī)劃求解”，對卸貨點位置進(jìn)行迭代，得到最佳卸貨點位置。3.第100次迭代求得卸貨點坐標(biāo)為（107.8923,26.37949），此時總路程為2.12666KM。4. 七個卸貨點均用此方法算出最佳位置，并計算出每個卸貨點每天的需貨量，圖下表所示。表7 卸貨點信息表卸貨點緯度經(jīng)度周一貨量周二貨量周四貨量合計21107.878831726.409041701270012702107.846643226.4271580306626923107.892301526.3794931022802284107.823049726.37831175022802285107.808212526.32132914502695027456107.856424926.303978290700707107.826923526.28442958402100250合計1904767264883 由此可知一周之內(nèi)該區(qū)域總共需要4883箱貨物，根據(jù)計算我們可知一輛小型貨車一周往返一次(一個車次)即可滿足運貨需求，并且小型貨車在市區(qū)行駛靈活，減少交通污染。如果貨車走完該區(qū)域用時遠(yuǎn)小于8小時，則回到出發(fā)點后進(jìn)行其他區(qū)域的運貨任務(wù)（相當(dāng)于另外一輛車）。 接下來我們只需確定貨車在一個區(qū)域的最短行駛路線即可。5.1.8運用Floyd算法5確定每兩個卸貨點之間的最短距離 要給出將貨物送到七個卸貨點并返回的最短路線，我們將卸貨點之間的距離求出。利用圖論中的Floyd算法和哈密爾頓圈求解往返最短路線問題，在matlab中可以得出它的最佳路線和最短路程。首先，我們繪制用戶位置、卸貨點以及其附近交通道路的圖像，如圖3所示。配送中心 圖3 卸貨點位置圖由圖可知，卸貨點均選在用戶密集的地點，即卸貨點選擇正確。然后，我們需要利用Floyd算法，計算每兩點之間的最短距離。Floyd算法是一種用于尋找給定的加權(quán)圖中頂點間最短路徑的算法。我們可以通過一個圖的權(quán)值矩陣求出它的每兩點間的最短路徑矩陣。從圖的帶權(quán)鄰接矩陣A=a(i,j) nn開始，遞歸地進(jìn)行n次更新，即由矩陣D(0)=A，按一個公式，構(gòu)造出矩陣D(1)；又用同樣地公式由D(1)構(gòu)造出D(2)；最后又用同樣的公式由D(n-1)構(gòu)造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點到j(luò)號頂點的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個后繼節(jié)點矩陣path來記錄兩點間的最短路徑。為了簡便計算，我們尋找離卸貨點最近的公路節(jié)點作為“真實卸貨點”，由此可知卸貨點之間經(jīng)歷的公路編號和ID。從而我們可以知道七個卸貨點之間的最短距離，注意此距離并非是卸貨點間直線距離，而是通過floyd算法而得到的公路折線距離。例如卸貨點1到卸貨點2之間的最短距離為 KM，其間一次經(jīng)歷的公路編號為： 具體情況如下表所示。表8 卸貨點間距表起點終點距離（KM）0122.209580224.290470324.361570428.184460533.595560632.580550735.66729123.4583141329.60301146.1924211544.337311616.658421720.347852325.14470242.7341072532.623842613.20012716.889543422.410593523.989463611.94460378.2551604529.889734610.465994714.465995619.423745715.73430673.6894385.1.9哈密爾頓圈6模型求解貨車最短行駛路線送貨員要將貨物送到七個卸貨點（加上配送中心共八個點）并返回，即經(jīng)過其中每一個點剛好形成一個圈。對于這種情況設(shè)計它的最短路線問題，我們建立哈密爾頓圈模型。哈密頓圖（Hamiltonian path）是一個無向圖，由天文學(xué)家哈密頓提出，由指定的起點前往指定的終點，途中經(jīng)過所有其他節(jié)點且只經(jīng)過一次。在圖論中是指含有哈密頓回路的圖，閉合的哈密頓路徑稱作哈密頓回路，含有圖中所有頂?shù)穆窂椒Q作哈密頓路徑。1、 對于這一模型我們開始要畫出8個點的坐標(biāo)圖，結(jié)合圖形便于模型的求解和優(yōu)化。圖4 區(qū)域送貨地點的坐標(biāo)圖8146 2735二、任取初始哈密頓回路: 對所有的，若，則在中刪去邊和而插入新邊和，形成新的H圈，即，對重復(fù)這一步驟，直到條件不滿足為止，結(jié)合圖一的路線圖觀察，從而進(jìn)行優(yōu)化，使用這種方法，借助matlab編程使用迭代的方法可以求出它的最優(yōu)路徑（見附錄程序）。綜合上述方法，可求：最短路線： 最短路程：84.4332KM。最短運貨用時為2.11小時。圖5 區(qū)域貨物的最佳路線圖 5.1.10設(shè)計車輛調(diào)度方案 上述，我們已經(jīng)解決了某個區(qū)域的供貨方式和行駛路徑問題，以下我們做出整體的配送方案。1.根據(jù)貨物的每日和每周的需求量，我們做以下安排，當(dāng)當(dāng)日運送量Q遠(yuǎn)小于一輛貨車的載貨量（5180箱）的，由相鄰區(qū)域安排貨車同時運送兩個區(qū)域的貨物或者積壓貨物到一周之內(nèi)運送，我們其他情況則為一個區(qū)域單獨安排車次M，保證貨物盡快送到。粗糙模型時，貨物運送采用一周統(tǒng)籌的方式。 M=Q/5180 (四舍五入) （14）2.車次不代表安排貨車的數(shù)量，同一輛貨車一天可以走多個車次。每日貨車行駛車次N需要根據(jù)計算貨車行走某一路線（一個車次）所需的時間T來設(shè)定。已知司機每日工作八小時。 N=8/T (取整法) （15） 3. 貨車數(shù)量確定后，則可分別安排每輛車的負(fù)責(zé)區(qū)域，盡量保證幾輛車的行駛時間和行駛車次相等。表9 各區(qū)域車次安排區(qū)域周1車次周2車次周3車次周4車次周5車次周6車次任一天周總車次A443400015B00011002C21101005D22221009E01101003F10011003G11001003H01000001I01000001J01010002K01201002L21120006M00110002N10010002O01101003P12010004Q23121009R521510014S323140013T432310013合計282719251500112 一、粗糙模型 1、通過步驟5.1.4我們已知每個區(qū)域所需的車次數(shù)量，以及總車次數(shù)為112。根據(jù)以上結(jié)果，最近的區(qū)域出一個車次需要2.11小時，我們近似估計行駛一個車次平均需要的時間為4小時。按每個司機每天行駛8小時，每天行駛2個車次，則每輛車一周可以行駛16個車次計算，需要7輛車分送所有的貨物。進(jìn)一步考慮到貨車到卸貨點卸貨花費的時間，貨車修理和司機輪休的影響，我們安排15輛車來進(jìn)行運送。將圖中20個統(tǒng)籌區(qū)分為5部分，每3輛貨車分管一個部分，均勻送貨，具體情況參照步驟5.1.4中的車次表。2、 若所有貨物都必須當(dāng)天送達(dá)，則無論貨物多少都要出車，仍按每輛車一天行駛2個車次計算，表中給出周一最繁忙需要出28個車次，即公司要安排14輛車?？梢钥闯鲋拔覀儼才趴偣?5輛車的計劃是合理的。二、最終配送方案 下面給出車輛的具體較優(yōu)調(diào)度方法和運輸公司所需擁有的最少車數(shù)。由于對全部給定區(qū)域內(nèi)的所有點進(jìn)行優(yōu)化統(tǒng)籌過于繁雜，但若是只考慮全局中的一小塊又會失去統(tǒng)籌規(guī)劃的意義，為此我們對題目給定范圍進(jìn)行扇形分區(qū)。總共劃分為10個區(qū)域。則對于每一塊區(qū)域，其總的貨物需求量為它所包含的所有用戶的貨物需求量之和。貨物由配送中心運至該區(qū)域的平均時間由于考慮到用戶利益優(yōu)先，最遠(yuǎn)點保證送到的原則，定為到其中較遠(yuǎn)點的距離。則有配送中心分別到各區(qū)域所需要的時間和各區(qū)域的貨物需求量如下表：表10 配送情況表區(qū)域ABCDEFGHIJ到貨時間8h8h5h4.4h2.3h3.5h3.5h4h6.5h8h需求量74100件53706件12304件13169件7477件40887件14439件33230件102119件115861件 優(yōu)化調(diào)度方案所要達(dá)到的目標(biāo)是所需的車輛數(shù)最少，所需發(fā)車的車次數(shù)最少。車輛的總閑置時間最少，以及車輛的總剩余可載貨空間最少。 經(jīng)多次試驗（窮舉法）得到一種較優(yōu)的調(diào)度方案，見下表：表11 調(diào)度方案表 星期 目的地車輛 星期一星期二星期三星期四星期五星期六星期日小車1F,HF,HF,HF,CBH,HB小車2BBBBBBB小車3JJJJJJJ小車4JJJJJJJ小車5JJJJJJJ小車6IIIIIIJ小車7IIIIIIJ小車8IIIIIIA中車1B,ED,GD,GC,FF,HII大車1AAAAAAA 經(jīng)分析知此方案所有車輛均沒有閑置時間，車輛總數(shù)僅需10輛，總的剩余可載貨量僅有4000件左右，發(fā)車次數(shù)也僅有80車次，是一種較優(yōu)的調(diào)度方案。5.2 對問題二的求解 問題二中，我們需要在原圖中再安置5個配送中心，從而使配送更快捷，服務(wù)更優(yōu)化，使目標(biāo)函數(shù)取得最優(yōu)解。5.2.1 確定八個待定的配送中心坐標(biāo) 首先我們利用excel對數(shù)據(jù)進(jìn)行合并，利用經(jīng)緯度分割的方法，使16764個用戶位置聚合到100個用戶聚合點（每個區(qū)域的中心位置）。并用三維圖進(jìn)行表示，其中坐標(biāo)x,y代表100點的經(jīng)緯度，坐標(biāo)z表示某個點的貨物總需求量，如下圖所示。圖6 用戶需求三維圖 從圖中可以看出，有明顯的貨物量凸起的部分，為貨物緊需區(qū)域。我們利用matlab篩選出局部最優(yōu)點，給出八個待定的配送中心位置，即需要從這八個點中進(jìn)行選擇。 八個待定配送中心的位置如下：表10 待定點信息待定點編號經(jīng)度緯度1107.791497226.224783552108.198075826.223576263108.056801526.717164454108.67965126.96689015108.689218525.97394826109.211669326.895898637109.174977326.16367028107.75715826.65597414 在matlab中繪制二維圖可以看出八個待定點的位置如下：圖7 待定點方位圖5.2.2選定最終的配送中心位置和配送范圍 我們現(xiàn)在要做的工作是在8個待定點中確定5個最終要選取的配送中心位置并為各配送網(wǎng)點劃分配送范圍。明顯可以看出，這是一個多韋伯問題7（multi-Weber problem）,它既包括用戶的分配，又包括設(shè)施在空間上的定位，所以通常又把設(shè)施定位問題稱為設(shè)施定位分配問題。設(shè)施定位問題是指在空間上尋找合適的設(shè)施布局，使用戶與設(shè)施相互作用的費用滿足某一準(zhǔn)則的問題，共有18種準(zhǔn)則，但最常用有三種準(zhǔn)則，即“總和最小化”（MinSum）準(zhǔn)則、“最大最小化”（Maxmin）準(zhǔn)則和“最小最大化”（Minmax）準(zhǔn)則。設(shè)施定位問題又有單設(shè)施定位問題和多設(shè)施定位問題。本題為多設(shè)施定位問題。為了簡化問題，我們利用第一步中聚合的100個用戶聚合點代替實際的用戶位置。一、問題簡化為：1.有5個配送中心的需要選址，有100個已知位置的用戶分配給不同的配送中心，每個用戶需求的為aj,j=1,2,n。2.我們需要找到配送中心的位置（選址）顧客對配送中心的分配3. 使顧客和服務(wù)他們的配送中心的距離之和最短。4. 同時考慮配送中心應(yīng)該離用戶需求量大的地方近一些。 二、我們用0-1規(guī)劃來解決這個問題 設(shè)配送中心Pi坐標(biāo)為(xi,yi)(i=1,2,36)（包含了原有的配送中心P6），用戶Rj坐標(biāo)為（vj,uj）(j=1,2,3100),每個用戶的需求量為wj，配送點i是否對用戶j服務(wù)為zij，值為1表示服務(wù)，0表示不服務(wù)。 目標(biāo)函數(shù) Min j=1,2,3,100 (16) zij =0或1 此問題為非線性0-1規(guī)劃問題，不易求解，所以我們將配送中心的可能位置定在備選的八個待定點上。我們計算出用戶Rj到配送中心Pi的距離為dij，。重新設(shè)定用戶Rj坐標(biāo)為（vj,uj）(j=1,2,3100),每個用戶的需求量為wj，配送點i是否對用戶j服務(wù)為zij，值為1表示服務(wù)，0表示不服務(wù)。si表示是否在i點設(shè)立配送中心。則模型簡化為： 目標(biāo)函數(shù) Min j=1,2,3,100 (17) zij =0或1 si=0或1 運算過程見附錄程序，結(jié)果見下表：表11 配送中心位置信息配送中心編號經(jīng)度緯度3108.056801526.717164454108.67965126.96689015108.689218525.97394826109.211669326.895898637109.174977326.1636702原107.97255461516226.6060305362822 同時我們也知道了各個配送中心的配送范圍，因為我們是用100個聚合點代替的所有用戶位置進(jìn)行計算，所以范圍在圖中的表示是網(wǎng)格狀的，具體情況見下圖：圖11 配送網(wǎng)點配送范圍劃分結(jié)論：各個配送中心的位置較為分散，近似平均的劃分了圖中所有的用戶位置點，且用戶相對密集的地方配送中心比較密集。同時，本模型將“距離*需求量”作為0-1規(guī)劃的權(quán)重，綜合考慮了這兩個指標(biāo)，全面地分析了模型。所以本模型合理。六、模型推廣1.在基本模型中我們只考慮了所有車輛一次只對一個區(qū)域服務(wù)的情況。如果大、中、小型貨車同時使用，則使模型更加復(fù)雜?？赡芤惠v大貨車可以一次性運送幾個區(qū)的貨物，則貨車路徑需要重新設(shè)計。貨車調(diào)度表也更加復(fù)雜。已知：大型貨車：長：6M 寬：2.0M 高: 2.7M 滿載量：182852箱 中型貨車：長：5M 寬：1.9M 高: 1.9M 滿載量： 9576箱 小型貨車：長：3M 寬：1.8M 高: 1.8M 滿載量： 6800箱2. 實際情況中要將貨物在指定時間送達(dá)指定地點，我們會考慮指定時間早的先送貨物，后送指定時間比較晚的?；A(chǔ)這樣的考慮問題的方向，我們將貨物送貨時間和送達(dá)地點進(jìn)行分塊分組。由于數(shù)據(jù)量巨大，我們可以采用局部最優(yōu)、模擬退火法和遺傳算法計算出每一塊中貨物送達(dá)點的路線，求出其中耗時最短的路線即最短路程和最短時間。3. 設(shè)計出送貨員將貨物全部送到指定地點并返回的路線時，送貨員有要中途返回取貨的可能性。所以我們我們可以將送貨員的送貨區(qū)域的路線分為四條支路。結(jié)合這一情況，我們考慮到圖論中的最小生成樹。由于最小生成樹可以解決連線問題，而設(shè)計路線就屬于連線問題。對于多個送貨地點，送貨員的線路比較多，所以我們采用Prim算法構(gòu)造最小生成樹。根據(jù)最小生成樹，將送貨員的送貨區(qū)域劃分為四組，從而得出它們的最佳路線。4. 對于這樣的模型，我們可以推廣到飛機送貨路線，輪船運輸?shù)葐栴}。七、模型檢驗7.1層次分析法的檢驗 由于本題的數(shù)據(jù)量，未能做出整個城市完整的模型，無法對模型進(jìn)行合理度的計算。所以我們利用matlab隨機生成3個矩陣，檢驗層次分析法的9個權(quán)重設(shè)置的合理性，證明該方法的正確性。檢驗生成的隨機值如下：取貨距離到貨時間倉庫存貨量大車數(shù)中車數(shù)小車數(shù)出車次數(shù)總路程51364117981313120890777687.002158670210118909860233707922151068908則根據(jù)計分標(biāo)準(zhǔn)可計算出各分項得分如下：取貨距離到貨時間倉庫存貨量公司車數(shù)出車次數(shù)總里程車總數(shù)車種類總油耗51360117981712089071727890777681.001158671211890981216909860230707919106890819318908歸一化后所得的分項得分如下：取貨距離到貨時間倉庫存貨量公司車數(shù)出車次數(shù)總里程車總數(shù)車種類總油耗0.46310300.5617670210.6033070.6033270.5732030.6033070.6120580