馬軍平，徐寅峰，吳騰宇

(1.西安工業(yè)大學 經濟管理學院，陜西 西安 710032； 2.西安交通大學 管理學院，陜西 西安 710049； 3.重慶郵電大學 經濟管理學院，四川 重慶 400065)

0 引言

2018年6月中國國家郵政局在《2017年郵政行業(yè)發(fā)展統(tǒng)計公報》中指出，2017年，中國郵政行業(yè)業(yè)務總量突破9000億元，收入突破6000億元。其中全年快遞服務企業(yè)業(yè)務量完成400.6億件，同比增長28%；快遞業(yè)務收入完成4957.1億元，同比增長24.7%。對于快遞企業(yè)來說，其收益主要來自攬件服務，因此，為了達到更高的收益水平，實現(xiàn)對快遞攬件車輛進行有效調度(例如投遞路線智能優(yōu)化技術、運輸管理全程跟蹤查詢技術等)，具有重要的現(xiàn)實意義。

在實際攬件過程中，快遞車輛的行駛路線調度具有兩個顯著特征：一是無法提前獲知顧客發(fā)快遞的需求；第二個是需求的到來時間和地點難以預測，甚至難以給出其分布概率。這是一個典型的在線決策問題，即決策者在只知道部分信息的情況下需要做出全局優(yōu)化決策的問題。該問題在理論上可以用在線旅行商模型進行刻畫，但是以往的在線旅行商模型尚未考慮快遞攬件情境的特殊性，例如，服務每一個快遞需求需要花費一定的時間(如填寫面單，收取服務費等時間)，并且，有時快遞車輛因時間、容量、距離等原因有可能拒絕新的快遞請求從而導致?lián)p失(如經濟損失、企業(yè)聲譽損害或者產生顧客抱怨等)。因此，針對上述情形，本文提出帶有服務時長和服務可選擇性的快遞車輛在線調度問題，建立在線優(yōu)化模型，設計相應的快遞車輛在線調度策略并且在理論上分析其競爭比，結論將為快遞車輛的科學調度提供理論依據。

需求出現(xiàn)的時間和位置等信息不確定的在線旅行商問題最早由Ausiello等在2001年提出。Ausiello等在一般網絡上給出了2-競爭比的在線策略，在直線上給出了1.75-競爭比的在線策略[1]。后來的學者在此基礎上對在線旅行商問題進行擴展，例如：在線PCTSP問題[2]、具有可選擇性的在線旅行商問題[3,4]、帶有預知時間的在線旅行商問題[5～10]、特殊網絡上的在線旅行商問題、基于時間約束的在線旅行商問題[11,12]等。其中具有可選擇性的在線旅行商問題是指在線車可以選擇拒絕服務需求，但是拒絕需求將付出一個懲罰[3]。Jaillett和Lu對此問題進行了研究，并在正半軸上給出了一個2-競爭比的在線策略，在一般網絡上給出了一個2.28-競爭比的在線策略[3]。他們后來又研究了具有實時可選擇性的在線旅行商問題，即當一個新的需求到達時，在線策略要立即做出選擇接受或者拒絕該需求的決策，并在正半軸上給出2.5-競爭比的在線策略，在直線上給出3-競爭比的在線策略[4]。在此基礎上，溫新剛等研究了具有時間約束和服務可選擇性的在線旅行商問題[11]，廉文琪等研究了基于預知信息和實時服務選擇的在線旅行商問題[12]。以上研究中均假設服務需求的服務時長為零，即在線車經過需求點即視為服務完成，這使得以往提出的車輛在線路徑選擇策略不再適用于本文所研究的情形。因此，同時考慮服務時長和服務可選擇性的快遞車輛在線調度問題，應當如何建模并設計相應的在線策略，在理論上需要進一步研究。

本文克服以往模型中未同時考慮服務時長和服務可選擇性的不足，在理論上是對已有研究的深入和擴展，并且更加符合快遞車輛實時調度的現(xiàn)實。后續(xù)行文首先進行問題描述并證明了該問題在線策略競爭比的下界；然后在正半軸上，提出了Replan策略并證明其競爭比；在直線上，提出了ReOPT策略并證明其競爭比；在一般網絡上，提出了GRH策略并證明其競爭比；最后給出實例和結論。

1 問題描述與基本定義

帶有服務時長和服務可選擇性的快遞車輛在線調度問題描述如下。給出一個網絡圖M，d為定義在M上兩點間的距離函數(shù)d(.,.)。網絡圖M具有三個屬性：(1)M是對稱網絡，即對于M上的任意點對x,y，均滿足d(x,y)=d(y,x)；(2)對于M上的任意一點x，滿足d(x,x)=0；(3)網絡圖M滿足三角不等式。該網絡圖M包括一個起點o和一系列可能出現(xiàn)需求的節(jié)點。將需求表示為Ri=(li,ri,pi,si)，i=1,2,3,…,n，其中n為需求的總數(shù)量。li∈M表示需求i的位置，ri≥0表示需求的釋放時間(release time)，只有到達釋放時間的需求才可以接受服務，并且ri具有時間順序，即當i

0時刻，一個在線車處于起點o。在線車事先不知道需求的數(shù)量n，當需求釋放后，在線車才能獲知需求的位置和服務時長。當一個新的需求被釋放時，在線車需要決定是否接受該需求。車輛只能保持靜止或以單位速度移動來服務已接受的需求，在線車最終狀態(tài)為處理完所有需求后在起點o靜止。將車輛最早進入最終狀態(tài)的時間定義為完工時間(makespan)。該問題的目標是服務需求的總成本盡可能小，其中總成本是指完工時間與懲罰之和。

2 在線策略競爭比下界

情形2r1≤t0≤rn+1。令m∈{1,2,…,n}，設在線車離開起點o的時間t0滿足rm≤t0≤rm+1。當在線車從起點o出發(fā)時，離線敵手只能釋放前m個需求。

由以上分析可以得到：

否則令k(k≤m)為接受的需求中距離起點o位置最遠的一個需求，則在線車的成本為

因此，由以上分析可得：

3 快遞車輛調度在線策略

3.1 正半軸上的在線策略

3.1.1 正半軸上的最優(yōu)離線策略A

為給出正半軸上的在線策略，首先在正半軸上考慮如下離線問題：即不考慮釋放時間的帶有服務可選擇性和服務時長的車輛調度問題。假定一個車輛位于x位置(x≥0)并且有n個需求(li,pi,si)1≤i≤n需要服務。車輛只能保持靜止或以單位速度移動來服務已接受的需求并且最后返回起點o。目標是服務需求的總成本盡可能小，其中總成本是指完工時間與懲罰之和。

引理1正半軸上不考慮釋放時間的帶有服務可選擇性和服務時長的車輛調度問題最優(yōu)離線策略的總成本滿足下列條件：

證明分兩種情形討論：

引理得證。

從引理1的分析可以得出，當車輛處于x位置(x≥0)時，可提出一個解決不考慮釋放時間的帶有服務可選擇性和服務時長的車輛調度問題的最優(yōu)離線策略A，該策略根據車輛處于x位置，分為兩種情形，具體描述如下。

策略A(x≠0)

步驟1將所有的需求非遞減排序滿足lki≤…≤lkn。令1≤m≤n使得lkm≤x≤lkm+1。如果不存在這樣的m，令m=0，轉步驟 2。

策略A(x=0)

步驟1將所有的需求非遞減排序滿足lki≤…≤lkn。令1≤m≤n使得lkm≤x≤lkm+1。如果不存在這樣的m，令m=0，轉步驟2。

3.1.2 正半軸上在線策略Replan策略及其分析

在策略A的基礎上，針對帶有服務時長和服務可選擇性的快遞車輛在線調度問題，本文提出正半軸上的在線策略Replan策略。該策略的主要思想是每當一個新的需求被釋放時，在線車根據當前的位置的情況，選擇調用策略A。

Replan策略在線車根據當前的位置x進行決策：

步驟1初始化。令x=0，初始時間t=0，迭代次數(shù)i=0，轉步驟2。

步驟2如果沒有新的需求釋放，停止：拒絕任何以前未服務的需求，則完工時間(makespan)為t。否則，另i=i+1，在線車在起點o靜止到下一個需求釋放的時間ri，轉步驟3。

步驟3如果x>0，則在線車調用策略A(x≠0)，否則調用策略A(x=0)，此進，ω=ri-t，然后根據計算出的路徑服務接受的需求，令按照該路徑移動返回起點o的時間為tr。轉步驟4。

步驟4如果在線車在完成當前路徑(未到達起點o)之前沒有新的需求釋放，則設x=0，t=tr，轉步驟2。如果在線車在未完成當前路徑(未到達起點o)時就釋放了新的需求，令i=i+1，根據新需求出現(xiàn)的時間更新在線車當前的位置x和t，轉步驟3。

證明根據離線服務器的行動決定在線車的行動，不失一般性，令最后一個釋放的需求為第n個需求。

情形2.2x≥lm。令Lmax為當前路徑上距起點o最遠的需求的位置。令S′為離線車未接受而在線車在一次和第二次通過lm位置之間接受的需求集合。

在情形2.2下，在線車的成本為：

由情形2.1的分析，可知在情形2.2下，在線車成本與離線車成本之比為：

定理得證。

3.2 直線上的在線策略

3.2.1 直線上的最優(yōu)離線策略B

在直線上，帶有服務時長和服務可選擇性的快遞車輛在線調度問題對應的離線問題可以描述如下。在一條直線上已經釋放了n個需求(li,pi,si)1≤i≤n，不失一般性，假定離線車位于x≥0處。離線車只能保持靜止或以單位速度移動來服務已接受的需求并且最后返回起點o。目標是服務需求的總成本盡可能小，其中總成本是指完工時間與懲罰之和。

因此，離線車只要在滿足下列三個條件的需求中選擇相應的需求構成實際服務的需求集合S，使得離線成本最小即可。

(1)

由以上分析，可以給出直線上帶有服務時長和服務可選擇性的快遞車輛在線調度問題對應的最優(yōu)離線策略B。

3.2.1 直線上在線策略ReOPT策略及其分析

在直線上最優(yōu)離線策略B的基礎上，針對帶有服務時長和服務可選擇性的快遞車輛在線調度問題，給出直線上的在線策略ReOPT策略。

ReOPT策略 在線車根據當前的位置x進行決策：

步驟1初始化。令初始時間t=0，迭代次數(shù)i=0，轉步驟2。

步驟2如果沒有新的需求釋放，停止：拒絕任何以前未服務的需求，則完工時間(makespan)為t。否則，另i=i+1，在線車在起點o靜止到下一個需求釋放的時間ri，轉步驟3。

步驟3在線車調用離線最優(yōu)策略B，然后根據計算出的路徑服務集合S中的需求，令按照該路徑移動返回起點o的時間為tr。轉步驟4。

步驟4如果在線車在完成當前路徑(未到達起點o)之前沒有新的需求，釋放則t=tr，轉步驟 2。如果在線車在未完成當前路徑(未到達起點o)時就釋放了新的需求，令i=i+1，根據新需求出現(xiàn)的時間更新t，轉步驟3。

定理3對于帶有服務時長和服務可選擇性的快遞車輛在線調度問題，ReOPT策略在直線上的競爭比為2。

證明在線車根據離線服務器的行動決定自身的行動，不失一般性，令最后一個釋放的需求為第n個需求。

情形2離線車接受了最后一個需求n。令S為離線車所有接受的需求集合，令S位于區(qū)間[-L,R]之內。令P(t)為在線車在t時刻的位置，則將rn時刻在線車的位置記為x=P(rn)。

3.3 一般網絡上的在線策略

假設策略C是一個針對不考慮釋放時間情形下，帶有服務可選擇性和服務時長的快遞車輛在線調度問題的離線策略。令Sm為策略C在前m個需求中接受的需求集合，該集合包括起點o。策略C可以計算出一條服務Sm中需求的服務路徑。對于每一個新的需求釋放的時刻tm(m≥1)，在線策略調用策略C來計算該服務路徑。

GRH策略(Greedy return home)的主要思路是一旦有新的需求出現(xiàn)，在線車就通過最短路徑返回起點o以便于可以盡快調用策略C重新計算一條服務路徑。這里的Greedy是指在線車總是通過最短路徑在兩個需求點之間移動。

GRH策略每次一個新需求m在rm時刻被釋放時，在線車根據這個需求是否被策略C接受決策行動：

情形1m?Sm。在線車忽略該需求，繼續(xù)保持當前路徑；

情形2m∈Sm。在線車通過最短路從當前位置返回起點o，然后調策略C計算一條服務路徑Tm。然后沿著路徑Tm服務集合Sm中的所有需求，直到新的需求出現(xiàn)或最終返回起點o。

首先給出引理2，在此基礎上證明GRH策略的競爭比。

定理4對于帶有服務時長和服務可選擇性的快遞車輛在線調度問題，GRH策略在一般網絡上的競爭比為2.5。

從定理2～定理4的結果可知，Replan策略是一個最優(yōu)的在線策略，ReOPT策略和GRH策略的競爭性能較優(yōu)。本研究與傳統(tǒng)的在線旅行商問題相比，克服其模型中未考慮需求點服務時長和服務可選擇性的不足，在理論上證明了考慮服務時長能夠改善在線策略的競爭性能。因此，本文對在線旅行商問題在理論上給出了更一般化的模型，提出的在線策略也更加符合快遞車輛運營的實際情形。

4 實例分析

某國內快遞公司DB物流西安東郊分部負責的長樂東路沿途分布著20家單位(用實心圓點標記)，該分部的集貨點位于長樂路中段(用圓圈標記)，見圖1。每一家單位均有可能有發(fā)快遞的需求，但是快遞車輛根據實際情況，可以選擇接受或拒絕該需求。如果快遞車輛接受該需求，則服務這個需求要花費一定的服務時長。如果快遞車輛拒絕該需求，則需要付出相應的懲罰。某日快遞公司收到用戶的發(fā)貨請求r1～r6的出現(xiàn)時間分別為t1=0，t2=200，t3=500，t4=1500，t5=2000,t6=2900。0時刻時，快遞車位于起點o處。對于快遞攬件車輛而言，攬件需求是依次出現(xiàn)的，快遞車輛無法事先獲知快遞需求將在何時何處出現(xiàn)。那么，快遞車應如何選擇路徑，使得從集貨點出發(fā)服務所有需求并返回集貨點的總成本(makespan+懲罰)最?。?/p>

圖1 DB物流公司西安長樂東路攬件需求點分布

不失一般性，假設快遞車以單位速度移動來服務需求，快遞車服務每個需求點的服務時長為100個距離單位，快遞車輛拒絕每個需求點的懲罰為1400個距離單位。為分析方便，將上述需求點的出現(xiàn)次序和位置在直線上標出(圖2)。

先分析在線情形。假設在線車采用直線上的ReOPT策略來調度車輛。當每一個需求出現(xiàn)時，在線車的決策和移動過程如表1。經計算，在線車最終實際的服務路徑是o-r3-o-r1-r5-r6-r2-o，總的服務成本為8800。

表1 在線車路徑選擇決策過程

再分析離線情形。在離線情形下，在0時刻時，快遞車已知道所有需求點的未來的位置和釋放時間。經計算，離線車的最優(yōu)路徑為：o-r3-o-r6-r2-r1-o。在t=o時刻時，離線車即從起點o出發(fā)，在移動的過程中服務沿途已釋放的需求，其所花費的總成本為7900(離線車和在線車的移動軌跡如圖2所示)

圖2 實例中需求點位置及車輛的移動軌跡

綜上，本實例中，ReOPT策略的實際競爭比為8800/7900=1.114，優(yōu)于ReOPT策略競爭比下界的理論值2，這說明ReOPT策略在現(xiàn)實中實用性較好。這是因為本問題在線策略的下界是指當需求以最壞情形出現(xiàn)時，在線策略有可能達到的最好情況。但是現(xiàn)實中的快遞需求序列出現(xiàn)最壞序列的可能性較小。

5 結論

針對快遞攬件需求出現(xiàn)具有不確定性、服務每一個快遞需求需要一定的服務時長，且拒絕快遞需求會受到一定的懲罰的情形，提出針對帶有服務時長和服務可選擇性的快遞車輛在線調度問題。對此問題在線策略競爭比的下界進行了證明，并且對網絡是正半軸、直線和在一般網絡的情形，設計了相應的在線策略并且證明在線策略的競爭比。與一般在線旅行商問題比較，本文建立了更為一般的模型和在線策略，是對已有研究的擴展。所提在線策略在實際中具有實用性，可為快遞車輛的科學調度提供理論依據。對于在線車到達需求點時才能獲知該需求的服務時長的情形，未來可以進一步研究。