蟻群算法求解帶有時(shí)間約束旅行商問(wèn)題

李安穎,陳 群,宋 荷

(西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院,陜西 西安 710072)

0 引言

隨著線(xiàn)上線(xiàn)下(online to offline，O2O)商業(yè)模式發(fā)展迅速，對(duì)物流配送的要求越來(lái)越高。物流配送已成為O2O服務(wù)中的一個(gè)重要環(huán)節(jié)[1]，其服務(wù)質(zhì)量對(duì)提高O2O企業(yè)的競(jìng)爭(zhēng)力具有重要意義。當(dāng)前，物流企業(yè)一般提供的是由客戶(hù)下單時(shí)預(yù)先設(shè)定的貨物送達(dá)時(shí)間，進(jìn)而在該設(shè)定的時(shí)間段內(nèi)實(shí)現(xiàn)配送服務(wù)。為了實(shí)現(xiàn)快速、有效的配送，可以將問(wèn)題轉(zhuǎn)化為含時(shí)間約束的旅行商問(wèn)題(traveling salesman problem,TSP)[2-3]。TSP其實(shí)是一個(gè)多項(xiàng)式復(fù)雜程度的非確定性問(wèn)題(non-deterministic polynomial,NP)，常用粒子群算法、遺傳算法、蟻群算法等智能算法來(lái)解決。但是使用這些傳統(tǒng)的智能算法，存在運(yùn)行時(shí)間較長(zhǎng)、求解效率低的問(wèn)題。本文采用以MapReduce為基礎(chǔ)的蟻群算法，從而更為高效地解決物流配送順序的帶時(shí)間約束TSP。

Hadoop框架是由Apache開(kāi)源組織開(kāi)發(fā)的、具有高可靠性、高可擴(kuò)展性的存儲(chǔ)與分布式并行計(jì)算平臺(tái)[4]。MapReduce是Hadoop框架的核心模型之一，已經(jīng)廣泛應(yīng)用于大數(shù)據(jù)處理、分布式計(jì)算等[5]。本文使用MapReduce實(shí)現(xiàn)蟻群算法以及高效求解帶時(shí)間約束的TSP，從而快速地給出對(duì)含時(shí)間約束的物流配送問(wèn)題的有效解決方案[6-8]。目前，對(duì)于基于MapReduce的蟻群算法進(jìn)行求解傳統(tǒng)的TSP已經(jīng)有比較好的闡述，但是對(duì)于含時(shí)間約束的TSP，尚未有相關(guān)文獻(xiàn)對(duì)其進(jìn)行詳細(xì)分析。

1 問(wèn)題描述及構(gòu)建模型

傳統(tǒng)TSP是假設(shè)一個(gè)貨郎需要走訪(fǎng)N個(gè)城市，每個(gè)城市必須且僅經(jīng)過(guò)一次，最終回到起點(diǎn)城市，形成閉環(huán)。因此，必須找到一條最短的旅行路徑。

假設(shè)物流配送的客戶(hù)集為U={u1,u2,…,ui,…,un}，1≤i≤n。當(dāng)前時(shí)間為T(mén)0,配送員配送過(guò)程中的速度為v,到達(dá)客戶(hù)ui的時(shí)間為T(mén)i；客戶(hù)ui預(yù)定的配送時(shí)間在Ti1到之間，記為[Ti1-Ti2]，對(duì)于未約定配送時(shí)間的客戶(hù)，其配送時(shí)間設(shè)置為(-∞,+∞)。為了提高客戶(hù)滿(mǎn)意度，如果Ti?[Ti1-Ti2]，即未能在客戶(hù)約定的時(shí)間內(nèi)到達(dá)城市i，則設(shè)置懲罰值wi。不考慮配送員在每個(gè)節(jié)點(diǎn)上提留的時(shí)間，懲罰值可定義如下：

(1)

式中：εv為懲罰因子。該值為經(jīng)驗(yàn)值。在計(jì)算過(guò)程中，通過(guò)將該懲罰值wi增加到路徑開(kāi)銷(xiāo)中，可以將客戶(hù)ui的時(shí)間約束轉(zhuǎn)化為路徑約束Li。

假設(shè)物流配送人員訪(fǎng)問(wèn)的節(jié)點(diǎn)順序?yàn)閄={x1,x2，…,.xi,…,xn}，0≤xi≤N。xi表示物流配送人員到達(dá)的第i個(gè)節(jié)點(diǎn)。則該路徑對(duì)應(yīng)總路徑長(zhǎng)度為：

(2)

式中：d(xi,xi+1)為總路徑中第i個(gè)、第(i+1)個(gè)節(jié)點(diǎn)之間的距離。

整個(gè)路徑上的懲罰值為：

(3)

式中：w(xi)為總路徑上第i個(gè)節(jié)點(diǎn)所對(duì)應(yīng)的客戶(hù)節(jié)點(diǎn)的懲罰值wi。

可構(gòu)建目標(biāo)函數(shù)為路徑值與懲罰值的總和：

C=L+W

(4)

本文求解的最終目標(biāo)是尋找目標(biāo)函數(shù)的最小值，實(shí)現(xiàn)路徑最優(yōu)化與懲罰值最小。

2 改進(jìn)的蟻群算法

蟻群算法 (ant system或ant colony system)由意大利學(xué)者Dorigo、Maniezzo等人于20世紀(jì)90年代提出。使用該算法解決優(yōu)化配送路徑問(wèn)題的基本思路為：用螞蟻的行走路徑表示待優(yōu)化路徑問(wèn)題的可能解，整個(gè)螞蟻群體的所有路徑構(gòu)成待優(yōu)化問(wèn)題的解空間。路徑較短的螞蟻釋放的信息素(模擬螞蟻會(huì)在其經(jīng)過(guò)的路徑上釋放的物質(zhì)，能使得螞蟻根據(jù)感知到的信息素濃度行走)量較多。隨著時(shí)間的演化，較短路徑上累積的信息素濃度逐漸增高，選擇該路徑的螞蟻個(gè)數(shù)也將約來(lái)越多。最終，每個(gè)螞蟻會(huì)在這種正反饋的作用下集中到最佳的路徑上。此時(shí)對(duì)應(yīng)的路徑便是待優(yōu)化問(wèn)題的最優(yōu)解。

本文在傳統(tǒng)的蟻群算法基礎(chǔ)上進(jìn)行改進(jìn)。因此，求解含時(shí)間約束的TSP算法詳述如下。

2.1 參數(shù)說(shuō)明

設(shè)m為本算法中的螞蟻數(shù)目，di,j(i,j=1,2,…,n)表示從ui用戶(hù)到用戶(hù)uj之間的距離，τi,j(t)表示時(shí)刻t在用戶(hù)i、j之間的路徑上保留的信息素。將每條路徑上初始時(shí)刻的信息素設(shè)為τi,j(0)=c。在運(yùn)動(dòng)過(guò)程中，螞蟻k(k=1,2,…，m)根據(jù)各個(gè)路徑上的信息素確定下一步待轉(zhuǎn)移的目標(biāo)用戶(hù)；S表示在t時(shí)刻，螞蟻k轉(zhuǎn)移到用戶(hù)uj的概率。

(5)

2.2 蟻群算法信息素改良機(jī)制

將信息素強(qiáng)度的值進(jìn)行限定在范圍[τmin,τmax]內(nèi)，不在這個(gè)范圍內(nèi)的最小值與最大值分別設(shè)為τmin或τmax。限制最大值的目的是防止算法陷入局部最優(yōu)解；限制最小值的目的是防止搜索向錯(cuò)誤的方向收斂。

當(dāng)τij>τmax時(shí)，按式(6)計(jì)算信息素強(qiáng)度：

τij(t+1)=(1-α1)1+s(m)τij(t)+Δτij

(6)

當(dāng)τij﹤τmin時(shí)，按式(7)計(jì)算信息素強(qiáng)度：

τij(t+1)=(1-α1)1-s(m)τij(t)+Δτij

(7)

當(dāng)τmin≤τij≤τmax時(shí)，按式(8)計(jì)算信息素強(qiáng)度：

τij(t+1)=(1-α1)τij(t)+Δτij

(8)

式中：α1為揮發(fā)因子，表示信息素的保留率；Δτij為示信息素的增加量；s(m)為與迭代過(guò)程中被改進(jìn)的解的個(gè)數(shù)m成正比的函數(shù)。

2.3 局部信息素更新機(jī)制

在采用局部信息素更新規(guī)則來(lái)修正信息素值時(shí)，螞蟻k對(duì)其走過(guò)的每條路徑，參照式(6)～式(8)來(lái)更新邊上保留的局部信息素值。

當(dāng)0<α1<1時(shí)，信息素?fù)]發(fā)參數(shù)：

Δτij=(ngLnn)-1

(9)

式中：Lnn為由最近鄰域啟發(fā)算法計(jì)算出的路徑長(zhǎng)度。

2.4 全局信息素更新機(jī)制

對(duì)于應(yīng)用全局信息素更新規(guī)則來(lái)修正信息素值時(shí)，考慮在一次迭代的過(guò)程中，m個(gè)螞蟻生成m個(gè)解后，計(jì)算該求解過(guò)程中的最短路徑，作為本次迭代的最優(yōu)解。將這條路徑上所有保留的信息素按照式(10)更新：

τ(t+1)=(1-α)τ(t)+αΔτ(t)

(10)

當(dāng)0<α<1時(shí)，信息素?fù)]發(fā)系數(shù)為：

(11)

式中：Lgb為當(dāng)前得到的全局最優(yōu)解的路線(xiàn)長(zhǎng)度。

隨著信息素的揮發(fā)，全局最短路線(xiàn)上各邊上的信息素值得到增加。

3 基于MapReduce的蟻群算法的實(shí)現(xiàn)

使用MapReduce方法求解本問(wèn)題的思路如下：在Map函數(shù)中初始化，設(shè)置蟻群，利用多個(gè)Map函數(shù)并行計(jì)算螞蟻的求解過(guò)程，獲得多個(gè)可行解，并在Map函數(shù)中設(shè)置局部信息素矩陣，對(duì)局部信息素進(jìn)行更新。

首先，讀入待處理文件中記錄的數(shù)據(jù)，并設(shè)置m個(gè)Map，每個(gè)Map中設(shè)置n個(gè)螞蟻，并以鍵值對(duì)的形式輸出，key代表蟻群編號(hào)，value的形式為{X={x1,x2,…,xi,…xn}}，該Map計(jì)算得到的最優(yōu)解的路徑長(zhǎng)度}。在Reduce函數(shù)中設(shè)置全局信息素矩陣為：

Pn×n=|pij|

(12)

式中：pij為用戶(hù)ui到用戶(hù)uj之間的全局信息素，1≤i,j≤n。

利用Reduce函數(shù)，求得全局最優(yōu)解和調(diào)整全局信息素。然后，利用云計(jì)算的管道能力，將Reduce函數(shù)的計(jì)算結(jié)果，即信息素的改變、全局最優(yōu)解、全局最優(yōu)解路徑，傳遞到Map函數(shù)，作為下一個(gè)Map函數(shù)的輸入，執(zhí)行迭代計(jì)算。使用的蟻群算法最終改進(jìn)如下。

①初始化。

{1-1：構(gòu)造Map函數(shù)、Reduce函數(shù)，設(shè)置Map函數(shù)的個(gè)數(shù)NUM_MAP、Reduce函數(shù)的個(gè)數(shù)NUM_REDUCE，初始化局部信息素矩陣、全局信息素矩陣；

1-2：設(shè)置每個(gè)Map函數(shù)中的螞蟻數(shù)，螞蟻算法運(yùn)行代數(shù)為no_iteration}

②對(duì)每個(gè)Map函數(shù)中的每只螞蟻隨機(jī)產(chǎn)生一個(gè)初始解：

{X={x1,…xi,…xn}}

③更新信息素。

{3-1：每個(gè)Map節(jié)點(diǎn)分別根據(jù)式(1)～式(4)計(jì)算本節(jié)點(diǎn)下各個(gè)螞蟻的解;

3-2：根據(jù)式(9)更新每個(gè)螞蟻的局部信息素以及局部最優(yōu)解。}

④調(diào)整信息素。

{4-1：將Map獲得的各個(gè)螞蟻分配到各個(gè)Reduce節(jié)點(diǎn)中;

4-2：通過(guò)Reduce函數(shù)計(jì)算全局最優(yōu)解;

4-3：根據(jù)式(10)調(diào)整全局解向量的信息素。}

⑤本次迭代結(jié)束。

{if 迭代次數(shù) => no_ iteration

算法結(jié)束；

Else 將全局最優(yōu)解信息更新到所有的Map節(jié)點(diǎn)中}

4 試驗(yàn)

為了對(duì)以上理論進(jìn)行驗(yàn)證，試驗(yàn)環(huán)境搭建如下。采用4臺(tái)普通的服務(wù)器進(jìn)行搭建的Hadoop集群系統(tǒng)試驗(yàn)，每臺(tái)服務(wù)器內(nèi)存2 GB，存儲(chǔ)空間250 GB。Hadoop的版本是hadoop.0.20.2。操作系統(tǒng)的版本是Red Hat Linux 9.0。測(cè)試方法是在Hadoop的框架下進(jìn)行計(jì)算。以TSP標(biāo)準(zhǔn)測(cè)試集中的數(shù)據(jù)gr431為例，設(shè)置物流配送人員的配送時(shí)間段為[9：00-21：00]，在該時(shí)間段內(nèi)以?xún)蓚€(gè)小時(shí)為一個(gè)預(yù)約時(shí)間段，隨機(jī)設(shè)置預(yù)約配送時(shí)間，求解了運(yùn)算結(jié)果。另外，還比較了TSP節(jié)點(diǎn)數(shù)分別為48、120、229、431時(shí)，基于MapReduce的蟻群算法(記為并行)與串行的蟻群算法(即未使用分布式算法的蟻群算法)的運(yùn)行時(shí)間。蟻群算法與串行蟻群算法的運(yùn)行時(shí)間對(duì)比如表1所示。

表1 并行蟻群算法與串行蟻群算法的運(yùn)行時(shí)間對(duì)比

經(jīng)過(guò)多次反復(fù)試驗(yàn)，程序中用到的參數(shù)設(shè)置為ρ=0.1、α=0.7、β=0.1、θ=0.4比較合理，能夠得到較好的試驗(yàn)結(jié)果。設(shè)置Map數(shù)m=4，每個(gè)Map上的螞蟻數(shù)n=200，車(chē)速為60 km/h。又以TSP標(biāo)準(zhǔn)測(cè)試集中的數(shù)據(jù)gr431為例，比較了螞蟻數(shù)不同時(shí)對(duì)運(yùn)算時(shí)間的影響。

運(yùn)行時(shí)間1 800 s，運(yùn)行的解路徑長(zhǎng)度為221 827.78。

如圖1所示，當(dāng) TSP 節(jié)點(diǎn)數(shù)為 48 和 120 時(shí)，并行算法的運(yùn)行時(shí)間大于串行算法；當(dāng)TSP節(jié)點(diǎn)數(shù)為229和431時(shí)，并行算法運(yùn)行的時(shí)間小于串行算法所需的時(shí)間。隨著TSP節(jié)點(diǎn)數(shù)增多，并行算法運(yùn)行時(shí)間比串行算法更短時(shí)間的趨勢(shì)。不同螞蟻數(shù)的運(yùn)算時(shí)間對(duì)比如圖1所示。

圖1 不同螞蟻數(shù)的運(yùn)算時(shí)間對(duì)比圖

從圖1中的結(jié)果可以看出，隨著螞蟻數(shù)量的增加，運(yùn)行時(shí)間有縮短的趨勢(shì)。

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

本文采用基于MapReduce的蟻群算法求解包含時(shí)間約束的TSP，用螞蟻的行走路徑表示待優(yōu)化路徑問(wèn)題的可能解，整個(gè)螞蟻群體的所有路徑構(gòu)成待優(yōu)化問(wèn)題的解空間；利用MapReduce的并行機(jī)制，對(duì)蟻群算法進(jìn)行并行處理，使其運(yùn)行在分布式環(huán)境中，增強(qiáng)了求解大規(guī)模問(wèn)題的能力，提高了運(yùn)行速度。試驗(yàn)結(jié)果表明，該算法有效。后續(xù)的工作將探索結(jié)合多種智能算法解決帶有復(fù)雜約束的NP問(wèn)題。