包曉光, 焦長(zhǎng)春

(上海海洋大學(xué) 信息學(xué)院,上海 201306)

0 引言

本文研究線型/圈型網(wǎng)絡(luò)上單臺(tái)車輛分群調(diào)度問題。給定一個(gè)線型/圈型網(wǎng)絡(luò)，若干個(gè)待服務(wù)的客戶分布其中。所有客戶被劃分成若干個(gè)子集，每個(gè)子集稱為一個(gè)群。給定一臺(tái)車輛，其初始時(shí)位于網(wǎng)絡(luò)中的某處，它需要服務(wù)所有客戶，且每個(gè)群內(nèi)的客戶連續(xù)服務(wù)。每個(gè)客戶有一個(gè)釋放時(shí)間和一個(gè)服務(wù)時(shí)間。釋放時(shí)間的含義是車輛只能在該時(shí)刻之后才能對(duì)客戶進(jìn)行服務(wù)，而服務(wù)時(shí)間則是車輛對(duì)其進(jìn)行服務(wù)時(shí)需花費(fèi)一定的服務(wù)時(shí)間。同時(shí)，車輛在每?jī)蓚€(gè)客戶之間移動(dòng)亦需花費(fèi)一定的旅行時(shí)間。問題的要求是計(jì)算一個(gè)時(shí)間表，使得車輛能夠按要求服務(wù)完所有客戶并返回初始出發(fā)位置所花費(fèi)的時(shí)間最少。車輛分群調(diào)度問題是運(yùn)籌學(xué)和計(jì)算機(jī)科學(xué)中一個(gè)重要的組合優(yōu)化問題，它和它的變形在諸如交通運(yùn)輸、生產(chǎn)制造、生物科學(xué)等相關(guān)行業(yè)具有廣泛應(yīng)用[1]。

在車輛分群調(diào)度問題中，若客戶的釋放時(shí)間和服務(wù)時(shí)間均為零，則對(duì)應(yīng)的問題稱為分群旅行商問題(Clustered Traveling Salesman Problem，CTSP)。就CTSP問題，Guttmann等[2]給出了一個(gè)11/4近似算法，Bao和Liu[3]進(jìn)一步給出了一個(gè)13/6近似算法。

在車輛分群調(diào)度問題中，若群的個(gè)數(shù)等于1，則對(duì)應(yīng)的問題稱為車輛調(diào)度問題(Vehicle Scheduling Problem，VSP)。就線型網(wǎng)絡(luò)上的VSP問題，Tsitsiklis[4]證明了它是NP困難問題，Bhattacharya等[5]，Yu和Liu[6]分別獨(dú)立給出了一個(gè)3/2近似算法。就圈型網(wǎng)絡(luò)上的VSP問題，若圈中存在一條長(zhǎng)度超過圈長(zhǎng)一半的邊時(shí)，其可以轉(zhuǎn)化為線型網(wǎng)絡(luò)上的VSP問題，即其仍是NP困難問題，Wu和Lu[7]給出了一個(gè)5/3近似算法。就樹型網(wǎng)絡(luò)上的VSP問題，因線型網(wǎng)絡(luò)上的VSP問題是其特例，故其亦是NP困難問題，Wu和Lu[7]給出了一個(gè)16/9近似算法。就一般網(wǎng)絡(luò)上的VSP問題，Nagamochi等[8]給出了一個(gè)5/2近似算法。

本文研究線型網(wǎng)絡(luò)和圈型網(wǎng)絡(luò)上單臺(tái)車輛分群調(diào)度問題。因它們是相應(yīng)VSP問題的推廣情形，故均是NP困難問題。針對(duì)這兩個(gè)問題，我們分別給出了一個(gè)7/4和一個(gè)13/7近似算法。本文余下內(nèi)容安排如下：第1節(jié)給出問題的數(shù)學(xué)描述和將在后文使用的一些符號(hào)；第2和3節(jié)分別考慮線型網(wǎng)絡(luò)和圈型網(wǎng)絡(luò)上的該問題。

1 問題描述和符號(hào)

設(shè)G=(V,E)是一個(gè)線型(圈型)網(wǎng)絡(luò)，其中V={0,1,2,…,n-1}是該網(wǎng)絡(luò)的頂點(diǎn)集，E={(i,j)}是該網(wǎng)絡(luò)的邊集。初始時(shí)，有一臺(tái)車輛位于h(0≤h≤n-1)處。頂點(diǎn)集Vh的每個(gè)頂點(diǎn)處有一個(gè)客戶，它們被劃分成K個(gè)連續(xù)子集V0,V1,V2,…,VK-1，每個(gè)子集Vi稱為一個(gè)群。每個(gè)客戶有一個(gè)釋放時(shí)間ri，它的含義是車輛只能在時(shí)刻ri后服務(wù)該客戶。每個(gè)客戶有一個(gè)服務(wù)時(shí)間pi，它的含義是機(jī)器在服務(wù)該客戶時(shí)需花費(fèi)pi個(gè)時(shí)間單位。邊集E中的每條邊e=(i,j)關(guān)聯(lián)一個(gè)車輛的旅行時(shí)間t(i,j)。旅行時(shí)間是對(duì)稱的，即對(duì)任意e=(i,j)∈E，成立t(i,j)=t(j,i)。車輛分群調(diào)度問題的目標(biāo)是，計(jì)算一個(gè)客戶服務(wù)順序的時(shí)間表，要求車輛從初始位置出發(fā)，服務(wù)完所有客戶且每個(gè)群內(nèi)的客戶連續(xù)服務(wù)，使得其最終返回初始出發(fā)位置所花費(fèi)的時(shí)間最少。

給定一個(gè)時(shí)間表S，我們用Cmax(S)表示其時(shí)間表長(zhǎng)。同時(shí)，我們另外定義一些將在后文使用的符號(hào)。

符號(hào)含義P=∑i∈Vhpi所有客戶的服務(wù)時(shí)間之和;rmax=maxi∈Vhri所有客戶的最大釋放時(shí)間;t(G)=∑(i,j)∈Et(i,j)網(wǎng)絡(luò)圖G的每條邊的旅行時(shí)間之和;0?t?rmaxV(t)={l|?i∈Vl,ri?t}存在釋放時(shí)間大于等于t的客戶的群的集合;V′(t)={l|?i∈Vl,ri>t}存在釋放時(shí)間嚴(yán)格大于t的客戶的群的集合;P(t)=∑{i|i∈Vl,l∈V(t)}piV(t)中客戶的服務(wù)時(shí)間之和;P′(t)=∑{i|i∈Vl,l∈V′(t)}piV′(t)中客戶的服務(wù)時(shí)間之和;Q(t)=maxl∈V(t)∑{i|i∈Vl,ri

2 線型網(wǎng)絡(luò)

本節(jié)考慮線型網(wǎng)絡(luò)上單臺(tái)車輛分群調(diào)度問題。給定一個(gè)線型網(wǎng)絡(luò)G=(V,E)，不失一般性，我們假設(shè)V={0,1,2,…,n-1}中的頂點(diǎn)從左至右按遞增序排列，頂點(diǎn)分群示意圖見圖1。注意車輛初始出發(fā)位置h不在任何一個(gè)子集(群)中。

圖1 線型網(wǎng)絡(luò)頂點(diǎn)劃分示意圖

針對(duì)該問題的一種更一般的情形，即h可以處于某個(gè)子集(群)中，包曉光等[9]給出了一個(gè)16/9近似算法。針對(duì)本文考慮的情形，即h不在任何一個(gè)子集(群)中，提出一個(gè)7/4近似算法，進(jìn)而就這種情形我們改進(jìn)了求解問題的近似比。兩個(gè)算法的區(qū)別主要在于算法中t*的選擇和車輛的行駛路線上。接下來，我們首先給出算法，然后對(duì)算法進(jìn)行分析。

算法A1

步驟1對(duì)相應(yīng)的零服務(wù)時(shí)間問題，調(diào)用包曉光等[9]的動(dòng)態(tài)規(guī)劃最優(yōu)算法生成時(shí)間表S1，然后按照S1服務(wù)客戶的順序?qū)蛻暨M(jìn)行服務(wù)。

步驟2計(jì)算滿足條件P′(t*)-Q′(t*)≤t*≤P(t*)-Q(t*)的時(shí)刻t*(0≤t*≤rmax)，將群劃分成{0,1,2,…,K-1}V′(t*)和V′(t*)u′(t*)以及{u′(t*)}三部分。依據(jù)Vu′(t*)的位置，構(gòu)造一個(gè)時(shí)間表S2，使得車輛首先在h處等至?xí)r刻t*，然后，若Vu′(t*)位于h的左側(cè)(右側(cè))，則接下來從右至左(從左至右)服務(wù)下標(biāo)屬于{0,1,2,…,K-1}V′(t*)的每個(gè)群，再?gòu)淖笾劣?從右至左)服務(wù)Vu′(t*)中釋放時(shí)間不超過t*的所有客戶，然后從右至左(從左至右)服務(wù)Vu′(t*)中釋放時(shí)間超過t*的所有客戶，最后從左至右(從右至左)服務(wù)V′(t*)u′(t*)中的每個(gè)群。S2中車輛的行駛路線示意圖見圖2(為后面分析方便，假設(shè)Vu′(t*)的左右端頂點(diǎn)分別為u1和u2，V′(t*)u′(t*)中最左(右)端的群為Vl(Vr)，其相應(yīng)的兩個(gè)端頂點(diǎn)分別為l1(r1)和l2(r2))。

步驟3從S1和S2中選擇時(shí)間表長(zhǎng)較小者作為最終的近似解。

圖2 算法A1中群Vu′(t*)位于h左側(cè)時(shí)車輛的行駛路線示意圖

在圖2，①表示在h處等至t*時(shí)刻后行駛至頂點(diǎn)n-1，期間不服務(wù)任何群；②表示從頂點(diǎn)n-1旅行至頂點(diǎn)0，期間服務(wù){(diào)0,1,2,…,K-1}V′(t*)中每個(gè)群；③表示從頂點(diǎn)0旅行至頂點(diǎn)u2，期間服務(wù)Vu′(t*)中釋放時(shí)間不超過t*的所有客戶；④表示從頂點(diǎn)u2旅行至頂點(diǎn)l1，期間服務(wù)Vu′(t*)中釋放時(shí)間超過t*的所有客戶；⑤表示從頂點(diǎn)l1旅行至頂點(diǎn)r2，期間服務(wù)V′(t*)u′(t*)中的每個(gè)群；⑥表示從頂點(diǎn)r2返回初始出發(fā)位置h。

由于P′(t)-Q′(t)和P(t)-Q(t)是單調(diào)非增的分段常數(shù)函數(shù)，且僅在t=ri處函數(shù)值才有可能不同，故在[0,rmax]范圍內(nèi)一定能找到滿足條件的t*。對(duì)于時(shí)間表S1，由包曉光等[9]知，其可在O(n2)內(nèi)計(jì)算；對(duì)于時(shí)間表S2，類似Yu和Liu[6]的分析知，其主要由計(jì)算t*控制并可在O(nlogn)內(nèi)計(jì)算。因此，算法A1的時(shí)間復(fù)雜度為O(n2)。接下來，在分析算法A1的近似比之前，首先給出幾個(gè)最優(yōu)時(shí)間表長(zhǎng)的下界。

下面在引理2和3分別給出S1和S2的時(shí)間表長(zhǎng)上界。由于S1與包曉光等[9]的相應(yīng)時(shí)間表構(gòu)造相同，故由他們的相應(yīng)結(jié)果可以得出引理2。

綜合引理2和3，我們可以得出本節(jié)的主要結(jié)論：

定理1對(duì)于線型網(wǎng)絡(luò)上單臺(tái)車輛分群調(diào)度問題，算法A1是一個(gè)求解該問題的7/4近似算法。

3 圈型網(wǎng)絡(luò)

本節(jié)考慮圈型網(wǎng)絡(luò)上單臺(tái)車輛分群調(diào)度問題。給定一個(gè)圈型網(wǎng)絡(luò)G=(V,E)，不失一般性，我們假設(shè)V={0,1,2,…,n-1}中的頂點(diǎn)按順時(shí)針方向遞增序排列，頂點(diǎn)分群示意圖見圖3。注意車輛初始出發(fā)位置h不在任何一個(gè)子集(群)中。

圖3 圈型網(wǎng)絡(luò)頂點(diǎn)劃分示意圖

3.1 服務(wù)時(shí)間為零的情形

當(dāng)群的個(gè)數(shù)K=1時(shí)，就圈型網(wǎng)絡(luò)且服務(wù)時(shí)間為零的情形，Nagamochi等[8]給出了一個(gè)時(shí)間復(fù)雜性為O(n2)的動(dòng)態(tài)規(guī)劃最優(yōu)算法。接下來，我們將其推廣到群的個(gè)數(shù)可以任意的情形，進(jìn)而給出一個(gè)求解該情形的O(n2)動(dòng)態(tài)規(guī)劃最優(yōu)算法。首先，我們給出一個(gè)最優(yōu)時(shí)間表的性質(zhì)。

定理2對(duì)于零服務(wù)時(shí)間的圈型網(wǎng)絡(luò)上單臺(tái)車輛分群調(diào)度問題，存在一個(gè)最優(yōu)時(shí)間表，使得在任意時(shí)刻，未服務(wù)的群的集合與h一起誘導(dǎo)的子圖是連通的。

基于定理2，我們給出求解該情形的一個(gè)動(dòng)態(tài)規(guī)劃最優(yōu)算法。為方便起見，設(shè)第i個(gè)群的兩個(gè)端頂點(diǎn)按順時(shí)針方向分別為si和ti，且h位于第m與m+1個(gè)群之間。設(shè)V[i,j]表示按順時(shí)針方向從Vi到Vj的群集合。特別地，令V[i,i]=Vi。設(shè)f-(V[i,i+k])和f+(V[i,i+k])(i=0,1,2,…,K-1;k=K-3,K-2,…,1,0)分別為車輛從h出發(fā)，服務(wù)完群{V0,V1,V2,…,VK-1}V[i,i+k]，且停在ti-1和si+k+1所需的最短時(shí)間。注意，由于網(wǎng)絡(luò)結(jié)構(gòu)是圈型，這里假設(shè)每個(gè)群下標(biāo)都是(mod K)的。因此，成立下面的遞推公式:

當(dāng)i=m+2,m+3,…,m-1,k=0,1,…,K+m-i-1時(shí)，f-(V[i,i+k])=f+(V[i,i+k])=+∞。因此，問題的最優(yōu)值可由下式給出：

3.2 服務(wù)時(shí)間任意的情形

針對(duì)服務(wù)時(shí)間任意的情形，我們首次給出一個(gè)近似比為13/7的近似算法。在下文，我們?cè)O(shè)θ為以h為起點(diǎn)，經(jīng)過Vh中所有頂點(diǎn)且每個(gè)群中的頂點(diǎn)連續(xù)經(jīng)過，同時(shí)又以h為終點(diǎn)的最短旅行路線。此外，亦設(shè)θ表示該路線長(zhǎng)度。接下來，我們首先給出算法，然后給出算法分析。

算法A2

步驟1對(duì)相應(yīng)的零服務(wù)時(shí)間問題，調(diào)用3.1節(jié)的動(dòng)態(tài)規(guī)劃最優(yōu)算法生成時(shí)間表S3，然后按照S3服務(wù)客戶的順序?qū)蛻暨M(jìn)行服務(wù)。

步驟2計(jì)算滿足條件P′(t*)-Q′(t*)≤αt*≤P(t*)-Q(t*)的時(shí)刻t*(0≤t*≤rmax)，其中α為待定參數(shù)。依據(jù)t*，將所有的群劃分成{0,1,2,…,K-1}V′(t*)和V′(t*)u′(t*)以及{u′(t*)}三部分。構(gòu)造時(shí)間表S4，使得車輛首先在h處等至?xí)r刻t*，然后沿θ服務(wù)下標(biāo)屬于{0,1,2,…,K-1}V′(t*)中的每個(gè)群；接下來，車輛沿著以h為起點(diǎn)的最短旅行路服務(wù)Vu′(t*)中釋放時(shí)間不超過t*的所有客戶；再下來，車輛沿著最短旅行路服務(wù)Vu′(t*)中釋放時(shí)間嚴(yán)格大于t*的所有客戶；最后，車輛沿著以h為終點(diǎn)，經(jīng)過V′(t*)u′(t*)中所有頂點(diǎn)且每個(gè)群中頂點(diǎn)連續(xù)經(jīng)過的最短旅行路，服務(wù)V′(t*)u′(t*)中的每個(gè)群。

步驟3從S3和S4中選擇時(shí)間表長(zhǎng)較小者作為最終的近似解。

圖4 當(dāng)圖G不存在旅行時(shí)間超過t(G)/2的 邊時(shí)，算法A2中車輛的行駛路線示意圖

在圖4，不失一般性假設(shè)，V′(t*)u′(t*)中，從h按順時(shí)針方向，兩端的群分別為Vl和Vr。其中，①表示在h處等至t*時(shí)刻后沿θ服務(wù){(diào)0,1,2,…,K-1}V′(t*)中每個(gè)群；②表示沿著以h為起點(diǎn)的最短旅行路(這里不妨設(shè)t(h,su′(t*))≤t(h,tu′(t*)))服務(wù)Vu′(t*)中釋放時(shí)間不超過t*的所有客戶；③表示沿著以當(dāng)前點(diǎn)為起點(diǎn)的最短旅行路服務(wù)Vu′(t*)中釋放時(shí)間超過t*的所有客戶；④表示沿著以當(dāng)前點(diǎn)為起點(diǎn)，經(jīng)過V′(t*)u′(t*)中所有頂點(diǎn)且每個(gè)群中頂點(diǎn)連續(xù)經(jīng)過的最短旅行路服務(wù)V′(t*)u′(t*)中的每個(gè)群；⑤表示從當(dāng)前點(diǎn)返回初始出發(fā)位置h。

同算法A1的時(shí)間復(fù)雜度分析，算法A2的時(shí)間復(fù)雜度亦為O(n2)。類似于線型網(wǎng)絡(luò)上單臺(tái)車輛分群調(diào)度問題最優(yōu)時(shí)間表長(zhǎng)下界的證明，我們不難得出圈型網(wǎng)絡(luò)上最優(yōu)時(shí)間表長(zhǎng)的下界。

下面在引理5和6分別給出S3和S4的時(shí)間表長(zhǎng)上界。

綜合引理5和6，我們可以得出本節(jié)的主要結(jié)論。