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

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

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

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

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

5、運(yùn)車(chē)的詳細(xì)使用量如下表所示，并且完成運(yùn)輸任務(wù)所需行駛的總里程為35140。序號(hào)目的地A目的地B目的地C目的地D目的地E余量101470002070100131100011041203000520008060000025700400080115000950000010430101目的地總量342529111927轎運(yùn)車(chē)總量118關(guān)鍵詞：整車(chē)物流 整數(shù)規(guī)劃 分支定界法 經(jīng)驗(yàn)閾值 啟發(fā)式調(diào)整優(yōu)化 排樣算法一、 問(wèn)題重述1.1 問(wèn)題背景整車(chē)物流指的是按照客戶(hù)訂單對(duì)整車(chē)快速配送的全過(guò)程。隨著我國(guó)汽車(chē)工業(yè)的高速發(fā)展，整車(chē)物流量，特別是乘用車(chē)的整車(chē)物流量迅速增長(zhǎng)。乘用車(chē)生產(chǎn)廠家根據(jù)全國(guó)客戶(hù)的購(gòu)車(chē)訂單，向物流

6、公司下達(dá)運(yùn)輸乘用車(chē)到全國(guó)各地的任務(wù)，物流公司則根據(jù)下達(dá)的任務(wù)制定運(yùn)輸計(jì)劃并配送這批乘用車(chē)。為此，物流公司首先要從他們當(dāng)時(shí)可以調(diào)用的“轎運(yùn)車(chē)”中選擇出若干輛轎運(yùn)車(chē)，進(jìn)而給出其中每一輛轎運(yùn)車(chē)上乘用車(chē)的裝載方案和目的地，以保證運(yùn)輸任務(wù)的完成?！稗I運(yùn)車(chē)”是通過(guò)公路來(lái)運(yùn)輸乘用車(chē)整車(chē)的專(zhuān)用運(yùn)輸車(chē)，根據(jù)型號(hào)的不同有單層和雙層兩種類(lèi)型，而單層轎運(yùn)車(chē)實(shí)際中很少使用，本題僅考慮雙層轎運(yùn)車(chē)。在確保完成運(yùn)輸任務(wù)的前提下，物流公司追求降低運(yùn)輸成本。但由于轎運(yùn)車(chē)、乘用車(chē)有多種規(guī)格等原因，當(dāng)前很多物流公司在制定運(yùn)輸計(jì)劃時(shí)主要依賴(lài)調(diào)度人員的經(jīng)驗(yàn)，在面對(duì)復(fù)雜的運(yùn)輸任務(wù)時(shí)，往往效率低下，而且運(yùn)輸成本不盡理想。1.2 已知信息（1

7、）每種轎運(yùn)車(chē)上、下層裝載區(qū)域均可等價(jià)看成長(zhǎng)方形，各列乘用車(chē)均縱向擺放，相鄰乘用車(chē)之間縱向及橫向的安全車(chē)距均至少為0.1米，下層力爭(zhēng)裝滿(mǎn)，上層兩列力求對(duì)稱(chēng)，以保證轎運(yùn)車(chē)行駛平穩(wěn)。（2）1-1型及2-2型轎運(yùn)車(chē)上、下層裝載區(qū)域相同；第五問(wèn)中1-2型轎運(yùn)車(chē)上、下層裝載區(qū)域長(zhǎng)度相同，但上層比下層寬0.8米。（3）受層高限制，高度超過(guò)1.7米的乘用車(chē)只能裝在1-1、1-2型下層，2-2型上、下層均不能裝載高度超過(guò)1.7米的乘用車(chē)。（4）在轎運(yùn)車(chē)使用數(shù)量相同情況下，1-1型轎運(yùn)車(chē)的使用成本較低，2-2型較高，1-2型略低于前兩者的平均值，但物流公司1-2型轎運(yùn)車(chē)擁有量小，為方便后續(xù)任務(wù)安排，每次1-2型轎

8、運(yùn)車(chē)使用量不超過(guò)1-1型轎運(yùn)車(chē)使用量的20%。（5）在轎運(yùn)車(chē)使用數(shù)量及型號(hào)均相同情況下，行駛里程短的成本低。1.3 需要解決的問(wèn)題請(qǐng)為物流公司安排以下五次運(yùn)輸，制定詳細(xì)計(jì)劃，含所需要各種類(lèi)型轎運(yùn)車(chē)的數(shù)量、每輛轎運(yùn)車(chē)的乘用車(chē)裝載方案、行車(chē)路線(xiàn)。（前三問(wèn)目的地只有一個(gè)，可提供一個(gè)通用程序；后兩問(wèn)也要給出啟發(fā)式算法的程序，優(yōu)化模型則更佳）：（1）物流公司要運(yùn)輸車(chē)型的乘用車(chē)100輛及車(chē)型的乘用車(chē)68輛。（2）物流公司要運(yùn)輸車(chē)型的乘用車(chē)72輛及車(chē)型的乘用車(chē)52輛。（3）物流公司要運(yùn)輸車(chē)型的乘用車(chē)156輛、車(chē)型的乘用車(chē)102輛及車(chē)型的乘用車(chē)39輛。（4）物流公司要運(yùn)輸166輛車(chē)型的乘用車(chē)（其中目的地是A、

9、B、C、D的分別為42、50、33、41輛）和78輛車(chē)型的乘用車(chē)（其中目的地是A、C的分別為31、47輛）。（5）根據(jù)附件表1給出的物流公司需要運(yùn)輸?shù)某擞密?chē)類(lèi)型（含序號(hào))、尺寸大小、數(shù)量和目的地和附件表2給出的可以調(diào)用的轎運(yùn)車(chē)類(lèi)型（含序號(hào))、數(shù)量和裝載區(qū)域大小，采用啟發(fā)式算法，求解裝載、運(yùn)輸方案，并自行設(shè)計(jì)運(yùn)輸方案的表達(dá)形式。二、 模型假設(shè)(1) 每輛轎運(yùn)車(chē)裝載乘用車(chē)的組合是獨(dú)立的；(2) 轎運(yùn)車(chē)裝載乘用車(chē)時(shí)上下層部分是對(duì)稱(chēng)的，即數(shù)量一致；(3) 轎運(yùn)車(chē)到達(dá)目的地后原地待命，無(wú)須放空返回；(4) 轎運(yùn)車(chē)在運(yùn)輸過(guò)程中不存在往返情況；(5) 每次卸車(chē)成本可以忽略不計(jì)。三、 基本符號(hào)說(shuō)明符號(hào)符號(hào)說(shuō)明

10、符號(hào)符號(hào)說(shuō)明v_n第v輛車(chē)的裝載組合數(shù)L轎運(yùn)車(chē)的長(zhǎng)度Cvjk第v輛車(chē)第j個(gè)裝載組合裝載第k種類(lèi)型物品的容量lj第j種乘用車(chē)的長(zhǎng)度xivj物品i裝載在車(chē)輛v的第j個(gè)裝載組合c安全距離yvj車(chē)輛v選擇第j個(gè)裝載組合x(chóng)i第i種方案的使用數(shù)量Cij第i種裝載組合方案能承載第j種乘用車(chē)的數(shù)目r長(zhǎng)度余量Nj需要裝載的第j種乘用車(chē)的數(shù)量T經(jīng)驗(yàn)閾值PkO到A、B、C、D、E的距離S轎運(yùn)車(chē)的總路程bjk第j種乘用車(chē)運(yùn)往第k個(gè)目的地的數(shù)量yik第i種方案去第k個(gè)目的地四、 問(wèn)題分析本文研究的是乘用車(chē)物流運(yùn)輸計(jì)劃問(wèn)題，通過(guò)對(duì)轎運(yùn)車(chē)的空間利用率和運(yùn)輸成本進(jìn)行優(yōu)化，設(shè)計(jì)啟發(fā)式算法，以求解各種運(yùn)輸條件下詳細(xì)的裝載與運(yùn)輸方

11、案，能夠使得轎運(yùn)車(chē)的利用率達(dá)到最高、運(yùn)輸成本達(dá)到最低、行車(chē)路線(xiàn)最優(yōu)。針對(duì)題中的五個(gè)問(wèn)題，分析如下：4.1 問(wèn)題一分析題目要求給出運(yùn)輸車(chē)型的乘用車(chē)100輛及車(chē)型的乘用車(chē)68輛時(shí)物流公司的運(yùn)輸方案。本問(wèn)題即將給定數(shù)量的車(chē)型和車(chē)型乘用車(chē)裝載到1-1型轎運(yùn)車(chē)和1-2型轎運(yùn)車(chē)上，并使得所用的1-1型轎運(yùn)車(chē)和1-2型轎運(yùn)車(chē)數(shù)量之和最少，亦即成本最少。并在滿(mǎn)足數(shù)量最少的情況下，求解車(chē)型和車(chē)型乘用車(chē)的最佳裝載組合方案，以使得兩種轎運(yùn)車(chē)空間利用率達(dá)到最大。由于兩種乘用車(chē)的高度均不超過(guò)1.7米，且其寬度小于轎運(yùn)車(chē)的下層寬度、兩倍寬度也不超過(guò)轎運(yùn)車(chē)的上層寬度，即車(chē)型和車(chē)型乘用車(chē)可以裝載在1-1型和1-2型轎運(yùn)車(chē)的任

12、意層上。所以，問(wèn)題可以歸結(jié)為一維組合裝車(chē)問(wèn)題，求解的目標(biāo)是充分利用轎運(yùn)車(chē)的長(zhǎng)度，以使得轎運(yùn)車(chē)的長(zhǎng)度余量最少，則轎運(yùn)車(chē)的空間利用率也將達(dá)到最大。4.2 問(wèn)題二分析題目要求給出運(yùn)輸車(chē)型的乘用車(chē)72輛及車(chē)型的乘用車(chē)52輛時(shí)物流公司的運(yùn)輸方案。本問(wèn)題即將給定數(shù)量的車(chē)型和車(chē)型乘用車(chē)裝載到1-1型轎運(yùn)車(chē)和1-2型轎運(yùn)車(chē)上，并使得所用的1-1型轎運(yùn)車(chē)和1-2型轎運(yùn)車(chē)數(shù)量之和最少，亦即成本最少。并在滿(mǎn)足數(shù)量最少的情況下，求解車(chē)型和車(chē)型乘用車(chē)的最佳裝載組合方案，以使得兩種轎運(yùn)車(chē)空間利用率達(dá)到最大。由于車(chē)型乘用車(chē)的高度大于1.7米，根據(jù)題目中的要求，只能將其裝載在1-1型和1-2型轎運(yùn)車(chē)的下層上。而車(chē)型的乘用車(chē)，

13、仍然可以裝載在1-1型和1-2型轎運(yùn)車(chē)的任意層。問(wèn)題仍為求解一維組合裝車(chē)問(wèn)題，求解的目標(biāo)是充分利用轎運(yùn)車(chē)的長(zhǎng)度，以使得轎運(yùn)車(chē)的長(zhǎng)度余量最少。 4.3 問(wèn)題三分析題目要求給出運(yùn)輸車(chē)型的乘用車(chē)156輛、車(chē)型的乘用車(chē)102輛及車(chē)型的乘用車(chē)39輛時(shí)物流公司的運(yùn)輸方案。本問(wèn)題即將給定數(shù)量的車(chē)型、車(chē)型和車(chē)型乘用車(chē)裝載到1-1型轎運(yùn)車(chē)和1-2型轎運(yùn)車(chē)上，并使得所用的1-1型轎運(yùn)車(chē)和1-2型轎運(yùn)車(chē)數(shù)量之和最少，亦即成本最少。并在滿(mǎn)足數(shù)量最少的情況下，求解車(chē)型、車(chē)型和車(chē)型乘用車(chē)的最佳裝載組合方案，以使得兩種轎運(yùn)車(chē)空間利用率達(dá)到最大。此問(wèn)題可以看作是前兩問(wèn)的延伸，此時(shí)1-1型轎運(yùn)車(chē)和1-2型轎運(yùn)車(chē)下層均可以裝載三

14、種乘用車(chē)，而上層只能裝載車(chē)型和車(chē)型轎運(yùn)車(chē)。4.4 問(wèn)題四分析題目要求給出運(yùn)輸166輛車(chē)型的乘用車(chē)（其中目的地是A、B、C、D的分別為42、50、33、41輛）和78輛車(chē)型的乘用車(chē)（其中目的地是A、C的分別為31、47輛）時(shí)物流公司的運(yùn)輸方案。本問(wèn)題可以看作是問(wèn)題一的延伸，在問(wèn)題一的基礎(chǔ)上將路徑加入到了考慮之列，目的地不再相同。問(wèn)題變成將給定數(shù)量的車(chē)型和車(chē)型乘用車(chē)裝載到1-1型轎運(yùn)車(chē)和1-2型轎運(yùn)車(chē)上，并運(yùn)往相應(yīng)的目的地，以滿(mǎn)足各目的地的需求，使得運(yùn)輸成本最少。而影響運(yùn)輸成本的首要因素是轎運(yùn)車(chē)使用數(shù)量，其次是行駛里程長(zhǎng)短。因而問(wèn)題轉(zhuǎn)換為求解車(chē)型和車(chē)型乘用車(chē)的最佳裝載組合方案，以使得兩種轎運(yùn)車(chē)的使

15、用總數(shù)量最小且所需的路程最短。這是一個(gè)雙目標(biāo)規(guī)劃問(wèn)題，此時(shí)轎運(yùn)車(chē)有可能不再滿(mǎn)足滿(mǎn)載的條件。4.5 問(wèn)題五分析題目要求利用10種不同規(guī)格轎運(yùn)車(chē)，來(lái)裝載45種不同規(guī)格的乘用車(chē)，以滿(mǎn)足A、B、C、D、E五個(gè)目的地對(duì)45種乘用車(chē)的數(shù)量需求。本問(wèn)題可以看作是問(wèn)題四的擴(kuò)展研究，只是問(wèn)題比第四問(wèn)要復(fù)雜的多，但整體的模型是一致的。對(duì)于這種NP難問(wèn)題，尋找最優(yōu)解是不切實(shí)際的，需要重新設(shè)計(jì)啟發(fā)式算法，簡(jiǎn)化目標(biāo)函數(shù)，使其更容易求解，以期能夠求得滿(mǎn)足約束條件的可行解。五、 問(wèn)題求解與算法設(shè)計(jì)5.1裝載問(wèn)題的基本模型5.1.1 模型定性分析在不考慮整車(chē)目的地和轎運(yùn)車(chē)的路徑選擇的情況下，問(wèn)題可抽象為帶裝載組合約束的一維裝

16、車(chē)問(wèn)題1，即有n個(gè)屬于l種類(lèi)型的相同（單位）尺寸的物品，有w輛車(chē)，每輛車(chē)對(duì)這l種類(lèi)型的物品有幾種裝載組合，不同車(chē)輛的裝載組合不同，每輛車(chē)選擇一種裝載組合并嚴(yán)格按照物品組合進(jìn)行裝載。優(yōu)化目標(biāo)是在滿(mǎn)載的情況下裝載最多的物品，同時(shí)給出每個(gè)物品的具體配載方案。5.1.2 復(fù)雜性分析考慮帶裝載組合約束的一維裝車(chē)問(wèn)題的簡(jiǎn)化問(wèn)題，當(dāng)每輛車(chē)只有一個(gè)裝載組合時(shí)，問(wèn)題變?yōu)椋河衛(wèi)種類(lèi)型的物品，類(lèi)型k的物品數(shù)Nk，有n個(gè)裝載組合，第j個(gè)裝載組合對(duì)類(lèi)型k物品的容量Cjk，對(duì)所有類(lèi)型物品的容量Cj，選擇裝載組合以盡可能裝載最多的物品。已知多維背包問(wèn)題為NP難問(wèn)題2，而多維背包問(wèn)題可以轉(zhuǎn)化為一維組合裝車(chē)問(wèn)題的簡(jiǎn)化問(wèn)題，則一

17、維組合裝車(chē)問(wèn)題的簡(jiǎn)化問(wèn)題為NP難問(wèn)題，顯然一維組合裝車(chē)問(wèn)題更為復(fù)雜，也即一維組合裝車(chē)問(wèn)題為NP難問(wèn)題。5.1.3 一維組合裝車(chē)問(wèn)題線(xiàn)性混合整數(shù)規(guī)劃模型3問(wèn)題最終結(jié)果是給出具體的裝載方案，即物品裝載在哪輛車(chē)的哪個(gè)裝載組合上，因此以物品作為決策主體，物品選擇車(chē)輛、裝載組合。設(shè)物品數(shù)為m,類(lèi)型數(shù)為l，車(chē)輛數(shù)為w，第v輛車(chē)的裝載組合數(shù)為v_n，第v輛車(chē)第j個(gè)裝載組合裝載第k種類(lèi)型物品的容量為Cvjk, xivj為物品i是否裝載在車(chē)輛v的第j個(gè)裝載組合上的0、1變量，yvj為車(chē)輛v是否選擇第j個(gè)裝載組合的0、1變量，則有如下數(shù)學(xué)模型： (5-1)優(yōu)化目標(biāo)為物品裝載數(shù)最多；約束式第一式表示一輛車(chē)最多只能選

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

19、，我們簡(jiǎn)化為考慮轎運(yùn)車(chē)的空間利用率最大，為此，建立了兩階段裝載優(yōu)化模型4。5.2.2 裝載組合方案的確定在給定運(yùn)輸任務(wù)的乘用車(chē)類(lèi)型后，根據(jù)各乘用車(chē)的規(guī)格和各裝載用轎運(yùn)車(chē)的規(guī)格，首先確定1-1型和1-2型轎運(yùn)車(chē)每層可以裝載的乘用車(chē)類(lèi)型，然后依據(jù)1-1型和1-2型轎運(yùn)車(chē)的實(shí)際長(zhǎng)度，再加上縱向的安全車(chē)距的限制，采用窮舉法，可以確立各類(lèi)型轎運(yùn)車(chē)的所有裝載組合。假定轎運(yùn)車(chē)的長(zhǎng)度為L(zhǎng)，第j種乘用車(chē)的長(zhǎng)度為lj（j = 1, 2, 3分別代表型、型、型），并用kj表示裝載組合中承載的第j種乘用車(chē)的數(shù)目，安全距離c=0.1，滿(mǎn)足要求的裝載組合方案應(yīng)滿(mǎn)足（只考慮單個(gè)下層的情況，其它層類(lèi)似）： （5-2）5.2.

20、3 兩階段裝載優(yōu)化模型（1）第一階段：空間利用率最大化優(yōu)化模型 a）目標(biāo)函數(shù)的確定考慮到無(wú)論是使用1-1型轎運(yùn)車(chē)還是1-2型轎運(yùn)車(chē)，均采用雙層裝載。而且為了安全，下層裝載的是重心高度較高的乘用車(chē)，如車(chē)型乘用車(chē)。再者，車(chē)型和車(chē)型乘用車(chē)的寬度均在轎運(yùn)車(chē)的允許范圍之內(nèi)。因此，轎運(yùn)車(chē)在裝載乘用車(chē)時(shí)，在高度和寬度上并不存在利用的概念，在最大化空間利用率時(shí)僅需考慮長(zhǎng)度的充分利用即可，而具體裝載輛數(shù)取決于乘用車(chē)的類(lèi)型。設(shè)Ci，j表示第i種裝載組合方案能承載第j種乘用車(chē)的數(shù)目（i = 1, 2， , m, m+1, , M，m為使用1-1型轎運(yùn)車(chē)的最大方案數(shù)，M為分別使用1-1型、1-2型轎運(yùn)車(chē)的總方案數(shù)之和

21、；j = 1, 2, 3, 4, 5, 分別表示上（型車(chē)放在上層，后面依次類(lèi)推）、上、下、下、下五種情況），n表示轎運(yùn)車(chē)的列數(shù)（1-1型為2, 1-2型為3, 2-2型為4），則目標(biāo)函數(shù)可以表示為：（5-3） b）約束條件的確定轎運(yùn)車(chē)裝載時(shí)，應(yīng)保證乘用車(chē)與乘用車(chē)之間，乘用車(chē)與轎運(yùn)車(chē)端壁之間的最小間隙, 避免發(fā)生碰撞，此安全距離為0.1米，同時(shí)應(yīng)滿(mǎn)足轎運(yùn)車(chē)的裝載長(zhǎng)度約束。即，滿(mǎn)足的約束條件如下： （5-4）（2）第二階段：運(yùn)輸成本最小化優(yōu)化模型 a）目標(biāo)函數(shù)的確定由于影響整車(chē)物流運(yùn)輸成本高低的主要因素首先是轎運(yùn)車(chē)使用數(shù)量，其次是在轎運(yùn)車(chē)使用數(shù)量相同情況下的轎運(yùn)車(chē)使用成本，最后是行駛里程成本。而在

22、前三問(wèn)的模型中，不考慮路徑問(wèn)題，因而我們以轎運(yùn)車(chē)的使用數(shù)量最少為主要考慮因素，對(duì)組合方案進(jìn)行優(yōu)化，以使運(yùn)輸成本最小。設(shè)第i種方案的使用數(shù)量為xi(i = 1, 2， , m, m+1, , M)，則目標(biāo)函數(shù)為： （5-5） b）約束條件的確定由于1-1型轎運(yùn)車(chē)的使用成本較低，2-2型較高，1-2型略低于前兩者的平均值。為了降低成本，應(yīng)使1-2型轎運(yùn)車(chē)使用量少于1-1型轎運(yùn)車(chē)，且每次1-2型轎運(yùn)車(chē)使用量不超過(guò)1-1型轎運(yùn)車(chē)使用量的20%，這也符合物流公司1-2型轎運(yùn)車(chē)擁有量小的實(shí)際；再者，無(wú)論采用哪些組合方案，都必須滿(mǎn)足物流公司的運(yùn)輸安排，努力完成任務(wù)。即，滿(mǎn)足的約束條件如下： （5-6）其中，

23、Nj為需要裝載的第j種乘用車(chē)的數(shù)量。5.2.4基于經(jīng)驗(yàn)閾值的求解優(yōu)化方法考慮到在求解上述兩階段裝載優(yōu)化模型時(shí)，問(wèn)題歸結(jié)為一個(gè)雙目標(biāo)規(guī)劃問(wèn)題，實(shí)際求解時(shí)較為困難。為此，對(duì)問(wèn)題進(jìn)行重新分析，空間利用率最大可以等價(jià)為長(zhǎng)度余量最少，而組合方案的求解時(shí)也可以通過(guò)考慮長(zhǎng)度余量來(lái)進(jìn)行分析。設(shè)長(zhǎng)度余量為r，則 （5-7）根據(jù)實(shí)際情況，r應(yīng)滿(mǎn)足非負(fù)的要求。由于每種方案的長(zhǎng)度余量不同，但對(duì)于每種類(lèi)型的轎運(yùn)車(chē)的所有裝載組合方案，其長(zhǎng)度余量必有一個(gè)取值范圍，我們可以考慮人為的給定一個(gè)閾值。這樣可以對(duì)組合方案進(jìn)行有目的的篩選，也可以解決因窮舉法產(chǎn)生的“組合爆炸”問(wèn)題，同時(shí)也考慮了空間利用率最大。因而，求解兩階段裝載優(yōu)化

24、問(wèn)題最終歸結(jié)為一個(gè)整數(shù)規(guī)劃問(wèn)題 （5-8） 其中，T為閾值，根據(jù)經(jīng)驗(yàn)獲得，在本文的計(jì)算中，T取2。5.3 裝載優(yōu)化模型的通用求解算法設(shè)計(jì)5.3.1 求解整數(shù)規(guī)劃的分支定界算法分支定界算法是一種隱枚舉法,是整數(shù)規(guī)劃中常用的算法之一5。它的主要思想是根據(jù)某種策略將原問(wèn)題松弛問(wèn)題的可行域分解為越來(lái)越小的子域, 并檢查每個(gè)子域內(nèi)整數(shù)解的情況, 直到找到最優(yōu)整數(shù)解或證明整數(shù)解不存在。分支定界法從求松弛問(wèn)題開(kāi)始, 將問(wèn)題可行域分為許多的子域(最通常的分解方式是“兩分法”),這一過(guò)程稱(chēng)為分支；通過(guò)分支找到更好的整數(shù)解來(lái)不斷的修改問(wèn)題的上下解,這一過(guò)程稱(chēng)為定界。定界的目的是為了測(cè)定界的趨勢(shì),留下有價(jià)值的或尚不

25、能判定的分支。刪除肯定不存在最優(yōu)解的分支, 稱(chēng)之為剪枝, 以達(dá)到加速收斂, 簡(jiǎn)化運(yùn)算的目的。不同的分支定界方法在于分支、定界和剪枝的不同處理手段上, 其算法的一般步驟可概括為：Step1：初始化。選擇可行域的S的初始松弛集合F，滿(mǎn)足；初始可行點(diǎn)集合，上界，令P=F，計(jì)算下界，并令。在計(jì)算的過(guò)程中，若有必要，則更新Q和。Step2：分割。將F分割成有限個(gè)子集Fi，（指標(biāo)集）滿(mǎn)足，令。Step3：剪枝。對(duì)每個(gè)，計(jì)算f 在子集Fi 上的下界，使其滿(mǎn)足，利用在計(jì)算)的過(guò)程中所發(fā)現(xiàn)的所有可行點(diǎn)修正集合Q，同時(shí)按照合適的刪除規(guī)則，刪除P中所有不包含最優(yōu)解的Fi或Fi的一部分，剩余集合不妨仍記為P；Step

26、4：定界。令，。Step5：終止判斷。若（充分小的正數(shù)），則終止算法。否則，從P中挑選合適的子集F，轉(zhuǎn)入步驟2。5.3.2 啟發(fā)式調(diào)整優(yōu)化啟發(fā)式算法3是一種基于直觀或經(jīng)驗(yàn)構(gòu)造的算法,在可接受的花費(fèi)(指計(jì)算時(shí)間和空間)下給出待解決組合優(yōu)化問(wèn)題每一個(gè)實(shí)例的一個(gè)可行解,該可行解與最優(yōu)解的偏離程度不一定事先可以預(yù)計(jì)。利用分支定界法求解整數(shù)規(guī)劃問(wèn)題（5-8）所得的解有時(shí)并不是最優(yōu)解，此時(shí)就需要進(jìn)行調(diào)整，這時(shí)只需要在保證轎運(yùn)車(chē)總數(shù)量不變的情況下，對(duì)可行解進(jìn)行啟發(fā)式的局部調(diào)整即可。這種啟發(fā)式的調(diào)整思路大致如下：（1） 放寬閾值T，擴(kuò)大解的范圍；（2） 根據(jù)經(jīng)驗(yàn)，將新解范圍中的某一種方案的數(shù)量與可行解相應(yīng)的方

27、案數(shù)量進(jìn)行替換；（3） 驗(yàn)證新的解是否滿(mǎn)足約束條件，如果新解滿(mǎn)足約束條件且新解的轎運(yùn)車(chē)數(shù)量總數(shù)不超過(guò)可行解，則新解即為可能的最優(yōu)解；（4） 在這些所有可能的最優(yōu)解中，尋找轎運(yùn)車(chē)數(shù)目最少的即為最優(yōu)解。啟發(fā)式算法簡(jiǎn)單直觀，速度快，容易被接受，但在最壞情況下，也不能獲得最優(yōu)解，這時(shí)就只能通過(guò)人工干預(yù)進(jìn)行調(diào)整，以獲得最優(yōu)解。5.3.3 通用算法設(shè)計(jì)圖1 通用算法流程圖本文通過(guò)前三問(wèn)的求解，歸納總結(jié)出了一種適合求解前三問(wèn)的通用算法，并用一個(gè)通用程序進(jìn)行了實(shí)現(xiàn)。所實(shí)現(xiàn)的通用程序，能夠滿(mǎn)足前三問(wèn)運(yùn)輸任務(wù)，并能按照題目要求輸入輸出最優(yōu)解。算法的流程圖如圖1所示，這里，簡(jiǎn)單敘述一下通用算法的主要步驟：Step1

28、：分別輸入轎運(yùn)車(chē)與乘用車(chē)的規(guī)格數(shù)據(jù)（長(zhǎng)、寬、高），并輸入需要運(yùn)輸?shù)娜N乘用車(chē)的數(shù)量，如果沒(méi)有某種乘用車(chē)，則輸入0；Step2：通過(guò)（5-2）式來(lái)計(jì)算所有可能的轎運(yùn)車(chē)裝載方案，并進(jìn)行編號(hào)；Step3：利用分支定界法求解式（5-8）所示的整數(shù)規(guī)劃問(wèn)題，并對(duì)所求得的解進(jìn)行驗(yàn)證，如果求得的解就是最優(yōu)解，則轉(zhuǎn)到Step6；否則繼續(xù)；Step4：按照上節(jié)所述的啟發(fā)式調(diào)整優(yōu)化方法繼續(xù)求解優(yōu)化，尋找最優(yōu)解，并對(duì)所求得的解進(jìn)行驗(yàn)證，如果所得的解即是最優(yōu)解，則轉(zhuǎn)到Step6；否則繼續(xù)；Step5：對(duì)上步所得的可行解進(jìn)行人工干預(yù)，局部小范圍調(diào)整方案，以獲得最優(yōu)解；Step6：按照題目要求輸出裝載方案與所需轎運(yùn)車(chē)數(shù)量

29、的Excel格式。5.4 問(wèn)題一求解本問(wèn)題中，N1=100，N2=68，N3=0，帶入式（5-8）中，可得問(wèn)題一的具體模型為： （5-9）將N1=100，N2=68，N3=0輸入到通用程序中，可以求得11種裝載組合方案，如表1所示，其中前5種為使用1-1型轎運(yùn)車(chē)時(shí)的所有可能裝載組合方案，后6種為使用1-2型轎運(yùn)車(chē)時(shí)的所有可能裝載組合方案。表1 問(wèn)題一的所有可能裝載組合方案方案數(shù)目方案1方案2方案3方案4方案5方案6方案7方案8方案9方案10方案11上層裝載型乘用車(chē)數(shù)目432101086420上層裝載型乘用車(chē)數(shù)目0123502481012下層裝載型乘用車(chē)數(shù)目43210543210下層裝載型乘用車(chē)

30、數(shù)目01235012456最終求得的所有裝載方案情況如表2所示：表2 問(wèn)題一的裝載方案轎運(yùn)車(chē)類(lèi)型相同類(lèi)型、相同裝載方式的車(chē)輛數(shù)裝在上層序號(hào)為1乘用車(chē)數(shù)量裝在上層序號(hào)為2乘用車(chē)數(shù)量裝在上層序號(hào)為3乘用車(chē)數(shù)量裝在下層序號(hào)為1乘用車(chē)數(shù)量裝在下層序號(hào)為2乘用車(chē)數(shù)量裝在上層序號(hào)為3乘用車(chē)數(shù)量中間?？康啬康牡?-1型11400400001-1型5050050001-2型248024000統(tǒng)計(jì)的轎運(yùn)車(chē)數(shù)量，如表3所示：表3 問(wèn)題一的轎運(yùn)車(chē)數(shù)量統(tǒng)計(jì)轎運(yùn)車(chē)類(lèi)型使用總車(chē)輛數(shù)1-1型161-2型2利用MATLAB軟件實(shí)現(xiàn)了前三問(wèn)通用算法的exe可執(zhí)行文件，其第一問(wèn)運(yùn)行結(jié)果如圖2所示。圖2中，讀取的excel表格名字

31、為“inputData_1”，輸出了inputData_1.xls中輸入的乘用車(chē)數(shù)量以及通過(guò)算法所得到的不同類(lèi)型轎運(yùn)車(chē)數(shù)量，其具體轎運(yùn)車(chē)裝載方案輸出并保存在了outData_1.xls與outData_1_2.xls中。圖2 第一問(wèn)運(yùn)行結(jié)果5.5 問(wèn)題二求解本問(wèn)題中，N1=0，N2=72，N3=52，帶入式（5-8）中，可得問(wèn)題二的具體模型為： （5-10）將N1=0，N2=72，N3=52輸入到通用程序中，可以求得9種裝載組合方案，如表4所示，其中前4種為使用1-1型轎運(yùn)車(chē)時(shí)的所有可能裝載組合方案，后5種為使用1-2型轎運(yùn)車(chē)時(shí)的所有可能裝載組合方案。表4 問(wèn)題二的所有可能裝載組合方案方案數(shù)目

32、方案1方案2方案3方案4方案5方案6方案7方案8方案9上層裝載型乘用車(chē)數(shù)目55551212121212下層裝載型乘用車(chē)數(shù)目012301245下層裝載型乘用車(chē)數(shù)目432154321最終求得的所有裝載方案情況如表5所示：表5 問(wèn)題二的裝載方案轎運(yùn)車(chē)類(lèi)型相同類(lèi)型、相同裝載方式的車(chē)輛數(shù)裝在上層序號(hào)為1乘用車(chē)數(shù)量裝在上層序號(hào)為2乘用車(chē)數(shù)量裝在上層序號(hào)為3乘用車(chē)數(shù)量裝在下層序號(hào)為1乘用車(chē)數(shù)量裝在下層序號(hào)為2乘用車(chē)數(shù)量裝在上層序號(hào)為3乘用車(chē)數(shù)量中間?？康啬康牡?-1型12050004001-2型1012000500統(tǒng)計(jì)的轎運(yùn)車(chē)數(shù)量，如表6所示：表6 問(wèn)題二的轎運(yùn)車(chē)數(shù)量統(tǒng)計(jì)轎運(yùn)車(chē)類(lèi)型使用總車(chē)輛數(shù)1-1型121

33、-2型1利用MATLAB軟件實(shí)現(xiàn)了前三問(wèn)通用算法的exe可執(zhí)行文件，其第一問(wèn)運(yùn)行結(jié)果如圖3所示。圖3中，讀取的excel表格名字為“inputData_2”，輸出了inputData_2.xls中輸入的乘用車(chē)數(shù)量以及通過(guò)算法所得到的不同類(lèi)型轎運(yùn)車(chē)數(shù)量，其具體轎運(yùn)車(chē)裝載方案輸出并保存在了outData_2.xls與outData_2_2.xls中。圖3 第二問(wèn)運(yùn)行結(jié)果5.6 問(wèn)題三求解本問(wèn)題中，N1=156，N2=102，N3=39，帶入式（5-8）中，可得問(wèn)題三的具體模型為： （5-11） 將N1=156，N2=102，N3=39輸入到通用程序中，由于此時(shí)得到的所有可能裝載組合方案達(dá)到了140

34、種，所以不再列出。最終求得的所有裝載方案情況如表7所示：表7 問(wèn)題三的裝載方案轎運(yùn)車(chē)類(lèi)型相同類(lèi)型、相同裝載方式的車(chē)輛數(shù)裝在上層序號(hào)為1乘用車(chē)數(shù)量裝在上層序號(hào)為2乘用車(chē)數(shù)量裝在上層序號(hào)為3乘用車(chē)數(shù)量裝在下層序號(hào)為1乘用車(chē)數(shù)量裝在下層序號(hào)為2乘用車(chē)數(shù)量裝在上層序號(hào)為3乘用車(chē)數(shù)量中間?？康啬康牡?-1型1050031001-1型1400004001-1型5400202001-1型11400301001-1型2050202001-1型5050301001-2型548014100統(tǒng)計(jì)的轎運(yùn)車(chē)數(shù)量，如表8所示：表8 問(wèn)題三的轎運(yùn)車(chē)數(shù)量統(tǒng)計(jì)轎運(yùn)車(chē)類(lèi)型使用總車(chē)輛數(shù)1-1型251-2型5我們用MATLAB軟件實(shí)

35、現(xiàn)了前三問(wèn)通用算法的exe可執(zhí)行文件，其運(yùn)行結(jié)果如圖4所示。圖4中，讀取的excel表格名字為“inputData_3”，輸出了inputData_3.xls中輸入的乘用車(chē)數(shù)量以及通過(guò)算法所得到的不同類(lèi)型轎運(yùn)車(chē)數(shù)量，其具體轎運(yùn)車(chē)裝載方案輸出并保存在了outData_3.xls與outData_3_2.xls中。圖4 第三問(wèn)運(yùn)行結(jié)果5.7 問(wèn)題四求解與算法設(shè)計(jì)5.7.1 模型建立本問(wèn)題中，N1=166，N2=78，N3=0，只考慮的是型和型乘用車(chē)，所有可能裝載組合方案如表1所示。按照運(yùn)輸成本最少的要求，只需要在這些可能的裝載組合方案中，選取某些方案數(shù)，并考慮采用每種方案的轎運(yùn)車(chē)數(shù)量，以使總的轎運(yùn)

36、車(chē)數(shù)量最少，盡最大可能的滿(mǎn)足各目的地對(duì)型和型乘用車(chē)的數(shù)量要求，同時(shí)使得轎運(yùn)車(chē)的總路程最少即可。設(shè)，Pk表示O到A、B、C、D的距離，（k = 1, 2, 3, 4, 分別代表A、B、C、D），則可以建立如下雙目標(biāo)規(guī)劃模型： （5-12）此雙目標(biāo)規(guī)劃問(wèn)題也屬于整數(shù)規(guī)劃問(wèn)題，當(dāng)然也可以使用分支定界法進(jìn)行求解。故在此問(wèn)的求解中我們?nèi)允褂蒙厦嫠龅耐ㄓ盟惴ㄟM(jìn)行求解，也將問(wèn)題按兩階段處理，先考慮轎運(yùn)車(chē)數(shù)量最少，尋找較優(yōu)解，然后在這些解中尋找路徑最優(yōu)的解，即為所求。5.7.2 啟發(fā)式調(diào)整優(yōu)化算法與前三問(wèn)不同的是，在求解時(shí)的啟發(fā)式調(diào)整優(yōu)化算法，這里簡(jiǎn)述如下：（1） 根據(jù)圖5所示的路線(xiàn)圖，確定距離O點(diǎn)距離最遠(yuǎn)

37、的點(diǎn)，如A；（2） 優(yōu)先考慮距離最遠(yuǎn)的點(diǎn)。為了減少行駛成本，對(duì)于最遠(yuǎn)的點(diǎn)應(yīng)盡可能減少轎運(yùn)車(chē)的數(shù)量，所以盡可能的采用1-2型轎運(yùn)車(chē)裝載乘用車(chē)，運(yùn)往目的地A；（3） 再考慮次最遠(yuǎn)點(diǎn)，如B。如仍有1-2型轎運(yùn)車(chē)剩余，則優(yōu)先考慮使用1-2型轎運(yùn)車(chē)，否則就只能采用1-1型轎運(yùn)車(chē)；（4） 接著考慮C點(diǎn)（OCOB）。根據(jù)A、B的運(yùn)輸量以及每次1-2型轎運(yùn)車(chē)使用量不超過(guò)1-1型轎運(yùn)車(chē)使用量的20%的約束，可以確定在C點(diǎn)時(shí)，不會(huì)有1-2型轎運(yùn)車(chē)剩余，所以只能采用1-1型轎運(yùn)車(chē)；（5） 最后考慮D點(diǎn)。由于去A、B、C點(diǎn)均要經(jīng)過(guò)D點(diǎn)，在滿(mǎn)足A、B、C運(yùn)輸量需求的情況下，有時(shí)可能轎運(yùn)車(chē)并不能達(dá)到滿(mǎn)載，為了充分利用轎運(yùn)

38、車(chē)的空間，可以再裝上一定數(shù)目的乘用車(chē)，到了D點(diǎn)卸車(chē)即可。EBACDO圖5 路線(xiàn)圖5.7.3 求解結(jié)果最終求得的所有裝載方案情況如表9所示：表9 問(wèn)題四的裝載方案轎運(yùn)車(chē)類(lèi)型相同類(lèi)型、相同裝載方式的車(chē)輛數(shù)裝在上層序號(hào)為1乘用車(chē)數(shù)量裝在上層序號(hào)為2乘用車(chē)數(shù)量裝在上層序號(hào)為3乘用車(chē)數(shù)量裝在下層序號(hào)為1乘用車(chē)數(shù)量裝在下層序號(hào)為2乘用車(chē)數(shù)量裝在上層序號(hào)為3乘用車(chē)數(shù)量中間?？康赝？康匦遁d序號(hào)為1乘用車(chē)數(shù)量?？康匦遁d序號(hào)為1乘用車(chē)數(shù)量目的地1-2型2480240000A1-2型1470500000A1-2型11000500000A1-1型1400400B20A1-1型6400400000B1-1型405005

39、0000C1-1型1220050000C1-1型3400400000C1-1型1400400D10C1-1型5400400000D統(tǒng)計(jì)的轎運(yùn)車(chē)數(shù)量，如表10所示：表10 問(wèn)題四的轎運(yùn)車(chē)數(shù)量統(tǒng)計(jì)轎運(yùn)車(chē)類(lèi)型使用總車(chē)輛數(shù)1-1型211-2型4此時(shí)，轎運(yùn)車(chē)的總路程S為S=(2+1+1+1)*360+6*280+(4+1+3+1)*236+5*160=6404我們用MATLAB軟件實(shí)現(xiàn)了第四問(wèn)算法的exe可執(zhí)行文件，其運(yùn)行結(jié)果如圖6所示。圖6中，讀取的excel表格名字為“inputData_4”，輸出了inputData_4.xls中輸入的乘用車(chē)數(shù)量以及通過(guò)算法所得到的不同類(lèi)型轎運(yùn)車(chē)數(shù)量，其具體轎運(yùn)車(chē)

40、裝載方案輸出并保存在了outData_4.xls與outData_4_2.xls中。圖6 第四問(wèn)運(yùn)行結(jié)果5.8 問(wèn)題五求解與算法設(shè)計(jì)5.8.1 模型建立本問(wèn)題可以看作是問(wèn)題四的擴(kuò)展研究，此時(shí)，乘用車(chē)類(lèi)型增加到45， 轎運(yùn)車(chē)種類(lèi)增加到10，目的地增加到5，優(yōu)化目標(biāo)仍與第四問(wèn)相同，參照（5-12）的雙目標(biāo)規(guī)劃模型，可以得到如下模型： （5-13） 其中，mh表示第h種轎運(yùn)車(chē)在所有組合方案中的位置下標(biāo)（h=0, 1, , 10; m0=0），bjk表示第j種乘用車(chē)運(yùn)往第k個(gè)目的地的數(shù)量。5.8.2 基于排樣算法的裝載優(yōu)化算法在求解（5-13）所示的優(yōu)化模型時(shí)，為避免釆用窮舉法出現(xiàn)的“組合爆炸”，可采

41、用基于排樣算法的裝載優(yōu)化算法來(lái)解決該問(wèn)題4。由于該算法與汽車(chē)運(yùn)輸設(shè)備的規(guī)格尺寸、所到目的地密切相關(guān)，因此結(jié)合運(yùn)輸汽車(chē)專(zhuān)用車(chē)的結(jié)構(gòu)尺寸、所到目的地，可設(shè)計(jì)基于排樣算法的汽車(chē)裝載優(yōu)化算法如下：Step l：根據(jù)轎運(yùn)車(chē)裝載乘用車(chē)的限高尺度，初步確定轎運(yùn)車(chē)可以裝載的乘用車(chē)類(lèi)型；Step 2：根據(jù)乘用車(chē)及轎運(yùn)車(chē)的規(guī)格尺寸，進(jìn)一步對(duì)轎運(yùn)車(chē)可以裝載的乘用車(chē)類(lèi)型進(jìn)行劃分；Step 3：依據(jù)待裝乘用車(chē)不同類(lèi)型的目的地需求，構(gòu)建關(guān)系樹(shù)；Step 4：根據(jù)待裝乘用車(chē)的關(guān)系樹(shù)以及啟發(fā)式調(diào)整優(yōu)化算法（見(jiàn)下文所述），初步選擇配載方案；Step 5：驗(yàn)證配載方案是否滿(mǎn)足約束條件；若不滿(mǎn)足，則回到Step4；滿(mǎn)足，則進(jìn)入下一

42、步；Step6：確定各種轎運(yùn)車(chē)裝載乘用車(chē)的方案。根據(jù)上述算法，結(jié)合實(shí)際待裝乘用車(chē)的長(zhǎng)度及轎運(yùn)車(chē)的類(lèi)型，我們將待裝乘用車(chē)劃分為“高”、“低窄”、“低寬”三種車(chē)型?！案摺钡臉?biāo)準(zhǔn)是：乘用車(chē)高度大于1.7米；“低窄”的標(biāo)準(zhǔn)是：乘用車(chē)高度不超過(guò)1.7米且寬度不超過(guò)1.7米；“低寬”的標(biāo)準(zhǔn)是：乘用車(chē)高度不超過(guò)1.7米且寬度大于1.7米。最終的乘用車(chē)分類(lèi)結(jié)果如下表所示：表11 乘用車(chē)分類(lèi)結(jié)果車(chē)型高低窄低寬乘用車(chē)編號(hào)1,12,17,24,25,26,31,373,5,7,8,14,18,20,27,29,30,34,39,402,4,6,9,10,11,13,15,16,19,21,22,23,28,32,3

43、3,35,36,38,41,42,43,44,45接著，按照待裝乘用車(chē)的三種類(lèi)型以及五個(gè)目的地對(duì)乘用車(chē)的需求，可得到具體的關(guān)系樹(shù)，如圖7所示。5.8.3 啟發(fā)式調(diào)整優(yōu)化算法根據(jù)附表中給出的轎運(yùn)車(chē)數(shù)據(jù)，可以看出，對(duì)于“高”型車(chē)，只能裝載在1-2型車(chē)的下層和1-1型的下層；對(duì)于“低窄”型車(chē)，可以裝載在任意類(lèi)型的轎運(yùn)車(chē)上，但根據(jù)經(jīng)驗(yàn)，應(yīng)盡可能的選擇2-2型車(chē)和1-2型車(chē)的上層進(jìn)行裝載，這樣可以最大限度的利用2-2型車(chē)和1-2型車(chē)的上層空間，使其裝載的“低窄”型車(chē)數(shù)量最大化，這樣將使其空間得到充分利用，又能減少轎運(yùn)車(chē)的成本；對(duì)于“低寬”型車(chē)，可以裝載在1-1型的上下層，2-2型車(chē)和1-2型車(chē)的下層，上

44、層由于考慮到要使兩列對(duì)稱(chēng)，如果裝載“低寬”型車(chē)將只能利用一列，不能充分利用2-2型車(chē)和1-2型車(chē)的上層空間，故此，根據(jù)經(jīng)驗(yàn)以及成本要求，應(yīng)考慮只選擇1-1型的上下層進(jìn)行裝配。通過(guò)上述分析，可得最終簡(jiǎn)化的裝載方案如下：（1）“高”型車(chē)：只選擇1-2型車(chē)和1-1型的下層；（2）“低窄”型車(chē)：優(yōu)先選擇2-2型車(chē)和1-2型車(chē)的上層；（3）“低寬”型車(chē)：只考慮1-1型車(chē)的上下層。圖7 關(guān)系樹(shù)在調(diào)度的過(guò)程中，根據(jù)目的地對(duì)不同類(lèi)型乘用車(chē)的需求以及上述裝載方案進(jìn)行調(diào)度。調(diào)度過(guò)程中，仍然采用啟發(fā)式的調(diào)整優(yōu)化算法，其主要遵循的原則如下：（1） 根據(jù)距離的遠(yuǎn)近，按目的地E、A、B、C、D的順序進(jìn)行調(diào)整優(yōu)化；（2）

45、E地優(yōu)先選用2-2型車(chē)和1-2型車(chē)裝載；（3） A地優(yōu)先選用1-2型車(chē)裝載；（4） E地裝載后，若未滿(mǎn)載，則未滿(mǎn)載的空間裝載D地需要的乘用車(chē)，即這些車(chē)是?？吭贒地卸載的；（5） A地裝載后，若未滿(mǎn)載，則未滿(mǎn)載的空間裝載B或D地需要的乘用車(chē)；（6） C地裝載后，若未滿(mǎn)載，則未滿(mǎn)載的空間裝載D地需要的乘用車(chē)；（7） 使用的1-1型與1-2型轎運(yùn)車(chē)數(shù)量要滿(mǎn)足題目提及的20%比例約束；（8） 使用同類(lèi)型轎運(yùn)車(chē)（1-1型、1-2型和2-2型車(chē)）時(shí)，優(yōu)先選擇運(yùn)輸長(zhǎng)度較長(zhǎng)的。5.8.4 求解結(jié)果首先對(duì)本問(wèn)中求解所得的表格進(jìn)行說(shuō)明，即在表12表20中，對(duì)以下幾種表達(dá)方式的解釋如下：“3（1）”表示3號(hào)轎運(yùn)車(chē)的

46、第1輛車(chē)；“16D”表示需要在D處卸載車(chē)型編號(hào)為16的乘用車(chē)，并且表格中其對(duì)應(yīng)的數(shù)字就是該乘用車(chē)在D處的卸載乘用車(chē)量。在對(duì)問(wèn)題進(jìn)行簡(jiǎn)化的基礎(chǔ)上，對(duì)不同的目的地分別進(jìn)行求解詳細(xì)的裝載與運(yùn)輸方案，在此基礎(chǔ)上通過(guò)matlab編程可解的相應(yīng)的可行解，然后再根據(jù)實(shí)際生活中的調(diào)度經(jīng)驗(yàn)對(duì)多得的可行解進(jìn)行不斷地優(yōu)化，從而可得ABCDE五處目的地比較優(yōu)異的裝載和運(yùn)輸方案。其中目的地A的詳細(xì)裝載和運(yùn)輸方案如表12所示。表12 目的地A處的乘用車(chē)裝載方案裝載方案序號(hào)目的地A乘用車(chē)車(chē)型編號(hào)1轎運(yùn)車(chē)序號(hào)（編號(hào)）2416D3（1）上層裝載量221下層裝載量52轎運(yùn)車(chē)序號(hào)（編號(hào)）232816D14D3（2）上層裝載量41下層裝載量1313轎運(yùn)車(chē)序號(hào)（編號(hào)）463（3）上層裝載量41下層裝載量414轎運(yùn)車(chē)序號(hào)（編號(hào)）693（4）上層裝載量41下層裝載量415轎運(yùn)車(chē)序號(hào)（編號(hào)）113（5）上層裝載量5下層裝載量56轎運(yùn)車(chē)序號(hào)（編號(hào)）910113（6）上層裝載量131下層裝載量1317轎運(yùn)車(chē)序號(hào)（編號(hào)）133（7）上層裝載量5下層裝載量58轎運(yùn)車(chē)序號(hào)（編號(hào)）13151