帶有時(shí)間約束與懲罰的在線訂單配送研究

武小平 孫靖

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

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

問(wèn)題描述：

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

基本假設(shè) ：

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

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

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

4） 服務(wù)請(qǐng)求一旦被接受就不能被取消；

在線策略設(shè)計(jì)與競(jìng)爭(zhēng)分析

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

參考文獻(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] 馬軍平，徐寅峰，陳聰，等.具有服務(wù)時(shí)長(zhǎng)的在線TSP問(wèn)題[J].系統(tǒng)工程理論與實(shí)踐， 2015， 35（11）：2832-2839.

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

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

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