基于漸進(jìn)服務(wù)半徑的自提柜選址算法①

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

?

基于漸進(jìn)服務(wù)半徑的自提柜選址算法①

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

1(中國(guó)科學(xué)院大學(xué), 北京 100049)2(中國(guó)科學(xué)院沈陽(yáng)計(jì)算技術(shù)研究所, 沈陽(yáng) 110168)

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

最后一公里; 漸進(jìn)服務(wù)半徑; 服務(wù)滿意度; 混合整數(shù)規(guī)劃; 拉格朗日松弛算法

1 引言

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

2 相關(guān)工作

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

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

本文在漸進(jìn)覆蓋的理論基礎(chǔ)上, 提出了基于漸進(jìn)服務(wù)半徑的自提柜選址模型, 充分考慮服務(wù)半徑覆蓋范圍對(duì)需求者滿意度的影響. 此外, 在模型建立過(guò)程中, 綜合考慮自提柜的服務(wù)容量、服務(wù)半徑、及需求點(diǎn)的需求量等約束性條件, 對(duì)實(shí)際生產(chǎn)生活中物流企業(yè)、電商企業(yè)等布局自提柜提供了科學(xué)的決策指導(dǎo).

3 自提柜選址模型

3.1 問(wèn)題描述

自提柜作為向客戶提供物流服務(wù)的末端公共服務(wù)設(shè)施, 其選址定位問(wèn)題和服務(wù)容量限制, 不僅關(guān)系到物流企業(yè)的成本投入和市場(chǎng)覆蓋范圍, 更關(guān)系到客戶對(duì)服務(wù)質(zhì)量滿意度評(píng)價(jià). 通常距離高密度客戶聚集區(qū)越近, 越能夠提高自提柜的服務(wù)范圍; 合理的服務(wù)容量既關(guān)系到物流企業(yè)的成本投入又關(guān)系到各區(qū)域?qū)嶋H需求量來(lái)合理規(guī)劃.

3.2 符號(hào)聲明

同時(shí)定義如下決策變量:

3.3 模型假設(shè)

假設(shè)1. 不考慮同行業(yè)其他競(jìng)爭(zhēng)者同類設(shè)施對(duì)本自提柜用戶使用情況的影響;

假設(shè)2. 使用者的服務(wù)半徑滿意度函數(shù)用覆蓋距離的凹凸函數(shù)來(lái)描述, 且對(duì)同一類型的自提柜, 所有的使用者均服從同樣的覆蓋函數(shù);

假設(shè)3. 不考慮自提柜設(shè)施的建設(shè)成本(包括設(shè)施占地成本、器材成本及運(yùn)營(yíng)和維護(hù)成本).

3.4 服務(wù)滿意度函數(shù)

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

采用問(wèn)卷形式對(duì)客戶對(duì)周?chē)?wù)網(wǎng)點(diǎn)距離的滿意度調(diào)查情況進(jìn)行統(tǒng)計(jì)分析, 得出在一定距離內(nèi)客戶可以完全接收, 但超過(guò)某一距離, 用戶會(huì)選擇性地接收服務(wù), 直至更遠(yuǎn)的距離, 用戶完全不接受其網(wǎng)點(diǎn)的服務(wù). Berman和Krass[22]提出基于距離的凹凸函數(shù), 比較貼切現(xiàn)實(shí)生活中距離與覆蓋水平的關(guān)系, 較好地模擬真實(shí)情況.

3.5 模型建立

目標(biāo)函數(shù):

約束條件:

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

約束條件(3): 每個(gè)需求點(diǎn)只能選擇一個(gè)設(shè)施點(diǎn)提供服務(wù), 默認(rèn)情況下, 當(dāng)一個(gè)需求點(diǎn)被多個(gè)自提柜服務(wù)范圍覆蓋時(shí), 選擇距離最近的自提柜接受服務(wù);

約束條件(6): 確保所有自提柜設(shè)施點(diǎn)對(duì)每個(gè)需求點(diǎn)提供的服務(wù)不超過(guò)其需求量;

約束條件(7): 確保所有需求點(diǎn)對(duì)每個(gè)自提柜設(shè)施點(diǎn)的供應(yīng)量不超過(guò)其容量;

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

4 模型分析與求解

4.1模型分析

以上建立的選址模型是一個(gè)混合整數(shù)規(guī)劃模型, 屬于NP-hard問(wèn)題, 隨著問(wèn)題規(guī)模的增大或約束條件的增多求解復(fù)雜度呈指數(shù)增長(zhǎng), 因此在實(shí)際應(yīng)用中, 一般會(huì)采用啟發(fā)式算法進(jìn)行求解, 故本文設(shè)計(jì)了基于次梯度算法和拉格朗日松弛法的啟發(fā)式模型求解算法.

4.2 模型求解

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

為保證對(duì)搜索步長(zhǎng)的控制, 將約束式(3)放到目標(biāo)函數(shù)(2)中, 得到拉格朗日松弛問(wèn)題(2).

目標(biāo)函數(shù):

約束條件:

(4)至(9)

其中, 令

本文利用次梯度優(yōu)化來(lái)調(diào)整拉格朗日乘子的值, 以此逼近最優(yōu)解, 拉格朗日乘子計(jì)算過(guò)程如下所示.

算法執(zhí)行步驟如下: (說(shuō)明: 基于次梯度算法和改進(jìn)拉格朗日松弛法的啟發(fā)式算法)

Step 2. 求解拉格朗日松弛問(wèn)題. 按以上計(jì)算方法計(jì)算出,.

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

5 實(shí)驗(yàn)仿真

5.1數(shù)據(jù)集及運(yùn)行環(huán)境

需求點(diǎn)數(shù)據(jù)集: 本文通過(guò)隨機(jī)算法, 日需求量按照正態(tài)分布產(chǎn)生, 需求點(diǎn)到自提柜點(diǎn)的空間距離按照正態(tài)分布產(chǎn)生, 需求點(diǎn)個(gè)數(shù)分別為100、400、1000的三個(gè)數(shù)據(jù)集.

實(shí)驗(yàn)環(huán)境: 運(yùn)行環(huán)境: Matlab R2013a; 操作系統(tǒng): Windows 7 旗艦版 64位; 處理器: 英特爾第二代酷睿 i5-2320 @ 3.00GHz 四核; 內(nèi)存: 4G.

5.2實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)結(jié)果表明, 拉格朗格松弛算法在求解0-1整型規(guī)劃問(wèn)題上具有良好的運(yùn)算效果, 見(jiàn)表1和圖1.

表1 不同算例下, 拉格朗格松弛算法運(yùn)行情況

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

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

6 結(jié)語(yǔ)

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

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

2 劉柳,馬英才.智能物流上演“最后一公里”爭(zhēng)奪戰(zhàn).互聯(lián)網(wǎng)經(jīng)濟(jì),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 楊曉農(nóng),王振蒙.基于服務(wù)功能的公共圖書(shū)館服務(wù)半徑理論研究.圖書(shū)館,2014,(6):17–19.

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

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

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

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

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

13 喬聯(lián)寶.覆蓋類選址問(wèn)題分類及研究綜述.物流科技,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 褚玉婧,馬良,張慧珍.時(shí)間滿意逐漸覆蓋電動(dòng)騎車(chē)充電站選址及算法.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),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 “l(fā)ast 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 “l(fā)ast 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]