王增臣，周 良

(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 210016)

0 引 言

物流配送中的車輛調(diào)度問(wèn)題(vehicle scheduling problem，VSP)是由Dantzig和Ramser[1]在1959年提出的，是物流配送中的一個(gè)重要步驟，一般可以描述為：對(duì)一系列裝貨點(diǎn)和(或)卸貨點(diǎn)，在一定條件(如指定交貨時(shí)間、車輛載重量、貨物的需求量等限制)的約束下，組織適當(dāng)?shù)能囕v路線，達(dá)到預(yù)定的目的，如行駛時(shí)間較少、車輛行駛路程較短、花費(fèi)成本較少等[2]。

近幾十年來(lái)，車輛調(diào)度問(wèn)題逐漸成為運(yùn)籌學(xué)和組合優(yōu)化領(lǐng)域的研究熱點(diǎn)，其研究重點(diǎn)也從單因素向多因素協(xié)同考慮，各國(guó)學(xué)者進(jìn)行了大量和深入的研究工作。馬祥麗等[3]針對(duì)車輛調(diào)度問(wèn)題，結(jié)合蝙蝠算法的原理，重新設(shè)計(jì)了BA的操作算子并采用罰函數(shù)方式對(duì)目標(biāo)函數(shù)進(jìn)行了簡(jiǎn)化，取得了較好的求解性能。吳聰?shù)萚4]將車輛與車輛路徑編碼成粒子，通過(guò)粒子之間的協(xié)作找到最優(yōu)物流配送車輛調(diào)度優(yōu)化方案，并對(duì)粒子群算法存在的不足進(jìn)行了相應(yīng)的改進(jìn)，提高了算法性能。Marinakis等[5]提出了一種蜜蜂交配優(yōu)化算法，并對(duì)局部尋優(yōu)方法進(jìn)行改進(jìn)，使算法解決組合優(yōu)化問(wèn)題效果更佳，對(duì)開放式車輛路徑問(wèn)題也取得了令人滿意的結(jié)果。Zhang等[6]考慮客戶滿意度，建立了多目標(biāo)車輛路徑問(wèn)題模型，提出了一種自適應(yīng)網(wǎng)格的多目標(biāo)量子進(jìn)化算法，利用一種改進(jìn)的模糊時(shí)間窗來(lái)反映客戶滿意程度。鄧麗君[7]通過(guò)對(duì)影響客戶滿意度的一些影響因素進(jìn)行分析，構(gòu)建了一種測(cè)度客戶滿意度的模糊隸屬度函數(shù)，利用線性加權(quán)將多目標(biāo)函數(shù)轉(zhuǎn)化成單目標(biāo)函數(shù)并設(shè)計(jì)一種改進(jìn)的遺傳算法對(duì)單目標(biāo)函數(shù)進(jìn)行優(yōu)化求解。以上文獻(xiàn)都對(duì)車輛調(diào)度問(wèn)題進(jìn)行研究并取得了一定成果，但在二維裝載約束方面研究甚少。劉海明等[8]通過(guò)改進(jìn)最低水平線方法與基于分階段遺傳算子的遺傳算法相結(jié)合,求解矩形件排樣問(wèn)題，有效改善了排樣效果,提高了材料利用率。Sarwono等[9]融合了物流配送中的兩個(gè)最重要問(wèn)題，提出了一種最鄰近法求解車輛路徑問(wèn)題，并提出了裝載啟發(fā)式算法解決貨物裝載問(wèn)題。王征等[10]針對(duì)二維裝載約束的車輛調(diào)度問(wèn)題建立了數(shù)學(xué)模型,提出了Memetic算法,對(duì)算法中的幾個(gè)關(guān)鍵算子:深度優(yōu)先的啟發(fā)式裝箱方法、染色體的編碼方式及其路徑分割程序等,進(jìn)行了詳細(xì)的闡述和改進(jìn)。

針對(duì)近年來(lái)實(shí)際應(yīng)用領(lǐng)域中出現(xiàn)的帶二維裝載約束的車輛調(diào)度新問(wèn)題，文中綜合考慮時(shí)間窗、二維裝載約束、載重量、成本和客戶滿意度，建立了帶時(shí)間窗和二維裝載約束的開放式車輛路徑問(wèn)題模型(open vehicle routing problem with time windows and two-dimensional loading constraints，2L-OVRPTW),提出了一種結(jié)合多目標(biāo)蟻群優(yōu)化算法和最低水平線搜索算法的車輛路徑優(yōu)化算法，并通過(guò)實(shí)驗(yàn)對(duì)模型的可解性及算法的有效性進(jìn)行驗(yàn)證。

1 車輛調(diào)度問(wèn)題建模

1.1 問(wèn)題描述

2L-OVRPTW問(wèn)題是融合二維裝箱問(wèn)題(two-dimensional bin packing problem，2BPP)和帶時(shí)間窗約束的開放式車輛路徑問(wèn)題(open vehicle routing problem with time windows，OVRPTW)之后的一個(gè)變種問(wèn)題[11]。2BPP問(wèn)題同樣屬于NP難題，貨物能否裝載、貨物如何擺放等因素都對(duì)配送車輛的調(diào)度以及服務(wù)線路的安排產(chǎn)生很大的影響，因此這兩個(gè)問(wèn)題的融合產(chǎn)生了新的問(wèn)題，有別于一般的車輛路徑問(wèn)題，使得新問(wèn)題的模型會(huì)發(fā)生很大的變化，而對(duì)新問(wèn)題進(jìn)行求解也有較大的挑戰(zhàn)[12]。

2L-OVRPTW問(wèn)題可描述為：一組相同的車輛由配送中心出發(fā)，負(fù)責(zé)給N個(gè)客戶進(jìn)行貨物配送。每輛車均有一個(gè)長(zhǎng)為L(zhǎng)寬為W的長(zhǎng)方形裝載空間，且所載貨物的總重量不能超過(guò)車輛最大載重量Q。每個(gè)客戶都有隨機(jī)數(shù)量和重量的貨物需求，每件貨物有特定的長(zhǎng)度和寬度[13]。貨物裝載時(shí)，遵守有向有序條件，即同一客戶的所有貨物必須裝載在一輛車上，貨物不可旋轉(zhuǎn)，不能相互疊放，并且不同客戶的貨物之間不能產(chǎn)生阻擋。另外，每個(gè)客戶都有一個(gè)服務(wù)時(shí)間長(zhǎng)度和理想的服務(wù)軟時(shí)間窗[14]。配送中心派送各個(gè)車輛并安排行車路線，使得每個(gè)客戶都能被服務(wù)到，每輛車完成任務(wù)后不需要返回原配送中心。在這些約束下尋求最佳的車輛調(diào)度配送方案[15]。

1.2 2L-OVRPTW模型定義

根據(jù)車輛路徑問(wèn)題描述，在建模階段建立了2L-OVRPTW模型框架，如圖1所示。

圖1 2L-OVRPTW模型框架

2L-OVRPTW模型主要由四個(gè)方面組成：基礎(chǔ)信息包括客戶及配送中心的位置坐標(biāo)、車輛基礎(chǔ)參數(shù)和貨物基礎(chǔ)參數(shù)；客戶需求是客戶的預(yù)定訂單和臨時(shí)訂單信息；約束條件有軟時(shí)間窗區(qū)間、車輛載重量約束和二維裝載約束；調(diào)度優(yōu)化主要是要達(dá)到運(yùn)輸成本最小和客戶滿意度最大的目標(biāo)。

因此得到模型問(wèn)題編碼：(1)位置：配送中心和客戶由N+1個(gè)坐標(biāo)節(jié)點(diǎn)表示，0代表配送中心的標(biāo)號(hào)，其他數(shù)字表示要被服務(wù)的客戶標(biāo)號(hào)。標(biāo)號(hào)i到標(biāo)號(hào)j的距離為dij，單位距離的成本為cij。(2)配送中心：有K輛相同的車輛提供運(yùn)輸配送服務(wù)，每輛車的額定載重量為Qk(k=1,2,…,K)，承載貨物的車廂為一個(gè)面積A=W×L的矩形，每輛車的固定發(fā)車成本為FK。(3)客戶：i=1,2,…,N，客戶i所需求的貨物為一個(gè)集合ITi，包含mi個(gè)矩形物品，ITi中所有物品的總面積為ai，總重量為qi，第m個(gè)物品Iim有一個(gè)具體的寬度wim和長(zhǎng)度lim(m=1,2,…,mi)。設(shè)置車廂承載面俯視圖的左下角為原點(diǎn)，水平向右為橫坐標(biāo)，垂直向上為縱坐標(biāo)，則有物品Iim的坐標(biāo)(vim,him)，vim,him分別代表到坐標(biāo)原點(diǎn)的水平距離和垂直距離。車輛到達(dá)客戶進(jìn)行服務(wù)的時(shí)間為ti，令每個(gè)客戶的服務(wù)軟時(shí)間窗為[Ei,Li]，客戶滿意度ui(ti)表示為：

客戶i固有的服務(wù)時(shí)間表示為si，當(dāng)車輛提前到達(dá)客戶i處時(shí)，則需等待，產(chǎn)生等待時(shí)間wi(ti)。等待的單位時(shí)間成本為cwait，客戶i的等待成本則表示為wi(ti)×cwait。定義決策變量如下：

2L-OVRPTW模型可表示如下：

目標(biāo)函數(shù)為：

(1)

(2)

約束條件為：

(3)

(4)

(5)

(6)

(7)

xijk=0或1，?i,j,k

(8)

yik=0或1，?i,k

(9)

0≤vimk≤W-wimk,?i∈{1,2,…,N},m∈

{1,2,…,mi},k∈K

(10)

0≤himk≤L-limk,?i∈{1,2,…,N},m∈{1,

2,…,mi},k∈K

(11)

vimk+wimk≤vi'm'k,?i,i'∈{1,2,…,N},m∈{1,

2,…,mi},m'∈{1,2,…,N},k∈K,i≠i'

(12)

himk+limk≤hi′m′k,?i,i'∈{1,2,…,N},m∈{1,

2,…,mi},m'∈{1,2,…,N},k∈K,i≠i'

(13)

vimk≥vi′m′k,?i,i'∈{1,2,…,N},m∈{1,2,…,mi},m'∈{1,2,…,N},k∈K,i≠i'

(14)

himk+limk≥hi'm'k,?i,i'∈{1,2,…,N},m∈{1,

2,…,mi},m'∈{1,2,…,N},k∈K,i≠i'

(15)

hi'm'k+li'm'k≥himk,?i,i'∈{1,2,…,N},m∈{1,2,…,mi},m'∈{1,2,…,N},k∈K,i≠i'

(16)

(17)

wi(ti)=max{0,Ei-ti}

(18)

其中，式1～3為目標(biāo)函數(shù)，式1表示運(yùn)輸成本最小化，式2表示平均客戶滿意度最大化。約束3限制每輛車的最大載重量；約束4保證每個(gè)客戶都能被服務(wù)到；約束5和6保證一個(gè)客戶有且僅有一輛車進(jìn)行服務(wù)；約束7是消除子回路；約束8、約束9表示變量的取值范圍；約束10、約束11保證在每條路徑上貨物以固定方向都能放置于車上；約束12、約束13表示貨物相互之間不可以疊放；約束14～約束16保證貨物能在裝入方向直線移進(jìn)移出并不受其他貨物阻擋；約束17計(jì)算車輛的到達(dá)時(shí)間；約束18計(jì)算車輛的等待時(shí)間。

2 車輛調(diào)度問(wèn)題優(yōu)化

2L-OVRPTW是屬于NP-hard難題，啟發(fā)式算法成為解決該問(wèn)題的首選[16]。針對(duì)上述問(wèn)題模型，文中設(shè)計(jì)了一種啟發(fā)式算法。該算法是以改進(jìn)的蟻群算法為算法大體框架，并融入了基于BLF的裝載策略以確保滿足二維裝載約束。針對(duì)2L-OVRPTW模型設(shè)計(jì)的調(diào)度優(yōu)化總體流程如圖2所示。

圖2 調(diào)度優(yōu)化總體流程

2.1 二維裝載策略

在裝載階段，結(jié)合啟發(fā)式經(jīng)驗(yàn)知識(shí)，設(shè)計(jì)了基于最低水平線搜索算法的二維裝載策略，將各個(gè)客戶的矩形貨物有序裝入矩形車廂，提高車輛裝載率。

2.1.1 啟發(fā)式經(jīng)驗(yàn)知識(shí)

一般情況下,對(duì)于二維裝載問(wèn)題很難直接構(gòu)造出一個(gè)最優(yōu)解或者滿意解,尤其當(dāng)貨物數(shù)量比較多時(shí),盲目搜索或者遍歷就變得更加困難,甚至根本不可行。因此,利用一些人工經(jīng)驗(yàn)和結(jié)構(gòu)特征來(lái)構(gòu)造出一些啟發(fā)式規(guī)則,并按照該規(guī)則指導(dǎo)采用的啟發(fā)式算法,由該算法可以求得問(wèn)題的滿意解。

對(duì)于二維裝載約束,有以下幾個(gè)經(jīng)驗(yàn)和特征可以參考利用:

(1)物品裝入車廂可行區(qū)域的邊角處，產(chǎn)生的零碎區(qū)域更少，車廂的裝載率更高；

(2)先裝大塊物品，后裝小塊物品。面積較大的矩形物品裝入后產(chǎn)生的區(qū)域可以裝入面積較小的矩形貨品，由人工裝箱經(jīng)驗(yàn)可知，通常先裝大塊的物品，后裝小塊的物品；

(3)裝載過(guò)程中產(chǎn)生的剩余區(qū)域整體水平線越平整,即組成水平線的數(shù)量越少,高度越一致，就越有利于后期矩形的裝入。

基于上述三種啟發(fā)式經(jīng)驗(yàn)知識(shí)，對(duì)現(xiàn)有的最低水平線搜索算法進(jìn)行指導(dǎo)改進(jìn)，一個(gè)客戶的全部物品能且只能由一輛車進(jìn)行運(yùn)輸服務(wù)，在裝載之前對(duì)該客戶貨物總面積和車廂剩余面積進(jìn)行比較；對(duì)一個(gè)客戶的物品按照寬度和面積進(jìn)行倒序排序，減少不可行區(qū)域的產(chǎn)生，同時(shí)提高向后搜索匹配的效率；物品放置于可裝入的最低水平線的左下方。

2.1.2 裝載策略主要步驟

步驟1：將待裝載的指定客戶i的物品總面積ai與當(dāng)前車廂剩余面積A剩進(jìn)行比較：如果ai>A剩，則不可裝入，結(jié)束；否則對(duì)該客戶的物品按照寬度和面積進(jìn)行倒序排序，然后執(zhí)行步驟2。

步驟2：每當(dāng)裝入客戶i的下一待裝物品Iim時(shí)，比較水平線集中各個(gè)水平線高度，選擇高度最低的一段水平線，若存在多段水平線段高度相同并且同為最低，則選取位置處于最左邊的一段水平線，作為最低水平線Wlow。

步驟3：比較最低水平線段和待裝物品Iim的寬度wim：

(1)如果Wlow≥wim，則將Iim放置于最低水平線的左下方，并更新水平線集的條數(shù)和高度。

(2)如果Wlow

步驟4：重復(fù)步驟3，直至能裝入客戶i物品Iim，并更新此時(shí)的水平線集。

步驟5：重復(fù)步驟4，直至客戶i的物品全部裝入，得到最終的水平線集。

步驟6：選取水平線集中的高度最大值Hmax，與車廂長(zhǎng)度L進(jìn)行比較：如果Hmax>L，客戶i的貨品不可裝入，水平線集更新到客戶i的貨品未裝入前狀態(tài)，結(jié)束；如果Hmax

2.2 車輛調(diào)度優(yōu)化

蟻群算法(ant colony optimization，ACO)是一種新興的優(yōu)化技術(shù)，是一種模擬進(jìn)化算法。ACO是一種啟發(fā)式仿生進(jìn)化系統(tǒng)，通過(guò)模擬螞蟻群體在自然生活中的覓食行為而得出，其搜索過(guò)程是分布式并行計(jì)算方式，能夠提高算法的計(jì)算能力和運(yùn)行效率，并采用啟發(fā)式正反饋機(jī)制，能夠使算法獲得全局最優(yōu)解。

2.2.1 算法的具體改進(jìn)

由于2L-OVRPTW模型同時(shí)優(yōu)化兩個(gè)目標(biāo)，文中設(shè)計(jì)出多目標(biāo)蟻群優(yōu)化算法，在改進(jìn)的蟻群優(yōu)化算法基礎(chǔ)上，采用Pareto最優(yōu)解來(lái)進(jìn)行多目標(biāo)優(yōu)化[17]。在2L-OVRPTW模型中選擇下一客戶時(shí),在滿足車輛容量和時(shí)間窗約束的前提下,還需要考慮時(shí)間先后的擇優(yōu)性,其啟發(fā)式因子由路徑距離和客戶的時(shí)間窗寬度等因素綜合決定，因此對(duì)狀態(tài)轉(zhuǎn)移的概率計(jì)算和信息素的更新等進(jìn)行改進(jìn)。

改進(jìn)的多目標(biāo)蟻群算法既可以在迭代運(yùn)行過(guò)程中保持螞蟻種群的多樣性，也能夠保持Pareto解集的多樣性。

(19)

其中，τij(t)為t時(shí)刻客戶i或者倉(cāng)庫(kù)到客戶j路徑上的信息素濃度；ηij(t)=1/dij為距離啟發(fā)式函數(shù)；θij(t)=1/twidthj為時(shí)間啟發(fā)式函數(shù)。

啟發(fā)式函數(shù)表示t時(shí)刻客戶i或者倉(cāng)庫(kù)到客戶j的轉(zhuǎn)移期望程度；allowk為螞蟻k待訪問(wèn)的客戶集合。

在螞蟻狀態(tài)轉(zhuǎn)移過(guò)程中引入偽隨機(jī)概率規(guī)則，以克服螞蟻狀態(tài)轉(zhuǎn)移速度慢的不足，規(guī)則如下：

j=

其中，r為在[0,1]上服從均勻分布的隨機(jī)變量；參數(shù)r0為用來(lái)控制轉(zhuǎn)移規(guī)則的概率。若r≤r0，則從待服務(wù)的客戶中找出概率最大的客戶為下一服務(wù)客戶；否則就根據(jù)式19并運(yùn)用輪盤賭法按概率選擇出下一個(gè)服務(wù)客戶。

為了避免路徑上的信息素濃度差異過(guò)大，引入信息素最低閾值τmin,避免算法過(guò)早陷入局部最優(yōu)。當(dāng)螞蟻完成一次循環(huán)后，路徑上的信息素會(huì)揮發(fā)，螞蟻也會(huì)留下信息素，需要對(duì)各個(gè)路徑上的信息素進(jìn)行更新，規(guī)則如下：

τij(t+1)=max(ρ·τij(t)+Δτij,τmin)

(21)

(22)

(23)

2.2.2 算法主要步驟

步驟1：編碼采用整數(shù)編碼方式并初始化參數(shù)。

步驟2：配送中心為螞蟻的當(dāng)前起點(diǎn)，將所有客戶納入待服務(wù)集合表allow中，清空禁忌表Tabu。

步驟3：螞蟻在當(dāng)前位置根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則(式20)從集合表allow中選擇下一服務(wù)客戶j，并用二維裝載策略對(duì)客戶j的貨品進(jìn)行裝載。

(1)如無(wú)法裝入或超重，則放棄服務(wù)客戶j，將螞蟻位置更新到配送中心，并分配新車輛，轉(zhuǎn)步驟3。

(2)如果裝入成功并且不超重，則更新螞蟻位置到客戶j，將客戶j從集合表allow轉(zhuǎn)移到禁忌表Tabu中，并重復(fù)步驟3直至所有客戶全部被服務(wù)到。

步驟4：計(jì)算種群中每只螞蟻所走路徑的總長(zhǎng)度、路線和目標(biāo)值等信息，并根據(jù)各個(gè)螞蟻之間的支配關(guān)系構(gòu)建和更新非劣解集Nset。

步驟5：根據(jù)式21～23更新螞蟻種群的信息素濃度表τ。

步驟6：若迭代次數(shù)NC未達(dá)到最大迭代次數(shù)NCmax,則迭代次數(shù)NC=NC+1,并轉(zhuǎn)到步驟2；否則，輸出非劣解集Nset，結(jié)束。

3 實(shí)驗(yàn)結(jié)果及分析

文中所有程序采用MATLAB編寫，在Inter 酷睿 I7-7500U CPU 3.5 GHz、內(nèi)存4.0 GB的計(jì)算機(jī)上運(yùn)行。目前2L-OVRPTW問(wèn)題尚且沒(méi)有標(biāo)準(zhǔn)的測(cè)試數(shù)據(jù)庫(kù)，因此通過(guò)對(duì)已有的測(cè)試實(shí)例庫(kù)進(jìn)行改造并設(shè)計(jì)了一個(gè)實(shí)例來(lái)進(jìn)行算法分析。

為了比較提出的調(diào)度優(yōu)化方法的性能，分別采用遺傳算法(A)、混合粒子群算法(B)與提出的調(diào)度優(yōu)化方法(C)，對(duì)標(biāo)準(zhǔn)Solomon實(shí)例庫(kù)的三個(gè)不同類別實(shí)例C101、R101和RC101進(jìn)行改造，多次運(yùn)行并取平均結(jié)果，得到的運(yùn)行情況如表1所示。通過(guò)比較可以看出，用車數(shù)量和算法運(yùn)行時(shí)間基本一樣，而行駛距離有大幅減少，客戶滿意度也略有提高?？傮w而言，文中算法明顯優(yōu)于其他兩種算法。

表1 算法比較

將文中算法用于求解某國(guó)際物流公司的車輛調(diào)度問(wèn)題的一個(gè)實(shí)例。在該實(shí)例中，物流公司有1個(gè)配送中心，為33個(gè)客戶進(jìn)行貨物配送，每個(gè)客戶位于不同的坐標(biāo)上，并有不同種類貨物的需求。

在求解過(guò)程中，種群大小為50，迭代次數(shù)為200，得到Pareto最優(yōu)解集為(2 413.9，0.57)，(2 429.1，0.60)，(2 478.3，0.64)，(2 544.0，0.72)，(2 682.1，0.76)，(2 835.9，0.79)，如圖3所示。分別選取2個(gè)目標(biāo)向量的調(diào)度線路，如表2所示。

表2 優(yōu)化調(diào)度線路

4 結(jié)束語(yǔ)

一般的車輛調(diào)度方法都是滿足在客戶的需求下，僅從經(jīng)濟(jì)因素的角度出發(fā)，追求最短的行駛距離或者最低的成本。而在當(dāng)前激烈的市場(chǎng)競(jìng)爭(zhēng)環(huán)境下，現(xiàn)代物流企業(yè)需要綜合考慮時(shí)間窗、二維裝載約束和客戶滿意度等情況，提高企業(yè)競(jìng)爭(zhēng)力。結(jié)合實(shí)際情況，文中描述了2L-OVRPTW問(wèn)題并建立相應(yīng)模型，以多目標(biāo)蟻群優(yōu)化算法為大體框架，并融合改進(jìn)的最低水平線搜索算法，對(duì)模型進(jìn)行求解，同時(shí)優(yōu)化貨物裝載和配送路線。實(shí)驗(yàn)結(jié)果表明，該方法可以在較短的時(shí)間內(nèi)獲得模型問(wèn)題的滿意解，滿足車輛調(diào)度的實(shí)時(shí)性需求，并具有較高客戶滿意度和較短的行駛路程。文中設(shè)計(jì)的模型和車輛調(diào)度方法對(duì)于現(xiàn)代物流企業(yè)科學(xué)并合理地開展物流調(diào)度工作有一定的理論指導(dǎo)和借鑒意義。