2014年全國研究生數(shù)學建模競賽一等獎論文(E題)

1、參賽密碼（由組委會填寫）第十一屆華為杯全國研究生數(shù)學建模競賽學校西安理工大學參賽隊號107000021.柯俊山隊員姓名 2.朱文奇3.胡凱參賽密碼（由組委會填寫）第十一屆華為杯全國研究生數(shù)學建模競賽題 目乘用車物流運輸計劃問題摘要：本文主要解決的是乘用車整車物流的運輸調(diào)度問題，通過對轎運車的空間 利用率和運輸成本進行優(yōu)化，建立整數(shù)規(guī)劃模型，設計了啟發(fā)式算法，求解出 了各種運輸條件下的詳細裝載與運輸方案。針對前三問，由于不考慮目的地和轎運車的路徑選擇，將問題抽象為帶裝 載組合約束的一維裝車問題，優(yōu)化目標是在保證完成運輸任務的前提下盡可能 滿載，選擇最優(yōu)裝載組合方案使得所使用的轎運車數(shù)量最少。對于

2、滿載的條件， 將其簡化為考慮轎運車的空間利用率最大，最終建立了空間利用率最大化和運 輸成本最小化的兩階段裝載優(yōu)化模型。該模型類似于雙目標規(guī)劃模型，很難求 解。為此，將空間利用率最大轉(zhuǎn)換為長度余量最少，并為其設定一個經(jīng)驗閾值， 將問題轉(zhuǎn)換為求解整數(shù)規(guī)劃問題，利用分支定界法進行求解。由于分支定界法 有時并不能求得最優(yōu)解，設計了一種基于閾值的啟發(fā)式調(diào)整優(yōu)化算法。最后， 設計了求解該類問題的通用算法程序，并對前三問的具體問題進行了求解和驗 證。通過求解得出，滿足前三問運輸任務的 1-1 型轎運車和 1-2 型轎運車數(shù)量 如下表所示（具體的乘用車裝載方案見表 2、表 5、表 7）：第一問第二問第三問1-

3、1 16 12 251-2 2 1 5針對問題四，其是在問題一的基礎上加入了整車目的地的條件，需要考慮 最優(yōu)路徑的選擇。在運輸成本上，加入了行駛里程成本，因而可以建立所使用 的轎運車數(shù)量最少和總里程最少的雙目標整數(shù)規(guī)劃模型。對于此種模型，可以 采用前三問所設計的通用算法進行求解。此時，需要重新設計啟發(fā)式調(diào)整優(yōu)化 算法。為此，根據(jù)路線距離的遠近和轎運車數(shù)量需要滿足的比例約束條件設計 了新的調(diào)整優(yōu)化方案。最終求得的各目的地的轎運車使用數(shù)量如下表所示，此時的總路程為 6404，具體裝載方案見表 9。1-1 型1-2 型總量a145b606c909d505總數(shù)21425針對問題五，作為問題四的擴展研究

4、，類似于問題四建立了雙目標規(guī)劃模 型。由于乘用車的種類達到了 45 種，導致轎運車的裝載組合方案急劇增多。如 果仍采用窮舉法確定裝載組合方案，將產(chǎn)生“組合爆炸”。為此，采用基于排 樣算法的裝載優(yōu)化算法，來避免這種現(xiàn)象。這種算法的基本流程是：首先按照 乘用車的寬、高將乘用車分為“高”、“低窄”、“低寬”三種車型； 然后根 據(jù)不同類型的乘用車在不同目的地的需求量，構(gòu)建關系樹；接著根據(jù)關系樹和 啟發(fā)式調(diào)整優(yōu)化算法來確立初步配載方案；最后驗證配載方案是否滿足約束條 件以求得最終方案。其中，啟發(fā)式調(diào)整優(yōu)化算法仍然是基于經(jīng)驗的，這里主要 考慮轎運車上層空間的利用率最大化和距離較遠的點以盡可能地減少轎運車的

5、 數(shù)量，同時也要滿足不同轎運車型之間的數(shù)量比例約束。最終求得的各目的地 轎運車的詳細使用量如下表所示，并且完成運輸任務所需行駛的總里程為 35140。序號12345678910目的地總量 轎運車總量目的地 a00111220005434目的地 b1470000010325目的地 c7003004150029118目的地 d0100000000111目的地 e0011080000019余量0100025000127關鍵詞：整車物流 整數(shù)規(guī)劃 分支定界法 經(jīng)驗閾值 啟發(fā)式調(diào)整優(yōu)化 排樣算法一、 問題重述1.1 問題背景整車物流指的是按照客戶訂單對整車快速配送的全過程。隨著我國汽車工 業(yè)的高速發(fā)展，

6、整車物流量，特別是乘用車的整車物流量迅速增長。乘用車生產(chǎn)廠家根據(jù)全國客戶的購車訂單，向物流公司下達運輸乘用車到 全國各地的任務，物流公司則根據(jù)下達的任務制定運輸計劃并配送這批乘用車。 為此，物流公司首先要從他們當時可以調(diào)用的“轎運車”中選擇出若干輛轎運 車，進而給出其中每一輛轎運車上乘用車的裝載方案和目的地，以保證運輸任 務的完成。“轎運車”是通過公路來運輸乘用車整車的專用運輸車，根據(jù)型號 的不同有單層和雙層兩種類型，而單層轎運車實際中很少使用，本題僅考慮雙 層轎運車。在確保完成運輸任務的前提下，物流公司追求降低運輸成本。但由于轎運 車、乘用車有多種規(guī)格等原因，當前很多物流公司在制定運輸計劃時

7、主要依賴 調(diào)度人員的經(jīng)驗，在面對復雜的運輸任務時，往往效率低下，而且運輸成本不 盡理想。1.2 已知信息（1） 每種轎運車上、下層裝載區(qū)域均可等價看成長方形，各列乘用車均縱 向擺放，相鄰乘用車之間縱向及橫向的安全車距均至少為 0.1 米，下層力爭裝 滿，上層兩列力求對稱，以保證轎運車行駛平穩(wěn)。（2） 1-1 型及 2-2 型轎運車上、下層裝載區(qū)域相同；第五問中 1-2 型轎運 車上、下層裝載區(qū)域長度相同，但上層比下層寬 0.8 米。（3） 受層高限制，高度超過 1.7 米的乘用車只能裝在 1-1、1-2 型下層，2-2 型上、下層均不能裝載高度超過 1.7 米的乘用車。（4） 在轎運車使用數(shù)量

8、相同情況下，1-1 型轎運車的使用成本較低，2-2 型 較高，1-2 型略低于前兩者的平均值，但物流公司 1-2 型轎運車擁有量小，為 方便后續(xù)任務安排，每次 1-2 型轎運車使用量不超過 1-1 型轎運車使用量的 20%。（5） 在轎運車使用數(shù)量及型號均相同情況下，行駛里程短的成本低。 1.3 需要解決的問題請為物流公司安排以下五次運輸，制定詳細計劃，含所需要各種類型轎運 車的數(shù)量、每輛轎運車的乘用車裝載方案、行車路線。（前三問目的地只有一個， 可提供一個通用程序；后兩問也要給出啟發(fā)式算法的程序，優(yōu)化模型則更佳）：（1）物流公司要運輸車型的乘用車 100 輛及車型的乘用車 68 輛。 （2）

9、物流公司要運輸車型的乘用車 72 輛及車型的乘用車 52 輛。 （3）物流公司要運輸車型的乘用車 156 輛、車型的乘用車 102 輛及車型的乘用車 39 輛。（4） 物流公司要運輸 166 輛車型的乘用車（其中目的地是 a、b、c、d 的分別為 42、50、33、41 輛）和 78 輛車型的乘用車（其中目的地是 a、c 的 分別為 31、47 輛）。（5） 根據(jù)附件表 1 給出的物流公司需要運輸?shù)某擞密囶愋停ê蛱?)、尺 寸大小、數(shù)量和目的地和附件表 2 給出的可以調(diào)用的轎運車類型（含序號)、數(shù) 量和裝載區(qū)域大小，采用啟發(fā)式算法，求解裝載、運輸方案，并自行設計運輸 方案的表達形式。(1)(

10、2)(3)(4)(5)二、 模型假設每輛轎運車裝載乘用車的組合是獨立的；轎運車裝載乘用車時上下層部分是對稱的，即數(shù)量一致； 轎運車到達目的地后原地待命，無須放空返回；轎運車在運輸過程中不存在往返情況；每次卸車成本可以忽略不計。三、 基本符號說明符號v_ncvjkxivjyvjcijnjpkbjk符號說明第 v 輛車的裝載組合數(shù)第 v 輛車第 j 個裝載組合裝載第 k 種類型物品的容量物品 i 裝載在車輛 v 的第 j 個裝載組合車輛 v 選擇第 j 個裝載組合第 i 種裝載組合方案能承載第 j 種乘用車的數(shù)目需要裝載的第 j 種乘用車的數(shù)量o 到 a、b、c、d、e 的距離第 j 種乘用車運往

11、第 k 個目的地的數(shù)量符號lljcxirtsyik符號說明轎運車的長度第 j 種乘用車的長度安全距離第 i 種方案的使用數(shù)量長度余量經(jīng)驗閾值轎運車的總路程第 i 種方案去第 k 個目的地四、 問題分析本文研究的是乘用車物流運輸計劃問題，通過對轎運車的空間利用率和運 輸成本進行優(yōu)化，設計啟發(fā)式算法，以求解各種運輸條件下詳細的裝載與運輸 方案，能夠使得轎運車的利用率達到最高、運輸成本達到最低、行車路線最優(yōu)。 針對題中的五個問題，分析如下：4.1 問題一分析題目要求給出運輸車型的乘用車 100 輛及車型的乘用車 68 輛時物流公 司的運輸方案。本問題即將給定數(shù)量的車型和車型乘用車裝載到 1-1 型轎

12、 運車和 1-2 型轎運車上，并使得所用的 1-1 型轎運車和 1-2 型轎運車數(shù)量之和 最少，亦即成本最少。并在滿足數(shù)量最少的情況下，求解車型和車型乘用 車的最佳裝載組合方案，以使得兩種轎運車空間利用率達到最大。由于兩種乘 用車的高度均不超過 1.7 米，且其寬度小于轎運車的下層寬度、兩倍寬度也不 超過轎運車的上層寬度，即車型和車型乘用車可以裝載在 1-1 型和 1-2 型 轎運車的任意層上。所以，問題可以歸結(jié)為一維組合裝車問題，求解的目標是 充分利用轎運車的長度，以使得轎運車的長度余量最少，則轎運車的空間利用率也將達到最大。4.2 問題二分析題目要求給出運輸車型的乘用車 72 輛及車型的乘

13、用車 52 輛時物流公 司的運輸方案。本問題即將給定數(shù)量的車型和車型乘用車裝載到 1-1 型轎 運車和 1-2 型轎運車上，并使得所用的 1-1 型轎運車和 1-2 型轎運車數(shù)量之和 最少，亦即成本最少。并在滿足數(shù)量最少的情況下，求解車型和車型乘用 車的最佳裝載組合方案，以使得兩種轎運車空間利用率達到最大。由于車型 乘用車的高度大于 1.7 米，根據(jù)題目中的要求，只能將其裝載在 1-1 型和 1-2 型轎運車的下層上。而車型的乘用車，仍然可以裝載在 1-1 型和 1-2 型轎運 車的任意層。問題仍為求解一維組合裝車問題，求解的目標是充分利用轎運車 的長度，以使得轎運車的長度余量最少。4.3 問

14、題三分析題目要求給出運輸車型的乘用車 156 輛、車型的乘用車 102 輛及車 型的乘用車 39 輛時物流公司的運輸方案。本問題即將給定數(shù)量的車型、車 型和車型乘用車裝載到 1-1 型轎運車和 1-2 型轎運車上，并使得所用的 1-1 型轎運車和 1-2 型轎運車數(shù)量之和最少，亦即成本最少。并在滿足數(shù)量最少的 情況下，求解車型、車型和車型乘用車的最佳裝載組合方案，以使得兩 種轎運車空間利用率達到最大。此問題可以看作是前兩問的延伸，此時 1-1 型 轎運車和 1-2 型轎運車下層均可以裝載三種乘用車，而上層只能裝載車型和 車型轎運車。4.4 問題四分析題目要求給出運輸 166 輛車型的乘用車（其

15、中目的地是 a、b、c、d 的分 別為 42、50、33、41 輛）和 78 輛車型的乘用車（其中目的地是 a、c 的分別 為 31、47 輛）時物流公司的運輸方案。本問題可以看作是問題一的延伸，在問 題一的基礎上將路徑加入到了考慮之列，目的地不再相同。問題變成將給定數(shù) 量的車型和車型乘用車裝載到 1-1 型轎運車和 1-2 型轎運車上，并運往相 應的目的地，以滿足各目的地的需求，使得運輸成本最少。而影響運輸成本的 首要因素是轎運車使用數(shù)量，其次是行駛里程長短。因而問題轉(zhuǎn)換為求解車 型和車型乘用車的最佳裝載組合方案，以使得兩種轎運車的使用總數(shù)量最小 且所需的路程最短。這是一個雙目標規(guī)劃問題，此

16、時轎運車有可能不再滿足滿 載的條件。4.5 問題五分析題目要求利用 10 種不同規(guī)格轎運車，來裝載 45 種不同規(guī)格的乘用車，以 滿足 a、b、c、d、e 五個目的地對 45 種乘用車的數(shù)量需求。本問題可以看作是 問題四的擴展研究，只是問題比第四問要復雜的多，但整體的模型是一致的。 對于這種 np難問題，尋找最優(yōu)解是不切實際的，需要重新設計啟發(fā)式算法， 簡化目標函數(shù)，使其更容易求解，以期能夠求得滿足約束條件的可行解。五、 問題求解與算法設計5.1 裝載問題的基本模型5.1.1 模型定性分析w v _ nm-在不考慮整車目的地和轎運車的路徑選擇的情況下，問題可抽象為帶裝載組合約束的一維裝車問題1

17、，即有 n 個屬于 l 種類型的相同（單位）尺寸的物品，有 w 輛車，每輛車對這 l 種類型的物品有幾種裝載組合，不同車輛的裝載 組合不同，每輛車選擇一種裝載組合并嚴格按照物品組合進行裝載。優(yōu)化目標 是在滿載的情況下裝載最多的物品，同時給出每個物品的具體配載方案。 5.1.2 復雜性分析考慮帶裝載組合約束的一維裝車問題的簡化問題，當每輛車只有一個裝載 組合時，問題變?yōu)椋河?l 種類型的物品，類型 k 的物品數(shù) n ，有 n 個裝載組合，k第 j 個裝載組合對類型 k 物品的容量 c ，對所有類型物品的容量 c ，選擇裝載jk j組合以盡可能裝載最多的物品。已知多維背包問題為 np難問題2，而多

18、維背 包問題可以轉(zhuǎn)化為一維組合裝車問題的簡化問題，則一維組合裝車問題的簡化 問題為 np難問題，顯然一維組合裝車問題更為復雜，也即一維組合裝車問題 為 np難問題。5.1.3 一維組合裝車問題線性混合整數(shù)規(guī)劃模型 3問題最終結(jié)果是給出具體的裝載方案，即物品裝載在哪輛車的哪個裝載組 合上，因此以物品作為決策主體，物品選擇車輛、裝載組合。設物品數(shù)為 m,類型數(shù)為 l，車輛數(shù)為 w，第 v 輛車的裝載組合數(shù)為 v_n，第 v 輛車第 j 個裝載組合裝載第 k 種類型物品的容量為 c , x 為物品 i 是否裝載vjk ivj在車輛 v 的第 j 個裝載組合上的 0、1 變量，y 為車輛 v 是否選擇

19、第 j 個裝載組vj合的 0、1 變量，則有如下數(shù)學模型：maxm w v _ n xivj(5-1)v_ nj =1i =1 v =1 j =1y 1, v =1,2, l , w vjx 1, i =1,2, l , mivjv =1 j =1s.t .x =c y , if m =kivj vjk vj ii=1k =1,2, l , l; v =1,2 l , w; j =1,2 l , v nx 0,1 i =1,2, l , m, v =1,2, l , w, j =1,2, l , v n ivj -y 0,1 v =1,2, l , w, j =1,2, l , v n vj

20、-優(yōu)化目標為物品裝載數(shù)最多；約束式第一式表示一輛車最多只能選擇一種 裝載組合；第二式表示一個物品最多只能被裝載到一輛車的某個裝載組合上； 第三式表示每輛車必須嚴格按照裝載組合裝滿每種類型的物品；第四、五式定 義了變量的取值范圍。5.2 兩階段裝載優(yōu)化模型的建立5.2.1 實際問題的分析與簡化在本問題中，有三種類型的乘用車，其數(shù)量根據(jù)具體的運輸任務而定，每 種車的規(guī)格均不同。轎運車也有兩種，其規(guī)格也有較大差異。現(xiàn)要考慮將給定 數(shù)量的三種類型的乘用車裝載到兩種類型的較運車上，但轎運車的數(shù)量可以無3限多。為了在保證完成運輸任務的前提下，降低整車物流的運輸成本，目標函 數(shù)變?yōu)樵跐M足滿載的情況下，選擇最

21、優(yōu)裝載組合方案，使得所使用的轎運車數(shù) 量最少。而滿載的條件在本問題中不再適用，我們簡化為考慮轎運車的空間利 用率最大，為此，建立了兩階段裝載優(yōu)化模型4。5.2.2 裝載組合方案的確定在給定運輸任務的乘用車類型后，根據(jù)各乘用車的規(guī)格和各裝載用轎運車 的規(guī)格，首先確定 1-1 型和 1-2 型轎運車每層可以裝載的乘用車類型，然后依 據(jù) 1-1 型和 1-2 型轎運車的實際長度，再加上縱向的安全車距的限制，采用窮 舉法，可以確立各類型轎運車的所有裝載組合。假定轎運車的長度為 l，第 j 種乘用車的長度為 l （j = 1, 2, 3分別代表j型、型、型），并用 k 表示裝載組合中承載的第 j 種乘用

22、車的數(shù)目，安全j距離 c=0.1，滿足要求的裝載組合方案應滿足（只考慮單個下層的情況，其它 層類似）：3(k -1) c+k l l, j j jj =1k l / min(l , l , l ) j 1 2 3 j=1（5-2）5.2.3 兩階段裝載優(yōu)化模型（1）第一階段：空間利用率最大化優(yōu)化模型a）目標函數(shù)的確定考慮到無論是使用 1-1 型轎運車還是 1-2 型轎運車，均采用雙層裝載。而 且為了安全，下層裝載的是重心高度較高的乘用車，如車型乘用車。再者， 車型和車型乘用車的寬度均在轎運車的允許范圍之內(nèi)。因此，轎運車在裝 載乘用車時，在高度和寬度上并不存在利用的概念，在最大化空間利用率時僅

23、需考慮長度的充分利用即可，而具體裝載輛數(shù)取決于乘用車的類型。設 c 表示第 i 種裝載組合方案能承載第 j 種乘用車的數(shù)目（i = 1, 2， , i，jm, m+1, , m，m 為使用 1-1 型轎運車的最大方案數(shù)，m 為分別使用 1-1 型、 1-2 型轎運車的總方案數(shù)之和；j = 1, 2, 3, 4, 5, 分別表示上（型車放 在上層，后面依次類推）、上、下、下、下五種情況），n 表示轎運車 的列數(shù)（1-1 型為 2, 1-2 型為 3, 2-2 型為 4），則目標函數(shù)可以表示為：max f =(c l +ci ,1 1i ,2l +c l +c 2 i ,3 1i ,4l +c l

24、 + 2 i ,5 35(ci , j-1) c) /( n l) （5-3）j =1b）約束條件的確定轎運車裝載時，應保證乘用車與乘用車之間，乘用車與轎運車端壁之間的 最小間隙, 避免發(fā)生碰撞，此安全距離為 0.1 米，同時應滿足轎運車的裝載長 度約束。即，滿足的約束條件如下：j =1j =15 5mmmmii2 2c l + (c -1) cl i , j j i , js.t .c l +(c -1) cl i , j j i , jj=3 j =3（2）第二階段：運輸成本最小化優(yōu)化模型a）目標函數(shù)的確定（5-4）由于影響整車物流運輸成本高低的主要因素首先是轎運車使用數(shù)量，其次 是在轎運

25、車使用數(shù)量相同情況下的轎運車使用成本，最后是行駛里程成本。而 在前三問的模型中，不考慮路徑問題，因而我們以轎運車的使用數(shù)量最少為主 要考慮因素，對組合方案進行優(yōu)化，以使運輸成本最小。設第 i 種方案的使用數(shù)量為 x (i = 1, 2， , m, m+1, , m)，則目標i函數(shù)為：mmin f = xi =1i（5-5）b）約束條件的確定由于 1-1 型轎運車的使用成本較低，2-2 型較高，1-2 型略低于前兩者的平 均值。為了降低成本，應使 1-2 型轎運車使用量少于 1-1 型轎運車，且每次 1-2 型轎運車使用量不超過 1-1 型轎運車使用量的 20%，這也符合物流公司 1-2 型 轎

26、運車擁有量小的實際；再者，無論采用哪些組合方案，都必須滿足物流公司 的運輸安排，努力完成任務。即，滿足的約束條件如下： m j=m+1x 0.2x ,j ii =1(c +c ) x =n ,i ,1 i ,3 i 1i =1s.t .(c +c ) x =n ,i ,2 i ,4 i 2i=1c x =n ,i ,5 i 3i =1x 0, x z其中，n 為需要裝載的第 j 種乘用車的數(shù)量。 j5.2.4 基于經(jīng)驗閾值的求解優(yōu)化方法（5-6）考慮到在求解上述兩階段裝載優(yōu)化模型時，問題歸結(jié)為一個雙目標規(guī)劃問 題，實際求解時較為困難。為此，對問題進行重新分析，空間利用率最大可以 等價為長度余量

27、最少，而組合方案的求解時也可以通過考慮長度余量來進行分 析。設長度余量為 r，則r =n l -c l +ci ,1 1i ,2l +c l +c 2 i ,3 1i ,45l +c l + (c 2 i ,5 3i , j-1) c（5-7）j =1根據(jù)實際情況，r 應滿足非負的要求。mmmmiii由于每種方案的長度余量不同，但對于每種類型的轎運車的所有裝載組合 方案，其長度余量必有一個取值范圍，我們可以考慮人為的給定一個閾值。這 樣可以對組合方案進行有目的的篩選，也可以解決因窮舉法產(chǎn)生的“組合爆 炸”問題，同時也考慮了空間利用率最大。因而，求解兩階段裝載優(yōu)化問題最 終歸結(jié)為一個整數(shù)規(guī)劃問題

28、mmin f = xi =1i（5-8） m j=m+1x 0.2x ,j ii =1(c +c ) x =n ,i ,1 i ,3 i 1i =1s.t .(c +c ) x =n ,i ,2 i ,4 i 2i =1c x =n ,i ,5 i 3i =1x 0, x z0 r t其中，t 為閾值，根據(jù)經(jīng)驗獲得，在本文的計算中，t 取 2。5.3 裝載優(yōu)化模型的通用求解算法設計5.3.1 求解整數(shù)規(guī)劃的分支定界算法分支定界算法是一種隱枚舉法,是整數(shù)規(guī)劃中常用的算法之一5。它的主要 思想是根據(jù)某種策略將原問題松弛問題的可行域分解為越來越小的子域 , 并檢 查每個子域內(nèi)整數(shù)解的情況, 直到找到

29、最優(yōu)整數(shù)解或證明整數(shù)解不存在。分支定界法從求松弛問題開始 , 將問題可行域分為許多的子域 (最通常的 分解方式是“兩分法”),這一過程稱為分支；通過分支找到更好的整數(shù)解來不 斷的修改問題的上下解 ,這一過程稱為定界。定界的目的是為了測定界的趨勢 , 留下有價值的或尚不能判定的分支。刪除肯定不存在最優(yōu)解的分支 , 稱之為剪 枝, 以達到加速收斂 , 簡化運算的目的。不同的分支定界方法在于分支、定界 和剪枝的不同處理手段上, 其算法的一般步驟可概括為：step1：初始化。選擇可行域的 s 的初始松弛集合 f，滿足 f s ；初始可行點集合 q =j，上界 a=+，令 p=f，計算下界 b( f )

30、 min f ( x ), x s ，并令 b=b(f ) 。在計算 b( f ) 的過程中，若有必要，則更新 q 和 a 。step2：分割。將 f 分割成有限個子集 f ， i i （指標集）滿足if =uf , int f iint f =, i , j i , i j ，令 p =( p f )u(uf ) 。i i j iililbstep3：剪枝。對每個 i i ，計算 f 在子集 f 上的下界 b( f ) ，使其滿足i( f ) int f ( f us ) ，利用在計算 b( f ) ) 的過程中所發(fā)現(xiàn)的所有可行點修正集 i i i合 q，同時按照合適的刪除規(guī)則，刪除 p 中

31、所有不包含最優(yōu)解的 f 或 f 的一部i i分，剩余集合不妨仍記為 p；step4：定界。令 b =min b( f ) | f p， a =min f ( x) | x q。istep5：終止判斷。若 a-be（充分小的正數(shù)），則終止算法。否則，從 p 中挑選合適的子集 f， f p ，轉(zhuǎn)入步驟 2。5.3.2 啟發(fā)式調(diào)整優(yōu)化啟發(fā)式算法 3是一種基于直觀或經(jīng)驗構(gòu)造的算法 ,在可接受的花費 (指計算 時間和空間)下給出待解決組合優(yōu)化問題每一個實例的一個可行解 ,該可行解與 最優(yōu)解的偏離程度不一定事先可以預計。利用分支定界法求解整數(shù)規(guī)劃問題（5-8）所得的解有時并不是最優(yōu)解，此 時就需要進行調(diào)整

32、，這時只需要在保證轎運車總數(shù)量不變的情況下，對可行解 進行啟發(fā)式的局部調(diào)整即可。這種啟發(fā)式的調(diào)整思路大致如下：（1） 放寬閾值 t，擴大解的范圍；（2） 根據(jù)經(jīng)驗，將新解范圍中的某一種方案的數(shù)量與可行解相應的方案 數(shù)量進行替換；（3） 驗證新的解是否滿足約束條件，如果新解滿足約束條件且新解的轎 運車數(shù)量總數(shù)不超過可行解，則新解即為可能的最優(yōu)解；（4） 在這些所有可能的最優(yōu)解中，尋找轎運車數(shù)目最少的即為最優(yōu)解。 啟發(fā)式算法簡單直觀，速度快，容易被接受，但在最壞情況下，也不能獲得最優(yōu)解，這時就只能通過人工干預進行調(diào)整，以獲得最優(yōu)解。5.3.3 通用算法設計開始輸入轎運車與乘用車規(guī)格輸入需要運輸?shù)某?/p>

33、用車數(shù)量計算轎運車裝載方案啟發(fā)式調(diào)整 優(yōu)化可行解分支定界法求 解線性規(guī)劃整數(shù)問題最優(yōu)解yn人工干預，調(diào)整裝載方案n最優(yōu)解y輸出裝載方案與 所需轎運車數(shù)量結(jié)束圖 1 通用算法流程圖本文通過前三問的求解，歸納總結(jié)出了一種適合求解前三問的通用算法， 并用一個通用程序進行了實現(xiàn)。所實現(xiàn)的通用程序，能夠滿足前三問運輸任務， 并能按照題目要求輸入輸出最優(yōu)解。算法的流程圖如圖 1 所示，這里，簡單敘 述一下通用算法的主要步驟：step1：分別輸入轎運車與乘用車的規(guī)格數(shù)據(jù)（長、寬、高），并輸入需要 運輸?shù)娜N乘用車的數(shù)量，如果沒有某種乘用車，則輸入 0；step2：通過（5-2）式來計算所有可能的轎運車裝載方

34、案，并進行編號； step3：利用分支定界法求解式（ 5-8）所示的整數(shù)規(guī)劃問題，并對所求得的解進行驗證，如果求得的解就是最優(yōu)解，則轉(zhuǎn)到 step6；否則繼續(xù)； step4：按照上節(jié)所述的啟發(fā)式調(diào)整優(yōu)化方法繼續(xù)求解優(yōu)化，尋找最優(yōu)解，并對所求得的解進行驗證，如果所得的解即是最優(yōu)解，則轉(zhuǎn)到 step6；否則繼 續(xù)；step5：對上步所得的可行解進行人工干預，局部小范圍調(diào)整方案，以獲得 最優(yōu)解；step6：按照題目要求輸出裝載方案與所需轎運車數(shù)量的 excel 格式。 5.4 問題一求解本問題中，n =100，n =68，n =0，帶入式（5-8）中，可得問題一的具體模1 2 3mm型為：mmin

35、f = xi =1i（5-9） m j=m+1x 0.2x ,j ii =1i=1s.t .m i=1(c +c ) x =100, i ,1 i ,3 i(c +c ) x =68, i ,2 i ,4 ix 0, x z i i0 r 2將 n =100，n =68，n =0 輸入到通用程序中，可以求得 11 種裝載組合方案， 1 2 3如表 1 所示，其中前 5 種為使用 1-1 型轎運車時的所有可能裝載組合方案，后 6 種為使用 1-2 型轎運車時的所有可能裝載組合方案。表 1 問題一的所有可能裝載組合方案方方方方方方方方方方方方數(shù)案案案案案案案案案案案案目1 2 3 4 5 6 7

36、8 9 10 11上層裝載型乘用車數(shù)目432101086420上層裝載型乘用車數(shù)目01235024810 12下層裝載型乘用車數(shù)目 下層裝載型乘用車數(shù)目4031221305504132241506最終求得的所有裝載方案情況如表 2 所示：表 2 問題一的裝載方案轎運車類型1-1 型1-1 型1-2 型相同類型、相 同裝載方式 的車輛數(shù)1152裝在上層序號為 1 乘用車數(shù)量404裝在上層序號為 2乘用車數(shù)量058裝在上層序號為 3乘用車數(shù)量000裝在下層序號為 1 乘用車數(shù)量402裝在下層序號為 2乘用車數(shù)量054裝在上層序號為 3乘用車數(shù)量000中間?？康?00目的地000統(tǒng)計的轎運車數(shù)量，如

37、表 3 所示：表 3 問題一的轎運車數(shù)量統(tǒng)計mm轎運車類型 1-1 型1-2 型使用總車輛數(shù)162利用 matlab 軟件實現(xiàn)了前三問通用算法的 exe 可執(zhí)行文件，其第一問運行 結(jié)果如圖 2 所示。圖 2 中，讀取的 excel 表格名字為“inputdata_1”，輸出了 inputdata_1.xls 中輸入的乘用車數(shù)量以及通過算法所得到的不同類型轎運車 數(shù) 量 ， 其 具 體 轎 運 車 裝 載 方 案 輸 出 并 保 存 在 了 outdata_1.xls 與 outdata_1_2.xls 中。圖 2 第一問運行結(jié)果5.5 問題二求解本問題中， n =0 ，n =72 ，n =52

38、，帶入式（ 5-8 ）中，可得問題二的具體模1 2 3型為：min f =mxi（5-10） m j=m+1i =1x 0.2x ,j ii =1i=1s.t .m i=1(c +c ) x =72, i ,2 i ,4 ic x =52,i ,5 ix 0, x z i i0 r 2將 n =0，n =72，n =52 輸入到通用程序中，可以求得 9 種裝載組合方案， 1 2 3如表 4 所示，其中前 4 種為使用 1-1 型轎運車時的所有可能裝載組合方案，后5 種為使用 1-2 型轎運車時的所有可能裝載組合方案。表 4 問題二的所有可能裝載組合方案數(shù)目方案方 方 方 方 方 方 方 方 方

39、 案 案 案 案 案 案 案 案 案 1 2 3 4 5 6 7 8 9上層裝載型乘用車數(shù)目 5 5 5 5 12 12 12 12 12下層裝載型乘用車數(shù)目 下層裝載型乘用車數(shù)目041322310514234251最終求得的所有裝載方案情況如表 5 所示：表 5 問題二的裝載方案轎運車類型1-1 型1-2 型相同類型、相 同裝載方式 的車輛數(shù)121裝在上層序號為 1 乘用車數(shù)量00裝在上層序號為 2乘用車數(shù)量512裝在上層序號為 3乘用車數(shù)量00裝在下層序號為 1 乘用車數(shù)量00裝在下層序號為 2乘用車數(shù)量00裝在上層序號為 3乘用車數(shù)量45中間?？康?0目的地00統(tǒng)計的轎運車數(shù)量，如表 6

40、 所示：表 6 問題二的轎運車數(shù)量統(tǒng)計轎運車類型 1-1 型1-2 型使用總車輛數(shù)121利用 matlab 軟件實現(xiàn)了前三問通用算法的 exe 可執(zhí)行文件，其第一問運行 結(jié)果如圖 3 所示。圖 3 中，讀取的 excel 表格名字為“inputdata_2”，輸出了 inputdata_2.xls 中輸入的乘用車數(shù)量以及通過算法所得到的不同類型轎運車 數(shù) 量 ， 其 具 體 轎 運 車 裝 載 方 案 輸 出 并 保 存 在 了 outdata_2.xls 與 outdata_2_2.xls 中。mmmmii圖 3 第二問運行結(jié)果5.6 問題三求解本問題中，n =156，n =102，n =3

41、9，帶入式（5-8）中，可得問題三的具體1 2 3模型為：mmin f = xi =1i（5-11） m j=m+1x 0.2x ,j ii =1(c +c ) x =156,i ,1 i ,3 ii =1s.t .(c +c ) x =102,i ,2 i ,4 ii =1c x =39,i ,5 ii =1x 0, x z0 r 2將 n =156，n =102，n =39 輸入到通用程序中，由于此時得到的所有可能裝 1 2 3載組合方案達到了 140 種，所以不再列出。最終求得的所有裝載方案情況如表 7 所示：表 7 問題三的裝載方案轎運車相同類型、相裝在裝在裝在裝在裝在裝在中目類型同裝

42、載方式 的車輛數(shù)上層序號上層序號上層序號下層序號下層序號上層序號間停的地為 1 乘用車數(shù)量為 2乘用車數(shù)為 3乘用車數(shù)為 1 乘用車數(shù)量為 2乘用車數(shù)為 3乘用車數(shù)靠地量量量量1-1 型1-1 型1-1 型1-1 型1-1 型1-1 型1-2 型1151125504440045000558000000000232313000004142121100000000000000統(tǒng)計的轎運車數(shù)量，如表 8 所示：表 8 問題三的轎運車數(shù)量統(tǒng)計轎運車類型 1-1 型1-2 型使用總車輛數(shù)255我們用 matlab 軟件實現(xiàn)了前三問通用算法的 exe 可執(zhí)行文件，其運行結(jié)果 如圖 4 所示。圖 4 中，讀

43、取的 excel 表格名字為“inputdata_3”，輸出了 inputdata_3.xls 中輸入的乘用車數(shù)量以及通過算法所得到的不同類型轎運車 數(shù) 量 ， 其 具 體 轎 運 車 裝 載 方 案 輸 出 并 保 存 在 了 outdata_3.xls 與 outdata_3_2.xls 中。圖 4 第三問運行結(jié)果5.7 問題四求解與算法設計ikm 4 mmmmms.t .mmmm5.7.1 模型建立本問題中， n =166 ，n =78 ，n =0 ，只考慮的是型和型乘用車，所有可1 2 3能裝載組合方案如表 1 所示。按照運輸成本最少的要求，只需要在這些可能的 裝載組合方案中，選取某些

44、方案數(shù)，并考慮采用每種方案的轎運車數(shù)量，以使 總的轎運車數(shù)量最少，盡最大可能的滿足各目的地對型和型乘用車的數(shù)量 要求，同時使得轎運車的總路程最少即可。1, 第i種方案去第k個目的地 設 y =0, 第i種方案不去第k個目的地，p 表示 o 到 a、b、c、d 的距離， k（k = 1, 2, 3, 4, 分別代表 a、b、c、d），則可以建立如下雙目標規(guī)劃模型：min f =x 且min s =(y x ) pi i , k i ki =1 k =1 i =1（5-12） m i=m+1x 0.2 x ,i ii =1mi=1i=1(c +c ) x =166, i ,1 i ,3 i(c +

45、c ) x =78, i ,2 i ,4 iy c x =42,i ,1 i ,1 ii=1y c x =31,i ,1 i ,2 ii =1y c x =50,i ,2 i ,1 ii =1y c x =33,i ,3 i ,1 ii =1y c x =47,i ,3 i ,2 ii =1y c x =41,i ,4 i ,1 ii =1x 0, x z , y =0,1i i i , k此雙目標規(guī)劃問題也屬于整數(shù)規(guī)劃問題，當然也可以使用分支定界法進行 求解。故在此問的求解中我們?nèi)允褂蒙厦嫠龅耐ㄓ盟惴ㄟM行求解，也將問題 按兩階段處理，先考慮轎運車數(shù)量最少，尋找較優(yōu)解，然后在這些解中尋找路

46、徑最優(yōu)的解，即為所求。5.7.2 啟發(fā)式調(diào)整優(yōu)化算法與前三問不同的是，在求解時的啟發(fā)式調(diào)整優(yōu)化算法，這里簡述如下： （1） 根據(jù)圖 5 所示的路線圖，確定距離 o 點距離最遠的點，如 a； （2） 優(yōu)先考慮距離最遠的點。為了減少行駛成本，對于最遠的點應盡可能減少轎運車的數(shù)量，所以盡可能的采用 1-2 型轎運車裝載乘用車，運往目的地 a；（3） 再考慮次最遠點，如 b。如仍有 1-2 型轎運車剩余，則優(yōu)先考慮使 用 1-2 型轎運車，否則就只能采用 1-1 型轎運車；（4） 接著考慮 c 點（ocob）。根據(jù) a、b 的運輸量以及每次 1-2 型轎運車 使用量不超過 1-1 型轎運車使用量的 2

47、0%的約束，可以確定在 c 點 時，不會有 1-2 型轎運車剩余，所以只能采用 1-1 型轎運車；（5） 最后考慮 d 點。由于去 a、b、c 點均要經(jīng)過 d 點，在滿足 a、b、c 運輸量需求的情況下，有時可能轎運車并不能達到滿載，為了充分 利用轎運車的空間，可以再裝上一定數(shù)目的乘用車，到了 d 點卸車 即可。eacbdo圖 5 路線圖5.7.3 求解結(jié)果最終求得的所有裝載方案情況如表 9 所示：表 9 問題四的裝載方案轎運車類型相同類型、相同裝載方式的車輛數(shù)裝在上層序號為 1乘用車數(shù)裝在上層序號為 2乘用車數(shù)裝在 裝在 裝在 上層 下層 下層 序號 序號 序號 為 3 為 1 為 2 乘用 乘用 乘用 車數(shù) 車數(shù) 車數(shù)裝在上層序號為 3乘用車數(shù)?？恐械匦堕g 載序停 號為靠 1