中南大學(xué) 數(shù)學(xué)建模 lingo matlab 優(yōu)化建模論文 貨運(yùn)公司的運(yùn)輸問題

摘要合理安排車輛的運(yùn)載方案，能夠大大節(jié)省貨運(yùn)公司的運(yùn)輸費(fèi)用，以便能得到更大的利潤。本文通過構(gòu)建數(shù)學(xué)模型，尋求車輛配置的最優(yōu)方法，從而為運(yùn)輸公司提供明確的車輛的運(yùn)載方案。問題一為不調(diào)頭情況下的線性目標(biāo)規(guī)劃問題。模型一使用了圖論里的矩陣，再使用目標(biāo)規(guī)劃模型建立目標(biāo)函數(shù)與約束條件求出最少運(yùn)輸費(fèi)用。模型二采取分批次設(shè)置分界線兩側(cè)運(yùn)輸?shù)姆椒ǎ诳紤]運(yùn)載原料不能拆分，小件在上大件在下、運(yùn)輸途中不允許掉頭、空車運(yùn)載費(fèi)用小于重載費(fèi)用等約束條件的情況下，建立出車次-運(yùn)費(fèi)的資源配置多目標(biāo)規(guī)劃模型。通過逐步搜索的方法，在三種材料能卸便卸的情況下選擇出每一次出車的最優(yōu)方案，并且對材料A、B、C進(jìn)行重要性分析，將C材料看作是附加產(chǎn)品搭載在A、B材料上一起運(yùn)輸來滿足各公司對三種材料的需求，最后得到了一共出車28次，耗時(shí)為42小時(shí)，費(fèi)用為4905.4元的最優(yōu)方案。問題二為可掉頭情況下的線性目標(biāo)規(guī)劃問題。我們?nèi)匀徊捎昧祟愃朴趩栴}一的思路進(jìn)行解決的方式，為達(dá)到運(yùn)輸費(fèi)用小、運(yùn)輸時(shí)間短的要求，我們修改了每次的出車方案使得貨車卸完貨之后都原路返回，這樣就減少了貨車空載情況下所跑路程、時(shí)間與費(fèi)用。由此得到了出車28次，耗時(shí)為27.93小時(shí)，費(fèi)用為4572.8元的最優(yōu)方案。問題三考慮到部分公司有道路相通，在沒有出現(xiàn)負(fù)權(quán)的情況下，可以采用Dijkstra算法來解決這類最短路問題。對于有8個(gè)公司的規(guī)劃問題，可以將其進(jìn)行區(qū)域化，求出各部分局部最優(yōu)解，從而得到最優(yōu)運(yùn)輸方案。本題目的難點(diǎn)為車輛、貨物、公司三者之間相互關(guān)系中得到最小調(diào)度費(fèi)用的問題，所以首先得確定貨車的載貨情況，在各輛車均滿載的情況下，試圖滿足各公司的材料需求量，在某些公司無法滿足時(shí)，考慮某些車次不滿載或只裝載某一類貨物。在模型的推廣部分，加入了跨越分界線的運(yùn)輸方式，這樣可以相當(dāng)程度上減少不滿載情況下的出車次數(shù)，并解決單一材料的運(yùn)輸問題，雖未能減少了出車次數(shù)，但節(jié)約了行車費(fèi)用。關(guān)鍵字：目標(biāo)規(guī)劃模型逐步搜索Dijkstra算法問題重述1.1基本情況某地區(qū)有8個(gè)公司（如圖一編號①至⑧），某天某貨運(yùn)公司要派車將各公司所需的三種原材料A，B，C從某港口（編號⑨）分別運(yùn)往各個(gè)公司。路線是唯一的雙向道路（如圖一）。貨運(yùn)公司現(xiàn)有一種載重6噸的運(yùn)輸車，派車有固定成本20元/輛，從港口出車有固定成本為10元/車次（車輛每出動(dòng)一次為一車次）。每輛車平均需要用15分鐘的時(shí)間裝車，到每個(gè)公司卸車時(shí)間平均為10分鐘，運(yùn)輸車平均速度為60公里／小時(shí)（不考慮塞車現(xiàn)象），每日工作不超過8小時(shí)。運(yùn)輸車載重運(yùn)費(fèi)1.8元/噸公里，運(yùn)輸車空載費(fèi)用0.4元/公里。一個(gè)單位的原材料A，B，C分別毛重4噸、3噸、1噸，原材料不能拆分，為了安全，大小件同車時(shí)必須小件在上，大件在下。卸貨時(shí)必須先卸小件，1.2有關(guān)信息附錄中給出了該貨運(yùn)公司所掌握的一些數(shù)據(jù)資料：附件1：各公司當(dāng)天的需求量表；附件2：唯一的運(yùn)輸路線圖及相關(guān)里程數(shù)；問題提出請根據(jù)題中所給的這些數(shù)據(jù)資料，利用數(shù)學(xué)建模的方法，解決如下問題：（1）貨運(yùn)公司派出運(yùn)輸車6輛，每輛車從港口出發(fā)（不定方向）后運(yùn)輸途中不允許掉頭，應(yīng)如何調(diào)度（每輛車的運(yùn)載方案，運(yùn)輸成本）使得運(yùn)費(fèi)最??；（2）每輛車在運(yùn)輸途中可隨時(shí)掉頭，若要使得成本最小，貨運(yùn)公司怎么安排車輛數(shù)？應(yīng)如何調(diào)度？（3）選做（任選一問）：（01）如果有載重量為4噸、6噸、8噸三種運(yùn)輸車，載重運(yùn)費(fèi)都是1.8元/噸公里，空載費(fèi)用分別為0.2，0.4，0.7元/公里，其他費(fèi)用一樣，又如何安排車輛數(shù)和調(diào)度方案？（02）當(dāng)各個(gè)公司間都有或者部分有道路直接相通時(shí)，分析運(yùn)輸調(diào)度的難度所在，給出你的解決問題的想法（可結(jié)合實(shí)際情況深入分析）。二、問題分析合理安排車輛的運(yùn)載方案，能夠大大節(jié)省貨運(yùn)公司的運(yùn)輸費(fèi)用，以便能得到更大的利潤?？v觀全題，通過剖析題意可得：負(fù)重運(yùn)輸載重量越少，負(fù)載里程越短，運(yùn)載費(fèi)用就越少，因此需要貨車能卸貨就卸；此外派車次數(shù)越少，越能減少出車費(fèi)用，因此需使貨車每次載重相對最大化。另外由于出車方向不定，假設(shè)以順時(shí)針貨運(yùn)方向上，貨車最遠(yuǎn)到達(dá)④點(diǎn)；同樣的在逆時(shí)針貨運(yùn)方向上，貨車最遠(yuǎn)到達(dá)⑤點(diǎn)，由于負(fù)載費(fèi)用遠(yuǎn)大于空載，所以定④⑤為分界線，兩側(cè)運(yùn)輸為貨運(yùn)不超過分界限的運(yùn)輸方式。通過在相關(guān)原則下建立車次-運(yùn)費(fèi)的資源配置多目標(biāo)規(guī)劃模型來解決問題一。在問題一中，它的最短空載里程為兩側(cè)運(yùn)輸在各個(gè)公司卸載完畢后，不掉頭按原來行駛方向駛向⑨的里程。而在問題二中，由于運(yùn)輸途中可隨時(shí)掉頭，只需在問題一所建模型的基礎(chǔ)上，將其中的最短空載路程確定為：若超過分界線卸載完畢，就繼續(xù)前行至⑨；未超過分界線而卸載完畢，則按原路返回至⑨。對于問題三，當(dāng)各個(gè)公司間都有或者部分有道路直接相通時(shí)，原來確定的運(yùn)輸最小路徑已發(fā)生改變，各公司和港口已形成一個(gè)網(wǎng)狀結(jié)構(gòu)，在綜合考慮各方面約束的條件下可運(yùn)用Dijkstra算法來解決此類最短路問題。三、模型假設(shè)(1)假設(shè)每輛車裝載時(shí)盡量發(fā)揮其最大裝載能力；(2)假設(shè)運(yùn)輸車在行駛過程中不考慮塞車拋錨現(xiàn)象，以保證每輛車每天可以達(dá)到最大的工作時(shí)間；(3)假設(shè)運(yùn)輸車不會(huì)因天氣狀況，而影響其行駛速度，和裝載、卸載時(shí)間;四、符號說明m—出車一次的費(fèi)用(已知10元/次)k—派車一次的費(fèi)用（已知20元/次）—第i次出車時(shí)載重的費(fèi)用—第i次出車時(shí)空載的費(fèi)用S—總運(yùn)費(fèi)方案a:A+2C方案b:A方案c:2B方案d:5C方案e：A+C方案f：B+3C方案g：B+2C方案h：B+C方案i：B五、模型的建立與求解問題1：模型一：符號說明：：第i次出車在公司j所卸A材料單位數(shù)：第i次出車在公司j所卸B材料單位數(shù)：第i次出車在公司j所卸C材料單位數(shù)：港口9順時(shí)針到各個(gè)公司的距離：第i次出車在公司j將所有的材料卸完：第j個(gè)公司對第k種材料的當(dāng)日需求量模型的建立：根據(jù)三種材料的裝卸情況，可以分別得到關(guān)于材料A、B、C裝卸情況的三個(gè)矩陣X、Y、Z：建立港口⑨順時(shí)針方向與各個(gè)公司之間距離的矩陣M：矩陣N為0-1矩陣，當(dāng)?shù)趇次出車在第j個(gè)城市正好將所有的材料都卸完，記作，其他情況下記作。建立每日各公司對各材料需求量的矩陣A：最小運(yùn)輸費(fèi)用的目標(biāo)函數(shù)：由相關(guān)的約束條件得到以下式子：本模型的缺點(diǎn)是沒有辦法將逆時(shí)針方向運(yùn)輸材料的情況，用0-1型整數(shù)規(guī)劃模型融合到該模型中來，得到的解不是最少運(yùn)輸費(fèi)用的運(yùn)載方案，所以我們采用了模型二對問題一進(jìn)行進(jìn)一步求解。模型二：對于問題一，在貨運(yùn)里程為固定的60公里的情況下，我們希望貨車能盡可能早的將貨物從車上卸下，以減少負(fù)載行駛過程中產(chǎn)生的費(fèi)用。首先將A種材料看作是重要物資首先進(jìn)行運(yùn)輸，而將C種材料看作是附加物資與A種材料一起裝車；在滿足各公司A種產(chǎn)品的要求之后，同樣的，再將B種材料看作是重要的物資進(jìn)行運(yùn)輸，將C種材料與B種材料一起裝車；最后對于所剩B類材料未能滿足的公司，我們將繼續(xù)以貨車能卸貨就卸、貨車每次載重相對最大化的原則只裝載B種材料進(jìn)行運(yùn)輸。在考慮運(yùn)載原料不能拆分，小件在上大件在下、運(yùn)輸途中不允許掉頭、空車運(yùn)載費(fèi)用小于重載費(fèi)用等約束條件以及在貨車能卸貨就卸貨、貨車每次載重相對最大化總原則下，建立出車次-運(yùn)費(fèi)的資源配置多目標(biāo)規(guī)劃模型。為了達(dá)到費(fèi)用最小的目標(biāo)，給出一個(gè)運(yùn)輸原則：盡可能的滿載，運(yùn)送時(shí)以滿足各個(gè)公司的需求中A的優(yōu)先級最高，其次是B，最后是C；若順時(shí)針運(yùn)送，盡量在到達(dá)公司5之前把貨物卸完，若逆時(shí)針運(yùn)輸，則盡量在到達(dá)公司4之前把貨物卸完。若沒有滿足這兩個(gè)條件中的任何一個(gè)，都可以考慮反向運(yùn)輸。費(fèi)用模型如下：模型的求解步驟：派出裝載方案a（1單位A，2單位C）的貨車順時(shí)針?biāo)拓浕蛘吣鏁r(shí)針?biāo)拓?，在行車途中所?jīng)過的公司能卸貨便將車上的可卸貨物放下，順時(shí)針?biāo)拓浀呢涇嚤仨氃诠?之前將貨卸完，逆時(shí)針?biāo)拓浀呢涇嚤仨氃诠?之前將貨卸完，若派出的貨車無法將6噸貨物卸完便不再派發(fā)方案a的貨車；二、若有某一公司以及它之前的公司只需要1單位C材料，則派出裝載方案e（1單位A，1單位C）的貨車進(jìn)行運(yùn)輸；三、若有某一公司以及它之前的公司不需要C材料，則派出裝載方案b（1單位A）的貨車就近運(yùn)輸；四、若A材料已滿足各公司的需求，則派出裝載方案f（1單位B，3單位C）的貨車順時(shí)針或者逆時(shí)針?biāo)拓?，卸貨原則同步驟一，五、若有某一公司以及它之前的公司只需要2單位C材料，則派出裝載方案g（1單位B，2單位C）的貨車進(jìn)行運(yùn)輸；六、若有某一公司以及它之前的公司只需要2單位C材料，則派出裝載方案h（1單位B，1單位C）的貨車進(jìn)行運(yùn)輸；七、若有某一公司以及它之前的公司不需要C材料，則派出裝載方案c（2單位B）的貨車就近運(yùn)輸，能卸貨便卸貨；八、若最后只有公司4或公司5各需要1單位B，則派出裝載方案i（1單位B）的貨車就近運(yùn)輸，并不能跨越分界線。得出最佳出車情況具體如下：出車方案卸貨方案xiyixi+yi1a9→1（1，0，2）86.420.8107.22a9→1（1，0，2）86.420.8107.23a9→8（0，0，1）→7（1，0，1）10819.6127.64a9→8→7（1，0，2）118.819.6138.45a9→1（0，0，1）→2（1，0，1）149.418167.46a9→8→7（0，0，2）→6→5（1，0，0)205.214.82207a9→1→2(0，0，1)→3(1，0，1)24314.4257.48a9→1→2→3(1，0，2)259.214.4273.69a9→1→2→3(0，0，1)→4(1，0，1)31512.4327.410a9→8→7→6(0，0，2)→5→4(1，0，1)277.211.6288.811a9→8→7→6(0，0，1)→5(0，0，1)→4(1，0，0)291.611.6303.212b9→8(1，0，0)3622.458.413b9→8(1，0，0)3622.458.414b9→8(1，0，0)3622.458.415b9→8(1，0，0)3622.458.416b9→8(1，0，0)3622.458.417b9→1(1，0，0)57.620.878.418b9→1(1，0，0)57.620.878.419c9→8(0，2，0)54227620c9→8(0，1，0)→7(0，1，0)86.419.610621c9→1(0，1，0）→2（0，1，0）124.218142.222c9→8→7(0，1，0)→6(0，1，0)140.418158.423c9→8→7→6(0，2，0)1621818024c9→1→2（0，2，0）1621818025c9→1→2（0，2，0）1621818026c9→8→7→6（0，1，0）→5（0，1，0）205.214.822027c9→8→7→6→5（0，1，0）→4（0，1，0)291.611.6303.228d9→8→7→6→5(0，0，3)→4(0，0，1)18011.6191.6合計(jì)4003.2501.24504.4方案a:A+2C方案b:A方案c:2B方案d:5C用上述模型進(jìn)行計(jì)算：總費(fèi)用:又因?yàn)?8次的出車中共停車卸貨42次，裝貨28次，若不卸貨的出車一次需1個(gè)小時(shí)，故總時(shí)間為三部分時(shí)間的加和:總時(shí)間問題2：在第一問的基礎(chǔ)上，假定載貨方案及卸載方案不變的情況下，運(yùn)費(fèi)的變動(dòng)只取決于空載的距離，如果掉頭的空載距離短就掉頭行駛，如果不掉頭的空載距離短就按原方向行駛。即：當(dāng)車輛沿順時(shí)針方向跨過4公司還沒有卸完或者沿逆時(shí)針方向到達(dá)公司5還沒有卸完的的話，就不掉頭，按原來方向繼續(xù)前進(jìn)；當(dāng)車輛沿順時(shí)針方向到達(dá)5公司之前或者沿逆時(shí)針方向到達(dá)4公司之前就能卸完的情況下，就掉頭行駛；得出最佳出車情況具體如下：出車裝載方案卸貨方案xiyixi+yi1a9→1（1，0，2）→掉頭86.43.289.62a9→1（1，0，2）→掉頭86.43.289.63a9→8（0，0，1）→7（1，0，1）→掉頭1084.4112.44a9→8→7（1，0，2）→掉頭118.84.4123.25a9→1（0，0，1）→2（1，0，1）→掉頭149.46155.46a9→8→7（0，0，2）→6→5（1，0，0)→掉頭205.29.2214.47a9→1→2(0，0，1)→3(1，0，1)→掉頭2439.6252.68a9→1→2→3(1，0，2)→掉頭259.29.6268.89a9→1→2→3(0，0，1)→4(1，0，1)→掉頭31511.6326.610a9→8→7→6(0，0，2)→5→4(1，0，1)277.211.6288.811a9→8→7→6(0，0，1)→5(0，0，1)→4(1，0，0)291.611.6303.212b9→8(1，0，0)→掉頭3623813b9→8(1，0，0)→掉頭3623814b9→8(1，0，0)→掉頭3623815b9→8(1，0，0)→掉頭3623816b9→8(1，0，0)→掉頭3623817b9→1(1，0，0)→掉頭57.63.260.818b9→1(1，0，0)→掉頭57.63.260.819c9→8(0，2，0)→掉頭5425620c9→8(0，1，0)→7(0，1，0)→掉頭86.44.490.821c9→1(0，1，0）→2（0，1，0）→掉頭124.26130.222c9→8→7(0，1，0)→6(0，1，0)→掉頭140.46146.423c9→8→7→6(0，2，0)→掉頭162616824c9→1→2（0，2，0）→掉頭162616825c9→1→2（0，2，0）→掉頭162616826c9→8→7→6（0，1，0）→5（0，1，0）→掉頭205.29.2214.427c9→8→7→6→5（0，1，0）→4（0，1，0)291.611.6303.228d9→8→7→6→5(0，0，3)→4(0，0，1)18011.6191.6合計(jì)4003.2169.64172.8總費(fèi)用總時(shí)間為六、模型評價(jià)與推廣約束條件重新確定后的推廣模型本文依據(jù)題目分析運(yùn)輸問題，做出分批次運(yùn)輸與兩側(cè)運(yùn)輸?shù)呐袛?，以及第三問題的區(qū)域化求局部最優(yōu)解，得出了我們自己認(rèn)為比較理想的結(jié)果。我們的模型對于題目的完整性解答有些不足，在第一問與第二問中，我們籠統(tǒng)的將貨運(yùn)地點(diǎn)按分界線分成兩個(gè)部分來進(jìn)行求解，無法考慮到在跨越分界線運(yùn)輸情況下的最優(yōu)解，而且我們沒有能夠建立通用的計(jì)算模型而是采取的手工計(jì)算。因此在取消跨界約束的情況下，我們對問題二的模型做了改進(jìn)，重新構(gòu)建了數(shù)學(xué)模型，所得最佳運(yùn)載方案結(jié)果如下表優(yōu)化改進(jìn)方案出車裝載方案卸貨方案xiyixi+yi1a9→1（1，0，2）→空載掉頭86.43.289.62a9→1（1，0，2）→空載掉頭86.43.289.63a9→8（0，0，1）→7（1，0，1）→空載掉頭1084.4112.44a9→8→7（1，0，2）→空載掉頭118.84.4123.25a9→1（0，0，1）→2（1，0，1）→空載掉頭149.46155.46a9→8→7(0，0，2)→6(0，0，2)→空載掉頭93.6699.67a9→8→7→6(0，0，1)→5(1，0，1)→空載掉頭2349.2243.28a9→1→2(0，0，1)→3(1，0，1)→空載掉頭2439.6252.69a9→1→2→3(1，0，2)→空載掉頭259.29.6268.810a9→1→2→3(0，0，1)→4(1，0，1)→空載掉頭304.211.6315.811b9→8→7→6→5(0，0，2)→4(1，0，0)30611.6317.612b9→8→7→6→5(0，0，1)→4(1，0，1)320.411.633213b9→8(1，0，0)→空載掉頭3623814b9→8(1，0，0)→空載掉頭3623815b9→8(1，0，0)→空載掉頭3623816b9→8(1，0，0)→空載掉頭3623817b9→8(1，0，0)→空載掉頭3623818b9→1(1，0，0)→空載掉頭57.63.260.819b9→1(1，0，0)→空載掉頭57.63.260.820c9→8(0，2，0)→空載掉頭5425621c9→8(0，1，0)→7(0，1，0)→空載掉頭86.44.490.822c9