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

摘要“運(yùn)輸調(diào)度”數(shù)學(xué)模型是通過運(yùn)輸車運(yùn)輸路線的確定以及運(yùn)輸車調(diào)配方案的確定來使運(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)輸車”來運(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)量乘以其速度，又因運(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)送物資。同樣在整體上對問題從經(jīng)濟(jì)上來考慮比較合理。結(jié)合各約束條件求得最低費(fèi)用為1969.66元，需要7輛車關(guān)鍵詞：物資調(diào)度最短路線最優(yōu)化原理Dijkstra算法0-1規(guī)劃一、問題重述1.1.背景資料與條件某城區(qū)有29個(gè)物資需求點(diǎn)，需求點(diǎn)的地理坐標(biāo)和每天物資的需求量見如下表一。（表一為原表截取的一部分，原表其余部分見附錄一）。每天凌晨都要從倉庫（第30號站點(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)編號需求量T坐標(biāo)(km)站點(diǎn)編號需求量T坐標(biāo)(km)xyxy132162162151761835418111744719151250820199631121225下圖為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ì)高速發(fā)展，各種信息物資交流頻繁，特別是當(dāng)今，對如何優(yōu)化物資分配，降低經(jīng)濟(jì)成本，時(shí)間成本的要求十分迫切。研究在使費(fèi)用最小情況下的物資調(diào)度問題，對于滿足各地物資需求，優(yōu)化資源配置，促進(jìn)經(jīng)濟(jì)社會(huì)發(fā)展具有十分重要的意義。.有關(guān)方面在這個(gè)問題上做過的研究[2]物流配送車輛優(yōu)化調(diào)度問題最早是由學(xué)者Dantzig和Ramser于1959年首次提出的,國外一般稱之為vehicleroutingproblem或vehicleschedulingproblem.一般以為,不考慮時(shí)間要求,僅根據(jù)空間位置安排線路時(shí)稱為車輛線路安排問題VRP;考慮時(shí)間要求,安排線路時(shí)稱為車輛調(diào)度問題VSP。目前針對車輛優(yōu)化調(diào)度問題的求解算法可以說是相當(dāng)豐富,根據(jù)對這些算法本質(zhì)的分類研究,基本上可以分為精確算法和啟發(fā)式算法兩大類.精確算法指可求出最優(yōu)解的算法,主要有分枝定界法、割平面法、網(wǎng)絡(luò)流算法和動(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ā)式方法能夠比較快地得到滿意解,這對解決NP難題來說有著不可估量的作用.因此大部分文獻(xiàn)中專家們主要是在構(gòu)造各種高質(zhì)量的啟發(fā)式算法。倉庫物資由運(yùn)輸車進(jìn)行調(diào)運(yùn)。每輛車的工作時(shí)間不超過4小時(shí)，并且每輛車的載重不能超過6噸。若調(diào)運(yùn)的需求地點(diǎn)已經(jīng)明確，為了使運(yùn)費(fèi)最小，必須用最少的車在允許的工作時(shí)間內(nèi)把需要運(yùn)送的物資運(yùn)送到需求地點(diǎn)，因此選擇什么樣的調(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)仍是最?。患慈裘績傻刂g的運(yùn)輸費(fèi)用都是最小的，那么將所有聯(lián)通的兩個(gè)需求地的運(yùn)費(fèi)求和仍是最少的運(yùn)費(fèi)。即假設(shè)為地和地的最小運(yùn)輸費(fèi)用，為0-1變量，即兩地與若聯(lián)通，則為1，若兩地不連通，則為0。在運(yùn)輸車運(yùn)往個(gè)需求點(diǎn)的過程中，總運(yùn)輸最小費(fèi)用為：針對地，根據(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)度車輛要考慮的因素是使總運(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è)有一輛“超級大車”，載重了29個(gè)需求點(diǎn)的全部物資，每到一個(gè)需求點(diǎn)，就卸下一部分物資，直至最后一個(gè)需求點(diǎn)。第二種方案：假設(shè)每輛運(yùn)輸車不一定滿載，車在運(yùn)送完最短路上指定的幾個(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.忽略運(yùn)輸車加速和制動(dòng)的速度變化及時(shí)間的影響。3.不考慮汽車在紅綠燈，堵車，惡劣天氣狀況時(shí)的延誤時(shí)間。4.每輛車派出的人工成本，裝卸貨等固定成本忽略不計(jì)。5.供應(yīng)物資的公司能夠提供足夠多的車輛。不考慮其他因素，第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í)可靠。四、符號說明為了便于問題的求解，我們給出以下符號說明：（其他未說明的符號在文中第一次出現(xiàn)時(shí)會(huì)做詳細(xì)的說明。）符號意義第i輛車需求點(diǎn)需求點(diǎn)和需求點(diǎn)之間的距離需求點(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．在中，令，令，若為空集則算法結(jié)束，否則轉(zhuǎn)33．對全部屬于,如果存在邊，那么，轉(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)對應(yīng)一個(gè)距離，中的頂點(diǎn)的距離就是從到此頂點(diǎn)的最短路徑長度，中的頂點(diǎn)的距離，是從到此頂點(diǎn)只包括中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長度。算法具體步驟（1）初始時(shí)，只包含源點(diǎn)，即＝的距離為0。包含除外的其他頂點(diǎn)，中頂點(diǎn)距離為邊上的權(quán)（若與有邊）或）（若不是的出邊鄰接點(diǎn)）。（2）從中選取一個(gè)距離最小的頂點(diǎn)，把加入中（該選定的距離就是到的最短路徑長度）。（3）以為新考慮的中間點(diǎn)，修改中各頂點(diǎn)的距離；若從源點(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)策略，它滿足相對前面決策所形成的狀態(tài)而言，余下的子策略必然構(gòu)成“最優(yōu)子策略”。一個(gè)問題滿足最優(yōu)化原理也稱其擁有最優(yōu)子結(jié)構(gòu)性質(zhì)。．模型一的運(yùn)用與求解（1）運(yùn)用整體思想，最短路思想的由來從倉庫開出任一輛運(yùn)輸車對物資進(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è)有一輛“超級運(yùn)輸車”，裝載了29個(gè)需求地的所有所需物資之和，即首先，使運(yùn)輸車從倉庫運(yùn)往地的運(yùn)輸費(fèi)用最少，再從地運(yùn)往地的運(yùn)輸費(fèi)用最小，如此類推，若運(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)完所裝載物資后，即空載撤回，第二輛車接著向下一個(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)系。對此我們將二者化零為整，將每個(gè)需求點(diǎn)的需求量乘以其坐標(biāo)得到新的坐標(biāo)。同時(shí)也將運(yùn)輸車的載重量乘以它的速度。將二者同時(shí)放在花費(fèi)的角度上（金錢的角度上）進(jìn)行求解。如此我們求了花費(fèi)上的最短距離，同時(shí)我們設(shè)所有的運(yùn)輸車都載重6噸。對得到的最短行程做解，以得到最小的花費(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)編號需求量T地理坐標(biāo)（km）花費(fèi)坐標(biāo)（km*t）站點(diǎn)編號需求量T地理坐標(biāo)（km）花費(fèi)坐標(biāo)（km*t）xyxy132162162721156176183541811174244719151250820199631121225772221089623279910224151910140251514111732226120173712146542722113681312928124204414101229251615714300000我們又用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)度方案。但問題一中各需求點(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)。在如何裝載的問題上,顯然有兩種情況:情況一:若每量車均為滿載,即每量發(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)配物資情況表車次12345678調(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)配圖圖例：此圖例也適用于圖六、圖七注:考慮此種方案，目的是簡化對車輛的調(diào)度。使得可以假想為所有的車輛排成一條長隊(duì)，當(dāng)車到地時(shí)恰好運(yùn)完所有貨物，空載返回，車接著補(bǔ)充，滿足地的需求量，以此類推，直至滿足完第29個(gè)需求地的需求量。情況二:若各輛車按具體需求量裝載貨物(可以滿載,可以非滿載),比如根據(jù)最短路徑的連接站點(diǎn),如果前3個(gè)站點(diǎn)需要總物資為m噸(m<6),而前四個(gè)站點(diǎn)需要總物資為M噸（M>6）,這樣的情況我們可以把第一輛車裝載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ù)3778112147174218262308費(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)送噸物資所需的耗費(fèi)。（5）問題一進(jìn)一步的優(yōu)化在前面兩種情況中，考慮的均是讓所有運(yùn)輸車沿著同一條線路運(yùn)送物資，即花費(fèi)最短路。事實(shí)上，可以讓各運(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噸，即對車有最大運(yùn)量240噸公里/小時(shí)。我們重新定義每個(gè)需求點(diǎn)的需求為：（需求量）*（該需求點(diǎn)的坐標(biāo)和）。數(shù)據(jù)見表二（見附錄2）。如此我們可求得總需求量為：，由表二我們可求得：=939.08噸公里對圖六非滿載車輛調(diào)配圖作如下運(yùn)輸車輛調(diào)配方案：非滿載最優(yōu)車輛調(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ù)3446545049738087對于該方案：我們派出去八輛車，分別開往3，2，12，9，15，26，24，30這八個(gè)站點(diǎn)。第一條路線有：車載重為5.15噸，其行程為34km，返回時(shí)行駛了11共用時(shí)約為2小時(shí)；花費(fèi)為：2×（）×11；第二條路線有：車載重為6噸，其行程為46km，返回時(shí)行駛了14共用時(shí)約為2.5小時(shí)了；花費(fèi)為：2×（）×14；第三條路線有：車載重為5.5噸，其行程為54km，返回時(shí)行駛了27共用時(shí)約為3小時(shí)了；花費(fèi)為：2×（）2×7第四條路線有：車載重為5.1噸，其行程為50km，返回時(shí)行駛了34共用時(shí)約為2.5小時(shí)了；花費(fèi)為：2×（）×34第五條路線有：車載重為4.9噸，其行程為49km，返回時(shí)行駛了29共用時(shí)約為2.5小時(shí)了；花費(fèi)為：2×（）×29第六條路線有：車載重為5.6噸，其行程為73km，返回時(shí)行駛了21共用時(shí)約為3小時(shí)了；花費(fèi)為：2×（）×21第七條路線有：車載重為5.2噸，其行程為80km，返回時(shí)行駛了44共用時(shí)約為3.5小時(shí)了；花費(fèi)為：2×（）×44第八條路線有：車載重為5.7噸，其行程為87km，返回時(shí)行駛了24共用時(shí)約為3.5小時(shí)了；花費(fèi)為：2×（）×24綜上：對第一到第八條路線有總花費(fèi)P（總）=2×（）×11++（）×24即：花費(fèi)P（總）=+0.5×（11+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í)，原則是盡量用一輛運(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噸3→6→16→5→4→241對于該方案：我們派出去七輛車，分別開往3，8，21，27，26，24，30，7這七個(gè)站點(diǎn)。第一條路線有：8噸的車車載重為7.65噸，其行程為41km，返回時(shí)行駛了5共用時(shí)約為2小時(shí)；花費(fèi)為：2×（）×5第二條路線有：8噸的車車載重為7.6噸，其行程為80km，返回時(shí)行駛了27共用時(shí)約為3.5小時(shí)；花費(fèi)為：2×（）2×7第三條路線有：6噸的車車載重為5.5噸，其行程為54km，返回時(shí)行駛了21共用時(shí)約為2.5小時(shí)；花費(fèi)為：2×（）×21第四條路線有：6噸的車車載重為5.9噸，其行程為76km，返回時(shí)行駛了34共用時(shí)約為3.7小時(shí)；花費(fèi)為：2×（）×34第五條路線有：6噸的車車載重為5.6噸，其行程為73km，返回時(shí)行駛了20共用時(shí)約為2.6小時(shí)；花費(fèi)為：2×（×20第六條路線有：6噸的車車載重為5.2噸，其行程為87km，返回時(shí)行駛了34共用時(shí)約為2.6小時(shí)；花費(fèi)為：2×（）×34第七條路線有：4噸的車車載重為3.6噸，其行程為71km，返回時(shí)行駛了18共用時(shí)約為2.5小時(shí)；花費(fèi)為：2×（）×18第八條路線有：4噸的車（路線七的車）車載重為3.6噸，其行程為10km，返回時(shí)行駛了24共用時(shí)約為1.3小時(shí)；花費(fèi)為：2×（）×24綜上：對第一到第八條路線有：總花費(fèi)P（總）=2×（）×5++（）×24即：花費(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ǔ)的，我們又可以通過“人工改進(jìn)調(diào)配”，靈活的運(yùn)用此模型。在第一問中，我們最終選擇八輛車非滿載的調(diào)配方案，并求解出了相對最低的運(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ì)到眾多的變量，上述模型尚有許多因素沒有考慮在內(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),可以最大限度地降低其商品物流成本和增加銷售量,從而在競爭中始終處于優(yōu)勢地位[56]在我國,隨著國民經(jīng)濟(jì)健康穩(wěn)定的高速發(fā)展,市場經(jīng)濟(jì)日益發(fā)達(dá),各種生產(chǎn)經(jīng)營方式發(fā)展得十分迅速.在生產(chǎn)活動(dòng)中,提出了以零庫存為目標(biāo)的Just2in2time模式;而各式連鎖經(jīng)營的便利店和直送業(yè)務(wù)的蓬勃發(fā)展,也使零售業(yè)物流配送呈現(xiàn)出多頻度、小批次的特點(diǎn),這些都對以運(yùn)輸為中心的物流配送活動(dòng)提出了更高的要求.但就目前情況而言,我國的VRP研究仍然有限,可以說仍未能滿足經(jīng)濟(jì)發(fā)展的需要.首先是起步較晚,通用理論研究較少;其次,對于具體問題提出的應(yīng)用研究相對較多,但多為對具體算法的部分改進(jìn),且限于各自的適用條件,局限性較強(qiáng).八、模型的評價(jià)與優(yōu)化模型的優(yōu)點(diǎn)1、花費(fèi)最小路的思想。將總費(fèi)用最小分解為任意兩個(gè)需求點(diǎn)間費(fèi)用最小，即若每一需求點(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)一所有量的單位。對最小路上個(gè)邊權(quán)的意義的深化。在將各需求點(diǎn)的坐標(biāo)單位合成為噸·千米后，將運(yùn)輸車載重6噸及速度為40千米/小時(shí)合成為240噸·千米/小時(shí)，計(jì)算時(shí)按不是按地理意義上的最短路而是按花費(fèi)意義上的最短路，對問題的抽象與簡化。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ù)某杀?。且在本題求解的兩問中，各輛車總的運(yùn)輸時(shí)間離每天四小時(shí)的工作限制還有較大的余地，因此應(yīng)考慮進(jìn)一步優(yōu)化調(diào)運(yùn)方案，減少派出車輛的輛數(shù)。2、雖然我們運(yùn)用具體模型求解時(shí)，完全根據(jù)題中所給出的約束條件，但是交通狀況，車速變化等客觀因素仍然對模型的緊缺度有較大影響。3、我們雖然通過“化零為整”，“人工優(yōu)化”等措施最大程度上保證了運(yùn)輸車的最優(yōu)調(diào)配，但是仍然不排除個(gè)別站點(diǎn)間最短距離與花費(fèi)存在誤差。模型的優(yōu)化由于我們運(yùn)輸車的工作時(shí)間沒有充分利用，且沒有充分考慮實(shí)際情況。對勞動(dòng)力有較大的浪費(fèi)。因此我們可以假設(shè)在行車時(shí)有平均耽擱時(shí)間為Td，以及平均損耗為n元/小時(shí)輛，工人的工資q元/小時(shí)，每輛車過收費(fèi)站的平均花費(fèi)為w元/小時(shí)對于運(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+w）t+2（）11++（）24同樣的道理對于第二問我們有：則：花費(fèi)P=（n+q+w）t+2（）5++（）24這樣我們便可求出真實(shí)的解。參考文獻(xiàn)[1]馮小杰，黃力偉，王力勤，尹成義，數(shù)學(xué)建模原