面向JIT采購的多目標(biāo)車輛調(diào)度

李雨鑫，李悅悅

河北工業(yè)大學(xué) 經(jīng)濟(jì)管理學(xué)院，天津300401

準(zhǔn)時(shí)制（Just-In-Time，JIT）采購，是一種基于準(zhǔn)時(shí)制生產(chǎn)的采購模式，指企業(yè)按需求將原料以小批量、多批次的方式進(jìn)行準(zhǔn)時(shí)采購，以低庫存、降成本為目標(biāo)，從而提升企業(yè)市場(chǎng)競(jìng)爭(zhēng)力。JIT采購最初豐田公司（Toyota automobiles）提出且在工業(yè)生產(chǎn)中被廣泛應(yīng)用[1]。不少學(xué)者在此基礎(chǔ)上對(duì)JIT采購的研究進(jìn)行了完善，王玉燕等[2]以提高JIT采購交付效率為目標(biāo)，針對(duì)幾種不同的采購模型制定了相應(yīng)的采購和供應(yīng)策略；楊文勝等[3]以提高準(zhǔn)時(shí)交貨率為目標(biāo)，分析準(zhǔn)時(shí)采購過程中采購商與供應(yīng)商決策的交互影響關(guān)系；也有部分學(xué)者針對(duì)JIT采購的批量?jī)?yōu)化進(jìn)行了深入的研究，Chiu等[4]著重研究了生產(chǎn)環(huán)境對(duì)采購批量的影響，提出一種新的采購運(yùn)輸運(yùn)送批量的方法；聶蘭順等[5]在以上研究的基礎(chǔ)上，比較了不同采購運(yùn)輸批次策略，得到最優(yōu)交付次數(shù)，對(duì)JIT采購進(jìn)行了優(yōu)化決策。

在實(shí)際生產(chǎn)中，路徑的合理規(guī)劃對(duì)JIT采購運(yùn)輸同樣重要，車輛調(diào)度作為影響采購路徑優(yōu)劣的決定性因素，逐漸引起學(xué)術(shù)界的廣泛關(guān)注[6-7]。現(xiàn)實(shí)中JIT環(huán)境下貨物運(yùn)輸?shù)囊粋€(gè)重要目標(biāo)是盡可能地保證貨物能夠及時(shí)交付，因此也將此類問題看成帶有時(shí)間窗的車輛調(diào)度問題（Vehicle Scheduling With Time Window，VRPTW）或?qū)r(shí)間約束作為目標(biāo)函數(shù)的一部分加入VRP模型中，可看作是“軟”時(shí)間窗，即多目標(biāo)車輛調(diào)度問題（MVRP）[8]。眾多學(xué)者從算法和模型兩方面對(duì)此類MVRP問題進(jìn)行了完善，一部分學(xué)者在MVRP模型的基礎(chǔ)上加入條件約束，確保配送效率的同時(shí)降低了問題的求解難度[9-10]；另一部分學(xué)者以MVRP為背景，將人工蜂群算法和禁忌搜索算法相結(jié)合來增加初始種群的多樣性，并通過引進(jìn)復(fù)制和遷移算子，改變粒子的編碼方式且提高算法的精確性[11-12]。

隨著對(duì)JIT運(yùn)輸?shù)纳钊胙芯?，白?guó)仲[13]比較了JIT運(yùn)輸模型與其他運(yùn)輸模型，認(rèn)為基于JIT管理的多品種、多物資的運(yùn)輸問題不同于傳統(tǒng)的運(yùn)輸問題，也不同于帶時(shí)間窗的車輛路徑問題。早期研究者為了盡可能降低JIT采購運(yùn)輸費(fèi)用，采用整合運(yùn)輸、循環(huán)取貨路（MILKRUN）等優(yōu)化方法解決此類問題[14-15]，但此類運(yùn)輸優(yōu)化方法雖然降低了采購費(fèi)用，易導(dǎo)致車輛利用率過低、邊線庫存較大等問題[16]。因此，部分學(xué)者認(rèn)為JIT采購運(yùn)輸時(shí)必須考慮與生產(chǎn)環(huán)節(jié)的有效銜接[17]；李昆鵬等[18]和Chang[19]以最小化運(yùn)輸總成本為目標(biāo)，建立了基于JIT的3PL運(yùn)輸協(xié)調(diào)調(diào)度模型，通過仿真實(shí)驗(yàn)驗(yàn)證其模型的有效性，但是目前3PL運(yùn)輸多數(shù)是同時(shí)服務(wù)多個(gè)制造商，其生產(chǎn)調(diào)度必須服從運(yùn)輸工具調(diào)度，不能及時(shí)響應(yīng)各制造商的生產(chǎn)需求。因此，在研究JIT采購的運(yùn)輸調(diào)度問題時(shí)，既要符合多品種、多頻次、小批量的運(yùn)輸特點(diǎn)，也要考慮采購過程中需要各批次之間的相關(guān)性對(duì)優(yōu)化運(yùn)輸路徑和運(yùn)量的影響。

在滿足采購運(yùn)輸過程中生產(chǎn)不中斷的前提條件下，從物流運(yùn)輸?shù)慕嵌?，JIT采購的VRP問題也可以用配送領(lǐng)域的多目標(biāo)優(yōu)化算法來解決[20]。目前現(xiàn)有的多目標(biāo)優(yōu)化算法，如遺傳算法、禁忌算法在求解時(shí)往往易陷入局部最優(yōu)，導(dǎo)致搜索效率較低，使Pareto解集分布不均衡或提高了解集的精確性而忽略了求解的多樣性[21-22]。因此，不少學(xué)者在解決此類問題時(shí)發(fā)現(xiàn)雖然人工蜂群算法（ABC）全局搜索時(shí)的策略的單一性，且易陷入局部最優(yōu)，但與遺傳算法、禁忌搜索算法相比，人工蜂群算法的信息共享機(jī)制是不同的。因此，針對(duì)傳統(tǒng)的開發(fā)搜索效率低、隨機(jī)性差、易陷入局部最優(yōu)等缺點(diǎn)，通過改進(jìn)隨機(jī)搜索策略和傳統(tǒng)搜索算子，提出了一種改進(jìn)的人工蜂群?jiǎn)l(fā)式算法，提高了求解質(zhì)量和搜索效率，并通過結(jié)果表明，改進(jìn)的人工蜂群算法是解決車輛路徑問題的一種新方法[23]。

在求解多目標(biāo)優(yōu)化問題時(shí)，由于算法每次迭代過程都會(huì)出現(xiàn)新的非支配個(gè)體，但標(biāo)空間內(nèi)非劣解集規(guī)模是有限的，因此如何增加pareto解集的多樣性，同時(shí)保證解集中個(gè)體均勻分布在目標(biāo)空間，也逐漸成為研究的重點(diǎn)。Yang[24]將網(wǎng)格排序、網(wǎng)格擁擠距離和網(wǎng)格坐標(biāo)點(diǎn)距離引入到進(jìn)化算法（MOEAS）迭代中，來區(qū)分個(gè)體在搜索選擇過程中的差異，并利用鄰域和網(wǎng)格優(yōu)勢(shì)關(guān)系調(diào)整個(gè)體適應(yīng)度的調(diào)整策略，以避免局部過度擁擠；實(shí)驗(yàn)結(jié)果表明了該算法在均衡收斂性和多樣性方面的有效性和競(jìng)爭(zhēng)力。本文在滿足JIT采購運(yùn)輸特點(diǎn)的條件下，考慮到運(yùn)輸批次之間的相關(guān)性對(duì)車輛調(diào)度的影響，以最小化車輛使用數(shù)和總路徑為目標(biāo)，建立了雙目標(biāo)模型，并設(shè)計(jì)一種自適應(yīng)網(wǎng)格的人工蜂群算法（GAMOABC）進(jìn)行求解；通過對(duì)目標(biāo)空間進(jìn)行劃分網(wǎng)格，確定解集規(guī)模，保留每個(gè)網(wǎng)格內(nèi)部中當(dāng)前搜索到的非劣解，增加解集的多樣性；同時(shí)利用人工蜂群算法對(duì)網(wǎng)格內(nèi)靠近PF的解，實(shí)現(xiàn)有針對(duì)性、高精度的搜索，并在通過引入位置共享機(jī)制，在跟隨蜂動(dòng)態(tài)搜索后與當(dāng)前網(wǎng)格內(nèi)的引領(lǐng)蜂進(jìn)行位置共享操作，進(jìn)一步提高了算法的精確性，由于算法迭代過程中僅保留了引領(lǐng)蜂與跟隨蜂兩種角色，減少了參數(shù)設(shè)置，有效地提高了搜索效率。

1 模型建立與假設(shè)

如圖1所示采購運(yùn)輸過程，具體問題可描述為：在JIT采購模式下，生產(chǎn)商需要采購n種原料，N={1,2,…,n}表示原料集合，每種原料j,j∈N的需求量為q j。生產(chǎn)商從物流公司租賃K輛車運(yùn)輸，車輛k,k∈K，車載量為Q。從生產(chǎn)商出發(fā)，從供應(yīng)商M j,j∈N處開始安排采購，直到車輛滿載后返回生產(chǎn)商處并將運(yùn)載的原料放入原料庫，確保運(yùn)輸中生產(chǎn)不中斷。采購運(yùn)輸中生產(chǎn)商以一定的消耗速率u j消耗原料j。求解目標(biāo)是在JIT采購模式下，安排運(yùn)輸?shù)耐瑫r(shí)優(yōu)化車輛數(shù)與總運(yùn)輸距離。

圖1 采購運(yùn)輸路線

假設(shè)條件：（1）原料j,j∈N有初始庫存為C j，且?guī)齑嫒萘繜o限；（2）生產(chǎn)商租賃的車輛的型號(hào)，運(yùn)載能力相同；（3）生產(chǎn)準(zhǔn)備時(shí)間和原材料卸載時(shí)間忽略不計(jì)；（4）生產(chǎn)商是從0時(shí)刻開始運(yùn)輸物料；（5）每種原料僅由一種供應(yīng)商提供。

1.1 參數(shù)說明

模型中所用符號(hào)說明：

N={1,2,…,j,…,n}：所需原料的集合。

K={1,2,…,k}：所有租賃的車輛集合。

m={1,2,…}：車輛的運(yùn)輸次數(shù)。

M i：原料i的供應(yīng)商。

u j：原料j的消耗速率。

r j：原料j所需的數(shù)量。

C j：原料j的初始庫存。

t ij：從供應(yīng)商i到供應(yīng)商j的運(yùn)輸時(shí)間/距離。

Q：租賃車輛的運(yùn)載量。

t：當(dāng)前時(shí)刻。

t′：前時(shí)刻。

決策變量：

若第k號(hào)車，第m次運(yùn)輸時(shí)，若供應(yīng)商i緊前于供應(yīng)商j被遍歷，其值為1；否則，為0。

若使用第k輛車其值為1；否則，其值為0。

若原料j沒有被車輛k第m次采購，則令采購量的值為0；若原料j被車輛k運(yùn)輸在第m次采購，則根據(jù)權(quán)值po(k,j)計(jì)算的此次運(yùn)輸?shù)牟少徚浚襭o(k,j)∈(0,1)；若原料j被車輛k運(yùn)輸在第m次采購，且當(dāng)前待運(yùn)量小于其權(quán)值計(jì)算的采購量，則令其值為待運(yùn)量，即：r j-其中，po(k,j)表示車輛k與原料j的對(duì)應(yīng)權(quán)值。

1.2 調(diào)度模型

基于JIT采購的車輛路徑調(diào)度模型構(gòu)造如下：

公式（1）表示最小化運(yùn)輸車輛的數(shù)目；公式（2）表示最小化運(yùn)輸完成的總距離；公式（3）和公式（4）表示原料總需求量遠(yuǎn)大于單車運(yùn)載量且總運(yùn)輸批次大于1；公式（5）確保供應(yīng)商在運(yùn)輸中至少被車輛遍歷一次；公式（6）每次采購運(yùn)輸?shù)脑狭坎荒艹^單車的運(yùn)載量；公式（7）表示車輛k第m次運(yùn)輸完成時(shí)間且采購中不能中斷；公式（8）表示第m批原料的采購交付時(shí)間小于或者等于當(dāng)前原料消耗最快、最先不能滿足生產(chǎn)需要的要料時(shí)間；公式（9）表示當(dāng)每次運(yùn)輸?shù)脑辖桓稌r(shí)，當(dāng)前庫存應(yīng)無限接近為0；公式（10）表示當(dāng)運(yùn)輸完成時(shí)，總運(yùn)輸量與原料需求量相等。

1.3 JIT對(duì)運(yùn)輸調(diào)度的影響分析

JIT模式下的采購運(yùn)輸調(diào)度，不僅要保證采購中生產(chǎn)的連續(xù)性，且在安排車輛調(diào)度時(shí)還要考慮“準(zhǔn)時(shí)化”“零庫存”的運(yùn)輸問題。因此在進(jìn)行生產(chǎn)-采購運(yùn)輸調(diào)度時(shí)既要使車輛在各原料的需求時(shí)間之前到達(dá)，使生產(chǎn)能夠連續(xù)穩(wěn)定的進(jìn)行；也要使各原料的當(dāng)前庫存應(yīng)接近為0，減少出現(xiàn)庫存積壓的現(xiàn)象?；谏鲜龅奶卣鳎疚膶⒃喜少忂^程中的影響因素分為靜態(tài)影響因素與動(dòng)態(tài)影響因素兩種，并且在運(yùn)輸調(diào)度模型中加入特征約束。

影響因素：（1）靜態(tài)因素包括車輛的運(yùn)輸能力、生產(chǎn)原料的需求量以及生產(chǎn)原料消耗速率等相對(duì)固定不變的影響因素；（2）動(dòng)態(tài)因素包括當(dāng)前原料的需求時(shí)間、當(dāng)前各原料的庫存量以及車輛的運(yùn)輸?shù)竭_(dá)時(shí)間和運(yùn)輸路徑等隨生產(chǎn)進(jìn)行而不斷發(fā)生改變的影響因素。

特征約束：（1）每批次的采購運(yùn)輸調(diào)度必須保證當(dāng)前采購的原料量可以滿足以下批次運(yùn)輸?shù)竭_(dá)時(shí)間內(nèi)的原料消耗量（公式（8））；（2）在運(yùn)輸調(diào)度模型中加入JIT的時(shí)間約束，保證所需原料在其需求時(shí)間以前如數(shù)運(yùn)到，且要盡量縮小運(yùn)輸?shù)牡竭_(dá)時(shí)間與每批次的原料需求時(shí)間，使各原料的當(dāng)前庫存接近為0（公式（9））；（3）為了使所需原料能夠均衡地投入到生產(chǎn)中，減少原料的庫存堆積，實(shí)現(xiàn)零庫存，令采購車輛在每批次的運(yùn)輸調(diào)度中盡可能的多遍歷幾種原料的供應(yīng)點(diǎn)，且每批次采購的原料量不超過車載量（詳見2.3節(jié)）。

JIT對(duì)模型目標(biāo)的影響：本文以最小化車輛數(shù)目與總運(yùn)輸路徑為目標(biāo)，針對(duì)JIT的約束和特征對(duì)目標(biāo)的影響進(jìn)行分析，當(dāng)每批次采購運(yùn)輸遍歷的原料種類增加時(shí)，易導(dǎo)致運(yùn)輸路徑增加、各批次原料交付量減少，易導(dǎo)致生產(chǎn)中斷。為了滿足JIT對(duì)運(yùn)輸調(diào)度的強(qiáng)約束，不少企業(yè)通過增加運(yùn)力資源，然而當(dāng)使用車輛數(shù)的變化時(shí)，當(dāng)前原料庫存、運(yùn)輸調(diào)度均受到影響，如圖2～圖5所示。

圖2 車輛-運(yùn)輸時(shí)間/距離關(guān)系圖

圖3 車輛-采購交付量關(guān)系圖

圖4 車輛-原料j變化圖（車輛數(shù)目較大）

圖5 車輛-原料j變化圖（車輛數(shù)目較?。?/p>

圖2 中隨著車輛數(shù)增加時(shí)，每輛車遍歷的原料供應(yīng)商種類減少，易導(dǎo)致單批次采購交付時(shí)間提前，單批次運(yùn)輸距離減少，因此，單批次采購交付時(shí)間/距離與車輛數(shù)目增加呈負(fù)相關(guān)。

圖3中隨著遍歷的原料供應(yīng)商種類減少，相應(yīng)每輛車采購的原料量占車載量的比例增加，因此，單批次采購交付量與車輛數(shù)目增加呈正相關(guān)。

圖4中當(dāng)車輛數(shù)目較大時(shí)，單批次原料交付量較大，當(dāng)前原料消耗完成時(shí)間遠(yuǎn)大于單批次采購交付時(shí)間，采購頻次減少，易造成生產(chǎn)庫存堆積。

圖5中當(dāng)車輛數(shù)目較小時(shí)，單批次采購交付時(shí)間較接近當(dāng)前原料消耗完成時(shí)間，單批次原料交付量較小，采購運(yùn)輸頻次增加，易導(dǎo)致生產(chǎn)中斷。

1.4 問題復(fù)雜性分析

本文在JIT采購模式下，為了保證生產(chǎn)的連續(xù)性，根據(jù)原料的消耗速率和生產(chǎn)現(xiàn)狀制定采購運(yùn)輸計(jì)劃。但是在考慮實(shí)際問題時(shí)，生產(chǎn)所需原料種類較多，往往需要遍歷多個(gè)供應(yīng)商，因此車輛的選擇、采購路徑優(yōu)化、各批次原料種類和運(yùn)輸量的確定對(duì)本文都至關(guān)重要，本節(jié)以最小化車輛數(shù)目與總運(yùn)輸路徑為目標(biāo)，進(jìn)行問題分析。JIT采購下的多目標(biāo)車輛調(diào)度問題的實(shí)質(zhì)不僅是采購運(yùn)輸中的路徑優(yōu)化問題，也是車輛在運(yùn)輸中的資源配置問題；相較于MVRP問題，不僅考慮了運(yùn)輸批量的變化對(duì)路徑優(yōu)化的影響，且在采購運(yùn)輸中需要滿足生產(chǎn)約束、數(shù)量約束、批量約束和運(yùn)輸約束，提高了約束條件的復(fù)雜性。如，批量約束，即體現(xiàn)在原料需求量與車載量（公式（3）、公式（4）），也體現(xiàn)在決策變量在采購運(yùn)輸環(huán)節(jié)的取值范圍。數(shù)量約束，即體現(xiàn)在運(yùn)輸量與需求量（公式（10））、運(yùn)輸量與車載量（公式（6）），也體現(xiàn)在交付時(shí)刻的庫存量（公式（9））。生產(chǎn)約束，體現(xiàn)在運(yùn)輸采購環(huán)節(jié)中要保證生產(chǎn)不中斷（公式（7）、（8））。運(yùn)輸約束，即體現(xiàn)在運(yùn)輸采購環(huán)節(jié)（公式（5）），也體現(xiàn)在車輛與采購量的對(duì)應(yīng)關(guān)系（公式（6））。

基于問題的NP性和人工蜂群算法的特征，提出一種改進(jìn)的人工蜂群算法進(jìn)行求解。在標(biāo)準(zhǔn)的人工蜂群算法中，待優(yōu)化問題解首先編碼成蜜源位置，之后通過引領(lǐng)蜂、跟隨蜂和偵察蜂三類蜜蜂合作進(jìn)行問題求解。相較于其他算法，三類不同個(gè)體間分工-協(xié)作的求解過程，為智能進(jìn)化算法對(duì)解空間探索開發(fā)能力的平衡提供了算法結(jié)構(gòu)基礎(chǔ)。算法需要設(shè)定參數(shù)包括種群規(guī)模、引領(lǐng)蜂局部尋優(yōu)次數(shù)和算法循環(huán)次數(shù)[25]。

具體思路如下：首先，采用二維權(quán)值矩陣的編碼方式實(shí)現(xiàn)車輛與原料之間的對(duì)應(yīng)關(guān)系。其次，為進(jìn)一步提高算法效率，在解碼過程中根據(jù)權(quán)值優(yōu)先級(jí)設(shè)計(jì)了啟發(fā)式信息指引算法搜索（詳見2.3小節(jié)）。最后，為平衡pareto解集的收斂性和多樣性，提高算法搜索精度，并克服算法中參數(shù)設(shè)置過多和搜索效果差的問題，提出一種基于自適應(yīng)網(wǎng)格的多目標(biāo)人工蜂群算法（GAMOABC）進(jìn)行求解（詳見2.4節(jié)）。問題與算法邏輯關(guān)系詳見圖6所示。

2 自適應(yīng)網(wǎng)格的多目標(biāo)人工蜂群算法及啟發(fā)式信息設(shè)計(jì)

2.1 算法改進(jìn)設(shè)計(jì)

為求解上述多目標(biāo)優(yōu)化問題，更好地平衡pareto解集的收斂性和多樣性，提出一種基于自適應(yīng)網(wǎng)格的多目標(biāo)人工蜂群算法（GAMOABC），針對(duì)標(biāo)準(zhǔn)人工蜂群的編碼、解碼、算法流程等做了如下改進(jìn)，算法核心內(nèi)容與多目標(biāo)優(yōu)化關(guān)系如圖7。

圖6 問題-算法邏輯圖

圖7 算法核心-多目標(biāo)優(yōu)化關(guān)系圖

改進(jìn)思路如下：首先，在目標(biāo)空間內(nèi)根據(jù)種群內(nèi)引領(lǐng)蜂個(gè)數(shù)劃分網(wǎng)格，使引領(lǐng)蜂覆蓋在整個(gè)目標(biāo)空間內(nèi)，保證pareto集的多樣性及解空間的有效性，跟隨峰在搜索時(shí)可以根據(jù)劃分的每個(gè)網(wǎng)格內(nèi)的引領(lǐng)蜂的當(dāng)前位置進(jìn)行鄰域搜索，使其對(duì)引領(lǐng)蜂的周圍既能兼顧更大范圍搜索提高搜索結(jié)果的多樣性，又能更精細(xì)化地進(jìn)行局部搜索，提高算法的收斂性。其次，跟隨蜂針對(duì)當(dāng)前引領(lǐng)蜂的坐標(biāo)信息進(jìn)行隨機(jī)動(dòng)態(tài)搜索和鄰域搜索，跟隨蜂種群不僅根據(jù)每個(gè)網(wǎng)格內(nèi)引領(lǐng)蜂的位置進(jìn)行局部尋優(yōu)，且引入轉(zhuǎn)換函數(shù)計(jì)算跟隨蜂動(dòng)態(tài)隨機(jī)位置，并進(jìn)行鄰域隨機(jī)搜索，既能兼顧局部搜索的精確性，也能夠增加搜索范圍。最后，為了對(duì)網(wǎng)格內(nèi)靠近PF的解進(jìn)一步有針對(duì)性、高精度的搜索，基于動(dòng)態(tài)位置計(jì)算的跟隨蜂適應(yīng)值與目標(biāo)空間各網(wǎng)格內(nèi)的引領(lǐng)蜂適應(yīng)值進(jìn)行pareto判斷，完成二者之間的位置信息共享，以此來跳出局部最優(yōu)，進(jìn)一步提高解集的多樣性。

2.2 編碼設(shè)計(jì)

在研究面向JIT采購的多目標(biāo)車輛調(diào)度問題時(shí)，為了滿足生產(chǎn)約束，便于安排車輛進(jìn)行原料采購運(yùn)輸，因此利用二維權(quán)值矩陣表示車輛與各需求原料的對(duì)應(yīng)關(guān)系，每個(gè)優(yōu)先權(quán)值表示每批次車輛與各原料的運(yùn)輸優(yōu)先級(jí)，當(dāng)某一批次要安排原料運(yùn)輸時(shí)，確定當(dāng)前最早消耗完成的原料種類，根據(jù)矩陣中對(duì)應(yīng)的優(yōu)先權(quán)值確定運(yùn)輸車輛，并在解碼過程中依次確定混載運(yùn)輸原料集合、采購運(yùn)輸路線和車輛的采購交付時(shí)間，判斷是否滿足約束條件；若不滿足，選擇矩陣中次優(yōu)先權(quán)值對(duì)應(yīng)的車輛安排運(yùn)輸，直到滿足約束條件，保證生產(chǎn)能夠穩(wěn)定連續(xù)的進(jìn)行。

如圖8表示車輛與各原料對(duì)應(yīng)的權(quán)值矩陣。圖8中p0(1,1)表示車輛1與原料供應(yīng)商1對(duì)應(yīng)的權(quán)值，以此類推，如：p0(v,z)表示車輛v對(duì)應(yīng)原料供應(yīng)商z的權(quán)值；其中，v表示車輛編號(hào)(v∈K)，z表示原料供應(yīng)商編號(hào)(z∈N)。

圖8 車輛與原料對(duì)應(yīng)權(quán)值矩陣

2.3 解碼過程

設(shè)定原料的需求量為r j，起始庫存為C j，解碼前所有車輛均可用且采購運(yùn)輸開始時(shí)間為0。在保證生產(chǎn)不中斷的條件下，解碼過程依據(jù)車輛與原料對(duì)應(yīng)的優(yōu)先權(quán)值大小，安排車載量為Q的車輛k進(jìn)行采購，依次得到車輛的到達(dá)時(shí)間原料的運(yùn)輸量，最終得到目標(biāo)函數(shù)f1、f2的運(yùn)輸方案。具體步驟如下：

步驟1確定可用車輛數(shù)目K。

步驟2更新車輛的使用狀態(tài)、原料的運(yùn)輸狀態(tài)。

步驟2.1若當(dāng)前時(shí)刻t為0，即t=t′=0，車輛均未被占用，所有原料均未安排運(yùn)輸，則轉(zhuǎn)入步驟3。若當(dāng)前時(shí)刻t不為0，且已安排車輛采購，各采購車輛的交付時(shí)刻等于當(dāng)前時(shí)刻t，則卸載采購的原料j，更新車輛的使用狀態(tài)，記錄此次原料j的運(yùn)輸量，并根據(jù)公式（11）計(jì)算當(dāng)前時(shí)刻相應(yīng)原料的庫存。若當(dāng)前時(shí)刻t不為0，且已安排車輛采購，各采購車輛的交付時(shí)刻等于當(dāng)前時(shí)刻t，則卸載采購的原料j，更新車輛的使用狀態(tài)，記錄此次原料j的運(yùn)輸量，并根據(jù)公式（11）計(jì)算當(dāng)前時(shí)刻相應(yīng)原料的庫存。

步驟2.2根據(jù)公式（12）和公式（13）判斷當(dāng)前原料是否被運(yùn)輸完成，若原料均被運(yùn)輸完成，則轉(zhuǎn)入步驟4。

步驟3確定調(diào)度集合，安排運(yùn)輸。

若原料未被采購?fù)瓿?，確定待運(yùn)輸原料集合J,J?N中，并安排運(yùn)輸，記錄車輛使用次數(shù)、此次運(yùn)輸?shù)拈_始時(shí)間、運(yùn)輸?shù)慕Y(jié)束時(shí)間的調(diào)度集合中原料的運(yùn)輸量。

步驟3.1根據(jù)公式（14）確定當(dāng)前待運(yùn)輸原料集合J中最早消耗完成的原料j，將原料j的最早消耗完成時(shí)間作為此次運(yùn)輸?shù)淖钔淼竭_(dá)時(shí)刻。將原料j供應(yīng)商作為此次采購運(yùn)輸?shù)氖讉€(gè)遍歷點(diǎn)，從當(dāng)前可用車輛集合中選擇對(duì)應(yīng)優(yōu)先級(jí)最高的車輛k*安排采購運(yùn)輸，若車輛集合中無可用車輛或集合為空，則解碼失??；若找到可用車輛k*，則利用公式（15）和公式（16）計(jì)算車輛k*開始時(shí)間和采購交付時(shí)間，并根據(jù)公式（17）判斷采購交付時(shí)間是否大于最早消耗完成時(shí)間，若是，則從當(dāng)前可用車輛集合中選擇對(duì)應(yīng)權(quán)值優(yōu)先級(jí)次之的車輛k*安排采購運(yùn)輸，并重復(fù)上述步驟，若找到車輛k*可滿足生產(chǎn)約束，則令值為1，并轉(zhuǎn)入步驟3.2；若遍歷完車輛集合后仍未找到可用車輛k*，則解碼失敗。

其中，t0j表示生產(chǎn)商到原料j的采購運(yùn)輸時(shí)間，令生產(chǎn)商的節(jié)點(diǎn)為0且t j0與t0j運(yùn)輸時(shí)間相等。

步驟3.2將當(dāng)前采購的原料j加入此次混載運(yùn)輸?shù)脑霞?中，并標(biāo)記為j*；利用公式（18）和公式（19）選擇當(dāng)前待運(yùn)輸原料集合中未被標(biāo)記過的原料集合中距離原料j*供應(yīng)商最近的原料i*安排采購，并利用公式（20）和公式（17）判斷車輛k增加采購原料i*后的交付時(shí)間是否大于；若是，則根據(jù)公式（22）計(jì)算此次采購運(yùn)輸?shù)慕桓稌r(shí)間并轉(zhuǎn)入步驟3.3；否則，令值為1公式（21），并重復(fù)以上步驟直到待運(yùn)輸原料均被遍歷（為空集），利用公式（22）計(jì)算此次采購運(yùn)輸?shù)慕桓稌r(shí)間并轉(zhuǎn)到步驟3.3。

步驟3.3確定當(dāng)前混載運(yùn)輸原料集合?，令的值為1，并利用公式（23）和公式（24）計(jì)算采購量。方法是：根據(jù)?中原料j與車輛k對(duì)應(yīng)的權(quán)值計(jì)算采購量，若超過原料j的待運(yùn)量，則等于原料j的待運(yùn)量；若不超過原料，則令采購量等于

步驟3.4令t′=t，利用公式（25）移動(dòng)當(dāng)前時(shí)刻t到當(dāng)前使用車輛最早采購交付時(shí)刻，并轉(zhuǎn)入步驟2。

步驟4若原料已完成運(yùn)輸，表示調(diào)度任務(wù)已經(jīng)完成，遍歷當(dāng)前可選用車輛K，根據(jù)公式（26）記錄運(yùn)輸車輛k的編號(hào)，并利用公式（1）和公式（2）計(jì)算f1、f2，輸出調(diào)度方案，解碼結(jié)束。

2.4 算法步驟

算法運(yùn)行前，需要設(shè)定的參數(shù)有：蜂群總數(shù)N、引領(lǐng)蜂規(guī)模Ne、跟隨蜂規(guī)模Nb，即：N=Nb+N e。

步驟1任選其中一個(gè)目標(biāo)函數(shù)f1，估算網(wǎng)格在任意一維上的最大值()、最小值()，并根據(jù)一維網(wǎng)格最大、最小值，確定網(wǎng)格的上下邊界值()。

步驟2根據(jù)解（引領(lǐng)蜂）的規(guī)模，在一維坐標(biāo)軸上劃分網(wǎng)格，并確定一維坐標(biāo)軸上各個(gè)網(wǎng)格的間距（具體詳見2.4.1小節(jié)）。

步驟3初始化種群N e后，隨機(jī)生成引領(lǐng)蜂e的位置(e∈N e)。根據(jù)一維網(wǎng)格r內(nèi)的上下界，由公式poe(i,j).f1=確定引領(lǐng)蜂在該網(wǎng)格r中的位置，并將第二維設(shè)為最大值，即poe(i,j).f2=max_number。其中，為一維網(wǎng)格i上最小邊界值；c1為各個(gè)網(wǎng)格的間距；Rnd∈(0,1)。

步驟4網(wǎng)格中的引領(lǐng)蜂位置通過跟隨蜂的鄰域搜索進(jìn)行更新，具體方法如下：

步驟4.1選定一個(gè)待開發(fā)網(wǎng)格；令r=1。

步驟4.2隨機(jī)生成種群規(guī)模為Nb的跟隨蜂，以選定的網(wǎng)格r(r=1,2,…,N)中引領(lǐng)蜂位置為中心對(duì)每只跟隨蜂q(q=1,2,…,Nb)計(jì)算跟隨蜂q的動(dòng)態(tài)隨機(jī)位置及其適應(yīng)值（具體詳見2.4.2小節(jié)）。并依據(jù)定位后的跟隨蜂適應(yīng)值確定在網(wǎng)格中的位置，更新相應(yīng)網(wǎng)格內(nèi)引領(lǐng)蜂位置信息（具體詳見2.4.3小節(jié)）。

步驟4.3若跟隨蜂種群對(duì)當(dāng)前網(wǎng)格r內(nèi)的引領(lǐng)蜂進(jìn)行了更新，則令跟隨蜂尋優(yōu)次數(shù)計(jì)數(shù)器t=1；否則進(jìn)化代數(shù)t=t+1，若t＞Nb，則退出對(duì)該網(wǎng)格r的鄰域搜索轉(zhuǎn)入步驟4.4，否則轉(zhuǎn)入步驟4.2繼續(xù)搜索。

步驟4.4選定下一個(gè)網(wǎng)格，令r=r+1，確定網(wǎng)格中的引領(lǐng)蜂，若r＞N，則退出本次對(duì)所有網(wǎng)格的鄰域搜索；否則，令t=1，轉(zhuǎn)入步驟4.2。

步驟5由種群搜索的Pareto解與已知網(wǎng)格邊界解進(jìn)行Pareto判斷，若搜索結(jié)果是已知邊界的支配解，則調(diào)整網(wǎng)格邊界（具體詳見2.4.4小節(jié)），并轉(zhuǎn)入步驟4；否則轉(zhuǎn)入步驟6。

步驟6通過Pareto判斷網(wǎng)格中的解是否為效解，并統(tǒng)計(jì)有效解個(gè)數(shù)，算法結(jié)束。

2.4.1 網(wǎng)格構(gòu)建

首先，任選兩個(gè)目標(biāo)中其中一個(gè)目標(biāo)f1，計(jì)算f i函數(shù)在單目標(biāo)情況下最大值、最小值，并以此為依據(jù)確定任意一維坐標(biāo)軸上的最大和最小值；其次，根據(jù)引領(lǐng)蜂規(guī)模Ne，在一維坐標(biāo)軸上盡量均等地劃分網(wǎng)格。根據(jù)一維坐標(biāo)上，確定每個(gè)網(wǎng)格邊界的距離長(zhǎng)度如公式（27）。一維網(wǎng)格坐標(biāo)下界由開始（即）依次加網(wǎng)格長(zhǎng)度c1，由公式（28）計(jì)算得出。

如圖9，f1、f2為兩個(gè)目標(biāo)函數(shù)，在只考慮單目標(biāo)f1的情況下，令f2取值為無限大，為60、為20；設(shè)種群中引領(lǐng)蜂個(gè)數(shù)為10，Max_N表示無限大，據(jù)公式（27）和公式（28）計(jì)算出一維坐標(biāo)c1的值為4。

圖9 網(wǎng)格構(gòu)建

2.4.2 跟隨峰位置更新

標(biāo)準(zhǔn)ABC算法使跟隨蜂的搜索位置會(huì)較均勻地分布于引領(lǐng)蜂周圍空間，但卻不能使跟隨蜂既密集搜索引領(lǐng)蜂的鄰域空間，又可以跳出該鄰域空間的束縛，且隨進(jìn)化代數(shù)增加實(shí)現(xiàn)對(duì)鄰域空間更高精度搜索[26]。本文在文獻(xiàn)[26]的位置信息共享機(jī)制的基礎(chǔ)上，以網(wǎng)格r內(nèi)引領(lǐng)蜂位置為中心，隨機(jī)生成跟隨蜂種群Nb，利用公式（29）對(duì)跟隨蜂進(jìn)行鄰域動(dòng)態(tài)隨機(jī)定位。

轉(zhuǎn)換函數(shù)公式（29）提高算法多樣性與收斂性主要體現(xiàn)在以下方面：首先，ln(rnd/(1-rnd))使（0，1）之間的隨機(jī)數(shù)較大概率地分布于0值周圍，同時(shí)又有小概率的較大值，使得跟隨蜂可以兼顧引領(lǐng)蜂附近及其周圍更遠(yuǎn)的鄰域，增加解集的多樣性。其次，函數(shù)0.5t作為ln(rnd/(1-rnd))的聚焦因子，隨進(jìn)化代數(shù)的增加，跟隨蜂可實(shí)現(xiàn)對(duì)引領(lǐng)蜂周圍更密集地搜索，逐步提高搜索精度。其中為引領(lǐng)蜂的坐標(biāo)信息rnd∈(0,1)；為新跟隨蜂的坐標(biāo)信息；t為跟隨蜂尋優(yōu)次數(shù)計(jì)數(shù)器。

2.4.3 引領(lǐng)蜂位置更新策略

圖10 引領(lǐng)蜂位置更新

2.4.4 網(wǎng)格邊界更新策略

跟隨蜂對(duì)當(dāng)前網(wǎng)格內(nèi)引領(lǐng)蜂進(jìn)行動(dòng)態(tài)搜索后，若搜索結(jié)果是相對(duì)于已知邊界（如f1上界）的支配解，或者鄰近最大邊界的網(wǎng)格中不存在Pareto最優(yōu)解，則由搜索后的Pareto解集中f1上界的最大值替換當(dāng)前網(wǎng)格中f1的上界值。在邊界更新后，為了保持網(wǎng)格個(gè)數(shù)不變，利用公式（27）更新一維各網(wǎng)格長(zhǎng)度c1，并由公式（28）計(jì)算坐標(biāo)下界。對(duì)原網(wǎng)格解在新劃分的網(wǎng)格中重新定位，新網(wǎng)格中確保每一個(gè)網(wǎng)格內(nèi)只有一個(gè)解。

表1 原料屬性表

對(duì)邊界調(diào)整后生成的空網(wǎng)格，參照公式poe(i,j).f1=隨機(jī)生成引領(lǐng)蜂位置，并再次從引領(lǐng)蜂起始網(wǎng)格開始搜索。邊界更新后的目標(biāo)空間中，網(wǎng)格個(gè)數(shù)沒有變化，只是增加了目標(biāo)空間內(nèi)可行解的多樣性，進(jìn)一步提高了算法搜索精度，此時(shí)目標(biāo)空間內(nèi)引領(lǐng)蜂位置隨機(jī)地生成可以使算法更加精確，且后續(xù)跟隨峰針對(duì)引領(lǐng)蜂的局部搜索既能提高解集的精確性，也能夠提高解集的多樣性。

3 實(shí)驗(yàn)分析

3.1 參數(shù)設(shè)定

3.1.1 測(cè)例參數(shù)設(shè)定

假設(shè)某公司最大可租賃車輛數(shù)為10，額定載重為7 t的車輛在平直道路上行駛，且無交通擁堵情況出現(xiàn)，車輛前往5個(gè)原料供應(yīng)商運(yùn)輸原料，車速恒定不變，10個(gè)測(cè)例中各原料需求量、消耗速率如表1，供應(yīng)商之間距離如表2所示。

表2 多種原料供應(yīng)商和配送點(diǎn)之間的運(yùn)輸距離km

3.1.2 算法參數(shù)設(shè)定

為提高搜索效率，在算法中加入啟發(fā)式信息，形成帶啟發(fā)式的基于自適應(yīng)網(wǎng)格的多目標(biāo)人工蜂群算法（GAMOABC）。因此，本文采用VB.NET，編譯環(huán)境為Microsoft Visual Studio 2010專業(yè)版，操作系統(tǒng)為Windows 7 Ultimate實(shí)現(xiàn)算法。以表1、表2中的數(shù)據(jù)為例，對(duì)GAMOABC的效果進(jìn)行測(cè)試。改進(jìn)的人工蜂群算法參數(shù)主要有：蜂群的規(guī)模N、引領(lǐng)蜂個(gè)數(shù)Ne、跟隨蜂個(gè)數(shù)Nb、具體參數(shù)設(shè)計(jì)見表3。

表3 算法參數(shù)設(shè)定

3.2 算法實(shí)驗(yàn)分析

為驗(yàn)證改進(jìn)算法的有效性，本文利用表1中的10個(gè)測(cè)例，將基于自適應(yīng)網(wǎng)格的人工蜂群算法（GAMOABC）和NSGA-II、MOEAS同時(shí)用來求解本文的問題模型。設(shè)定NSGA-II的交叉概率pc=0.8，變異概率p m=0.1，循環(huán)次數(shù)為50。每種算法在相同參數(shù)和測(cè)例下運(yùn)行10次，比較3種算法運(yùn)行的結(jié)果（見表4）。從表4中可以得到：GAMOABC算法、NSGA-II和MOEAS算法分別通過運(yùn)行10個(gè)測(cè)例，每個(gè)測(cè)例運(yùn)行20次后得到的Pareto解集；其中，第4、5、6、10個(gè)測(cè)例運(yùn)行后求解的Pareto解集的多樣性要明顯好于NSGA-II和MOEAS求解的解集；第8個(gè)測(cè)例運(yùn)行后求解的Pareto解集中大部分解可以支配NSGA-II和MOEAS的Pareto解集中的部分解；第1、2、7、9個(gè)測(cè)例運(yùn)行后求解的Pareto解集的多樣性雖然不明顯，但明顯可支配NSGA-II和MOEAS求解后得到解集。

表4 算法運(yùn)行結(jié)果對(duì)比

3.3 模型對(duì)比分析

為保證在采購運(yùn)輸中生產(chǎn)不中斷，本文提出一種多批次、小批量的JIT采購運(yùn)輸策略，為了進(jìn)一步說明采購運(yùn)輸策略的有效性，通過與文獻(xiàn)[5]中提到的兩種運(yùn)輸模式Model-I、Model-II進(jìn)行對(duì)比，設(shè)定相同車載量(Wt)和固定的需求量（1 596 t）在僅考慮運(yùn)輸成本的條件下與本文采用的運(yùn)輸策略進(jìn)行對(duì)比，各項(xiàng)計(jì)算結(jié)果如表5所示。得到運(yùn)輸頻次與運(yùn)輸成本，從運(yùn)行結(jié)果可以得出，當(dāng)運(yùn)輸頻次較小，每批次采購批量較大時(shí)，本文運(yùn)輸費(fèi)用比為Model-I的運(yùn)輸費(fèi)用增長(zhǎng)16.28%，當(dāng)運(yùn)輸頻次較大，每批次采購批量較小時(shí)，本文的運(yùn)輸費(fèi)用比Model-II減少15.46%；綜上，當(dāng)采用小批量、多批次采購運(yùn)輸時(shí)本文的JIT采購運(yùn)輸策略優(yōu)于文獻(xiàn)[5]Model-II運(yùn)輸策略。

表5 模型結(jié)果對(duì)比

3.4 算法性能分析

本文研究的JIT采購下的多目標(biāo)車輛調(diào)度問題，本質(zhì)上是多目標(biāo)優(yōu)化問題，因此為驗(yàn)證所提出的GAMOABC算法在求解多目標(biāo)優(yōu)化問題的有效性，以同樣的模型和參數(shù)（如表3）對(duì)ZDT測(cè)試套件的5個(gè)雙目標(biāo)MOP（ZDT1～ZDT4和ZDT6）用于實(shí)驗(yàn)研究。為驗(yàn)證本文提出算法所獲得非支配解的多樣性和精確性的效果，GAMOABC算法與對(duì)比算法在每個(gè)測(cè)試實(shí)例上執(zhí)行30次獨(dú)立運(yùn)行，并取均值和標(biāo)準(zhǔn)偏差作為評(píng)價(jià)標(biāo)準(zhǔn)并選擇IGD指標(biāo)[27]來量化算法性能。實(shí)驗(yàn)選擇MOEA/D[28]，MOEA/IGD-NS[29]及NSGA-II[30]作比較算法，實(shí)驗(yàn)結(jié)果見表6。從表6中可以看出，本文所提出的算法在ZDT1～ZDT4、ZDT6上的優(yōu)化效果均顯著優(yōu)于其所有比較算法（MOEA/D、MOEA/IGD-NS、G-NSGA-II、R-NSGA-II）。從標(biāo)準(zhǔn)偏差上看，所提出的算法在個(gè)體間的離散程度較小。通過上述分析，可以發(fā)現(xiàn)本文所提出的算法在IGD指標(biāo)方面能夠取得較好的效果，表明所提出的算法能夠獲得較好質(zhì)量和分布性的非支配解集。為直觀地展示所提出的算法獲得非支配解的質(zhì)量和分布情況，選取算法30次運(yùn)行的最好結(jié)果繪制非支配解集的分布，圖11給出了部分測(cè)試函數(shù)的非支配解集的分布圖。通過對(duì)以上指標(biāo)的數(shù)據(jù)分析及分布圖可以發(fā)現(xiàn)，所提出的算法能夠獲得具有較好質(zhì)量和分布性的非支配解。

4 結(jié)語

隨著市場(chǎng)經(jīng)濟(jì)的高速發(fā)展，現(xiàn)代管理技術(shù)和方法廣泛應(yīng)用于企業(yè)中，企業(yè)一方面需要準(zhǔn)時(shí)交付，保持生產(chǎn)的連續(xù)性，另一方面，在JIT采購的運(yùn)輸中，除了考慮提高交付效率，還需要降低運(yùn)輸成本。本文以連續(xù)生產(chǎn)型企業(yè)為背景，將生產(chǎn)中的JIT采購與車輛路徑問題相結(jié)合，提出了一種小批量、多周期、可拆分的采購運(yùn)輸策略，同時(shí)考慮了最小化車輛使用數(shù)與運(yùn)輸總路徑最小化的多目標(biāo)的車輛路徑優(yōu)化調(diào)度問題；研究結(jié)果表明，本文提出的JIT采購下的多目標(biāo)車輛路徑優(yōu)化模型與算法是有效的，可以適應(yīng)于在安排采購時(shí)既考慮了車輛的使用也需要考慮路徑均衡的企業(yè)。

表6 六種算法的IGD指標(biāo)的實(shí)驗(yàn)結(jié)果比較

圖11 非支配解集分布圖