數(shù)學(xué)建模貨車編組問題

1、西南財(cái)經(jīng)大學(xué)數(shù)學(xué)建模競(jìng)賽貨運(yùn)列車編組運(yùn)輸問題貨運(yùn)列車編組運(yùn)輸問題摘要本次問題編程的目的是，在不同問題設(shè)定下，制定貨運(yùn)列車的最佳編組方案。對(duì)于問題一：?jiǎn)栴}一是以運(yùn)輸貨物數(shù)量最多、運(yùn)輸總重量最小為目標(biāo)函數(shù)的雙目標(biāo)優(yōu)化問題。參考公司投資組合問題中為解決利潤(rùn)最大、風(fēng)險(xiǎn)最小而采用的有效前沿的方法，我們用MATLAB編程得到可行的裝運(yùn)方案，做出各方案的運(yùn)輸總重量和運(yùn)輸數(shù)量決定的散點(diǎn)圖，得到類似的有效前沿，具體方案見4.2表二：對(duì)于問題二：?jiǎn)栴}二是下料問題，因此需要先確定可行的下料方式，即兩種車廂可行的貨物裝載方式。以每種裝載方式的使用次數(shù)為決策變量，總使用次數(shù)最少為目標(biāo)函數(shù)，建立整數(shù)線性規(guī)劃模型求解。用M

2、ATLAB解得：要將貨物運(yùn)輸完畢，B,C,E分別為68、50、41件時(shí)使用的最少車廂數(shù)量為25，B,C,E分別為48,42,52件時(shí)使用的最少車廂數(shù)量為21，具體方案見5.2表三、表四。對(duì)于問題三：由于上午、下午需要運(yùn)輸?shù)募b箱數(shù)量是隨機(jī)的，導(dǎo)致鐵路部門的利潤(rùn)也是隨機(jī)的，因此我們以鐵路部門的平均日利潤(rùn)最大為目標(biāo)函數(shù)，對(duì)上午、下午進(jìn)行獨(dú)立分析，構(gòu)建概率模型，并用MATLAB求解，得到最佳編組方案:上午發(fā)的列車帶41節(jié)型車廂、下午發(fā)的列車帶38節(jié)型車廂。對(duì)于問題四：我們參考圖論模型中的dijkstra算法，將模型中的權(quán)重新定義為到各站點(diǎn)的收益，利用matlab軟件找到收益最大的路線，盡可能滿足這條

3、路線上的需求量，然后去掉路線中除去起點(diǎn)和終點(diǎn)的點(diǎn)，再次運(yùn)用程序計(jì)算利潤(rùn)最大的路線，重復(fù)以上過程到只剩下起點(diǎn)和終點(diǎn)。得到最佳編組運(yùn)輸方案為：路線A-B1-C2-D2-E3-F運(yùn)輸3次分別帶40、40、29節(jié)車廂；路線A-B2-C2-D1-E1-F滿載運(yùn)輸1次；路線A-B2-C4-D3-E3-F運(yùn)輸2次分別帶40、2節(jié)車廂；路線A-B1-C1-D1-E2-F運(yùn)輸1次帶27節(jié)車廂；路線A-B2-C3-D2-E2-F運(yùn)輸1次分別帶29節(jié)車廂，此時(shí)鐵路部門利潤(rùn)為449050元。對(duì)于問題五：模仿第四題的思路，在其基礎(chǔ)上，考慮各個(gè)站點(diǎn)之間集裝箱運(yùn)輸?shù)男枨罅?，得到最佳編組運(yùn)輸方案見8.2.4表五。關(guān)鍵詞：雙目

4、標(biāo)優(yōu)化 有效前沿 下料問題 概率模型 dijkstra算法1.問題重述貨運(yùn)列車編組調(diào)度的科學(xué)性和合理性直接影響貨物運(yùn)輸?shù)男?。在不同的問題設(shè)定下，進(jìn)行分析得到貨運(yùn)列車的最佳編組方案。具體設(shè)定及需要解決的問題如下：1.1問題一1) 甲地到乙地每天有5種貨物需要運(yùn)輸，其包裝箱相關(guān)參數(shù)確定（附錄一表1）。2) 每天有一列貨運(yùn)列車從甲地發(fā)往乙地，由1節(jié)型車廂（單層平板車）和2節(jié)型車廂（雙層箱式貨車）編組（具體規(guī)格見附錄一表2）。3) 貨物在車廂中必須按占用車廂長(zhǎng)度最小的方式放置，且不允許重疊；型箱式車廂下層裝載貨物后剩余長(zhǎng)度小于等于0.2米，才能在上層放置貨物。Ø 試設(shè)計(jì)運(yùn)輸貨物數(shù)量最多的條

5、件下，運(yùn)輸總重量最小的裝運(yùn)方案。1.2問題二1) 在編組中型車廂的數(shù)量多于型車廂數(shù)量。2) 型箱式車廂下層裝載貨物后剩余長(zhǎng)度小于等于5米，才能在上層放置貨物。3) 貨物裝車其它規(guī)則同問題1。Ø 如果現(xiàn)有B,C,E三種類型的貨物各68、50、41件，試設(shè)計(jì)一個(gè)使用車廂數(shù)量最少的編組方案將貨物運(yùn)輸完畢。Ø 若B,C,E三種類型的貨物各有48,42,52件，請(qǐng)重新編組。1.3問題三1) 從甲地到乙地每天上午和下午各發(fā)送一列由型車廂編組的貨運(yùn)列車。2) 每列火車開行的固定成本為30000元，加掛一節(jié)車廂的可變成本為1500元。3) 鐵路部門擬將貨物放置到長(zhǎng)、寬、高分別為4米，3米及

6、1.99米的集裝箱中運(yùn)輸，每個(gè)集裝箱的總重量不超過18噸，集裝箱的運(yùn)費(fèi)為1000元/個(gè)。4) 每天需要運(yùn)輸?shù)募b箱數(shù)量是隨機(jī)的（過去最近100天數(shù)據(jù)見附錄一表3）。5) 上午的需求如果不能由上午開行列車運(yùn)輸，鐵路部門要支付50元/個(gè)的庫(kù)存費(fèi)用；下午列車開行后如果還有剩余集裝箱，鐵路部門將支付200元/個(gè)的賠償，轉(zhuǎn)而利用其它運(yùn)輸方式運(yùn)輸。Ø 試制定兩列火車的最佳編組方案。1.4問題四1) 每天鐵路部門將以A站為起點(diǎn)F站為終點(diǎn)，沿不同的路線開行若干趟全部用型車廂編組的貨運(yùn)列車，每列火車最大編組量為40節(jié)車廂。2) 每列火車列車開行的固定成本為15000元，每節(jié)車廂開行的可變成本為1元/公

7、里，每個(gè)集裝箱的運(yùn)費(fèi)為2元/公里（按兩車站間的最短鐵路距離計(jì)費(fèi)）。3) 鐵路網(wǎng)線情況見附錄一表4，從A站到其它站點(diǎn)的潛在集裝箱運(yùn)輸需求量見附錄一表5，集裝箱規(guī)格同第三問（鐵路部門沒有義務(wù)把集裝箱全運(yùn)輸完畢）。Ø 請(qǐng)為鐵路部門設(shè)計(jì)一個(gè)編組運(yùn)輸方案。1.5問題五1) 鐵路部門每天從A站用型車廂編組開行到F站的若干趟貨運(yùn)列車。2) 每天各個(gè)車站之間潛在的集裝箱運(yùn)輸量見附錄一表6。3) 鐵路網(wǎng)線及費(fèi)用設(shè)定同問題4。Ø 請(qǐng)為鐵路部門設(shè)計(jì)一個(gè)編組運(yùn)輸方案。2. 基本假設(shè)與符號(hào)說明2.1基本假設(shè)1) 貨物不能重疊放置，且不能直立放置；2) 上午運(yùn)不完的集裝箱，歸到下午需要運(yùn)的集裝箱的范疇

8、；3) 出于利潤(rùn)最大化的考慮，發(fā)出的列車車廂數(shù)達(dá)到最大編組量且每個(gè)車廂中裝滿三個(gè)集裝箱；4) 超過需求量的集裝箱，鐵路部門收不到相應(yīng)的運(yùn)費(fèi)；5) 從A出發(fā)時(shí)，為中途站點(diǎn)所有要裝上的集裝箱留下位置，即同一車廂位置不考慮裝卸集裝箱后的重復(fù)使用；6) 每一條路線可以重復(fù)運(yùn)輸。2.2符號(hào)說明=1,2,3,4,5分別對(duì)應(yīng)貨物類型A,B,C,D,Ei型貨物占用車廂長(zhǎng)度i型貨物重量、型車廂的長(zhǎng)度、型車廂的載重量單個(gè)車廂某裝載方式中i型貨物的裝載量只考慮B,C,E的型車廂第j種裝載方式的使用次數(shù)只考慮B,C,E的型車廂第j種裝載方式的使用次數(shù)i型貨物現(xiàn)有數(shù)量 r1 r2上午、下午需要運(yùn)的集裝箱的數(shù)量s1 s2

9、上午、下午發(fā)出的貨運(yùn)列車的車廂數(shù)R1 R2上午、下午鐵路部門的利潤(rùn)3. 問題分析針對(duì)問題一，我們首先明確了問題一是以運(yùn)輸貨物數(shù)量最多、運(yùn)輸總重量最小為目標(biāo)函數(shù)的雙目標(biāo)優(yōu)化問題，借鑒公司投資組合問題中為解決利潤(rùn)最大、風(fēng)險(xiǎn)最小而采用的有效前沿的方法，我們用MATLAB編程得到可行的裝運(yùn)方案，做出各方案的運(yùn)輸總重量和運(yùn)輸數(shù)量決定的散點(diǎn)圖，得到類似的有效前沿。針對(duì)問題二，我們注意到其實(shí)質(zhì)是下料問題，因此需要先考慮可行的下料方式，即兩種車廂可行的貨物裝載方式，以每種裝載方式的使用次數(shù)作為決策變量，總使用次數(shù)最少為目標(biāo)函數(shù)，建立整數(shù)線性規(guī)劃模型求解。針對(duì)問題三，由于每天需要運(yùn)輸?shù)募b箱數(shù)量是隨機(jī)的，導(dǎo)致鐵

10、路部門每天的利潤(rùn)也是隨機(jī)的，不能作為優(yōu)化模型的目標(biāo)函數(shù)，因此我們以鐵路部門的平均日利潤(rùn)最大為目標(biāo)函數(shù)，以上午、下午發(fā)出的貨運(yùn)列車的車廂數(shù)為決策變量，構(gòu)建概率模型，并用MATLAB求解。針對(duì)問題四，我們參考圖論模型中的dijkstra算法，將模型中的權(quán)重新定義為到各站點(diǎn)的收益，利用matlab軟件找到收益最大的路線，盡可能滿足這條路線上的需求量，然后去掉路線中除去起點(diǎn)和終點(diǎn)的點(diǎn)，再次運(yùn)用程序計(jì)算利潤(rùn)最大的路線，重復(fù)以上過程，直到只剩下起點(diǎn)和終點(diǎn)，得到最佳編組運(yùn)輸方案。針對(duì)問題五，模仿第四題的思路，在其基礎(chǔ)上，考慮各個(gè)站點(diǎn)之間集裝箱運(yùn)輸?shù)男枨罅?，進(jìn)行求解。4. 問題一的解答4.1模型一的建立4.1

11、.1基本思路確定雙目標(biāo)優(yōu)化類比投資組合問題的有效前沿確定可行的裝運(yùn)方案計(jì)算相應(yīng)的運(yùn)輸數(shù)量和運(yùn)輸總重量做出散點(diǎn)圖，得到有效前沿4.1.2對(duì)于雙目標(biāo)的處理問題一要求，根據(jù)題設(shè)，設(shè)計(jì)運(yùn)輸貨物數(shù)量最多的條件下，運(yùn)輸總重量最小的裝運(yùn)方案，這是以運(yùn)輸貨物數(shù)量最多、運(yùn)輸總重量最小為目標(biāo)函數(shù)的雙目標(biāo)優(yōu)化問題。對(duì)于雙目標(biāo)優(yōu)化問題常見的方法有，分層序列法以及化多為少的方法，如主要目標(biāo)法、線性加權(quán)法、理想點(diǎn)法等，但是這些方法各有局限，且優(yōu)化的結(jié)果并不直觀1。聯(lián)系公司投資組合中利潤(rùn)最大、風(fēng)險(xiǎn)最小的問題2，我們發(fā)現(xiàn)問題一與其有相似的情況，如下表。表一：投資組合問題與問題一的比較投資組合問題問題一雙目標(biāo)優(yōu)化利潤(rùn)最大運(yùn)輸貨

12、物數(shù)量最大風(fēng)險(xiǎn)最小運(yùn)輸總重量最小方案確定每年每個(gè)項(xiàng)目投資多少每車廂每貨物裝載多少方案選擇投資組合方案貨物裝運(yùn)方案因此我們決定類比公司投資組合問題中采用的有效前沿的方法,得到問題一的有效前沿。4.1.3確定可行的貨物裝運(yùn)方案要得到有效前沿，確定可行的貨物裝運(yùn)方案是第一步。1.基本思路由于貨物不能重疊放置，我們可以將貨物車廂中的裝載問題抽象為二維矩形件的排樣問題，只是增加了貨物總重量的上限約束。如果將一節(jié)車廂和兩節(jié)車廂一起進(jìn)行分析，情況較為復(fù)雜，為減少計(jì)算負(fù)荷，我們先對(duì)兩種車廂各自的可行裝載方式進(jìn)行分析，再將其進(jìn)行組合。2.考慮單個(gè)車廂時(shí)，滿足如下條件：1) 貨物占用車廂的高度車廂高度考慮實(shí)際情況

13、以及題中所給的例子，我們假設(shè)貨物不能豎直放置。此時(shí)只需考慮貨物實(shí)際高度與車廂高度的關(guān)系，得到型車廂的第二層不能放置A類和B類貨物的結(jié)論。2) 貨物按占用車廂長(zhǎng)度最小方式放置對(duì)于A,C,D,E類的貨物，他們占用車廂的最小長(zhǎng)度就是他們的實(shí)際長(zhǎng)度。對(duì)于B類貨物，需要進(jìn)行分類討論：車廂中B類貨物的裝載量為偶數(shù)時(shí)，兩兩并排放置（如圖1左）占用車廂長(zhǎng)度最??；車廂中B類貨物的裝載量為奇數(shù)時(shí)，在兩兩并排的基礎(chǔ)上，將余下的一件B類貨物橫著放置（如圖1右）占用車廂長(zhǎng)度最小。 圖1 B類貨物放置示意圖即3) 貨物占用車廂的寬度車廂寬度貨物按占用車廂長(zhǎng)度最小的方式放置時(shí)，恰使得A,C,D,E類貨物占用車廂的寬度等于車

14、廂寬度，而對(duì)B類貨物進(jìn)行分類討論時(shí)，已經(jīng)考慮到了車廂寬度的限制，因此這一條件可以不單獨(dú)列出。4) 貨物占用車廂總長(zhǎng)度車廂長(zhǎng)度5) 貨物總重量車廂載重量6) 型車廂下層裝載貨物后剩余長(zhǎng)度小于等于0.2米時(shí)，才能在上層放置貨物3. 在MATLAB中編程（源程序見附錄二表1）得到兩種車廂可行的貨物裝載方式（附錄二表2）4.對(duì)兩種車廂可行的貨物裝載方式進(jìn)行組合因?yàn)榱熊囉梢还?jié)、兩節(jié)編組，在型車廂可行的貨物裝載方式中選擇一種，在型車廂可行的貨物裝載方式中選擇兩次（可重復(fù)），記錄下裝載貨物不超過數(shù)量上限的組合，得到可行的裝運(yùn)方案，計(jì)算其運(yùn)輸數(shù)量及運(yùn)輸總重。（MATLAB源程序見附錄二表3，由于可行的裝運(yùn)方案

15、過多，不在附錄中體現(xiàn)，見附件 可行裝運(yùn)方案.xlsx）4.2模型一的求解由得到可行裝運(yùn)方案的數(shù)據(jù)，在MATLAB中做出散點(diǎn)圖及邊界曲線，并用MATLAB 自帶的基本擬合工具得到擬合曲線y=-0.00074x2+0.34x-14。結(jié)果如下：圖2：模型一求解出的有效前沿表二：有效前沿上的點(diǎn)所對(duì)應(yīng)的裝運(yùn)方案運(yùn)輸重量122128135143149.5158.5170180.5運(yùn)輸數(shù)量1718192021222324型車廂A4444344444322B0000000000000C0000000000244D0000100000000E0000000000000型車廂一A下0303211222333B下0

16、101000100111C下1010111011000D下5050033100000E下0202311233222C上0100000001100D上0000201022111E上0002022100122型車廂二A下3030222111122B下1010111000011C下0101000111100D下0505111333313E下2020222111120C上1000000000000D上0000000111131E上00201112222025.問題二的解答5.1模型二的建立問題二實(shí)質(zhì)是下料問題，因此建立模型二的思路與其一致。5.1.1確定兩種車廂只考慮B,C,E時(shí)可行的貨物裝載方式1.

17、基本思路問題二中減少了貨物的類型，但仍滿足4.1.3中考慮單個(gè)車廂時(shí)的基本思路，則1) 型車廂的第二層不能放置B類貨物2)3)4)需要注意的是：型箱式車廂下層裝載貨物后剩余長(zhǎng)度小于等于5米，就能在上層放置貨物。2.求解結(jié)果在MATLAB中編程求解（源程序見附錄三表1），通過Excel對(duì)結(jié)果進(jìn)行數(shù)據(jù)分析和整合，排除明顯劣解，得到只考慮B,C,E時(shí)型車廂可行的貨物裝載方式22種、車廂可行的貨物裝載方式125種（附錄三表2）。5.1.2確定決策變量用表示只考慮B,C,E時(shí)型車廂第j種裝載方式的使用次數(shù)，用表示只考慮B,C,E時(shí)型車廂第j種裝載方式的使用次數(shù)，則、是模型二的決策變量，均為非負(fù)整數(shù)。5.

18、1.3確定目標(biāo)函數(shù)問題二要求使用車廂數(shù)量最少，即各裝載方式使用次數(shù)之和最少，所以目標(biāo)函數(shù)為：5.1.4確定約束條件1) 型車廂的數(shù)量多于型車廂2) 貨物要運(yùn)輸完畢，即裝運(yùn)方案可運(yùn)走的i型貨物的數(shù)量不小于現(xiàn)有的數(shù)量T2、T3、T5分別為各方案中B,C,E類貨物的運(yùn)載量3) 決策變量為非負(fù)整數(shù)，即5.1.5得到目標(biāo)函數(shù) 5.2模型二的求解調(diào)用MATLAB整數(shù)線性規(guī)劃函數(shù)求解模型二（源程序見附錄三表3），得到B,C,E分別為68、50、41件時(shí)使用的最少車廂數(shù)量為25，B,C,E分別為48,42,52件時(shí)使用的最少車廂數(shù)量為21。具體結(jié)果如下:表三：B,C,E分別為68、50、41件時(shí)使用車廂數(shù)量最

19、少的編組方案方案次數(shù)型車廂（共13）型車廂（共12）No.7（2）No.15（8）No.19（2）No.22（1）No.106（5）No.121（7）B023534C622003D020040C上層00D上層10此時(shí)最后一個(gè)車廂多出了一件B的位置，以及三件C的位置。表四：B,C,E分別為48、42、52件時(shí)使用車廂數(shù)量最少的編組方案方案次數(shù)型車廂（共11）型車廂（共10）No.7（3）No.12（2）No.15（6）No.1（1）No.104（1）No.106（4）No.121（1）No.122（1）No.123（2）B012033455C642000300D012434011C上層00000

20、1D上層521010此時(shí)最后一個(gè)車廂多出了一件C的位置。6. 問題三的解答6.1數(shù)據(jù)處理根據(jù)過去最近100天上午和下午需要運(yùn)的集裝箱數(shù)量的數(shù)據(jù)，做出散點(diǎn)圖。沒有發(fā)現(xiàn)數(shù)據(jù)的明顯規(guī)律，用MATLAB進(jìn)行數(shù)據(jù)分布擬合，發(fā)現(xiàn)兩組數(shù)據(jù)均服從正態(tài)分布，接受概率分別為0.2943、0.9250.6.2模型三的建立6.2.1確定目標(biāo)函數(shù)因?yàn)槊刻焐衔?、下午需要運(yùn)輸?shù)募b箱數(shù)量都是隨機(jī)的，所以我們對(duì)上午、下午分別考慮，則鐵路部門的日利潤(rùn)等于上午、下午的利潤(rùn)之和，即目標(biāo)函數(shù)為6.2.2推導(dǎo)過程1.題意理解因?yàn)榧b箱和車廂的規(guī)格都固定，所以當(dāng)上午發(fā)出的列車有s1節(jié)車廂時(shí)，可運(yùn)輸集裝箱的為3s1。鐵路部門上午的利潤(rùn)R1

21、與上午需要運(yùn)輸?shù)募b箱的數(shù)量r1有關(guān)，當(dāng)時(shí)，鐵路部門獲得最多的運(yùn)費(fèi)；當(dāng)時(shí)，鐵路部門需要支付未被運(yùn)走的集裝箱的庫(kù)存費(fèi)用。即 對(duì)于下午，需要運(yùn)輸?shù)募b箱數(shù)量r2除了原來的需求，還可能包括上午剩余的集裝箱。則 2. 對(duì)上午的分析3假設(shè)上午需要運(yùn)輸?shù)募b箱數(shù)量是r1的概率為f(r1),可以由過去的數(shù)據(jù)得到，用鐵路部門的利潤(rùn)期望值來衡量利潤(rùn)，則 即在f(r1)已知時(shí)，求s1使得R1最大。為了便于分析，將概率f(r1)轉(zhuǎn)化為概率密度函數(shù)P(r1)，則對(duì)R1(s1)求導(dǎo)，并讓導(dǎo)數(shù)等于0，得到因?yàn)?，所以將上式左右兩邊的分母都加上分子，得到由?shù)據(jù)分析，已知r1服從正態(tài)分布，可以用正態(tài)分布的逆概率分布求解得到s1

22、。3. 對(duì)下午的分析類似的，我們可以得到注意：下午需要運(yùn)輸?shù)募b箱數(shù)量還包括上午未運(yùn)輸完的集裝箱。6.3模型三的求解用MATLAB求解正態(tài)分布的逆概率分布（源程序見附錄四表1），解得s1=40.3642、s2=37.3822.所以最佳編組方案是上午發(fā)的列車帶41節(jié)型車廂、下午發(fā)的列車帶38節(jié)型車廂。7. 問題四的解答7.1基本思路問題四的鐵路網(wǎng)線編組運(yùn)輸問題是與圖論相關(guān)的優(yōu)化問題，我們參考圖論模型中的dijkstra算法，設(shè)計(jì)模型四。由于集裝箱的運(yùn)費(fèi)按兩個(gè)車站之間的最短鐵路距離計(jì)費(fèi)，首先利用dijkstra算法將A站點(diǎn)到各站點(diǎn)的最短距離求出。出于利潤(rùn)最大化的考慮，我們先假設(shè)：1) 發(fā)出的列車車

23、箱數(shù)達(dá)到最大編組量；2) 每個(gè)車廂中裝滿三個(gè)集裝箱；3) 列車走過的距離先用A站到F站點(diǎn)的最短距離表示。運(yùn)費(fèi)的計(jì)算需要同時(shí)考慮各站點(diǎn)的需求量和A站點(diǎn)到各站點(diǎn)的最短距離。開始時(shí)，鐵路部門運(yùn)到各站點(diǎn)的集裝箱總數(shù)小于總需求量，全部收到了運(yùn)費(fèi)，因此運(yùn)費(fèi)收入成為了定值，且每個(gè)集裝箱的可變成本也固定為元/公里。利用excel軟件計(jì)算出各站點(diǎn)對(duì)應(yīng)的可變成本和運(yùn)費(fèi)收入。由于每次列車發(fā)出的固定成本一定，我們將權(quán)表示的收益定為運(yùn)費(fèi)收入與可變成本之差，利用matlab軟件找到一條收益最大的路線。對(duì)于最后不能將一列火車裝滿的部分，通過比較邊際成本和邊際收益判斷是否發(fā)出列車。由于已經(jīng)確定了路線，應(yīng)計(jì)算出A站點(diǎn)到各站點(diǎn)的

24、實(shí)際距離以及對(duì)應(yīng)的可變成本和收益，找出收益最小的站點(diǎn)。如果該站點(diǎn)的剩余需求量認(rèn)為是進(jìn)行邊際成本和邊際收益判斷的運(yùn)載量；如果需求量小于多出的部分，則尋找收益第二小的點(diǎn)，依次類推。計(jì)算完收益最大的路線后，去掉路線中除去起點(diǎn)和終點(diǎn)的點(diǎn)，再次運(yùn)用程序在剩下的點(diǎn)中計(jì)算收益最大的路線，重復(fù)以上過程，直到只剩下起點(diǎn)和終點(diǎn)，得到最佳的編組運(yùn)輸方案。7.2具體過程7.2.1計(jì)算A站點(diǎn)到各個(gè)站點(diǎn)的最短距離調(diào)用dijkstra算法的源程序見附錄五表1得到A站點(diǎn)到各站點(diǎn)的最短路徑圖，如下圖用excel計(jì)算出在假設(shè)的條件下的相關(guān)數(shù)據(jù)7.2.2確定路線1由于dijkstra算法中是找出權(quán)重的最小值，我們?cè)谑找媲凹由县?fù)號(hào)，

25、修改算法，得到了收益最大的路線，繪圖如下：即第一條路線1-2-5-9-13-14，對(duì)應(yīng)站點(diǎn)為A-B1-C2-D2-E3-F將路線確定下來之后，計(jì)算可變成本時(shí)走過的距離則為A站點(diǎn)到F站點(diǎn)的實(shí)際距離，對(duì)于最后不足放滿一列車廂的部分，將它依次放上收益最小的站點(diǎn)的貨物，計(jì)算邊際成本和邊際收益決定是否發(fā)出這列火車。路線1的集裝箱需求量共316箱，則裝滿兩列火車，剩下的86箱用29個(gè)車廂，相關(guān)計(jì)算結(jié)果如下：邊際成本大于邊際收益，則應(yīng)該開出這列車，故路線1共發(fā)出三列車，兩列為40車廂、一列為29車廂，將路線1上所有站點(diǎn)的需求量都滿足。7.2.3確定路線2對(duì)路線2計(jì)算時(shí)，需要將路線1中出起點(diǎn)和中點(diǎn)之外的點(diǎn)去掉

26、，故修改7.2.2求解的源程序中的B矩陣（見附錄五表3），再次運(yùn)行，得到如下結(jié)果： 則路線2為1-3-5-8-11-14，對(duì)應(yīng)站點(diǎn)為A-B2-C2-D1-E1-F（只是經(jīng)過C2站點(diǎn)，此時(shí)C2站點(diǎn)已經(jīng)沒有需求）。路線2相關(guān)計(jì)算結(jié)果:邊際成本大于邊際收益，則最后一列車不發(fā)出。路線2發(fā)出共一列車，為40個(gè)滿載車廂，將8，11站點(diǎn)的需求量全部滿足，并滿足3站點(diǎn)15箱的需求。7.2.4確定路線3再次修改B矩陣（見附錄五表4），刪去站點(diǎn)3、8、11，進(jìn)行運(yùn)算。得到路線3為1-3-7-10-13-14（3，13只經(jīng)過不卸貨），對(duì)應(yīng)站點(diǎn)A-B2-C4-D3-E3-F。路線3相關(guān)計(jì)算結(jié)果:邊際成本小于邊際收益，

27、所以發(fā)出最后一列車。共發(fā)出兩列車，一列40個(gè)車廂、一列2個(gè)車廂，將7，10兩站點(diǎn)的需求量完全滿足。7.2.5確定路線4和5路線4：1-2-4-8-12-14即A-B1-C1-D1-E2-F發(fā)出一列車，27個(gè)車廂裝八十箱集裝箱，在站點(diǎn)4卸下?？偸杖? 48000總成本：17400路線5：1-3-6-9-12-14即A-B2-C3-D2-E2-F共發(fā)出一列車，滿足站點(diǎn)6，12的需求，即用29節(jié)車廂裝上86箱集裝箱?？偸杖耄?7550總成本：175507.3最佳編組方案路線使用情況表示：次數(shù)（每次車廂數(shù)）路線長(zhǎng)度（公里）收入成本A-B1-C2-D2-E3-F3（40，40,29）8503728001

28、37650A-B2-C2-D1-E1-F1(40)100012460055000A-B2-C4-D3-E3-F2(40,2)90013410067800A-B1-C1-D1-E2-F1(27)8504800037950A-B2-C3-D2-E2-F1(29)85010760039650鐵路部門獲得的總利潤(rùn)為449050元。8.問題五的解答8.1基本思路問題五的基本思路與問題四相似，但在考慮各站點(diǎn)之間的需求量時(shí)，由于集裝箱在各個(gè)站點(diǎn)有裝有卸，使問題比較復(fù)雜。因此我們假設(shè)從A出發(fā)時(shí)，為中途站點(diǎn)所有要裝上的集裝箱留下位置，即同一車廂位置不考慮裝卸集裝箱后的重復(fù)使用，在此假設(shè)下進(jìn)行求解。8.2具體過程

29、8.2.1找到各個(gè)站點(diǎn)之間的最短鐵路距離重復(fù)運(yùn)用dijkstra算法，改變初始點(diǎn)，得到各個(gè)站點(diǎn)之間的最短鐵路距離：8.2.3確定路線1路線1求解源程序與7.2.2相同，所以路線1與問題四中一致，仍為1-2-5-9-13-14。由于有需求量上限限制1-2為57,1-14為56,2-9為71,9-13為4，所以在進(jìn)行完一列車之后，剩余需求114的邊際成本小于邊際收益，所以走兩趟，分別帶40節(jié)車廂和38節(jié)車廂。Execl中如下計(jì)算：8.2.4確定路線2因?yàn)槿コ谝粭l線中各點(diǎn)的影響，對(duì)矩陣B進(jìn)行修改（見附錄六表1），得到結(jié)果如下：路線2：1-3-7-10-13-14因?yàn)榧s束1-14為0（路線1全部滿足

30、），1-13為44,3-13為49，所以13約束為44，因?yàn)檫呺H收益大于邊際成本，所以開兩趟車，分別帶40、30節(jié)車廂。8.2.5確定路線3再次修改矩陣B（見附錄六表2），得到結(jié)果如下： 得到路線3：1-2-4-8-12-14結(jié)合前兩次的相減，約束為1-2為0,1-4為10,1-8為96,4-8為30，運(yùn)輸量共102，且收益大于成本。所以發(fā)出一列車，帶34節(jié)車廂。8.2.6確定路線4修改B矩陣后（見附錄六表3），結(jié)果如下：所以路線4：1-2-4-8-11-14因?yàn)闂l件約束，2,4，8，14點(diǎn)都為0，且11點(diǎn)有約束4-11為68，因?yàn)檫呺H收益大于邊際成本，所以應(yīng)開一列車，帶23列車廂。8.2.7

31、確定路線5修改B矩陣后（見附錄六表4），結(jié)果如下：線路5：1-2-4-9-13-14，此時(shí)2,4,9,13,14的需求已被滿足，線路無意義。8.3最佳編組方案表五 路線1-2-5-9-13-141-3-7-10-13-141-2-4-8-12-141-2-4-8-11-14次數(shù)（每次車廂數(shù)）2（40,38）2（40,38）1（34）1（23）9. 模型的評(píng)價(jià)、改進(jìn)與推廣9.1模型的評(píng)價(jià)1.模型優(yōu)點(diǎn)1) 運(yùn)用的算法簡(jiǎn)單易懂，且減少了計(jì)算機(jī)的計(jì)算負(fù)荷；2) 與有效前沿、dijkstra算法等進(jìn)行類比，舉一反三。2.模型缺點(diǎn):1) 對(duì)于可行的貨運(yùn)方案的確定時(shí)，只考慮了其中部分情況，忽略了貨物可以直立

32、放置的情況；2) 問題三中上午的數(shù)據(jù)雖然服從正態(tài)分布，但接受概率很低，對(duì)計(jì)算的結(jié)果帶來了誤差；3) 沒能很好地把每列車的剩余部分進(jìn)行很好地規(guī)劃，造成了運(yùn)輸空間的浪費(fèi)；4) 在計(jì)算的起始直接將最近距離看作實(shí)際距離進(jìn)行運(yùn)算，給結(jié)果帶來了一定的誤差；5) 將站點(diǎn)通過機(jī)械粗糙的路線劃分進(jìn)行了區(qū)別，直接排除了多次經(jīng)過一個(gè)站點(diǎn)的復(fù)雜情況，與實(shí)際情況不符，降低了模型的可用范圍。9.2模型的改進(jìn)對(duì)問題三中，收集更多數(shù)據(jù)，進(jìn)行更細(xì)致的擬合，得到更準(zhǔn)確的模型。9.3模型的推廣對(duì)于有效前沿的應(yīng)用，可以更廣泛地使用于雙目標(biāo)優(yōu)化問題。參考文獻(xiàn)1 王建偉-smile，數(shù)學(xué)建模-多目標(biāo)規(guī)劃2 張宗新，投資學(xué)（第二版），上海

33、：復(fù)旦大學(xué)出版社，20093 姜啟源，謝金星，葉俊，數(shù)學(xué)模型（第四版），北京：高等教育出版社，2011附錄附錄一：題目所給數(shù)據(jù)表1：貨物包裝箱相關(guān)參數(shù)貨物類型長(zhǎng)度（米）寬度（米）高度（米）重量（噸）數(shù)量A2.8131.325.57B2.221.51.3510.56C1.7130.995D2.6231.187E2.5331.27.56表2：火車車廂相關(guān)參數(shù)車廂類型長(zhǎng)度(米)寬度下層高度上層高度載重量（噸）型12.532.555型1531.41.370表3：近100天上午集裝箱數(shù)量：149 100106 13297 10297 123124 97103 130146 144108 110106 1

34、33144 99128 98133 10195 100144 111103 106125 105112 150105 14494 122148 137103 140121 146148 132120 115117 10393 128127 137100 121149 126130 14493 11795 91122 125120 13598 91134 107143 143146 115109 139107 97111 141149 112101 111131 140144 13095 108139 142117 115122 136129 90近100天下午集裝箱數(shù)量：128 137115

35、106133 5693 95 113 66155 10589 108131 10798 122 102 102104 109106 97 105 8786 125124 16573 82121 82 119 6186 11362 11673 8783 136102 75106 93 124 97121 119103 12168 84108 11192 88113 8578 11290 80116 75 107 8892 125111 91 99 11398 11092 8075 10185 98 69 61103 85 112 128101 10290 82 111 118128 88 85

36、47表4：鐵路網(wǎng)線說明鐵路網(wǎng)上火車站點(diǎn)名稱表：編號(hào)火車站點(diǎn)名稱X坐標(biāo)（單位km）Y坐標(biāo)（單位km）1A002B1111.1141.13B20.00-111.14C1157.9142.55C2228.455.96C3220.7-28.67C4148.1-191.48D1342.974.19D2363.7-5.610D3329.7-107.611E1429.8108.112E2410.75.713E3442.9-38.614F519.60站點(diǎn)之間的鐵路連結(jié)表（直接連接不通過其它站點(diǎn)）：注意：鐵路線路為單向行駛，即火車只能從起點(diǎn)至終點(diǎn)，不能從終點(diǎn)至起點(diǎn)編號(hào)鐵路線起點(diǎn)站點(diǎn)鐵路線終點(diǎn)站點(diǎn)鐵路線長(zhǎng)度，即鐵

37、路距離(km)1AB12502AB21503B1C1504B1C21505B1C33006B2C24007B2C33508B2C43009C1D130010C1D240011C2D115012C2D225013C3D215014C3D315015C4D240016C4D320017D1E110018D1E210019D2E25020D2E310021D3E215022D3E315023E1F20024E2F15025E3F100表5：各地集裝箱運(yùn)輸需求量（件）B1B2C1C2C3C4D1D2E1E2E3F583980541471826323726972表6：各地集裝箱運(yùn)輸需求量（件）起點(diǎn)站AA

38、AD2B1D3C2C1C4D1B2A終點(diǎn)站C1E3D1E3D2E2E1E1E3FFC3運(yùn)輸量10449647132196834221522起點(diǎn)站AC3C1D1A C1B2B2B2終點(diǎn)站FD2D1E2B1E3E1E2E3運(yùn)輸量562830895793995749附錄二：?jiǎn)栴}一相關(guān)信息表：MATLAB編程確定兩種車廂可行的貨物裝載方式的源程序?qū)τ谛蛙噹╬roblem1-1.m）p=;a11=0for a11=0:7;%aij中i表示貨物ABCDE，j表示層數(shù) for a21=0:6; for a31=0:5; for a41=0:7; for a51=0:6; if a21=0; %對(duì)B進(jìn)行分類

39、 l1=a11*2.81+a31*1.71+a41*2.62+a51*2.53; end if a21=1,3,5; l1=a11*2.81+(a21-1)*1.11+1.5+a31*1.71+a41*2.62+a51*2.53; end if a21=2,4,6; l1=a11*2.81+a21*1/2*2.22+a31*1.71+a41*2.62+a51*2.53; end w1=a11*5.5+a21*10.5+a31*9+a41*8+a51*7.5; %計(jì)算車廂載重 if l1<=12.5 & w1<=55 &(12.5-l1)<=1.5; p=p;a

40、11 a21 a31 a41 a51 a11+a21+a31+a41+a51 w1; end end end end endendP對(duì)于型車廂（problem1-2.m）p=;a11=0;for a11=0:5;%aij中i表示貨物ABCDE，j表示層數(shù) for a21=0:6; for a31=0:7; for a41=0:5; for a51=0:5; if a21=0; %對(duì)B進(jìn)行分類 l1=a11*2.81+a31*1.71+a41*2.62+a51*2.53; end if a21=1,3,5; l1=a11*2.81+(a21-1)*1.11+1.5+a31*1.71+a41*2.

41、62+a51*2.53; end if a21=2,4,6; l1=a11*2.81+a21*1/2*2.22+a31*1.71+a41*2.62+a51*2.53; end if l1<15&(15-l1)<=0.2; for a32=0:7; for a42=0:5; for a52=0:5; l2=1.71*a32+2.62*a42+2.53*a52; w2=5.5*a11+10.5*a21+9*(a31+a32)+8*(a41+a42)+7.5*(a51+a52); if l2<=15&w2<=70;p=p;a11 a21 a31 a41 a51 a32 a42 a52 a11+a21+a31+a41+a51+a32+a42+a52 w2; end end end end end end end end endendp表2：兩種車廂可行的貨物裝載方式型車廂編號(hào)ABCDE運(yùn)輸數(shù)量運(yùn)輸總重100104539200113539.530012