肖正中，譚建，周玉峰，曾俊

1 貴州省煙草公司黔東南州公司，貴州凱里，556000；

2 貴州財(cái)經(jīng)大學(xué)，貴州貴陽(yáng)，550003

跨區(qū)域多配送中心車(chē)輛調(diào)度智能優(yōu)化研究

肖正中1，譚建2，周玉峰1，曾俊1

1 貴州省煙草公司黔東南州公司，貴州凱里，556000；

2 貴州財(cái)經(jīng)大學(xué)，貴州貴陽(yáng)，550003

跨區(qū)域多配送中心車(chē)輛調(diào)度是一個(gè)典型的NP難題，是當(dāng)前運(yùn)籌學(xué)領(lǐng)域的一個(gè)研究熱點(diǎn)。本文采用邊界分配法將該問(wèn)題轉(zhuǎn)化為單配送中心車(chē)輛調(diào)度問(wèn)題，并結(jié)合遺傳算法與蟻群算法求解跨區(qū)域配送最優(yōu)調(diào)度方案。以貴州省黔東南州煙草公司物流中心卷煙配送為背景進(jìn)行了仿真分析，結(jié)果表明了算法的有效性。

車(chē)輛調(diào)度；邊界分配法；遺傳算法；啟發(fā)式算法

21世紀(jì)電子商務(wù)的蓬勃發(fā)展為物流行業(yè)帶來(lái)了新的機(jī)遇和挑戰(zhàn)[1]。由于客戶數(shù)量巨大，貨物需求量和配送時(shí)間要求的多樣性，在車(chē)輛載重、車(chē)輛最大行駛距離等方面的約束，使得當(dāng)前物流問(wèn)題變得非常復(fù)雜，亟需對(duì)物流問(wèn)題建模并研究準(zhǔn)確高效的求解算法。

現(xiàn)代物流體系建設(shè)主要涉及配送中心選址與配送車(chē)輛調(diào)度[2]。配送車(chē)輛調(diào)度是物流系統(tǒng)的關(guān)鍵環(huán)節(jié)，在配送時(shí)間、貨物需求量、配送中心車(chē)輛數(shù)目、車(chē)輛載重和車(chē)輛最長(zhǎng)運(yùn)載里程等限制下，采用某種算法得到最優(yōu)配送路線[3]。依據(jù)配送中心數(shù)目的多少，可將配送車(chē)輛調(diào)度問(wèn)題劃分為單配送和多配送中心車(chē)輛調(diào)度問(wèn)題。在一個(gè)物流體系中往往存在多個(gè)配送中心共同協(xié)作配送特定區(qū)域內(nèi)客戶。

跨區(qū)域多配送中心車(chē)輛調(diào)度是針對(duì)各配送中心所劃定的配送區(qū)域進(jìn)行綜合車(chē)輛調(diào)度，是一個(gè)NP難題[4]，隨著配送中心數(shù)目及客戶數(shù)目的增加，候選的配送方案數(shù)量以指數(shù)形式增加。因此，尋找合適的算法快速準(zhǔn)確找到配送方案問(wèn)題的全局最優(yōu)解是該問(wèn)題的研究重點(diǎn)。目前很多文獻(xiàn)對(duì)多配送中心車(chē)輛調(diào)度問(wèn)題進(jìn)行了研究[5-6]，研究集中在兩個(gè)方面，一是采用一定的客戶分配方法將多配送中心問(wèn)題轉(zhuǎn)換為單配送中心問(wèn)題，二是設(shè)計(jì)算法解決單配送中心車(chē)輛調(diào)度問(wèn)題。王征等（2013）以顧客時(shí)間窗偏離程度最小化和配送成本最小化為目標(biāo),在Solomon提出的標(biāo)準(zhǔn)算例上建立了問(wèn)題的數(shù)學(xué)模型及其求解算法[7]。馬宇紅等（2013）針對(duì)大規(guī)模的多配送中心多車(chē)型車(chē)輛調(diào)度問(wèn)題提出了一種新的多片段染色體混合編碼算法[8]。殷脂和葉春明（2014）提出了采用聚類分析最短距離分配法將多配送中心車(chē)輛調(diào)度問(wèn)題動(dòng)態(tài)地分解為多個(gè)單配送中心車(chē)輛調(diào)度問(wèn)題進(jìn)行求解的策略[9]。孫壯志等（2014）采用中心聚類、禁忌搜索、局部搜索等多種專業(yè)算法研究了卷煙配送調(diào)度問(wèn)題[10]。楊珍花等（2015）采用混合模擬退火算法分析了冷藏車(chē)多車(chē)型混合配送調(diào)度優(yōu)化[11]。

本文針對(duì)多配送中心車(chē)輛調(diào)度問(wèn)題，首先采用邊界分配法將多配送中心車(chē)輛調(diào)度問(wèn)題轉(zhuǎn)化為單配送中心車(chē)輛調(diào)度問(wèn)題，其次將單配送中心車(chē)輛調(diào)度問(wèn)題分解為車(chē)輛分配與單車(chē)輛路線優(yōu)劃兩個(gè)互相關(guān)聯(lián)的子問(wèn)題，并結(jié)合遺傳算法和蟻群算法求解。邊界分配法是將客戶分為邊界點(diǎn)位置客戶和非邊界點(diǎn)位置客戶，非邊界點(diǎn)位置客戶根據(jù)最近分配原則分配，邊界點(diǎn)位置客戶的分配由最大節(jié)約距離確定。遺傳算法是模擬群體的個(gè)體按照它們對(duì)環(huán)境適應(yīng)度實(shí)現(xiàn)優(yōu)勝劣汰的進(jìn)化過(guò)程。蟻群算法是模擬螞蟻覓食行為的優(yōu)化算法，采用分布式正反饋并行計(jì)算機(jī)制尋找最優(yōu)路徑，易與其他方法結(jié)合，且具有較強(qiáng)的魯棒性。

本文創(chuàng)新點(diǎn)體現(xiàn)在兩個(gè)方面：（1）提出了配送中心-客戶距離關(guān)系矩陣，研究了該矩陣的對(duì)稱性等基本性質(zhì)，并將路線長(zhǎng)度、載重量計(jì)算等轉(zhuǎn)換為矩陣運(yùn)算，使得優(yōu)化目標(biāo)和約束條件的表述更加清晰嚴(yán)格；（2）采用邊界分配法結(jié)合遺傳算法、蟻群算法對(duì)多配送中心車(chē)輛調(diào)度問(wèn)題進(jìn)行求解，并根據(jù)黔東南州煙草公司物流配送中心調(diào)動(dòng)數(shù)據(jù)進(jìn)行仿真驗(yàn)證，仿真結(jié)果說(shuō)明了算法的有效性。

1 多配送中心車(chē)輛調(diào)度問(wèn)題數(shù)學(xué)模型

多配送中心車(chē)輛調(diào)度模型中，配送中心表示為集合P={p1，p2，…，pm}，客戶表示為集合Q={q1，q2，…，qn}，且m＞1，n＞1?？蛻舻呢浳镄枨罅勘硎緸榧蟁={r1，r2，…，rn}，其中ri表示客戶qi的需求量。車(chē)輛調(diào)度問(wèn)題中一個(gè)重要輸入?yún)?shù)是配送中心與客戶相對(duì)距離，該參數(shù)直接影響到最佳調(diào)度路線的分配。為準(zhǔn)確描述配送中心與客戶的相對(duì)距離，本文提出距離關(guān)系矩陣：

其中，dx,y表示位置x到位置y的實(shí)際最短貨運(yùn)距離，dx,y會(huì)隨道路維修等實(shí)際情況變動(dòng)，因此具有時(shí)間相關(guān)性，但考慮到這種變動(dòng)情況很緩慢且離散，單次配送路線規(guī)劃中假定dx,y是常量。當(dāng)兩地之間最短貨運(yùn)距離不確定時(shí)，dx,y也可用球面距離代替。關(guān)于距離關(guān)系矩陣有如下兩個(gè)結(jié)論：

（1）dx,x=0，即同一位置之間的距離為0；

（2）D=DT，即地點(diǎn)x與地點(diǎn)y的距離等于地點(diǎn)y與地點(diǎn)x之間的距離。單向道路可能會(huì)導(dǎo)致dx,y≠dy,x，考慮到這種影響很小，本文假定dx,y=dy,x。

利用矩陣D可計(jì)算配送路徑的行駛距離。例如某一運(yùn)輸車(chē)從配送中心p1出發(fā)，先送貨到客戶q1，再送貨到客戶q2，然后回到配送中心p1。將其配送路線簡(jiǎn)記為L(zhǎng)=p1→q1→q2→p1，則該路線的總距離為d（L）=dp1,q1+dq1,q2+dq2,p1。由于每輛運(yùn)輸車(chē)均是從某一配送中心出發(fā)，經(jīng)過(guò)若干客戶后回到原配送中心，所以配送路線L在拓?fù)鋵W(xué)上是一個(gè)簡(jiǎn)單環(huán)。記QL為路線L上的客戶集合，例如Qp1→q1→q2→p1={q1,q2}。在每個(gè)客戶的貨物僅由一個(gè)車(chē)輛配送的前提下，任兩個(gè)配送路線QL的交集應(yīng)為空集。每條配送路線上運(yùn)輸車(chē)總載重量G(L)為該路線途徑的客戶的需求量總和，例如G(p1→q1→q2→p1)=r1+r2。實(shí)際問(wèn)題中，存在車(chē)輛載重量和單次最大行駛距離的限制，即d(L)≤dup，G(L)≤Gup，其中，dup表示一次配送最大行駛距離，Gup表示車(chē)輛最大載重量。由于配送產(chǎn)品均為卷煙，其體積與重量基本呈正比，因此，本文只考慮車(chē)輛最大載重量。

總配送成本包含很多方面，如車(chē)輛油耗、車(chē)輛損耗、人工成本，時(shí)間成本等等。總成本大致與車(chē)輛總行駛里程成正比，可假設(shè)比例系數(shù)為常數(shù)k，此時(shí)多配送中心車(chē)輛調(diào)度問(wèn)題的優(yōu)化目標(biāo)即為總配送成本最小。綜上得到車(chē)輛調(diào)度問(wèn)題的數(shù)學(xué)模型為：

其中，四個(gè)約束條件分別為：（1）最大行駛距離約束；（2）載重約束；（3）每個(gè)客戶僅由一臺(tái)車(chē)輛送貨；（4）所有客戶需求全部滿足。該優(yōu)化問(wèn)題可分為兩步求解。步驟一：為每位客戶分配一個(gè)配送中心負(fù)責(zé)為其運(yùn)貨；步驟二：每個(gè)配送中心選擇最優(yōu)的車(chē)輛數(shù)以及配貨路線完成配貨。若采用窮舉法則第一步的問(wèn)題復(fù)雜度為O(mn)，第二步是m個(gè)相互獨(dú)立的單配送中心車(chē)輛調(diào)度問(wèn)題，該問(wèn)題具有NP復(fù)雜度。鑒于問(wèn)題的復(fù)雜度，每個(gè)步驟均需采用一定的算法快速求解。下文分別用邊界分配法和遺傳算法解決步驟一與步驟二。

2 客戶分配方法

2.1 最近距離分配法

步驟一可看做一個(gè)聚類問(wèn)題，聚類中心為配送中心，聚類目的是將每個(gè)客戶按一定標(biāo)準(zhǔn)分配給某一配送中心。最簡(jiǎn)單的標(biāo)準(zhǔn)將客戶歸類到與其距離最近的配送中心，該方法已經(jīng)在部分文獻(xiàn)中使用[6-7]。但該聚類方式在某些情形下不合理，例如某一地區(qū)包含兩個(gè)配送中心和兩個(gè)客戶，坐標(biāo)分別為p1∶(2，2)，p2∶(6，2)，q1∶(3，5)，q2∶(5，5)，如圖1 所示。

圖1配送路線比較Fig.1 Distribution route comparison

配送路線一的總運(yùn)輸距離為：dis1=Dp1→q1→p1+Dp2→q2→p2=dp1,q1+dq1,p1+dp2,q2+dq2,p2=12.64

配送路線二的總運(yùn)輸距離為：dis2=Dp1→q2→p1=dp1,q1+dq1,q2+dq2,p1=9.4

當(dāng)采用最近距離分配法時(shí)，得到配送路線一，這種配送方案顯然不如配送方案二。最近距離分配法僅考慮了配送中心與客戶之間的距離，而未考慮客戶之間的距離。

2.2 邊界分配法

采用邊界分配法分配客戶時(shí)包含兩個(gè)過(guò)程：首先確定邊界點(diǎn)，其次是計(jì)算最大節(jié)約距離，并將邊界點(diǎn)分配給最大節(jié)約距離對(duì)應(yīng)的配送中心。取矩陣D的左下子塊并記為M，即

將矩陣M的第i行記為Mi，則Mi表示客戶qi到各配送中心之間的距離。記min（Mi）為Mi中最小的元素值；記submin（Mi）為Mi中次小的元素值。取一個(gè)臨界值σ，σ∈[0，1]。當(dāng)min（Mi）/submin（Mi）＜σ時(shí)，將客戶i分配給min（Mi）相應(yīng)的分配中心；當(dāng) min（Mi）/submin（Mi）＞=σ時(shí)，將客戶i標(biāo)記為邊界點(diǎn)。按照下述步驟為邊界點(diǎn)分配配送中心，記

則Spi（qk）表示當(dāng)邊界點(diǎn)qk分配給配送中心pi時(shí)所能節(jié)約的配送距離。則表示分配邊界點(diǎn)qk后所能節(jié)約的最大配送距離。將邊界點(diǎn)qk分配給對(duì)應(yīng)的pi。

臨界值σ取值會(huì)影響到邊界點(diǎn)的分配。當(dāng)σ=1時(shí)，任何客戶均按照最近距離分配，邊界分配法退化為最近距離分配法；當(dāng)σ=0時(shí)，任何客戶均是臨界點(diǎn)。邊界分配法既考慮到了配送中心與客戶之間的距離，又考慮到了客戶與客戶之間的距離，因此更加合理。

3 車(chē)輛選擇與線路優(yōu)化算法

3.1 基于遺傳算法的車(chē)輛分配方案

邊界分配法分配客戶之后，多配送中心車(chē)輛調(diào)度問(wèn)題轉(zhuǎn)換為單配送中心車(chē)輛調(diào)度問(wèn)題。單配送中心車(chē)輛調(diào)度問(wèn)題可拆分為車(chē)輛選擇和路線優(yōu)化兩個(gè)相互關(guān)聯(lián)的子問(wèn)題。車(chē)輛選擇是單配送中心車(chē)輛調(diào)度問(wèn)題的核心，可采用遺傳算法解決[12-13]，其流程如圖2所示。

圖2 遺傳算法流程圖Fig.2 Flow chart of genetic algorithm

該矩陣表示將五個(gè)客戶分配給三臺(tái)車(chē)輛的一個(gè)方案，其中第一和第三個(gè)客戶分配給第一輛車(chē)；第二和第五個(gè)客戶分配給第二臺(tái)車(chē)；第四個(gè)客戶分配給第三臺(tái)車(chē)。

適應(yīng)度函數(shù)定義。適應(yīng)度函數(shù)用于評(píng)價(jià)遺傳算法中每個(gè)個(gè)體編碼的好壞，適應(yīng)度較高的個(gè)體優(yōu)先遺傳到下一代。車(chē)輛配送方案的總行駛里程越低，其相應(yīng)染色體的適應(yīng)度越高。因此將總行駛里程的倒數(shù)作為適應(yīng)度函數(shù)。

生成初始種群。根據(jù)車(chē)輛數(shù)和客戶數(shù)隨機(jī)生成N個(gè)矩陣C作為初始種群G0={C1,C2,…,CN}，種群中的每個(gè)個(gè)體必須滿足最大行駛距離限制和最大載重量限制，否則將該個(gè)體淘汰并隨機(jī)產(chǎn)生新的個(gè)體直到滿足限制條件為止。

種群選擇與復(fù)制。種群中的個(gè)體以一定概率進(jìn)行選擇與復(fù)制，每個(gè)個(gè)體的選擇概率與其適應(yīng)度成正比。概率選擇機(jī)制確保了優(yōu)秀個(gè)體有更大機(jī)會(huì)遺傳到下一代。

交叉操作。種群的選擇復(fù)制本質(zhì)上不產(chǎn)生新的個(gè)體，即新的車(chē)輛分配方案。因此，經(jīng)種群選擇與復(fù)制操作后，雖然種群的平均適應(yīng)度上升了，但其適應(yīng)度的上限并沒(méi)有升高。交叉操作以一定概率隨機(jī)交換種群中兩個(gè)個(gè)體的某些片段，由此產(chǎn)生一些新的個(gè)體。交叉操作有利于提升種群適應(yīng)度上限，從而得到更合理的配送方案。

變異。變異操作隨機(jī)對(duì)個(gè)體中的某些基因座的值作變動(dòng)，即對(duì)矩陣C的某些列中1的位置進(jìn)行變換。遺傳算法中，交叉算子具有全局搜索能力，而變異算子具有局部搜索能力，兩者相輔相成促進(jìn)遺傳算法得到全局最優(yōu)解。

終止規(guī)則。當(dāng)兩次迭代過(guò)程得到的群體適應(yīng)度上限相差很小或達(dá)到迭代次數(shù)上限時(shí)停止迭代，選擇最大適應(yīng)度對(duì)應(yīng)的分配方案作為最終車(chē)輛分配方案。

3.2 基于蟻群算法的車(chē)輛路線優(yōu)化

車(chē)輛路線安排問(wèn)題實(shí)質(zhì)上是一個(gè)旅行商問(wèn)題（TSP），當(dāng)車(chē)輛分配方案確定時(shí)，車(chē)輛路線優(yōu)化可用蟻群算法解決[14]。假設(shè)車(chē)輛所屬配送中心的坐標(biāo)為（0，0），隨機(jī)生成20個(gè)客戶。采用的蟻群算法基本參數(shù)如表1所示。

蟻群算法是一種進(jìn)化算法，螞蟻個(gè)數(shù)越多，算法搜索的路徑越多，得到的解越精確，但是蟻群越大計(jì)算復(fù)雜度也越大。信息素重要程度體現(xiàn)了已知信息對(duì)螞蟻路徑選擇的重要程度，該值越大蟻群運(yùn)動(dòng)軌跡的隨機(jī)性也就越弱。啟發(fā)式因子的重要程度則會(huì)影響蟻群尋找路徑時(shí)的先驗(yàn)性，該值越大螞蟻越容易選擇局部最優(yōu)路徑。信息素蒸發(fā)系數(shù)對(duì)算法收斂速度有很大影響。信息素增加強(qiáng)度系數(shù)表示螞蟻釋放信息量的大小，該系數(shù)越大算法收斂性越強(qiáng)，同時(shí)也更容易陷入局部最優(yōu)解。

表1 蟻群算法基本參數(shù)Tab.1 basic parameters of ant colony algorithm

利用蟻群算法得最短路徑為：2-16-9-17-7-1-15-20-10-13-8-14-3-19-12-6-5-11-18-4，最短路徑距離為95.0333，路線圖以及收斂曲線如圖3所示。

圖3 基于蟻群算法的路線圖及收斂曲線Fig.3 route map and convergence curve based on ant colony algorithm

4 仿真分析

4.1 參數(shù)設(shè)置

本節(jié)以黔東南州煙草公司物流配送為例做仿真分析。該公司共有六個(gè)配送站，以東經(jīng)107度北緯25度為原點(diǎn)，在橫坐標(biāo)[50,250]縱坐標(biāo)[50,250]的矩形區(qū)域內(nèi)隨機(jī)產(chǎn)生50個(gè)點(diǎn)代表相應(yīng)客戶位置。每個(gè)點(diǎn)與最近鄰的配送站的距離小于60km。配送中心以及客戶位置如圖4所示，中小矩形代表配送中心，小圓形代表客戶。不同的配送中心以不同顏色區(qū)分。模型參數(shù)設(shè)置如下：每個(gè)配送中心的車(chē)輛數(shù)目為4，每輛車(chē)最大載重量dup=8噸，每輛車(chē)的最大行駛距離Gup=120km，每個(gè)客戶的貨物需求量在1噸至2噸之間隨機(jī)生成。

圖4 配送中心以及隨機(jī)產(chǎn)生的客戶位置圖Fig.4 Distribution center and the random generation of customer location map

4.2 分配客戶

分別用最近距離法和邊界分配法分配客戶，分配結(jié)果如圖5和圖6所示。為清晰地表示分配結(jié)果，客戶的顏色用分配中心所屬的顏色標(biāo)記。

圖5 最近距離法分配客戶Fig.5 Nearest distance distribution method

圖6 邊界分配法Fig.6 Boundary distribution method

對(duì)比圖5和圖6可知，不同的客戶分配方法會(huì)產(chǎn)生不同的分配結(jié)果。最近距離分配法將客戶分配給距離最近的配送中心，這種配送方法可能將大量不同方位的客戶分配到同一配送中心，而邊界分配法傾向于將“成簇”的客戶分配到同一配送中心。

4.3 計(jì)算最佳配送方案

本文采用遺傳算法和蟻群算法對(duì)六個(gè)配送中心計(jì)算其最佳配送方案，限于篇幅僅展示黎平配送中心的配送方案和從江配送中心的配送方案，分別如圖6和圖7所示。圖6中黎平配送中心負(fù)責(zé)6個(gè)客戶的貨物配送，由兩輛車(chē)完成，其中一輛車(chē)負(fù)責(zé)西北方向的三個(gè)客戶，另一輛車(chē)負(fù)責(zé)東南方向的三個(gè)客戶；圖7中從江配送中心負(fù)責(zé)七個(gè)客戶的貨物配送，同樣由兩輛車(chē)完成，其中一輛車(chē)負(fù)責(zé)西面的4個(gè)客戶，另外一輛車(chē)負(fù)責(zé)東面的三個(gè)客戶。

圖7 黎平車(chē)輛調(diào)度路線圖Fig.7 Liping vehicle routing map

圖8 從江車(chē)輛調(diào)度路線圖Fig.8 Congjiang vehicle routing map

作為對(duì)比，本文采用窮舉法求解黎平和從江配送中心的配送路線。含有m輛車(chē)，n個(gè)客戶的配送中心，其客戶分配方案總共有mn種，每輛車(chē)的行駛路線數(shù)為k!，其中k為該車(chē)輛負(fù)責(zé)的客戶數(shù)目。窮取法可以評(píng)價(jià)所有可能的配送方案從而得到最優(yōu)解。但當(dāng)m和n數(shù)值較大時(shí)，窮舉法計(jì)算上難以實(shí)現(xiàn)。而結(jié)合遺傳算法及蟻群算法求解黎平和從江配送中心的配送方案，得到與窮舉法同樣的解（正向與反向的路線配送長(zhǎng)度相同，可看作相同方案），但同等計(jì)算機(jī)配置下耗時(shí)僅為窮舉法的百分之一。該對(duì)比說(shuō)明結(jié)合遺傳算法及蟻群算法應(yīng)用于求解配送方案是一種準(zhǔn)確高效的方法。

為研究算法的收斂性與有效性，論文模擬了包含3輛車(chē)、12個(gè)客戶的運(yùn)輸調(diào)度問(wèn)題，結(jié)合遺傳算法及蟻群算法中隨機(jī)選取初始種群重復(fù)100次實(shí)驗(yàn)，在其中85次實(shí)驗(yàn)中該算法均得到與窮舉法相同的配送方案，即收斂到全局最優(yōu)解，而在其余15次實(shí)驗(yàn)中收斂到局部最優(yōu)解。這說(shuō)明遺傳算法及蟻群算法的結(jié)合有很大概率得到全局最優(yōu)解，是一種有效的方法。

5 總結(jié)與展望

本文采用邊界分配法將多分配中心車(chē)輛調(diào)度問(wèn)題轉(zhuǎn)化為單分配中心車(chē)輛調(diào)度問(wèn)題，并將單分配中心車(chē)輛調(diào)度問(wèn)題分解為車(chē)輛選擇與單車(chē)輛路線規(guī)劃兩個(gè)互相關(guān)聯(lián)的子問(wèn)題，分別用遺傳算法和蟻群算法求解。問(wèn)題的轉(zhuǎn)化和分解提高了求解速度，有利于解決大規(guī)模跨區(qū)域倉(cāng)儲(chǔ)配送問(wèn)題?？蛻舴峙浞椒▽?duì)后續(xù)的車(chē)輛路線規(guī)劃結(jié)果有很大影響，邊界分配法相比于最近距離分配法更加合理，然而更有效的客戶分配法有待后續(xù)研究。

[1]郇青.電子商務(wù)物流發(fā)展模式研究[D].山東大學(xué), 2012.HUAN Qing.E-commerce logistics development model [D].Shandong University, 2012.

[2]張培林, 魏巧云.物流配送中心選址模型及其啟發(fā)式算法[J].交通運(yùn)輸工程學(xué)報(bào), 2003, 3(02):65-68.ZHANG Peilin, WEI Qiaoyun.Model of logistics distribution center location model and its heuristic algorithm [J].Journal of Traf fi c and Transportation Engineering, 2003, 3 (02): 65-68.

[3]劉云忠, 宣慧玉.車(chē)輛路徑問(wèn)題的模型及算法研究綜述[J].管理工程學(xué)報(bào), 2005, 19(01):124-130.LIU Yunzhong, XUAN Huiyu.Research on model and algorithm of vehicle routing problem [J].Journal of Management Engineering,2005, 19 (01): 124-130.

[4]Bogdanovi? M.Overview of some solved NP-complete problems in graph theory[J].Advances and Applications in Mathematical Science, 2011, 9(1):35-45.

[5]施朝春, 王旭, 葛顯龍.帶有時(shí)間窗的多配送中心車(chē)輛調(diào)度問(wèn)題研究[J].計(jì)算機(jī)工程與應(yīng)用, 2009, 45(34):21-24.SHI Zhaochun, WANG Xu, GE Xianlong.Vehicle routing problem with time windows in multiple distribution centers [J].Computer Engineering and Applications, 2009, 45 (34): 21-24.

[6]邢鵬.基于云平臺(tái)的多配送中心車(chē)輛調(diào)度問(wèn)題研究[D].北京交通大學(xué), 2013.XING Peng.Study on vehicle scheduling problem of multi distribution center based on cloud platform [D].Beijing Jiaotong University, 2013.

[7]王征,胡祥培,王旭坪.行駛時(shí)間延遲下配送車(chē)輛調(diào)度的干擾管理模型與算法[J].系統(tǒng)工程理論與實(shí)踐,2013,33(2):378-387.WANG Zheng, HU Xiangpei, WANG Xuping.Disturbance management model and algorithm for distribution vehicle scheduling with time delay [J].System Engineering Theory and Practice, 2013,33(2):378-387.

[8]馬宇紅,姚婷婷,張浩慶.基于分區(qū)的多配送中心多車(chē)型車(chē)輛調(diào)度問(wèn)題與遺傳算法設(shè)計(jì)[J].科技導(dǎo)報(bào),2013,(2):61-67.MA Yuhong, YAO Tingting, ZHANG Haoqing.Multi vehicle scheduling problem and genetic algorithm design based on partition of multi distribution centers [J].Technology review, 2013,(2):61-67.

[9]殷脂,葉春明.多配送中心物流配送車(chē)輛調(diào)度問(wèn)題的分層算法模型[J].系統(tǒng)管理學(xué)報(bào),2014,(4):602-606.YIN Zhi, YE Chunming.Hierarchical algorithm model of logistics distribution vehicle scheduling problem of multi distribution center[J].Journal of Systems Management, 2014,(4):602-606.

[10]孫壯志,鄢烈虎,要學(xué)瑋.基于線路優(yōu)化算法的卷煙配送調(diào)度系統(tǒng)[J].中國(guó)煙草學(xué)報(bào),2014,(5):128-133.SUN Zhuangzhi, YAN Liehu, YAO Xuewei.Cigarette distribution scheduling system based on line optimization algorithm[J].Chinese Journal of Tobacco, 2014,(5):128-133.

[11]楊珍花,賴平仲,湯洋等.冷藏車(chē)多車(chē)型混合配送調(diào)度優(yōu)化[J].系統(tǒng)工程,2015,(10):28-36.Yang Zhenhua, Lai Pingzhong, Tang Yang, et al.Multi vehicle type mixed refrigerated vehicle distribution scheduling optimization [J].System Engineering, 2015,(10):28-36.

[12]Bayley D J, Hart fi eld R J, Burkhalter J E, et al.Design Optimization of a Space Launch Vehicle Using a Genetic Algorithm[J].Journal of Spacecraft & Rockets, 2015, 45(4):733-740.

[13]Gage P J, Kroo I M, Sobieski I P.Variable-complexity genetic algorithm for topological design[J].Aiaa Journal, 2015,33(11):2212-2217.

[14]許爭(zhēng)爭(zhēng), 唐加福.基于協(xié)作的三階段啟發(fā)式算法求解多行程車(chē)輛行程問(wèn)題[J].南開(kāi)大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015,(5):51-59.XU Zhengzheng, TANG Jafu.Three stage heuristic algorithm for solving multi stroke vehicle routing problem [J].Journal of Nankai University (NATURAL SCIENCE EDITION), 2015, (5): 51-59.

Research on intelligent optimization of trans-regional vehicle scheduling among multiple distribution centers

XIAO Zhengzhong1, TAN Jian2*, ZHOU Yufeng1, ZENG Jun1
1 Guizhou Provincial Tobacco Company Qiandongnan Branch, Kaili, Guizhou 556000, China
2 Guizhou University of Finance and Economics, Guiyang 550003, China

Trans-regional vehicle scheduling among multiple distribution centers is a typical NP issue.Boundary distribution method was applied to transform this issue into the issue of vehicle scheduling in single distribution center.An optimal scheduling scheme was then obtained through genetic algorithm combined with ant colony optimization.Simulation analysis was carried out using logistics data of Qiandongnan Tobacco Company in Guizhou province.Results of the analysis proved that the method is valid and ef fi cient.

vehicle scheduling; boundary distribution; genetic algorithm; ant colony optimization

肖正中，譚建，周玉峰，等.跨區(qū)域多配送中心車(chē)輛調(diào)度智能優(yōu)化研究[J].中國(guó)煙草學(xué)報(bào)，2017, 23（4）

肖正中(1977—)，碩士，經(jīng)濟(jì)師，煙草供應(yīng)鏈管理，Email：gzxiaozz@163.com

譚 建(1982—)，博士，副教授，煙草供應(yīng)鏈管理，Email：tanjian123@126.com

2016-08-23；< class="emphasis_bold">網(wǎng)絡(luò)出版日期：

日期：2017-03-06

：XIAO Zhengzhong, TAN Jian, ZHOU Yufeng,et al.Research on intelligent optimization of trans-regional vehicle scheduling among multiple distribution centers [J].Acta Tabacaria Sinica, 2017, 23(4)

*Corresponding author.Email：tanjian123@126.com