多車次同時送取貨物車輛路徑問題的量子蟻群算法

,

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

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

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

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

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

2.1 問題描述

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

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

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

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

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

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

決策變量:

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

目標函數(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)

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

3 MTVRPSDP的量子蟻群算法

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

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

3.1 量子編碼特性

量子計算的基本原理是使量子態(tài)所處疊加態(tài)的各個基態(tài)間的相對相位和概率幅度發(fā)生改變,使各個基態(tài)的發(fā)生概率產(chǎn)生變化,從而使其疊加態(tài)發(fā)生變化,具有并行、疊加、干涉等特征[12].量子比特是量子計算中基本信息的存儲單元,采用|0〉和|1〉(“|〉”稱為Dirac記號,在量子力學中表示狀態(tài))來表示微觀粒子的兩種基本狀態(tài).單量子比特的任意狀態(tài)都可以表示為這兩個基本狀態(tài)的線性組合,即除|0〉和|1〉之外,還可以是這兩種狀態(tài)之間的中間狀態(tài)(疊加態(tài)):|φ〉=α|0〉+β|1〉(α和β是一對復數(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中用量子比特來表示量子信息素,設種群大小為n,其量子信息素用量子位表示為p=(p1,p2,…,pn),其中pj(j=1,2,…,n)如式(10)所示.

3.2 量子旋轉(zhuǎn)門

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

(11)

本文針對MTVRPSDP的求解和借鑒文獻[12]中量子旋轉(zhuǎn)角的取值方法,設計了一種改進的θi取值方法,該方法能夠根據(jù)當前量子比特概率幅和MTVRPSDP問題的目標函數(shù)值計算出相位的旋轉(zhuǎn)角度,從而實現(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ù),自適應地調(diào)整旋轉(zhuǎn)角的大小.當f(xi)-f(bi)>0時,sign(f(xi)-f(bi))=1;當f(xi)-f(bi)<0時,sign(f(xi)-f(bi))=-1;當f(xi)-f(bi)=0時,則sign(f(xi)-f(bi))=0.θ0為初始旋轉(zhuǎn)角度,xi表示當前解,bi表示當前最優(yōu)解,f(x)為目標函數(shù).

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

(13)

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

3.4 信息素更新

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

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

(14)

(15)

(16)

3.5 算法步驟

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

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

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

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

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

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

4 算例分析

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

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

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

表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的計算結果優(yōu)于QACO的計算結果,但迭代大約50次以后QACO的計算結果優(yōu)于ACO的計算結果.此外,由于QACO中轉(zhuǎn)移概率的計算和客戶點量子信息的計算比ACO中的計算過程繁雜,導致QACO迭代200次的總計算時間224 s多于ACO的計算時間206 s,但QACO收斂到滿意解的速度比ACO收斂到滿意解的速度快.

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

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

表3 本文計算結果與文獻[14]計算結果比較Tab.3 Comparison of results obtained in the paper with the ones shown in literature [14]

QACO求得的配送路線圖如圖2所示(見下頁),共12條配送路線.車輛1為2條配送路線的客戶提供服務,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條配送路線的客戶提供服務,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條配送路線的客戶提供服務,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條配送路線的客戶提供服務,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條配送路線的客戶提供服務,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 結 論

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

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

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

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

[9] 吳斌,錢存華,董敏,等.具有同時集送貨需求車輛路徑問題的混沌量子進化算法研究[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].計算機應用,2012,32(2):444-447.

[12] 何小鋒,馬良.帶時間窗車輛路徑問題的量子蟻群算法[J].系統(tǒng)工程理論與實踐,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] 李建,達慶利,何瑞銀.多車次同時集散貨物路線問題研究[J].管理科學學報,2010,13(10):1-7.