模擬退火算法在整車物流問(wèn)題中的應(yīng)用

張遠(yuǎn)++余依

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

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

中圖分類號(hào)：U294 文獻(xiàn)標(biāo)識(shí)碼：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 引 言

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

1 整車物流問(wèn)題

1.1 整車物流問(wèn)題描述

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

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

1.2 整車物流問(wèn)題的模型

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 算法改進(jìn)

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

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

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

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

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

（3）生成鄰域解x。

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

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

（6）若x.cost

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

（8）若x.cost

（9）內(nèi)循環(huán)步驟（3）至步驟（8），達(dá)到內(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，降溫過(guò)程越慢，越容易接近全局收斂點(diǎn)，但求解時(shí)間過(guò)長(zhǎng)，降溫系數(shù)小，降溫過(guò)程越快，容易陷入局部收斂點(diǎn)，求解時(shí)間短。經(jīng)過(guò)多次實(shí)驗(yàn)，均勻抽樣一組狀態(tài)，以各狀態(tài)目標(biāo)值得方差為初溫，降溫系數(shù)設(shè)為0.9。

2.4 構(gòu)造初始解

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

（1）將客戶點(diǎn)隨機(jī)排列得到隨機(jī)全排列q；

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

（3）計(jì)算第一個(gè)客戶點(diǎn)q的需求量n，轎運(yùn)車行駛的距離D；

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

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

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

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

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

Q*s+sumQ

-p*L≤p*L

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

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

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

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

3 算例驗(yàn)證

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

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

4 結(jié) 論

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

參考文獻(xiàn)：

[1] 吳保峰，劉仲英. 我國(guó)整車物流發(fā)展趨勢(shì)及資源整合問(wèn)題研究[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ì)壽文，繆立新，李克強(qiáng)，等. 貨運(yùn)車輛優(yōu)化調(diào)度方法[J]. 公路交通科技，2003（6）：109-112.

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