基于漸進服務半徑的自提柜選址算法①

肖卡飛, 孫 詠, 王 嵩, 田 月, 王美吉

?

基于漸進服務半徑的自提柜選址算法①

肖卡飛1,2, 孫 詠2, 王 嵩2, 田 月2, 王美吉2

1(中國科學院大學, 北京 100049)2(中國科學院沈陽計算技術研究所, 沈陽 110168)

物流“最后一公里”是直接面向客戶服務的物流末端環節, 直接影響到物流的效率、成本和服務質量. 針對此“最后一公里”問題, 提出基于自提柜的末端物流配送解決方案. 通過引入自提柜漸進服務半徑的概念, 用需求點到自提柜的距離來刻畫需求點對自提柜的服務滿意度,并用凹凸函數來表示, 建立自提柜選址問題的混合整數規劃模型. 同時, 充分考慮模型的各項約束性條件, 設計出啟發式拉格朗日松弛算法并進行模型求解. 最后, 運用大量算例進行檢驗, 分析算法的迭代次數、迭代時間等指標, 證明選址模型的準確性和求解算法的有效性, 為實際工程應用提供了理論指導.

最后一公里; 漸進服務半徑; 服務滿意度; 混合整數規劃; 拉格朗日松弛算法

1 引言

物流行業的“最后一公里”問題, 是制約物流企業發展、影響用戶滿意度的一個重要因素[1]. 就目前而言, 部署自提柜成為各大物流企業或電商平臺解決“最后一公里”問題所采取的積極措施. 在我國, 智能自提柜的研發技術已經趨于成熟, 涌現出一批知名企業, 如豐巢科技、樂棧、鳥箱等[2]. 但是, 如何對自提柜進行選址、布局等問題, 國內外尚缺乏深入的研究. 并且, 合理地對自提柜進行選址才能保障效益最大化, 這是一個亟待解決的技術難題. 因此, 本文主要針對具有容量限制的自提柜選址問題進入研究, 提出對應的選址模型、設計求解算法.

2 相關工作

國外研究學者對無人交貨接收盒(Unattended reception box)[3], 遞送盒(Delivery box)和共享接收盒(Shared reception box)[4,5]等遞送方式進行研究, 并實證分析了自提點模式可以極大地減少運輸成本[6], 同時論證了兩種自提式服務模式中: 有人值守式CDP (Attended CDP)和無人值守式CDP(Unattended CDP)中的無人值守式CDP(即自提柜式自提點模式)能降低1/3的配送成本, 因此自提柜配送模式得到了業界和研究領域的雙重肯定. 雖然國內外鮮有直接對自提柜的服務半徑和選址問題進行的研究, 但是對于公共設施、應急設施甚至物流配送中心等選址研究已經積累了豐碩的成果. 因此, 自提柜作為一種基于覆蓋范圍的服務性公共設施, 也具有自己的服務覆蓋范圍, 即服務半徑. 楊曉農、王振蒙[7]等人對基于服務功能的公共設施的服務半徑理論進行研究并給出了服務半徑的界定、理論基礎和功能劃分. 楊珺[8]等人對一類帶服務半徑的服務站截流選址-分配問題進行了研究, 并給出對應的啟發式算法, 研究服務站的服務范圍. 楊曉飛[9]等人對公交服務半徑的影響因素進行了分析, 并給出了服務半徑的計算模型和評價方法. 同時也有學者對物流節點中服務半徑進行了更深一步研究. 江從發、龔國華[10]等人簡單分析了配送中心的服務半徑, 并描述了它的決定因素和決定方式, 同時分析了其實現最佳服務半徑、達到資源優化利用的一些建議. 高潔、李錦飛[11]分析了物流中心服務水平與服務覆蓋范圍之間的關系, 提出了一種基于服務水平約束的、綜合考慮物流節點的運輸成本、配送路線以及覆蓋范圍的網絡選址模型, 并設計了緊急搜索算法來求解該模型.

同時, 王非等人對國外學者研究成果進行總結匯總, 將離散選址問題詳細劃分8 類子問題[12], 其中覆蓋模型已被證明是用于解決選址問題的有效模型之一. 傳統的服務半徑的研究, 多假設需求者的空間距離在服務半徑覆蓋范圍之內, 將100%接受到該設施點的服務; 而超出服務半徑的覆蓋范圍則100%不接受該設施點的服務, 這種“非黑即白”的評價方式, 屬于經典的“二元”覆蓋問題. 隨著研究的深入, 學者逐漸放松了對完全覆蓋的條件限制, 發展了多種覆蓋情況的理論. 喬聯寶[13]對覆蓋類選址問題進行了分類, 并在其基礎上給出了各類覆蓋問題的數學模型和各類模型之間的內在聯系. Daskin[14]和Batta[15]等人基于需求點被服務半徑覆蓋的不確定性研究, 研究了最大覆蓋問題. Home[16]基于服務半徑的固定與可變情況, 討論了條件覆蓋下選址問題的動態規劃算法. Hassin、Segev[17]研究了可變服務半徑的選址問題, 但未對可變半徑對服務滿意度的影響進行深入定義. Drezner等人[18]提出漸進覆蓋模型來解決需求者選址滿意度問題. 不同于傳統“二元”覆蓋問題之處, 漸進覆蓋細化覆蓋粒度, 將“非1即0”的二元覆蓋假設拓展為多元覆蓋假設[19], 將覆蓋定義為基于覆蓋距離的非增函數, 取值范圍為[0,1][20], 但是未考慮服務容量的限制. 褚玉婧[21]提出時間滿意逐漸覆蓋電動汽車充電站選址及算法給本文帶來一定的啟發.

本文在漸進覆蓋的理論基礎上, 提出了基于漸進服務半徑的自提柜選址模型, 充分考慮服務半徑覆蓋范圍對需求者滿意度的影響. 此外, 在模型建立過程中, 綜合考慮自提柜的服務容量、服務半徑、及需求點的需求量等約束性條件, 對實際生產生活中物流企業、電商企業等布局自提柜提供了科學的決策指導.

3 自提柜選址模型

3.1 問題描述

自提柜作為向客戶提供物流服務的末端公共服務設施, 其選址定位問題和服務容量限制, 不僅關系到物流企業的成本投入和市場覆蓋范圍, 更關系到客戶對服務質量滿意度評價. 通常距離高密度客戶聚集區越近, 越能夠提高自提柜的服務范圍; 合理的服務容量既關系到物流企業的成本投入又關系到各區域實際需求量來合理規劃.

3.2 符號聲明

同時定義如下決策變量:

3.3 模型假設

假設1. 不考慮同行業其他競爭者同類設施對本自提柜用戶使用情況的影響;

假設2. 使用者的服務半徑滿意度函數用覆蓋距離的凹凸函數來描述, 且對同一類型的自提柜, 所有的使用者均服從同樣的覆蓋函數;

假設3. 不考慮自提柜設施的建設成本(包括設施占地成本、器材成本及運營和維護成本).

3.4 服務滿意度函數

作為一種商用的公共服務設施, 自提柜有自己的服務半徑, 且在其最小服務半徑覆蓋距離內需求點可以被完全覆蓋, 在其最大服務半徑覆蓋距離外的需求點則是完全不可覆蓋的, 而兩者之間的需求點則是基于一定概率非增的可覆蓋情況. 其中完全覆蓋表示很滿意、不可覆蓋表示很不滿意、可覆蓋表示不同程度的滿意度, 用此概念來描述基于覆蓋距離的需求點的服務滿意度函數.

采用問卷形式對客戶對周圍服務網點距離的滿意度調查情況進行統計分析, 得出在一定距離內客戶可以完全接收, 但超過某一距離, 用戶會選擇性地接收服務, 直至更遠的距離, 用戶完全不接受其網點的服務. Berman和Krass[22]提出基于距離的凹凸函數, 比較貼切現實生活中距離與覆蓋水平的關系, 較好地模擬真實情況.

3.5 模型建立

目標函數:

約束條件:

目標函數(2): 使得總的服務半徑覆蓋范圍最大化和選址效益最大化;

約束條件(3): 每個需求點只能選擇一個設施點提供服務, 默認情況下, 當一個需求點被多個自提柜服務范圍覆蓋時, 選擇距離最近的自提柜接受服務;

約束條件(6): 確保所有自提柜設施點對每個需求點提供的服務不超過其需求量;

約束條件(7): 確保所有需求點對每個自提柜設施點的供應量不超過其容量;

約束條件(8)、(9): 變量取值約束.

4 模型分析與求解

4.1模型分析

以上建立的選址模型是一個混合整數規劃模型, 屬于NP-hard問題, 隨著問題規模的增大或約束條件的增多求解復雜度呈指數增長, 因此在實際應用中, 一般會采用啟發式算法進行求解, 故本文設計了基于次梯度算法和拉格朗日松弛法的啟發式模型求解算法.

4.2 模型求解

算法分析: 對于NP-hard問題, 最常用的求解方法就是構造啟發式算法, 以求盡量接近最優解的可行解. 拉格朗日松弛算法就是求解下界的一種方法, 它的基本原則是將造成問題求解困難的約束條件吸收到目標函數中, 并保持目標函數的線性, 使問題容易求解, 并且實現比較簡單和有比較好的性質. 算法的執行過程主要分為兩個階段: 第一階段為求松弛后的線性規劃問題的最優解; 第二階段為將解整數化, 并考慮其可行性. 在本模型中, 通過分析(3)-(9)的約束條件, 認定條件(3)是“困難約束”, 其余為“簡單約束”.

為保證對搜索步長的控制, 將約束式(3)放到目標函數(2)中, 得到拉格朗日松弛問題(2).

目標函數:

約束條件:

(4)至(9)

其中, 令

本文利用次梯度優化來調整拉格朗日乘子的值, 以此逼近最優解, 拉格朗日乘子計算過程如下所示.

算法執行步驟如下: (說明: 基于次梯度算法和改進拉格朗日松弛法的啟發式算法)

Step 2. 求解拉格朗日松弛問題. 按以上計算方法計算出,.

Step 9. 終止條件判斷. 若滿足如下任何條件, 即結束迭代過程.

5 實驗仿真

5.1數據集及運行環境

需求點數據集: 本文通過隨機算法, 日需求量按照正態分布產生, 需求點到自提柜點的空間距離按照正態分布產生, 需求點個數分別為100、400、1000的三個數據集.

實驗環境: 運行環境: Matlab R2013a; 操作系統: Windows 7 旗艦版 64位; 處理器: 英特爾第二代酷睿 i5-2320 @ 3.00GHz 四核; 內存: 4G.

5.2實驗結果分析

實驗結果表明, 拉格朗格松弛算法在求解0-1整型規劃問題上具有良好的運算效果, 見表1和圖1.

表1 不同算例下, 拉格朗格松弛算法運行情況

圖1 上下界誤差(%)隨迭代次數增加的變化情況

觀察表1可得: 除No.1之外上下界誤差絕大部分情況下在3%以下; 平均迭代次數在100到300之間; 覆蓋率平均在80%以上, 且隨著選址數的增加均能達到較高的覆蓋率; 而算例的運行時間均是在30s之內, 不過隨著需求點數據量的增多, 算例的運行時間有明顯的增長趨勢. 然而, 拉格朗日松弛法可以對最優解的上下界進行估計, 在實際工程問題中, 可以根據不 同需要對參數進行相應的調整, 如迭代次數、步長等參數, 以達到自己可接收的近似近似最優解.

6 結語

自提柜配送模式是近年來物流領域發展迅猛的新型配送方式. 本文通過引入自提柜漸進服務半徑的概念, 基于需求點到自提柜的距離來刻畫需求點對自提柜的服務滿意度函數, 建立了自提柜選址問題的混合整數規劃模型, 并設計啟發式算法進行求解. 通過運用大量算例分析, 驗證了模型的準確性和啟發式算法的正確性, 證明了求解算法具有很強的收斂性, 同時對于現實生活中物流企業等進行自提柜選址具有很強的指導意義. 但本文中未考慮不同地域及不同服務容量的自提柜建設成本因素, 以及同一地域中不同企業之間同類末端物流方式存在對需求點的競爭關系, 會對模型的準確性和穩定造成一定的影響, 未來本文將對此進行深入研究, 建立更穩健的基于競爭關系和服務成本自提柜選址模型.

1 周速華.以用戶體驗為核心贏在最后一公里.現代家電, 2015,(3):27–29.

2 劉柳,馬英才.智能物流上演“最后一公里”爭奪戰.互聯網經濟,2014,(7):16–19.

3 McKinnon AC, Tallam D. Unattended delivery to the home: an assessment of the security implications. International Journal of Retail & Distribution Management, 2003, 31(1): 30–41.

4 Punakivi M, Yrjoèlaè H, Holmstroèm J. Solving the last mile issue: Reception box or delivery box. International Journal of Physical Distribution & Logistics Management, 2001, 31(6): 427–439.

5 Punakivi M, Tanskanen K. Increasing the cost efficiency of e-fulfilment using shared reception boxes. International Journal of Retail & Distribution Management, 2002, 30(10): 498–507.

6 McLeod F, Cherrett T, Song L. Transport impacts of local collection/delivery points. International Journal of Logistics, 2006, 9(3): 307–317.

7 楊曉農,王振蒙.基于服務功能的公共圖書館服務半徑理論研究.圖書館,2014,(6):17–19.

8 楊珺,張敏,陳新.一類帶服務半徑的服務站截流選址-分配問題.系統理論與實踐,2006,26(1):117–120.

9 楊曉飛,馬健宵,仲小飛.公交服務半徑及服務水平研究.森林工程,2011,27(1):61–64.

10 江從發,龔國華.配送中心最佳服務半徑分析.物流技術,2003,(9):19–20.

11 高潔,李錦飛.基于服務水平的區域物流中心優化選址模型研究.物流技術,2005,(10):279–281.

12 王非,徐渝,李毅學.離散設施選址問題研究綜述.運籌與管理,2006,15(5):64–69.

13 喬聯寶.覆蓋類選址問題分類及研究綜述.物流科技,2015,38(3):59–66.

14 Daskin M. A maximum expected covering location model: fprmulation, properties and heuristic solution. Transportion Science, 1983, 17(1): 48–70.

15 Batta R, Dolan J. The maximal expected covering location problem: Revisited. Transportation Science, 1989, 23(4): 277–287.

16 Home J, Smith J. Dynamic programming algorithms for the conditional covering problem on path and extended star graphs. Networks, 2005, 46(4): 177–185.

17 Hassin R, Segev D. The multi-radius cover problem. Lecture Notes in Computer Science, 2005, 3608: 24–35.

18 Drezner Z, Wesolowsky GO, Drezner T. The gradual covering problem. Naval Research Logistics, 2004, 51(6): 841–855.

19 Saaty TL. Fundamentals of Decision Making and Priority Theory with the Analytic Hierarchy Process. RWS Publications, 1994.

20 Berman O, Krass D. The generalized maximal covering locationproblem. Computers & Operations Research, 2002, 29(6): 563–581.

21 褚玉婧,馬良,張慧珍.時間滿意逐漸覆蓋電動騎車充電站選址及算法.數學的實踐與認識,2015,45(10):101–106.

22 Berman O, Krass D. The generalized maximal covering location problem. Computers and Operations Research, 2002, 29(6): 563–581.

Location Algorithm of Lifting Cabinet Based on Gradual Service Radius

XIAO Ka-Fei1,2, SUN Yong2, WANG Song2, TIAN Yue2, WANG Mei-Ji2

1(University of Chinese Academy of Sciences, Beijing 100049, China)2(Shenyang Institute of Computing Technology, Chinese Academy of Sciences, Shenyang 110168, China)

The “last mile” in logistic is the terminal link of logistic service for users, and directly affects the efficiency, cost and service quality of logistic. This paper presents a solving method based on lifting cabinet for the “last mile” in logistic (this problem). Based on the concept of gradual service radius, and the relationship between service satisfaction and distance from the demand point to lifting cabinet, this paper proposes a mixed integer programming model for lifting cabinet’s location problem. Moreover, this paper designs a heuristic Lagrange’s relaxation algorithm by taking into full account of the various constraints factors to solve the model. Finally, illustrative examples further analyze the number of iterations, iteration times and other indicators, which show the correctness of the results in this paper and the good performance of the proposed method.

last mile; gradual service radius; service satisfaction; mixed integer programming; Lagrange’s relaxation algorithm

2016-06-12;

2016-07-25

[10.15888/j.cnki.csa.005630]