張曉楠，王陸宇，譚昕妮，姜帥

（陜西科技大學(xué) 機(jī)電工程學(xué)院，西安 710021）

時(shí)變條件下基于道路網(wǎng)的車輛路徑優(yōu)化問題（Time dependent vehicle routing problem under road network, TDVRPRN）是在時(shí)間依賴型車輛路徑問題（Time-dependentvehicle routing problem，TDVRP）的基礎(chǔ)上，又綜合考慮了道路網(wǎng)絡(luò)而展開的研究。TDVRPRN 是TDVRP 和基于道路網(wǎng)絡(luò)的車輛路徑問 題（Vehicle routing problem under road network,VRPRN）的擴(kuò)展，也屬于NP 難題[1-2]?，F(xiàn)實(shí)中, 受城市早晚交通高峰、路段限速和意外事故等影響，不同時(shí)段內(nèi)任意兩節(jié)點(diǎn)間的旅行時(shí)間不同，出現(xiàn)跨時(shí)段特征[3-4]。同時(shí)，配送車輛在道路網(wǎng)絡(luò)上行駛，路線安排受道路網(wǎng)絡(luò)通達(dá)性的影響，如道路單雙向限行策略、節(jié)點(diǎn)間連通性等。因此，研究TDVRPRN 具有重要的理論與現(xiàn)實(shí)意義[5]。

目前還沒有關(guān)于TDVRPRN 的研究，但與TDVRPRN 相關(guān)的TDVRP 和VRPRN 已有相關(guān)研究。在TDVRP 方面，Malandraki 等[6]采用階段函數(shù)表示時(shí)間依賴性，在該策略下，旅行時(shí)間在跨時(shí)段時(shí)產(chǎn)生跳躍, 而實(shí)際旅行時(shí)間應(yīng)隨時(shí)間連續(xù)變化。Hill 等[7]提出了基于旅行速度階段函數(shù)的處理方法以避免旅行時(shí)間在跨時(shí)段時(shí)產(chǎn)生跳躍。然而，這兩種處理方法均不滿足先入先出（ First-in-first-out,FIFO） 準(zhǔn)則，為此，李妍峰[8]提出滿足FIFO 準(zhǔn)則的一類處理通用跨時(shí)段的方法, 研究了時(shí)變網(wǎng)絡(luò)環(huán)境下旅行商問題，并構(gòu)造了跨時(shí)段情形下的動(dòng)態(tài)搜索優(yōu)化算法。唐金環(huán)等[9]考慮碳排放，研究考慮旅行時(shí)間和碳排放量的多目標(biāo)車輛路徑問題；趙志學(xué)和李夏苗[10]考慮電動(dòng)車配送的技術(shù)條件限制，研究了時(shí)變交通下的電動(dòng)車城市生鮮配送路徑問題；劉長(zhǎng)石等[11]將TDVRP 與聯(lián)合配送相結(jié)合，綜合考慮油耗、碳排放與聯(lián)合配送模式等因素，研究時(shí)變路網(wǎng)條件下聯(lián)合配送的開放式時(shí)變車輛路徑問題；侯登凱等[12]將TDVRP 與多中心車輛路徑問題和混合車隊(duì)車輛路徑問題結(jié)合。在VRPRN 方面，李妍峰等[13-14]在研究旅行時(shí)間實(shí)時(shí)更新的動(dòng)態(tài)車輛路徑問題時(shí)涉及了道路網(wǎng)絡(luò)，實(shí)驗(yàn)在Sioux Falls 道路網(wǎng)絡(luò)下展開，并提出了關(guān)鍵節(jié)點(diǎn)更新策略。葛顯龍和張慧[15]在研究實(shí)時(shí)交通路網(wǎng)車輛路徑優(yōu)化問題時(shí)基于重慶市道路網(wǎng)絡(luò)展開。

通過梳理以上相關(guān)文獻(xiàn)可見：1）近幾年已出現(xiàn)TDVRP 與其他問題（如聯(lián)合配送[11]、多中心配送[12]、混合車輛配送[12]）的結(jié)合，但還沒有關(guān)于TDVRPRN的研究，而該問題是現(xiàn)實(shí)存在的，需通過更深入研究才能解決。2）現(xiàn)有關(guān)于道路網(wǎng)絡(luò)的相關(guān)研究均是在實(shí)時(shí)動(dòng)態(tài)旅行時(shí)間VRP 中涉及，而其他VRP 擴(kuò)展問題在道路網(wǎng)絡(luò)上的研究還沒有（TDVRP 與實(shí)時(shí)動(dòng)態(tài)旅行時(shí)間VRP 區(qū)別在于，在TDVRP 中，路段行駛時(shí)間隨時(shí)間變化但事先可以通過預(yù)測(cè)確定[13-14]）?；谝陨?，在時(shí)變車輛路徑問題基礎(chǔ)上，考慮車輛行駛的道路網(wǎng)絡(luò)，研究時(shí)變條件下基于道路網(wǎng)的車輛路徑優(yōu)化問題。首先，考慮車輛行駛速度的時(shí)變特征，通過構(gòu)建旅行速度的分段函數(shù)，采用跨時(shí)域的方法利用離散速度計(jì)算動(dòng)態(tài)旅行時(shí)間；其次，基于關(guān)鍵節(jié)點(diǎn)的概念構(gòu)建道路網(wǎng)絡(luò)，克服VRP 考慮道路網(wǎng)絡(luò)時(shí)存在的維度災(zāi)問題；然后，結(jié)合時(shí)變旅行時(shí)間和基于關(guān)鍵點(diǎn)構(gòu)建的道路網(wǎng)路建立TDVRPRN 的數(shù)學(xué)模型，設(shè)計(jì)蟻群算法求解；最后以西安市未央?yún)^(qū)桶裝水配送區(qū)域?qū)嵗M(jìn)行測(cè)試，驗(yàn)證了模型和算法的有效性。

1 問題描述及模型建立

1.1 問題描述

TDVRPRN 問題如圖1 所示，其中，方形表示配送中心，藍(lán)色圓圈表示客戶服務(wù)點(diǎn)，白色圓圈表示網(wǎng)絡(luò)節(jié)點(diǎn)且未產(chǎn)生服務(wù)需求。從圖1 中可以看出：

圖1 TDVRPRN 示意圖Fig.1 Diagram of the TDVRPRN

1）客戶2 僅與客戶3、配送中心1、客戶7 和客戶8 有直接的路徑相連，與其他節(jié)點(diǎn)則沒有；

2）網(wǎng)絡(luò)中沒有配送中心到需求點(diǎn)5 的直接服務(wù)路線，若車輛要去客戶5 服務(wù)，僅能從節(jié)點(diǎn)“A”或者節(jié)點(diǎn)“6”繞過去；

3）其他節(jié)點(diǎn)同理。

為了更好地理解該道路網(wǎng)絡(luò)，圖1b）以客戶2 為例展示了常規(guī)VRP 研究中道路網(wǎng)絡(luò)假設(shè)，也就是說，在常規(guī)VRP 中，假設(shè)所有節(jié)點(diǎn)之間均是連通的，這與實(shí)際不符。圖1c）是基于圖1a）的道路網(wǎng)絡(luò)的旅行時(shí)間時(shí)變車輛路線示意圖。

從圖1 還可以看出，1 個(gè)配送中心和7 個(gè)客戶 的配送網(wǎng)絡(luò)結(jié)構(gòu)涉及8 個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)（網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)≥客戶需求點(diǎn)數(shù)）。在現(xiàn)實(shí)中，若考慮道路網(wǎng)絡(luò)，有限個(gè)服務(wù)需求點(diǎn)的配送網(wǎng)絡(luò)可能涉及龐大的道路網(wǎng)絡(luò)節(jié)點(diǎn)。由此可見，在考慮道路網(wǎng)絡(luò)下，網(wǎng)絡(luò)節(jié)點(diǎn)繁多，路徑優(yōu)化復(fù)雜程度成指數(shù)級(jí)增加?；诖?，本文將其簡(jiǎn)化為單車輛的TDVRPRN，即TDTSPRN（Time dependent travelsale problem under road network,TDTSPRN）。將VRP 簡(jiǎn)化為TSP 是現(xiàn)實(shí)且可行的，如，學(xué)術(shù)界文獻(xiàn)[8]就是針對(duì)時(shí)變網(wǎng)絡(luò)環(huán)境下旅行商問題展開的研究；現(xiàn)實(shí)中，很多物流公司按照街道等行政區(qū)域?qū)⒎?wù)區(qū)域劃分至各個(gè)配送員，然后再對(duì)每個(gè)配送員的服務(wù)路徑展開具體優(yōu)化。

TDTSPRN 可以描述為：配送系統(tǒng)有1 個(gè)配送中心和n個(gè)客戶，配送中心編號(hào)為1，客戶集合C={2, ···,n+ 1}。車輛從配送中心出發(fā)對(duì)n個(gè)客戶組織配送。網(wǎng)絡(luò)中的道路節(jié)點(diǎn)集合為N，N={1,C,N0}，其中N0為車輛可以在該點(diǎn)改變行駛路線的網(wǎng)絡(luò)節(jié)點(diǎn)，一般默認(rèn)該點(diǎn)不會(huì)產(chǎn)生服務(wù)需求。求解的目的是在滿足客戶需求的基礎(chǔ)上，合理安排配送車輛的行駛路徑，使得總旅行時(shí)間最短。其他相關(guān)假設(shè)為：車輛從配送中心出發(fā)完成配送服務(wù)后返回配送中心；每個(gè)客戶只能被服務(wù)一次；交通路網(wǎng)具有時(shí)變特性，配送車輛在不同時(shí)間段內(nèi)以不同時(shí)速行駛，且當(dāng)車輛遇到交通擁堵，按照先進(jìn)先出原則隨車流緩慢行駛。

1.2 符號(hào)定義

TDTSPRN 模型中的所有符號(hào)如表1 所示。

表1 符號(hào)定義Tab.1 Definition of notations

1.3 時(shí)變旅行速率的動(dòng)態(tài)旅行時(shí)間確定

這里考慮車輛旅行速度的時(shí)變特征，把一天分為幾個(gè)時(shí)段，給出車輛在不同時(shí)段內(nèi)的分段函數(shù)，采用跨時(shí)域的方法利用離散速度計(jì)算車輛在任意兩節(jié)點(diǎn)間的旅行時(shí)間。通常情況下，時(shí)間段的劃分需要很短，如15 min，這樣才能將該時(shí)段內(nèi)的車輛平均速度視為該時(shí)間段內(nèi)的固定速度。這種方法可確保車輛根據(jù)FIFO 規(guī)則沿弧線行駛。圖2 是相應(yīng)的旅行速度分段函數(shù)，圖3 是不同時(shí)間段的車輛行駛距離和行駛時(shí)間。

圖2 不同時(shí)間段車輛行駛速度Fig.2 Vehicle traveling speed at different time periods

圖3 不同時(shí)間段車輛行駛距離和時(shí)間Fig.3 Traveling distance and time at different time periods

假設(shè)di∈ [TL-1，TL],則tij的詳細(xì)計(jì)算步驟如下：

1.4 關(guān)鍵點(diǎn)的道路網(wǎng)絡(luò)確定

為了克服車輛路徑問題在考慮道路網(wǎng)時(shí)存在的維度災(zāi)問題，提出一種基于關(guān)鍵節(jié)點(diǎn)的概念來構(gòu)建道路網(wǎng)絡(luò)，即在實(shí)際道路網(wǎng)絡(luò)的基礎(chǔ)上，選擇車流量較大的路徑交叉節(jié)點(diǎn)作為路網(wǎng)中的關(guān)鍵節(jié)點(diǎn)。假定車輛從節(jié)點(diǎn)A出發(fā)到達(dá)節(jié)點(diǎn)B，圖4 中的節(jié)點(diǎn)表示為實(shí)際路網(wǎng)中的交叉路口，實(shí)線線段表示為實(shí)際路網(wǎng)中的可通行路段，虛線線段表示實(shí)際路網(wǎng)中的不可通行路段，由此可看出，從節(jié)點(diǎn)A到節(jié)點(diǎn)B之間存在包括A、B在內(nèi)的49 個(gè)路徑交叉節(jié)點(diǎn)，因此車輛從A到B的路徑選擇有O(449)種方案。圖5 是基于關(guān)鍵節(jié)點(diǎn)的道路網(wǎng)絡(luò)，其中，實(shí)心原點(diǎn)表示選擇的路徑關(guān)鍵節(jié)點(diǎn)，可以明顯看出，基于關(guān)鍵點(diǎn)道路網(wǎng)絡(luò)的路徑選擇急劇減少，可見，該策略可行。

圖5 基于關(guān)鍵節(jié)點(diǎn)的道路網(wǎng)絡(luò)示意圖Fig.5 Diagram of road network based on key nodes

1.5 模型建立

基于以上，建立如下模型：

式（1）為目標(biāo)函數(shù)，目標(biāo)函數(shù)表示總旅行時(shí)間最短；式（2）和式（3）表示車輛到達(dá)和離開的是同一個(gè)節(jié)點(diǎn)；式（4）表示車輛到達(dá)節(jié)點(diǎn)的時(shí)間等于離開節(jié)點(diǎn)的時(shí)間；式（5）表示車輛在第L時(shí)間段行駛的距離不大于弧線e(i,j) 的 總距離；式（6）表示弧線e(i,j)的總距離為各個(gè)時(shí)間段車輛行駛距離總和；式（7）表示在第L時(shí)間段車輛的旅行時(shí)間等于在該時(shí)間段車輛的行駛距離與旅行速度之比；式（8）表示車輛在第L時(shí)間段的實(shí)際行駛時(shí)間不大于車輛行駛完弧線e(i,j) 的 總時(shí)間；式（9）表示車輛行駛完弧線e(i,j)的總旅行時(shí)間為各個(gè)時(shí)間段車輛行駛時(shí)間的總和；式（10）表示車輛離開j節(jié)點(diǎn)的時(shí)間；式（11）表示子回路約束；式（12）和式（13）表示符號(hào)和決策變量的約 束。

2 算法設(shè)計(jì)

蟻群算法是一種全局搜索算法，當(dāng)搜索最優(yōu)解時(shí)，能通過信息素的來進(jìn)行信息的交互，繼而實(shí)現(xiàn)同時(shí)在不同空間進(jìn)行搜索。文獻(xiàn)[16-17]已經(jīng)證明了該算法有較強(qiáng)的全局搜索能力，適用于在求解VRP及其擴(kuò)展問題。鑒于此，本文采用蟻群算法求解TDTSPRN 模型。蟻群算法流程如圖6 所示。

圖6 蟻群算法流程圖Fig.6 Flow chart of ant colony algorithm

1）初始化算法所有參數(shù)和變量。輸入最大迭代maxgen ， 螞蟻總數(shù)m， 信息素重要程度因子 α，啟發(fā)函數(shù)重要程度因子 β，信息素的蒸發(fā)因子ρ。令當(dāng)前迭代次數(shù) gen=1。

2）構(gòu)建可行的方案。

步驟1 將m螞蟻放入配送中心中，定義tabum表示螞蟻m的 禁忌列表，令 tabum=?。

步驟2 螞蟻m依次從配送中心出發(fā)，將當(dāng)前螞蟻所有還沒有訪問的節(jié)點(diǎn)放入集合 a llowedm。

步驟3 依據(jù)時(shí)變旅行速度分階段函數(shù)，計(jì)算當(dāng)前時(shí)刻下兩點(diǎn)間的旅行時(shí)間tij，并計(jì)算車輛到達(dá)節(jié)點(diǎn)J的時(shí)間aj。

步驟4 計(jì)算車輛從當(dāng)前節(jié)點(diǎn)行駛到節(jié)點(diǎn)的轉(zhuǎn)移概率。螞蟻m根據(jù)信息素和信息素組成的狀態(tài)轉(zhuǎn)移概率函數(shù)Pmi j，使用輪盤賭的形式從當(dāng)前節(jié)點(diǎn)選擇下一個(gè)節(jié)點(diǎn)進(jìn)行訪問。螞蟻m移動(dòng)的概率Pmij從當(dāng)前節(jié)點(diǎn)i到下一個(gè)節(jié)點(diǎn)j定義為：

式中：參數(shù) α ， β用于權(quán)衡各個(gè)因素以指導(dǎo)搜索過程；ηij為啟發(fā)式因子，定義 ηij=1/tij。

5）算法終止。如果 gen

3 實(shí)例測(cè)試

3.1 實(shí)例描述

本文以西安市未央?yún)^(qū)桶裝水配送中心及其服務(wù)的10 個(gè)需求點(diǎn)為例，圖7 為服務(wù)的10 個(gè)需求點(diǎn)，圖8 為該配送區(qū)域內(nèi)的19 個(gè)關(guān)鍵網(wǎng)絡(luò)節(jié)點(diǎn)，這些節(jié)點(diǎn)來源于現(xiàn)有路徑網(wǎng)絡(luò)的基礎(chǔ)上確定經(jīng)常發(fā)生交通擁堵的節(jié)點(diǎn)。

圖7 服務(wù)的10 個(gè)需求點(diǎn)Fig.7 The 10 demand nodes

圖8 關(guān)鍵道路網(wǎng)絡(luò)節(jié)點(diǎn)Fig.8 Key nodes at road network

3.2 道路網(wǎng)絡(luò)

根據(jù)需求點(diǎn)和關(guān)鍵道路節(jié)點(diǎn)位置，圖9 給出了各節(jié)點(diǎn)之間城市主干雙向通行道路構(gòu)建的關(guān)鍵路網(wǎng)示意圖。圖中，黑色圓圈易發(fā)生交通擁堵的19 個(gè)關(guān)鍵路徑節(jié)點(diǎn)，藍(lán)色圓圈代表1 個(gè)桶裝水配送中心，紅色圓圈代表10 個(gè)小區(qū)需求點(diǎn)。各節(jié)點(diǎn)之間的路徑均由實(shí)際路網(wǎng)簡(jiǎn)化處理，車輛可在路徑之間雙向行駛。

圖9 道路網(wǎng)絡(luò)構(gòu)建Fig.9 Load network construction

在上述實(shí)際道路網(wǎng)絡(luò)圖中，除去選定的配送中心、需求點(diǎn)、路徑關(guān)鍵節(jié)點(diǎn)以外，還存在路徑與路徑之間的交叉節(jié)點(diǎn)，在后續(xù)的算法求解過程當(dāng)中這些路徑交叉節(jié)點(diǎn)與實(shí)際選取關(guān)鍵節(jié)點(diǎn)難以被區(qū)分。為解決此問題，本文進(jìn)一步簡(jiǎn)化路網(wǎng)，即道路網(wǎng)絡(luò)僅包括路徑關(guān)鍵節(jié)點(diǎn)、需求點(diǎn)以及配送中心點(diǎn)的道路網(wǎng)絡(luò)，簡(jiǎn)化后道路模型如圖10 所示。

圖10 基于關(guān)鍵點(diǎn)的道路網(wǎng)絡(luò)Fig.10 Road networks based on key points

3.3 動(dòng)態(tài)旅行時(shí)間

根據(jù)西安市未央?yún)^(qū)的道路交通報(bào)告，預(yù)測(cè)出西安市未央?yún)^(qū)城市主干道路在早晚高峰時(shí)間的速度隨時(shí)間的變化圖。早高峰速度時(shí)間圖如圖11 所示，晚高峰速度時(shí)間圖如圖12 所示。其余時(shí)間段車輛行駛速度統(tǒng)一為城市道路平均順暢速度45 km/h。

圖11 早高峰速度時(shí)間變化圖Fig.11 Speed during morning peak time span

圖12 晚高峰速度時(shí)間變化圖Fig.12 Speed during evening peak time span

3.4 求解結(jié)果

采用MATLAB 2016a 編程，操作系統(tǒng)Windows 10，電腦內(nèi)存為8G，CPU 為Intel i7-6700, 主頻3.40 GHz。設(shè)置算法參數(shù)為：車輛出發(fā)時(shí)間為07：00，最大迭代次數(shù) m axgen=300，螞蟻總數(shù)為20，信息素重要程度因子 α=1，啟發(fā)函數(shù)重要程度因子 β =1，信息素的蒸發(fā)因子 ρ =1。

圖13 是本文算法的求解迭代圖，算法搜索約在50 次以內(nèi)趨于平穩(wěn)，說明該算法能穩(wěn)定收斂，算法合理有效。

圖13 算法進(jìn)化迭代圖Fig.13 Algorithm iteration diagram

圖14 是車輛旅行路徑圖。從求解結(jié)果來看：需求點(diǎn)服務(wù)順序?yàn)椤? — 10 — 11 — 9 — 8— 7— 6 —5— 4— 3”，即車輛先服務(wù)藍(lán)光公園華府，到五一花園、芊域陽光、中心小區(qū)（尚稷路）、萬花園小區(qū)、奇星御園、百花園小區(qū)、東方名苑、名都城小區(qū)最后服務(wù)立豐昆明時(shí)光。車輛行駛路線為1— （12）— 2 —（13）—（15）—（29）—（30）— 10 —11—（27）— 9 —（27）—（25）— 7 —（25）— 8 —（20）—（19）— 6 —（18）—（17）— 5 — 4 —（14）— 3 — 1，括號(hào)中為路徑關(guān)鍵節(jié)點(diǎn)，行駛路程為67.879 km。車輛07：00 從配送中心出發(fā)，09:21 回到配送中心完成配送任務(wù)。

圖14 車輛行駛路徑Fig.14 Vehicle routing

3.5 敏感性分析

1）旅行速度變化

由于城市交通擁堵情況越發(fā)的嚴(yán)重，部分城市采取了錯(cuò)峰出行政策，如杭州與重慶通過實(shí)施這項(xiàng)政策在緩解交通擁堵，較少路段通行車流量方面取得了非常不錯(cuò)的成績(jī)；重慶采取錯(cuò)峰出行政策的第二日，中心城區(qū)的早高峰平均車速同比提升9.2%，早高峰車流量同比平均下降14.3%。另外，尾號(hào)限行制度也是各大城市緩解城市交通壓力的另一重要措施?；诖?，分析在政策引導(dǎo)下，早晚高峰旅行速度的分階段函數(shù)改變對(duì)車輛總旅行時(shí)間影響。以錯(cuò)峰出行和尾號(hào)限行兩種不同的交通擁堵政策可能引起的旅行速度函數(shù)用于測(cè)試。

模式1 在實(shí)施錯(cuò)峰出行的情況下，車輛速度下降得到一定緩解，但很長(zhǎng)時(shí)間內(nèi)車輛在節(jié)點(diǎn)間的行車速度不能快速恢復(fù)到日常速度45 km/h，這里以圖15 和圖16 為例測(cè)試。

圖15 早高峰速度時(shí)間變化（錯(cuò)峰出行）Fig.15 Speed during morning peak time span(staggered shifts)

圖16 晚高峰速度時(shí)間變化（錯(cuò)峰出行）Fig.16 Speed during evening peak time span(staggered shifts)

車輛旅行路徑如圖17 所示，可以看出，需求點(diǎn)服務(wù)順序?yàn)?— 4 — 5 — 6— 8 — 7 — 9 — 11 — 10 — 2 。完整行駛路線為1— 3 —（14）— 4 — 5 —（17）—（18）—6 —（19）—（20）—（24）— 8 —（25）— 7 —（25）—（27）— 9 —（27）— 11 — 10 —（30）—（29）—（15）—（13）—2 —（12）— 1。車輛從07:00 離開桶裝水配送中心，08:52 完成所有配送任務(wù)回到配送中心。可見，該模式下車輛行駛路徑不變，但旅行時(shí)間縮短了29 min。

圖17 車輛配送路徑圖Fig.17 Vehicle routing

模式2 在實(shí)施尾號(hào)限行的情況下，車輛速度下降也得到一定緩解，并能快速恢復(fù)到日常速度45 km/h，這里以圖18 和圖19 為例測(cè)試。

圖18 早高峰速度時(shí)間變化圖（尾號(hào)限行）Fig.18 Speed during morning peak time span (license plate restrictions)

圖19 晚高峰速度時(shí)間變化圖（尾號(hào)限行）Fig.19 Speed during evening peak time span (license plate restrictions)

車輛旅行路徑圖如圖20 所示，可以看出：需求點(diǎn)服務(wù)順序?yàn)? — 4 — 5 — 6 — 8 — 7 — 9 — 11 — 10 —2 ；完整行駛路線為1— 3 —（14）— 4 — 5 —（17）—（18）— 6 —（19）—（20）—（24）— 8 —（25）—7 —（25）—（27）— 9 —（27）— 11 — 10 —（30）—（29）—（15）—（13）— 2 —（12）— 1。車 輛 從07:00 離開桶裝水配送中心，08:47 完成所有配送任務(wù)回到配送中心?？梢姡撃Ｊ较萝囕v行駛路徑不發(fā)生改變，但行駛時(shí)間縮短34 min。

圖20 車輛配送路徑圖Fig.20 Vehicle routing

從以上兩種模式求解結(jié)果對(duì)比可以看出：車輛旅行速度的改變并不會(huì)引起車輛優(yōu)化路徑的改變，但對(duì)總旅行時(shí)間影響較大。說明，伴隨著城市為緩解擁堵的各項(xiàng)交通政策的實(shí)施，運(yùn)輸企業(yè)無需對(duì)配送路徑進(jìn)行重新優(yōu)化，配送效率能得到極大提升。

2）出發(fā)時(shí)間變化

車輛在城市路網(wǎng)中的行駛速度不僅受到行駛距離與行駛路段的影響，還受到車輛出發(fā)時(shí)間的影響，如早晚高峰擁堵導(dǎo)致車輛在早晚高峰時(shí)間段內(nèi)出發(fā)配送貨物，就易遇上交通擁堵，車輛行駛速度較慢。基于此，本文進(jìn)一步將通過改變?cè)紝?shí)例中的車輛出發(fā)時(shí)間去研究怎樣選擇車輛的出行時(shí)間，使車輛的行駛方案能夠更加優(yōu)化。

表2 為不同出發(fā)時(shí)間下的目標(biāo)函數(shù)值對(duì)比，從中可以看出，不同出發(fā)時(shí)間對(duì)于車輛的行駛時(shí)間影響較大，相較于07:00 出發(fā)而言，車輛從早上10:00 出發(fā)總旅行時(shí)間更短。相較于車輛出發(fā)時(shí)間為07:00 的情況下，車輛的行駛時(shí)間縮短了40 min。

表2 不同出發(fā)時(shí)間算例的目標(biāo)函數(shù)值表Tab.2 Objective function values for instances of different departure time

4 結(jié)論

1）在時(shí)變VRP 的基礎(chǔ)上，綜合考慮了道路網(wǎng)絡(luò)，建立了相應(yīng)的單車輛模型，研究問題更符合實(shí)際配送的運(yùn)作。

2）提出了基于關(guān)鍵點(diǎn)的道路網(wǎng)絡(luò)構(gòu)建，克服了現(xiàn)實(shí)道路網(wǎng)絡(luò)的復(fù)雜性。

3）車輛行駛速度的改變并不會(huì)引起車輛優(yōu)化路徑的改變，但對(duì)行駛效率提升較大；相較于早上07:00 出發(fā)而言，車輛從10:00 出發(fā)總旅行時(shí)間更短，能縮減行駛時(shí)間40 min。

未來研究中將將其擴(kuò)展到多車輛問題，并進(jìn)一步考慮時(shí)間窗、模糊需求等因素的影響， 使問題更貼近實(shí)際配送。