武小平 孫靖

客戶提出訂貨需求后，供應商需要按訂單將產(chǎn)品配送給他們。在現(xiàn)實情況下，由于客戶的需求是隨機提出的，在任意時刻，供應商并不知道客戶何時提出訂貨需求和訂單大小，只有當訂單到達后，這些信息才能知道，稱這樣的問題為在線問題，評價在線算法的性能，常常利用競爭分析的方法[1]；衡量在線算法性能的最廣泛接受的方法是競爭分析。 某種在線策略的質(zhì)量由在線算法對一系列請求所需的時間與事先知道該序列的算法所需的最佳時間之間的最壞情況比率來衡量，該比率稱為在線算法的競爭比率。因此，如果每個輸入的完成時間最多是算法的ρ倍，則該算法稱為ρ競爭。想象一下一個配送員不必滿足所有要求，但是有一個滿足已接受要求的截止日期。通常延遲的服務會導致客戶不滿意，因為心理學研究表明人們傾向于估計等待時間[2]。對于在線配送問題，Igor以所有訂單的總流時間（訂單到達至配送給客戶這段時間）和配送費用之和最小為目標，在假設配送能力無限時，對于只有一個客戶的情形，采用SRPT（Shortest Remaining Processing Time）最優(yōu)加工策略加工訂單，同時設計了競爭比為2的最優(yōu)在線策略，對于有m個客戶情形，給出了競爭比為2m的最優(yōu)在線策略[3]；隨后他又研究了配送能力有限的情形，分別討論了權重都為1且具有一定加工時間、權重互不相等且加工時間為0、以及訂單先到先配送的問題，給出了相應的在線調(diào)度策略并給出了競爭比[4]；對于在線旅行商TSP問題（Travelling Salesman Problem），馬軍平等針對需求事先無法預知并且每個需求服務時長不確定的情形，提出具有服務時長的在線TSP問題，給出在一般網(wǎng)絡上PAH-ST算法和直線上的PQR-ST算法，并計算了它們的競爭比[5]。溫新剛等研究了預知信息的在線Nomadic TSP問題，分析了需求可提前被預知但不能立即接受服務的情形，即需求揭露時間和釋放時間不同的情形，給出在一般網(wǎng)絡和直線上的在線策略，結果表明，獲取的信息越多，在線策略的競爭性越好[6]。廉文琪等考慮快餐店在提供外送服務時，可選擇性提供送餐服務的情形，提出基于預知信息和實時服務選擇的在線TSP問題，分析了需求在正半軸和直線上的情形[7]。以上研究僅僅要求訂單配送給客戶即可，并沒有配送時間的限制。訂單在供應商處延遲不受限制，這與現(xiàn)實不相符，例如，很多網(wǎng)購行為中，供應商收到訂單后必須在規(guī)定的時間把產(chǎn)品送到客戶手里，否則就會降低信用度或喪失很多潛在客戶。本文就是在這種實際背景下，結合已有經(jīng)典研究，提出了帶有時間約束與懲罰的在線訂單配送問題。

問題描述與基本假設

問題描述：

攬件員從起點到終點 e過程中，既承擔攬件任務，也承擔將貨物配送至客戶所要求的地點（即終點 e）的任務，訂貨需求隨機產(chǎn)生。為了節(jié)省費用，某些訂單需求產(chǎn)生之后，不用立刻配送至終點 e，而是同后來的訂單一同配送，訂單需求產(chǎn)生未及時配送的產(chǎn)品存在等待時間（即訂單產(chǎn)生后到配送這一段時間），而且客戶對貨物到達時間有一定的要求，如何權衡這兩者之間的矛盾，使得總費用盡可能小呢？即以所有產(chǎn)品等待的時間和配送費用之和最小為目標，如何優(yōu)化帶有時間約束的配送問題。

基本假設 ：

1） 只考慮有一輛服務車的情況，令其行駛速度為1；

2） 載重車輛載重能力不受限制，即一次可以配送所有加工完未配送的產(chǎn)品；

3） 每一份訂單不能因配送而被分割（即不能配送訂單的一部分）；

4） 服務請求一旦被接受就不能被取消；

在線策略設計與競爭分析

（西安郵電大學現(xiàn)代郵政學院）

參考文獻：

[1] K.Pruhs， J.Sgall， E.Tong. Online scheduling，in：Joseph Y.-T. Leung（Ed.）， Handbook of scheduling：Algorithms， Models， and Performance Analysis， CRC Press， 2004，15：1-15， 41（Chapter 15）.

[2] Katz K， Larson B， Larson R （2003） Prescription for the waiting-in-line blues entertain， enlighten， and engage. Oper Manag Crit Perspect Bus Manag 2：160

[3] Igor Averbakh， Zhihui Xue. On-line supply chain scheduling problems with preemption[J].European Journal of Operational Research ， 2007， 181： 500-504.

[4] Igor Averbakh. On-line integrated productiondistribution scheduling problems with capacitated deliveries[J]. European Journal of Operational Research ， 2010， 200：377-384.

[5] 馬軍平，徐寅峰，陳聰，等.具有服務時長的在線TSP問題[J].系統(tǒng)工程理論與實踐， 2015， 35（11）：2832-2839.

[6] 溫新剛，徐寅峰，丁黎黎.基于預知信息的占線Nomadic TSP問題[J].系統(tǒng)工程理論與實踐，2013，33（1）：1-7.

[7] 廉文琪，徐寅峰.基于預知信息和實時服務選擇的在線TSP問題[J].系統(tǒng)工程理論與實踐，2016，26（1）：88-95.

[8] 吳騰宇，陳嘉俊，蹇潔，等.O2O模式下的配送車輛實時取送貨路徑選擇問題[J].系統(tǒng)工程理論與實踐，2018，38（11）：167-173.[9]吳騰宇，徐寅峰，溫新剛.預知信息和有限運載能力下應急車輛路徑選擇問題[J].系統(tǒng)工程理論與實踐， 2015， 35（5）：1224-1229.