線型/圈型網絡上單臺車輛分群調度問題

包曉光, 焦長春

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

0 引言

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

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

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

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

1 問題描述和符號

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

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

符號含義P=∑i∈Vhpi所有客戶的服務時間之和;rmax=maxi∈Vhri所有客戶的最大釋放時間;t(G)=∑(i,j)∈Et(i,j)網絡圖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)中客戶的服務時間之和;P′(t)=∑{i|i∈Vl,l∈V′(t)}piV′(t)中客戶的服務時間之和;Q(t)=maxl∈V(t)∑{i|i∈Vl,ri

2 線型網絡

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

圖1 線型網絡頂點劃分示意圖

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

算法A1

步驟1對相應的零服務時間問題，調用包曉光等[9]的動態規劃最優算法生成時間表S1，然后按照S1服務客戶的順序對客戶進行服務。

步驟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*)}三部分。依據Vu′(t*)的位置，構造一個時間表S2，使得車輛首先在h處等至時刻t*，然后，若Vu′(t*)位于h的左側(右側)，則接下來從右至左(從左至右)服務下標屬于{0,1,2,…,K-1}V′(t*)的每個群，再從左至右(從右至左)服務Vu′(t*)中釋放時間不超過t*的所有客戶，然后從右至左(從左至右)服務Vu′(t*)中釋放時間超過t*的所有客戶，最后從左至右(從右至左)服務V′(t*)u′(t*)中的每個群。S2中車輛的行駛路線示意圖見圖2(為后面分析方便，假設Vu′(t*)的左右端頂點分別為u1和u2，V′(t*)u′(t*)中最左(右)端的群為Vl(Vr)，其相應的兩個端頂點分別為l1(r1)和l2(r2))。

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

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

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

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

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

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

定理1對于線型網絡上單臺車輛分群調度問題，算法A1是一個求解該問題的7/4近似算法。

3 圈型網絡

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

圖3 圈型網絡頂點劃分示意圖

3.1 服務時間為零的情形

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

定理2對于零服務時間的圈型網絡上單臺車輛分群調度問題，存在一個最優時間表，使得在任意時刻，未服務的群的集合與h一起誘導的子圖是連通的。

基于定理2，我們給出求解該情形的一個動態規劃最優算法。為方便起見，設第i個群的兩個端頂點按順時針方向分別為si和ti，且h位于第m與m+1個群之間。設V[i,j]表示按順時針方向從Vi到Vj的群集合。特別地，令V[i,i]=Vi。設f-(V[i,i+k])和f+(V[i,i+k])(i=0,1,2,…,K-1;k=K-3,K-2,…,1,0)分別為車輛從h出發，服務完群{V0,V1,V2,…,VK-1}V[i,i+k]，且停在ti-1和si+k+1所需的最短時間。注意，由于網絡結構是圈型，這里假設每個群下標都是(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])=+∞。因此，問題的最優值可由下式給出：

3.2 服務時間任意的情形

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

算法A2

步驟1對相應的零服務時間問題，調用3.1節的動態規劃最優算法生成時間表S3，然后按照S3服務客戶的順序對客戶進行服務。

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

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

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

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

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

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

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