環形路網上帶有服務時長的在線TSP問題

樊相宇，林小果，武小平

(1.西安郵電大學， a.郵政研究院； b.經濟與管理學院； c.現代郵政學院，陜西 西安 710061)

0 引言

隨著電子商務和快遞行業的快速發展，人們對快遞的需求不斷提高，使得時效性成為評價快遞企業優劣的一個標準。攬件作為快遞收入的主要收益部分，為了得到更大的收益，需要提高快遞攬件的時效性，使快遞攬件所花費的時間盡可能短，因此，需要對攬件的快遞車輛進行有效調度?？爝f攬件的一般流程是：快遞車輛從服務中心出發，根據顧客的需求進行攬件，在攬件過程中會花費一定服務時長去填寫快遞單、包裝快遞和費用收取等，服務完成后回到服務中心，因此服務時長不可忽略。對于快遞攬件的服務過程，由于顧客需求具有不確定性，我們可以用在線旅行商(TSP, Traveling Salesman Problem)來刻畫這個問題。在實際生活中，由于城市交通路網具有多樣性，攬件員負責的路段也就多樣化，包括環形路網、方格路網、環形放射式路網等，而很多城市都有環形路網，例如成都，有“3環16射”，它的環形道路有內環路、一環路、二環路、三環路和外環路，其中外環路成放射狀道路，三環以內是商業中心，人流量大，快遞攬件需求量多，因此，針對快遞攬件中需求具有在線特征，即無法提前預知需求提出的時間、位置、以及服務時長，提出環形路網上帶有服務時長的在線TSP問題。

對于需求具有在線特征的TSP問題，我們可以用在線算法進行競爭分析。國外學者Ausiello等在2001年最早提出Online TSP問題，并且在一般網絡上給出2-競爭比的算法，在直線上給出1.75-競爭比的算法[1]，然后Lipmami將直線上的結果改進到1.64，達到直線上該問題的下界[2]。Blom等進一步將網絡限制在非負半軸上，給出1.5-競爭比的算法[3]，但這些都是在一般網絡和直線上的算法。對于非直線特殊路網上的在線問題，國外學者Frieze等最早在滿足三角不等式的網絡上設計了近似比為O(logn)的近似算法[4]，后來學者對此算法略有改進[5,6]，但該問題是否存在常數近似比的算法仍是開放問題，且需求是事先已知的，未考慮需求到來的不確定性。國內學者徐寅峰等研究了基于方格路網上的兩車應急救援路徑在線選擇問題，并設計了相應算法，但未考慮到服務時長等更貼近現實的因素[7]。隨著研究的深入，吳騰宇等研究了帶有配額的在線Nomadic旅行商問題[8]，和帶有線性懲罰的在線旅行商問題[9]，考慮了在現實生活中更為合理的情形，但也只是考慮到直線和一般網絡。馬軍平等研究了帶有預知信息的在線問題和具有服務時長的在線TSP問題，并在一般網絡和直線上設計了相應的在線算法[10,11]，但也未涉及到非直線特殊網絡。

本文綜合特殊網絡、服務時長和TSP問題，在已有研究上進行融合創新，具有一定的理論意義。研究對象為快遞攬件，如今快遞行業的競爭壓力大，如果能對攬件的快遞車輛進行有效調度，在更好服務客戶的同時，也能提高快遞企業的工作效率，使快遞企業具有極大的競爭優勢，具有一定的實踐價值。此外，通過結合路網結構設計相應的策略進行攬件，更貼合當下快遞攬件的真實情況，對快遞車輛進行有效調度具有重要的現實指導意義。

本文研究環形路網上帶有服務時長的在線TSP問題，即在環形路網上在線車即時獲取需求信息后，攬件完成回到服務中心總時間盡可能短的路徑選擇問題。首先分析了此問題的下界，然后設計了兩個在線算法，分析了各自的競爭比，并給出一個簡單算例說明其可行性，算法的結論可以為環形路網上的快遞車輛實時調度提供依據。

1 問題描述與基本假設

問題描述：給定一個環形路網圖C，半徑為r，起點為O，直徑為OB，顧客隨機在路網上提出需求Di(ti，li，si)，i=n，n∈N+，其中ti為需求的釋放時間，li為需求的服務位置，si為需求的服務時長，并將所有需求的集合記為N，攬件員接收到需求后立刻獲知該需求的所有信息，收集完所有快件后回到原點O，使得服務完所有需求并返回原點所花費的總服務時間盡可能短，則攬件員應該采取什么策略才能使總花費時間盡可能短？

基本假設：

(1)需求為離散序列，即ti+1-ti≥ε，ε為任意小的正數；

(2)服務時長si≤S，即服務時長取值正常，不存在服務時長過大的情況；

(3)車速為單位速度。

2 環形路網上帶有服務時長的在線TSP問題的下界

為了得到問題的下界，需要構造特殊的需求序列，在服務此需求序列過程中，無論使用什么策略，在線費用與離線費用的比值不小于某個數值，它就是該問題的競爭比下界。該數值與策略無關，即無論用什么策略，兩者的比值都不會小于這個數。

證明構造這樣一組需求序列，第一個需求釋放的時間為t(0≤t≤2πr)，需求出現的位置總是在在線車直徑的另一端，并且服務完當前需求下一個需求立即釋放，不服務完當前需求，沒有新的需求到來。

情形1當在線車在起點O，需求在B點釋放時：

情形1.1只有一個需求的情形。

情形1.2有多個需求，且最后一個需求釋放點在B點，釋放時間為tn時(最后一個需求的釋放點在O點跟B點類似)。

情形2當在線車不在起點O時，令其當前位置為x，則需求在πr+x處釋放：

情形2.1只有一個需求的情形。

情形2.2有多個需求，且最后一個需求的釋放點在πr+x處，釋放時間為tn時(最后一個需求的釋放點位置在x跟πr+x處類似)。

定理1的結論表明，服務時長降低了離線車的優勢，改善了在線車的競爭性能。

3 在線算法設計

不同的在線算法具有不同的服務效果，用競爭分析的方法評價在線算法，是因為它能使某一算法的解與離線最優方案給出的解總在一定的比例之內，進而可以確定該在線算法的性能。

3.1 LOOP算法

LOOP算法的具體步驟如下：

(1)如果沒有已釋放但還未被服務的需求，在線車就在起點O等待。否則，在線車就從起點O出發去服務已釋放但還未服務的需求，并從另一邊返回。

(2)如果在服務過程中新需求出現的位置li不小于在線車當前位置x就服務此需求，否則就忽略。

證明令所有需求中離起點O的最大距離為L(L=πr-ε,ε→0)，下面分情況進行討論：

情形1當最后一個需求在tn時刻釋放時，在線車在起點O。將此時在線車從起點O出發到返回起點O服務的所有需求序列為記為M(M∈N)。

情形2當最后一個需求在tn時刻釋放時，在線車不在起點O，將此時所有未服務的需求序列記為M(M∈N)。

由定理2可知，在LOOP算法下，總服務時長越大，在線車的競爭性能越好。

3.2 SD算法

SD(Smartstart and directional route)算法的具體步驟如下：

情形a當在線車在起點O時，如果沒有已釋放需求，在線車就在起點等待，否則，在線車就沿著最優路徑去服務已釋放但還未被服務的需求并沿最短路徑回到原點O。

情形b當在線車不在起點O時，如果沒有已釋放需求，在線車沿最短路徑回到原點O。如果有新的需求Di提出時，在線車根據需求的位置li做出下列決策：

(1)當li在在線車行駛方向的前方時，在線車繼續前行，沿著當前路徑去服務已釋放但還未被服務的需求并沿最短路徑返回起點O(如果返回路徑上有滿足服務的需求就進行服務)，進入情形a。

(2)當li不在在線車行駛方向的前方時，在線車忽略此需求繼續前行，沿著當前路徑去服務已釋放但還未被服務的需求并沿最短路徑返回起點O(如果返回路徑上有滿足服務的需求就進行服務)，進入情形a。

證明令各需求離起點O的最大距離為L(L=πr-ε,ε→0)，下面分情況進行討論：

情形1當最后一個需求在tn時刻釋放時，在線車在起點O。將此時在線車從起點O出發到返回起點O服務的所有需求序列為記為M(M∈N)。

情形2當最后一個需求在tn時刻釋放時，在線車不在起點O，令其位置為x，將此時在線車從起點O出發到返回起點O服務的所有需求序列為記為M(M∈N)。

4 算例分析

給出的兩種算法，從結果分析SD算法比LOOP算法要好，但是不能否認LOOP算法也有其應用價值，下面給出兩種算法的適用范圍：

(1)如果采用SD算法進行服務，在線車從起點O出發到返回O點方向始終一致，則采用SD算法和LOOP算法效果相同。

(2)如果采用SD算法進行服務，在線車沿最短路徑返回O點的方向跟從起點O出發的方向不一致，但是采用LOOP算法進行服務在線車從起點O出發到返回O點方向一致時：

如果?lm+n-lm<πr,lm為在線車反方向返回O點前服務的最后一個需求，此時采用LOOP算法較優。

否則，采用SD算法較優。

(3)除了上述(1)(2)兩種情況，其它情況采用SD算法較優。

本文給出環形路網上一個比較小的算例來說明上面2個在線算法的可行性，假如環形路網的半徑為1，路網上將有3個需求，分別是D1(2，1，1)，D2(3，2.5，0.5)，D3(6.5，4，0.5)，則α=2/π，β=1/2π，LOOP算法和SD算法的競爭比分別為2.638和2.259。

先分析離線情形，由于離線車提前知道所有需求的信息，它能提前規劃路徑，所以對于這些需求離線車0時刻出發，沿著O→D1→D2→D3→O的路徑去服務并返回起點，總的服務時長為2π+3，LOOP算法和SD算法的服務計算如表1所示(→表示逆時針方向行駛，←表示順時針方向行駛)：

表1 LOOP算法和SD算法的競爭比計算過程

上面給出的算例是l3-l2<πr的情況，如果把D3(6.5,4，0.5)的需求位置改為6，即D3(6.5，6，0.5)，此時l3-l2>πr，LOOP算法和SD算法的服務計算如表2所示(→表示逆時針方向行駛，←表示順時針方向行駛)：

表2 LOOP算法和SD算法的競爭比計算過程

從兩個表中的數據可以得出，表1的算例LOOP算法比SD算法的性能要好，表2的算例SD算法比LOOP算法的性能要好，但是比值都與理論上的競爭比有差距，這是因為理論上的競爭比是最壞情況分析的競爭比，而算例給出的不是最壞的情況，所以實際算例的比值會小于理論上的競爭比。

結合環形路網特點設計的兩個在線算法，經分析可知，在生活中LOOP算法適用于攬件需求分布較分散且需求多的路段，SD算法適用于攬件需求分布集中的路段，在實際服務中，攬件員可以根據實際情況采取不同的服務策略或者綜合使用兩種策略。

5 結論

針對環形路網上帶有服務時長的快遞攬件，構建了環形路網上帶有服務時長的在線TSP問題，與不考慮服務時長的在線問題相比較，具有服務時長的在線TSP問題降低了離線車的優勢，改善了在線車的競爭性能。本文在服務時長的基礎上又考慮了環形路網，這兩個因素相結合更加符合現實生活中快遞攬件的情形，所以得到的比值相對只考慮服務時長的情形來說會增大，因此本文的研究結果是對已有研究的擴展。當沒有服務時長，該問題就轉化為環形路網上的一般在線TSP問題，因此，本文的模型更具一般性，更貼近現實生活，結論可以為實時調度決策提供一定的依據。城市交通路網結構具有多樣性，未來可以進一步研究其它特殊路網上的在線問題。