肖柯偉，陳 志，趙 博 XIAO Ke-wei, CHEN Zhi, ZHAO Bo

（1. 中國農(nóng)業(yè)大學 工學院，北京100083；2. 中國機械工業(yè)集團有限公司，北京100080；3. 中國農(nóng)業(yè)機械化科學研究院，北京100083）

(1. College of Engineering, China Agricultural University, Beijing 100083, China； 2. China National Machinery Industy Corporation,Beijing 100080, China； 3. Chinese Academy of Agricultural Mechanization Science, Beijing 100083, China)

0 引 言

物流配送車輛優(yōu)化調(diào)度問題是由Dantzig 和Ramser[1]于1959 年首次提出的，一般認為它是車輛路徑問題（Vehicle Routing Problem） 和車輛排程問題（Vehicle Scheduling Problem） 的統(tǒng)稱。車輛路徑問題一經(jīng)提出，就受到了組合數(shù)學、網(wǎng)絡(luò)分析、圖論、計算機應(yīng)用等學科的專家與運輸計劃制定者和管理者的極大重視，他們進行了大量的理論研究和實驗分析，并將其研究成果成功運用在運輸、物流配送、快遞收發(fā)等系統(tǒng)中。目前，我國物流需求規(guī)模保持較高增幅，物流成本逐年攀升，物流配送車輛調(diào)度問題在企業(yè)運營中的作用越來越大。而物流配送車輛調(diào)度問題的研究目標就是要降低物流企業(yè)成本、提高物流配送的效益、提高企業(yè)競爭力，進而達到發(fā)展現(xiàn)代物流配送系統(tǒng)、促進產(chǎn)業(yè)結(jié)構(gòu)調(diào)整、推動區(qū)域經(jīng)濟發(fā)展的戰(zhàn)略目標。因此，該問題一直是國內(nèi)外研究的熱點。

1 車輛調(diào)度問題概述

1.1 車輛調(diào)度的優(yōu)化目標

車輛調(diào)度問題是在滿足一定約束條件下，選擇某種目標作為優(yōu)化目標，實現(xiàn)總配送成本（廣義的配送成本，如配送時間、總費用、需要車輛等） 最優(yōu)[2]。其中總配送成本一般表現(xiàn)為最小化總費用，即車輛完成配送任務(wù)的各項費用之和最小，如車輛啟用固定費用、車輛行駛費用、車輛等待費用、車輛服務(wù)費用、車輛懲罰費用等；最小所需車輛數(shù)即完成全部配送任務(wù)所需總車輛數(shù)最?。蛔钚】偩嚯x即完成全部配送任務(wù)車輛路徑總長度最??；最短服務(wù)時間即完成全部配送任務(wù)總配送時間最小，配送時間一般包括車輛行駛時間、等待時間、服務(wù)時間和延誤時間等。

1.2 配送車輛優(yōu)化調(diào)度的模型

通過建立數(shù)學模型來定量研究物流配送成本的方法，目前可以歸納為三類：車輛流模型、物資流模型和集覆蓋模型。從建立模型時的出發(fā)點考慮，絕大多數(shù)模型可以看做這三種模型的變形與組合。在派出一輛車固定費用高于行駛費用時，一般采用車輛流模型。本文車輛調(diào)度問題采用的就是車輛流模型。

物流配送車輛調(diào)度問題數(shù)學模型可描述為：車輛由配送中心發(fā)出，對每一個客戶按照時間或其它要求配送到，車輛完成配送后返回配送中心，規(guī)定每個客戶只能由一輛車對其進行服務(wù)且只服務(wù)一次，要求在滿足約束條件（如載重約束、時間約束、里程約束等） 下對車輛行駛路徑進行優(yōu)化，使完成配送的優(yōu)化目標（成本、路程、車輛數(shù)等） 最小。

物流車輛調(diào)度問題的數(shù)學模型是目標規(guī)劃模型，其結(jié)構(gòu)特征一般為：

1.2.1 有載重約束的車輛調(diào)度模型。車輛調(diào)度問題根據(jù)載貨任務(wù)情況可分為非滿載車輛調(diào)度問題以及滿載車輛調(diào)度問題。非滿載車輛調(diào)度問題要求每個客戶需求量少于車輛載重量，一輛車能夠同時給一個或多個客戶運送貨物。大多數(shù)時候一次任務(wù)不能恰好裝滿整車，這往往造成車輛裝載率不高。滿載車輛調(diào)度問題中，客戶需求不小于車輛載重量，完成每次任務(wù)都需要滿載行駛，配送過程需要多輛車滿載，存在著最后一輛車非滿載的情況。

目前，對于車輛調(diào)度問題的研究以非滿載車輛調(diào)度問題為主。首先，給出決策變量：

下面對非滿載車輛調(diào)度問題建立車輛調(diào)度模型。

其中：F為車輛固定費用，m為車輛數(shù)，cijk為單位里程成本，dij為客戶i到客戶j的距離，qi為客戶需求量，Q為車輛載重量，Lk為車輛最大行駛距離；式（2） 是載重約束，式（3） 是每個需求客戶由一輛車來完成，式（4） 是車輛最大行駛距離限制，式（5） 表示每個客戶都能得到車輛的配送任務(wù)，式（6）、式（7） 表示兩個變量之間的關(guān)系，式（8）、式（9） 表示決策變量為0-1 約束。

1.2.2 有時間約束的車輛調(diào)度模型。時間約束問題可分為硬時間窗約束、軟時間窗約束、混合時間窗約束三種。硬時間窗約束模型對不能在規(guī)定時間內(nèi)運達的給予一較大的懲罰M值（即成本升高），從而降低其適應(yīng)值；軟時間窗約束模型是對不能在規(guī)定時間運達的給予懲罰，懲罰值依到達時間與規(guī)定時間的差值而定；混合時間窗模型則是對不能按規(guī)定時間運達的分段處理，在可接受時間范圍內(nèi)采用軟時間窗問題處理，超過可接受時間范圍則采用硬時間窗問題處理。

硬時間窗問題懲罰函數(shù)設(shè)置：車輛必須在[ei,li]時間內(nèi)到達，否則給予其較大懲罰值M。下面建立帶硬時間窗約束的車輛調(diào)度模型：

需添加時間窗約束方程式：

其中：ti為配送車輛到達客戶i的時間，Ti為在客戶i處裝卸貨所耗費的時間，tij表示車輛從i到j(luò)所用的時間，T為一足夠大的常數(shù)。

1.2.3 有里程約束的車輛調(diào)度模型。帶里程約束問題的現(xiàn)實來源是車輛油箱容積限制。也有一種經(jīng)濟學解釋：車輛在行駛超過一定里程后會收取燃料附加費。其數(shù)學模型見1～9。

2 智能算法在物流配送車輛路徑問題中的應(yīng)用

通過對已有文獻進行總結(jié)歸納，車輛調(diào)度問題求解算法可以分為三類：精確算法、傳統(tǒng)啟發(fā)式算法和現(xiàn)代智能算法。鑒于精確算法計算能力有限、計算時間長，傳統(tǒng)啟發(fā)式算法易陷于局部最優(yōu)、參數(shù)設(shè)置過于影響算法效果，目前，現(xiàn)代智能算法是研究車輛調(diào)度問題的主流算法。用于車輛調(diào)度問題的智能算法主要有：遺傳算法、蟻群算法、人工神經(jīng)網(wǎng)絡(luò)算法、模擬退火算法、禁忌搜索算法等。雖然智能算法具有全局搜索能力強，運算方便等優(yōu)點，但是也存在著局部搜索能力差、收斂時間過長、易陷于局部最優(yōu)等問題，單一智能算法不是車輛調(diào)度問題的最有效算法。混合算法是當今研究車輛調(diào)度問題的熱點算法。

2.1 混合遺傳算法

在實際運算過程中，遺傳算法存在著局部搜索能力差、易早熟等問題，而鄰域搜索算法、模擬退火算法、量子進化算法等卻具有較強的局部搜索能力，能夠快速收斂?，F(xiàn)有研究也證明了常規(guī)遺傳算法往往不是求解具體問題的最有效算法，而將遺傳算法與某些算法結(jié)合起來構(gòu)成混合算法，卻有可能產(chǎn)生求解性能極佳的方法。

2.1.1 量子遺傳算法。量子遺傳算法是20 世紀90 年代后期新興的一個研究領(lǐng)域，主要是在遺傳算法中引入量子計算的一些概念，利用量子態(tài)的疊加性和相干性帶來的內(nèi)在并行性來加速算法的求解速度，與其他經(jīng)典算法本質(zhì)的區(qū)別在于它具有量子并行性。與傳統(tǒng)遺傳算法相比，量子遺傳算法能夠在較小的種群規(guī)模下，快速地收斂到全局最優(yōu)。文獻[3]研究了動態(tài)車輛調(diào)度問題，運用量子遺傳算法對建立時間軸的車輛調(diào)度模型求解，通過與其他算法比較，驗證了算法的有效性。文獻[4]研究了車輛路徑問題，將遺傳算法交叉，變異操作引入到量子粒子群算法，取得了較好的效果。

2.1.2 遺傳算法與模擬退火算法結(jié)合。遺傳模擬退火算法是將遺傳算法與模擬退火算法相結(jié)合而構(gòu)成的一種優(yōu)化算法。遺傳模擬退火算法具有遺傳算法的整體搜索能力和模擬退火算法的局部搜索能力，算法運算效率高[5]。文獻[6]結(jié)合tsp 問題的特點，運用遺傳與模擬退火算法相結(jié)合的遺傳模擬退火算法，成功解決了該tsp 問題。

文獻[7]研究改進遺傳模擬退火算法，采用多層并行搜索結(jié)構(gòu)，給出了一種早熟評價指標，并成功將該算法應(yīng)用于tsp 問題中。

2.1.3 遺傳算法與其他算法的混合算法。文獻[8]采用遺傳算法與最近鄰域算法結(jié)合混合遺傳算法解決單車線路優(yōu)化問題，在可行時間內(nèi)得到了滿意解。文獻[9]研究了模糊需求的車輛路徑問題，以模糊可信行理論為基礎(chǔ)，引入掃描算法進行種群的初始化，結(jié)合配送分隊數(shù)和剩余載重因素提出了混合交叉算子。文獻[10]研究了一類具有多個配送中心、需要進行車輛租賃和車輛共享、有時間窗限制、開環(huán)的VRP 問題，設(shè)計了一種結(jié)合掃描算法和C-W 節(jié)約算法對車輛路徑和車輛調(diào)度統(tǒng)籌優(yōu)化的混合遺傳算法。

2.2 混合粒子群算法

2.2.1 量子粒子群混合算法。量子粒子群算法是將量子進化算法融合到粒子群中產(chǎn)生的。該算法中粒子的位置是由量子比特進行編碼，粒子位置的更新是由量子旋轉(zhuǎn)門來完成。文獻[11]研究了帶時間窗車輛調(diào)度問題，提出了一種基于粒子碰撞的離散粒子群算法，成功解決該問題。文獻[12]將量子粒子群算法與模擬退火算法相結(jié)合，用來求解帶時間窗的車輛路徑問題。文獻[13]提出混沌量子粒子群算法，并將它應(yīng)用于車輛調(diào)度問題，取得了較好的效果。

2.2.2 粒子群算法與模擬退火算法。粒子群—模擬退火融合算法增強了粒子群優(yōu)化算法的全局搜索能力和跳出局部最優(yōu)的能力，增加了粒子群的多樣性，提高了算法收斂速度。文獻[14]針對改進的車輛調(diào)度模型，設(shè)計了混合粒子群算法，用粒子群算法來分配每輛車的客戶，用模擬退火求解每輛車完成運輸任務(wù)的次序，避免了單純粒子群算法編碼復雜的缺陷，求出了其有效近似解。文獻[15]提出粒子群算法與模擬退火算法結(jié)合的混合粒子群算法，快速求得帶時間窗車輛路徑問題的優(yōu)化解。

2.2.3 粒子群算法與其它算法的混合算法。文獻[16]研究了帶時間窗車輛調(diào)度問題，提出改進的粒子群優(yōu)化算法，在慣性權(quán)重遞減的基礎(chǔ)上通過群體極值進行t分布變異。文獻[17]建立了多車場多車型車輛路徑調(diào)度問題的數(shù)學模型，提出了在種群中的粒子采用一定的概率進行柯西變異的改進粒子群算法。

2.3 混和蟻群算法

2.3.1 量子蟻群算法。量子蟻群算法是一種概率優(yōu)化算法，它以量子計算的理論和概念作為基礎(chǔ)，具有較強的全局尋優(yōu)能力和豐富的群體多樣性。文獻[18]采用量子蟻群算法研究帶時間窗的車輛路徑問題，通過定義人工螞蟻的轉(zhuǎn)移概率，增加量子比特啟發(fā)式因子，以及用量子旋轉(zhuǎn)門實現(xiàn)信息素更新，從而提高算法全局搜索能力，有效避免了算法陷入局部最優(yōu)。文獻[19]通過量子蟻群算法對物流配送路徑優(yōu)化問題進行求解，對各路徑上的信息素進行子比特編碼，采用量子旋轉(zhuǎn)門及最優(yōu)路徑對信息素進行更新，有效解決了物流配送路徑問題。

2.3.2 蟻群算法與粒子群算法結(jié)合。蟻群粒子群混合算法同時具有蟻群算法的大規(guī)模尋優(yōu)特性和粒子群算法的較強局部搜索能力，在確保全局收斂性的基礎(chǔ)上，能夠快速搜索到高質(zhì)量的優(yōu)化解。文獻[20]建立貨運關(guān)系明細的多需求點車輛調(diào)度模型，模型求解過程是先由粒子群算法的粒子位置向量得到單車運送的貨物，再由蟻群算法優(yōu)化單車路徑，根據(jù)優(yōu)化目標篩選粒子，直到終止條件，實現(xiàn)所有貨物對所有車輛的分配。

2.3.3 蟻群算法與其他算法結(jié)合。文獻[21]采用改進蟻群算法，引入信息變異算子和種群入侵算子，較好地求解了多車場多車型最快完成車輛路徑問題。文獻[22]設(shè)計了一種改進的蟻群算法，將蟻群系統(tǒng)（ACS） 與最大最小螞蟻系統(tǒng)（MMAS） 相結(jié)合，求解了帶時間窗的車輛路徑問題。文獻[23]提出了一個能同時利用演化算法的全局優(yōu)化能力和蟻群算法的局部探索能力的混合智能優(yōu)化算法，對動態(tài)網(wǎng)絡(luò)環(huán)境下動態(tài)需求的最優(yōu)路徑搜索問題進行了研究。

3 總結(jié)與展望

車輛調(diào)度問題盡管在模型和算法方面已取得了大量的成果，但是由于該問題涉及的因素多，仍有很多重要問題值得進一步研究。目前研究的缺陷主要體現(xiàn)在：①研究目標單一，應(yīng)用價值不大。在實際研究中，客戶需求各異甚至相互沖突，如客戶滿意度的提高和運作成本的降低就可能是一對效益相反的矛盾。因此，在決策中需要更多地考慮多目標的情況，但以往對車輛調(diào)度問題的研究主要集中于單一目標問題，對多目標問題的研究尚顯不足。一個值得深入研究的方向是采用線性加權(quán)法或理想點法等評價函數(shù)法將多目標優(yōu)化問題轉(zhuǎn)化為單目標優(yōu)化問題，從而求得多目標優(yōu)化問題的pareto 最優(yōu)解。②模型考慮因素單一，與實際應(yīng)用尚有距離?，F(xiàn)今研究的模型多因為建模的方便和可行性，建模過程相對理想化，人為的增加或減少一些約束，這往往與實際不符?？紤]的因素一般不能全面反映具體物流車輛調(diào)度模型，如車輛滿載與非滿載耗油量是不同的，相應(yīng)燃料費用也是不一樣，但往往在實際模型中沒有考慮這點或者做簡單線性處理。③對動態(tài)車輛調(diào)度問題研究相對較少。動態(tài)車輛路徑問題取得了一定的研究成果，但是其研究的深度還不夠，對動態(tài)車輛路徑問題的模型研究還很少，對動態(tài)信息處理的研究不成熟、解決實際問題的能力還比較差。早前的研究中，動態(tài)車輛調(diào)度問題主要是采用靜態(tài)調(diào)度問題的研究思路，先根據(jù)概率確定動態(tài)車輛調(diào)度問題中可能出現(xiàn)的因素，然后采用靜態(tài)車輛調(diào)度問題的模型解決。這種研究思路雖然可行，但是對于解決實際問題意義不大。近年來，隨著量子算法等新算法和改進算法研究的深入，動態(tài)車輛調(diào)度問題研究思路也在轉(zhuǎn)變。譬如，利用分布估計算法解決動態(tài)車輛調(diào)度問題就是值得研究的方向。分布估計算法是遺傳算法和統(tǒng)計學相結(jié)合的思想，它是基于概率模型的進化，更能適應(yīng)動態(tài)的優(yōu)化。

今后物流配送車輛調(diào)度問題研究的重點還是在調(diào)度模型與求解算法這兩點上。調(diào)度模型越貼近實際，考慮的因素越多，對模型的構(gòu)建以及求解算法要求越高。目前算法改進思路大致有三種：（1） 對現(xiàn)有算法進行細節(jié)上調(diào)整；（2） 采用混合算法的方式；（3） 根據(jù)對自然界的探索并結(jié)合交叉學科提出新的算法。第一種改進思路受算法自身缺陷的限制，求解性能一般；第三種改進思路需要較長時間探索并完善新算法且算法本身也需要進一步改進。所以，在可以預見的較長時間里，求解算法更多會是多種算法的混合，混合算法會是今后研究物流配送車輛調(diào)度問題的重點與熱點。

[1] Dantzig G, Ramser J. The truck dispatching problem[J]. Managment Science, 1959(6):80-91.

[2] 葛顯龍. 面向云配送模式的車輛調(diào)度問題及算法研究[D]. 重慶：重慶大學，2011:4-5.

[3] 王旭，葛顯龍，代應(yīng). 基于兩階段求解算法的動態(tài)車輛調(diào)度問題研究[J]. 控制與決策，2012,27(2):175-181.

[4] 黃震. 混合量子粒子群算法求解車輛路徑問題[J]. 工程與應(yīng)用，2013,49(24):219-223.

[5] 周明，孫樹棟. 遺傳算法原理及應(yīng)用[M]. 北京：國防工業(yè)出版社，1999:78-83.

[6] 杜宗宗，劉國棟. 基于混合遺傳模擬退火算法求解TSP 問題[J]. 計算機工程與應(yīng)用，2010,46(29):40-46.

[7] 喬彥平，張駿. 基于一種改進遺傳模擬退火算法的TSP 求解[J]. 計算機仿真，2009,26(5):205-208.

[8] 曹二保，賴明勇，聶凱,等. 大規(guī)模物流配送車輛調(diào)度問題研究[J]. 湖南大學學報（自然科學版），2007,34(12):89-92.

[9] 吳天羿，許繼恒. 基于混合遺傳算法的模糊需求車輛路徑問題[J]. 解放軍理工大學學報（自然科學版），2014,15(5):475-481.

[10] 劉家利，馬祖軍. 存在車輛租賃及共享且有時間窗的多配送中心開環(huán)VRP[J]. 系統(tǒng)工程理論與實踐，2013,33(3):666-675.

[11] 李婭，王東，楊躍武,等. 改進的量子粒子群算法求解車輛路徑問題[J]. 計算機與數(shù)學工程，2013,284(6):870-886.

[12] 李艷芳，姜磊，黃洪亮. 基于量子粒子群優(yōu)化算法的車輛路徑問題[J]. 計算機與數(shù)字工程，2008,211(3):25-27.

[13] 秦家嬌，張勇，毛劍琳,等. 基于粒子碰撞的粒子群算法求解帶時間窗車輛調(diào)度問題[J]. 計算機應(yīng)用研究，2012,29(4):1253-1256.

[14] 劉芹，史忠科. 混合粒子群算法求解交通路網(wǎng)中的車輛調(diào)度問題[J]. 控制與決策，2006,21(11):1284-1288.

[15] 張麗艷，龐小紅，夏蔚軍,等. 帶時間窗車輛路徑問題的混合粒子群算法[J]. 上海交通大學學報，2006(11):90-94.

[16] 李德富，郭海湘，劉龍輝,等. 改進型粒子群優(yōu)化算法求解車輛路徑優(yōu)化問題[J]. 計算機工程與應(yīng)用，2012,48(20):216-223.

[17] 羅鴻斌. 多車場多車型車輛調(diào)度問題的改進粒子群算法[J]. 計算機工程與應(yīng)用，2014,50(7):251-253.

[18] 何小鋒，馬良. 帶時間窗車輛路徑問題的量子蟻群算法[J]. 系統(tǒng)工程理論與實踐，2013,33(5):1255-1261.

[19] 沈鵬. 物流配送路徑優(yōu)化問題求解的量子蟻群算法[J]. 計算機工程與應(yīng)用，2013,49(21):56-59.

[20] 王素欣，高利，崔小光,等. 多需求點車輛調(diào)度模型及其群體智能混合求解[J]. 自動化學報，2008,34(1):102-104.

[21] 馬建華，房勇，袁杰. 多車場多車型最快完成車輛路徑問題的變異蟻群算法[J]. 系統(tǒng)工程理論與實踐，2011,31(8):1508-1516.

[22] 李琳，劉士新，唐加福. 改進的蟻群算法求解帶時間窗的車輛路徑問題[J]. 控制與決策，2010,25(9):1379-1383.

[23] 王江晴，覃俊，李子茂. 求解動態(tài)最優(yōu)路徑的混合優(yōu)化算法[J]. 通信學報，2008,29(7):135-140.