包曉光, 焦長春

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

0 引言

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

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

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

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

1 問題描述和符號

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

給定一個時間表S，我們用Cmax(S)表示其時間表長。同時，我們另外定義一些將在后文使用的符號。

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

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

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

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

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

算法A1

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

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

步驟3從S1和S2中選擇時間表長較小者作為最終的近似解。

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

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

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

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

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

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

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

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

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

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

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

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

基于定理2，我們給出求解該情形的一個動態(tài)規(guī)劃最優(yōu)算法。為方便起見，設(shè)第i個群的兩個端頂點按順時針方向分別為si和ti，且h位于第m與m+1個群之間。設(shè)V[i,j]表示按順時針方向從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所需的最短時間。注意，由于網(wǎng)絡(luò)結(jié)構(gòu)是圈型，這里假設(shè)每個群下標都是(mod K)的。因此，成立下面的遞推公式:

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

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

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

算法A2

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

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

步驟3從S3和S4中選擇時間表長較小者作為最終的近似解。

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

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

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

下面在引理5和6分別給出S3和S4的時間表長上界。

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