環(huán)形路網(wǎng)上帶有服務(wù)時(shí)長(zhǎng)的在線TSP問(wèn)題

樊相宇，林小果，武小平

(1.西安郵電大學(xué)， a.郵政研究院； b.經(jīng)濟(jì)與管理學(xué)院； c.現(xiàn)代郵政學(xué)院，陜西 西安 710061)

0 引言

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

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

本文綜合特殊網(wǎng)絡(luò)、服務(wù)時(shí)長(zhǎng)和TSP問(wèn)題，在已有研究上進(jìn)行融合創(chuàng)新，具有一定的理論意義。研究對(duì)象為快遞攬件，如今快遞行業(yè)的競(jìng)爭(zhēng)壓力大，如果能對(duì)攬件的快遞車輛進(jìn)行有效調(diào)度，在更好服務(wù)客戶的同時(shí)，也能提高快遞企業(yè)的工作效率，使快遞企業(yè)具有極大的競(jìng)爭(zhēng)優(yōu)勢(shì)，具有一定的實(shí)踐價(jià)值。此外，通過(guò)結(jié)合路網(wǎng)結(jié)構(gòu)設(shè)計(jì)相應(yīng)的策略進(jìn)行攬件，更貼合當(dāng)下快遞攬件的真實(shí)情況，對(duì)快遞車輛進(jìn)行有效調(diào)度具有重要的現(xiàn)實(shí)指導(dǎo)意義。

本文研究環(huán)形路網(wǎng)上帶有服務(wù)時(shí)長(zhǎng)的在線TSP問(wèn)題，即在環(huán)形路網(wǎng)上在線車即時(shí)獲取需求信息后，攬件完成回到服務(wù)中心總時(shí)間盡可能短的路徑選擇問(wèn)題。首先分析了此問(wèn)題的下界，然后設(shè)計(jì)了兩個(gè)在線算法，分析了各自的競(jìng)爭(zhēng)比，并給出一個(gè)簡(jiǎn)單算例說(shuō)明其可行性，算法的結(jié)論可以為環(huán)形路網(wǎng)上的快遞車輛實(shí)時(shí)調(diào)度提供依據(jù)。

1 問(wèn)題描述與基本假設(shè)

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

基本假設(shè)：

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

(2)服務(wù)時(shí)長(zhǎng)si≤S，即服務(wù)時(shí)長(zhǎng)取值正常，不存在服務(wù)時(shí)長(zhǎng)過(guò)大的情況；

(3)車速為單位速度。

2 環(huán)形路網(wǎng)上帶有服務(wù)時(shí)長(zhǎng)的在線TSP問(wèn)題的下界

為了得到問(wèn)題的下界，需要構(gòu)造特殊的需求序列，在服務(wù)此需求序列過(guò)程中，無(wú)論使用什么策略，在線費(fèi)用與離線費(fèi)用的比值不小于某個(gè)數(shù)值，它就是該問(wèn)題的競(jìng)爭(zhēng)比下界。該數(shù)值與策略無(wú)關(guān)，即無(wú)論用什么策略，兩者的比值都不會(huì)小于這個(gè)數(shù)。

證明構(gòu)造這樣一組需求序列，第一個(gè)需求釋放的時(shí)間為t(0≤t≤2πr)，需求出現(xiàn)的位置總是在在線車直徑的另一端，并且服務(wù)完當(dāng)前需求下一個(gè)需求立即釋放，不服務(wù)完當(dāng)前需求，沒(méi)有新的需求到來(lái)。

情形1當(dāng)在線車在起點(diǎn)O，需求在B點(diǎn)釋放時(shí)：

情形1.1只有一個(gè)需求的情形。

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

情形2當(dāng)在線車不在起點(diǎn)O時(shí)，令其當(dāng)前位置為x，則需求在πr+x處釋放：

情形2.1只有一個(gè)需求的情形。

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

定理1的結(jié)論表明，服務(wù)時(shí)長(zhǎng)降低了離線車的優(yōu)勢(shì)，改善了在線車的競(jìng)爭(zhēng)性能。

3 在線算法設(shè)計(jì)

不同的在線算法具有不同的服務(wù)效果，用競(jìng)爭(zhēng)分析的方法評(píng)價(jià)在線算法，是因?yàn)樗苁鼓骋凰惴ǖ慕馀c離線最優(yōu)方案給出的解總在一定的比例之內(nèi)，進(jìn)而可以確定該在線算法的性能。

3.1 LOOP算法

LOOP算法的具體步驟如下：

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

(2)如果在服務(wù)過(guò)程中新需求出現(xiàn)的位置li不小于在線車當(dāng)前位置x就服務(wù)此需求，否則就忽略。

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

情形1當(dāng)最后一個(gè)需求在tn時(shí)刻釋放時(shí)，在線車在起點(diǎn)O。將此時(shí)在線車從起點(diǎn)O出發(fā)到返回起點(diǎn)O服務(wù)的所有需求序列為記為M(M∈N)。

情形2當(dāng)最后一個(gè)需求在tn時(shí)刻釋放時(shí)，在線車不在起點(diǎn)O，將此時(shí)所有未服務(wù)的需求序列記為M(M∈N)。

由定理2可知，在LOOP算法下，總服務(wù)時(shí)長(zhǎng)越大，在線車的競(jìng)爭(zhēng)性能越好。

3.2 SD算法

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

情形a當(dāng)在線車在起點(diǎn)O時(shí)，如果沒(méi)有已釋放需求，在線車就在起點(diǎn)等待，否則，在線車就沿著最優(yōu)路徑去服務(wù)已釋放但還未被服務(wù)的需求并沿最短路徑回到原點(diǎn)O。

情形b當(dāng)在線車不在起點(diǎn)O時(shí)，如果沒(méi)有已釋放需求，在線車沿最短路徑回到原點(diǎn)O。如果有新的需求Di提出時(shí)，在線車根據(jù)需求的位置li做出下列決策：

(1)當(dāng)li在在線車行駛方向的前方時(shí)，在線車?yán)^續(xù)前行，沿著當(dāng)前路徑去服務(wù)已釋放但還未被服務(wù)的需求并沿最短路徑返回起點(diǎn)O(如果返回路徑上有滿足服務(wù)的需求就進(jìn)行服務(wù))，進(jìn)入情形a。

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

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

情形1當(dāng)最后一個(gè)需求在tn時(shí)刻釋放時(shí)，在線車在起點(diǎn)O。將此時(shí)在線車從起點(diǎn)O出發(fā)到返回起點(diǎn)O服務(wù)的所有需求序列為記為M(M∈N)。

情形2當(dāng)最后一個(gè)需求在tn時(shí)刻釋放時(shí)，在線車不在起點(diǎn)O，令其位置為x，將此時(shí)在線車從起點(diǎn)O出發(fā)到返回起點(diǎn)O服務(wù)的所有需求序列為記為M(M∈N)。

4 算例分析

給出的兩種算法，從結(jié)果分析SD算法比LOOP算法要好，但是不能否認(rèn)LOOP算法也有其應(yīng)用價(jià)值，下面給出兩種算法的適用范圍：

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

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

如果?lm+n-lm<πr,lm為在線車反方向返回O點(diǎn)前服務(wù)的最后一個(gè)需求，此時(shí)采用LOOP算法較優(yōu)。

否則，采用SD算法較優(yōu)。

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

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

先分析離線情形，由于離線車提前知道所有需求的信息，它能提前規(guī)劃路徑，所以對(duì)于這些需求離線車0時(shí)刻出發(fā)，沿著O→D1→D2→D3→O的路徑去服務(wù)并返回起點(diǎn)，總的服務(wù)時(shí)長(zhǎng)為2π+3，LOOP算法和SD算法的服務(wù)計(jì)算如表1所示(→表示逆時(shí)針?lè)较蛐旭?，←表示順時(shí)針?lè)较蛐旭?：

表1 LOOP算法和SD算法的競(jìng)爭(zhēng)比計(jì)算過(guò)程

上面給出的算例是l3-l2<πr的情況，如果把D3(6.5,4，0.5)的需求位置改為6，即D3(6.5，6，0.5)，此時(shí)l3-l2>πr，LOOP算法和SD算法的服務(wù)計(jì)算如表2所示(→表示逆時(shí)針?lè)较蛐旭?，←表示順時(shí)針?lè)较蛐旭?：

表2 LOOP算法和SD算法的競(jìng)爭(zhēng)比計(jì)算過(guò)程

從兩個(gè)表中的數(shù)據(jù)可以得出，表1的算例LOOP算法比SD算法的性能要好，表2的算例SD算法比LOOP算法的性能要好，但是比值都與理論上的競(jìng)爭(zhēng)比有差距，這是因?yàn)槔碚撋系母?jìng)爭(zhēng)比是最壞情況分析的競(jìng)爭(zhēng)比，而算例給出的不是最壞的情況，所以實(shí)際算例的比值會(huì)小于理論上的競(jìng)爭(zhēng)比。

結(jié)合環(huán)形路網(wǎng)特點(diǎn)設(shè)計(jì)的兩個(gè)在線算法，經(jīng)分析可知，在生活中LOOP算法適用于攬件需求分布較分散且需求多的路段，SD算法適用于攬件需求分布集中的路段，在實(shí)際服務(wù)中，攬件員可以根據(jù)實(shí)際情況采取不同的服務(wù)策略或者綜合使用兩種策略。

5 結(jié)論

針對(duì)環(huán)形路網(wǎng)上帶有服務(wù)時(shí)長(zhǎng)的快遞攬件，構(gòu)建了環(huán)形路網(wǎng)上帶有服務(wù)時(shí)長(zhǎng)的在線TSP問(wèn)題，與不考慮服務(wù)時(shí)長(zhǎng)的在線問(wèn)題相比較，具有服務(wù)時(shí)長(zhǎng)的在線TSP問(wèn)題降低了離線車的優(yōu)勢(shì)，改善了在線車的競(jìng)爭(zhēng)性能。本文在服務(wù)時(shí)長(zhǎng)的基礎(chǔ)上又考慮了環(huán)形路網(wǎng)，這兩個(gè)因素相結(jié)合更加符合現(xiàn)實(shí)生活中快遞攬件的情形，所以得到的比值相對(duì)只考慮服務(wù)時(shí)長(zhǎng)的情形來(lái)說(shuō)會(huì)增大，因此本文的研究結(jié)果是對(duì)已有研究的擴(kuò)展。當(dāng)沒(méi)有服務(wù)時(shí)長(zhǎng)，該問(wèn)題就轉(zhuǎn)化為環(huán)形路網(wǎng)上的一般在線TSP問(wèn)題，因此，本文的模型更具一般性，更貼近現(xiàn)實(shí)生活，結(jié)論可以為實(shí)時(shí)調(diào)度決策提供一定的依據(jù)。城市交通路網(wǎng)結(jié)構(gòu)具有多樣性，未來(lái)可以進(jìn)一步研究其它特殊路網(wǎng)上的在線問(wèn)題。