【文章內(nèi)容簡(jiǎn)介】 接下來我們只需確定貨車在一個(gè)區(qū)域的最短行駛路線即可。[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(n1)構(gòu)造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號(hào)頂點(diǎn)到j(luò)號(hào)頂點(diǎn)的最短路徑長(zhǎng)度，稱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）01020304050607121314151617232425262734353637454647565767[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作哈密頓路徑。 對(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)路徑（見附錄程序）。綜合上述方法，可求：最短路線： 最短路程：。圖5 區(qū)域①貨物的最佳路線圖 上述，我們已經(jīng)解決了某個(gè)區(qū)域的供貨方式和行駛路徑問題，以下我們做出整體的配送方案。，我們做以下安排，當(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 一、粗糙模型 以及總車次數(shù)為112。根據(jù)以上結(jié)果，我們近似估計(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è)部分，均勻送貨。 若所有貨物都必須當(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í)間8h8h5h4h8h需求量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)度方案。 對(duì)問題二的求解 問題二中，我們需要在原圖中再安置5個(gè)配送中心，從而使配送更快捷，服務(wù)更優(yōu)化，使目標(biāo)函數(shù)取得最優(yōu)解。 確定八個(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)度緯度12345678 在matlab中繪制二維圖可以看出八個(gè)待定點(diǎn)的位置如下：圖7 待定點(diǎn)方位圖 我們現(xiàn)在要做的工作是在8個(gè)待定點(diǎn)中確定5個(gè)最終要選取的配送中心位置并為各配送網(wǎng)點(diǎn)劃分配送范圍。明顯可以看出，這是一個(gè)多韋伯問題[7]（multiWeber problem）,它既包括用戶的分配，又包括設(shè)施在空間上的定位，所以通常又把設(shè)施定位問題稱為設(shè)施定位分配問題。設(shè)施定位問題是指在空間上尋找合適的設(shè)施布局，使用戶與設(shè)施相互作用的費(fèi)用滿足某一準(zhǔn)則的問題，共有18種準(zhǔn)則，但最常用有三種準(zhǔn)則，即“總和最小化”（MinSum）準(zhǔn)則、“最大