基于整數(shù)規(guī)劃模型的乘用車最優(yōu)運(yùn)輸方案

周靖靖 劉金杰 張萬里

(1.重慶師范大學(xué)經(jīng)濟(jì)與管理學(xué)院，重慶 401331;2.重慶師范大學(xué)數(shù)學(xué)學(xué)院，重慶 401331)

1 問題敘述

物流問題是近年來的研究熱點(diǎn)之一。張騰松研究了整車物流配送路徑的優(yōu)化設(shè)計(jì)［1］。陳賽虎利用整數(shù)規(guī)劃模型研究了轎車物流配載的優(yōu)化問題［2］。秦緒偉等人研究了整車物流網(wǎng)絡(luò)的集成優(yōu)化問題［3］。本次研究主要解決2014年全國研究生數(shù)學(xué)建模競(jìng)賽提出的乘用車最優(yōu)運(yùn)輸問題。具體問題背景如下:

雙層轎運(yùn)車又分為3種子型:上下層各裝載1列乘用車，故記為1-1型;上層裝載2列，下層裝載1列，記為1-2型;上、下層各裝載2列，記為2-2型，每輛轎運(yùn)車可以裝載乘用車6～27輛。

裝載具體要求:每種轎運(yùn)車上、下層裝載區(qū)域均可視為長(zhǎng)方形，各列乘用車均縱向擺放，相鄰乘用車之間縱、橫向安全車距均至少保持0.1 m，下層力爭(zhēng)裝滿，上層兩列力求對(duì)稱，以保證轎運(yùn)車行駛平穩(wěn)。受層高限制，高度超過1.7 m的乘用車只能裝在1-1型和1-2型的下層。乘用車、轎運(yùn)車規(guī)格見表1和表2。

各因素關(guān)系:影響成本的要素首先是轎運(yùn)車使用數(shù)量;其次，在轎運(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%;再次，在轎運(yùn)車使用數(shù)量及型號(hào)均相同的情況下，行駛里程短的成本較低。

表2 轎運(yùn)車規(guī)格 m

因?yàn)樵撐锪鞴臼侨珖怨?，在各地均?huì)有整車物流業(yè)務(wù)，所以轎運(yùn)車到達(dá)目的地后原地待命，無須放空返回。每次卸車成本幾乎可以忽略。

公司安排2次運(yùn)輸，在此需要制定詳細(xì)計(jì)劃，含所需各種類型轎運(yùn)車的數(shù)量、每輛轎運(yùn)車的乘用車裝載方案。需要建立模型解決以下問題:

(1)最低成本下，物流公司運(yùn)輸Ⅰ車型的乘用車100輛及Ⅱ車型的乘用車68輛。

(2)最低成本下，物流公司運(yùn)輸Ⅱ車型的乘用車72輛及Ⅲ車型的乘用車52輛。

2 模型假設(shè)

(1)僅考慮雙層轎運(yùn)車型號(hào);

(2)不考慮卸車成本;

(3)轎運(yùn)車在運(yùn)行過程中不會(huì)發(fā)生故障;

(4)轎運(yùn)車到達(dá)目的地后原地待命，無須放空返回;

(5)各列乘用車均縱向擺放;

(6)假設(shè)各類轎運(yùn)車的裝載區(qū)域和乘用車均是長(zhǎng)方形。

模型中各符號(hào)說明見表1。

表1 模型中各符號(hào)說明

3 模型建立及求解

為確定乘用車的最優(yōu)運(yùn)輸方案，結(jié)合經(jīng)典貪婪算法思想，在此給出改進(jìn)的貪婪算法。算法主要步驟如下:

Step 1:輸入乘用車的數(shù)量和類型，轉(zhuǎn)Step 2;

Step 2:計(jì)算能夠裝載全部乘用車所需的轎運(yùn)車型號(hào)及其最少數(shù)量，轉(zhuǎn)Step 3;

Step 3:按每類轎運(yùn)車裝載后剩余空間最小為目標(biāo)安排計(jì)算所需乘用車類型和數(shù)量轉(zhuǎn)Step 4;

Step 4:計(jì)算具有相同裝載方案的乘運(yùn)車數(shù)量;并計(jì)算出每輛轎運(yùn)車上層的裝載方案;最后計(jì)算每類乘用車剩余數(shù)量，轉(zhuǎn)Step 3;

Step 5:輸出每輛轎運(yùn)車的裝載方案，結(jié)束。

3.1 問題(1)的模型建立及求解

3.1.1 確定最少轎運(yùn)車車輛使用數(shù)

假設(shè)需要1-1型轎運(yùn)車n1輛，1-2型轎運(yùn)車n2輛，需要進(jìn)行裝載的Ⅰ車型乘用車有c1輛，Ⅱ車型乘用車有c2輛，則轎運(yùn)車的使用數(shù)量越少越符合物流公司節(jié)約成本的要求［7］，因此目標(biāo)函數(shù)為min(n1+n2)。又由每次1-2型轎運(yùn)車使用量不超過1-1型轎運(yùn)車使用量的20%，故有n2≤20%n1。首先考慮1-1型轎運(yùn)車與1-2型轎運(yùn)車的下層寬度，w1和w2≤W1，w1和w2≤W2;再考慮1-2型轎運(yùn)車的上層寬度:

將需要運(yùn)輸?shù)某擞密嚾靠v向擺放，應(yīng)滿足在安全車距下其總長(zhǎng)度小于轎運(yùn)車運(yùn)載長(zhǎng)度之和。因此有:

建立以轎運(yùn)車車輛數(shù)最少為目標(biāo)的整數(shù)規(guī)劃模型:

3.1.2 確定每輛轎運(yùn)車的最優(yōu)裝載方案

(1)考慮每輛1-2型轎運(yùn)車的乘用車裝載方案。在此前已將1-2型轎運(yùn)車上下層裝載平面轉(zhuǎn)化為3個(gè)長(zhǎng)為L(zhǎng)2的長(zhǎng)方形，裝載后剩下的空間長(zhǎng)度min D1最少，即裝載方案使得L2的長(zhǎng)度充分利用。建立模型:

(模型1-2)min D1

其中k11為L(zhǎng)2長(zhǎng)度內(nèi)所需Ⅰ型乘用車的數(shù)量，k12為L(zhǎng)2長(zhǎng)度內(nèi)所需Ⅱ型乘用車的數(shù)量。

求得k11與k12后，計(jì)算需要安排的乘用車數(shù)量:

(2)考慮每輛1-1型轎運(yùn)車的乘用車裝載方案。前面已將裝載平面轉(zhuǎn)化為2個(gè)長(zhǎng)為L(zhǎng)1的長(zhǎng)方形，由此建立裝載后剩余空間長(zhǎng)度最少的模型:

模型1-3 min D2

其中k21為L(zhǎng)1長(zhǎng)度內(nèi)所需Ⅰ型乘用車的數(shù)量，k22為L(zhǎng)1長(zhǎng)度內(nèi)所需Ⅱ型乘用車的數(shù)量。

求得k21與k22后計(jì)算剩余乘用車數(shù)量:

對(duì)c1(2)與c2(2)進(jìn)行判斷。若c1(2)與c2(2)大于0，則剩余c1(2)輛Ⅰ型乘用車和c2(2)輛Ⅱ型乘用車，此時(shí)則額外分配1輛1-1型轎運(yùn)車運(yùn)載;否則，若c1(2)，c2(2)均小于等于0，則裝配方案成立。

3.1.3 問題(1)的計(jì)算

令 c1(0)=100，c2(0)=60，使用 Matlab 7.11［6］軟件編程計(jì)算可得問題(1)的最優(yōu)裝載方案如表3所示。

表3 Ⅰ車型(100輛)與Ⅱ車型(68輛)乘用車的最優(yōu)運(yùn)輸方案

3.2 問題(2)的模型建立及求解

3.2.1 確定最少轎運(yùn)車車輛使用數(shù)

設(shè)需要1-1型轎運(yùn)車n1輛，1-2型轎運(yùn)車n2輛，Ⅱ型乘用車有c2(0)輛，Ⅲ型乘用車有c3(0)輛，Δl為兩車間隔。結(jié)合物流公司成本節(jié)約要求及車型限制，可建立以轎運(yùn)車車輛數(shù)最少為目標(biāo)的整數(shù)線性優(yōu)化模型:

模型2-1 min(n1+n2)

3.2.2 確定每輛轎運(yùn)車的裝載方案

(1)考慮每輛1-2型轎運(yùn)車最佳運(yùn)載方案。安排1-2型轎運(yùn)車下層裝載方案:設(shè)1-2型轎運(yùn)車下層L2長(zhǎng)度內(nèi)可以安排k21輛Ⅱ型乘用車，k31輛Ⅲ型乘用車。

模型2-2 min D3

求得k21與k31后計(jì)算接下來需要安排的乘用車數(shù)量:

安排1-2型車上層裝載方案。

模型2-3 min D32

式中k22表示1-2型轎運(yùn)車L2長(zhǎng)度內(nèi)裝載的Ⅱ型乘用車數(shù)量。

計(jì)算安排完1-2型轎運(yùn)車上下層后，乘用車的剩余數(shù)量:

(2)考慮每輛1-1型轎運(yùn)車最佳運(yùn)載方案。安排1-1型轎運(yùn)車下層裝載方案:設(shè)1-1型轎運(yùn)車下層安排k23輛Ⅱ型乘用車，k32輛Ⅲ型乘用車，則有:

模型2-4 min D41

求得k23與k32后計(jì)算接下來需要安排的乘用車數(shù)量:

安排1-1型轎運(yùn)車上層裝載方案:設(shè)1-1型車上層安排k24輛Ⅱ型乘用車，則有:

模型2-5 min D42

計(jì)算安排完1-1型轎運(yùn)車上下層后乘用車的剩余數(shù)量:

對(duì)c2(4)和c3(4)進(jìn)行判斷:若c2(4)與c3(4)大于0，則剩余c2(4)輛Ⅱ型乘用車和c3(4)Ⅲ型乘用車，此時(shí)則額外分配1輛1-1型轎運(yùn)車進(jìn)行運(yùn)載;否則，若c2(4)與c3(4)小于等于0，則裝配方案成立。

3.2.3 問題(2)的求解

令c2(0)=72，c3(0)=52，用Matlab 7.11編程計(jì)算可得問題(2)的最優(yōu)裝載方案，見表4。

表4 Ⅱ車型(72輛)與Ⅲ車型(52輛)乘用車的最優(yōu)運(yùn)輸方案

［1］張騰松.SQ公司整車物流配送路徑優(yōu)化研究［D］.大連:大連海事大學(xué)，2012.

［2］陳賽虎.基于整數(shù)規(guī)劃的轎車物流配載優(yōu)化的研究［D］.上海:上海交通大學(xué)，2008.

［3］秦緒偉，范玉順，尹朝萬.整車物流網(wǎng)絡(luò)規(guī)劃集成優(yōu)化模型研究［J］.計(jì)算機(jī)集成制造系統(tǒng)，2006，12(3):364-370.

［4］陳建嶺.集裝箱裝載問題的啟發(fā)式優(yōu)化算法［J］.山東交通學(xué)院學(xué)報(bào)，2006，13(3):53-56.

［5］何鳳志，劉家財(cái).安吉物流裝車道位利用率優(yōu)化設(shè)計(jì)［J］.物流工程與管理，2014，36(5):107-109.

［6］張志涌，楊祖櫻.MATLAB教程［M］.北京:北京航空航天大學(xué)出版社，2006.