基于強化學習的電商促銷期時隙運能柔性分配研究

唐 微，陳淮莉

（上海海事大學 物流研究中心，上海 201306）

0 引言

隨著電子商務在零售業的深入滲透以及互聯網應用的普及，電商發展迅速，其競爭焦點逐步從價格轉向顧客服務體驗，而配送服務水平直接影響顧客的滿意度。時隙（time slot或 delivery slot）是指電商在網站平臺上提供給顧客選擇的訂單配送的時間區間[1]，但目前我國只有少部分電商能為顧客提供準確的商品送達時間，尤其是在“雙十一”、“6.18”年中大促等促銷活動中，顧客瘋狂下單使得訂單量在短時間猛增，而呈現井噴狀態的銷售量缺少相應配送能力支持，造成交付期延長、快遞爆倉、顧客滿意度低等現象[2]。因此面對促銷期間激增的訂單，為了盡可能的降低交付成本和均衡時隙的需求波動，更高效的完成所有訂單的配送，網絡零售商必須根據自身的交付能力來合理規劃其時隙運能。

目前，國內外學者關于時隙的研究主要集中在時隙動態定價、訂單分配和物流配送路徑規劃等方面。K.Asdemir[3]等人的研究對網絡零售商提供的不同的交付時隙進行動態定價，考慮需求的不確定性并將顧客分級，通過控制每個顧客等級的動態價格建立完整的分配模型。Corolli[4]等以航空公司航班時隙分配為例，建立了兩個隨機規劃模型，并對比顧客要求的時隙和實際可能延遲配送的時隙之間的時間差，針對減少航班延誤問題提出時隙運能分配的方法。Lin[5]研究了不同配送策略對互聯網零售電商運作的影響，分別從車輛數量、時隙數量、時隙寬度、配送時間等時隙配置方面因素進行分析，并提出因為顧客提供高水平的服務而導致更高的交付成本的時隙分配方法。

一些學者從整數規劃和動態規劃角度研究了動態的時隙訂單分配策略和能力分配問題。但是，在時隙運能分配問題中，不確定的因素很多（如客戶選擇行為不確定性、交付期、時隙價格等），強化學習（Reinforcement learning，RL）對于解決馬爾可夫決策過程的訂單分配問題有更好的仿真效果[6]。劉夢婷[7]等運用強化學習思想來解決供應鏈管理中的訂單制定問題，來減少牛鞭效應所帶來的影響，通過算例證明基于強化學習的訂單制定策略比傳統的固定庫存策略能獲得更高的收益。國外學者Snoek[8]使用強化學習算法研究了生產型企業的訂單分配問題，通過仿真得到采用強化學習的方法對于解決此類問題有更好的效果。國內學者王曉歡[9]等人針對訂單生產型企業在訂單接收過程中的不確定性，基于強化學習的思想，引入顧客等級這一要素，從收益管理的角度建立了基于半馬爾科夫決策過程，結果驗證了引入顧客等級的必要性和重要性。陳淮莉[10]等人從價格和交付期對顧客選擇時隙的影響進行分析，采用強化學習的方法并結合時隙運能分配特點對于到達的訂單群做出運能分配，驗證了強化學習解決時隙運能配置問題的可行性和有效性。

并且，以上研究通常不是針對某一特定時期進行的，時隙運能分配的方式也過于單一，對于訂單只能接受或拒絕。而本文基于我國電商配送的特點，針對促銷期間這一時期，從顧客選擇行為分析出發，為顧客提供準時配送和延遲配送兩種配送模式以均衡時隙需求，并建立馬爾可夫決策過程的時隙運能柔性分配模型，采用強化學習方法研究時隙運能柔性分配策略問題，為網絡零售商合理安排促銷期間車輛運能及顧客滿意度提供有效建議。

1 問題描述與模型概述

1.1 問題描述

在電商促銷期間的大環境下，訂單量激增，車輛負荷過大。由于車輛運能的限制，并不是所有訂單都能夠按時發貨與配送，則存在取舍問題。因此考慮到時隙的運能限制和訂單處理過程的動態性，根據顧客對交付期和價格的偏好，為顧客提供兩種時隙選擇：準時配送（F模式）和延遲配送模式（S模式）[11]，從而緩解電商促銷期間的配送壓力，將促銷期間的訂單分攤到促銷期后的時間配送。通過對車輛的運能柔性分配，即替代配送和外包配送最大限度的完成所有訂單的配送。使商家的利潤得到保證，同時盡可能的提高顧客滿意度。

1.2 模型概述

在線訂單處理過程是一個動態決策過程，訂單的到達使系統狀態不斷改變，而且當前的訂單轉移與之前的發展狀況無關，具有無后效性，符合馬爾可夫決策過程[12]。因此本文將在線訂單處理過程抽象成半馬爾科夫決策過程模型，并采用強化學習策略中的Q-learning算法進行求解，根據訂單的特性不斷選擇較好的分配策略，強化此策略的動作選擇，從而整個過程達到最優。本文將強化學習與時隙運能分配問題的融合思路如圖1所示。

圖1 強化學習與時隙運能分配問題融合思路

2 基于馬爾可夫決策過程的時隙運能柔性分配模型

2.1 符號說明

集合：D表示選擇配送時隙當天的日期集合，d=1,2,3,…,n'，d∈D。d=1表示顧客選擇時隙t配送的當天為第一天，d'表示延遲天數。當d≤d'時，即顧客選擇延遲期限內的時隙t進行配送，為準時配送模式；當d＞d'時，即顧客選擇延遲期限后的時隙t進行配送，為延遲配送模式；I表示配送時隙選項集合，t=1,2,3,…,n，t∈I；V表示配送車輛集合，v=1,2,3,…,m，v∈V；V'表示外包配送車輛集合，v'=1,2,3,…,m'，v'∈V'；O表示訂單集合，q=1,2,3,…,k，q∈O。

參數：β表示顧客對時隙價格的偏好系數，η表示顧客對價格的偏好系數，表示效用函數的隨機變量，服從Gumbel分布；表示訂單q的初始預計效用（受歡迎度）；fq表示訂單q的價格；ft表示選擇延遲配送比選擇準時配送模式下時隙價格的折扣金額；fv'表示訂單使用外包車輛配送產生的額外成本；W表示每個時隙t固定的配送能力；α表示狀態函數更新迭代的學習速率；γ表示狀態函數更新迭代的折扣因子；λ表示訂單到達率。

變量：表示所選時隙的中間時刻；表示顧客的下訂單的時刻；表示訂單q選擇時隙t的即時收益；表示訂單q選擇時隙t的實際效用；表示顧客在下達訂單q時，選擇時隙t的概率；表示訂單q選擇配送時隙t的時隙價格；Nt表示顧客對時隙t的需求；表示訂單q選擇動作時的值函數。

2.2 時隙選擇模型

本文假設只考慮時隙價格和交付期偏好對顧客的影響，針對促銷期間時隙需求大的特點，為顧客提供準時配送模式（F模式）和延遲配送模式（S模式）這兩類時隙選項，以此引導顧客的選擇，均衡時隙需求。F模式提前期短，價格高；S模式提前期長，但價格給予一定的折扣，較低。顧客可根據自身的情況進行選擇。采用線性效用函數來表示顧客對于不同價格和提前期時隙的選擇行為，并根據效用最大化原則預測每個時隙選項對顧客實際效用[13]。則時隙t對顧客的實際效用可表示為：

對于配送時隙時間要求較高或急需收到購買物品的顧客，通常愿意支付高價選擇較短交付期的時隙，即F配送模式，時隙t的交付期越長，該時隙的實際效用也會越小；對因促銷進行囤貨而對配送時間要求不高的顧客，愿意選擇帶有折扣價格的時隙而等待較長的配送時間，即S配送模式，當時隙t的價格減小的時候，其實際效用會相應增加，對顧客的吸引更強。顧客在促銷期間選擇時隙時，根據自己的需求綜合考慮價格和交付期的影響，進行時隙選擇。

以下是根據效應函數建立Binary Logit選擇概率模型[14]，將通過此模型預測出顧客選擇未來某時隙的概率，作為系統預測顧客選擇訂單配送時隙的概率。則顧客訂單q選擇時隙t的概率為：

2.3 時隙運能柔性分配模型

基于馬爾可夫決策過程來研究，促銷期間時隙運能柔性分配的過程可以表述為：新訂單的到達使系統進入一個新狀態，系統根據客戶選擇模型預測的時隙選擇概率，為每一個訂單分配動作，即分配時隙和車輛。直到所有訂單處理完畢，得到最優的時隙運能分配表和收益。強化學習各要素的定義如下：

1）狀態集S：

假設時隙運能柔性分配模型的環境狀態由隨機到達的新訂單q所決定，每到達一個訂單，時隙運能柔性配送計劃表P和收益Q均發生改變，從而系統的環境狀態S發生變化，因此環境狀態可以用S=(P,Q)表示。狀態集S對新到達的訂單q會不斷更新計劃表P和收益Q。

2）動作集A：

當系統面對訂單到達時，需根據顧客的時隙選擇概率和車輛運能限制對負責訂單配送的時隙和車輛進行分配。可以采取3種動作選擇：（1）當所分配車輛運能未滿時，由該車輛v配送；（2）當所分配車輛運能已滿時，由同時隙內其他車輛進行替代配送；（3）當時隙內所有車輛運能全滿時，由外包車輛v'進行外包配送。當新訂單到達時，對新訂單重新選擇動作，即分配時隙和車輛。A表示強化學習的動作集合，

3）立即回報函數：在強化學習的應用中，立即回報函數是指從一個動作的反饋中計算回報的函數，即完成每筆訂單所獲得的收益。立即回報主要包括訂單價格fq、所選擇時隙價格Cdqt和外包車輛的費用fv'，因此狀態S，即訂單q的即時收益rdqt表示為：

其中，xt和yt均是0～1變量。xt表示當顧客選擇F配送模式時，xt=0，時隙價格無折扣；否則顧客選擇S配送模式，時隙價格有折扣。yt用來判斷是否產生外包車輛的額外費用。當時隙需求大于車輛總運能時等于1，否則為0。其中顧客訂單的到達率用λ表示，則表示顧客對每個時隙t的需求。

3 基于強化學習Q-learning算法的模型求解方法

3.1 Q-learning算法

Q-learning算法是強化學習中非常重要的算法之一，其主要用于求解馬爾可夫決策模型的最優值函數和最優值策略問題。通過建立Q值表，比較狀態S下每個動作A的Q(s,a)值，系統將選擇具有最大Q值的動作到達下一狀態，并不斷更新Q值，進而得到最優的累積Q值[15]。而且通過對每個“狀態-動作”對不斷選擇和重復，保證了學習過程的收斂性。此算法不需要考察所有的后續狀態,因此簡化了決策過程。因此選用Q-learning算法來解決時隙運能分配問題。

其更新規則如下：

其中Q(sq,atv)表示當前訂單q選擇動作atv所獲得的累計收益；α為學習率，隨著α趨向于0，值函數Q(sq,atv)將會收斂到最優策略；γ為折扣因子(0≤1＜1)。上式采用了無限范圍衰減模型，即考慮系統長遠的獎勵情況，同時基于一定的衰減因子γ對其進行幾何衰減。

3.2 模型求解算法設計與步驟

基于Q-learning算法的車輛時隙運能柔性分配過程如圖2所示。

具體解釋如下：

初始化Q值表、配送計劃表P、車輛運能限制表和即使收益矩陣R；設置學習步數；設置狀態轉移概率為1；初始化模型中的參數值。開始系統仿真，一直循環到處理過所有訂單結束。

對于每一個訂單q均重復以下過程：

Step1：根據logit選擇概率模型選擇動作atv，獲得相應即時收益rdqt：1）在時隙t車輛v上添加該訂單，若未超過車輛v運能配置的最大值，則選擇動作atv；否則，系統將自動選擇同時隙的其他運能未滿車輛為該訂單進行替代配送；2）如仍超過該時隙所有車輛運能最大限制，則采用外包車輛進行配送。

Step2：處理下一訂單q，得到下一狀態S'，依據下式更新規則更新狀態-動作值Q(sq,atv)：

圖2 基于Q-learning算法的時隙運能分配策略的流程

Step3：更新q←q+1，處理下一個訂單；否則找出每個狀態下的最優動作，獲得最優策略。

3.3 探索與利用

強化學習通常存在著探索與利用之間的平衡問題。探索是不斷嘗試新動作，尋求獲得更多獎勵的動作；而利用使系統更傾向于采取先前收到最大回報的動作。-greedy策略是比常用方法之一，但本文結合顧客時隙選擇行為的特點，以Logit客戶選擇概率來探索和利用，不以獲得的獎勵最大為探索利用依據，而是在考慮顧客自身情況以及時隙運能限制前提下，綜合考慮各種時隙運能分配的策略，尋求最優策略達到較高的收益。

4 算例分析

假設前三天為促銷期，后四天為正常銷售日期，討論七天的車輛時隙運能分配情況。因此在前三天為顧客提供F配送模式和S配送模式兩類時隙選項，并假設延遲天數為3天。每天可供顧客選擇配送時間的范圍為每天的8點到20點，時隙寬度是3個小時，每天的時隙均為8點～11點、11點～14點、14點～17點、17點～20點，共有4輛商家自營車輛可用來計劃分配，每輛車每個時隙的運能限制均為25個單位。

正常配送模式是指不為顧客提供延遲配送的選項且對運能不足的訂單不采用外包配送，即不采用以上柔性配送的方式。此模式下當訂單分配到的運輸車輛和所選時隙內的替代運輸車輛均無法承擔配送任務時，訂單會因沒有車輛運能而被拒絕，而柔性配送模式則由外包車輛進行配送。假設訂單價值服從均勻分布[100,400]，每天固定時間段內顧客訂單按泊松分布到達，如表1所示。

表1 各時段訂單到達的數量

采用matlab2016a對柔性配送模式和正常配送模式這兩種模式進行算例模擬仿真，設置強化學習訓練次數為1000，兩種模式下的參數設置如表2所示。

4.1 柔性配送模式與正常配送模式對比

經過模擬運行，從表3結果來看，采用柔性配送模式時，所有訂單均可準時配送，只有第二天8:00～11:00以及第四天的11:00～14:00需要使用外包車輛進行配送，具有較高的訂單配送率。

此外，如圖3所示，將每天訂單到達量與兩種配送模式下實際配送量作對比，可以看出，運用柔性配送策略將促銷期間的高訂單量合理分配到促銷期之后進行配送，并且加入外包車輛的參與，使得每天配送約200個訂單，7天內完成全部1700個訂單的配送，車輛運能分配達到均衡。而采用正常配送模式，則因促銷期間訂單量大車輛運能不足，而放棄223個訂單，降低訂單配送率。

表2 相關參數設置

表3 促銷期前后每時隙每輛車時隙運能分配

圖3 柔性配送策略下訂單實際到達量對比

采用柔性配送模式下，網絡零售電商7天的總收益為151293元，正常配送模式114878元，雖然采用柔性配送模式采用外包車輛進行配送，會產生一定的額外費用，但通過均時隙需求，只有兩個時隙的訂單需用外包車輛配送，總體來說比采用正常配送模式收益要高。因此建議網絡零售商在促銷期間可為顧客提供準時配送和延遲配送兩種選項，使得顧客根據其自身情況選擇，緩解促銷期井噴的需求，同時配合使用外包車輛，不僅可以提高訂單配送率，而且利于均衡每天各時隙的配送運能，提高車輛利用率，降低配送成本。

4.2 交付期偏好對總收益的分析

1）交付期偏好系數對收益的影響

交付期是指顧客從預定訂單到訂單送達這一時間段，顧客在促銷期間對交付期的偏好程度直接影響其對時隙的選擇，進而影響商家的總收益。下圖是以柔性配送模式下第一天訂單時隙運能分配為研究對象，分別采用不同的交付期偏好系數，得到其變化對訂單總收益的影響。從圖中可以看出，交付期偏好系數與總收益成反比。顧客對交付期偏好越大，給總利潤帶來的波動就越大。當η=0.5時，即交付期偏好較小時，總收益隨著學習步數的增加也逐漸增加并趨于平穩，達到最大值，這說明當顧客對促銷期間交付期無太高要求時，更偏向選擇具有折扣價格的時隙，即會選擇S模式下的時隙，利于均衡時隙運能。這類顧客雖然也傾向于選擇交付期較短的時隙，但其并不愿意支付較高價格。因此交付期長短即促銷期間提供給顧客的時隙延遲天數，影響其對時隙的選擇，從而影響總收益。

圖4 不同交付期偏好系數下的總收益

2）延遲天數對顧客選擇概率的影響

以柔性配送模式第一天的顧客選擇概率為研究對象，當延遲天數d'=1,3,6時，分析提供不同延遲天數下顧客選擇概率的變化。從圖中可以看出，當延遲天數較小，即d'=1時，第二天的選擇概率非常高，這是由于選擇延遲配送的時隙具有折扣價格，且相較于選擇第一天的時隙，交付期相差不大，因此易導致7天內運能分配不均；當延遲天數中等，即d'=3時，顧客的選擇概率較為平穩，因第一天提前期較短及第四天的折扣時隙價格獲得偏高的選擇概率；當延遲天數較長，即d'=6時，因為交付期過長，即使時隙具有價格優勢，顧客仍不愿意選擇。

圖4 不同延遲天數下客戶的選擇概率

3）最優延遲天數

如圖，當d'=0即不提供延遲配送的選擇的正常配送模式下，總收益約為114878。當延遲天數較短時，上一部分已經分析過，顧客更傾向選擇具有價格優勢的延遲配送模式下的時隙，導致時隙運能分配不均，需要使用外包車輛進行配送，從而增加配送成本，降低收益；而當延遲天數過長時，顧客傾向選擇交付期較短的日期進行配送，放棄交付期較長時隙的選擇，浪費車輛運能，而導致收益出現負增長。確定合理的延遲天數才能引導顧客對時隙的選擇，得到理想的效益增長。如圖可見當延遲天數為3天時，總收益能夠達到最佳，且利潤增長率也是最高點。

圖5 不同延遲天數的利潤增長率和總收益變化

5 結束語

針對促銷期間電商時隙運能分配的問題，本文分析客戶選擇行為的影響因素，采用強化學習的思想，建立了基于馬爾可夫決策過程的時隙運能分配模型。通過對比發現，為顧客提供F配送模式和S配送模式的選擇以及采用替代配送、外包配送等柔性方式，使得促銷期前后的時隙需求均衡，提高訂單的配送率，減少車輛運能浪費，獲得更高收益。對于顧客交付期偏好的研究發現，交付期偏好越小，收益越大，并且延遲配送策略中延遲天數的大小，也影響著顧客對于時隙的選擇，最終算例結果表明，延遲3天為最優延遲天數，既均衡每天各個時隙車輛運能，又能夠獲得較大收益。同時驗證了強化學習的方法適用于解決促銷期間不確定、動態訂單的時隙運能分配的問題。

在未來的研究中，可以加入客戶滿意度因素，通過根據客戶服務水平來衡量時隙運能分配策略的效果，以獲得更高的客戶滿意度；本文采用的多項Logit模型還存在著“IIA”局限，即與其他選擇無關的特性，以后的研究可以采用嵌套Logit模型和混合Logit模型等其他離散選擇模型來更準確地預測消費者的選擇行為。

[1]Agatz N, Campbell A, Fleischmann M, et al. Time slot management in attended home delivery | NOVA. The University of Newcastle’s Digital Repository[J].Institute for Operations Research & the Management Sciences,2011.

[2]劉錦峰.大數據背景下電子商務物流配送發展對策研究[J].商業時代,2017,(2):98-99.

[3]Asdemirabc K.Dynamic pricing of multiple home delivery options[J].European Journal of Operational Research,2009,196(1):246-257.

[4]Luca Corolli.The time slot allocation problem under uncertain capacity[J].Transportation Research Part C,2014,46(46):16-29.

[5]Lin I I, Mahmassani H S.Can Online Grocers Deliver?: Some Logistics Considerations[J].Transportation Research Record Journal of the Transportation Research Board,2002,1817:17-24.

[6]Doya K. Reinforcement learning in continuous time and space[J].Neural computation,2000,12(1):219-245.

[7]劉夢婷,牟永敏,趙剛,歐陽騰飛.基于強化學習算法的供應鏈管理訂單策略研究[J].數據通信,2013,(1):22-25.

[8]SNOEKM.Neuron—genetic order acceptance in a job shop setting[A].Proceedings of the 7th International Confirence on Neural Information Processing.Seoul[C].2000:815-819.

[9]王曉歡,王寧寧,樊治平.基于強化學習的訂單生產型企業的訂單接受策略[J].系統工程理論與實踐,2014,34(12):3121-3129.

[10]陳淮莉,吳夢姣.基于強化學習的在線訂單配送時隙運能分配[J].上海海事大學學報,2017,38(2):51-55.

[11]李怡娜.基于顧客選擇行為的提前期和價格響應模式[J].系統工程學報,2016,31(4):460-470.

[12]Yifan Zhou,Lin Ma,Yong Sun.Maintenance strategy optimization using a continuous- state partially observable semi- Markov decision process[J].Microelectronics Reliability,2011,51(2):300-309.

[13]Campbell A M, Savelsbergh M. Incentive Schemes for Attended Home Delivery Services[M].INFORMS,2006.

[14]王爽,趙鵬.基于Logit模型的客運專線旅客選擇行為分析[J].鐵道學報,2009,31(3):6-10.

[15]Cheng Y. Real Time Demand Learning-Based Q-learning Approach for Dynamic Pricing in E-retailing Setting[A].International Symposium on Information Engineering and Electronic Commerce. IEEE[C].2009:594-598.