物資調(diào)運問題

1、物資調(diào)運問題摘要如今物資調(diào)度問題普遍存在于生活的每個角落，利用有效的方法解決該問題會給 我們的工作生產(chǎn)帶來許多便利，也會帶來可觀的利益。本文在確定了物資需求地點和 每個需求地點的需求量提下，用什么樣的調(diào)度方案使所需的運費最少，來達到題目的 要求。本文主要從最省費用的角度來考慮問題的，這樣我們不妨把每個地點都放到直角 坐標(biāo)系中，每個地點都有自己的固定坐標(biāo)，設(shè)發(fā)貨點為坐標(biāo)原點，每條街道都與坐標(biāo) 軸平行，更具題LI的要求我們可以得出：每兩個點之間的距離就是兩點橫坐標(biāo)之差的 絕對值和縱坐標(biāo)之差的絕對值之和。如A（X,yi） ,B（x2,y2）兩點，他們之間的運輸距離為S二卜2-對+ |，2-川，而且必

2、須滿足每輛車運輸時間的條件，所以對于問題一， 山于要求費用最省，根據(jù)圖形每輛車從原點出發(fā)到最近的點送貨，在滿足各項條件的 前提下，用多U標(biāo)動態(tài)規(guī)劃求解。并可以得出需要用6輛6噸的車，最省費用為元。 對于問題二，與問題一類似，只是具體要求不同，最后求得所花費用為2428元。將 問題一和問題二的運輸費用描繪柱狀圖（附錄一圖4）,相比較之下，可以發(fā)現(xiàn)在路 程較短時，問題二所用運輸費用較高；路程較長時，問題一所用運輸費用較低。關(guān)鍵詞：物資調(diào)度 最優(yōu)化 圖形求解 多目標(biāo)動態(tài)規(guī)劃重述1.1.背景資料與條件某城區(qū)有29個物資需求點，需求點的地理坐標(biāo)和每天物資的需求量見下表。每 天凌晨都要從倉庫（第30號站點

3、）出發(fā)將物資運至每個需求點。現(xiàn)有一種載重6噸 的運輸車，運輸車平均速度為40公里/小時，每臺車每日工作4小時，每個需求點 需要用10分鐘的時間下貨，運輸車重載運費2元/噸公里，空載費用元/公里；并且 假定街道方向均平行于坐標(biāo)軸。需要解決的問題1. 為了使得總運營費用最少，運輸車應(yīng)如何調(diào)度（需要投入多少臺運輸車，每 臺車的調(diào)度方案，運營費用）2如果有載重量為4噸，6噸，8噸的三種運輸車，又應(yīng)該如何調(diào)度，失蹤營運 費用最少二、問題分析.問題的重要性分析（社會背景）近年來，大規(guī)模的突發(fā)性公共事件如sars危機.印度洋海嘯、冰雪災(zāi)害、汶川 地震等在世界各國頻有發(fā)生，這些突發(fā)事件造成的巨大損失，給人們留

4、下了難以忘懷 的慘痛記憶。現(xiàn)代社會正處在髙速發(fā)展的過程中，與此同時，人口.資源.環(huán)境、公 共衛(wèi)生等方面的問題日益嚴(yán)重，這導(dǎo)致各類突發(fā)事件爆發(fā)的頻率加快，影響范圍擴大, 危害程度加劇。我國當(dāng)前正處在突發(fā)性公共事件高發(fā)時期，隨著城鎮(zhèn)化進程的加快， 這種形勢還在加劇，因此研究應(yīng)急物流和應(yīng)急物資調(diào)度問題具有非常重要的現(xiàn)實意 義。突發(fā)事件之后往往伴隨著大量的應(yīng)急物資需求，采用合理的運輸方式、運輸路徑 和最優(yōu)的應(yīng)急物資調(diào)度方案，及時的將救援物資送達物資需求點，這直接影響到整個 突發(fā)性公共事件救援行動的成效。.問題的思路分析問題一：從倉庫開出一輛車，到任意未配送的需求點，然后將這輛車開往最近的 未服務(wù)的需求

5、點范圍之內(nèi)的鄰居，并使運輸時間小于4小時，各車所運物資的總重量 不超過6T。繼續(xù)上述指派，直到各點總重量超過6T,或者運輸時間大于4小時。最 后車輛返回倉庫，記錄得到的可行行程（即路線）。對另一輛車重復(fù)上述安排，直到 沒有未服務(wù)的需求點。對得到的可行的行程安排解中的每一條路徑，求解一個旅行商 問題，決定訪問指派給每一條行程的車輛的順序，最小化運輸總距離。得到可行解的 行程安排解后退出。問題二：車輛有4噸、6噸、8噸，同理運輸時間小于4小時，各線路所運物資 最大不能超過8T。在計算過程中，確定具體使用哪種類型的運輸車。對得到的可行 的行程安排解中的每一條路徑，計算所花費用，最后與問題一比較。表1

6、給出了各個需求點的需求量，為了完成任務(wù)，在工作時間范圍內(nèi)，每輛運輸 車可以承擔(dān)兩條甚至更多的線路。表中給出了需求點序號，編號，需求物資量T,以 及需求點的直角坐標(biāo)。表1站點編號需求量T坐標(biāo)（km）站點編號需求量T坐標(biāo)（km）XyXy1321621621517618354181117447191512508201996311212257792221089623279910224151910140251514111732620171214627211313129282420141012292516157143000將表1的30個點繪在坐標(biāo)系上。252016171824 28 26*.2915152

7、5 19271410 67 4-42344-20r13J4*2152*381211 1*91022 .0051015202530三. 基本假設(shè)模型假設(shè)1. 運輸車在運行的過程中無紅綠燈現(xiàn)象也沒有意外的發(fā)生，即不花時間2. 運輸車中途不停3. 運輸車回到倉庫的配貨時間不計4. 每個物資點只停留一次5. 運輸車沿街道方向均平行于坐標(biāo)軸6. 運輸車在中途除了送貨之外沒有別的時間耽擱7. 本文所用的資料和數(shù)據(jù)均真實可靠四、符號說明模型符號說明T,站點的物資需求量（i為站點編號，（x,y）為需求點的坐標(biāo)）M載運輸車運輸物資的總重費用M空運輸車空載的總重費用M運輸車運輸物資的總費用N運輸車運輸物資的總次數(shù)

8、K運輸車的總輛量*第j個運輸車的次數(shù)1運輸車在站點編號為i的需求點所送物資時為10運輸車在站點編號為i的需求點未送物資時為0心第m條線路選擇站點編號為i的需求點是最遠點時為1b =0t第m條線路選擇站點編號為i的需求點是最近點時為0五. 模型的建立與求解模型一的建立與求解：本模型考慮用多目標(biāo)動態(tài)規(guī)劃求解。由于問題中只要求給出一個合理的方案，故 只要滿足條件一一運輸車的工作時間上限是4個小時以及每條路線的最大載重量不 大于6T即可，本模型中追加兩個目標(biāo)一一路程最短和車輛最少?？梢酝ㄟ^以下方法 實現(xiàn)：每一個行程的第一個需求點是距離倉庫最近的未服務(wù)的需求點。用這種方法， 即可得到一組運行路線，總的運

9、行公里數(shù)，以及總費用。整理作圖，即可得到最優(yōu)化 結(jié)果。本模型中以滿足需求的費用最小的車輛行駛路徑，且使用盡量少的運輸車， 即，具體操作：1. 第一條行程中訪問了節(jié)點0-1-3-4-0,是因為1距離原點最近，因此由1出發(fā), 3是距離1點最近的點，而且兩處物資量之和為4,小于每輛最大負(fù)重量，可以繼續(xù) 指配。接著，4是距離3最近的點，而且三處物資量之和為，仍小于6,還可以繼續(xù)指 配。在剩下的未服務(wù)送貨點中，再繼續(xù)擴充，發(fā)現(xiàn)就會超出“6”這個上限，因此選 擇返回，所以0-1-3-4-0就為第一條路線所含有的需求點。2. 第二條行程中訪問了節(jié)點0-2-5-6-15-14-0,是因為在剩下的未服務(wù)送貨點中

10、, 2距離原點最近，因此由,2出發(fā)，5是距離2點最近的點，而且兩處物資量之和為， 小于每輛最大負(fù)重量，可以繼續(xù)指配。接著，6是距離5最近的點，而且三處物資量 之和為，仍小于6,還可以繼續(xù)指配。在剩下的未服務(wù)送貨點中，15距離6最近，總 物資量之和為。再繼續(xù)擴充，14距離15最近，總物資量之和為噸。再繼續(xù)擴充，發(fā) 現(xiàn)就會超出“6”這個上限，因此選擇返回，所以0-2-5-6-15-14-0就為第二條路線 所含有的送貨點。3第三條行程中訪問了 0-9-8-7-0,是因為在第二條形成以后剩下的為服務(wù)的送 貨點中，9點距離原點最近，然后8是離9最近的點，7是離8最近的點，而且三個 點的總貨重量為噸，小于

11、6噸，但在接下來的點中找不到符合條件的送貨點了，所以 只能從最近的路線返回原點。由計算得出所用的時間也在要求之內(nèi)。4第四條行程中訪問了 0-10-11-12-0,是因為在接下來的點中10離原點最近， 接著又找到11點然后12點最后選擇最近的道路回來，其中三個貨點的貨的總璽量為 噸，時間在四小時之內(nèi)。5第五條路線訪問了是因為在接下來的點中16點距離原點最近，該路線的四個送貨點的總重量為噸小于6噸，且時間在允許的范圍內(nèi)。6第六條路線訪問了 因為在剩下的點中13點距離原點最近，然后14和12 又劃為別的路線而且又不滿足貨物總量的限制要求，所以選擇19點然后就是25點， 排除24點之后選擇了 26點，

12、這四個點的貨物總量為噸，在貨物總量的限制范圍內(nèi)。 同樣總運輸時間也不超過4小時。7.第七條路線訪問了 0-22-21-20-23-0,是因為在剩下的點中22距離原點最近, 然后接著選擇21,然后20,然后再去23點，這四個點的貨物總重量為噸，時間為小 時。&第八條路線訪問了 0-27-29-28-0,因為剩下的三個點，總貨量為噸總路程為 100公里時間為3小時。符合題目的要求。在這八條路線中1、2條路線合用一輛車，3、4條路線合用一輛車，其余的路線 各配用一輛車。詳細(xì)的數(shù)據(jù)見表2和表3:詳細(xì)流程圖如下：找離原點最近的點設(shè)為 町且該點的訪問標(biāo)志設(shè) 為被訪問，該點物資需 求量為肌輸出該點我次遠點Y

13、找到符合條件的點，且不止一個是選擇物資質(zhì)量最大的那個點，標(biāo)志設(shè)為被訪問，輸岀該點，賦值給打且wewi+w圖21, 找離原該點最近的點A,且該點的訪問標(biāo)志設(shè)為被訪問，該點需求物資重量為 W,輸出該點；2, 找點v最近的點，物資重量為wl,且wl+w28-0根據(jù)以上路線，計算。表2線路序 號所經(jīng)站數(shù)最近點所用時 （小時）總載重（T）總路程 （公里）131 (3,2)24252 (1,5)54339 (10,2)384310 (14,0)465416 (2,16)706413 (12,9)747422 (21,0)788327(21,13)310029484然后，根據(jù)所經(jīng)歷的時間進行劃分，確定運輸車

14、數(shù)量。在工作時間小于4小時的 前提下，最終只需要六輛運輸車，第一條線路和第二條線路由一輛車運送，第三條和 第四條線路由一輛車運送，則各運輸車具體情況如下（表4）：表3車輛 序列線路所到需求點已行路程+載重空載 路程11+21342561514335+4+4+6+4+6+7+5+23+498710 11 123612+5+5+14+6+6+35161718243418+6+6+6+46131925263721+6+2+8+57222120233621+6+7+8+682729284434+7+5+根據(jù)表，運輸車重載運費2元/噸公里，空載費用元/公里，計算運輸車的費用為 下表（表4）:表4車輛序號

15、線路非空載總 費用（元）空載費用（元）總費用 （元）11+223+4183517465718682220411102151模型求解結(jié)果：第一輛車：0t1t34t0 和 OTTTm第二輛車：0t9t8t7t0和第三輛車：Otttt tO第四輛車：OtttttO 第五輛車：Ot tO 第六輛車：0t27t29t28t0 所花費用為：元模型二的建立與求解：此時運輸車的種類有4噸，6噸，8噸，運用問題一的方法：首先選擇距離遠點 最近的點a,再找距離a點最近的點，假設(shè)是b,且Ta+Tb=8,那么就繼續(xù)尋找距離 點b最近的點，并計算物資總重，比較。繼續(xù)以上步驟，當(dāng)總重大于8終止。然后比 較總重相加過程中接

16、近且小于4、6、8時的部分總重的差的絕對值，取絕對值最小的。 例如，1線路：最初計算線路是O-,此時的總重量為，但是在到達3時為4, |4-4|10t11t42-04 05 0-6 6噸運輸車8噸運輸車8噸運輸車8噸運輸車各條線路詳細(xì)情況表5:表5線路序 號所經(jīng)站數(shù)最近點m總載重(T)總路程(公里)131 (3,2)82262 (1, 5)423310 (14,0)46466 (3,11)685616 (2,16)1006513 (12,9)7229410根據(jù)工作時間小于4小時劃分組合，第一條線路和第七條線路由一輛車運送，因 此總共需要六輛運輸車，具體情況如下，表6：運輸車編 號線路所到需求點

17、已行路程+載重空載路 程11+71329415+4+32+22254789126+4+5+5+5+5+331011122014+6+6+44615141925182814+7+5+5+2+7+551617242627284418+6+10+7+5+10+6613202321222121+7+8+9+6+表6計算費用為表7表7運輸車 編號線路（重）非空 載總費用（元）（M空）空 載費用（元）（M）總費 用（元）11+7223126318331044145522662345832428模型求解結(jié)果：第-輛車：0 130 和 0290 第二輛車：0t2t5t4t7t8t9 第三輛車：Ot1Ot11t

18、42tO第四輛車：0T6mm第五輛車：0 第六輛車：0- - 所花費用為：2428元路徑為圖4：圖4將問題一和問題二的運輸費用描繪柱狀圖（附件一圖5）,相比較之下，可以發(fā) 現(xiàn)在路程較短時，問題二所用運輸費用較高；路程較長時，問題一所用運輸費用較低。六、模型的分析和檢驗倉庫每天要運送的物資在早上出發(fā)時間之前已經(jīng)全到了，沒有到的當(dāng)天就不運 送，這種模型現(xiàn)在已經(jīng)很成熟，因此采用這種解法應(yīng)該能夠達到減少運費的要求。但是曲于物資調(diào)運是一個比較復(fù)雜的問題設(shè)計到眾多的變量，上述模型尚有許多 因素沒有考慮在內(nèi)。比如每輛車送完物資，回來再準(zhǔn)備第二趟運送這個過程也要花時 間，這個時間沒有考慮到時間范圍內(nèi)。還有像城

19、市交通不平衡等問題，貨物分類等問 題。結(jié)果和誤差分析：理論上總時間算下來是小時和小時，每輛車平均工作4個小時，因此車數(shù)算下來 平均是和4039575輛車，在實際情況中4輛車就能送完所有的物資。七.型的推廣該模型廣泛運用于物資調(diào)度問題，大規(guī)模的突發(fā)性公共事件如sars危機.印度 洋海嘯.冰雪災(zāi)害、汶川地震等重大問題，在面臨這些問題時釆用多目標(biāo)動態(tài)分析，并且結(jié)合圖表，這樣會很大程度上加快解決問題的速度，減少不必要的損失，節(jié)省運 輸資金。而且突發(fā)事件之后往往伴隨著大量的應(yīng)急物資需求，釆用合理的運輸方式. 運輸路徑和最優(yōu)的應(yīng)急物資調(diào)度方案，及時的將救援物資送達物資需求點，這直接影 響到整個突發(fā)性公共事

20、件救援行動的成效。八、模型的評價與優(yōu)化模型的優(yōu)點本文此方案能合理的調(diào)度物資、分配物資的運輸、怎樣調(diào)度運輸費的最低，使供 貨商減小運輸過程中的費用，加快運輸時間，合理的配裝物資，合理的選擇運輸路線, 從而使供貨商增大利潤，收利最大。模型的缺點此方案沒有考慮運輸過程中有紅綠燈現(xiàn)象.意外的發(fā)生.中途遇某事而停車的現(xiàn) 象等，實際上這些現(xiàn)象和狀況是存在的，我們卻理想化的去調(diào)度物資的運輸。理論值 和實際值是相差很大的，這方案還需進行實踐的驗證才能更好的分配.調(diào)運物資。問 題二，我們在考慮到運輸成本的最低的前提下，沒有用到4噸的運輸車，如果用4噸 車必須把路線（1）拆成兩部分0-13-0, 0t29t0這樣

21、沒有直接用8噸車一 次運完便宜。參考文獻：1 霍亮，空間物流信息系統(tǒng)，中國測繪出版社：2006, 2（6675）2 鄭莉，董淵，張瑞，面向?qū)ο蟮某绦蛟O(shè)計和C+ （第三版），清華大學(xué)出版 社：（369-381）3 張磊。車輛調(diào)度問題的混合運算。鐵路運輸與經(jīng)濟，第三十卷第8附件：1.附件一問題一與問題二總費用對比總費用一總費用二運輸車的編號2.附件二計算過程中的部分程序： #include #include #include#define max 1000 using namespace std; struct verint x;int y;int num; float weight;bool v

22、isited30:ver v30;int nextl () int k, min=max, tag=0; float w;for (int i=l;i w)k=i;w=vi weight;tag=l;)if (tag)return k;else return 0;int next2(int k,float w)int min=max, tag=0, m, i;for(i=l;i30i+)if (visitedifalse&fabs(vk. xvi. x) + fabs (vk y-vi y)min&w+vi weight二6) minfabs (vk x-vi x)+fabs(vk y-vi y);111= i;tag=l;if (visitedifalse&fdbs(vk. xvi. x)+fabs (vk y-vi y)二二min&w+vi weightvm weight) m二 i;tagFl;if(tag)return m;else return 0;void way () int k;float w;k=next 1 ();w