乘用車物流運(yùn)輸計劃問題

周建軍，張 順，臧碧蓮，林道榮

（1.南京工程學(xué)院，江蘇 南京 211167；2.南通大學(xué) 理學(xué)院，江蘇 南通 226019）

乘用車物流運(yùn)輸計劃問題

周建軍1，張 順2，臧碧蓮2，林道榮2

（1.南京工程學(xué)院，江蘇 南京 211167；2.南通大學(xué) 理學(xué)院，江蘇 南通 226019）

對于整車物流問題，先研究每輛轎運(yùn)車有效的乘用車各種方案，從裝載方案、行車路線、目的地、區(qū)分上、下層等角度引入基于運(yùn)輸需求的轎運(yùn)車數(shù)量的決策變量，建立了整數(shù)線性規(guī)劃模型，并利用啟發(fā)式算法求解了該模型，主要是考慮順帶問題，使總成本較低。

轎運(yùn)車；乘用車；整車物流；運(yùn)輸計劃；整數(shù)線性規(guī)劃模型；啟發(fā)式算法

1 引言

整車物流指的是按照客戶訂單對整車快速配送的全過程。近年來，隨著我國汽車工業(yè)的高速發(fā)展和國內(nèi)整車物流量，特別是乘用車的整車物流量的日益迅速增長[1]，而國內(nèi)大多數(shù)物流公司在制定運(yùn)輸計劃時主要依賴于調(diào)度人員的經(jīng)驗，在面對復(fù)雜的運(yùn)輸任務(wù)時，效率低下且運(yùn)輸成本相對較高。因此，乘用車物流運(yùn)輸優(yōu)化問題已經(jīng)成為物流領(lǐng)域研究的熱點問題，受到了諸多學(xué)者的關(guān)注[2]。物流公司在確保完成乘用車生產(chǎn)廠家所下達(dá)的任務(wù)的前提下，制定科學(xué)、有效且詳細(xì)的運(yùn)輸計劃十分必要，從而實現(xiàn)物流成本的最小化，提高整車物流的工作效率，推動社會經(jīng)濟(jì)的迅速發(fā)展[3]。

本文通過研究整車物流的運(yùn)輸規(guī)劃問題，經(jīng)過問題分析可知，要用經(jīng)典的運(yùn)輸問題線性規(guī)劃模型來描述整車物流并不可行，由于運(yùn)輸問題的宗旨是運(yùn)價或運(yùn)輸成本最低，而運(yùn)價或運(yùn)輸成本是所派轎運(yùn)車輛數(shù)的線性函數(shù)，故可通過建立線性規(guī)劃模型求解，通過實際應(yīng)用，驗證了模型的可行性。

2 模型的建立

2.1 問題分析

乘用車物流運(yùn)輸規(guī)劃問題是一類運(yùn)輸方案，而對于平衡運(yùn)輸問題，可以建立線性規(guī)劃模型利用表上作業(yè)法解決[4]。對于整車物流運(yùn)輸問題，其宗旨是運(yùn)價或運(yùn)輸成本最低，而運(yùn)價或運(yùn)輸成本是所派轎運(yùn)車輛數(shù)的線性函數(shù)（系數(shù)為運(yùn)輸距離與所行里程運(yùn)價），可以想象此問題可以建立線性規(guī)劃模型進(jìn)行求解。作為線性規(guī)劃問題有三大要素：一是確定合理的決策變量，二是目標(biāo)函數(shù)，三是給出約束條件[5]。

對于乘用車物流問題，可考慮轎運(yùn)車裝載乘用車，并且可雙層裝載，由于車輛長度限制，應(yīng)保證乘用車前后、左右的間距為0.1m，轎運(yùn)車有上、下兩層，可用Q表示轎運(yùn)車的類型量，q表示第q型轎運(yùn)車的上層，q=1,2,...,Q，Q+q表示第q型轎運(yùn)車的下層，Mq表示第q型轎運(yùn)車的擁有量。對于乘用車，可用L表示乘用車的類型量，l為乘用車的類型序號，表示第l型乘用車，l=1,2,...,L。由于轎運(yùn)車上下層的裝載方式不同，用nq表示第q型轎運(yùn)車上層充分裝載乘用車的方案數(shù)，nQ+q表示第Q+q型轎運(yùn)車下層充分裝載乘用車的方案數(shù)。用

表示對于第q型轎運(yùn)車的上層采用第i種裝載方式裝載的第l型乘用車的數(shù)量，兩列時保持兩側(cè)對稱，表示對于第q型轎運(yùn)車的下層采用第i種裝載方式裝載的第l型乘用車的數(shù)量，兩列時保持兩側(cè)對稱。引入的決策變量是數(shù)值本身應(yīng)當(dāng)是基于運(yùn)輸需求的轎運(yùn)車的數(shù)量。

整車物流的運(yùn)輸成本計算較為復(fù)雜，可以這樣簡化：與轎運(yùn)車使用量x成正比，與行駛里程hq(q =1,2,...,Q )成正比，與轎運(yùn)車車型有關(guān)，引入運(yùn)價系數(shù)Kq(q=1,2,...,Q)來解決，這樣x輛第q型轎運(yùn)車行駛里程hq(q =1,2,...,Q )的運(yùn)輸成本表示為Kqhqx。在此基礎(chǔ)上對運(yùn)輸路線累加，再對轎運(yùn)車車型累加即得總成本。

對于約束條件，由于轎運(yùn)車有上下兩層，因此為了充分利用轎運(yùn)車的上下兩層，必須考慮在一定條運(yùn)輸路線上，同一種轎運(yùn)車的上層數(shù)量是應(yīng)當(dāng)?shù)扔谙聦訑?shù)量，這理解為平行約束，并且限制條件要注意各轎運(yùn)車的使用量要分別小于運(yùn)載乘用車所需的轎運(yùn)車的數(shù)量。約束最重要的是需求約束，注意到目的地有兩類，一類是終點性目的地，另一類是中轉(zhuǎn)型目的地。用 Z表示目的地的總數(shù)，z表示第 z個目的地，z=1,2,...,Z。對于目的地需求量，用Pil表示第i個目的地對第l型乘用車的總需求量或起點的待運(yùn)量。Plz表示第z個目的地對第l型乘用車的需求量。對于終點性目的地的，到達(dá)這一終點性目的地的各種類型乘用車的運(yùn)輸是分別不小于該目的地各種類型乘用車的需求量；而對于中轉(zhuǎn)型目的地，應(yīng)考慮經(jīng)過這一中轉(zhuǎn)性目的地運(yùn)輸路線上的其他目的地遠(yuǎn)離起點的方向，所有到達(dá)這些目的地的各種類型的乘用車的運(yùn)數(shù)量之和分別不小于這些目的地各種類型乘用車的需求量。

2.2 轎運(yùn)車的可裝載方案

每輛轎運(yùn)車裝載乘用車是有效裝載。所謂有效的乘用車裝載方案是指：一是一層雙列排時需左右對稱裝載乘用車；二是一列盡可能轎運(yùn)車，直到未能裝載為止，或有車位限制時，每個車位裝載一輛乘用車，車位位置可前后適當(dāng)調(diào)整；三是裝載乘用車時保證乘用車前后、左右的間距（規(guī)定0.1m）。

對于每輛轎運(yùn)車的裝載可構(gòu)建模型如下：若整個裝載過程分為M步，規(guī)定轎運(yùn)車最大載重量為G，整個轎運(yùn)車的裝載空間為V(X ,Y,Z)，其中X表示長，Y表示寬，Z表示z軸方向的長度。如果有n種乘用車，數(shù)量依次為l1,l2,???,ln，每個乘用車的體積為vj(j=1,2,???,n)，可用vj(xj,yj,zj)表示第 j種型號的箱子的體積，其中 xj,yj,zj(j =1,2,???,n )分別表示長、寬、高，重量為gj(j=1,2,???,n)，lij表示第i步裝入第 j種型號乘用車的個數(shù)，Li為第i步裝載后n種型號乘用車擺放乘用車的總數(shù)量?？蓸?gòu)建只有約束條件沒有目標(biāo)函數(shù)的可裝載方式模型：

約束條件為：

對于上述建立的模型，由于沒有目標(biāo)函數(shù)，只有約束條件，可利用LINGO軟件進(jìn)行求解。LINGO軟件可以解決只有約束條件，沒有目標(biāo)函數(shù)的組合（規(guī)劃）問題。

2.3 轎運(yùn)車的派發(fā)

2.3.1 一般優(yōu)化模型形式。對于決策變量：如果從起點到每一個目的地只有單一運(yùn)輸路線，表示對第z個目的地的需求量，在轎運(yùn)車上層選用第 j種裝載方式裝載乘用車所需第q型轎運(yùn)車的數(shù)量，其中q=1,2,...,Q;z=1,2,...,Z;j=1,2,...,nQ+q；+q表示對第z個目的地的需求量，在轎運(yùn)車下層選用第 j種裝載方式裝載乘用車所需第q型轎運(yùn)車的數(shù)量。

如果從起點到一些目的地有多種運(yùn)輸路線，這樣的目的地記為 A1,A2,...,Az0，這里1≤z≤Z0對于目的地Az(1 ≤z≤Z0)，假設(shè)有Kz條路線，表示對第z個目的地的部分需求量，在從起點O到目的地Az的第s條路線上，在轎運(yùn)車上層選用第 j種裝載方式裝載乘用車所需第q型轎運(yùn)車的數(shù)量，其中q=1,2,...,Q;z=1,2,...,Z;j=1,2,...,nQ+q;s=1,2,...,OKz。+q,s表示對第z個目的地的部分需求量，在從起點O到目的地Az的第s條路線上，在轎運(yùn)車下層選用第 j種裝載方式裝載乘用車所需第q型轎運(yùn)車的數(shù)量。如果Z0=Z，那么從起點到每一個目的地都有多條運(yùn)輸行車路線，此時Kz＞1,z=1,2,...,Z；如果Z0=0，那么從起點到每一個目的地都有一條運(yùn)輸路線，此時 Kz=1,z=1,2,...,Z ；如果 0＜Z0＜Z ，那 么從起點到A1,A2,...,Az0目的地都有多條運(yùn)輸路線，其余Z-Z0個目的地均只 有 一 條 運(yùn) 輸 路 線 ，此 時 K1＞1,K2＞1,...,Kz0＞1, Kz0+1=,...,=KZ=1，這樣采用假設(shè)從起點到目的地Az有Kz條運(yùn)輸路線，Kz≥1,z=1,2,...,Z。表示從起點O到目的地Az的第s條運(yùn)輸路線所派的第q型轎運(yùn)車的數(shù)量，z=1,2,...,Z;s=1,2,...,Kz;q=1,2,...,Q ，顯 然

對于目標(biāo)函數(shù)，hzs表示從起點O到目的地Az的第s條運(yùn)輸路線的距離，s=1,2,...,Kz;z=1,2,...,Z；用Kq表示第q型轎運(yùn)車的距離運(yùn)價系數(shù)，即從起點O到目的地Az的運(yùn)輸里程成本：

由此可得起點O到所有目的地的運(yùn)輸里程總成本：

對于約束條件，上下層平衡約束:

需求約束：把目的地分為兩類，一類是終點性目的地，記為{B1,B2,...,Bu}，另一類是中轉(zhuǎn)性目的地記為{G1,G2,...,Gv}，顯然1＜u,v＜Z，且u+v=Z。

（1）終點性目的地約束。zt表示終點目的地的Bt目的地序號，1≤zt≤Z,t=1,2,...,u。

（2）中轉(zhuǎn)性目的地需求約束。對于中轉(zhuǎn)性目的地Gw(w =1,2,...,v) ， 目 的 地 序 號 用 zw表 示 ，1≤zw≤Z,w=1,2,...,v，用c1,c2,...,chw表示運(yùn)輸路線經(jīng)過的目的地，目的地序號依次用zα1,zα2,...,zαhw表示。

變量關(guān)系約束:

變量數(shù)值約束:

使用量約束限制:

綜上所述，可得到一般優(yōu)化模型形式，即以式（7）表示的目標(biāo)函數(shù)為最小，式（8）-式（14）為約束的整數(shù)線性規(guī)劃模型。2.3.2 模型求解算法。對于建立的一般優(yōu)化模型，可采用啟發(fā)式算法來求解。算法求解步驟如下：

Step1：輸入轎運(yùn)車規(guī)格（長、寬、高）及擁有量、轎運(yùn)車型號數(shù)、乘運(yùn)車規(guī)格（長、寬、高）、乘運(yùn)車型號數(shù)、目的地乘運(yùn)車各型號需求量、目的地數(shù)目、起點到目的地的運(yùn)輸路線數(shù)目、起點到目的地各運(yùn)輸路線的距離、轎運(yùn)車單位里程運(yùn)價系數(shù)、目的地序號、終點性目的地集合與序號、中轉(zhuǎn)性目的地與序號等數(shù)據(jù)。

Step2：確定終點性目的地的運(yùn)輸方案。

（1）針對此目的地的需求量，確定轎運(yùn)車車型及轎運(yùn)車裝載乘運(yùn)車的有效裝載方案，并對一層的各有效裝載方案按最優(yōu)、次優(yōu)....最差進(jìn)行優(yōu)劣排序；

（2）按一層的最優(yōu)裝載方案選擇第一種型號的若干轎運(yùn)車輛裝載乘運(yùn)車，直到用這種轎運(yùn)車正好裝完結(jié)束；否則，剩余乘運(yùn)車一輛轎運(yùn)車裝完轉(zhuǎn)（3），剩余乘運(yùn)車不能裝滿一轎運(yùn)車轉(zhuǎn)（4），記錄所用第一種型號的轎運(yùn)車的數(shù)量與裝載情況；

（3）按一層的非最優(yōu)裝載方案選擇第一種型號的若干轎運(yùn)車輛裝載乘運(yùn)車，直到用這種轎運(yùn)車正好裝完；否則，剩余的乘運(yùn)車不能裝滿一轎運(yùn)車，轉(zhuǎn)（4），記錄并累加所用第一種型號的轎運(yùn)車的數(shù)量與裝載情況；

（4）調(diào)整：減少一輛裝滿乘運(yùn)車的第一種型號的轎運(yùn)車，其所裝載乘運(yùn)車連同之前剩余乘運(yùn)車選擇第二種型號的轎運(yùn)車。如果用1輛第二種基本能裝載完乘運(yùn)車（轎運(yùn)車上允許有空車位，但很少），結(jié)束；否則，再減少一輛裝載乘運(yùn)車的轎運(yùn)車，兩輛轎運(yùn)車所裝載的乘運(yùn)車連同之前剩余乘運(yùn)車選擇第二種型號轎運(yùn)車。如果用兩輛第二種型號的轎運(yùn)車基本能裝載完乘運(yùn)車（轎運(yùn)車上允許有空車位，但很少），結(jié)束；否則繼續(xù)調(diào)整，記錄并累計所用各種型號轎運(yùn)車的數(shù)量與裝載方式。

Step3：確定中轉(zhuǎn)性目的地的運(yùn)輸方案。

（1）同Step2（1）；

（2）同Step2（2）；

（3）同Step2（3）；

（4）對剩余不能裝滿一轎運(yùn)車的乘運(yùn)車向經(jīng)過此中轉(zhuǎn)性目的地的其它目的地的轎運(yùn)車進(jìn)行添加裝載，如果能添加裝載完剩余乘運(yùn)車，結(jié)束；否則轉(zhuǎn)（5）。記錄轎運(yùn)車型號、數(shù)量與裝載方式；

（5）調(diào)整：減少一輛裝滿乘運(yùn)車的第一種型號的轎運(yùn)車，其所裝載乘運(yùn)車連同之前剩余乘運(yùn)車選擇第二種型號的轎運(yùn)車，先考慮向經(jīng)過此中轉(zhuǎn)性目的地的其它目的地的轎運(yùn)車進(jìn)行添加裝載，如果用1輛第二種型號的轎運(yùn)車基本能裝載完乘運(yùn)車，結(jié)束；否則，繼續(xù)調(diào)整（對經(jīng)過此目的地的第一種轎運(yùn)車可以減少地調(diào)整）。

Step4：轎運(yùn)車運(yùn)輸路線確定與成本計算。確定直達(dá)目的地的轎運(yùn)車型號、數(shù)量及運(yùn)輸路線距離，計算成本。確定非直達(dá)目的地的轎運(yùn)車型號、數(shù)量，停留下載地點與下載乘運(yùn)車型號、數(shù)量及運(yùn)輸路線距離，計算成本，并累加成本。

Step5：記錄可行解與總成本。

Step6：可行解改進(jìn)最優(yōu)。

（1）多運(yùn)輸路線目的地車輛調(diào)整，運(yùn)輸路線距離長的線路減少運(yùn)價系數(shù)高的并增加運(yùn)價系數(shù)低的轎運(yùn)車；運(yùn)輸路線距離短的線路減少運(yùn)價系數(shù)低的并且增加運(yùn)價系數(shù)高的轎運(yùn)車，計算總成本，如減少繼續(xù)調(diào)整，否則轉(zhuǎn)（2）；

（2）離起點遠(yuǎn)的目的地轎運(yùn)車盡可能選用運(yùn)價系數(shù)低的轎運(yùn)車，離起點近的目的地轎運(yùn)車盡可能選用運(yùn)價系數(shù)高的轎運(yùn)車。計算總成本，如減少，繼續(xù)調(diào)整；否則停止調(diào)整，以調(diào)整前的可行解作為較優(yōu)的解，結(jié)束。

2.4 模型舉例及推廣

若某物流公司要運(yùn)輸166輛I車型的乘用車（其中目的地A、B、C、D分別為42、50、33、41輛）和78輛II車型的乘用車（其中目的地A、C分別為31、47輛），具體路線如圖1所示，1-1型及2-2型轎運(yùn)車上、下層裝載區(qū)域相同，可裝載一列；1-2型轎運(yùn)車上、下層裝載區(qū)域長度相同，但上層比下層寬0.8m，上層裝載兩列，下層裝載一列，為方便后續(xù)任務(wù)安排，每次1-2型轎運(yùn)車使用量不超過1-1型轎運(yùn)車使用量的20%；各段長度：OD=160，DC=76，DA=200，DB=120，BE=104，AE=60。具體數(shù)據(jù)見表1-表3。請為物流公司安排運(yùn)輸，制定詳細(xì)計劃，含所需要各種類型轎運(yùn)車的數(shù)量、每輛轎運(yùn)車的乘用車裝載方案。

圖1 各個目的地分布狀況

表1 乘用車的規(guī)格

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

表3 轎運(yùn)車的運(yùn)價系數(shù)（km/元）

利用模型啟發(fā)式算法并結(jié)合LINGO求解軟件可得到，總運(yùn)價為3 376元，OD段需要1-1型轎運(yùn)車15輛，1-2型轎運(yùn)車7輛，每輛車的裝載情況見表4。

表4 OD段車輛裝載情況

DC段需要1-1型轎運(yùn)車5輛，1-2型轎運(yùn)車2輛，每輛車的裝載情況見表5。

表5 DC段車輛裝載情況

DB段需要1-1型轎運(yùn)車10輛，1-2型轎運(yùn)車3輛，每輛車的裝載情況見表6。

表6 DB段車輛裝載情況

BA段需要1-1型轎運(yùn)車5輛，1-2型轎運(yùn)車2輛，每輛車的裝載情況見表7。

表7 BA段車輛裝載情況

[1]韓龍士.供應(yīng)鏈管理下的汽車物流研究[J].汽車工業(yè)研究,2006,(6):8-9.

[2]楊海榮.現(xiàn)代物流系統(tǒng)與管理[M].北京:北京郵電大學(xué)出版社,2003.

[3]王占鋒,張翠軍.求解非滿載車輛調(diào)度問題的改進(jìn)遺傳算法[J].計算機(jī)工程與設(shè)計,2008,29(15):3 991-3 993.

[4]胡富昌.線性規(guī)劃(第二版)[M].北京:中國人民大學(xué)出版社,1990.

[5]姜啟源,謝金星,葉俊.數(shù)學(xué)模型(第三版)[M].北京:高等教育出版社, 2008.

Study on Problems in Passenger Vehicle Logistics and Transportation Solutions

Zhou Jianjun1,Zhang Shun2,Zang Bilian2,Lin Daorong2
(1.Nanjing Institute of Technology,Nanjing 211167;2.School of Science,Nantong University,Nantong 226019,China)

In this paper,we first analyzed some effective passenger vehicle transportation solutions,then from the angles of loading, route,destination and stacking,etc.,introduced in the decision-making variables concerning the quantity of the car carriers,built the corresponding integer linear programming model and at the end,used a heuristic algorithm to solve it.

car carrier;passenger vehicle;vehicle logistics;transportation plan;integer linear programming model;heuristic algorithm

F426.471；F252

A

1005-152X(2015)10-0123-04

2015-07-11

周建軍（1968-），男，江蘇如皋人，講師，博士在讀，研究方向：系統(tǒng)工程；張順（1990-），女，山東單縣人，研究生，研究方向：運(yùn)籌與控制；臧碧蓮（1992-），女，江蘇靖江人，研究生，研究方向：組合設(shè)計理論；林道榮（1963-），通訊作者，男，江蘇海安人，教授，研究方向：組合優(yōu)化。

10.3969/j.issn.1005-152X.2015.10.034