,

(1.上海理工大學(xué) 管理學(xué)院,上海 200093; 2.國網(wǎng)上海市電力公司物資公司,上海 200002)

1 研究背景

同時送取貨物的車輛路徑問題(vehicle routing problem with simultaneous deliveries and pickups,VRPSDP)最早由Min[1]于1989年提出,Dethloff[2]于2001年首次從逆向物流的角度研究了此問題.VRPSDP是逆向物流車輛路徑問題(vehicle routing problem,VRP)的一個重要組成部分,與其并列的還有先送貨后取貨的車輛路徑問題(vehicle routing problem with backhauls,VRPB),以及混合送貨和取貨的車輛路徑問題VRPBM(vehicle routing problem with backhauls of mixed loads,VRPBM)[3].

由于VRPSDP將正向物流和逆向物流同時加以考慮,更接近于現(xiàn)實(shí)生活中的物流配送服務(wù),對實(shí)際問題更有指導(dǎo)意義,近年來越來越多的學(xué)者對VRPSDP展開了研究[3-9],其研究成果可被分為兩大部分:a.對基本VRPSDP進(jìn)行改進(jìn),提出了多種VRPSDP的變種問題,如帶時間窗的VRPSDP[4]、具有車輛最大行程約束的VRPSDP[5]、隨機(jī)旅行時間的VRPSDP[3]、車輛容量可調(diào)節(jié)的VRPSDP[6]、異車型VRPSDP等[7].b.設(shè)計(jì)并提出了多種求解VRPSDP的方法.張建勇等[8]結(jié)合2-opt 法和等級替換策略設(shè)計(jì)了求解VRPSDP 的一種混合遺傳算法,給出了該算法初始種群的兩種生成規(guī)則,闡述了違反約束條件的處理方法;Liu等[4]在求解帶時間窗的VRPSDP時,用遺傳算法進(jìn)行局部搜索,用禁忌搜索進(jìn)行路徑分配的優(yōu)化;吳斌等[9]提出了基于混沌理論的精英均值計(jì)算旋轉(zhuǎn)角算法;Qu等[6]設(shè)計(jì)了兩階段啟發(fā)式算法,并將其用于車輛容量可調(diào)節(jié)的VRPSDP.

自VRPSDP 提出至今,其模型的改進(jìn)和求解算法雖然均已取得很大研究成果,但大部分研究仍存在一些不足,可歸納為兩方面.一方面,絕大多數(shù)VRPSDP模型假設(shè)在計(jì)劃期內(nèi)(一般為一天)配送車輛只能運(yùn)行一次,考慮多車次的VRPSDP模型在現(xiàn)有文獻(xiàn)中極其罕見.然而,現(xiàn)實(shí)生活中,物流公司為了節(jié)約配送成本和完成配送任務(wù),通常會啟用較少的配送車輛,同一輛車會多次往返于配送中心,完成多條配送路線的配送任務(wù).另一方面,絕大多數(shù)VRPSDP模型沒有考慮貨物的裝卸時間和車輛的工作時間.

本文研究多車次同時送取貨的車輛路徑問題(multi-trip vehicle routing problem with simultaneous deliveries and pickups,MTVRPSDP),并在該問題中考慮了貨物的裝卸時間、車輛的工作時間和載重量限制.與基本VRPSDP相比,本文考慮的MTVRPSDP存在以下幾個難點(diǎn):第一,多車次的引入,增加了問題的復(fù)雜度;第二,對車輛工作時間的限制,加強(qiáng)了問題的約束.當(dāng)車輛工作時間接近最大限制時,即使車輛的載重量仍然可以滿足某些客戶的需求,但也必須返回配送中心.對車輛工作時間的限制不僅會導(dǎo)致車輛總行程的增加,而且會導(dǎo)致車輛數(shù)和配送路徑數(shù)的增加,使問題的優(yōu)化難度加大[3].

為了求解MTVRPSDP,本文在量子計(jì)算和蟻群算法的基礎(chǔ)上,吸收這兩種方法的長處和優(yōu)勢,克服它們的短處和缺陷,進(jìn)而提出求解該問題的量子蟻群算法.本文的第二部分建立了MTVRPSDP問題的數(shù)學(xué)模型;第三部分介紹了量子蟻群算法,以及求解MTVRPSDP的基本流程;第四部分進(jìn)行了實(shí)例仿真,采用量子蟻群算法求解MTVRPSDP問題,獲得了滿意的結(jié)果.

2 MTVRPSDP描述及其數(shù)學(xué)模型

2.1 問題描述

本文研究的MTVRPSDP是在所有客戶點(diǎn)的位置和貨物需求均已知的情況下,完成所有客戶的配送和取貨服務(wù),并要求配送中心啟用的配送車輛成本和完成配送服務(wù)的行駛成本之和達(dá)到最小.假設(shè)每個客戶點(diǎn)可以同時收貨和發(fā)貨,也可以只收貨或只發(fā)貨;每輛車可以在一個工作日內(nèi)為多條配送路線上的客戶提供送貨和取貨服務(wù).此外,配送車輛和客戶點(diǎn)還必須同時滿足如下條件:

a.服務(wù)約束,每輛車可以服務(wù)多個客戶,但一個客戶僅能由一輛車服務(wù);

b.配送中心約束,所有車輛由單一配送中心出發(fā),配送完路徑上所有的客戶后返回配送中心;

c.裝載量約束,每條配送路徑上車輛的裝載量不能超過其最大載重量限制;

d.最大工作時間限制,每輛車的工作時間(行駛時間和裝卸貨時間之和)不能超過其最大工作時間.

2.2 符號定義與數(shù)學(xué)模型

決策變量:

MTVRPSDP的目標(biāo)是在滿足上述約束條件的基礎(chǔ)上,確定完成所有送貨和取貨任務(wù)且期望成本最小的車輛路徑.可將MTVRPSPD表述為如下數(shù)學(xué)模型:

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

(1)

約束條件

(2)

(3)

(4)

(5)

(6)

0≤qijkxijk≤Gk,i∈V,j∈V,k∈K

(7)

(8)

xijk∈{0,1},i∈V,j∈V,k∈K

(9)

其中:目標(biāo)函數(shù)式(1)表示最小化所有車輛的啟動成本與行駛路徑成本之和;約束式(2)保證每個顧客都要被服務(wù)一次且僅被服務(wù)一次;式(3)保證一輛車服務(wù)客戶j,則離開該客戶的仍然是這輛車,即客戶j只被同一輛車服務(wù);式(4)保證每輛車從配送中心出發(fā)并最終返回到配送中心;式(5)排除子回路;式(6)表示車輛在經(jīng)過客戶j前后的載貨量變化情況;式(7)保證每輛車在任意一條配送路段上的貨物運(yùn)輸量不超過其最大載重量,且不為負(fù);式(8)保證車輛k在計(jì)劃期內(nèi)的總工作時間不超過其最大工作時間Tk,stki表示車輛k在節(jié)點(diǎn)i的裝卸時間;式(9)是決策變量xijk的取值范圍.

3 MTVRPSDP的量子蟻群算法

蟻群算法(ant colony optimization,ACO)是意大利學(xué)者Dorigo等[10]通過模擬蟻群覓食行為提出的一種基于種群的模擬進(jìn)化算法,其在求解組合優(yōu)化難題和連續(xù)優(yōu)化問題中均取得了較好的結(jié)果.近年來,越來越多的學(xué)者利用ACO求解物流配送中的車輛調(diào)度和路徑優(yōu)化問題[11].相比于其他智能優(yōu)化算法,ACO具有較強(qiáng)魯棒性、易與其他方法結(jié)合的優(yōu)點(diǎn).首先,ACO對初始路線的要求不高,即ACO的求解結(jié)果不依賴于初始路線的選擇,而且在搜索過程中不需要進(jìn)行人工調(diào)整;其次,ACO的參數(shù)數(shù)目少,設(shè)置簡單.但是,ACO也有一些不足之處,如:容易陷入局部最優(yōu),搜索速度比較慢等.

螞蟻狀態(tài)的轉(zhuǎn)移和路徑上信息素的更新是ACO的重要組成部分.本文針對基本ACO收斂速度慢和易陷入局部最優(yōu)等缺點(diǎn),將量子進(jìn)化算法中的量子比特和量子旋轉(zhuǎn)門引入ACO,用以改進(jìn)基本ACO算法中的狀態(tài)轉(zhuǎn)移概率,有效抑制算法的早熟現(xiàn)象,并加快算法的求解速度.本文將改進(jìn)后的ACO算法稱為量子蟻群算法(quantum ant colony optimization,QACO),并將其用于求解MTVRPSDP.

3.1 量子編碼特性

量子計(jì)算的基本原理是使量子態(tài)所處疊加態(tài)的各個基態(tài)間的相對相位和概率幅度發(fā)生改變,使各個基態(tài)的發(fā)生概率產(chǎn)生變化,從而使其疊加態(tài)發(fā)生變化,具有并行、疊加、干涉等特征[12].量子比特是量子計(jì)算中基本信息的存儲單元,采用|0〉和|1〉(“|〉”稱為Dirac記號,在量子力學(xué)中表示狀態(tài))來表示微觀粒子的兩種基本狀態(tài).單量子比特的任意狀態(tài)都可以表示為這兩個基本狀態(tài)的線性組合,即除|0〉和|1〉之外,還可以是這兩種狀態(tài)之間的中間狀態(tài)(疊加態(tài)):|φ〉=α|0〉+β|1〉(α和β是一對復(fù)數(shù),表示量子態(tài)的概率幅,即量子態(tài)|φ〉以|α|2的概率坍縮到|0〉或以|β|2的概率坍縮到|1〉,且滿足|α|2+|β|2=1).

一個量子比特同時可包含0和1的信息,那么一個長度為m的量子位可以表示2m種不同的狀態(tài),有m個量子位的個體j的概率幅可表示為

(10)

其中,|αi|2+|βi|2=1(i=1,2,…,m).

在QACO中用量子比特來表示量子信息素,設(shè)種群大小為n,其量子信息素用量子位表示為p=(p1,p2,…,pn),其中pj(j=1,2,…,n)如式(10)所示.

3.2 量子旋轉(zhuǎn)門

量子比特相位的改變可以用量子旋轉(zhuǎn)門實(shí)現(xiàn),量子旋轉(zhuǎn)門的調(diào)整方式可定義為:

(11)

本文針對MTVRPSDP的求解和借鑒文獻(xiàn)[12]中量子旋轉(zhuǎn)角的取值方法,設(shè)計(jì)了一種改進(jìn)的θi取值方法,該方法能夠根據(jù)當(dāng)前量子比特概率幅和MTVRPSDP問題的目標(biāo)函數(shù)值計(jì)算出相位的旋轉(zhuǎn)角度,從而實(shí)現(xiàn)蟻群算法中種群的多樣性,避免算法早熟收斂.θi的取值定義如下:

θi=s(αiβi)(θ0+sign(f(xi)-f(bi))0.07π)

(12)

式中,s(αiβi)控制旋轉(zhuǎn)角的旋轉(zhuǎn)方向,若αiβi≥0,s(αiβi)=1,否則,s(αiβi)=-1.sign(f(xi)-f(bi))為符號函數(shù),自適應(yīng)地調(diào)整旋轉(zhuǎn)角的大小.當(dāng)f(xi)-f(bi)>0時,sign(f(xi)-f(bi))=1;當(dāng)f(xi)-f(bi)<0時,sign(f(xi)-f(bi))=-1;當(dāng)f(xi)-f(bi)=0時,則sign(f(xi)-f(bi))=0.θ0為初始旋轉(zhuǎn)角度,xi表示當(dāng)前解,bi表示當(dāng)前最優(yōu)解,f(x)為目標(biāo)函數(shù).

3.3 狀態(tài)轉(zhuǎn)移規(guī)則

(13)

螞蟻k由客戶點(diǎn)i出發(fā),采用偽隨機(jī)規(guī)則確定所要訪問的下一個客戶:若q>q0(q0∈(0,1)是一個常數(shù);q為(0,1)區(qū)間的隨機(jī)數(shù)),根據(jù)式(13)計(jì)算出的轉(zhuǎn)移概率并按照輪盤賭的方法確定下一個訪問的客戶;否則,取轉(zhuǎn)移概率最大的客戶j為下一個訪問的客戶.

3.4 信息素更新

本文利用式(14)～(16)對客戶i和j路徑上的信息素進(jìn)行更新:

τij=(1-ρ)τij+Δτij

(14)

(15)

(16)

3.5 算法步驟

步驟3所有客戶服務(wù)結(jié)束后,螞蟻k完成一次周游,得到問題的一個可行解.更新螞蟻數(shù)k=k+1,若k≤Num,轉(zhuǎn)步驟2;否則,轉(zhuǎn)步驟4.

步驟4計(jì)算各螞蟻的目標(biāo)函數(shù)值zk(k=1,2,…,Num),并記錄當(dāng)前最滿意的解.

步驟5根據(jù)信息素更新規(guī)則,利用式(14)～(16)對信息素進(jìn)行更新.

步驟6應(yīng)用量子旋轉(zhuǎn)門對所有客戶點(diǎn)的量子信息進(jìn)行更新.

步驟8若迭代次數(shù)t

步驟9輸出當(dāng)前最優(yōu)解.

4 算例分析

本文采用文獻(xiàn)[14]的算例測試QACO的優(yōu)化性能和MTVRPSDP模型(1)～(9)的可行性與實(shí)用性.該算例為:某第三方物流企業(yè)需要利用一定數(shù)量的車輛和配送人員為100個客戶提供同時送貨和取貨的服務(wù),配送中心(用0表示)的位置坐標(biāo)為(34,36)(單位km),配送中心的送貨需求量di和取貨需求量gi均為0 t;100個客戶的位置坐標(biāo),送貨需求量和取貨需求量如表1所示(見下頁);配送中心提供的配送車輛的車型相同,平均運(yùn)行速度均為35 km/h,最大裝載容量均為10 t,最長工作時間均為8 h.

利用Matlab R2010a 對基本ACO和QACO算法進(jìn)行編程實(shí)現(xiàn),2種算法在Intel Core i5 3.40 GHz,4 GB內(nèi)存,操作系統(tǒng)為Windows7的環(huán)境下運(yùn)行.

為了確保算法之間的可比性,使基本ACO和QACO在相同的起點(diǎn)上進(jìn)行比較,根據(jù)文獻(xiàn)[14]對ACO和QACO的共同參數(shù)設(shè)定了相同的值:螞蟻數(shù)Num=60,距離成本系數(shù)fk=10元/km,車輛啟動成本系數(shù)hk=2 500元,客戶點(diǎn)的裝卸時間sti=0.1h,配送中心的裝貨(卸貨)時間st0=0.1h,信息素軌跡的相對重要性α=1,能見度的相對重要性β=1,量子信息強(qiáng)度的相對重要性μ=2,送取貨物差值的重要性λ=2,節(jié)省量的重要性ξ=1.5,信息素總量Q=15,算法迭代次數(shù)tmax=200.量子蟻群算法中的初始旋轉(zhuǎn)角度θ0=0.06π.QACO算法和基本ACO算法各隨機(jī)運(yùn)行10次,求解結(jié)果如表2所示(見下頁).基本ACO算法求出的車輛數(shù)為5,車輛行駛成本為12 047元,總成本為24 547元.QACO算法求出的車輛數(shù)也為5,車輛行駛成本為9 285.4元,總成本為21 785.4元.QACO求解結(jié)果的標(biāo)準(zhǔn)差為0.67,小于ACO求解結(jié)果的標(biāo)準(zhǔn)差為2.29,這說明QACO的求解性能比ACO的求解性能穩(wěn)定.雖然QACO與ACO求得相同的車輛數(shù),但QACO求解的平均成本和總成本分別為22 129.8元和21 785.4元,分別小于ACO求得的平均成本24 984元和總成本24 547元.這說明本文設(shè)計(jì)的QACO算法求解MTVRPSDP的求解結(jié)果優(yōu)于基本ACO算法的求解結(jié)果.

表1 客戶數(shù)據(jù)Tab.1 Data of clients

表2 量子蟻群算法與蟻群算法效果比較Tab.2 Comparison of the quantum-inspired ant colony algorithm with the basic ant colony algorithm

圖1為ACO和QACO算法求解滿意解的總成本收斂圖.由圖1可知,ACO算法和QACO算法迭代100次已基本趨于收斂.雖然算法迭代開始時,ACO的計(jì)算結(jié)果優(yōu)于QACO的計(jì)算結(jié)果,但迭代大約50次以后QACO的計(jì)算結(jié)果優(yōu)于ACO的計(jì)算結(jié)果.此外,由于QACO中轉(zhuǎn)移概率的計(jì)算和客戶點(diǎn)量子信息的計(jì)算比ACO中的計(jì)算過程繁雜,導(dǎo)致QACO迭代200次的總計(jì)算時間224 s多于ACO的計(jì)算時間206 s,但QACO收斂到滿意解的速度比ACO收斂到滿意解的速度快.

表3給出了本文和文獻(xiàn)[14]利用不同的模型和算法求解該算例的結(jié)果.文獻(xiàn)[14]所建立的MTVRPSDP模型為二次規(guī)劃模型,所采用的求解方法是允許不可行解的禁忌搜索法,模型和算法均與本文的模型和算法不同.將本文計(jì)算結(jié)果與文獻(xiàn)[14]的計(jì)算結(jié)果進(jìn)行對比,發(fā)現(xiàn):雖然本文QACO求解式(1)～(9)獲得的車輛數(shù)與文獻(xiàn)[14]中利用允許不可行解的禁忌搜索法求解得到的車輛數(shù)相同,均為5輛車;但是,文獻(xiàn)[14]共有10條配送路徑,每輛車完成2條路線的配送任務(wù),而本文算法求得的解共有12條配送路線,有2輛車的配送路線數(shù)為3,其余3輛車的配送路線數(shù)為2,不僅完成送貨和取貨任務(wù)的總行駛距離928.54 km優(yōu)于文獻(xiàn)[14]的總行駛距離940.66 km,而且車輛工作總時間37.16 h優(yōu)于文獻(xiàn)[14]的工作總時間38.88 h.本文所計(jì)算的結(jié)果提高了車輛在單位時間內(nèi)完成送貨和取貨的任務(wù)量,即提高了車輛的服務(wù)效率.這說明本文所建立的MTVRPSDP線性整數(shù)規(guī)劃模型和設(shè)計(jì)的QACO算法在實(shí)際應(yīng)用中均是可行的,且有一定的優(yōu)越性,能夠?yàn)樗蠼獾膯栴}找到較好的滿意解.

圖1 QACO和ACO迭代趨勢對比Fig.1 Comparison between the iteration convergences of QACO and ACO

表3 本文計(jì)算結(jié)果與文獻(xiàn)[14]計(jì)算結(jié)果比較Tab.3 Comparison of results obtained in the paper with the ones shown in literature [14]

QACO求得的配送路線圖如圖2所示(見下頁),共12條配送路線.車輛1為2條配送路線的客戶提供服務(wù),2條配送路線分別為:0-2-24-4-26-96-48-51-95-53-58-59-0;0-99-28-70-93-94-27-5-7-8-0;車輛2為2條配送路線的客戶提供服務(wù),2條配送路線分別為:0-79-1-32-84-85-66-49-77-0,0-62-17-20-40-30-76-81-75-45-44-88-80-11-0;車輛3為3條配送路線的客戶提供服務(wù),3條配送路線分別為:0-16-54-56-52-57-97-67-12-0,0-14-31-83-0,0-63-68-23-55-69-15-18-92-0;車輛4為3條配送路線的客戶提供服務(wù),3條配送路線分別為:0-36-22-78-90-86-0,0-41-98-72-21-73-100-42-0,0-37-3-25-47-60-71-0;車輛5為2條配送路線的客戶提供服務(wù),2條配送路線分別為:0-87-6-46-9-74-29-50-0,0-38-10-61-19-91-43-89-13-39-34-64-65-35-0.

圖2 配送方案路徑圖Fig.2 Distribution routes

5 結(jié) 論

MTVRPSDP的研究對物流公司的配送服務(wù)具有十分重要的現(xiàn)實(shí)意義.根據(jù)現(xiàn)實(shí)生活中配送車輛具有工作時間和載重量限制的特點(diǎn),本文建立了更符合實(shí)際應(yīng)用且考慮了裝卸貨物時間的MTVRPSDP線性整數(shù)規(guī)劃模型.然后,將量子計(jì)算中的量子比特和量子旋轉(zhuǎn)門引入ACO,在每個客戶點(diǎn)設(shè)置了量子信息,用其改進(jìn)螞蟻的狀態(tài)轉(zhuǎn)移規(guī)則,設(shè)計(jì)了求解該問題的QACO算法.求解測試算例表明:本文所設(shè)計(jì)的MTVRPSDP線性整數(shù)規(guī)劃模型在實(shí)際應(yīng)用中是可行和有效的;此外,本文所設(shè)計(jì)的QACO算法能夠有效求解MTVRPSDP的線性整數(shù)規(guī)劃模型,具有較高的穩(wěn)定性.

本文所設(shè)計(jì)的MTVRPSDP模型并未考慮客戶對送貨和取貨服務(wù)的時間窗的限制和滿意度,也未將物流公司完成配送和取貨任務(wù)所啟動的車輛數(shù)、行駛路徑總成本作為優(yōu)化的多個目標(biāo).建立并求解帶有時間窗限制的多目標(biāo)多車次同時取送貨物的車輛路徑問題模型將是作者下一步的研究工作.

[1] MIN H.The multiple vehicle routing problem with simultaneous delivery and pick-up points[J].Transportation Research Part A:General,1989,23(5):377-386.

[2] DETHLOFF J.Vehicle routing and reverse logistics:the vehicle routing problem with simultaneous delivery and pick-up[J].OR-Spektrum,2001,23(1):79-96.

[3] 張濤,余綽婭,劉嵐,等.同時送取貨的隨機(jī)旅行時間車輛路徑問題方法[J].系統(tǒng)工程理論與實(shí)踐,2011,31(10):1912-1920.

[4] LIU R,XIE X L,AUGUSTO V,et al.Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care[J].European Journal of Operational Research,2013,230(3):475-486.

[5] MONTANé F A T,GALVO R D.A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service[J].Computers & Operations Research,2006,33(3):595-619.

[6] QU Y,BARD J F.The heterogeneous pickup and delivery problem with configurable vehicle capacity[J].Transportation Research Part C:Emerging Technologies,2013,32:1-20.

[7] 田宇,伍煒勤.求解異車型同時集送問題的多屬性標(biāo)簽算法[J].系統(tǒng)工程理論與實(shí)踐,2015,35(1):183-190.

[8] 張建勇,李軍.具有同時配送和回收需求的車輛路徑問題的混合遺傳算法[J].中國公路學(xué)報,2006,19(4):118-122.

[9] 吳斌,錢存華,董敏,等.具有同時集送貨需求車輛路徑問題的混沌量子進(jìn)化算法研究[J].控制與決策,2010,25(3):383-388.

[10] DORIGO M,BONABEAU E,THERAULAZ G.Ant algorithms and stigmergy[J].Future Generation Computer Systems,2000,16(8):851-871.

[11] 李婭,王東.基于混沌擾動和鄰域交換的蟻群算法求解車輛路徑問題[J].計(jì)算機(jī)應(yīng)用,2012,32(2):444-447.

[12] 何小鋒,馬良.帶時間窗車輛路徑問題的量子蟻群算法[J].系統(tǒng)工程理論與實(shí)踐,2013,33(5):1255-1261.

[13] LI B B,WANG L.A hybrid quantum-inspired genetic algorithm for multiobjective flow shop scheduling[J].IEEE Transactions on Systems,Man,and Cybernetics,Part B (Cybernetics),2007,37(3):576-591.

[14] 李建,達(dá)慶利,何瑞銀.多車次同時集散貨物路線問題研究[J].管理科學(xué)學(xué)報,2010,13(10):1-7.