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

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