全國研究生數(shù)學(xué)建模競賽一等獎(jiǎng)?wù)撐?e題)-乘用車物流運(yùn)輸計(jì)劃問題

1、<p><b>　　參賽密碼 </b></p><p><b>　　（由組委會填寫）</b></p><p><b>　　全</b></p><p>　　第十一屆華為杯全國研究生數(shù)學(xué)建模競賽</p><p><b>　　參賽密碼 </b><

2、/p><p><b>　?。ㄓ山M委會填寫）</b></p><p>　　第十一屆華為杯全國研究生數(shù)學(xué)建模競賽</p><p>　　題 目 乘用車物流運(yùn)輸計(jì)劃問題</p><p>　　摘 要：</p><p>　　本文主要解決的是乘用車整車物流的運(yùn)輸調(diào)度問題，通過對轎運(yùn)

3、車的空間利用率和運(yùn)輸成本進(jìn)行優(yōu)化，建立整數(shù)規(guī)劃模型，設(shè)計(jì)了啟發(fā)式算法，求解出了各種運(yùn)輸條件下的詳細(xì)裝載與運(yùn)輸方案。</p><p>　　針對前三問，由于不考慮目的地和轎運(yùn)車的路徑選擇，將問題抽象為帶裝載組合約束的一維裝車問題，優(yōu)化目標(biāo)是在保證完成運(yùn)輸任務(wù)的前提下盡可能滿載，選擇最優(yōu)裝載組合方案使得所使用的轎運(yùn)車數(shù)量最少。對于滿載的條件，將其簡化為考慮轎運(yùn)車的空間利用率最大，最終建立了空間利用率最大化和運(yùn)輸成本最小

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

5、2、表5、表7）：</p><p>　　針對問題四，其是在問題一的基礎(chǔ)上加入了整車目的地的條件，需要考慮最優(yōu)路徑的選擇。在運(yùn)輸成本上，加入了行駛里程成本，因而可以建立所使用的轎運(yùn)車數(shù)量最少和總里程最少的雙目標(biāo)整數(shù)規(guī)劃模型。對于此種模型，可以采用前三問所設(shè)計(jì)的通用算法進(jìn)行求解。此時(shí)，需要重新設(shè)計(jì)啟發(fā)式調(diào)整優(yōu)化算法。為此，根據(jù)路線距離的遠(yuǎn)近和轎運(yùn)車數(shù)量需要滿足的比例約束條件設(shè)計(jì)了新的調(diào)整優(yōu)化方案。最終求得的各目的地的

6、轎運(yùn)車使用數(shù)量如下表所示，此時(shí)的總路程為6404，具體裝載方案見表9。</p><p>　　針對問題五，作為問題四的擴(kuò)展研究，類似于問題四建立了雙目標(biāo)規(guī)劃模型。由于乘用車的種類達(dá)到了45種，導(dǎo)致轎運(yùn)車的裝載組合方案急劇增多。如果仍采用窮舉法確定裝載組合方案，將產(chǎn)生“組合爆炸”。為此，采用基于排樣算法的裝載優(yōu)化算法，來避免這種現(xiàn)象。這種算法的基本流程是：首先按照乘用車的寬、高將乘用車分為“高”、“低窄”、“低寬”三

7、種車型； 然后根據(jù)不同類型的乘用車在不同目的地的需求量，構(gòu)建關(guān)系樹；接著根據(jù)關(guān)系樹和啟發(fā)式調(diào)整優(yōu)化算法來確立初步配載方案；最后驗(yàn)證配載方案是否滿足約束條件以求得最終方案。其中，啟發(fā)式調(diào)整優(yōu)化算法仍然是基于經(jīng)驗(yàn)的，這里主要考慮轎運(yùn)車上層空間的利用率最大化和距離較遠(yuǎn)的點(diǎn)以盡可能地減少轎運(yùn)車的數(shù)量，同時(shí)也要滿足不同轎運(yùn)車型之間的數(shù)量比例約束。最終求得的各目的地轎運(yùn)車的詳細(xì)使用量如下表所示，并且完成運(yùn)輸任務(wù)所需行駛的總里程為35140。<

8、/p><p>　　關(guān)鍵詞：整車物流 整數(shù)規(guī)劃 分支定界法 經(jīng)驗(yàn)閾值 啟發(fā)式調(diào)整優(yōu)化 排樣算法</p><p><b>　　問題重述</b></p><p><b>　　1.1 問題背景</b></p><p>　　整車物流指的是按照客戶訂單對整車快速配送的全過程。隨著我國汽車工</p>&

9、lt;p>　　業(yè)的高速發(fā)展，整車物流量，特別是乘用車的整車物流量迅速增長。</p><p>　　乘用車生產(chǎn)廠家根據(jù)全國客戶的購車訂單，向物流公司下達(dá)運(yùn)輸乘用車到全國各地的任務(wù)，物流公司則根據(jù)下達(dá)的任務(wù)制定運(yùn)輸計(jì)劃并配送這批乘用車。為此，物流公司首先要從他們當(dāng)時(shí)可以調(diào)用的“轎運(yùn)車”中選擇出若干輛轎運(yùn)車，進(jìn)而給出其中每一輛轎運(yùn)車上乘用車的裝載方案和目的地，以保證運(yùn)輸任務(wù)的完成?！稗I運(yùn)車”是通過公路來運(yùn)輸乘用車整

10、車的專用運(yùn)輸車，根據(jù)型號的不同有單層和雙層兩種類型，而單層轎運(yùn)車實(shí)際中很少使用，本題僅考慮雙層轎運(yùn)車。</p><p>　　在確保完成運(yùn)輸任務(wù)的前提下，物流公司追求降低運(yùn)輸成本。但由于轎運(yùn)車、乘用車有多種規(guī)格等原因，當(dāng)前很多物流公司在制定運(yùn)輸計(jì)劃時(shí)主要依賴調(diào)度人員的經(jīng)驗(yàn)，在面對復(fù)雜的運(yùn)輸任務(wù)時(shí)，往往效率低下，而且運(yùn)輸成本不盡理想。</p><p><b>　　1.2 已知信息&l

11、t;/b></p><p>　?。?）每種轎運(yùn)車上、下層裝載區(qū)域均可等價(jià)看成長方形，各列乘用車均縱向擺放，相鄰乘用車之間縱向及橫向的安全車距均至少為0.1米，下層力爭裝滿，上層兩列力求對稱，以保證轎運(yùn)車行駛平穩(wěn)。</p><p>　?。?）1-1型及2-2型轎運(yùn)車上、下層裝載區(qū)域相同；第五問中1-2型轎運(yùn)車上、下層裝載區(qū)域長度相同，但上層比下層寬0.8米。</p>&l

12、t;p>　?。?）受層高限制，高度超過1.7米的乘用車只能裝在1-1、1-2型下層，2-2型上、下層均不能裝載高度超過1.7米的乘用車。</p><p>　?。?）在轎運(yùn)車使用數(shù)量相同情況下，1-1型轎運(yùn)車的使用成本較低，2-2型較高，1-2型略低于前兩者的平均值，但物流公司1-2型轎運(yùn)車擁有量小，為方便后續(xù)任務(wù)安排，每次1-2型轎運(yùn)車使用量不超過1-1型轎運(yùn)車使用量的20%。</p><

13、;p>　　（5）在轎運(yùn)車使用數(shù)量及型號均相同情況下，行駛里程短的成本低。</p><p>　　1.3 需要解決的問題</p><p>　　請為物流公司安排以下五次運(yùn)輸，制定詳細(xì)計(jì)劃，含所需要各種類型轎運(yùn)車的數(shù)量、每輛轎運(yùn)車的乘用車裝載方案、行車路線。（前三問目的地只有一個(gè)，可提供一個(gè)通用程序；后兩問也要給出啟發(fā)式算法的程序，優(yōu)化模型則更佳）：</p><p>

14、　?。?）物流公司要運(yùn)輸Ⅰ車型的乘用車100輛及Ⅱ車型的乘用車68輛。</p><p>　　（2）物流公司要運(yùn)輸Ⅱ車型的乘用車72輛及Ⅲ車型的乘用車52輛。</p><p>　?。?）物流公司要運(yùn)輸Ⅰ車型的乘用車156輛、Ⅱ車型的乘用車102輛及Ⅲ車型的乘用車39輛。</p><p>　　（4）物流公司要運(yùn)輸166輛Ⅰ車型的乘用車（其中目的地是A、B、C、D的分別為

15、42、50、33、41輛）和78輛Ⅱ車型的乘用車（其中目的地是A、C的分別為31、47輛）。</p><p>　?。?）根據(jù)附件表1給出的物流公司需要運(yùn)輸?shù)某擞密囶愋停ê蛱?、尺寸大小、數(shù)量和目的地和附件表2給出的可以調(diào)用的轎運(yùn)車類型（含序號)、數(shù)量和裝載區(qū)域大小，采用啟發(fā)式算法，求解裝載、運(yùn)輸方案，并自行設(shè)計(jì)運(yùn)輸方案的表達(dá)形式。</p><p><b>　　模型假設(shè)</

16、b></p><p>　　(1) 每輛轎運(yùn)車裝載乘用車的組合是獨(dú)立的；</p><p>　　(2) 轎運(yùn)車裝載乘用車時(shí)上下層部分是對稱的，即數(shù)量一致；</p><p>　　(3) 轎運(yùn)車到達(dá)目的地后原地待命，無須放空返回；</p><p>　　(4) 轎運(yùn)車在運(yùn)輸過程中不存在往返情況；</p><p>　　(5)

17、 每次卸車成本可以忽略不計(jì)。</p><p><b>　　基本符號說明</b></p><p><b>　　問題分析</b></p><p>　　本文研究的是乘用車物流運(yùn)輸計(jì)劃問題，通過對轎運(yùn)車的空間利用率和運(yùn)輸成本進(jìn)行優(yōu)化，設(shè)計(jì)啟發(fā)式算法，以求解各種運(yùn)輸條件下詳細(xì)的裝載與運(yùn)輸方案，能夠使得轎運(yùn)車的利用率達(dá)到最高、運(yùn)輸成本

18、達(dá)到最低、行車路線最優(yōu)。針對題中的五個(gè)問題，分析如下：</p><p><b>　　4.1 問題一分析</b></p><p>　　題目要求給出運(yùn)輸Ⅰ車型的乘用車100輛及Ⅱ車型的乘用車68輛時(shí)物流公司的運(yùn)輸方案。本問題即將給定數(shù)量的Ⅰ車型和Ⅱ車型乘用車裝載到1-1型轎運(yùn)車和1-2型轎運(yùn)車上，并使得所用的1-1型轎運(yùn)車和1-2型轎運(yùn)車數(shù)量之和最少，亦即成本最少。并在滿

19、足數(shù)量最少的情況下，求解Ⅰ車型和Ⅱ車型乘用車的最佳裝載組合方案，以使得兩種轎運(yùn)車空間利用率達(dá)到最大。由于兩種乘用車的高度均不超過1.7米，且其寬度小于轎運(yùn)車的下層寬度、兩倍寬度也不超過轎運(yùn)車的上層寬度，即Ⅰ車型和Ⅱ車型乘用車可以裝載在1-1型和1-2型轎運(yùn)車的任意層上。所以，問題可以歸結(jié)為一維組合裝車問題，求解的目標(biāo)是充分利用轎運(yùn)車的長度，以使得轎運(yùn)車的長度余量最少，則轎運(yùn)車的空間利用率也將達(dá)到最大。</p><p&

20、gt;<b>　　4.2 問題二分析</b></p><p>　　題目要求給出運(yùn)輸Ⅱ車型的乘用車72輛及Ⅲ車型的乘用車52輛時(shí)物流公司的運(yùn)輸方案。本問題即將給定數(shù)量的Ⅱ車型和Ⅲ車型乘用車裝載到1-1型轎運(yùn)車和1-2型轎運(yùn)車上，并使得所用的1-1型轎運(yùn)車和1-2型轎運(yùn)車數(shù)量之和最少，亦即成本最少。并在滿足數(shù)量最少的情況下，求解Ⅱ車型和Ⅲ車型乘用車的最佳裝載組合方案，以使得兩種轎運(yùn)車空間利用率達(dá)

21、到最大。由于Ⅲ車型乘用車的高度大于1.7米，根據(jù)題目中的要求，只能將其裝載在1-1型和1-2型轎運(yùn)車的下層上。而Ⅱ車型的乘用車，仍然可以裝載在1-1型和1-2型轎運(yùn)車的任意層。問題仍為求解一維組合裝車問題，求解的目標(biāo)是充分利用轎運(yùn)車的長度，以使得轎運(yùn)車的長度余量最少。 </p><p><b>　　4.3 問題三分析</b></p><p>　　題目要求給出運(yùn)輸Ⅰ車型

22、的乘用車156輛、Ⅱ車型的乘用車102輛及Ⅲ車型的乘用車39輛時(shí)物流公司的運(yùn)輸方案。本問題即將給定數(shù)量的Ⅰ車型、Ⅱ車型和Ⅲ車型乘用車裝載到1-1型轎運(yùn)車和1-2型轎運(yùn)車上，并使得所用的1-1型轎運(yùn)車和1-2型轎運(yùn)車數(shù)量之和最少，亦即成本最少。并在滿足數(shù)量最少的情況下，求解Ⅰ車型、Ⅱ車型和Ⅲ車型乘用車的最佳裝載組合方案，以使得兩種轎運(yùn)車空間利用率達(dá)到最大。此問題可以看作是前兩問的延伸，此時(shí)1-1型轎運(yùn)車和1-2型轎運(yùn)車下層均可以裝載三種乘

23、用車，而上層只能裝載Ⅰ車型和Ⅱ車型轎運(yùn)車。</p><p><b>　　4.4 問題四分析</b></p><p>　　題目要求給出運(yùn)輸166輛Ⅰ車型的乘用車（其中目的地是A、B、C、D的分別為42、50、33、41輛）和78輛Ⅱ車型的乘用車（其中目的地是A、C的分別為31、47輛）時(shí)物流公司的運(yùn)輸方案。本問題可以看作是問題一的延伸，在問題一的基礎(chǔ)上將路徑加入到了考慮

24、之列，目的地不再相同。問題變成將給定數(shù)量的Ⅰ車型和Ⅱ車型乘用車裝載到1-1型轎運(yùn)車和1-2型轎運(yùn)車上，并運(yùn)往相應(yīng)的目的地，以滿足各目的地的需求，使得運(yùn)輸成本最少。而影響運(yùn)輸成本的首要因素是轎運(yùn)車使用數(shù)量，其次是行駛里程長短。因而問題轉(zhuǎn)換為求解Ⅰ車型和Ⅱ車型乘用車的最佳裝載組合方案，以使得兩種轎運(yùn)車的使用總數(shù)量最小且所需的路程最短。這是一個(gè)雙目標(biāo)規(guī)劃問題，此時(shí)轎運(yùn)車有可能不再滿足滿載的條件。</p><p><

25、;b>　　4.5 問題五分析</b></p><p>　　題目要求利用10種不同規(guī)格轎運(yùn)車，來裝載45種不同規(guī)格的乘用車，以滿足A、B、C、D、E五個(gè)目的地對45種乘用車的數(shù)量需求。本問題可以看作是問題四的擴(kuò)展研究，只是問題比第四問要復(fù)雜的多，但整體的模型是一致的。對于這種NP－難問題，尋找最優(yōu)解是不切實(shí)際的，需要重新設(shè)計(jì)啟發(fā)式算法，簡化目標(biāo)函數(shù)，使其更容易求解，以期能夠求得滿足約束條件的可行解

26、。</p><p><b>　　問題求解與算法設(shè)計(jì)</b></p><p>　　5.1裝載問題的基本模型</p><p>　　5.1.1 模型定性分析</p><p>　　在不考慮整車目的地和轎運(yùn)車的路徑選擇的情況下，問題可抽象為帶裝載組合約束的一維裝車問題[1]，即有n個(gè)屬于l種類型的相同（單位）尺寸的物品，有w輛車，

27、每輛車對這l種類型的物品有幾種裝載組合，不同車輛的裝載組合不同，每輛車選擇一種裝載組合并嚴(yán)格按照物品組合進(jìn)行裝載。優(yōu)化目標(biāo)是在滿載的情況下裝載最多的物品，同時(shí)給出每個(gè)物品的具體配載方案。</p><p>　　5.1.2 復(fù)雜性分析</p><p>　　考慮帶裝載組合約束的一維裝車問題的簡化問題，當(dāng)每輛車只有一個(gè)裝載組合時(shí)，問題變?yōu)椋河衛(wèi)種類型的物品，類型k的物品數(shù)Nk，有n個(gè)裝載組合，第j

28、個(gè)裝載組合對類型k物品的容量Cjk，對所有類型物品的容量Cj，選擇裝載組合以盡可能裝載最多的物品。已知多維背包問題為NP－難問題[2]，而多維背包問題可以轉(zhuǎn)化為一維組合裝車問題的簡化問題，則一維組合裝車問題的簡化問題為NP－難問題，顯然一維組合裝車問題更為復(fù)雜，也即一維組合裝車問題為NP－難問題。</p><p>　　5.1.3 一維組合裝車問題線性混合整數(shù)規(guī)劃模型[3]</p><p>

29、　　問題最終結(jié)果是給出具體的裝載方案，即物品裝載在哪輛車的哪個(gè)裝載組合上，因此以物品作為決策主體，物品選擇車輛、裝載組合。</p><p>　　設(shè)物品數(shù)為m,類型數(shù)為l，車輛數(shù)為w，第v輛車的裝載組合數(shù)為v_n，第v輛車第j個(gè)裝載組合裝載第k種類型物品的容量為Cvjk, xivj為物品i是否裝載在車輛v的第j個(gè)裝載組合上的0、1變量，yvj為車輛v是否選擇第j個(gè)裝載組合的0、1變量，則有如下數(shù)學(xué)模型：</p

30、><p><b>　　(5-1)</b></p><p>　　優(yōu)化目標(biāo)為物品裝載數(shù)最多；約束式第一式表示一輛車最多只能選擇一種裝載組合；第二式表示一個(gè)物品最多只能被裝載到一輛車的某個(gè)裝載組合上；第三式表示每輛車必須嚴(yán)格按照裝載組合裝滿每種類型的物品；第四、五式定義了變量的取值范圍。</p><p>　　5.2 兩階段裝載優(yōu)化模型的建立</p&

31、gt;<p>　　5.2.1 實(shí)際問題的分析與簡化</p><p>　　在本問題中，有三種類型的乘用車，其數(shù)量根據(jù)具體的運(yùn)輸任務(wù)而定，每種車的規(guī)格均不同。轎運(yùn)車也有兩種，其規(guī)格也有較大差異?，F(xiàn)要考慮將給定數(shù)量的三種類型的乘用車裝載到兩種類型的較運(yùn)車上，但轎運(yùn)車的數(shù)量可以無限多。為了在保證完成運(yùn)輸任務(wù)的前提下，降低整車物流的運(yùn)輸成本，目標(biāo)函數(shù)變?yōu)樵跐M足滿載的情況下，選擇最優(yōu)裝載組合方案，使得所使用的轎

32、運(yùn)車數(shù)量最少。而滿載的條件在本問題中不再適用，我們簡化為考慮轎運(yùn)車的空間利用率最大，為此，建立了兩階段裝載優(yōu)化模型[4]。</p><p>　　5.2.2 裝載組合方案的確定</p><p>　　在給定運(yùn)輸任務(wù)的乘用車類型后，根據(jù)各乘用車的規(guī)格和各裝載用轎運(yùn)車的規(guī)格，首先確定1-1型和1-2型轎運(yùn)車每層可以裝載的乘用車類型，然后依據(jù)1-1型和1-2型轎運(yùn)車的實(shí)際長度，再加上縱向的安全車距的

33、限制，采用窮舉法，可以確立各類型轎運(yùn)車的所有裝載組合。</p><p>　　假定轎運(yùn)車的長度為L，第j種乘用車的長度為lj（j = 1, 2, 3分別代表Ⅰ型、Ⅱ型、Ⅲ型），并用kj表示裝載組合中承載的第j種乘用車的數(shù)目，安全距離c=0.1，滿足要求的裝載組合方案應(yīng)滿足（只考慮單個(gè)下層的情況，其它層類似）：</p><p><b>　?。?-2）</b></p&

34、gt;<p>　　5.2.3 兩階段裝載優(yōu)化模型</p><p>　?。?）第一階段：空間利用率最大化優(yōu)化模型</p><p><b>　　a）目標(biāo)函數(shù)的確定</b></p><p>　　考慮到無論是使用1-1型轎運(yùn)車還是1-2型轎運(yùn)車，均采用雙層裝載。而且為了安全，下層裝載的是重心高度較高的乘用車，如Ⅲ車型乘用車。再者，Ⅰ車型和

35、Ⅱ車型乘用車的寬度均在轎運(yùn)車的允許范圍之內(nèi)。因此，轎運(yùn)車在裝載乘用車時(shí)，在高度和寬度上并不存在利用的概念，在最大化空間利用率時(shí)僅需考慮長度的充分利用即可，而具體裝載輛數(shù)取決于乘用車的類型。</p><p>　　設(shè)Ci，j表示第i種裝載組合方案能承載第j種乘用車的數(shù)目（i = 1, 2，… , m, m+1, …, M，m為使用1-1型轎運(yùn)車的最大方案數(shù)，M為分別使用1-1型、1-2型轎運(yùn)車的總方案數(shù)之和；j =

36、1, 2, 3, 4, 5, 分別表示上Ⅰ（Ⅰ型車放在上層，后面依次類推）、上Ⅱ、下Ⅰ、下Ⅱ、下Ⅲ五種情況），n表示轎運(yùn)車的列數(shù)（1-1型為2, 1-2型為3, 2-2型為4），則目標(biāo)函數(shù)可以表示為：</p><p><b>　?。?-3）</b></p><p><b>　　b）約束條件的確定</b></p><p>　

37、　轎運(yùn)車裝載時(shí)，應(yīng)保證乘用車與乘用車之間，乘用車與轎運(yùn)車端壁之間的最小間隙, 避免發(fā)生碰撞，此安全距離為0.1米，同時(shí)應(yīng)滿足轎運(yùn)車的裝載長度約束。即，滿足的約束條件如下：</p><p><b>　?。?-4）</b></p><p>　?。?）第二階段：運(yùn)輸成本最小化優(yōu)化模型</p><p><b>　　a）目標(biāo)函數(shù)的確定</

38、b></p><p>　　由于影響整車物流運(yùn)輸成本高低的主要因素首先是轎運(yùn)車使用數(shù)量，其次是在轎運(yùn)車使用數(shù)量相同情況下的轎運(yùn)車使用成本，最后是行駛里程成本。而在前三問的模型中，不考慮路徑問題，因而我們以轎運(yùn)車的使用數(shù)量最少為主要考慮因素，對組合方案進(jìn)行優(yōu)化，以使運(yùn)輸成本最小。</p><p>　　設(shè)第i種方案的使用數(shù)量為xi(i = 1, 2，… , m, m+1, …, M)，則目

39、標(biāo)函數(shù)為：</p><p><b>　?。?-5）</b></p><p><b>　　b）約束條件的確定</b></p><p>　　由于1-1型轎運(yùn)車的使用成本較低，2-2型較高，1-2型略低于前兩者的平均值。為了降低成本，應(yīng)使1-2型轎運(yùn)車使用量少于1-1型轎運(yùn)車，且每次1-2型轎運(yùn)車使用量不超過1-1型轎運(yùn)車使用量

40、的20%，這也符合物流公司1-2型轎運(yùn)車擁有量小的實(shí)際；再者，無論采用哪些組合方案，都必須滿足物流公司的運(yùn)輸安排，努力完成任務(wù)。即，滿足的約束條件如下：</p><p><b>　?。?-6）</b></p><p>　　其中，Nj為需要裝載的第j種乘用車的數(shù)量。</p><p>　　5.2.4基于經(jīng)驗(yàn)閾值的求解優(yōu)化方法</p>

41、<p>　　考慮到在求解上述兩階段裝載優(yōu)化模型時(shí)，問題歸結(jié)為一個(gè)雙目標(biāo)規(guī)劃問題，實(shí)際求解時(shí)較為困難。為此，對問題進(jìn)行重新分析，空間利用率最大可以等價(jià)為長度余量最少，而組合方案的求解時(shí)也可以通過考慮長度余量來進(jìn)行分析。設(shè)長度余量為r，則</p><p><b>　?。?-7）</b></p><p>　　根據(jù)實(shí)際情況，r應(yīng)滿足非負(fù)的要求。</p>

42、<p>　　由于每種方案的長度余量不同，但對于每種類型的轎運(yùn)車的所有裝載組合方案，其長度余量必有一個(gè)取值范圍，我們可以考慮人為的給定一個(gè)閾值。這樣可以對組合方案進(jìn)行有目的的篩選，也可以解決因窮舉法產(chǎn)生的“組合爆炸”問題，同時(shí)也考慮了空間利用率最大。因而，求解兩階段裝載優(yōu)化問題最終歸結(jié)為一個(gè)整數(shù)規(guī)劃問題</p><p><b>　?。?-8）</b></p><

43、p>　　其中，T為閾值，根據(jù)經(jīng)驗(yàn)獲得，在本文的計(jì)算中，T取2。</p><p>　　5.3 裝載優(yōu)化模型的通用求解算法設(shè)計(jì)</p><p>　　5.3.1 求解整數(shù)規(guī)劃的分支定界算法</p><p>　　分支定界算法是一種隱枚舉法,是整數(shù)規(guī)劃中常用的算法之一[5]。它的主要思想是根據(jù)某種策略將原問題松弛問題的可行域分解為越來越小的子域, 并檢查每個(gè)子域內(nèi)整數(shù)解

44、的情況, 直到找到最優(yōu)整數(shù)解或證明整數(shù)解不存在。</p><p>　　分支定界法從求松弛問題開始, 將問題可行域分為許多的子域(最通常的分解方式是“兩分法”),這一過程稱為分支；通過分支找到更好的整數(shù)解來不斷的修改問題的上下解,這一過程稱為定界。定界的目的是為了測定界的趨勢,留下有價(jià)值的或尚不能判定的分支。刪除肯定不存在最優(yōu)解的分支, 稱之為剪枝, 以達(dá)到加速收斂, 簡化運(yùn)算的目的。不同的分支定界方法在于分支、定

45、界和剪枝的不同處理手段上, 其算法的一般步驟可概括為：</p><p>　　Step1：初始化。選擇可行域的S的初始松弛集合F，滿足；初始可</p><p>　　行點(diǎn)集合，上界，令P={F}，計(jì)算下界，并令。在計(jì)算的過程中，若有必要，則更新Q和。</p><p>　　Step2：分割。將F分割成有限個(gè)子集Fi，（指標(biāo)集）滿足</p><p>

46、<b>　　，令。</b></p><p>　　Step3：剪枝。對每個(gè)，計(jì)算f 在子集Fi 上的下界，使其滿足，利用在計(jì)算)的過程中所發(fā)現(xiàn)的所有可行點(diǎn)修正集合Q，同時(shí)按照合適的刪除規(guī)則，刪除P中所有不包含最優(yōu)解的Fi或Fi的一部分，剩余集合不妨仍記為P；</p><p>　　Step4：定界。令，。</p><p>　　Step5：終止判斷。

47、若（充分小的正數(shù)），則終止算法。否則，從P中挑選合適的子集F，，轉(zhuǎn)入步驟2。</p><p>　　5.3.2 啟發(fā)式調(diào)整優(yōu)化</p><p>　　啟發(fā)式算法[3]是一種基于直觀或經(jīng)驗(yàn)構(gòu)造的算法,在可接受的花費(fèi)(指計(jì)算時(shí)間和空間)下給出待解決組合優(yōu)化問題每一個(gè)實(shí)例的一個(gè)可行解,該可行解與最優(yōu)解的偏離程度不一定事先可以預(yù)計(jì)。</p><p>　　利用分支定界法求解整數(shù)規(guī)

48、劃問題（5-8）所得的解有時(shí)并不是最優(yōu)解，此時(shí)就需要進(jìn)行調(diào)整，這時(shí)只需要在保證轎運(yùn)車總數(shù)量不變的情況下，對可行解進(jìn)行啟發(fā)式的局部調(diào)整即可。這種啟發(fā)式的調(diào)整思路大致如下：</p><p>　　放寬閾值T，擴(kuò)大解的范圍；</p><p>　　根據(jù)經(jīng)驗(yàn)，將新解范圍中的某一種方案的數(shù)量與可行解相應(yīng)的方案數(shù)量進(jìn)行替換；</p><p>　　驗(yàn)證新的解是否滿足約束條件，如果新解

49、滿足約束條件且新解的轎運(yùn)車數(shù)量總數(shù)不超過可行解，則新解即為可能的最優(yōu)解；</p><p>　　在這些所有可能的最優(yōu)解中，尋找轎運(yùn)車數(shù)目最少的即為最優(yōu)解。</p><p>　　啟發(fā)式算法簡單直觀，速度快，容易被接受，但在最壞情況下，也不能獲得最優(yōu)解，這時(shí)就只能通過人工干預(yù)進(jìn)行調(diào)整，以獲得最優(yōu)解。</p><p>　　5.3.3 通用算法設(shè)計(jì)</p>&l

50、t;p>　　圖1 通用算法流程圖</p><p>　　本文通過前三問的求解，歸納總結(jié)出了一種適合求解前三問的通用算法，并用一個(gè)通用程序進(jìn)行了實(shí)現(xiàn)。所實(shí)現(xiàn)的通用程序，能夠滿足前三問運(yùn)輸任務(wù)，并能按照題目要求輸入輸出最優(yōu)解。算法的流程圖如圖1所示，這里，簡單敘述一下通用算法的主要步驟：</p><p>　　Step1：分別輸入轎運(yùn)車與乘用車的規(guī)格數(shù)據(jù)（長、寬、高），并輸入需要運(yùn)輸?shù)娜N乘

51、用車的數(shù)量，如果沒有某種乘用車，則輸入0；</p><p>　　Step2：通過（5-2）式來計(jì)算所有可能的轎運(yùn)車裝載方案，并進(jìn)行編號；</p><p>　　Step3：利用分支定界法求解式（5-8）所示的整數(shù)規(guī)劃問題，并對所求得的解進(jìn)行驗(yàn)證，如果求得的解就是最優(yōu)解，則轉(zhuǎn)到Step6；否則繼續(xù)；</p><p>　　Step4：按照上節(jié)所述的啟發(fā)式調(diào)整優(yōu)化方法繼續(xù)求

52、解優(yōu)化，尋找最優(yōu)解，并對所求得的解進(jìn)行驗(yàn)證，如果所得的解即是最優(yōu)解，則轉(zhuǎn)到Step6；否則繼續(xù)；</p><p>　　Step5：對上步所得的可行解進(jìn)行人工干預(yù)，局部小范圍調(diào)整方案，以獲得最優(yōu)解；</p><p>　　Step6：按照題目要求輸出裝載方案與所需轎運(yùn)車數(shù)量的Excel格式。</p><p><b>　　5.4 問題一求解</b>&

53、lt;/p><p>　　本問題中，N1=100，N2=68，N3=0，帶入式（5-8）中，可得問題一的具體模型為：</p><p><b>　?。?-9）</b></p><p>　　將N1=100，N2=68，N3=0輸入到通用程序中，可以求得11種裝載組合方案，如表1所示，其中前5種為使用1-1型轎運(yùn)車時(shí)的所有可能裝載組合方案，后6種為使用1-

54、2型轎運(yùn)車時(shí)的所有可能裝載組合方案。</p><p>　　表1 問題一的所有可能裝載組合方案</p><p>　　最終求得的所有裝載方案情況如表2所示：</p><p>　　表2 問題一的裝載方案</p><p>　　統(tǒng)計(jì)的轎運(yùn)車數(shù)量，如表3所示：</p><p>　　表3 問題一的轎運(yùn)車數(shù)量統(tǒng)計(jì)</p>

55、<p>　　利用MATLAB軟件實(shí)現(xiàn)了前三問通用算法的exe可執(zhí)行文件，其第一問運(yùn)行結(jié)果如圖2所示。圖2中，讀取的excel表格名字為“inputData_1”，輸出了inputData_1.xls中輸入的乘用車數(shù)量以及通過算法所得到的不同類型轎運(yùn)車數(shù)量，其具體轎運(yùn)車裝載方案輸出并保存在了outData_1.xls與outData_1_2.xls中。</p><p>　　圖2 第一問運(yùn)行結(jié)果</

56、p><p><b>　　5.5 問題二求解</b></p><p>　　本問題中，N1=0，N2=72，N3=52，帶入式（5-8）中，可得問題二的具體模型為：</p><p><b>　?。?-10）</b></p><p>　　將N1=0，N2=72，N3=52輸入到通用程序中，可以求得9種裝載組合

57、方案，如表4所示，其中前4種為使用1-1型轎運(yùn)車時(shí)的所有可能裝載組合方案，后5種為使用1-2型轎運(yùn)車時(shí)的所有可能裝載組合方案。</p><p>　　表4 問題二的所有可能裝載組合方案</p><p>　　最終求得的所有裝載方案情況如表5所示：</p><p>　　表5 問題二的裝載方案</p><p>　　統(tǒng)計(jì)的轎運(yùn)車數(shù)量，如表6所示：<

58、;/p><p>　　表6 問題二的轎運(yùn)車數(shù)量統(tǒng)計(jì)</p><p>　　利用MATLAB軟件實(shí)現(xiàn)了前三問通用算法的exe可執(zhí)行文件，其第一問運(yùn)行結(jié)果如圖3所示。圖3中，讀取的excel表格名字為“inputData_2”，輸出了inputData_2.xls中輸入的乘用車數(shù)量以及通過算法所得到的不同類型轎運(yùn)車數(shù)量，其具體轎運(yùn)車裝載方案輸出并保存在了outData_2.xls與outData_2_

59、2.xls中。</p><p>　　圖3 第二問運(yùn)行結(jié)果</p><p><b>　　5.6 問題三求解</b></p><p>　　本問題中，N1=156，N2=102，N3=39，帶入式（5-8）中，可得問題三的具體模型為：</p><p><b>　　（5-11）</b></p>

60、<p>　　將N1=156，N2=102，N3=39輸入到通用程序中，由于此時(shí)得到的所有可能裝載組合方案達(dá)到了140種，所以不再列出。</p><p>　　最終求得的所有裝載方案情況如表7所示：</p><p>　　表7 問題三的裝載方案</p><p>　　統(tǒng)計(jì)的轎運(yùn)車數(shù)量，如表8所示：</p><p>　　表8 問題三的轎運(yùn)車

61、數(shù)量統(tǒng)計(jì)</p><p>　　我們用MATLAB軟件實(shí)現(xiàn)了前三問通用算法的exe可執(zhí)行文件，其運(yùn)行結(jié)果如圖4所示。圖4中，讀取的excel表格名字為“inputData_3”，輸出了inputData_3.xls中輸入的乘用車數(shù)量以及通過算法所得到的不同類型轎運(yùn)車數(shù)量，其具體轎運(yùn)車裝載方案輸出并保存在了outData_3.xls與outData_3_2.xls中。</p><p>　　圖4

62、 第三問運(yùn)行結(jié)果</p><p>　　5.7 問題四求解與算法設(shè)計(jì)</p><p>　　5.7.1 模型建立</p><p>　　本問題中，N1=166，N2=78，N3=0，只考慮的是Ⅰ型和Ⅱ型乘用車，所有可能裝載組合方案如表1所示。按照運(yùn)輸成本最少的要求，只需要在這些可能的裝載組合方案中，選取某些方案數(shù)，并考慮采用每種方案的轎運(yùn)車數(shù)量，以使總的轎運(yùn)車數(shù)量最少，盡

63、最大可能的滿足各目的地對Ⅰ型和Ⅱ型乘用車的數(shù)量要求，同時(shí)使得轎運(yùn)車的總路程最少即可。</p><p>　　設(shè)，Pk表示O到A、B、C、D的距離，（k = 1, 2, 3, 4, 分別代表A、B、C、D），則可以建立如下雙目標(biāo)規(guī)劃模型：</p><p><b>　?。?-12）</b></p><p>　　此雙目標(biāo)規(guī)劃問題也屬于整數(shù)規(guī)劃問題，當(dāng)然

64、也可以使用分支定界法進(jìn)行求解。故在此問的求解中我們?nèi)允褂蒙厦嫠龅耐ㄓ盟惴ㄟM(jìn)行求解，也將問題按兩階段處理，先考慮轎運(yùn)車數(shù)量最少，尋找較優(yōu)解，然后在這些解中尋找路徑最優(yōu)的解，即為所求。</p><p>　　5.7.2 啟發(fā)式調(diào)整優(yōu)化算法</p><p>　　與前三問不同的是，在求解時(shí)的啟發(fā)式調(diào)整優(yōu)化算法，這里簡述如下：</p><p>　　根據(jù)圖5所示的路線圖，確定距

65、離O點(diǎn)距離最遠(yuǎn)的點(diǎn)，如A；</p><p>　　優(yōu)先考慮距離最遠(yuǎn)的點(diǎn)。為了減少行駛成本，對于最遠(yuǎn)的點(diǎn)應(yīng)盡可能減少轎運(yùn)車的數(shù)量，所以盡可能的采用1-2型轎運(yùn)車裝載乘用車，運(yùn)往目的地A；</p><p>　　再考慮次最遠(yuǎn)點(diǎn)，如B。如仍有1-2型轎運(yùn)車剩余，則優(yōu)先考慮使用1-2型轎運(yùn)車，否則就只能采用1-1型轎運(yùn)車；</p><p>　　接著考慮C點(diǎn)（OC<OB）。

66、根據(jù)A、B的運(yùn)輸量以及每次1-2型轎運(yùn)車使用量不超過1-1型轎運(yùn)車使用量的20%的約束，可以確定在C點(diǎn)時(shí)，不會有1-2型轎運(yùn)車剩余，所以只能采用1-1型轎運(yùn)車；</p><p>　　最后考慮D點(diǎn)。由于去A、B、C點(diǎn)均要經(jīng)過D點(diǎn)，在滿足A、B、C運(yùn)輸量需求的情況下，有時(shí)可能轎運(yùn)車并不能達(dá)到滿載，為了充分利用轎運(yùn)車的空間，可以再裝上一定數(shù)目的乘用車，到了D點(diǎn)卸車即可。</p><p><

67、b>　　圖5 路線圖</b></p><p>　　5.7.3 求解結(jié)果</p><p>　　最終求得的所有裝載方案情況如表9所示：</p><p>　　表9 問題四的裝載方案</p><p>　　統(tǒng)計(jì)的轎運(yùn)車數(shù)量，如表10所示：</p><p>　　表10 問題四的轎運(yùn)車數(shù)量統(tǒng)計(jì)</p>

68、<p>　　此時(shí)，轎運(yùn)車的總路程S為</p><p>　　S=(2+1+1+1)*360+6*280+(4+1+3+1)*236+5*160=6404</p><p>　　我們用MATLAB軟件實(shí)現(xiàn)了第四問算法的exe可執(zhí)行文件，其運(yùn)行結(jié)果如圖6所示。圖6中，讀取的excel表格名字為“inputData_4”，輸出了inputData_4.xls中輸入的乘用車數(shù)量以及通過算法

69、所得到的不同類型轎運(yùn)車數(shù)量，其具體轎運(yùn)車裝載方案輸出并保存在了outData_4.xls與outData_4_2.xls中。</p><p>　　圖6 第四問運(yùn)行結(jié)果</p><p>　　5.8 問題五求解與算法設(shè)計(jì)</p><p>　　5.8.1 模型建立</p><p>　　本問題可以看作是問題四的擴(kuò)展研究，此時(shí)，乘用車類型增加到45，

70、轎運(yùn)車種類增加到10，目的地增加到5，優(yōu)化目標(biāo)仍與第四問相同，參照（5-12）的雙目標(biāo)規(guī)劃模型，可以得到如下模型：</p><p><b>　?。?-13）</b></p><p>　　其中，mh表示第h種轎運(yùn)車在所有組合方案中的位置下標(biāo)（h=0, 1, …, 10; m0=0），bjk表示第j種乘用車運(yùn)往第k個(gè)目的地的數(shù)量。</p><p>

71、　　5.8.2 基于排樣算法的裝載優(yōu)化算法</p><p>　　在求解（5-13）所示的優(yōu)化模型時(shí)，為避免釆用窮舉法出現(xiàn)的“組合爆炸”，可采用基于排樣算法的裝載優(yōu)化算法來解決該問題[4]。由于該算法與汽車運(yùn)輸設(shè)備的規(guī)格尺寸、所到目的地密切相關(guān)，因此結(jié)合運(yùn)輸汽車專用車的結(jié)構(gòu)尺寸、所到目的地，可設(shè)計(jì)基于排樣算法的汽車裝載優(yōu)化算法如下：</p><p>　　Step l：根據(jù)轎運(yùn)車裝載乘用車的限

72、高尺度，初步確定轎運(yùn)車可以裝載的乘用車類型；</p><p>　　Step 2：根據(jù)乘用車及轎運(yùn)車的規(guī)格尺寸，進(jìn)一步對轎運(yùn)車可以裝載的乘用車類型進(jìn)行劃分；</p><p>　　Step 3：依據(jù)待裝乘用車不同類型的目的地需求，構(gòu)建關(guān)系樹；</p><p>　　Step 4：根據(jù)待裝乘用車的關(guān)系樹以及啟發(fā)式調(diào)整優(yōu)化算法（見下文所述），初步選擇配載方案；</p&g

73、t;<p>　　Step 5：驗(yàn)證配載方案是否滿足約束條件；若不滿足，則回到Step4；滿足，則進(jìn)入下一步；</p><p>　　Step6：確定各種轎運(yùn)車裝載乘用車的方案。</p><p>　　根據(jù)上述算法，結(jié)合實(shí)際待裝乘用車的長度及轎運(yùn)車的類型，我們將待裝乘用車劃分為“高”、“低窄”、“低寬”三種車型。“高”的標(biāo)準(zhǔn)是：乘用車高度大于1.7米；“低窄”的標(biāo)準(zhǔn)是：乘用車高度不

74、超過1.7米且寬度不超過1.7米；“低寬”的標(biāo)準(zhǔn)是：乘用車高度不超過1.7米且寬度大于1.7米。最終的乘用車分類結(jié)果如下表所示：</p><p>　　表11 乘用車分類結(jié)果</p><p>　　接著，按照待裝乘用車的三種類型以及五個(gè)目的地對乘用車的需求，可得到具體的關(guān)系樹，如圖7所示。</p><p>　　5.8.3 啟發(fā)式調(diào)整優(yōu)化算法</p><

75、;p>　　根據(jù)附表中給出的轎運(yùn)車數(shù)據(jù)，可以看出，對于“高”型車，只能裝載在1-2型車的下層和1-1型的下層；對于“低窄”型車，可以裝載在任意類型的轎運(yùn)車上，但根據(jù)經(jīng)驗(yàn)，應(yīng)盡可能的選擇2-2型車和1-2型車的上層進(jìn)行裝載，這樣可以最大限度的利用2-2型車和1-2型車的上層空間，使其裝載的“低窄”型車數(shù)量最大化，這樣將使其空間得到充分利用，又能減少轎運(yùn)車的成本；對于“低寬”型車，可以裝載在1-1型的上下層，2-2型車和1-2型車的下層

76、，上層由于考慮到要使兩列對稱，如果裝載“低寬”型車將只能利用一列，不能充分利用2-2型車和1-2型車的上層空間，故此，根據(jù)經(jīng)驗(yàn)以及成本要求，應(yīng)考慮只選擇1-1型的上下層進(jìn)行裝配。通過上述分析，可得最終簡化的裝載方案如下：</p><p>　?。?）“高”型車：只選擇1-2型車和1-1型的下層；</p><p>　?。?）“低窄”型車：優(yōu)先選擇2-2型車和1-2型車的上層；</p>

77、;<p>　　（3）“低寬”型車：只考慮1-1型車的上下層。</p><p><b>　　圖7 關(guān)系樹</b></p><p>　　在調(diào)度的過程中，根據(jù)目的地對不同類型乘用車的需求以及上述裝載方案進(jìn)行調(diào)度。調(diào)度過程中，仍然采用啟發(fā)式的調(diào)整優(yōu)化算法，其主要遵循的原則如下：</p><p>　　根據(jù)距離的遠(yuǎn)近，按目的地E、A、B、C、

78、D的順序進(jìn)行調(diào)整優(yōu)化；</p><p>　　E地優(yōu)先選用2-2型車和1-2型車裝載；</p><p>　　A地優(yōu)先選用1-2型車裝載；</p><p>　　E地裝載后，若未滿載，則未滿載的空間裝載D地需要的乘用車，即這些車是停靠在D地卸載的；</p><p>　　A地裝載后，若未滿載，則未滿載的空間裝載B或D地需要的乘用車；</p>

79、;<p>　　C地裝載后，若未滿載，則未滿載的空間裝載D地需要的乘用車；</p><p>　　使用的1-1型與1-2型轎運(yùn)車數(shù)量要滿足題目提及的20%比例約束；</p><p>　　使用同類型轎運(yùn)車（1-1型、1-2型和2-2型車）時(shí)，優(yōu)先選擇運(yùn)輸長度較長的。</p><p>　　5.8.4 求解結(jié)果</p><p>　　首先對

80、本問中求解所得的表格進(jìn)行說明，即在表12–表20中，對以下幾種表達(dá)方式的解釋如下：“3（1）”表示3號轎運(yùn)車的第1輛車；“16D”表示需要在D處卸載車型編號為16的乘用車，并且表格中其對應(yīng)的數(shù)字就是該乘用車在D處的卸載乘用車量。</p><p>　　在對問題進(jìn)行簡化的基礎(chǔ)上，對不同的目的地分別進(jìn)行求解詳細(xì)的裝載與運(yùn)輸方案，在此基礎(chǔ)上通過matlab編程可解的相應(yīng)的可行解，然后再根據(jù)實(shí)際生活中的調(diào)度經(jīng)驗(yàn)對多得的可行

81、解進(jìn)行不斷地優(yōu)化，從而可得ABCDE五處目的地比較優(yōu)異的裝載和運(yùn)輸方案。其中目的地A的詳細(xì)裝載和運(yùn)輸方案如表12所示。</p><p>　　表12 目的地A處的乘用車裝載方案</p><p>　　對表12中所使用的轎運(yùn)車進(jìn)行統(tǒng)計(jì)，可得到目的地A所需的轎運(yùn)車類型以及相應(yīng)的數(shù)量如表13所示：</p><p>　　表13 目的地A所需的轎運(yùn)車類型與數(shù)量</p>

82、<p>　　目的地B的詳細(xì)裝載和運(yùn)輸方案如表14所示：</p><p>　　表14 目的地B處的乘用車裝載方案</p><p>　　對表14中所使用的轎運(yùn)車進(jìn)行統(tǒng)計(jì)，可得到目的地B所需的轎運(yùn)車類型以及相應(yīng)的數(shù)量如表15所示：</p><p>　　表15 目的地B所需的轎運(yùn)車類型與數(shù)量</p><p>　　目的地C的詳細(xì)裝載和運(yùn)輸

83、方案如表16所示：</p><p>　　表16 目的地C處的乘用車裝載方案</p><p>　　對表16中所使用的轎運(yùn)車進(jìn)行統(tǒng)計(jì)，可得到目的地C所需的轎運(yùn)車類型以及相應(yīng)的數(shù)量如表17所示：</p><p>　　表17 目的地C所需的轎運(yùn)車類型與數(shù)量</p><p>　　目的地D的詳細(xì)裝載和運(yùn)輸方案如表18所示：</p><

84、p>　　表18 目的地D處的乘用車裝載方案</p><p>　　對表18中所使用的轎運(yùn)車進(jìn)行統(tǒng)計(jì)，可得到目的地D所需的轎運(yùn)車類型以及相應(yīng)的數(shù)量如表19所示：</p><p>　　表19 目的地D所需的轎運(yùn)車類型與數(shù)量</p><p>　　目的地E的詳細(xì)裝載和運(yùn)輸方案如表20所示：</p><p>　　表20 目的地E處的乘用車裝載方案&

85、lt;/p><p>　　對表20中所使用的轎運(yùn)車進(jìn)行統(tǒng)計(jì)，可得到目的地E所需的轎運(yùn)車類型以及相應(yīng)的數(shù)量如表21所示：</p><p>　　表21 目的地E所需的轎運(yùn)車類型與數(shù)量</p><p>　　將上述ABCDE五處目的地所需的轎運(yùn)車類型與數(shù)量進(jìn)行綜合便可得到該物流公司在完成本次運(yùn)輸任務(wù)所需的轎運(yùn)車類型及數(shù)量如表22所示：</p><p>　　

86、表22 完成本次運(yùn)輸任務(wù)所需的轎運(yùn)車類型及數(shù)量</p><p>　　表23 完成本次運(yùn)輸任務(wù)所需各目的地的1-1、1-2和2-2型轎運(yùn)車的數(shù)量</p><p>　　由表22和表23可知，完成物流公司該次運(yùn)輸任務(wù)共需118輛轎運(yùn)車，其中包括了95輛1-1型車，18輛1-2型車和5輛2-2型車，并且到達(dá)ABCDE五處所需的轎運(yùn)車分別為34、25、29、11、19輛。同時(shí)，由題中所給地圖可知，O

87、A=360，OB=280，OC=236，OD=160，OE=384，故完成本次運(yùn)輸任務(wù)所需要行駛的總里程為35140。</p><p>　　通用性算法檢驗(yàn)與測試</p><p>　　前三問的建立的兩階段裝載優(yōu)化模型，我們實(shí)現(xiàn)了通用性算法，對算法我們進(jìn)行了測試以檢驗(yàn)其在其他輸入數(shù)據(jù)組合下的求解能力，輸入的數(shù)據(jù)如表24、表25所示：</p><p>　　表24 第一次通

88、用程序測試的輸入數(shù)據(jù)</p><p>　　表25 第二次通用程序測試的輸入數(shù)據(jù)</p><p>　　使用exe可執(zhí)行文件得到的結(jié)果為：</p><p>　　圖8 第一次通用程序測試的輸出結(jié)果</p><p>　　圖9 第二次通用程序測試的輸出結(jié)果</p><p>　　通用程序測試輸出的excel表格如表26 ~ 表29

89、所示：</p><p>　　表26 第一次通用程序測試的輸出結(jié)果</p><p>　　表27 第一次通用程序測試的輸出結(jié)果</p><p>　　表 28 第二次通用程序測試的輸出結(jié)果</p><p>　　表29第二次通用程序測試的輸出結(jié)果</p><p>　　經(jīng)過驗(yàn)證，通過上述兩次測試得到的解均為最優(yōu)解。這說明了前三問

90、所提出的通用程序具有通用性，也說明了前三問所建立的模型具有準(zhǔn)確性。</p><p><b>　　模型的評價(jià)與推廣</b></p><p>　　6.1 模型的評價(jià) </p><p>　　6.1.1 模型的優(yōu)點(diǎn)</p><p>　?。?）前三問建立的模型在生活實(shí)際應(yīng)用中具有很高的實(shí)用性或參照性，能有效的解決目的地不多，轎運(yùn)

91、車與乘用車類型不多的物流裝載問題，且該模型易于求解；</p><p>　　（2）第四問、第五問建立的所使用的轎運(yùn)車數(shù)量最少和總路程最少的雙目標(biāo)整數(shù)規(guī)劃模型是對具體問題客觀合理的抽象描述，結(jié)合啟發(fā)式算法使得問題得到簡化，所得到的解也是優(yōu)異的。</p><p>　　6.1.2 模型的缺點(diǎn)</p><p>　　（1）前三問的通用算法在一些極端情況或者特殊情況下求得的解不一

92、定是最優(yōu)的，且建立的模型在目的地變多，轎運(yùn)車與乘用車類型變多的情況下求解也是較為困難的；</p><p>　　（2）第五問的模型求解算法，由于是按照經(jīng)驗(yàn)來的，所得的解只能是一種可行解，是局部最優(yōu)的，并不是全局最優(yōu)解。</p><p><b>　　6.2 模型的推廣</b></p><p>　　本文所設(shè)計(jì)的基于經(jīng)驗(yàn)閾值的分支定界優(yōu)化算法可以很好的

93、應(yīng)用到其他的領(lǐng)域中進(jìn)行問題的求解，其中主要可以用來解決路徑、背包以及下料問題，同時(shí)，通過對閾值的設(shè)置進(jìn)行優(yōu)化將使得該改進(jìn)型的分支定界優(yōu)化算法在求解問題時(shí)能夠得到更加優(yōu)異的解。</p><p>　　第四問與第五問中所使用的啟發(fā)式算法思維也可以應(yīng)用到其他大數(shù)據(jù)分析問題中，使得其問題本身進(jìn)行簡化，降低問題的求解難度，且該啟發(fā)式思想能很好的與其他算法結(jié)合，能夠進(jìn)一步提高求解問題的能力。 </p><p

94、><b>　　參考文獻(xiàn)</b></p><p>　　張江靜，陳峰. 帶裝載組合約束的一維裝車問題算法研究[J]. 工業(yè)工程與管理, 2012, 17(3): 90-96.</p><p>　　Chu P, Beasley J. A genetic algorithm for the multi-dimensional knapsack problem[J]. J

95、ournal of Heuristics, 1998, 4: 63-86.</p><p>　　張江靜. 一維組合裝車問題模型與算法研究[D]. 上海：上海交通大學(xué), 2012.</p><p>　　高立杰. 鐵路汽車物流配載優(yōu)化研究[D]. 北京: 北京交通大學(xué), 2012.</p><p>　　熊義杰. 運(yùn)籌學(xué)教程[M]. 國防工業(yè)出版社, 2004.</

96、p><p>　　姜啟源. 數(shù)學(xué)模型[M]. 北京: 高等教育出版社, 2005.</p><p>　　徐瑞, 黃兆東等. MATLAB2007科學(xué)計(jì)算與工程分析[M]. 北京: 科學(xué)出版社, 2008.</p><p><b>　　附件</b></p><p><b>　　附件清單：</b></p

97、><p><b>　　前三問：</b></p><p>　　JM_1.exe exe可執(zhí)行文件</p><p>　　JM_1.fig fig文件（GUI界面）</p><p>　　JM_1.m fig文件對應(yīng)m文件</p><p>　　ma

98、in.m m文件主程序</p><p>　　adjust.m 方案調(diào)整函數(shù)</p><p>　　cal_loadAbility3.m 計(jì)算轎運(yùn)車裝載方案函數(shù)</p><p>　　IntProgFZ.m 分支定界法函數(shù)</p><p>　　isRight.m 驗(yàn)

99、證方案可行性函數(shù)</p><p>　　OutData.m excel結(jié)果輸出函數(shù)</p><p>　　inputData_1.xls 第1問輸入數(shù)據(jù)excel表格</p><p>　　inputData_2.xls 第2問輸入數(shù)據(jù)excel表格</p><p>　　inputData_3.xls

100、 第3問輸入數(shù)據(jù)excel表格</p><p>　　inputData_JC1.xls 測試數(shù)據(jù)excel表格</p><p>　　inputData_JC2.xls 測試數(shù)據(jù)excel表格</p><p>　　outData_1.xls 第1問結(jié)果數(shù)據(jù)輸出excel表格</p><p>　　outData_1_2.

101、xls 第1問結(jié)果數(shù)據(jù)輸出excel表格</p><p>　　outData_2.xls 第2問結(jié)果數(shù)據(jù)輸出excel表格</p><p>　　outData_2_2.xls 第2問結(jié)果數(shù)據(jù)輸出excel表格</p><p>　　outData_3.xls 第3問結(jié)果數(shù)據(jù)輸出excel表格</p><

102、;p>　　outData_3_2.xls 第3問結(jié)果數(shù)據(jù)輸出excel表格</p><p>　　outData_JC1.xls 測試數(shù)據(jù)結(jié)果輸出excel表格</p><p>　　outData_JC1_2.xls 測試數(shù)據(jù)結(jié)果輸出excel表格</p><p>　　outData_JC2.xls 測試數(shù)據(jù)結(jié)果輸出excel

103、表格</p><p>　　outData_JC2_2.xls 測試數(shù)據(jù)結(jié)果輸出excel表格</p><p><b>　　第四問：</b></p><p>　　JM_4.exe exe可執(zhí)行文件</p><p>　　JM_4.fig fig文件（GUI界面）</p&

104、gt;<p>　　JM_4.m fig文件對應(yīng)m文件</p><p>　　main.m m文件主程序</p><p>　　adjust.m 方案調(diào)整函數(shù)</p><p>　　change.m 方案優(yōu)化函數(shù)</p><p>　　cal_

105、loadAbility3.m 計(jì)算轎運(yùn)車裝載方案函數(shù)</p><p>　　question4.m 計(jì)算得到初步裝載方案函數(shù)</p><p>　　IntProgFZ.m 分支定界法函數(shù)</p><p>　　isRight.m 驗(yàn)證方案可行性函數(shù)</p><p>　　getRoad.m

106、.m 得到運(yùn)輸路徑函數(shù)，并得到excel結(jié)果輸出</p><p>　　inputData_4.xls 第4問輸入數(shù)據(jù)excel表格</p><p>　　outData_1.xls 第4問結(jié)果數(shù)據(jù)輸出excel表格</p><p>　　outData_1_2.xls 第4問結(jié)果數(shù)據(jù)輸出excel表格</p&

107、gt;<p><b>　　第五問：</b></p><p>　　main.m m文件主程序,對應(yīng)乘用車類型一裝配調(diào)整主函數(shù)</p><p>　　main2.m m文件主程序2,對應(yīng)乘用車類型二裝配調(diào)整主函數(shù)</p><p>　　main3.m m文件主程序3

108、,對應(yīng)乘用車類型三裝配調(diào)整主函數(shù)</p><p>　　cal_N.m 得到乘用車類型一裝配方案函數(shù)</p><p>　　cal_N2.m 得到乘用車類型二裝配方案函數(shù)</p><p>　　cal_N3.m 得到乘用車類型三裝配方案函數(shù)</p><p>　　adjust.m