《數(shù)學(xué)建模論文-物資調(diào)度問題》

1、物資調(diào)度問題摘要“運(yùn)輸調(diào)度數(shù)學(xué)模型是通過運(yùn)輸車運(yùn)輸路線確實(shí)定以及運(yùn)輸車調(diào)配方案確實(shí)定來使運(yùn)輸?shù)幕ㄙM(fèi)最小。本文首先分析了物資調(diào)度中運(yùn)費(fèi)、載重量及各站點(diǎn)需求量間相互關(guān)系。而后，緊抓住總運(yùn)營費(fèi)用最小這個(gè)目標(biāo)，找出最短路徑，最后完成了每輛運(yùn)輸車的最優(yōu)調(diào)度具體方案。問題一：根據(jù)題目及實(shí)際經(jīng)驗(yàn)得出運(yùn)輸車運(yùn)輸物資與其載重量及其行駛的路程成正比例關(guān)系，又運(yùn)輸?shù)膬r(jià)格一定，再結(jié)合題目給出的條件“運(yùn)輸車重載運(yùn)費(fèi)2元/噸公里，其重載運(yùn)費(fèi)的單位“元/噸公里給我們的啟發(fā)。于是結(jié)合題目給定的表，我們將兩個(gè)決策變量載重量，路程化零為整為一個(gè)花費(fèi)因素來考慮，即從經(jīng)濟(jì)的角度來考慮。同理我們將多輛車也化零為整，即用一輛“超大運(yùn)輸車

2、來運(yùn)輸物資。根據(jù)這樣從經(jīng)濟(jì)的角度來考慮，于是我們將需求點(diǎn)的需求量乘入需求點(diǎn)的坐標(biāo)得到一個(gè)新的表，即花費(fèi)經(jīng)濟(jì)表，我們再運(yùn)用數(shù)學(xué)軟件作出一個(gè)新的坐標(biāo)，這樣可以得到一個(gè)花費(fèi)坐標(biāo)。于是按照從經(jīng)濟(jì)花費(fèi)最少的角度，根據(jù)我們所掌握的最短路徑及算法再結(jié)合數(shù)學(xué)軟件，可求得經(jīng)濟(jì)花費(fèi)坐標(biāo)上的最短路徑。具體求法上，采用了算法結(jié)合“最優(yōu)化原理，先保證每個(gè)站點(diǎn)的運(yùn)營費(fèi)用最小，從而找出所有站點(diǎn)的總運(yùn)營費(fèi)用最小，即找出了一條總費(fèi)用最低的最短路徑。用我們的“超大運(yùn)輸車“化整為零的思想，將該路線分為八條路徑。同時(shí)也將超大車進(jìn)行分解，于是派八輛運(yùn)輸車向29個(gè)需求點(diǎn)運(yùn)送物資。同樣的道理我們也將運(yùn)輸車運(yùn)送物資從經(jīng)濟(jì)的角度看，即將運(yùn)量乘

3、以其速度，又因運(yùn)輸?shù)膬r(jià)格一定，因此便可以將運(yùn)輸車在整體上從經(jīng)濟(jì)考慮。于是便可以將整體從經(jīng)濟(jì)上來考慮。將運(yùn)輸最小花費(fèi)轉(zhuǎn)化從經(jīng)濟(jì)方面來考慮比擬合理。由此可求解出運(yùn)輸車全程的最低費(fèi)用：結(jié)合各約束條件求得最低費(fèi)用為1980.16元。問題二：由題目知運(yùn)輸車的載重量不同，但由于我們從整體的經(jīng)濟(jì)上來考慮運(yùn)輸物資的花費(fèi)最少問題，因此花費(fèi)坐標(biāo)的最短路徑仍然不變。因此結(jié)合運(yùn)輸車工作時(shí)間的這個(gè)因素，我們?nèi)杂脝栴}一的思路，運(yùn)用“化零為整，“化整為零的思想來考慮第二問。按照這樣的的思路我們制定了八條路線，派了七輛運(yùn)輸車來運(yùn)送物資。同樣在整體上對(duì)問題從經(jīng)濟(jì)上來考慮比擬合理。結(jié)合各約束條件求得最低費(fèi)用為1969.66元，需

4、要7輛車關(guān)鍵詞：物資調(diào)度 最短路線 最優(yōu)化原理 Dijkstra算法 0-1規(guī)劃一、問題重述1.1. 背景資料與條件某城區(qū)有29個(gè)物資需求點(diǎn)，需求點(diǎn)的地理坐標(biāo)和每天物資的需求量見如下表一。表一為原表截取的一局部，原表其余局部見附錄一。每天凌晨都要從倉庫第30號(hào)站點(diǎn)出發(fā)將物資運(yùn)至每個(gè)需求點(diǎn)?，F(xiàn)有一種運(yùn)輸車，載重 6噸，運(yùn)輸車平均速度為40公里小時(shí)，每臺(tái)車每日工作 4小時(shí)，每個(gè)需求點(diǎn)需要用10分鐘的時(shí)間下貨。公里；并且街道方向均平行于坐標(biāo)軸。29個(gè)需求點(diǎn)物資需求量及地理坐標(biāo)站點(diǎn)編號(hào)需求量T坐標(biāo)(km)站點(diǎn)編號(hào)需求量T坐標(biāo)(km)xyxy1321621621517618354181117447191

5、51250820199631121225下列圖為29個(gè)需求點(diǎn)的地理坐標(biāo)示意圖：圖一：各需求點(diǎn)地理坐標(biāo)圖問題一：在運(yùn)輸車的載重固定為6噸的情況下，為使運(yùn)輸費(fèi)用最小，怎樣調(diào)動(dòng)運(yùn)輸車包括運(yùn)輸車的數(shù)量,每臺(tái)車的運(yùn)營路線及費(fèi)用。問題二：在運(yùn)輸車的載重分為三類四噸，六噸，八噸的情況下，為使運(yùn)輸費(fèi)用最小，怎樣調(diào)動(dòng)運(yùn)輸車包括運(yùn)輸車的數(shù)量,每臺(tái)車的運(yùn)營路線及費(fèi)用。二、問題分析2.1.問題的重要性分析社會(huì)背景現(xiàn)代社會(huì)經(jīng)濟(jì)高速開展，各種信息物資交流頻繁，特別是當(dāng)今，對(duì)如何優(yōu)化物資分配，降低經(jīng)濟(jì)本錢，時(shí)間本錢的要求十分迫切。研究在使費(fèi)用最小情況下的物資調(diào)度問題，對(duì)于滿足各地物資需求，優(yōu)化資源配置，促進(jìn)經(jīng)濟(jì)社會(huì)開展具有

6、十分重要的意義。. 有關(guān)方面在這個(gè)問題上做過的研究2物流配送車輛優(yōu)化調(diào)度問題最早是由學(xué)者 Dantzig和 Ramser 于 1959 年首次提出的,國外一般稱之為vehicle routing problem或vehicle scheduling problem.一般以為 ,不考慮時(shí)間要求 ,僅根據(jù)空間位置安排線路時(shí)稱為車輛線路安排問題VRP ;考慮時(shí)間要求 ,安排線路時(shí)稱為車輛調(diào)度問題VSP。目前針對(duì)車輛優(yōu)化調(diào)度問題的求解算法可以說是相當(dāng)豐富,根據(jù)對(duì)這些算法本質(zhì)的分類研究 ,根本上可以分為精確算法和啟發(fā)式算法兩大類. 精確算法指可求出最優(yōu)解的算法 ,主要有分枝定界法、 割平面法、 網(wǎng)絡(luò)流算

7、法和動(dòng)態(tài)規(guī)劃法.精確算法的計(jì)算量一般隨問題規(guī)模的增大而呈指數(shù)增長 ,所以多用于規(guī)模較小的問題。啟發(fā)式算法是指一種基于直觀或經(jīng)驗(yàn)構(gòu)造的算法 ,目標(biāo)是在可接受的花費(fèi)(計(jì)算時(shí)間、 占用空間等)下得出待解決問題的滿意解 ,而不是最優(yōu)解.考慮到VRP是強(qiáng)NP難題 ,而啟發(fā)式方法能夠比擬快地得到滿意解 ,這對(duì)解決NP難題來說有著不可估量的作用.因此大局部文獻(xiàn)中專家們主要是在構(gòu)造各種高質(zhì)量的啟發(fā)式算法。倉庫物資由運(yùn)輸車進(jìn)行調(diào)運(yùn)。每輛車的工作時(shí)間不超過4小時(shí)，并且每輛車的載重不能超過6噸。假設(shè)調(diào)運(yùn)的需求地點(diǎn)已經(jīng)明確，為了使運(yùn)費(fèi)最小，必須用最少的車在允許的工作時(shí)間內(nèi)把需要運(yùn)送的物資運(yùn)送到需求地點(diǎn)，因此選擇什么樣

8、的調(diào)運(yùn)路線和派遣多少車輛顯得尤為重要。本論文試圖從最短路程和最小花費(fèi)的角度，建立起滿足調(diào)運(yùn)費(fèi)用最少且調(diào)用車輛最少的數(shù)學(xué)模型，求出倉庫派遣的車輛的數(shù)量和運(yùn)送路線。問題一的分析：.“化零為整，求最短路此題要求在使總運(yùn)輸費(fèi)用最小的情況下，安排這29個(gè)運(yùn)輸點(diǎn)的車輛調(diào)度方案。先考慮運(yùn)輸車運(yùn)往各個(gè)需求地的總運(yùn)輸最小費(fèi)用。假設(shè)從倉庫0,0點(diǎn)開始，車先運(yùn)往地，此時(shí)運(yùn)費(fèi)最??；再運(yùn)往地，保證從地到地的總運(yùn)費(fèi)也是最小的；車再運(yùn)往地，保證此時(shí)地與地的運(yùn)費(fèi)仍是最??；即假設(shè)每兩地之間的運(yùn)輸費(fèi)用都是最小的，那么將所有聯(lián)通的兩個(gè)需求地的運(yùn)費(fèi)求和仍是最少的運(yùn)費(fèi)。即假設(shè)為地和地的最小運(yùn)輸費(fèi)用，為0-1變量，即兩地與假設(shè)聯(lián)通，那么

9、為1，假設(shè)兩地不連通，那么為0。在運(yùn)輸車運(yùn)往個(gè)需求點(diǎn)的過程中，總運(yùn)輸最小費(fèi)用為：針對(duì)地，根據(jù)實(shí)際情況，其運(yùn)輸費(fèi)用與該地的需求量及地到地的距離均成正比，故將地的需求量和地理位置合成一個(gè)新量，倉庫0,0到各個(gè)需求點(diǎn)的最短路徑即為總運(yùn)輸費(fèi)用最小的路徑。求總最小運(yùn)輸費(fèi)用在運(yùn)輸車從各個(gè)需求點(diǎn)回到倉庫的過程中，由于最短路已經(jīng)確定，因而返回時(shí)按每條運(yùn)輸路線上終止需求點(diǎn)到倉庫的最短路徑，就可求出整個(gè)運(yùn)輸車運(yùn)送物資與返回全過程的最小費(fèi)用。即在運(yùn)輸車往返需求點(diǎn)的全過程中的最小費(fèi)用為 .化整為零，調(diào)度車輛，分配每輛車運(yùn)輸線路根據(jù)本文前局部的求解，能求出從倉庫到29個(gè)需求點(diǎn)的最短物資調(diào)度線路，那么調(diào)度車輛要考慮的因素

10、是使總運(yùn)費(fèi)最小及使用的車輛盡量少。因?yàn)樵趯?shí)際物資調(diào)度過程中，派出一輛車的固定費(fèi)用遠(yuǎn)高于一輛車的行駛費(fèi)用，因此調(diào)度的車輛盡可能少也是優(yōu)化車輛調(diào)度的一個(gè)重要考慮因素。本文在此提供兩種方案。第一種方案：假設(shè)每輛運(yùn)輸車滿載，即載重均為6噸，假設(shè)運(yùn)輸車在運(yùn)到第個(gè)運(yùn)輸點(diǎn)時(shí)，將6噸貨全部卸完，此時(shí)運(yùn)輸?shù)降氐奈镔Y小于地的需求量，那么車返回，車?yán)^續(xù)往地送貨，滿足地的需求量后繼續(xù)前進(jìn)，按此種運(yùn)輸方式運(yùn)輸往各個(gè)需求地的需求量，直至第29個(gè)需求點(diǎn)。即在此過程中，假設(shè)有一輛“超級(jí)大車，載重了29個(gè)需求點(diǎn)的全部物資，每到一個(gè)需求點(diǎn)，就卸下一局部物資，直至最后一個(gè)需求點(diǎn)。第二種方案：假設(shè)每輛運(yùn)輸車不一定滿載，車在運(yùn)送完最短

11、路上指定的幾個(gè)需求點(diǎn)后，即空載返回，車沿著最短路線，繼續(xù)運(yùn)送物資。即在此種方案下，每個(gè)需求點(diǎn)只有一輛車來運(yùn)送物資。問題二的分析：在第一問已求出最短路的前提下，第二問中提供了三種載重不同的運(yùn)輸車。即在這種條件下，能夠繼續(xù)優(yōu)化調(diào)度方案，使載重大的車(8噸的車)，運(yùn)送離倉庫較近的需求地的物資，使這幾個(gè)需求地的物資總和盡量接近于8噸。載重越小的車，運(yùn)往的需求地離倉庫越遠(yuǎn)。因?yàn)榇筌嚨倪\(yùn)營本錢最高。大車載重多，因而每公里的運(yùn)輸費(fèi)用最高)。思路圖：三、根本假設(shè)結(jié)合此題的實(shí)際，為了確保模型求解的準(zhǔn)確性和合理性，我們排除了一些位置因素的干擾，提出以下幾點(diǎn)假設(shè)：問題一的假設(shè)1.每輛車載重不同時(shí)速度均相等。2.忽略

12、運(yùn)輸車加速和制動(dòng)的速度變化及時(shí)間的影響。3.不考慮汽車在紅綠燈，堵車，惡劣天氣狀況時(shí)的延誤時(shí)間。4.每輛車派出的人工本錢，裝卸貨等固定本錢忽略不計(jì)。5.供給物資的公司能夠提供足夠多的車輛。不考慮其他因素，第j個(gè)需求點(diǎn)的運(yùn)費(fèi)與第j個(gè)需求點(diǎn)的需求量及倉庫到第j個(gè)需求點(diǎn)的位置均成正比。問題二的假設(shè)1.此題求解最小費(fèi)用不考慮實(shí)際情況中三種載重不同的運(yùn)輸車的固定本錢的差異。2、不考慮三種載重不同的運(yùn)輸車速度的不同。3.3.本文引用的數(shù)據(jù)、資料均真實(shí)可靠。四、符號(hào)說明為了便于問題的求解，我們給出以下符號(hào)說明：其他未說明的符號(hào)在文中第一次出現(xiàn)時(shí)會(huì)做詳細(xì)的說明。符號(hào)意義第i輛車需求點(diǎn)需求點(diǎn)和需求點(diǎn)之間的距離需

13、求點(diǎn)的物資需求量需求量乘位置后需求點(diǎn)的合成坐標(biāo)0-1變量需求點(diǎn)和需求點(diǎn)之間的費(fèi)用第輛車的總運(yùn)輸費(fèi)用：注一：注二: ，其中、均為題中所給的第個(gè)需求點(diǎn)的橫縱坐標(biāo)。五、模型的建立與求解5.1.問題一的求解模型一概述算法3：算法是典型最短路算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。算法能得出最短路徑的最優(yōu)解。算法描述：(這里描述的是從節(jié)點(diǎn)1開始到各點(diǎn)的算法，其中 表示的邊的權(quán)值，即為最短路徑值) 1 置集合數(shù)組, (1,之間存在邊) or +無窮大(1. 之間不存在邊) 2 在中，令，令，假設(shè)為空集那么算法結(jié)束，否那么轉(zhuǎn)3 3 對(duì)全部屬于

14、,如果存在邊，那么，轉(zhuǎn)2 算法思想為：設(shè)是一個(gè)帶權(quán)有向圖，把圖中頂點(diǎn)集合分成兩組，第一組為已求出最短路徑的頂點(diǎn)集合用表示，初始時(shí)中只有一個(gè)源點(diǎn)，以后每求得一條最短路徑 , 就將 參加到集合中，直到全部頂點(diǎn)都參加到中，算法就結(jié)束了，第二組為其余未確定最短路徑的頂點(diǎn)集合用表示，按最短路徑長度的遞增次序依次把第二組的頂點(diǎn)參加中。在參加的過程中，總保持從源點(diǎn)到中各頂點(diǎn)的最短路徑長度不大于從源點(diǎn)到中任何頂點(diǎn)的最短路徑長度。此外，每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離，中的頂點(diǎn)的距離就是從到此頂點(diǎn)的最短路徑長度，中的頂點(diǎn)的距離，是從到此頂點(diǎn)只包括中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長度。 算法具體步驟 1初始時(shí)，只包含源點(diǎn)，即

15、的距離為0。包含除外的其他頂點(diǎn)，中頂點(diǎn)距離為邊上的權(quán)假設(shè)與有邊或 假設(shè)不是的出邊鄰接點(diǎn)。 2從中選取一個(gè)距離最小的頂點(diǎn)，把參加中該選定的距離就是到的最短路徑長度。 3以為新考慮的中間點(diǎn)，修改中各頂點(diǎn)的距離；假設(shè)從源點(diǎn)到頂點(diǎn) 的距離經(jīng)過頂點(diǎn)比原來距離不經(jīng)過頂點(diǎn)短，那么修改頂點(diǎn)的距離值，修改后的距離值的頂點(diǎn)k的距離加上邊上的權(quán)。 4重復(fù)步驟2和3直到所有頂點(diǎn)都包含在中。最優(yōu)化原理:作為整個(gè)過程的最優(yōu)策略，它滿足相對(duì)前面決策所形成的狀態(tài)而言，余下的子策略必然構(gòu)成“最優(yōu)子策略。一個(gè)問題滿足最優(yōu)化原理也稱其擁有最優(yōu)子結(jié)構(gòu)性質(zhì)。模型一的運(yùn)用與求解1運(yùn)用整體思想，最短路思想的由來從倉庫開出任一輛運(yùn)輸車對(duì)物資

16、進(jìn)行調(diào)運(yùn)，到任意的未配送的需求點(diǎn)。要求運(yùn)輸車的工作時(shí)間小于等于4小時(shí)，各運(yùn)輸車的載重量不超過6噸。且。為使總費(fèi)用最小，那么應(yīng)使運(yùn)輸車從每一個(gè)需求點(diǎn)運(yùn)往下一個(gè)需求點(diǎn)的費(fèi)用最少?，F(xiàn)先采用“化零為整的思想，假設(shè)有一輛“超級(jí)運(yùn)輸車，裝載了29個(gè)需求地的所有所需物資之和，即首先，使運(yùn)輸車從倉庫運(yùn)往地的運(yùn)輸費(fèi)用最少，再從地運(yùn)往地的運(yùn)輸費(fèi)用最小，如此類推，假設(shè)運(yùn)輸車從每一個(gè)需求地運(yùn)往下一個(gè)需求地的都是費(fèi)用最少的最優(yōu)路徑，那么29個(gè)需求地的運(yùn)輸費(fèi)用之和就是最少的費(fèi)用。即運(yùn)輸車走的29個(gè)需求地的路徑即為總費(fèi)用最少的路徑。再采用“化整為零的思想，使所有運(yùn)輸車均排成一條長隊(duì)，依次經(jīng)過最短路徑，當(dāng)?shù)谝惠v車運(yùn)完所裝載物

17、資后，即空載撤回，第二輛車接著向下一個(gè)需求點(diǎn)運(yùn)送物資，在經(jīng)過最短路上相應(yīng)需求點(diǎn)運(yùn)送完所裝載物資后，也空載撤回，如此類推，直至最后一輛運(yùn)輸車運(yùn)送完全部所需物資。再次，我們假設(shè)運(yùn)輸車行駛的速度與其載重?zé)o關(guān)假設(shè)1。2由每個(gè)需求點(diǎn)的最小費(fèi)用轉(zhuǎn)化為求最短路設(shè)運(yùn)往需求點(diǎn)的費(fèi)用為，代表與相連接，且為連向的費(fèi)用最少的需求點(diǎn)。即在最短路徑上，“超大運(yùn)輸車先經(jīng)過，再經(jīng)過。運(yùn)輸?shù)馁M(fèi)用與該點(diǎn)的物資需求量及該點(diǎn)的地理坐標(biāo)=成正比例關(guān)系。對(duì)此我們將二者化零為整，將每個(gè)需求點(diǎn)的需求量乘以其坐標(biāo)得到新的坐標(biāo)。同時(shí)也將運(yùn)輸車的載重量乘以它的速度。將二者同時(shí)放在花費(fèi)的角度上金錢的角度上進(jìn)行求解。如此我們求了花費(fèi)上的最短距離，同時(shí)

18、我們設(shè)所有的運(yùn)輸車都載重6噸。對(duì)得到的最短行程做解，以得到最小的花費(fèi)。由上，設(shè)比例系數(shù)分別為。那么可表示為： = = = =即此處，將需求點(diǎn)的地理坐標(biāo)與需求量合成為一個(gè)新的坐標(biāo)，該坐標(biāo)表示的是需求點(diǎn)的運(yùn)輸費(fèi)用坐標(biāo)。那么題目轉(zhuǎn)化為求一條最短路，將所有的29個(gè)需求點(diǎn)連接，使總運(yùn)輸費(fèi)用最小。我們根據(jù)原始數(shù)據(jù)表表1，將需求量乘入各個(gè)需求點(diǎn)的坐標(biāo)建立一張新的表2。表二 各站點(diǎn)花費(fèi)坐標(biāo)表站點(diǎn)編號(hào)需求量T地理坐標(biāo)km花費(fèi)坐標(biāo)km*t站點(diǎn)編號(hào)需求量T地理坐標(biāo)km花費(fèi)坐標(biāo)km*txyxy132162162721156176183541811174244719151250820199631121225772221

19、089623279910224151910140251514111732226120173712146542722113681312928124204414101229251615714300000我們又用Mathematica作出一張坐標(biāo)圖程序見附錄二：圖二：各需求點(diǎn)花費(fèi)坐標(biāo)圖3最短路的求法根據(jù)最小生成樹及Dijkstra算法可求得花費(fèi)位置的最短路徑其中數(shù)據(jù)表，及Mathematica程序見附錄。流程圖如下：圖三：花費(fèi)最短路徑算法流程圖最后求得使總費(fèi)用最少的最短路徑示意圖如下最短路上兩相鄰需求點(diǎn)的具體距離見附錄四：圖四：最短路徑示意圖4將合成坐標(biāo)轉(zhuǎn)化為地理坐標(biāo)，確定具體調(diào)度方案。但問題一中各

20、需求點(diǎn)的坐標(biāo)并非為各需求點(diǎn)的地理坐標(biāo)，而是求最小費(fèi)用的需求量與地理位置的合成坐標(biāo)，即坐標(biāo)是各需求點(diǎn)的費(fèi)用坐標(biāo)。因而，根據(jù)花費(fèi)最少的最小路徑，首先將合成坐標(biāo)回歸為地理坐標(biāo)。在如何裝載的問題上,顯然有兩種情況: 情況一:假設(shè)每量車均為滿載,即每量發(fā)出的車均承載6噸貨物.根據(jù)最短路徑經(jīng)過的各站點(diǎn)依次發(fā)貨,當(dāng)?shù)谝惠v貨車所裝載物資發(fā)完,第二輛繼續(xù)前進(jìn),發(fā)貨到下一個(gè)站點(diǎn),而此時(shí)第一輛超大運(yùn)輸車假想思路.在這里需要提出的是,有幾輛車應(yīng)該重復(fù)使用的(只需保證用時(shí)不大于4小時(shí)),因?yàn)楦鶕?jù)實(shí)際情況,派出一輛車的固定費(fèi)用遠(yuǎn)高于一輛車的行駛費(fèi)用. 具體的調(diào)度方案見如下表一：表一 運(yùn)輸車滿載調(diào)配物資情況表車次12345

21、678調(diào)配路線3-6-16-5-4-28-20-10-1211-22-21-914-27-15-1925-26-29-1324-23-2830-17-718裝載噸數(shù)6666666里程數(shù)4186125168218262298308注：此處里程數(shù)僅為各運(yùn)輸車走完各自調(diào)配物資線路的里程數(shù)，不包括空載返回的里程數(shù)。具體車輛調(diào)配見下列圖五：圖五：滿載車輛調(diào)配圖圖例：此圖例也適用于圖六、圖七注:考慮此種方案，目的是簡化對(duì)車輛的調(diào)度。使得可以假想為所有的車輛排成一條長隊(duì)，當(dāng)車到地時(shí)恰好運(yùn)完所有貨物，空載返回，車接著補(bǔ)充，滿足地的需求量，以此類推，直至滿足完第29個(gè)需求地的需求量。 情況二:假設(shè)各輛車按具體需

22、求量裝載貨物(可以滿載,可以非滿載),比方根據(jù)最短路徑的連接站點(diǎn),如果前3個(gè)站點(diǎn)需要總物資為m噸(m6,這樣的情況我們可以把第一輛車裝載m噸物資,那么第一輛車運(yùn)貨到第三個(gè)站點(diǎn)恰好運(yùn)完貨物，此時(shí)就可以空載撤回，第二輛也再通過計(jì)算下幾個(gè)站點(diǎn)需要的具體物資去裝載具體的物資量，完全發(fā)配以此類推，直到最后一個(gè)站點(diǎn)運(yùn)輸完畢，即最后一輛車恰好運(yùn)完，空載撤回具體的調(diào)度方案見如下表二：表二 各輛車非滿載調(diào)配物資情況表車次12345678調(diào)配路線3-6-16-5-42-8-20-1012-11-22-219-14-2715-19-2526-29-1324-23-2830-17-7-18裝載噸數(shù)6里程數(shù)377811

23、2147174218262308費(fèi)用547991注：此處里程數(shù)僅為各運(yùn)輸車走完各自調(diào)配物資線路的里程數(shù)，不包括空載返回的里程數(shù)。圖六:非滿載車輛調(diào)配圖由表一和表二的比照，可以看出雖然滿載和非滿載兩種情況下調(diào)配車輛輛數(shù)一樣，但非滿載情況下總運(yùn)輸費(fèi)用遠(yuǎn)小于滿載情況下總運(yùn)輸費(fèi)用。原因是滿載情況下，當(dāng)運(yùn)輸車在運(yùn)完第個(gè)需求點(diǎn)，此時(shí)運(yùn)輸總量小于6，即使很小，小于最小路線上下一個(gè)需求點(diǎn)的需求量,但必須前往下一個(gè)需求點(diǎn)將余下物資卸完，因而會(huì)多出行進(jìn)需求點(diǎn)與需求點(diǎn)之間的距離，多運(yùn)送噸物資所需的消耗。5問題一進(jìn)一步的優(yōu)化在前面兩種情況中，考慮的均是讓所有運(yùn)輸車沿著同一條線路運(yùn)送物資，即花費(fèi)最短路。事實(shí)上，可以讓各

24、運(yùn)輸車按最近路徑從倉庫到達(dá)各調(diào)配路線的初始需求點(diǎn)，而不是沿花費(fèi)最短路，使得開往各初始需求點(diǎn)的費(fèi)用大大減少。返回時(shí)那么由各調(diào)配路線終止點(diǎn)按最近路徑返回倉庫，而不是按花費(fèi)最少路徑。根據(jù)上述思路，由題意知：運(yùn)輸車的速度為40公里/小時(shí)，最大載重量為6噸，可得車一次最在可運(yùn)40公里/小時(shí)6噸，即對(duì)車有最大運(yùn)量240噸公里/小時(shí)。我們重新定義每個(gè)需求點(diǎn)的需求為：需求量*該需求點(diǎn)的坐標(biāo)和。數(shù)據(jù)見表二見附錄2。如此我們可求得總需求量為：，由表二我們可求得：=939.08噸公里 對(duì)圖六非滿載車輛調(diào)配圖作如下運(yùn)輸車輛調(diào)配方案：非滿載最優(yōu)車輛調(diào)配圖車次12345678調(diào)配路線3-6-16-5-42-8-20-10

25、12-11-22-219-14-2715-19-2526-29-1324-23-2830-17-7-18裝載噸數(shù)6里程數(shù)3446545049738087對(duì)于該方案：我們派出去八輛車，分別開往3，2，12，9，15，26，24，30這八個(gè)站點(diǎn)。第一條路線有：車載重為5.15噸，其行程為34km，返回時(shí)行駛了11km.，停留了40分鐘，共用時(shí)約為2小時(shí)；花費(fèi)為：211 ；第二條路線有：車載重為6噸，其行程為46km，返回時(shí)行駛了14km，停留了40分鐘，共用時(shí)約為2.5小時(shí)了；花費(fèi)為：214；第三條路線有：車載重為5.5噸，其行程為54km，返回時(shí)行駛了27km，停留了40分鐘，共用時(shí)約為3小時(shí)了

26、；花費(fèi)為：227第四條路線有：車載重為5.1噸，其行程為50km，返回時(shí)行駛了34km，停留了30分鐘，共用時(shí)約為2.5小時(shí)了；花費(fèi)為：234第五條路線有：車載重為4.9噸，其行程為49km，返回時(shí)行駛了29km，停留了30分鐘，共用時(shí)約為2.5小時(shí)了；花費(fèi)為：229第六條路線有：車載重為5.6噸，其行程為73km，返回時(shí)行駛了21km，停留了30分鐘，共用時(shí)約為3小時(shí)了；花費(fèi)為：221第七條路線有：車載重為5.2噸，其行程為80km，返回時(shí)行駛了44km，停留了30分鐘，共用時(shí)約為3.5小時(shí)了；花費(fèi)為：244第八條路線有：車載重為5.7噸，其行程為87km，返回時(shí)行駛了24km，停留了40分

27、鐘，共用時(shí)約為3.5小時(shí)了；花費(fèi)為：224綜上：對(duì)第一到第八條路線有總花費(fèi)P總=211+24即 ：花費(fèi)P總=+0.511+14+27+34+29+21+44+24由問題一的求解已找出使總費(fèi)用最小的最短路徑，因此在問題二中，只需沿著最小路徑，具體分配載重量不同的運(yùn)輸車輛?？紤]到一輛載重大的運(yùn)輸車每公里的運(yùn)營費(fèi)用遠(yuǎn)大于載重小的運(yùn)輸車，因?yàn)樵诿繃嵨镔Y每公里均為2元的情況下，載重越多，運(yùn)營公里數(shù)越多，所需總費(fèi)用也越多，因此，在分配時(shí)，首先應(yīng)考慮盡量分配大的運(yùn)輸車，先讓載重大的運(yùn)輸車前往距離近的運(yùn)輸點(diǎn)。再讓載重小一些的運(yùn)輸車前往距離遠(yuǎn)的運(yùn)輸點(diǎn)，此種情況下使運(yùn)輸費(fèi)用得到優(yōu)化。具體分配載重不同的車輛時(shí)，原那

28、么是盡量用一輛運(yùn)輸車運(yùn)送最短路上相鄰的需求點(diǎn)需求物資。即使最短路上需求點(diǎn)的需求量之和先滿足八噸的運(yùn)輸車，再滿足六噸的運(yùn)輸車，最后滿足四噸的運(yùn)輸車。離倉庫越近的需求點(diǎn)，使用的的運(yùn)輸車載重越大。具體分配情況如表三所示: 表三 三種載重不同車輛物資調(diào)度表車次1234567車型噸數(shù)8噸的8噸的6噸的6噸的6噸的6噸的4噸的4噸的調(diào)配路線3-6-16-5-4-28-20-10-12-11- 2221-9-1427-15- 19-2526-29- 1324-23- 2830-177-18裝載噸數(shù)里程數(shù)4180547673877110車次車型調(diào)配路線裝載噸數(shù)里程數(shù)18噸361654241對(duì)于該方案：我們派出

29、去七輛車，分別開往3，8，21，27，26，24，30，7這七個(gè)站點(diǎn)。第一條路線有： 8噸的車車載重為7.65噸，其行程為41km，返回時(shí)行駛了5km.，停留了60分鐘，共用時(shí)約為2小時(shí)；花費(fèi)為：25第二條路線有： 8噸的車車載重為7.6噸，其行程為80km，返回時(shí)行駛了27km.，停留了60分鐘，共用時(shí)約為3.5小時(shí)；花費(fèi)為：227第三條路線有：6噸的車車載重為5.5噸，其行程為54km，返回時(shí)行駛了21km.，停留了30分鐘，共用時(shí)約為2.5小時(shí)；花費(fèi)為：221第四條路線有：6噸的車車載重為5.9噸，其行程為76km，返回時(shí)行駛了34km.，停留了40分鐘，共用時(shí)約為3.7小時(shí)；花費(fèi)為：2

30、34第五條路線有：6噸的車車載重為5.6噸，其行程為73km，返回時(shí)行駛了20km.，停留了30分鐘，共用時(shí)約為2.6小時(shí)；花費(fèi)為：220第六條路線有：6噸的車車載重為5.2噸，其行程為87km，返回時(shí)行駛了34km.，停留了30分鐘，共用時(shí)約為2.6小時(shí)；花費(fèi)為：234第七條路線有：4噸的車車載重為3.6噸，其行程為71km，返回時(shí)行駛了18km.，停留了20分鐘，共用時(shí)約為2.5小時(shí)；花費(fèi)為：218第八條路線有：4噸的車路線七的車車載重為3.6噸，其行程為10km，返回時(shí)行駛了24km.，停留了20分鐘，共用時(shí)約為1.3小時(shí)；花費(fèi)為：224綜上：對(duì)第一到第八條路線有：總花費(fèi)P總=25+24

31、 即 ：花費(fèi)P總=六、模型結(jié)果的分析和檢驗(yàn)在研究物資調(diào)配問題時(shí)，我們忽略了交通，天氣等客觀因素，大大簡化了最短路徑的建立與求解。最初我們便通過“化零為整思想確立了一條“經(jīng)濟(jì)上最短路徑，并在下文求解最低費(fèi)用以及運(yùn)輸車的具體調(diào)配中深刻落實(shí)。這樣便最大程度上保證總運(yùn)輸費(fèi)用最低這一主旨，應(yīng)該說在落實(shí)“最低費(fèi)用方面是相當(dāng)可靠的，也是可行的。并且最終我們利用此方法求解出的低費(fèi)用，也證明了這一點(diǎn)。但是這個(gè)模型也并非最優(yōu)的，因?yàn)榇四Ｐ蜎]有充分考慮時(shí)間這個(gè)約束條件。換言之，如果以“最低費(fèi)用為主要要求，我們的模型有很高的可行性；如果以“時(shí)間為主要要求，此模型可能會(huì)產(chǎn)生較大誤差。但是，這個(gè)誤差并非無法彌補(bǔ)的，我們又

32、可以通過“人工改良調(diào)配，靈活的運(yùn)用此模型。在第一問中，我們最終選擇八輛車非滿載的調(diào)配方案，并求解出了相對(duì)最低的運(yùn) 輸費(fèi)用。因?yàn)樵趩栴}中我們已經(jīng)給出了每輛車要經(jīng)過的具體路線以及需要的承載 量，于是便可以按著具體的運(yùn)輸方案進(jìn)行檢驗(yàn)，經(jīng)過屢次求解調(diào)配，發(fā)現(xiàn)每次的 誤差并不大，這便一定程度說明此模型的穩(wěn)定性與可行性；而在第二問中，我們通過同樣的方法，結(jié)合利用軟件，計(jì)算檢驗(yàn)。1.4 .倉庫每天要運(yùn)送的物資在早上出發(fā)時(shí)間之前已經(jīng)全到了，沒有到的當(dāng)天就不運(yùn)送這種模型現(xiàn)在已經(jīng)很成熟，因此采用這種解法應(yīng)該能夠到達(dá)減少運(yùn)費(fèi)的要求。且總費(fèi)用控制在了一個(gè)較為合理的范圍內(nèi)。但是由于物資調(diào)運(yùn)是一個(gè)比擬復(fù)雜的問題設(shè)計(jì)到眾多

33、的變量，上述模型尚有許多因素沒有考慮在內(nèi)。比方每輛車送完物資，回來再準(zhǔn)備第二趟運(yùn)送這個(gè)過程也要花時(shí)間，這個(gè)時(shí)間沒有考慮到時(shí)間范圍內(nèi)，還有像城市交通不平衡等問題，貨物分類等問題。七、模型的推廣目前 ,物流配送車輛優(yōu)化調(diào)度在國外已廣泛運(yùn)用于生產(chǎn)和生活的各個(gè)方面 ,如報(bào)紙、 牛奶投遞及線路優(yōu)化 ,工業(yè)原材料和成品的運(yùn)輸 , 或網(wǎng)絡(luò)購物的車輛配裝及線路設(shè)計(jì) ,航運(yùn)公司輪船經(jīng)過港口和貨物裝卸的優(yōu)化設(shè)計(jì) ,連鎖商店的送配貨等等 ,并已經(jīng)取得了極大的經(jīng)濟(jì)效益.如美國沃爾瑪特百貨 ,其成為全球零售業(yè)霸主的首要因素是擁有了最先進(jìn)的物流配送指揮系統(tǒng) ,全球各門店通過衛(wèi)星實(shí)現(xiàn)聯(lián)網(wǎng) ,可以最大限度地降低其商品物流本錢

34、和增加銷售量 ,從而在競爭中始終處于優(yōu)勢地位56 在我國 ,隨著國民經(jīng)濟(jì)健康穩(wěn)定的高速開展 ,市場經(jīng)濟(jì)日益興旺 ,各種生產(chǎn)經(jīng)營方式開展得十分迅速.在生產(chǎn)活動(dòng)中 ,提出了以零庫存為目標(biāo)的Just2in2time 模式;而各式連鎖經(jīng)營的便利店和直送業(yè)務(wù)的蓬勃開展 , 也使零售業(yè)物流配送呈現(xiàn)出多頻度、 小批次的特點(diǎn) ,這些都對(duì)以運(yùn)輸為中心的物流配送活動(dòng)提出了更高的要求.但就目前情況而言 ,我國的VRP研究仍然有限 ,可以說仍未能滿足經(jīng)濟(jì)開展的需要.首先是起步較晚 ,通用理論研究較少;其次 ,對(duì)于具體問題提出的應(yīng)用研究相對(duì)較多 ,但多為對(duì)具體算法的局部改良 ,且限于各自的適用條件 ,局限性較強(qiáng).八、模

35、型的評(píng)價(jià)與優(yōu)化模型的優(yōu)點(diǎn)1、花費(fèi)最小路的思想。將總費(fèi)用最小分解為任意兩個(gè)需求點(diǎn)間費(fèi)用最小，即假設(shè)每一需求點(diǎn)到下一需求點(diǎn)的花費(fèi)最小，那么總花費(fèi)最小。從而由通過計(jì)算每兩個(gè)需求點(diǎn)間費(fèi)用最小而得到總費(fèi)用最小。防止了通過窮舉法搜索。2、各需求點(diǎn)經(jīng)濟(jì)坐標(biāo)的合成。將各需求點(diǎn)費(fèi)用的兩個(gè)影響因素地理位置與需求量合成一個(gè)新的坐標(biāo)，從而減少了變量的個(gè)數(shù)，大大簡化問題，至此使每個(gè)需求點(diǎn)費(fèi)用直接與總費(fèi)用相聯(lián)系。3、統(tǒng)一所有量的單位。對(duì)最小路上個(gè)邊權(quán)的意義的深化。在將各需求點(diǎn)的坐標(biāo)單位合成為噸千米后，將運(yùn)輸車載重6噸及速度為40千米/小時(shí)合成為240噸千米/小時(shí)，計(jì)算時(shí)按不是按地理意義上的最短路而是按花費(fèi)意義上的最短路，

36、對(duì)問題的抽象與簡化。4、在研究物資調(diào)配問題時(shí)，我們忽略了交通，天氣等客觀因素，大大簡化了最短路徑的建立與求解。5、作圖表示出最短路具體路徑，直觀清晰。6、在最短路的總體思想下，綜合考慮時(shí)間與運(yùn)費(fèi)等客觀約束條件，使模型更貼近實(shí)際，同時(shí)使運(yùn)輸車的調(diào)配更加合理清晰。模型的缺點(diǎn)1、在第一問中要派出八輛車，在第二問中也要派出七輛車，派出的車輛過多，而實(shí)際上，新派出一輛車的本錢遠(yuǎn)高于一輛車往返運(yùn)輸?shù)谋惧X。且在此題求解的兩問中，各輛車總的運(yùn)輸時(shí)間離每天四小時(shí)的工作限制還有較大的余地，因此應(yīng)考慮進(jìn)一步優(yōu)化調(diào)運(yùn)方案，減少派出車輛的輛數(shù)。2、雖然我們運(yùn)用具體模型求解時(shí)，完全根據(jù)題中所給出的約束條件，但是交通狀況，

37、車速變化等客觀因素仍然對(duì)模型的緊缺度有較大影響。3、我們雖然通過“化零為整，“人工優(yōu)化等措施最大程度上保證了運(yùn)輸車的最優(yōu)調(diào)配，但是仍然不排除個(gè)別站點(diǎn)間最短距離與花費(fèi)存在誤差。模型的優(yōu)化由于我們運(yùn)輸車的工作時(shí)間沒有充分利用，且沒有充分考慮實(shí)際情況。對(duì)勞動(dòng)力有較大的浪費(fèi)。因此我們可以假設(shè)在行車時(shí)有平均耽誤時(shí)間為Td，以及平均損耗為n元/小時(shí)輛，工人的工資q元/小時(shí)，每輛車過收費(fèi)站的平均花費(fèi)為w元/小時(shí)對(duì)于運(yùn)送較近的運(yùn)輸車，在影響工作時(shí)間不大的情況下可以運(yùn)輸兩趟。因此在花費(fèi)還應(yīng)參加這些花費(fèi)。然后綜合考慮，得出符合實(shí)際的最優(yōu)解；優(yōu)化模型求解：設(shè)時(shí)間為t；那么：花費(fèi)P=n+q+wt+ 2 11+ + 24同樣的道理對(duì)于第二問我們有：