李 鵬，竇霽虹，仲文林，盧克英

(西北大學數(shù)學學院，陜西西安710127)

基于乘用車物流運輸模型程序算法的分析

李 鵬，竇霽虹，仲文林，盧克英

(西北大學數(shù)學學院，陜西西安710127)

基于第十一屆“華為杯”全國研究生數(shù)學建模競賽E題，針對一類乘用車物流運輸問題，首先建立了單目的地乘用車運輸優(yōu)化模型；其次通過在遺傳算法中構(gòu)造新的適應(yīng)度函數(shù)對模型求解，得到較優(yōu)的運載方案。該程序算法對直接利用軟件或Java Web技術(shù)解決一般的乘用車物流運輸計劃問題提供了新的算法思想。

乘用車物流運輸；遺傳算法；適應(yīng)度函數(shù)；程序算法

隨著我國乘用車的整車物流量迅速增長，制定一個最佳的乘用車物流運輸計劃直接關(guān)系到物流公司的經(jīng)濟收益和發(fā)展狀況。但由于轎運車、乘用車有多種規(guī)格等原因，當前很多物流公司在制定運輸計劃時主要依賴調(diào)度人員的經(jīng)驗，面對復雜的運輸任務(wù)時，往往效率低下，而且運輸成本不盡理想。因此，建立一個合理的乘用車物流運輸計劃的數(shù)學模型變得至關(guān)重要，然后將模型中蘊含的數(shù)學思想轉(zhuǎn)化為程序算法，從而將數(shù)學問題轉(zhuǎn)化為計算機程序問題，極大地提高了應(yīng)用計算機解決實際問題的能力。因此，針對數(shù)學模型建立和算法分析的研究是很有價值的[1]。

圖1 1-1型轎運車

圖2 1-2轎運車

本文只針對文獻[1]中的前3問建立通用模型，在模型求解方面給出程序算法分析。為簡化分析，故作如下假設(shè)：

1)相鄰乘用車距離縱向和橫向距離按0.1 m計算；

2)裝載時，假設(shè)每輛乘用車的車身不能超出轎運車的邊緣線；

3)假設(shè)轎運車到達目的地后原地待命，無需放空返回；

4)轎運車足夠多，滿足所有運輸任務(wù)；

5)“裝滿”是指在滿足要求的情況下，不能再裝入任何類型的乘用車；

6)乘用車的重量對于運輸成本的影響忽略；

通過分析可得，該實際問題為雙目標的最優(yōu)化模型[2]。

1 模型的建立

ni表示1-t型轎運車的數(shù)量；m1表示Ⅰ型乘用車的數(shù)量，m2表示Ⅱ型乘用車的數(shù)量，m3表示Ⅲ型乘用車的數(shù)量；xij(k)(s.t)表示第s型的第i輛乘用車裝在第t型的第j輛轎運車的第k層；其中，xij(1)(s.t)表示第s型的第i輛乘用車裝在第t型的第j輛轎運車的上層，xij(2)(s,t)表示第s型的第i輛乘用車裝在第t型的第j輛轎運車的下層，s=1，2，3；k=1，2；t=1，2；i=1，2，…，ms；j=1，2，…，nt。具體符號說明如表1。

表1 有關(guān)轎運車-乘用車符號標記

由表1可以清楚得看出：任意一輛乘用車在物流運輸中的具體裝載方式，因此這樣的標記方式具有一定的科學性。

經(jīng)分析，該實際問題屬于雙目標規(guī)劃問題[2]。接下來根據(jù)題意并結(jié)合實際，深度挖掘數(shù)據(jù)信息，在模型建立之前確定目標函數(shù)和決策變量、尋找約束條件。

(1)目標函數(shù)

在確保完成運輸任務(wù)的前提下，物流公司追求降低運輸成本，影響成本高低的首先是轎運車使用數(shù)量；其次，在轎運車使用數(shù)量相同情況下，1-1型轎運車的使用成本較低，2-2型較高，1-2型略低于前兩者的平均值，用P1表示1-1型轎運車的使用成本，用P2表示1-2型轎運車的使用成本，則P1

本問題為總成本盡可能低和轎運車的數(shù)量盡可能小的雙目標規(guī)劃問題，目標函數(shù)如下：

(2)決策變量

根據(jù)以上的分析，nt和xi(k)(s,t)為決策變量(t=1,2)，其中

(3)約束條件

1-1型與1-2型兩種轎運車數(shù)量關(guān)系的約束：

為方便后續(xù)任務(wù)安排，每次1-2型轎運車使用量不超過1-1型轎運車使用量的20%，所有的1-1型車的數(shù)量為n1，所有的1-2型車的數(shù)量為n2，則有：

20%n1≥n2

(1)

Ⅲ型乘用車的約束：

受層高限制，高度超過1.7 m的乘用車只能裝在1-1、1-2型下層，因此在實際裝載中，Ⅲ型乘用車只能裝在1-1、1-2型轎運車的下層，不能裝載在1-1、1-2型轎運車的上層，即

xij(1)(3,t)=0 (t=1,2)

(2)

轎運車車長的約束：

每一輛轎運車上裝載的所有乘用車的縱向擺放，相鄰乘用車之間縱向及橫向的安全車距均至少為0.1m。1-2的上層只能裝載運輸Ⅰ、Ⅱ型乘用車，1-2的上層，本題只考慮縱向距離。對1-1型轎運車而言，上下兩層均單列裝載，轎運車每層上裝載的所有乘用車的縱向距離加上各個相鄰乘用車的0.1 m，應(yīng)該小于該轎運車的車長，因此有：

(k=1，2；j=1，2，…，n1)

(3)

對1-2型轎運車而言，下層單列裝載，同上有：

(j=1,2,…n2)

(4)

由于1-2型轎運車的上層裝載2列乘用車，該層上裝載的所有乘用車的縱向距離加上各個相鄰乘用車的0.1 m，應(yīng)該小于該轎運車的車長的兩倍，則：

(j=1,2,…,n2)

(5)

轎運車最大數(shù)量約束：

每輛轎運車可以裝載乘用車的最大數(shù)量在6到27輛之間，則：

t=1,2

(6)

下層盡量裝滿的約束：

題目要求“下層力爭裝滿”，我們理解的“裝滿”是在滿足要求的情況下，不能再裝入任何類型的乘用車，即最后所剩的長度比Ⅰ型、Ⅱ型、Ⅲ型三者車上的最小值ε還小就裝滿了，其中

ε=min(4.61，3.615，4.63)+0.1=3.715

那么就得到下面關(guān)系式：

(7)

上層兩列力求對稱的約束：

根據(jù)直觀性分析：1-2型轎運車的上層可以裝載兩列乘用車，為了保證轎運車行駛平穩(wěn)，上層兩列裝載時力求對稱。當1-2的上層所裝的同一類型的乘用車數(shù)量為偶數(shù)時，顯然能夠保證轎運車行駛平穩(wěn)，即

s=1,2,3；j=1,2,…,n2

(8)

以上是根據(jù)題意和對數(shù)據(jù)信息深度挖掘后得到：決策變量與目標函數(shù)間的約束關(guān)系，在數(shù)學建模過程中，這部分工作屬于難點部分。

綜上，建立單目的地的乘用車運輸模型：

2 遺傳算法及適應(yīng)度函數(shù)的構(gòu)造

模型的求解我們選擇遺傳算法[3]來尋找可行解，遺傳算法(Genetic Algorithm)是一種通過模擬自然進化過程搜索最優(yōu)解的方法，其中選擇、交叉和變異構(gòu)成了遺傳算法的遺傳操作，遺傳算法在解決優(yōu)化問題時，最主要的特征是：不在單點上尋優(yōu)，而是從整個種群中選擇生命力強的個體產(chǎn)生新的種群，應(yīng)用隨機轉(zhuǎn)換原理時，遺傳算法得到結(jié)果好壞，主要依賴于遺傳代數(shù)和解組規(guī)模。在實際中，可根據(jù)具體要求，在合理的時間內(nèi)對問題求解，如果得到的解不滿足要求，則可以增加遺傳代數(shù)或是解組規(guī)模，有望得到問題的全局最優(yōu)解，當然這是以延長計算時間為代價的?；具z傳算法的流程圖如圖3所示：

圖3 遺傳算法的流程圖

從實際的整車物流運輸出發(fā)，并由簡單到復雜逐步考慮，層層深入，如此會為解決乘用車物流運輸計劃問題提供寶貴的模型思想和簡單算法。因此需要通過直觀性分析計算出1-1和1-2型轎運車的所有滿載方案，具體方案如表2和表3。

表2 1-1型轎運車裝載方案

表3 1-2型轎運車裝載方案

為了清晰地表達，做符號說明：(pi(k),qi(k),ri(k))表示轎運車的第k層上裝有pi(k)輛Ⅰ型乘用車、qi(k)輛Ⅱ型乘用車、ri(k)輛Ⅲ型乘用車這類方案，?i表示第i種方案；At為t型轎運車的車長(t=1，2分別表示1-1型和1-2型轎運車)。為了更好地體現(xiàn)裝載剩余的空間，定義第i個裝載方案的“裝載效率”為：

其中ri為第i個運載方案中剩余的空間。將遺傳算法及其思想應(yīng)用到乘車物流運輸模型中，具體步驟如下[4]：

第一步：隨機產(chǎn)生初始種群，即從所有可能的裝載運輸方案中隨機m種1-1型轎運車的裝載方案、n種1-2型轎運車的裝載方案，如下表：

第二步：確定收斂準則

要完成所有的裝載運輸任務(wù)，裝載的i型乘用車的總量不少于需要裝載的i型乘用車的數(shù)量Ni，i=1，2，3，定義“剔除函數(shù)”g1、g2、g3：

第三步：適應(yīng)函數(shù)的構(gòu)造

為了剔除在約束條件下“明顯”不是最優(yōu)的裝載方案，建立適應(yīng)函數(shù)：

這樣便能逐步迭代，剔除“明顯”不是最優(yōu)的裝載方案，最后找出最優(yōu)解或次優(yōu)解。

3 模型結(jié)果

應(yīng)用以上算法思想并采用Java-web技術(shù)對模型求解。

表4 模型結(jié)果

注：模型結(jié)果不唯一，原因是采用遺傳算法時，初值點的選取是由計算機自動隨機生成，具有任意性，但是模型的結(jié)果都符合實際，真實有效，可供物流公司參考，從而采取最佳運輸方案。

根據(jù)模型思想和遺傳算法的程序算法思想，將數(shù)學問題轉(zhuǎn)化為計算機程序問題，極大地提高了應(yīng)用計算機解決實際問題的能力。

該實際問題必須借助計算機程序來執(zhí)行，程序有許多，如C語言、C++、Java-web和MATLAB等。但是多個計算機程序共同的算法是相同的，因此本文的核心工作是提供算法思想和算法分析。

[1]http：//www.madio.net/thread-223965-1-1.html.

[2]董文永，劉進，丁建立，等.最優(yōu)化技術(shù)與數(shù)學建模[M].北京：清華大學出版社，2010.

[3]張磊.汽車整車配載與路線優(yōu)化方案及算法研究[J].計算機技術(shù)與發(fā)展，2011，2(6)：199-222.

[4]王占鋒.求解非滿載車輛調(diào)度問題的改進遺傳算法[J].計算機工程與設(shè)計，2008，2(15)：3991-3996.

[責任編輯 畢 偉]

Based on Analysis of Passenger Transport Modeling Program Algorithm

LI PENG,DOU Ji-hong,ZHONG Wen-lin,LU Ke-ying

(School of Mathematics,Northwest University,Xi′an 710127,China)

Based on the E question of the eleventh Graduate Mathematical Modeling,which is related to a class of passenger transport and logistics problems.Firstly,a single destination for passenger transport optimization model is established; secondly a new fitness function of genetic algorithms is constructed when solving the model.This algorithm provides new algorithms ideas for the direct use of the software program or Java web technology to solve the general problem of passenger transport and logistics plan.

passenger transport logistics; genetic algorithms; fitness function; program algorithm

2014-12-19

陜西省教育廳自然科學專項基金(CU0631206030001)

李 鵬(1988-)，男，山西忻州人，西北大學在讀碩士研究生。

O232

A

1004-602X(2015)02-0059-04