時(shí)變網(wǎng)絡(luò)下多車型同時(shí)取送貨車輛路徑優(yōu)化

趙佳欣，雷 斌，3，王菀瑩

(1.蘭州交通大學(xué) 機(jī)電技術(shù)研究所，甘肅 蘭州 730070；2.甘肅省物流及運(yùn)輸裝備信息化工程技術(shù)研究中心，甘肅 蘭州 730070；3.甘肅省物流與運(yùn)輸裝備行業(yè)技術(shù)中心，甘肅 蘭州 730070)

0 引 言

隨著互聯(lián)網(wǎng)及電子商務(wù)的普及，顧客的物流需求越來(lái)越多樣化，從原來(lái)的單一送貨或取貨需求演變?yōu)榧鎮(zhèn)涠叩奈锪餍枨?。車輛在進(jìn)行配送任務(wù)時(shí)，車輛行駛速度常常會(huì)因?yàn)榈缆方煌ㄇ闆r改變[1]。在規(guī)劃車輛配送路線時(shí)，不僅需要考慮客戶需求還需要結(jié)合道路交通狀況。針對(duì)時(shí)變車輛路徑問(wèn)題，劉思遠(yuǎn)等[2]、張景玲等[3]采用分段函數(shù)表現(xiàn)車速隨時(shí)段變化，劉文琪[4]分段函數(shù)的基礎(chǔ)上考慮車輛行駛加速度，范厚明等[5，6]混合時(shí)間窗用多個(gè)三角函數(shù)關(guān)系式及多項(xiàng)式表現(xiàn)車速隨時(shí)間連續(xù)變化關(guān)系。目前的研究主要考慮時(shí)間對(duì)車輛行駛速度的影響，未考慮路段的影響。針對(duì)同時(shí)取送貨車輛路徑問(wèn)題，現(xiàn)有研究主要將其與選址問(wèn)題和不確定環(huán)境相結(jié)合。陳希瓊等[7，8]結(jié)合選址和路徑問(wèn)題，同時(shí)考慮車輛容量和行駛里程約束，通過(guò)縮短最優(yōu)目標(biāo)值和行駛距離的差值進(jìn)行尋優(yōu)。馬艷芳等[9，10]對(duì)模糊需求和不確定環(huán)境下的同時(shí)取送貨問(wèn)題進(jìn)行研究。李博威等[11]引入非線性約束對(duì)時(shí)變網(wǎng)絡(luò)下的同時(shí)取送貨問(wèn)題進(jìn)行研究。大部分的研究成果都默認(rèn)路網(wǎng)內(nèi)的客戶關(guān)系單一，沒(méi)有對(duì)多樣的取送貨情況進(jìn)行刻畫(huà)。本文綜合考慮路段和時(shí)段對(duì)車速的影響、不同客戶的取送貨需求及客戶關(guān)系、多種車輛的載重約束，建立時(shí)變路網(wǎng)下多車型同時(shí)取送貨車輛路徑模型(simultaneous pickup and delivery vehicle routing problem under time-varying road network，SPDVRPTN)。

1 模型建立

1.1 問(wèn)題描述

假定道路網(wǎng)絡(luò)內(nèi)存在一個(gè)配送中心，客戶位置已給定，每個(gè)客戶都有取送貨需求，取送貨量已知，當(dāng)取貨量為0時(shí)代表該客戶點(diǎn)只有送貨需求，反之亦然。配送中心共有K輛車可調(diào)配，共L種類型，以l(l∈L) 表示車輛類型，每種類型車輛載重為Q1，Q2，…，QL， 即Ql(l∈L)， 車輛數(shù)量為K1，K2，…，KL， 即Kl(l∈L)， 每個(gè)客戶僅由一輛車進(jìn)行服務(wù)一次。車輛從配送中心出發(fā)，在行駛過(guò)程中其行駛速度隨路段和時(shí)段的改變而改變，且不允許超載，在完成配送后返回配送中心。道路網(wǎng)絡(luò)內(nèi)包含路段a個(gè)，將配送中心的服務(wù)時(shí)段劃分為b個(gè)。要求合理規(guī)劃車輛行駛路線，使配送總成本達(dá)到最小值。總成本包括車輛固定成本、車輛派遣成本以及未滿足客戶時(shí)效要求產(chǎn)生的時(shí)間懲罰費(fèi)用。

1.2 參數(shù)及變量說(shuō)明

dij客戶點(diǎn)i到客戶點(diǎn)j的運(yùn)輸距離

pj客戶點(diǎn)j的取貨量

dj客戶點(diǎn)j的送貨量

A共有a個(gè)路段

B將配送中心服務(wù)時(shí)段劃分為b個(gè)

Sb第b個(gè)時(shí)間段的開(kāi)始時(shí)間

Eb第b個(gè)時(shí)間段的結(jié)束時(shí)間

yij車輛k從客戶點(diǎn)i到客戶點(diǎn)j路徑中的送貨量

zij車輛k從客戶點(diǎn)i到客戶點(diǎn)j路徑中的取貨量

QL類型為L(zhǎng)的車輛最大載重

tij車輛從客戶i到客戶點(diǎn)j的行駛時(shí)間

ej客戶點(diǎn)j的期望最早服務(wù)時(shí)間

lj客戶點(diǎn)j的期望最晚服務(wù)時(shí)間

e0送中心的最早服務(wù)時(shí)間

l0配送中心的最晚服務(wù)時(shí)間

tj車輛在客戶點(diǎn)j的取送貨時(shí)間

wj車輛到達(dá)客戶點(diǎn)j的時(shí)間

wj0車輛從客戶點(diǎn)j返回配送中心的時(shí)間

Pi(ti) 時(shí)間窗懲罰函數(shù)

1.3 考慮多種取送貨情況

針對(duì)同時(shí)取送貨問(wèn)題，從路網(wǎng)內(nèi)的客戶間關(guān)系出發(fā)，考慮以下兩種情況：

(1)路網(wǎng)內(nèi)客戶間不存在服務(wù)與被服務(wù)關(guān)系：所有客戶的送貨量等于從配送中心出發(fā)的車輛的總載貨量，返回配送中心的車輛載貨總量為所有客戶的總?cè)∝浟?，此時(shí)車輛無(wú)固定服務(wù)順序。

(2)路網(wǎng)內(nèi)存在客戶間服務(wù)與被服務(wù)關(guān)系：在特定客戶取到的貨物能夠?yàn)槁肪W(wǎng)內(nèi)其他客戶進(jìn)行送貨服務(wù)。假設(shè)存在客戶集m=(1，2，3，…，m) 為客戶集n=(1，2，…，n) 服務(wù)，客戶集m的供給能力能夠滿足客戶集n的需求。車輛在配送時(shí)需先對(duì)客戶集m中的客戶進(jìn)行服務(wù)，再對(duì)客戶集n中的客戶進(jìn)行服務(wù)。

綜合考慮以上兩種情況，將路網(wǎng)內(nèi)的客戶編號(hào)為 (1，2，3，…，m，m+1，…，m+n)， 對(duì)網(wǎng)絡(luò)內(nèi)流量設(shè)定以下約束條件

(1)

(2)

(3)

(4)

(5)

(6)

式(1)和式(2)表示從配送中心出發(fā)的載貨量大于等于前m個(gè)客戶點(diǎn)的總送貨量并且小于等于總送貨量；式(3)表示總?cè)∝浟啃∮诘扔诜祷嘏渌椭行牡目傒d貨量；式(4)表示前m個(gè)客戶點(diǎn)的取貨量大于等于后n個(gè)客戶點(diǎn)的送貨量；式(5)和式(6)保證客戶服務(wù)順序符合規(guī)定。

1.4 時(shí)變網(wǎng)絡(luò)下行駛時(shí)間計(jì)算

本文采用多個(gè)分段函數(shù)表現(xiàn)不同道路下的速度隨時(shí)間變化的曲線，定義出不同路段不同時(shí)段的車輛行駛速度集F，如式(7)所示，每個(gè)路段下車輛行駛速度隨時(shí)段變化

(7)

假設(shè)車輛從客戶點(diǎn)i行駛到客戶點(diǎn)j時(shí)處于路段a中，此時(shí)存在跨時(shí)段行駛和不跨時(shí)段行駛兩種情況，非跨時(shí)段行駛時(shí)，行駛時(shí)間計(jì)算公式如式(8)所示

(8)

跨時(shí)段行駛時(shí)，按式(9)計(jì)算到達(dá)下一節(jié)點(diǎn)的時(shí)間

(9)

若tj仍處于時(shí)段[tb-1，tb]， 則根據(jù)式(10)計(jì)算車輛在下個(gè)時(shí)段仍需行駛的距離。再根據(jù)行駛距離更新行駛時(shí)間，計(jì)算公式如式(11)所示，當(dāng)tj≤tb+1時(shí)停止計(jì)算，否則繼續(xù)上述步驟

(10)

(11)

1.5 模型建立

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

ai+ti+tij-M(1-xijk)≤aj

(20)

(21)

tjo≤l0

(22)

式(12)為目標(biāo)函數(shù)，以車輛租賃成本、派遣成本和時(shí)間懲罰費(fèi)用最小為總目標(biāo)；式(13)保證車輛從配送中心出發(fā)去往一條路徑；式(14)表示最多使用k輛車；式(15)為車輛最大容量限制；式(16)和式(17)為取送貨量定義式；式(18)保證車輛在客戶點(diǎn)a完成服務(wù)后必須前往下一客戶點(diǎn)；式(19)表示懲罰費(fèi)用函數(shù)；式(20)表示車輛k由客戶點(diǎn)i行駛到下一個(gè)客戶點(diǎn)時(shí)的到達(dá)時(shí)間關(guān)系；式(21)為流量平衡約束；式(22)保證車輛需在配送中心開(kāi)放的時(shí)段進(jìn)行服務(wù)。

2 改進(jìn)的自適應(yīng)遺傳算法設(shè)計(jì)

遺傳算法(genetic algorithm，GA)作為求解VRP問(wèn)題的常用算法已被多次驗(yàn)證其有效性，具有較強(qiáng)的全局搜索能力，但達(dá)到一定迭代次數(shù)后求解效率低下且易出現(xiàn)早熟。本文涉及問(wèn)題考慮了包括了時(shí)變網(wǎng)絡(luò)、多車型、同時(shí)取送貨等約束，問(wèn)題復(fù)雜，需要在標(biāo)準(zhǔn)遺傳算法的基礎(chǔ)上進(jìn)行改進(jìn)，提高求解效率和精確性。根據(jù)本文所建SPDVRPTN模型特點(diǎn)，主要從以下兩個(gè)方面進(jìn)行改進(jìn)：①自適應(yīng)遺傳算法(adaptive genetic algorithm)與普通遺傳算法相比能夠通過(guò)調(diào)整交叉變異概率使在求解次數(shù)到達(dá)一定規(guī)模時(shí)引導(dǎo)算法往更優(yōu)的方向進(jìn)化[12]，交叉變異概率在算法迭代時(shí)根據(jù)迭代情況發(fā)生自適應(yīng)改變。②針對(duì)遺傳算法容易出現(xiàn)早熟的問(wèn)題，對(duì)算法中的選擇、變異算子進(jìn)行改進(jìn)，引導(dǎo)其搜索方向，提高算法搜索能力。改進(jìn)的自適應(yīng)遺傳算法通過(guò)其自適應(yīng)機(jī)制和改進(jìn)后的選擇、變異算子提高求解效率和求解精度。

2.1 編碼與初始種群生成

本文采用整數(shù)編碼。隨機(jī)生成n條長(zhǎng)度為客戶點(diǎn)數(shù)的染色體，引入貪婪算法的思想，選擇容量約束最大的車輛按隨機(jī)生成的客戶排列順序先進(jìn)行取送貨，直到其達(dá)到容量約束，再選擇容量約束次之的車輛進(jìn)行服務(wù)，直到所有客戶點(diǎn)都被服務(wù)完畢。每輛車在開(kāi)始服務(wù)時(shí)，在開(kāi)始服務(wù)的客戶點(diǎn)前插入數(shù)字0，代表此時(shí)車輛從配送中心出發(fā)。遺傳算法編碼及解碼如圖1所示。本文建立的SPDVRPTN模型存在固定車輛服務(wù)順序即需先對(duì)客戶集m服務(wù)再對(duì)客戶集n服務(wù)。將兩個(gè)客戶集同時(shí)編碼時(shí)會(huì)因交叉變異產(chǎn)生許多不可行解，導(dǎo)致算法效率降低。因此對(duì)兩類客戶采用分段編碼，客戶集m在前，客戶集n在后，二者各自交叉變異互不影響。

圖1 編碼與解碼

2.2 適應(yīng)度函數(shù)與選擇策略

本文建立模型的目標(biāo)為總成本最小，適應(yīng)度函數(shù)的取值為總成本的倒數(shù)。在選擇操作時(shí)，本文結(jié)合精英保留和輪盤(pán)賭策略，保留每次迭代前m個(gè)精英個(gè)體，將其復(fù)制到下一代，非精英個(gè)體進(jìn)行輪盤(pán)賭選擇，保留種群中的優(yōu)秀個(gè)體，使其不因交叉變異而丟失，從而提高算法的求解速率。

2.3 交叉與變異操作

2.3.1 自適應(yīng)策略

本文采用文獻(xiàn)[13]提出的正弦自適應(yīng)遺傳算法，將交叉概率與當(dāng)代遺傳中種群適應(yīng)度值的平均值和最大值相聯(lián)系。算法交叉變異概率按式(23)和式(24)計(jì)算

(23)

(24)

其中，Pc、Pm為交叉、變異概率，Pc1、Pc2分別為最大最小交叉概率值，Pm1、Pm2為最大最小變異概率值Pc1、Pc2∈[0.4，0.99]，Pm1、Pm2∈[0.001，0.1]，fm為最大適應(yīng)度值，f′為個(gè)體適應(yīng)度值，fa為種群平均適應(yīng)度值。

2.3.2 交叉操作

本文采用部分匹配交叉。遺傳算法進(jìn)行交叉后容易產(chǎn)生無(wú)效個(gè)體，部分匹配交叉能夠通過(guò)建立不同染色體基因之間的映射關(guān)系對(duì)交叉后的染色體進(jìn)行修復(fù)。這里選用交叉點(diǎn)為2的部分匹配交叉，具體操作如圖2所示。

2.3.3 變異操作

文獻(xiàn)[14]在用禁忌搜索算法進(jìn)行車輛路徑規(guī)劃時(shí)運(yùn)用了一個(gè)混合算子，豐富算法的搜索方向，從而避免算法陷入局部最優(yōu)。本文將該混合算子作為IAGA的變異算子，即在變異時(shí)，隨機(jī)從以下4種變異方式中選擇一種執(zhí)行。

(1)進(jìn)化逆轉(zhuǎn)算子：染色體在隨機(jī)的兩個(gè)客戶點(diǎn)間發(fā)生斷裂，逆轉(zhuǎn)其基因順序后再插入，并且逆轉(zhuǎn)后適應(yīng)度值有所提高的才接受下來(lái)，否則逆轉(zhuǎn)無(wú)效，如圖3所示。

圖3 進(jìn)化逆轉(zhuǎn)算子

(2)1-opt交換搜索算子：隨機(jī)截取一個(gè)基因插入到染色體中的另一個(gè)位置，如圖4所示。

圖4 1-opt交換搜索算子

(3)2-opt交換搜索算子：隨機(jī)選擇兩個(gè)基因交換其位置，如圖5所示。

圖5 2-opt交換搜索算子

(4)3-opt交換搜索算子：隨機(jī)選擇3個(gè)基因從前往后依次調(diào)換位置，如圖6所示。

圖6 3-opt交換搜索算子

3 仿真實(shí)驗(yàn)

3.1 仿真數(shù)據(jù)與參數(shù)設(shè)置

本文采用solomn100數(shù)據(jù)集中的c101進(jìn)行改造。假設(shè)路網(wǎng)內(nèi)有一個(gè)編號(hào)為0的配送中心和25個(gè)客戶點(diǎn)，配送中心及客戶點(diǎn)坐標(biāo)采用原數(shù)據(jù)。客戶間存在服務(wù)與被服務(wù)關(guān)系，車輛在客戶編號(hào)為1-13的客戶處取貨后，為后續(xù)編號(hào)為14-25的客戶送貨，算例構(gòu)建時(shí)需保證客戶接受服務(wù)的時(shí)間在配送中心的服務(wù)時(shí)間窗內(nèi)，編號(hào)為1-13的客戶其取貨量大于編號(hào)14-25客戶的送貨量，確保供大于需，詳細(xì)信息見(jiàn)表1。時(shí)間窗的開(kāi)始時(shí)間以早上8點(diǎn)為計(jì)算的零時(shí)刻，配送中心時(shí)段為早8點(diǎn)至下午14點(diǎn)，共6個(gè)小時(shí)，360分鐘。以客戶1舉例，其時(shí)間窗為152-199，即早上10點(diǎn)32分至11點(diǎn)19分。車輛參數(shù)見(jiàn)表2，客戶的時(shí)間懲罰系p1=3，p2=5， 將不同時(shí)段不同路段下的行駛速度用多個(gè)分段函數(shù)表示，并整理為表3。

表1 客戶信息

表2 車輛參數(shù)

表3 不同路段時(shí)段下的車輛行駛速度集/(km/h)

進(jìn)行實(shí)驗(yàn)時(shí)從3個(gè)維度驗(yàn)證模型和算法有效性：①將IAGA算法用于求解本文SPDVRPTN模型，驗(yàn)證算法的有效性；②將IAGA算法與其它智能算法在不同客戶規(guī)模下的求解結(jié)果對(duì)比，驗(yàn)證本文設(shè)計(jì)算法的優(yōu)越性；③將本文的多車型配送與單車型配送成本對(duì)比，驗(yàn)證多車型配送的優(yōu)越性。

程序采用matlabR2017編程實(shí)現(xiàn)，運(yùn)行環(huán)境為主頻2.7 GHz的Intel Core i7處理器。算法參數(shù)設(shè)置如下：種群大小為200，迭代次數(shù)為500，算法代溝為0.9，交叉變異概率為Pc1=[0.5，0.8]，Pc2=[0.4，0.6]，Pm1=[0.03，0.05]，Pm2=[0.02，0.1]。

3.2 求解結(jié)果分析

利用本文設(shè)計(jì)的改進(jìn)的自適應(yīng)遺傳算法求解，得到最優(yōu)成本配送方案。求解結(jié)果共有6條配送路徑，調(diào)用車輛6臺(tái)，其中類型一4臺(tái)，類型二和類型三分別1臺(tái)，各子路徑距離與費(fèi)用見(jiàn)表4。配送路線如圖7所示，算法迭代過(guò)程如圖8所示。可以看出，算法隨著迭代次數(shù)的增加呈現(xiàn)快速收斂，求得最優(yōu)解為6438.2元，車輛行駛總距離為413 km。算法共運(yùn)行20次，平均運(yùn)行時(shí)間為81.3 s。說(shuō)明設(shè)計(jì)的算法對(duì)模型有較好的求解效果且具有良好的收斂性。

表4 最優(yōu)成本配送方案

圖7 最優(yōu)配送方案路線

圖8 自適應(yīng)遺傳算法迭代趨勢(shì)

3.3 單車型和多車型對(duì)比

為驗(yàn)證多車型配送對(duì)目標(biāo)成本的影響，針對(duì)此算例進(jìn)行單車型與多車型配送求解結(jié)果的對(duì)比分析，車輛參數(shù)參照上文。Pt表示時(shí)間窗懲罰成本，Cr表示車輛固定費(fèi)用，Ct表示車輛派遣成本，C表示總成本，GAP表示單車型配送各項(xiàng)成本與多車型配送各項(xiàng)成本的相對(duì)誤差。

由表5知，多車型配送相比于單車型配送在降低成本方面具有更大優(yōu)勢(shì)。單獨(dú)使用車型一時(shí)，由于車輛容量小，導(dǎo)致使用車輛數(shù)大大增加。單獨(dú)使用車型二時(shí)，配送成本升高了8.6%，單獨(dú)使用類型三的車輛進(jìn)行派送時(shí)，其配送成本最高。綜合來(lái)看，多車型配送成本最低，驗(yàn)證了本文所建多車型模型的有效性。

表5 單車型與多車型配送成本對(duì)比

3.4 智能算法對(duì)比分析

本文將IAGA與文獻(xiàn)[15]中的改進(jìn)蟻群算法(improved ant colony algorithm，IACO)及遺傳算法(GA)的在不同客戶規(guī)模下的最小目標(biāo)值(Best)、平均目標(biāo)值(Avg)、計(jì)算時(shí)間(t)、標(biāo)準(zhǔn)差(Dev)對(duì)比，以驗(yàn)證本文算法的有效性。GAP代表本文設(shè)計(jì)的IAGA算法與IACO、GA最小目標(biāo)值的偏差。IACO的參數(shù)設(shè)置：螞蟻數(shù)m=30， 信息素強(qiáng)度q0=20，α=2，β=3， 信息素濃度相對(duì)重要性為1。GA參數(shù)設(shè)置：種群大小200，pc=0.8，pm=0.8。 算法分別運(yùn)行20次，最大迭代次數(shù)為500次。

IAGA求解結(jié)果見(jiàn)表6。IACO與IAGA求解結(jié)果對(duì)比見(jiàn)表7?？梢钥闯觯琁AGA在保持良好求解精度的同時(shí)有效縮短了求解時(shí)間，提升求解效率，算法穩(wěn)定性較好。GA與IAGA求解結(jié)果對(duì)比見(jiàn)表8。易發(fā)現(xiàn)本文設(shè)計(jì)的IAGA算法相比傳統(tǒng)遺傳算法在求解精度和魯棒性方面都有明顯提升，算法性能增強(qiáng)。但因?yàn)樘嵘怂惴◤?fù)雜度，隨著客戶規(guī)模的擴(kuò)大，求解時(shí)間有所增加?？偟膩?lái)說(shuō)，本文設(shè)計(jì)的IAGA算法在求解本文研究問(wèn)題時(shí)具有較好的精確性和魯棒性，求解效率較高。

表6 IAGA求解結(jié)果

表8 IAGA與GA求解結(jié)果對(duì)比

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

為提升配送服務(wù)質(zhì)量，需結(jié)合現(xiàn)實(shí)環(huán)境中影響車輛配送的因素進(jìn)行路線安排。本文綜合考慮了路段和時(shí)段對(duì)車速的影響，定義出不同路段不同時(shí)段下的車輛行駛速度，結(jié)合客戶的取送貨需求，站在客戶關(guān)系角度出發(fā)，考慮多種取送貨情況和車型多樣性，建立時(shí)變網(wǎng)絡(luò)下同時(shí)取送貨車輛的車輛路徑優(yōu)化模型。根據(jù)模型特點(diǎn)，設(shè)計(jì)改進(jìn)的自適應(yīng)遺傳算法進(jìn)行求解。研究結(jié)果表明：本文考慮的多車型配送能夠有效降低配送成本，設(shè)計(jì)的改進(jìn)自適應(yīng)遺傳算法具有較好的性能，建立的模型考慮車速變化和不同取送貨情況，約束復(fù)雜，求解難度增加，但更符合實(shí)際。期望本文能為企業(yè)提升配送質(zhì)量，節(jié)約配送成本提供參考。