張遠++余依

摘 要：通過對整車物流問題進行分析，建立了一個多轎運車、多乘用車的整車物流模型。整車物流的轎運車和乘用車具有特殊的裝載方式，且轎運車的多層多排結(jié)構(gòu)決定了轎運車和乘用車之間具有多種裝載方案，再從不超載的行駛路徑下找到滿足裝載條件的裝載方案。文章基于傳統(tǒng)模擬退火算法的思想對算法進行改進，最后通過驗證24個客戶點的訂單問題，將初溫設(shè)置為190度，降溫系數(shù)設(shè)置為0.98，求解出共需轎運車8輛，平均裝載率為96%。實例驗證了算法的可行性。

關(guān)鍵詞：模擬退火算法；整車物流；VRP

中圖分類號：U294 文獻標(biāo)識碼：A

Abstract： According to analyze the influencing factor of finished car logistics， this paper established a finished car logistics model about multiple car transporter and multiple finished cars. Due to special structure and the way of loading， multiple car transporter and multiple finished cars have a variety of loading plan， the goal is find the loading plan adapt to loading conditions. Based on the traditional simulated annealing algorithm， the algorithm is improved. Verifing orders for 24 customer orders， set the initial temperature to 190 degrees， cooling coefficient is 0.98， the result of calculation is need 8 car transporter， average loading rate is 96%. Examples verify the feasibility of the algorithm.

Key words： simulated annealing algorithm； finished car logistics； VRP

0 引 言

整車物流問題是近些年隨著我國汽車經(jīng)濟的高速發(fā)展隨之而來的。整車物流是指從汽車在制造廠完成組裝下線后開始，直到送達用戶手中為止的一系列倉儲、運輸、維護、檢驗、加工以及其他各種增值服務(wù)過程，是實物流、信息流、資金流的統(tǒng)一[1]。乘用車私人定制化的普及，汽車生產(chǎn)商在接受到客戶訂單后需要快速進行組裝生成，這種多批次小批量的生產(chǎn)模式也是目前我國主流的乘用車生產(chǎn)模式。而隨著乘用車的型號增多，物流公司將面臨著更大的運輸壓力。不同乘用車其長度、寬度和高度都不相同，負責(zé)運輸?shù)霓I運車規(guī)格也有不同，且乘用車在運輸過程中不能堆壓擺放，每輛乘用車之間都必須有一定的安全間隔，以保證在運輸過程中乘用車之間不會發(fā)生擠壓或者碰撞而導(dǎo)致變形等損壞。為規(guī)范車輛運輸車（轎運車）的使用和管理，保障道路交通安全，交通部、發(fā)改委、工信部、公安部、國家質(zhì)監(jiān)局五部委于2016年8月18日聯(lián)合正式發(fā)布了《車輛運輸車治理工作方案》（以下簡稱《方案》）并開始實施。自2016年9月21日起，所有的雙排車輛禁止上路，從2016年9月21日至2018年6月30日為不合格車輛運輸車的整改期，暫時允許“單排車”過渡運行。《方案》的頒布將對整車物流行業(yè)造成巨大的影響，目前市場上的轎運車基本都會面臨禁止上路或者被改造的命運，本文將按照《方案》的標(biāo)準(zhǔn)對整車物流的裝載和配送路徑問題進行優(yōu)化，提出一種新的裝載配送模型，經(jīng)過多次實驗驗證，該模型能有效降低整車物流成本，提高整車物流效益。

1 整車物流問題

1.1 整車物流問題描述

整車物流問題包括整車物流裝載問題和整車物流配送路徑優(yōu)化問題，屬于VRP問題的分支。整車物流問題不僅要在路徑上進行優(yōu)化處理，對裝載的合理安排也是降低運輸成本的一個重要途徑。目前已有大量研究運用遺傳算法（GA），模擬退火算法（SA）等啟發(fā)式算法求解多車型車輛路徑問題或者裝載問題。Golden[2]最早于1984年開始研究多車型車輛路徑問題，J.Lawrence將遺傳算法用于VRP的研究，并可有效求解帶時間窗的VRP[3]。紀(jì)壽文等人詳細介紹求解貨運車輛優(yōu)化調(diào)度問題常用的啟發(fā)式算法、神經(jīng)網(wǎng)絡(luò)算法和遺傳算法的原理、模型和求解過程。然后以深圳市科技園的實際路網(wǎng)圖，采用神經(jīng)網(wǎng)絡(luò)的方法對運輸車輛優(yōu)化調(diào)度進行試驗研究，給出實驗結(jié)果[4]。謝紅燕[5]針對VRP問題建立了并行模擬退火算法，在傳統(tǒng)模擬退火的基礎(chǔ)上增加了記憶功能求解VRP問題。模擬退火算法（SA）是一種啟發(fā)式算法，算法思想源于熱力學(xué)中退火過程的模擬，即在某一給定的初始溫度下，通過緩慢地下降溫度參數(shù)，使算法能夠在多項式時間內(nèi)給出一個近似的最優(yōu)解。它以一定的概率來選擇鄰域中目標(biāo)值相對比較小的狀態(tài)，是一種理論上的全局最優(yōu)算法。本文假設(shè)客戶的等待時間足夠長，建立基于模擬退火算法的整車物流裝載與配送路徑優(yōu)化模型使第三方物流公司以最小的成本完成客戶訂單配送。

目前我國汽車生產(chǎn)商的整車物流大多外包給第三方整車物流公司，第三方物流公司有N種型號的轎運車，共有轎運車n輛，需配送的商品車有m種，轎運車和商品車的型號已知，現(xiàn)有K個客戶需要進行配送，每個客戶訂單需求量已知。第三方物流公司需要根據(jù)訂單進行合理的裝載并選擇恰當(dāng)?shù)呐渌吐肪€使每輛轎運車的利用率最大，同時所有轎運車的行駛距離最小。物流公司根據(jù)運單選擇若干輛轎運車進行裝載配送，每輛轎運車沿一條包含了若干個客戶的封閉的回路進行運輸任務(wù)，任務(wù)完成后返回出發(fā)點。

1.2 整車物流問題的模型

整車物流問題是一個NP-難題。傳統(tǒng)的VRP問題商品單一，整車物流問題中商品車種類多樣，不同型號的商品車和轎運車有成千上萬種的裝載方案，則對整車的裝載問題要求更高，要安排最優(yōu)的裝載方案滿足該輛轎運車運輸路徑上所有客戶點的需求?？蛻粲唵畏譃閮煞N情況，一種是訂單需求量超過單輛運輸車最大容量，一種是小于最大容量。對于訂單量超過最大容量的，首先安排單輛轎運車進行整車配送，本文不討論這種情況。對所有客戶點預(yù)處理完畢后，每個客戶點的需求量都小于單輛運輸車的裝載量，對模型做一下假設(shè)：

（1）現(xiàn)有n輛轎運車在配送中心等待運輸任務(wù)，共有N種商品車，每種轎運車和商品車的型號已知，共有M種型號的轎運車。共有K個客戶點，每個客戶的需求已知，客戶點之間的距離以及到配送中心的距離均已知。

（2）需要根據(jù)客戶點的需求以及客戶點之間的距離等約束確定每輛車的裝載方案以及運輸路線，使所有轎運車的總行駛距離最小。

（3）每個客戶點最多只能由一輛轎運車服務(wù)，每輛轎運車完成運輸任務(wù)后返回配送中心。

（4）為建立模型，首先定義如下符號和變量：C=0，1，2，…，k表示配送中心和客戶點集合，其中0表示配送中心；N：轎運車的種類；n：可用轎運車的數(shù)量；m：商品車的種類；q：第v個客戶對第i種商品車的需求量v=1，2，…，k， i=1，2，…，m；

d：客戶點u、v之間的距離u=0，1，2，…，k， v=0，1，2，…，k；L：裝載到轎運車上的相鄰兩輛商品車之間的安全間隔；L：第j輛轎運車的裝載長度j=1，2，…，n；p：第j種轎運車的排數(shù)，2≤P≤4，P=2表示上下各一排，P=3表示下層一排，上層兩排，P=4表示上下各兩排；f：第j輛轎運車第k排卸載的第i種商品車的數(shù)量；j=1，2，…，n， i=1，2，…，m， k=1…

P；s：第i種商品車的車身長度，i=1，2，…，m；e=f，e表示第j輛轎運車卸載的商品車i的總數(shù)量，j=1，2，…，n， i=1，2，…，m， k=1…

P；x：轎運車j是否由客戶點u行駛至客戶點 v，u=1，2，…，k； v=1，2，…，k， j=1，2，…，n。

以所有轎運車總行駛距離最短為目標(biāo)的整車物流裝載與路徑優(yōu)化問題可以表示成如下的整數(shù)規(guī)劃模型：

其中：M是很大的正數(shù)。

目標(biāo)函數(shù)表示極小化所有轎運車總行駛距離，約束條件（1）表示轎運車j從點u運輸至客戶v后在客戶點v卸載的商品車i的總數(shù)量；約束條件（2）表示只有當(dāng)轎運車j在客戶點v有運輸任務(wù)時，才開往客戶點v；約束條件（3）表示第j輛轎運車下層和上層的裝載長度約束；約束條件（4）表示客戶點v對各類型商品車的需求量恰好等于所有轎運車在該客戶點的卸載量；約束條件（5）表示每輛轎運車都是從配送中心出發(fā)；約束條件（6）表示每輛轎運車都要返回配送中心；約束條件（7）、（8）是變量取值約束。

2 模擬退火算法的應(yīng)用

模擬退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等將其應(yīng)用于組合優(yōu)化。模擬退火指的是在某一給定的初始溫度下，通過緩慢地降低溫度系數(shù)，使算法能夠在多項式時間內(nèi)給出一個近似的最優(yōu)解。它以一定的概率來選擇鄰域中目標(biāo)值相對比較小的狀態(tài)，是一種理論上的全局最優(yōu)算法。

2.1 算法改進

模擬退火算法的基本思想是通過內(nèi)外兩層循環(huán)尋求最優(yōu)解。外循環(huán)控制降溫，內(nèi)循環(huán)尋找當(dāng)前溫度下最優(yōu)解。但由于模擬退火算法在求解過程中是單個狀態(tài)進行求解，當(dāng)問題規(guī)模增大時，求解時間相對其他算法會較長，且較依賴降溫速度和其他控制系數(shù)。

為得到更高效、更準(zhǔn)確的算法，本文對算法進行了改進：（1）初始解狀態(tài)是基于客戶點的數(shù)量，對隨機生成的每條路徑，進行裝載條件的判斷；（2）在轎運車數(shù)量和總行駛距離上優(yōu)先選擇轎運車數(shù)量更少的方案；（3）算法先求解了各種型號的轎運車所有滿載情況，最后求解得的轎運車車輛裝載量不超過任一種滿載方案；（4）新狀態(tài)的產(chǎn)生，算法在上一步最優(yōu)解的基礎(chǔ)上進行鄰域解的搜索，采取多種變換算法（2-opt、兩點變換法等）；（5）程序中增加運行結(jié)果記憶功能，以便于對模型的結(jié)果進行分析。算法程序使用MATLAB 2015a進行編程實現(xiàn)。算法主要包括以下幾個函數(shù)：模擬退火算法主程序，轎運車滿載方案函數(shù)，隨機生成初始解函數(shù)，初始化函數(shù)，鄰域解函數(shù)，成本函數(shù)。

2.2 基于模擬退火算法的整車物流算法

（1）生成初始解x=Lj，每一個Lj代表一輛轎運車的服務(wù)客戶及行駛路線。

（2）計算目標(biāo)函數(shù)值x.cost，并令Best=x。

（3）生成鄰域解x。

（4）計算目標(biāo)函數(shù)值x.cost。

（5）若新解x的轎運車數(shù)量小于最優(yōu)解的轎運車數(shù)量，令Best=x；若新解x的轎運車數(shù)量與Best解一致，轉(zhuǎn)6；若新解x的轎運車數(shù)量大于Best，放棄該解，轉(zhuǎn)3。

（6）若x.cost

（7）計算Δ=x.cost-x.cost，判斷p=exp-delta/T是否被接受，隨機生成一個0，1之間的隨機數(shù)rand，若rand

（8）若x.cost

（9）內(nèi)循環(huán)步驟（3）至步驟（8），達到內(nèi)循環(huán)次數(shù)跳出循環(huán)。

（10）降溫，T=T*alpha，初始溫度一般設(shè)置較高，alpha為降溫系數(shù)。

（11）外循環(huán)步驟（3）至步驟（10），直到外循環(huán)次數(shù)結(jié)束跳出循環(huán)，得到最優(yōu)解。

2.3 初溫及降溫系數(shù)設(shè)置

初始溫度的設(shè)置影響算法最后結(jié)果的精確性，初始溫度越高，得到的解越精確，降溫系數(shù)越接近于1，降溫過程越慢，越容易接近全局收斂點，但求解時間過長，降溫系數(shù)小，降溫過程越快，容易陷入局部收斂點，求解時間短。經(jīng)過多次實驗，均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值得方差為初溫，降溫系數(shù)設(shè)為0.9。

2.4 構(gòu)造初始解

將客戶點編號進行隨機排序，得到一個客戶群的隨機全排列，從該全排列中的第一個客戶點開始，依次放入子路徑中，每條子路徑代表一輛轎運車的行駛路徑。每加入一個客戶點，判斷該輛該轎運車是否超載，若超載，調(diào)用新的轎運車，否則繼續(xù)裝載下一個客戶點，直到所有客戶點被滿足。由于大車型轎運車購買成本較高，所有大車型轎運車數(shù)量較少，每次選擇轎運車時隨機選擇，但是大車型的轎運車數(shù)量有限。具體算法如下：

（1）將客戶點隨機排列得到隨機全排列q；

（2）隨機選擇一輛轎運車，并更新剩余類型的轎運車數(shù)量；

（3）計算第一個客戶點q的需求量n，轎運車行駛的距離D；

（4）加入下一個客戶點q，計算新的需求量n=n+n，n表示當(dāng)前客戶點的需求量；

（5）判斷新加入客戶點后是否超載，若不超載，則更新行駛距離D=D+D，D表示新加入客戶點與上一個客戶點的距離，n=n；若超載，則轉(zhuǎn)（6）；

（6）保存上一步未超載的路徑L，總需求Q，重新選擇新的轎運車，j=j+1，將步驟（5）中未加入的客戶點保存至新的路徑中，n=n，D=D，D表示當(dāng)前客戶點與配送中心的距離；

（7）循環(huán)步驟（4）至步驟（6），直到所有客戶點被滿足。

對于每一個解的任何一條子路徑L，計算該條路徑的總需求量Q，根據(jù)轎運車的基本參數(shù)和乘用車的基本參數(shù)，不超載條件如下：

Q*s+sumQ

-p*L≤p*L

運用反證法，若轎運車裝載的乘用車所需總裝載長度不超過轎運車每排的裝載長度之和，則必然能找到一種裝載方案使得每一排裝載長度不超載。初始解記錄每條路徑選用的轎運車車型，每條路徑的裝載量，轎運車的行駛路線。

2.5 構(gòu)造轎運車滿載方案

在得到最優(yōu)解后，需要找到一種裝載方案對乘用車進行裝載。本文通過構(gòu)造可行裝載方案矩陣得到滿載方案。

根據(jù)轎運車的和乘用車的種類數(shù)生成解空間，轎運車有N種，乘用車有m種，轎運車每排的長度相同，根據(jù)整車物流模型約束條件（3）可以得到各種車型的滿載方案。在構(gòu)造的可行初始解中，根據(jù)每條路徑選擇的轎運車車型至少可以從該種轎運車車型的滿載方案中選擇一種裝載方案滿足該條路徑的裝載需求。

3 算例驗證

某汽車生產(chǎn)商主要生產(chǎn)三種車型的乘用車，某第三方整車物流公司有兩種型號的轎運車，都為上下單排雙層結(jié)構(gòu)，轎運車及乘用車的基本參數(shù)如表1，某次訂單共有24個客戶，客戶的需求量如表2，客戶與配送中心的距離如表3，根據(jù)模型及算法，為保證算法的準(zhǔn)確性，并進行了多次計算比較，得到在不同降溫系數(shù)，不同初始溫度下的最優(yōu)解。

經(jīng)過多次試驗，將初溫設(shè)置為190，降溫系數(shù)0.98，求解出最優(yōu)解。共需8輛轎運車，總行駛距離為1 709.8912千米，平均裝載率為95.83%，具體裝載方案如表

4 結(jié) 論

本文通過研究多車型的整車物流問題，建立整車物流數(shù)學(xué)模型，在傳統(tǒng)模擬退火算法上進行改進，通過均勻抽樣計算方差的方式確定初溫，避免溫度過高收斂較慢、溫度過低陷入局部收斂，在轎運車裝載問題上采用反向驗證，總長度不超載則每一層必有一種不超載的裝載方案，優(yōu)先選擇轎運車數(shù)量少的方案。實驗結(jié)果顯示了本文算法的有效性。

參考文獻：

[1] 吳保峰，劉仲英. 我國整車物流發(fā)展趨勢及資源整合問題研究[J]. 汽車工程，2005（3）：367-371.

[2] Golden B， Assad A， Levy L， et al. The fleet size and mix vehicle routing problem[J]. Computers and Operations Research， 1984（11）：19-66.

[3] Lawrenee S， Mohammad A. Parametric experimentation with a genetic algorithmic Configuration for solving the vehicle routing problem[C] // Proceedings-Annual Meeting of the Decision sciences Institute. Decis Scil Inst， 1996：488-490.

[4] 紀(jì)壽文，繆立新，李克強，等. 貨運車輛優(yōu)化調(diào)度方法[J]. 公路交通科技，2003（6）：109-112.

[5] 謝紅燕. 基于并行模擬退火算法的VRP問題研究[J]. 物流技術(shù)，2010（15）：67-69.