1、數(shù)模期末論文城市物流配送系統(tǒng)優(yōu)化小組成員：目 錄第一部分摘要1第二部分關(guān)鍵詞1第三部分建模問題分析與解答21.問題重述22.問題背景與問題分析23.模型假設(shè)與符號約定34.模型建立55.進(jìn)一步討論66.模型檢驗(yàn)67.模型優(yōu)缺點(diǎn)28.參考文獻(xiàn)39.附錄5一、問題重述配送是從用戶利益出發(fā)、按用戶要求進(jìn)行的一種物流活動(dòng)。公司應(yīng)根據(jù)用戶要求，在配送中心進(jìn)行貨物配備，并以最合理的方式送交用戶，把用戶利益放在第一位。因此企業(yè)不能單純從自身利益出發(fā)而應(yīng)從用戶利益出發(fā)，在滿足用戶利益基礎(chǔ)上進(jìn)而取得企業(yè)的利益。此外，城市交通擁堵和環(huán)境問題惡化給物流配送提出了更高的要求。城市的配送系統(tǒng)不但要考慮企業(yè)自身和用戶的利

2、益，也應(yīng)從公眾利益出發(fā)，盡量減少交通擁擠和廢物排放。雖然增加了配送系統(tǒng)管理的難度，但有效解決該問題對于改善城市出行環(huán)境和提高企業(yè)服務(wù)水平具有重要意義。基于以上背景，請為某企業(yè)設(shè)計(jì)其配送方案，建立數(shù)學(xué)模型分析如下問題：（1） 假設(shè)該公司在整個(gè)城區(qū)僅有一個(gè)配送中心，坐標(biāo)為：（107.972554615162，26.6060305362822）。附件1中給出了企業(yè)顧客位置和需求數(shù)據(jù)。附件2為配送網(wǎng)絡(luò)路網(wǎng)信息，其中，節(jié)點(diǎn)1和節(jié)點(diǎn)2表示某一個(gè)路段的始末節(jié)點(diǎn)，并給出了始末節(jié)點(diǎn)坐標(biāo)。由于顧客需求為平均量，為克服需求高峰車輛不夠的情況，實(shí)際中通常對每輛車的裝載量進(jìn)行限制，為規(guī)定滿載量的70%。司機(jī)工作時(shí)間為每

3、天8小時(shí)。不考慮車輛數(shù)量限制，請為企業(yè)設(shè)計(jì)合理的配送方案。（每件產(chǎn)品規(guī)格：長：27.5CM，寬：9CM，厚：5CM）。配送用車請參考實(shí)際貨車規(guī)格自己選定。（2） 適當(dāng)增加配送中心數(shù)量，能降低配送成本，假設(shè)計(jì)劃增設(shè)5個(gè)配送中心，請為各配送網(wǎng)點(diǎn)劃分配送范圍。二、問題背景和問題分析2.1問題背景城市物流配送是指在城市范圍內(nèi)進(jìn)行的物流配送業(yè)務(wù)活動(dòng)，城市物流配送系統(tǒng)的服務(wù)對象歸類為：政府、工業(yè)、商業(yè)、農(nóng)業(yè)、大眾客戶。城市物流配送已隨客戶需求變化從“少品種、大批量、少批次、長周期”向“多品種、小批量、多批次、短周期”轉(zhuǎn)變。隨著中國城市化進(jìn)程的進(jìn)一步加快，不管是從城市經(jīng)濟(jì)發(fā)展，還是從城市空間結(jié)構(gòu)、城市交通運(yùn)

4、輸布局及城市基礎(chǔ)設(shè)施建設(shè)來考慮，每個(gè)城市都面臨一個(gè)對原有的物流配送系統(tǒng)進(jìn)行改造、建立新的物流配送系統(tǒng)的問題，這就是城市物流配送系統(tǒng)優(yōu)化提出的原因。2.2問題分析 第一個(gè)問題求解的是最優(yōu)配送方案，要達(dá)到的效果是顧客、企業(yè)、社會(huì)三方利益的最大化。因此要先理清三者之間的利益關(guān)系以及限制因素，再從中選取權(quán)重較大的決定性因素進(jìn)行分析計(jì)算。諸如卸貨點(diǎn)數(shù)量及位置、運(yùn)輸路線、車輛數(shù)等等。同時(shí)，如果以城市為單位直接進(jìn)行計(jì)算，會(huì)導(dǎo)致數(shù)據(jù)量過大，且實(shí)施較為困難，因此要對城市進(jìn)行分區(qū)，并在每個(gè)區(qū)內(nèi)設(shè)計(jì)配送方案。第二個(gè)問題求解的是五個(gè)新增配送中心的位置并劃分其管轄的區(qū)域。這是一個(gè)設(shè)施定位分配問題。我們不但要注意使得配送

5、中心到用戶的距離之和最短，同時(shí)也要滿足配送中心盡量偏重用戶需求量大的地區(qū)的要求。三、模型假設(shè)1.建立的模型中，所有配送用車規(guī)格相同（選用福田廂式貨車）。2.送貨時(shí)配送用車均以50KM/h的速度勻速行駛。3.不考慮可能出現(xiàn)的交通擁擠、事故等情況。4.所有預(yù)訂貨物均能送出。5.顧客要求在訂貨周期內(nèi)送到即可。4、 符號約定xi：用戶位置的經(jīng)度值。yi：用戶位置的緯度值。x0：配送中心的經(jīng)度值。y0：配送中心的緯度值。W：評定配選方案是否最優(yōu)的的指標(biāo)。 ：判斷矩陣的最大特征值；：判斷矩陣的一致性指標(biāo)；：用戶相對于配送中心的方位角。L：用戶距離配送中心的距離。D：任意兩個(gè)用戶位置之間的距離。G：Hami

6、lton回路。w：區(qū)域內(nèi)所有顧客需貨量Z：0-1矩陣五、模型的建立與求解5.1 對問題一的求解問題一中，需要考慮用戶需求和公司利益，給出最佳的配送方案。5.1.1 數(shù)據(jù)預(yù)處理已知，每件產(chǎn)品規(guī)格：長：27.5CM，寬：9CM，厚：5CM），體積為1237.5CM3。根據(jù)實(shí)際情況，我們選定貨車箱為長4.05M，寬2.05M，高1.9M的福田廂式貨車，體積為15.78M3。題中對每輛車的裝載量進(jìn)行限制，規(guī)定最大裝載量為滿載量的70%，所以實(shí)際載物體積為11.04 M3，可載8923箱貨物。（據(jù)計(jì)算，貨物合理布局后可在貨車中全部安放。）對于表中空白數(shù)據(jù)，預(yù)先進(jìn)行處理：訂貨周期空白默認(rèn)為一周，訂貨量空白

7、默認(rèn)為0。其中還有極少數(shù)顧客訂貨時(shí)間為周六或者空白，將其一并算作周五訂貨，此部分?jǐn)?shù)據(jù)少，不影響最后結(jié)果。5.1.2 找尋設(shè)計(jì)配送方案的依據(jù)倘若想要設(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)重由題意，評價(jià)一個(gè)配送方案的是否合理主要可從用戶利益，公司收益、社會(huì)利益三個(gè)方面來考慮。首先應(yīng)該從用戶利益出發(fā)，在滿足用戶利益基礎(chǔ)上進(jìn)而取得本企業(yè)的利益，同時(shí)應(yīng)從公眾利益出發(fā)，盡量減少交通擁擠和廢物排放。1、 用戶利益主要由送貨時(shí)間與“卸貨點(diǎn)”到用戶實(shí)際位置間的距

8、離決定。*“卸貨點(diǎn)”：貨車的卸車地點(diǎn)，用戶可以到“卸貨點(diǎn)”來取貨，多個(gè)用戶可以共用一個(gè)“卸貨點(diǎn)”。2、 公司收益主要由倉庫存量，需要擁有的車輛數(shù)，每天發(fā)出的車次數(shù)，車輛的總行駛距離即耗油數(shù)決定。因?yàn)檫@些因素決定公司的支出，只有這些因素都達(dá)到最小值，公司的利益才能達(dá)到最大。3、 社會(huì)利益主要由所有車輛行駛的總行駛距離數(shù)，每天發(fā)出的車次數(shù)決定。因?yàn)檫@兩個(gè)量會(huì)影響污染的程度和交通擁擠的程度。 這是一個(gè)多目標(biāo)決策問題。我們運(yùn)用層次分析法確定各因素在評價(jià)方案優(yōu)劣時(shí)所占的權(quán)重。具體分層如圖所示：模型合理度評價(jià)A目標(biāo)層社會(huì)利益B3公司利益B2用戶利益B1準(zhǔn)則層每天發(fā)出的車次數(shù)C8車輛的總行駛距離C6所需車輛

9、數(shù)C4倉庫存量C3卸貨點(diǎn)與用戶間距離C2到貨時(shí)間C1總行駛距離C7發(fā)車次數(shù)C5對同一層次的各個(gè)元素關(guān)于上一層次中某一準(zhǔn)則的重要性進(jìn)行兩兩比較，構(gòu)造兩兩比較判斷矩陣。在構(gòu)造兩兩比較判斷矩陣的過程中，按19比例標(biāo)度對重要性程度進(jìn)行賦值。下表給出19標(biāo)度的含義:ui比uj極端重要強(qiáng)烈重要明顯重要稍微重要同樣重要相鄰判斷的中間值量化值975312,4,6,8根據(jù)上述給出的標(biāo)度含義表，對于任何一個(gè)準(zhǔn)則，幾個(gè)被比較元素按照兩兩比較構(gòu)成的矩陣（1），稱作判斷矩陣。易見aij0，aii=1且aij=1/aji（i，j=1,2，n），即A為正互反矩陣。 其中，就是與相對于的重要性的比例標(biāo)度。 根據(jù)得到的判斷矩陣

10、，我們采用“特征根法”來求解判斷矩陣中被比較元素的排序權(quán)重向量。若矩陣的最大特征值對應(yīng)的特征向量是，將所得到的經(jīng)歸一化后就是要求的權(quán)重向量。 設(shè)表示第層上個(gè)元素相對于總目標(biāo)的排序權(quán)重向量，用表示第層上個(gè)元素對第層上第個(gè)元素為準(zhǔn)則的排序權(quán)重向量，其中不受元素支配的元素權(quán)重取為零。那么第層上元素對目標(biāo)的總排序?yàn)椋?（2） 對于本模型依據(jù)上述的層次分析方法，計(jì)算得到如下各個(gè)層次下的判斷矩陣和其對應(yīng)的排序權(quán)重向量、一致性指標(biāo)：C.I.=（-n）/（n-1）表1 目標(biāo)層判斷矩陣合理度A用戶利益B1公司收益B2社會(huì)利益B3=3.0183W=0.9154,0.3493,0.1999用戶利益B1134公司收益

11、B21/312社會(huì)利益B31/41/21CI=0.00915，CR=0.0158，RI=0.58,此步驟中應(yīng)注意“用戶第一”的原則。表2準(zhǔn)則層B1的判斷矩陣用戶利益B1到貨時(shí)間C1取貨距離C2=2W=0.9487,0.3162到貨時(shí)間C1 13取貨距離C21/31CI=0，CR=0，RI=0,表3 準(zhǔn)則層B2的判斷矩陣公司收益B2倉庫存量C3所需車輛數(shù)C4發(fā)車次數(shù)C5總行駛距離C6=4.0813W=0.1047,0.2364,0.3852,0.8859倉庫存量C311/31/41/6所需車輛數(shù)C4311/21/4發(fā)車次數(shù)C54211/3總行駛距離C66431CI=0.0271，CR=0.030

12、4，RI=0.89,社會(huì)利益B3總行駛距離C7每天發(fā)出的車次數(shù)C8=2W=0.9487,0.3162總行駛距離C713每天發(fā)出的車次數(shù)C81/31CI=0,CR=0,RI=0,表5 各指標(biāo)權(quán)重指標(biāo)取貨距離到貨時(shí)間倉庫存量所需車輛數(shù)發(fā)車次數(shù)總行駛距離W0.76560.25520.03230.07280.17430.4400從這些指標(biāo)的權(quán)重中可以看出取貨距離和車輛的行駛距離占據(jù)的權(quán)重最大，所以下面我們將從這兩個(gè)方面入手，計(jì)算出顧客取貨距離最短和車輛行駛距離最短的方案。5.1.3繪制物流網(wǎng)絡(luò)圖圖中包含配送中心（紅色五角星）、顧客位置（黑色+號）以及配送道路（藍(lán)色線條）。從圖中可以看出，該城市的配送中

13、心位于西部稍微偏北，且附近顧客分布較為密集，交通發(fā)達(dá)，應(yīng)該為該市的市中心。而中部和東部顧客相對較少，交通道路也相對稀疏，應(yīng)為市區(qū)邊緣或者郊區(qū)。由此推測，西部業(yè)務(wù)量較大，卸貨點(diǎn)應(yīng)多于中部和東部。5.1.4對顧客位置進(jìn)行分區(qū) 我們認(rèn)為如果對城市的全部數(shù)據(jù)進(jìn)行直接計(jì)算過于復(fù)雜，數(shù)據(jù)量也太大，并不合理。因此我們將對城市進(jìn)行分區(qū)，分別計(jì)算每區(qū)的卸貨點(diǎn)數(shù)量和位置、貨車數(shù)量以及貨車行駛路線。由于全市只有配送中心，全城的配送都應(yīng)從該中心輻射出去，因此可以按照顧客距離配送中心的相對位置，以及顧客的密集程度進(jìn)行區(qū)域劃分。觀察該城市物流網(wǎng)絡(luò)，我們發(fā)現(xiàn)，我們可以根據(jù)方位角和距離將顧客分成100個(gè)目標(biāo)區(qū)域。首先要對數(shù)據(jù)

14、進(jìn)行處理：在Excel 中將該城市的顧客位置信息進(jìn)行整理，計(jì)算出各點(diǎn)對于配送中心的方位角和距離。以配送中心的位置（x0，y0）為圓心，利用各用戶位置的坐標(biāo)(xi，yi)，算出它們相對于配送中心位置（107.972554615162，26.6060305362822）的方位角和距離L。方位角：當(dāng)xi107.972554615162時(shí)，=arctan(yi-yo)/(xi-xo)當(dāng)xi26.6060305362822時(shí)， =arctan(yi-yo)/(xi-xo)+180當(dāng)xi107.972554615162,yi26.6060305362822時(shí)， =arctan(yi-yo)/(xi-xo)

15、 -180 其中 i=1,2,316764距離L： 在計(jì)算中，1緯度對應(yīng)距離大概為111km，北緯26度處，1經(jīng)度對應(yīng)距離大概為111cos緯度=100km。 因此 L=100xi-xo2+111yi-yo2其中 i=1,2,316764我們規(guī)定通過方位角將圖形等分為20個(gè)大區(qū)，每個(gè)區(qū)18度，標(biāo)號為字母A-T；通過距離將每個(gè)大區(qū)分為5個(gè)小區(qū)，考慮到顧客離配送中心越遠(yuǎn)越分散，且顧客最遠(yuǎn)距離大概為162km，因此5個(gè)小區(qū)的間距由配送中心開始依次增大，分別為25km，30km，35km，40km，45km，最遠(yuǎn)達(dá)到175km，最終遍及所有顧客。然而實(shí)際會(huì)有很多區(qū)域內(nèi)沒有顧客，可直接忽略。5.1.5確

16、定每個(gè)區(qū)域的訂貨量在execl中對數(shù)據(jù)進(jìn)行整合，可知每個(gè)區(qū)域的每日的訂貨量。結(jié)果如下表。大區(qū)小區(qū)周一訂貨量周二訂貨量周三訂貨量周四訂貨量周五訂貨量小區(qū)周總訂貨量大區(qū)周總訂貨量A17088712001693155076200054879413423127261082300148369072488821230173728858180039213534454755304734518B13793600137552766522251669603600401271324333060104312358172165832046682427547446867145303709854216514343422242

17、149617439C1226310020232280496072134329008531052353833496306352761548118802526342575402738461297678118526D1688230047311843686325998134448251481731235964686536532938681621242583505019602532012155E196319002110252529204238942991337525934643174963657398047449909183F196140600171167310554252846723557310722

18、87531155574262107206006G17316120456791117502150490139647696364325934001912504595H1768100257027271096626864074005615321320828360002918I1491011002663372349752454612001861252J1261682033915522022219200017017K14477904309169068226892206505070L16300022128415322233150714273201014951318030017412615581858M126

19、445438650649140817128220105112815820283530021200212N1495427271008333473112300397403977O133913023649567949911468271942575639609585052015726P133021045852165258211033142332428255241200309530001050105Q1376167621731268019711690516905R13125291630384312348118584601125728406866547016349302810205737505242426

20、5300332352849096765014851401002886S139297904901175429681356186213111012980017103384018818565201547122804754458053147553554822579567951443292065597312786T1325866209007954936082921321710112301426303676264511941566908146085834164186283251679359655490985408037280365.1.6 確定大致配送方案根據(jù)上表分析，實(shí)際只有65個(gè)區(qū)覆蓋到了顧客，因此，

21、最終城市被分為了65個(gè)送貨區(qū)，分別單獨(dú)送貨。但是，我們可以看到不同區(qū)域的需貨量差異較大，有的區(qū)域每天需要兩到三輛車，有的區(qū)域每周一輛車運(yùn)一次即可，有的甚至可以兩到三個(gè)相鄰區(qū)域一起運(yùn)送。因此我們對這65個(gè)區(qū)的配送進(jìn)行了以下規(guī)劃：大區(qū)合并后的單位運(yùn)輸區(qū)運(yùn)輸方式及車輛安排A1、2每周運(yùn)一次、每次一輛車3每周運(yùn)一次、每次一輛車4每天運(yùn)一次、每次一輛車（周二兩輛）5每周運(yùn)一次、每次一輛車B1、2每周運(yùn)兩次、每次一輛車3每周運(yùn)一次、每次一輛車4每天運(yùn)一次、每次一輛車（周五兩輛）5每周運(yùn)兩次、每次一輛車C1、2每周運(yùn)一次、每次一輛車3每周運(yùn)三次、每次一輛車（周五兩輛）4每周運(yùn)三次、每次一輛車D1、2每周運(yùn)一

22、次、每次一輛車3每周運(yùn)兩次、每次一輛車4每周運(yùn)兩次、每次一輛車E1、3每周運(yùn)兩次、每次一輛車2每周運(yùn)兩次、每次一輛車F1、2每周運(yùn)一次、每次一輛車3每周運(yùn)一次、每次一輛車G1、2每周運(yùn)一次、每次一輛車3每周運(yùn)一次、每次一輛車H1每周運(yùn)一次、每次一輛車2、3每周運(yùn)一次、每次一輛車I1、2每周運(yùn)一次、每次一輛車J1、2每周運(yùn)一次、每次一輛車K1、2每周運(yùn)一次、每次一輛車L1、3每周運(yùn)一次、每次一輛車2每周運(yùn)兩次、每次一輛車M1、2、3每周運(yùn)一次、每次一輛車N1、2每周運(yùn)一次、每次一輛車O1每周運(yùn)兩次、每次一輛車2每周運(yùn)兩次、每次一輛車P1每周運(yùn)兩次、每次一輛車2、3每周運(yùn)一次、每次一輛車Q1每周運(yùn)

23、兩次、每次一輛車R1每周運(yùn)兩次、每次一輛車2每周運(yùn)兩次、每次一輛車3每周運(yùn)一次、每次一輛車4、5每周運(yùn)兩次、每次一輛車S1、2每周運(yùn)一次、每次一輛車3每周運(yùn)兩次、每次一輛車4每天運(yùn)一次、每次一輛車5每周運(yùn)兩次、每次一輛車T1、2每周運(yùn)一次、每次一輛車3每周運(yùn)一次、每次一輛車4每周運(yùn)兩次、每次一輛車5每天運(yùn)一次、每次一輛車5.1.7 確定卸貨點(diǎn)的位置由于人力物力有限，公司不可能將貨物送到每一個(gè)顧客的位置。因此在向每個(gè)區(qū)域送貨時(shí)，運(yùn)貨車會(huì)將貨物卸在指點(diǎn)地點(diǎn)，即卸貨點(diǎn)。顧客會(huì)到離其最近的卸貨點(diǎn)取貨。在確定卸貨點(diǎn)時(shí)，我們以每個(gè)小區(qū)為單位進(jìn)行單獨(dú)劃分，即分別在65個(gè)小區(qū)內(nèi)，確定該小區(qū)的卸貨點(diǎn)數(shù)量和具體位

24、置。在這里我們將選取其中一個(gè)區(qū)域進(jìn)行求解，其他區(qū)域以此類推即可。接下來，我們針對某個(gè)區(qū)域的情況做進(jìn)一步的分析。我們選定圖中的E2區(qū)域進(jìn)行分析。其中共包含435個(gè)顧客。首先我們根據(jù)卸貨點(diǎn)的大致分布，將該區(qū)域的卸貨點(diǎn)數(shù)量定為4個(gè)，之后通過聚類分析法求解卸貨點(diǎn)具體位置。我們采取k均值聚類算法：k均值聚類算法是最著名的劃分聚類算法，由于簡潔和效率使得他成為所有聚類算法中最廣泛使用的。給定一個(gè)數(shù)據(jù)點(diǎn)集合和需要的聚類數(shù)目k，k由用戶指定，k均值算法根據(jù)某個(gè)距離函數(shù)反復(fù)把數(shù)據(jù)分入k個(gè)聚類中。先隨機(jī)選取K個(gè)對象作為初始的聚類中心。然后計(jì)算每個(gè)對象與各個(gè)種子聚類中心之間的距離，把每個(gè)對象分配給距離它最近的聚類中

25、心。聚類中心以及分配給它們的對象就代表一個(gè)聚類。一旦全部對象都被分配了，每個(gè)聚類的聚類中心會(huì)根據(jù)聚類中現(xiàn)有的對象被重新計(jì)算。這個(gè)過程將不斷重復(fù)直到滿足某個(gè)終止條件。終止條件可以是以下任何一個(gè)：1)沒有（或最小數(shù)目）對象被重新分配給不同的聚類。2)沒有（或最小數(shù)目）聚類中心再發(fā)生變化。3)誤差平方和局部最小。具體算法如下:1、初始化：選擇c個(gè)代表點(diǎn)p1,p2,p3pc2、建立c個(gè)空間聚類表k1,k2,k3kc3、按照最小距離法則逐個(gè)對樣本進(jìn)行分類：j=argminx,pi,add(x,kJ)4、計(jì)算J及用各聚類列表計(jì)算聚類均值，并用來作為各聚類新的代表點(diǎn)（更新代表點(diǎn)）5、若J不變或代表點(diǎn)未發(fā)生變

26、化，則停止。否則轉(zhuǎn)2.6、J=i=1Cxki(x,pi)最終根據(jù)matlab計(jì)算，我們得出了四個(gè)卸貨點(diǎn)的具體坐標(biāo)。卸貨點(diǎn)緯度經(jīng)度1108.077119532333026.8139384253416002108.121076857626127.0261090637714683108.106626068588926.8934638514998604108.167922004833926.934386472004310得出卸貨點(diǎn)坐標(biāo)后，我們將E2區(qū)域內(nèi)各點(diǎn)的坐標(biāo)代入，求出對于每個(gè)顧客距離最近的卸貨點(diǎn)，進(jìn)而統(tǒng)計(jì)出，4個(gè)卸貨點(diǎn)的卸貨量。卸貨點(diǎn)周一貨量周二貨量周三貨量周四貨量周五貨量總貨量10430027

27、4427872124226553375259318491171431114293005014574153800001538合計(jì)3894299133752593464317496由此可知一周之內(nèi)該區(qū)域總共需要17496箱貨物，根據(jù)計(jì)算我們可知一輛貨車一周往返兩次，即可滿足運(yùn)貨需求，與之前的預(yù)計(jì)相符。如果貨車走完該區(qū)域用時(shí)遠(yuǎn)小于8小時(shí)，則可以回到配送中心后進(jìn)行其他區(qū)域的運(yùn)貨任務(wù)。5.1.8運(yùn)用Floyd算法確定任意兩個(gè)卸貨點(diǎn)之間的最短距離 貨車需要經(jīng)過每一個(gè)卸貨點(diǎn)并且返回起點(diǎn)，這個(gè)問題是一個(gè)典型的旅行售貨員問題（TravellingSalesmanProblem）。為求解這個(gè)問題，我們將首先利用F

28、loyd算法求解出任意兩個(gè)卸貨點(diǎn)之間的最短距離，之后求解出遍歷這4個(gè)卸貨點(diǎn)的最優(yōu)Hamilton回路。即可得到貨車行駛的最佳路徑。首先，我們將用戶位置、卸貨點(diǎn)以及其附近交通道路的圖像繪制出來，如圖3所示。 圖3 卸貨點(diǎn)位置圖其中紅色小五角星為利用聚類算法計(jì)算所得的卸貨點(diǎn)。接下來，我們利用Floyd算法計(jì)算每兩點(diǎn)之間的最短距離。Floyd算法是解決任意兩點(diǎn)間的最短路徑的一種算法，可以正確處理有向圖或負(fù)權(quán)的最短路徑問題。下面說明Floyd算法的原理。G代表一個(gè)連通賦權(quán)圖，p代表G圖中所有的節(jié)點(diǎn)個(gè)數(shù)，vi代表G圖中的第i個(gè)節(jié)點(diǎn)，w(vi,vj)代表vi和vj節(jié)點(diǎn)之間路徑的權(quán)，權(quán)可以表示各種實(shí)際意義，

29、此處表示兩點(diǎn)之間的距離。1)首先取D(0)=(lij(0)pp，稱為G的邊權(quán)矩陣。這里lij(0)= w(vi,vj)，1i，jp。2)計(jì)算出p個(gè)矩陣D(1)，D(2)，D(p)，其中第k個(gè)矩陣D(k)的元素l(k) ij表示從vi到vj，而中間頂點(diǎn)僅屬于vi到vj的k個(gè)節(jié)點(diǎn)的所有道路中的道路長。已知D(k-1)=(lij(k-1)pp，則第k個(gè)矩陣D(k)= (lij(k)pp，k=1,2,p定義為lij(k)=minlij(k-1),lik(k-1)+lkj(k-1)3)當(dāng)k=p時(shí)終止。這時(shí)，D(p)中的元素lij(p)之值就是頂點(diǎn)vi與vj之間的最短路之值d(vi,vj)。為了簡便計(jì)算，

30、我們尋找離卸貨點(diǎn)最近的公路節(jié)點(diǎn)作為“真實(shí)卸貨點(diǎn)”。利用公式L=100xi-x02+111yi-y02和Excel軟件我們計(jì)算出了距離每個(gè)卸貨點(diǎn)最近的公路節(jié)點(diǎn)。如下表所示。卸貨點(diǎn)原經(jīng)度原緯度真實(shí)經(jīng)度真實(shí)緯度1108.077119532333026.813938425341600108.079526.811972108.121076857626127.026109063771468108.123627.025733108.106626068588926.893463851499860108.11226.891234108.167922004833926.934386472004310108.175

31、726.93361接下來，我們通過Excel畫散點(diǎn)圖并與利用Matlab所畫的道路圖對比的方式找到了每個(gè)公路拐點(diǎn)以及交匯點(diǎn)的坐標(biāo)。其中拐點(diǎn)是為了方便計(jì)算兩點(diǎn)距離而取的。取的原則是盡量使兩個(gè)拐點(diǎn)經(jīng)緯度所框成的矩形包含兩個(gè)拐點(diǎn)之間的路徑，并且不包含不是兩個(gè)拐點(diǎn)之間路徑的其他路徑。圖4所得點(diǎn)經(jīng)緯度見下表。點(diǎn)123456789101112緯度26.8119727.0257326.8912326.9336126.9375116426.9912411426.8402425126.9315200626.9678423326.9758546726.995018126.83768經(jīng)度108.0795108.12

32、36108.112108.1757108.1415419108.1299265108.0853806108.177078108.2052113108.2031589108.191681108.1071圖5其中為真實(shí)卸貨點(diǎn)。利用Excel我們算出了每個(gè)相連接點(diǎn)之間的距離。具體數(shù)值見下表。節(jié)點(diǎn)123456789101112105.152545403205.187777757308.7028340899.384740454400.80191828407028340890.80191828408.79807965.1877777578.79807909.01318701279

33、.38474045401.5964787088071880627594.71880627501.029350188101.02935018801.207636639119.0131870121.2076366390125.1525454031.5964787080單位km其中表示兩個(gè)節(jié)點(diǎn)沒有直接連接。得出了這十二個(gè)點(diǎn)之后，我們現(xiàn)在對其進(jìn)行簡化，刪除不必要的點(diǎn)，利用上表得出的各個(gè)點(diǎn)之間的距離算出剩下節(jié)點(diǎn)任意兩點(diǎn)之間的距離，可得下表。節(jié)點(diǎn)1234561016187777757316.1337645708.702834089400.80191828

34、416.1091965958.7028340890.80191828408.79807965109196598.7980790由此可得矩陣WW=016.13376457051337645708.70283408900.80191828416.109196598.7028340890.80191828408.7980795109196598.7980790將W代入Floyd算法中即可算出這六個(gè)節(jié)點(diǎn)間任意兩個(gè)節(jié)點(diǎn)之間的最短距離，F(xiàn)loyd算法的代碼可見附錄，其中path矩陣為兩個(gè)節(jié)點(diǎn)間所經(jīng)過節(jié)點(diǎn)的矩陣。計(jì)算結(jié)果如下。D=

35、038.822516.133825.638524.836633.634738.822522.688714.787813.98595.187816.133822.688709.50488.702817.500925.638514.78789.504800.80199.600024.836613.98598.70280.801908.7981 33.63475.187817.50099.6000 8.79810path=133333626666153555555455363456 5255 56由D可得任意兩點(diǎn)間最短距離節(jié)點(diǎn)1234561038.822516.133825.638524.83663

36、3.6347238.8225022.688714.787813.98595.1878316.133822.688709.50488.702817.5009425.638514.78789.504800.80199.6000524.836613.98598.70280.801908.7981633.63475.187817.50099.60008.79810單位km，其中1、2、3、4為卸貨點(diǎn)。由path矩陣可以看出任意兩點(diǎn)之間最短路徑所需要經(jīng)過的節(jié)點(diǎn)。例如，從1點(diǎn)到4點(diǎn)，查詢path矩陣第一行第四列與第四行第一列可知，從1點(diǎn)到4點(diǎn)需要經(jīng)過3，5兩點(diǎn)，再結(jié)合圖5可以推斷出，從1節(jié)點(diǎn)到4節(jié)點(diǎn)的最短

37、路徑為1354。其他各個(gè)最短路徑也可以依照此方法推斷出。具體結(jié)果可見下表。終點(diǎn)起點(diǎn)123456111356213135413513562265312265326542652633135623354353564453145624534454565531562535455666531626536546565.1.9利用最優(yōu)Hamilton回路模型求解貨車最短巡回路線上文已經(jīng)提及求解貨車最短巡回路線的問題是一個(gè)旅行售貨員問題（TravellingSalesmanProblem）。我們將利用Excel的規(guī)劃求解工具來解答。首先簡介一下關(guān)于Hamilton回路的相關(guān)定義。若圖G的一個(gè)回路C中含有G的所有

38、頂點(diǎn)，則稱此回路為G的一個(gè)Hamilton回路。而在一個(gè)賦權(quán)完全圖中，具有最小權(quán)的Hamilton回路稱為最優(yōu)Hamilton回路。具體到我們目前所求解的問題中，上述定義的權(quán)即指距離，最小權(quán)即距離最短。下面我們開始求解。容易求得四個(gè)卸貨點(diǎn)中距離配送中心最近的點(diǎn)為卸貨點(diǎn)1。故在此處選取卸貨點(diǎn)1為巡回路線起點(diǎn)。根據(jù)已知條件，我們在Excel中建立規(guī)劃求解所需的公式模型。如下圖所示。其中，C10:F13單元格區(qū)域用于記錄實(shí)際路徑選擇情況，用數(shù)字0表示路徑未選擇，用數(shù)字1表示選擇從某地出發(fā)前往另一地。此區(qū)域?qū)⒆鳛橐?guī)劃求解的可變單元格區(qū)域。G列用于統(tǒng)計(jì)抵達(dá)各點(diǎn)的來源地?cái)?shù)目，根據(jù)所需求解的最優(yōu)Hamilt

39、on回路易知，每個(gè)地點(diǎn)的訪問來源地是唯一確定的，即最后求解出的G列數(shù)值應(yīng)都為1。G10的值應(yīng)為C10、D10、E10、F10之和，G11、G12、G13同理可得。故在G10單元格內(nèi)輸入公式G10=SUM(C10:F10),并向下復(fù)制填充至G13單元格。第14行用于統(tǒng)計(jì)各出發(fā)點(diǎn)前往目的地的數(shù)目。同樣的，每個(gè)出發(fā)點(diǎn)的目標(biāo)地點(diǎn)也是唯一確定的，即14行求解出的值應(yīng)為1。C14單元格內(nèi)的公式為C14=SUM(C10:C13),向右復(fù)制填充至F14單元格。H列用于統(tǒng)計(jì)訪問線路確定的情況下各條線路所需的時(shí)間。下面H10單元格求值為例，此處的所需路程可用第3行對應(yīng)的四個(gè)值與第10行的值對應(yīng)相乘得到，假設(shè)出發(fā)地

40、為3抵達(dá)地為1，則第3行與第10行相乘為00+38.82250+16.13381+25.63850=16.1338，即H10為16.1338。故在H10輸入公式H10=SUMPRODUCT(C3:F3,C10:F10),然后向下復(fù)制至H13。H14單元格用于累積總路程，H14=SUM(H10:H13),此單元格將作為規(guī)劃求解的目標(biāo)單元格。選中H14單元格，打開【歸化求解參數(shù)】對話框。具體設(shè)置如圖所示。C10:F13取值為0或1，故將其設(shè)為二進(jìn)制。C10、D11、E12、F13等對角線上單元格取值應(yīng)為0。求得結(jié)果如下圖由圖可知，此結(jié)果包含了兩個(gè)獨(dú)立回路13，24。這與我們所需求的結(jié)果不符。針對此

41、問題，我們將添加充分的約束條件以避免子巡回的產(chǎn)生。下面引出不等式Ui-Uj+nXijn-1 , 2ijn，其中n為節(jié)點(diǎn)數(shù)。此不等式為一個(gè)不含子巡回的完整巡回的充要條件，以下為證明。以所求問題為例，U1表示卸貨點(diǎn)1是第幾個(gè)到達(dá)的，用U2表示卸貨點(diǎn)2是第幾個(gè)到達(dá)的，以此類推，U4就是表示卸貨點(diǎn)4是第幾個(gè)到達(dá)的。X12表示線路是否為從卸貨點(diǎn)1到卸貨點(diǎn)2，如果是就為1，否則為O,即為C11單元格的值。所求問題中n=4，故不等式為Ui-Uj+4Xij3 , 2ij4。必要性：一個(gè)完整巡回必然滿足此公式。一、如果巡回中存在卸貨點(diǎn)1到卸貨點(diǎn)2的路線，兩個(gè)卸貨點(diǎn)是直接相連的，且卸貨點(diǎn)1在卸貨點(diǎn)2之前，則有U1

42、-U2=-1，X12=1，按照公式所得運(yùn)算結(jié)果是33，滿足條件。若卸貨點(diǎn)1在卸貨點(diǎn)2之后，則有U1-U2=1，X12=0，運(yùn)算結(jié)果是13，滿足條件。二、如果卸貨點(diǎn)1與卸貨點(diǎn)2不相連，卸貨點(diǎn)1在卸貨點(diǎn)2之前，U1-U20，最大值是4-1=3，同時(shí)X12=0，結(jié)果為33同樣滿足條件。充分性：滿足此公式必然是單個(gè)完整巡回，此處用反證法來證明。假設(shè)存在子巡回滿足這個(gè)公式，那么必然至少有兩個(gè)子巡回。為了便于理解，現(xiàn)定義13為一個(gè)子巡回，24為一個(gè)子回路，那么卸貨點(diǎn)2和卸貨點(diǎn)4是連通的，即X24與X42都等于1，卸貨點(diǎn)2在第3位，卸貨點(diǎn)4在第4位，按照公式計(jì)算從卸貨點(diǎn)4到卸貨點(diǎn)2是4-3+41=5，大于3

43、，不符合條件，說明存在子巡回不能滿足公式，所以假設(shè)不成立，得證。接下來在Excel中應(yīng)用此公式。在第9行下插入新的第10行，B10輸入線路順序。如下圖所示。按照公式，建立輔助區(qū)域，C17單元格輸入公式：C7=C$10，向右復(fù)制填充至F17。選中C17:F17單元格區(qū)域，復(fù)制并轉(zhuǎn)置粘貼到B18:B21區(qū)域。接下來在C18中輸入公式：C18=C$17-$B18+4*C11，向右復(fù)制粘貼至F18單元格，再向下復(fù)制填充至F21單元格。由公式限定，ij，且都大于1，故C18:F18，C19:C21以及對角線單元格D19、E20、F21，全部清空數(shù)據(jù)。接下來添加必要約束條件，在【歸化求解參數(shù)】對話框中設(shè)置

44、如下。為減小誤差【選項(xiàng)】中設(shè)置如下。最終計(jì)算結(jié)果見下圖。故最短巡回路徑為：13241最短巡回路徑長度為：79.2488km最短巡回時(shí)間為：1.585h5.1.10設(shè)計(jì)車輛調(diào)度方案結(jié)合已經(jīng)得出的大致配送方案和單個(gè)區(qū)域內(nèi)的最短行駛路線，我們對實(shí)際的車輛安排進(jìn)行了以下統(tǒng)一：1、根據(jù)區(qū)域內(nèi)貨物每周的需求量，進(jìn)行車輛安排。上一問題中，我們發(fā)現(xiàn)所選區(qū)域內(nèi)貨車送貨最短時(shí)間只需1.585h，遠(yuǎn)小于一天工作時(shí)間8h。因此我們推斷，負(fù)責(zé)較近區(qū)域的貨車可在一天內(nèi)往返2次。只往返一次的貨車亦可在一天內(nèi)負(fù)責(zé)2-3個(gè)貨量較少相鄰區(qū)域。所以當(dāng)某區(qū)域內(nèi)需貨量遠(yuǎn)小于一輛貨車的載貨量時(shí)，可由相鄰區(qū)域安排貨車同時(shí)運(yùn)送兩個(gè)區(qū)域的貨物

45、。且可對顧客的貨物進(jìn)行囤積，在訂貨周期內(nèi)送達(dá)即可。2、車次不代表安排貨車的數(shù)量，同一輛貨車一天可視情況走多個(gè)車次。大區(qū)小區(qū)小區(qū)周總訂貨量小區(qū)周總車次大區(qū)小區(qū)小區(qū)周總訂貨量小區(qū)周總車次A19312J1220212134221739072K19311439213521342545181L12841B15522318582132432131802383201M14081143709852283551743923212C122801N13334123538239773252633O111468241852632157262D111841P11103322731223095131621223105412

46、1552Q1169052E125252R11185823918321634922174962352421F1167314967622287552886360061S168132G17911217102636431228023459514225793H127271512786232918T154931253211214262I137231390812125241679325280364合計(jì)總車次82結(jié)論：分析得出，全城每周運(yùn)輸貨物需要82個(gè)車次，考慮到有的貨車可以一天往返2次，以及每周工作5天，則一共需要約10輛車負(fù)責(zé)每周的配送。再進(jìn)一步考慮貨車到卸貨點(diǎn)卸貨花費(fèi)的時(shí)間，貨車修理和司機(jī)輪休的影響，我們最終安排15輛車來進(jìn)行配送。問題二主要涉及選址分配的多韋伯問題。我們先運(yùn)用聚類的思路將各區(qū)域集合成點(diǎn)，再根據(jù)無約束多元選址問題的思路求解，找到了五個(gè)配送中心及其配送范圍。5.2