采用超售策略的在線訂單配送時隙運能分配

劉鵬宇，陳淮莉

(上海海事大學物流科學與工程研究院，上海 201306)

0 引 言

隨著互聯網的高速發展，越來越多的零售商開通線上交易服務，然而在為銷售商提供便利的同時，在線交易的激烈競爭也給訂單配送提出了更多更高的要求。為盡可能地增加收益、降低成本，零售商不僅要把控好貨物質量還要盡可能合理安排運能。時隙(time slot)在B2C模式中是互聯網零售商在互聯網平臺上提供給客戶選擇的訂單貨物到達時間區間。[1-2]如菜鳥聯盟、京東等，都是通過讓消費者選擇到貨時隙安排運輸，一方面有利于消費者根據自身情況接收貨物，提高客戶滿意度，另一方面方便協調零售商與消費者、物流服務商的配送安排，合理規劃運能、時間、人力等資源，提升整體競爭力。

在運能分配方面，母柏松等[3]針對鐵路行包作業量小的車站容易產生的人力資源浪費問題，以作業量小的車站行包盡可能集中到發為優化目標，建立了行包運能分配的線性混合整數規劃模型，降低了鐵路行包運營管理成本。在電商領域，陳淮莉等[4]考慮價格和交付期對消費者選擇行為的影響，建立了Logit模型，采用強化學習對到達的訂單進行運能分配，解決了在線訂單配送效率低、時隙運能分配不均衡等問題。

在時隙定價方面，陳淮莉等[5]為盡可能地利用時隙配送能力，通過動態調整價格來誘導消費者的選擇行為，制定了合理的定價方法。DYE等[6]針對在參照效應背景下的時效產品動態定價和保鮮問題構建了連續參照函數，探討了參照效應對產品動態定價的影響。NASIRY等[7]構建了離散模型進行求解，他認為消費者錨定的參考價格是歷史上最低和最近的價格，偏好回避損失的消費者對損失比對參考價格更為敏感，他還指出相對應的動態定價問題有很多固定價格是最優的，如果更多的消費者將價格錨定在最低價格上，那么相對應的價格區間也就越寬。徐朗等[8]研究了在B2C背景下，在配送時隙均可用和某一時隙不可用兩種情況下的客戶替代時隙選擇問題。陳淮莉等[9]同時考慮區域和時隙寬度的影響，并動態估計訂單的交付成本，最終得到了在不同時隙寬度和效用下的激勵定價方案。

在實際問題中常用動態規劃方法處理動態訂單接受問題，但由于不確定因素很多，當問題規模變大時，采用動態規劃方法求解困難，容易面臨維數災難。強化學習算法是一種較好的求解方法。在強化學習的研究中，一般都是假設研究對象滿足馬爾科夫性質，隨后將其形式化為馬爾科夫決策過程[10]。王薇等[11]把可變限速過程通過控制定義為馬爾科夫決策過程，利用強化學習無模型的特點對高速公路主線流通進行了主動控制。對于強化學習在不確定環境下訂單處理中的應用，郝娟等[12]基于收益管理思想，采用平均強化學習算法研究了不確定環境下訂單生產方式企業的訂單接受策略，證明了用強化學習算法解決訂單接受問題的可行性。

超售在收入管理研究中有很長的歷史，它最早用在民航客運業，指售出的機票多于飛機的最大允許座位數，主要是為了減少退票和誤機帶來的座位浪費。陳敬光[13]分析了決策者的風險偏好因素，利用CVaR (conditional value-at-risk)風險度量法研究了在不同風險容忍水平下的超售策略。GE等[14]在超售模型中額外考慮了旅客換乘(即無法按時登機的旅客可以選乘下一航班)的影響。周薔等[15]將預售期內的旅客訂票過程看作泊松過程，并以此建立了超售模型，并結合枚舉法求解。SIERAG等[16]的研究表明不考慮客戶取消訂單的銷售策略可能導致20%的巨額收入損失，其模型特殊之處在于同時考慮了客戶選擇、取消訂單行為和企業超售策略。

目前在線訂單的研究焦點一直是時隙定價問題，少有文獻把車輛運輸能力和超售策略考慮進去。因此，在研究如何合理分配運能的同時，借鑒航空業的收益管理經驗，結合電商訂單時隙配送的特點，研究消費者選擇時隙的概率和時隙運能限制，充分考慮消費者的取消訂單行為，采用超售策略對時隙運能進行超售，提出通過強化學習有效解決考慮取消訂單行為的時隙運能分配問題。

1 基于強化學習的訂單處理過程

從強化學習的角度看，在訂單處理策略中，每個隨泊松分布概率λ到達的訂單都會使系統(把系統當作強化學習中agent)進入一個新的狀態。在每個狀態下，設定系統只會做出一種動作，即接受、取消或放棄。取消表示取消的是當前訂單之前客戶下達的訂單。系統在采取動作后分配訂單配送時隙和配送車輛，然后進入下一個狀態，對下一個訂單再選擇動作。可以看出在線訂單運能分配符合馬爾科夫決策過程，即一旦當前訂單運能確定，當前訂單運能分配結果就會直接影響下一訂單的運能分配。由于馬爾科夫決策過程是強化學習的理論基礎，故本文選擇強化學習中的Q學習算法來解決在線訂單運能分配問題。

1.1 參數定義

T為時隙集合，T={1,2,…,t0}。M為車輛集合，M={1,2,…,m0},m∈M。N為訂單集合，N={1,2,…,q0},q∈N。S為強化學習的狀態集合，S={sq},q∈N。A為強化學習的動作集合，A={a00}∪{a0m}∪{atm},t∈T,m∈M，其中：a00表示放棄訂單；a0m表示系統接受的訂單由車輛m在0時隙配送，即在客戶取消訂單后系統做出取消動作，此時運能分配出去但不安排配送時隙；atm表示接受的訂單由車輛m在時隙t配送。D為超售點過大時產生的懲罰成本。W為超售點過小時產生的失銷成本。Cmax為每輛車的最大運能；θq為系統為當前訂單q選擇的動作對應的訂單配送計劃表的實際運能。lq為訂單q的商品價格。εt(t∈T)為效用函數的隨機變量，服從Gumbel分布。β為消費者對價格的偏好系數，0<β<1。U0為訂單q初始最大效用。α和γ分別為狀態函數更新迭代的學習速率和折扣因子。hqt(t∈T)為訂單q的配送時隙t的時隙價格。λ為訂單到達率，服從泊松分布。k為取消訂單行為發生時收取消費者費用的比例，這里默認為與取消率相同。Uqt(t∈T)為訂單q選擇時隙t的效用，t=0時表示放棄訂單。Pqt(t∈T)為訂單q選擇時隙t的概率，Pq0為放棄訂單q的概率。Rqt(t∈T)為訂單q選擇時隙t的即時收益。Q(sq,atm)為強化學習中的Q函數，具體為當前訂單q選擇動作atm所獲得的累計收益，t∈T。Q(sq+1,atm)為當前訂單q選擇動作atm時，下一訂單q+1能夠獲得的累計收益，t∈T。

1.2 消費者時隙選擇

在電商領域，考慮客戶在線選擇的隨機性和客戶取消和放棄訂單的行為，選擇Logit模型對Q學習法中當前狀態下的動作進行選擇。

在經濟學中常用效用度量消費者通過消費行為使自己需求得到的滿足。[17]受時隙效用(受歡迎度)的影響，客戶在線選擇行為具有隨機性的特點，網絡零售商無法準確預知每個時隙選項的實際效用。因此，假設只考慮價格對消費者選擇行為的影響，則效用函數為

Uqt=U0-βhqt+εt,t∈T,q∈N

即當時隙價格增長時，其實際效用會有所減少。

綜上，基于Logit模型的選擇概率公式[18]為

這里假設接受、取消、放棄訂單這三個動作相互獨立，且僅與當前客戶有關。時隙選擇概率是通過零售商根據消費者對時隙價格的偏好建立的Logit模型，預測消費者選擇特定時隙的概率，通過該概率選擇相應動作，得到即時收益。這里默認消費者選擇概率為系統預測的消費者選擇概率。

1.3 基于超售策略的時隙運能分配模型

(1)狀態空間。根據系統對當前訂單采取的動作計算Q(sq,atm)后，再次更新訂單配送計劃表和已經獲得的收益。

(2)超售點的確定。一般，與取消的訂單相對應的運能是無法或很難“收回”的，故采用運能超售策略，即承諾出更多的運能來平衡由于訂單取消而閑置的運能。利用由訂單取消行為導致配送資源浪費而產生的機會成本建立時隙運能超售點，研究取消訂單行為下的時隙運能超售策略。如何確定一個合適的超售范圍是一個重要問題。如果超售范圍過大，雖然能在第一時間滿足客戶，但是沒有足夠的運能或者存貨提供給消費者，則產生商家口碑下降、賠償等一系列問題，從而產生懲罰成本D；如果超售范圍過小，則沒有了采取超售策略帶來的電商利潤的提高。同時，超售范圍過小將會導致訂單量與庫存量的不平衡，從而產生失銷成本W。因此，當前訂單采取超售策略產生的總成本表達式為

minf(b)=Dmax{b+Cmax-θq,0}+

Wmax{θq-b-Cmax,0}

式中，b為超售點，即b為比車輛最大運能多承諾出的運能。通過軟件模擬找出即時收益Rqt中涉及的最優超售點b*。這里默認每輛車的最佳超售點相同。

(3)即時收益的建立。強化學習的目標是經過若干次迭代后獲得最大值，因此系統在處理每個訂單時都會產生一個即時收益Rqt：

其中：式(1)為系統接受并完成訂單的即時收益，其中f(b*)為最優超售點下的懲罰成本；式(2)表示系統取消訂單，但由于促銷期間的特價商品數量有限，取消訂單時將收取部分費用，k∈[0,1)；式(3)表示系統放棄訂單。

1.4 Q學習算法求解

采用Q學習算法來進行訂單決策，其基本更新規則如下：

Q(sq,atm)←(1-α)Q(sq,atm)+

α(Rqt+γmaxQ(sq+1,atm))

(4)

從式(4)可以看出，學習速率α越大，新的Q值保留上一個Q值越少，即Q值變化越快，α∈[0,1]。如果α→0，那么Q(sq,atm)的估計值將以概率1收斂到最優值。

式(4)中γ為折扣因子，反映未來收益對當前收益的影響程度，故Rqt+γmaxQ(sq+1,atm)為訂單q在當前狀態sq下選擇動作atm的即時收益與訂單q在下一個狀態sq+1選擇動作atm后獲得的最大累計收益之和。

綜上，基于Q學習算法、考慮取消行為的在線訂單運能分配問題算法如下：初始化Q函數和配送計劃表；輸入每輛車的運能限制Cmax和即時收益矩陣；設定強化學習迭代次數，開始處理訂單。訂單處理過程：第1步，根據訂單價格，基于利用Logit模型得到的接受、取消、放棄概率來選擇動作，得到即時收益Rqt。如果訂單配置的時隙t和車輛m未超過最大運能Cmax則選擇動作atm(t∈{0}∪T,m∈M)，否則系統自動選擇同時隙其他車輛。a0m為客戶取消訂單，此時收益只有klq。如果所有時隙和所有車輛都超過了最大運能則選擇動作a00，即放棄訂單。第2步，根據式(4)更新Q(sq,atm)。第3步，完成當前訂單，狀態初始化為sq+1→sq。最后，計算下一個訂單直至結束。

2 算例分析

為分析超售策略在在線訂單時隙運能分配問題上的有效性，利用MATLAB 2014a進行算例模擬，模擬中的假設條件均從實際出發。

假設促銷期間的配送時間區間為6:00—21:00，時隙長度為3 h，時隙1～5對應的時間區間分別為6:00—9:00、9:00—12:00、12:00—15:00、15:00—18:00、18:00—21:00。共有4輛車配送。訂單初始配送計劃(也稱車輛與時隙的初始運能分配)見表1，定義了每輛車在對應時隙下需要完成的初始訂單任務數。假設每輛車在每個時隙的初始運能限制為50 unit，為每個訂單隨機分配的運能為1、2、3 unit，隨機產生的商品收益為100～400元/unit，時隙價格依次為25、20、15、10、5元。假設在促銷期間0:00—6:00內按照泊松分布到達300個訂單，參數λ=3。對這部分訂單進行運能配置。設置強化學習次數為500，α=0.98,γ=0.99,U0=20,β=0.1。運能超售點b=2 unit，失銷成本W=4元,懲罰成本D=2元，取消率k=1/10。

表1 訂單初始配送計劃 unit

2.1 運能分配

當今促銷活動，如雙十一、雙十二等，都是在0點開啟的，在6點開始配送時已有大量訂單等待配送，這說明假設符合實際情況。同時，電商權衡收支時會盡可能降低成本，充分利用配送能力，在已有的配送任務基礎上，加入新訂單，既節省成本，也均勻分配每輛車在每個時隙的配送任務。雖然訂單的到達、價格是隨機的，但是經過多次運算，在指定超售點和取消率的情況下，得到的平均收益與運能分配狀況匹配，說明模型結果具有普遍性，符合實際。分配結果見表2。300個訂單中有32個訂單放棄，有25個訂單取消。結果也證明Q學習算法適用于在線訂單運能分配問題。

表2 訂單最終配送計劃 unit

分析表1和2可以發現，初始配送計劃中有車輛在某些時隙沒有配送任務，如車輛3在時隙1(6:00—9:00)的被安排的運能為0，這無疑是一種運能浪費。通過Q學習算法對到達的訂單分配后，車輛在不同時隙上的運能得到均衡分配。從結果看，顧客從0點開始下單，訂單從6點開始配送，在中午12點之前和晚上18點之后(對應時隙1、2和5)配送車輛幾乎全部到達其運能限制，而時隙3(12:00—15:00) 次之，這符合顧客需求的實際情況。

2.2 最優超售點的確認

為確定最優超售點，根據以上參數設定運行軟件，得到在運用強化學習進行運能分配時不同超售點對總收益的影響，見圖1。從圖1可以明顯看出，在取消率為1/10，b為9 unit時總收益最大。b為0(即不采用超售策略)對應的是陳淮莉等[5]提出的基本訂單系統模型，在這個模型中零售商的總收益明顯低于采用超售策略的總收益，沒有到達最優值。

圖1 不同超售點對總收益的影響

然而，當b超過9 unit時總收益開始減少，當b超過16 unit時總收益會小于未采用超售策略時的總收益，此時b再增加已沒有意義。因此，在當前設定的條件下9 unit為最優超售點。

2.3 取消率對超售點的影響

在取消率為1/10時，最優超售點為9 unit。為進一步探索影響總收益的因素，分析采用不同取消率時零售商的總收益和最優超售點的變化，結果見表3。

表3 采用不同取消率時總收益增加率和最優超售點的變化

由表3可見，取消率從0開始增加時，總收益和最優超售點大體趨勢是增長的。在取消率為0時，最優超售點為1 unit，此時總收益最低；隨后總收益和最優超售點持續增長，在取消率為1/4時總收益最大，此時最優超售點為10 unit；當取消率增加到1/2時，總收益和最優超售點出現下降趨勢。表3表明，不同取消率對應的最優超售點是不同的，在消費者選擇不確定的情況下，互聯網零售商采用超售策略提高利潤是可行的，并且消費者選擇不確定性越大越有益。同時，隨著取消率的增加，最大超售點也增加，但存在很大風險，互聯網零售商應該慎重考慮。

2.4 懲罰成本對超售點的影響

當懲罰成本D=2,10,20,40,60,80元時,最優超售點為9 unit;當懲罰成本D=100,120,140,160,180,200元時,最優超售點為8 unit。由此可見：懲罰成本D的改變不會對最優超售點產生太大的影響；即使懲罰成本增加了100倍，最優超售點也只降低了1 unit。

3 結束語

在電商領域，對電商商家來說，消費者的需求波動比較大，在線訂單取消行為比較常見，采用傳統訂單處理方式很難在激烈的同行競爭中取得優勢。采用超售策略應對在線訂單取消行為，“回收”由取消行為產生的空閑配送能力以達到提高收益的目的。

根據消費者對時隙價格的偏好，建立考慮取消率的Logit模型，得出強化學習中的動作選擇概率，并設置時隙運能超售點等分配規則。模型結果顯示：強化學習能使訂單運能均勻分配，有效解決資源浪費問題，降低成本；根據由客戶訂單取消行為導致配送資源浪費而產生的機會成本建立時隙運能超售策略，相比傳統方式，采用超售策略能夠提高總收益，且在最優超售點時總收益最大；得出不同取消率對應的最優超售點和收益增加率，為商家制定相關銷售運輸策略提供參考。今后的研究將考慮在不放棄訂單的情況下，通過延遲配送或者提前預定來預分配運能的方式緩解促銷期間的配送壓力。