戴韜 毛佩琦
[摘要]近年來,伴隨著送貨上門取件模式送貨時(shí)間沖突、配送效率低下等問題的產(chǎn)生,快遞自提點(diǎn)的取貨模式應(yīng)運(yùn)而生。但由于設(shè)立自提點(diǎn)需要前期的建設(shè)和長(zhǎng)期的運(yùn)營(yíng)成本,因此自提點(diǎn)數(shù)量及位置的合理性對(duì)企業(yè)在自提網(wǎng)絡(luò)規(guī)劃的研究中至關(guān)重要。從客戶的角度出發(fā),不同的客戶對(duì)于送貨上門服務(wù)和自提點(diǎn)取貨模式存在不同的偏好程度,對(duì)于不同的自提點(diǎn)也存在不同的選擇意愿差異。文章在充分考慮客戶選擇意愿的基礎(chǔ)上,構(gòu)建了自提網(wǎng)絡(luò)的選址模型,并利用免疫算法求解了最佳的自提點(diǎn)數(shù)量及其最優(yōu)選址方案,算例結(jié)果驗(yàn)證了免疫算法的有效性。文章的模型比較符合現(xiàn)實(shí)生活中快遞公司對(duì)于自提網(wǎng)絡(luò)規(guī)劃的實(shí)際情況,具有較好的現(xiàn)實(shí)借鑒意義。
[關(guān)鍵詞]自提網(wǎng)絡(luò);選址規(guī)劃;送貨上門;客戶選擇概率;免疫算法
[DOI]1013939/jcnkizgsc201913178
1引言
近年來,我國(guó)快遞行業(yè)發(fā)展迅速,在國(guó)內(nèi)市場(chǎng)經(jīng)濟(jì)中逐步占據(jù)優(yōu)勢(shì)地位。伴隨著送貨上門取件模式送貨時(shí)間沖突、配送效率低下、快遞安全等問題的產(chǎn)生,客戶越來越偏向于自助快遞站的取件模式。
自提點(diǎn)的取件模式雖然在一定程度上緩解了送貨上門取貨模式存在的問題,但由于設(shè)立自提點(diǎn)需要前期的建設(shè)成本和長(zhǎng)期的運(yùn)營(yíng)成本[1],因此對(duì)于快遞公司而言,自提點(diǎn)的數(shù)量并非越多越好。由此可見,自提點(diǎn)數(shù)量及其位置的決策,對(duì)于快遞企業(yè)至關(guān)重要,對(duì)于快遞行業(yè)的未來發(fā)展具有重要的研究意義。[2]
目前,國(guó)內(nèi)外對(duì)于自提點(diǎn)的選址問題的研究比較少。陳義友等基于排隊(duì)模型,構(gòu)造了送貨上門和自提點(diǎn)的分段效用函數(shù),在此基礎(chǔ)上構(gòu)建了有限理性下自提點(diǎn)的多目標(biāo)優(yōu)化模型,并利用非支配排序遺傳算法對(duì)模型進(jìn)行了求解。[3]邱晗光等使用嵌套Logit選擇模型量化客戶對(duì)配送模式的選擇偏好行為,以配送數(shù)量最大化和配送成本最小化為目標(biāo),建立了自提柜選址-時(shí)間窗分配-路徑規(guī)劃模型,分析了客戶選擇配送模式對(duì)自提點(diǎn)選址的影響。[4]MAY等根據(jù)階段性客戶需求的變化來實(shí)時(shí)規(guī)劃快遞站點(diǎn)和中轉(zhuǎn)點(diǎn),以車輛總路徑最短為主要目標(biāo)函數(shù),利用啟發(fā)式算法求解模型。[5]CHAN等為了研究海上原油的配送點(diǎn)問題,以總成本最小化、服務(wù)水平最大化為目標(biāo)函數(shù),通過改進(jìn)多目標(biāo)蟻群優(yōu)化算法來求解最優(yōu)選址方案。[6]綜上所述,針對(duì)自提網(wǎng)絡(luò)選址問題,需要考慮客戶對(duì)送貨上門服務(wù)及自提點(diǎn)提貨服務(wù)的偏好程度。
2模型構(gòu)建
21問題背景
在限定區(qū)域范圍內(nèi),存在若干個(gè)需要配送的客戶點(diǎn),每個(gè)客戶點(diǎn)需要配送的貨物量已知,所有客戶點(diǎn)可作為候選點(diǎn)用來設(shè)立自提點(diǎn)。對(duì)客戶而言,存在兩種不同類型的取貨模式:送貨上門的基礎(chǔ)配送服務(wù),前往自提點(diǎn)提貨的取件模式??蛻翎槍?duì)不同的取貨服務(wù),存在不同的選擇意愿差異,這種差異取決于不同取貨模式帶給客戶的效用。
211客戶效用函數(shù)
文章通過構(gòu)建客戶效用函數(shù)來表示不同取貨模式帶給客戶的效用。文章將送貨上門服務(wù)的效用價(jià)值視為“0”。借鑒引力模型[7]來定義客戶效用函數(shù),因此客戶效用函數(shù)為:
Uij=Aikdisij2(1)
在式(1)中,Uij表示自提點(diǎn)i對(duì)客戶點(diǎn)j的效用,disij表示自提點(diǎn)i和客戶點(diǎn)j之間的距離,Ai表示不同自提點(diǎn)i對(duì)于客戶點(diǎn)的吸引力大小。k為函數(shù)中的調(diào)節(jié)變量系數(shù),用來量化距離和吸引力之間的比例關(guān)系。
212客戶選擇概率函數(shù)
客戶對(duì)于不同取貨模式的選擇概率大小取決于該取貨模式能帶給客戶的效用,文章借鑒MNL模型[8]來構(gòu)建客戶對(duì)于不同取貨模式的選擇概率函數(shù)。
(1)不考慮送貨上門服務(wù)。先不考慮送貨上門的配送服務(wù),客戶選擇不同自提點(diǎn)取貨的概率pij可以表示為:
pij=eUij∑k∈XeUkj(2)
其中pij表示客戶j對(duì)于不同自提點(diǎn)i的選擇概率,X表示自提點(diǎn)集合。
(2)考慮送貨上門服務(wù)。由于自提點(diǎn)取貨和送貨上門服務(wù)是兩種不同類型的取貨選擇,在計(jì)算客戶選擇概率時(shí),不能簡(jiǎn)單地混合相加。因此文章提出“客戶偏好程度”[9]的概念,用λ來表示客戶對(duì)于兩種不同類型選擇的偏好程度,λ∈(-∞,+∞)。當(dāng)λ=0時(shí),客戶不能辨別出兩種服務(wù)的區(qū)別,按照相同概率隨機(jī)選擇配送服務(wù);當(dāng)λ→+∞時(shí),客戶以概率1的可能性趨向于自提點(diǎn)取貨服務(wù);當(dāng)λ→-∞時(shí),客戶以概率1的可能性趨向于送貨上門服務(wù)。綜上分析,客戶選擇概率函數(shù)如下所示:
pij=eλUij1+∑k∈XeλUkj(3)
22模型假設(shè)及參數(shù)
221模型假設(shè)
(1)假設(shè)客戶選擇不同取貨模式的唯一依據(jù)是該取貨模式帶給客戶的效用。
(2)假設(shè)該自提點(diǎn)的效用值僅與該點(diǎn)與客戶點(diǎn)的距離和該點(diǎn)自身吸引力值相關(guān)。
222模型變量
P表示選中的自提點(diǎn)數(shù)量X表示可選的自提點(diǎn)集合;Y表示所有的客戶點(diǎn)集合;xi表示自提點(diǎn)被選中的情況;Dj表示每個(gè)客戶點(diǎn)j的總客戶數(shù)量;qi表示自提點(diǎn)i需要接收的客戶總量;Q表示自提點(diǎn)能接受的最大客戶容量;disij表示自提點(diǎn)i和客戶點(diǎn)j之間的距離;Uij表示自提點(diǎn)i對(duì)客戶點(diǎn)j的效用值;Ai表示自提點(diǎn)i的吸引力值;pij表示客戶點(diǎn)j選擇自提點(diǎn)i取貨的概率;k表示效用函數(shù)的調(diào)節(jié)變量系數(shù);λ表示客戶對(duì)兩種不同服務(wù)的偏好程度;L表示客戶點(diǎn)到自提點(diǎn)的最大距離限制;Cb表示設(shè)立自提點(diǎn)的固定建設(shè)成本(/天);Ch表示送貨上門雇傭成本;Ca表示站點(diǎn)接納單位數(shù)量客戶的運(yùn)營(yíng)成本。
23數(shù)學(xué)模型
minf=Cb×P+Ca×∑i∈X∑j∈YDjpij+Ch×∑j∈Y∑i∈XDij(1-pij)(4)
S.T.
Uij=Aikdisij2 (5)
pij=eλUij1+∑k∈XeλUkj(6)
qi=∑j∈YDjpij(7)
qi≤Q(8)
disij≤L(9)
pij≤xi(10)
∑i∈Xxi=P(11)
xi∈{0,1}(12)
式(4)為模型的目標(biāo)函數(shù),表示最小化快遞公司的配送總成本。該配送總成本由三部分費(fèi)用組成:自提網(wǎng)絡(luò)固定建設(shè)費(fèi)用、日常運(yùn)營(yíng)總費(fèi)用和送貨上門服務(wù)總費(fèi)用,計(jì)表達(dá)式如下所示:
配送總成本=自提網(wǎng)絡(luò)固定建設(shè)費(fèi)用+自提網(wǎng)絡(luò)日常運(yùn)營(yíng)費(fèi)用+送貨上門服務(wù)費(fèi)用
模型主要的約束有:式(6)表示客戶選擇概率函數(shù)。式(7)表示一個(gè)自提點(diǎn)接收到的客戶數(shù)量。式(8)和(9)分別表示模型的容量和距離約束。
3算法設(shè)計(jì)
文章建立的選址模型是P-中值模型[10]的變形,P-中值模型屬于NP-hard問題[11],需要設(shè)計(jì)啟發(fā)式算法求解。在文章的選址模型中,涉及到網(wǎng)絡(luò)中的候選點(diǎn)數(shù)量較多,考慮到算法運(yùn)行時(shí)間,文章采用免疫算法求解。免疫算法將求解的問題視為抗原,問題的解決方案視為抗體,通過抗原和抗體之間的相互匹配,產(chǎn)生最佳抗體。算法通過種群初始化、抗體多樣性評(píng)價(jià)、記憶細(xì)胞生成、種群再生等幾個(gè)步驟得到最優(yōu)解。
31種群初始化
模型中需要計(jì)算不同數(shù)量自提點(diǎn)下的最優(yōu)選址方案,如果采用二進(jìn)制編碼比較復(fù)雜,本文采用自提點(diǎn)序號(hào)簡(jiǎn)單編碼的方式。種群中每個(gè)抗體代表一種選址方案,例如抗體(6,8,11,16,30)表示選擇序號(hào)為6,8,11,16,30的客戶點(diǎn)作為自提點(diǎn)。
32抗體多樣性評(píng)價(jià)
321計(jì)算抗體適應(yīng)度
免疫算法中抗體適應(yīng)度表示該抗體的優(yōu)異程度,一般為該模型的目標(biāo)函數(shù),或者目標(biāo)函數(shù)的變形。在本模型中,抗體的適應(yīng)度函數(shù)表示為:
fa=∑j∈YDj (1-∑i∈Xpij(13)
在式(13)中,fa表示模型中選擇送貨上門服務(wù)的總?cè)藬?shù)。
322計(jì)算抗體濃度
抗體的濃度Ca由抗體相似度S(a,b)決定,S(a,b)表示抗體a和b中序號(hào)相同的位數(shù)再除以抗體長(zhǎng)度。將該抗體a和種群中剩余抗體逐一進(jìn)行對(duì)比,計(jì)算抗體相似度值。
為了方便抗體濃度Ca的計(jì)算,可預(yù)先設(shè)定一個(gè)抗體間親和力閥值B,若S(a,b)>B,則令S(v,s)=1,若S(a,b)≤B,則令S(v,s)=0。因此抗體的濃度Ca可以表示為(其中N為抗體總數(shù)):
Ca=1N ∑j∈NSa,b (14)
33生成記憶細(xì)胞
根據(jù)上述計(jì)算過程中得到的抗體適應(yīng)度和抗體濃度,計(jì)算每個(gè)抗體的期望繁殖概率P_a:
Pa=α fa∑fa+(1-α)Ca∑Ca(15)
α表示期望繁殖概率系數(shù)(α值可事先設(shè)定),用來平衡抗體濃度和抗體適應(yīng)度之間的比重。根據(jù)每個(gè)抗體的期望繁殖概率,對(duì)抗體進(jìn)行排序。將種群中排名前N的抗體加入記憶庫(kù)(N值可事先設(shè)定),形成記憶細(xì)胞,剩余抗體將自動(dòng)形成初代父代群。如圖1所示。
34對(duì)父代群進(jìn)行遺傳操作
針對(duì)步驟3形成的初始父代群體,進(jìn)行選擇、交叉和變異操作。
341選擇
文章采用輪盤賭法進(jìn)行選擇。將抗體的期望繁殖概率值占所有抗體期望繁殖概率總和的比例作為選擇概率,用輪盤法選擇產(chǎn)生下一代群體。
342交叉
抗體之間以一定的交叉概率進(jìn)行交叉,文章的交叉方式主要為片段交叉,如圖2所示。
交叉后的新抗體需要進(jìn)行距離約束檢驗(yàn)和容量約束檢驗(yàn),片段交叉之后如果出現(xiàn)不符合約束條件的抗體,則重新進(jìn)行交叉。
343變異
文章通過單點(diǎn)變異的形式來進(jìn)行抗體變異,如圖3所示。先在父代群體隨機(jī)選擇一個(gè)抗體,再隨機(jī)選定該抗體的變異位置,然后從序號(hào)中隨機(jī)產(chǎn)生一個(gè)不在選中抗體內(nèi)的序號(hào),由該序號(hào)替換掉抗體中變異位置的原始序號(hào)。
變異后的新染色體需要進(jìn)行距離和容量約束檢驗(yàn),如果出現(xiàn)不符合約束條件的抗體,則重新變異。
35種群再生
在上述遺傳操作后產(chǎn)生的新抗體群中加入原先在記憶庫(kù)中保留的抗體,形成一個(gè)新種群,然后再進(jìn)行下一輪的迭代尋優(yōu)。該過程中不會(huì)產(chǎn)生無效抗體。
初始種群在經(jīng)過不斷的迭代尋優(yōu)之后,判斷是否達(dá)到最大進(jìn)化代數(shù)MAXGEN,如果達(dá)到,則輸出結(jié)果;否則繼續(xù)迭代。
4算例分析
41算例描述
為了驗(yàn)證模型及算法的有效性,根據(jù)某城區(qū)居民分布情況,設(shè)計(jì)一個(gè)小規(guī)模算例進(jìn)行驗(yàn)證。假設(shè)某區(qū)域中有31個(gè)客戶點(diǎn),每個(gè)客戶點(diǎn)的客戶數(shù)量為Dj=(50,50,150,50,25,175,100,225,25,175,150,100,100,100,50,200,225,175,250,125,125,125,200,175,200,100,100,150,175,125,75)。每個(gè)候選點(diǎn)的最大容量限制為2500(個(gè)),客戶點(diǎn)和自提點(diǎn)之間的距離限制為2000(m)。假設(shè)其中該區(qū)域客戶總數(shù)為4050人,設(shè)立一個(gè)自提點(diǎn)的固定建設(shè)成本為200元/天。此外,根據(jù)市場(chǎng)調(diào)查,雇傭快遞員送貨上門的服務(wù)成本約為3元/單,而自提點(diǎn)接收客戶的運(yùn)營(yíng)成本約為005元/位。
42求解結(jié)果
利用上述算法思想,通過MATLAB編寫程序,假設(shè)初始種群規(guī)模為60組,調(diào)節(jié)變量系數(shù)k取000001,客戶偏好程度λ取1。多樣性評(píng)價(jià)參數(shù)α為095,抗體間親和力閥值B為07。每次保留最佳抗體10個(gè),交叉概率pc為05,變異概率pm為04,不斷迭代尋優(yōu),得到配送總成本最低的選址方案和最佳的自提點(diǎn)數(shù)量,如表1。
在本算例中,當(dāng)選擇5個(gè)自提點(diǎn)時(shí),配送總成本最低,約為20492元。對(duì)于決策企業(yè)而言,最佳的自提點(diǎn)數(shù)量為5個(gè),最優(yōu)的選址方案為[6 8 16 18 25]。該方案中,客戶選擇送貨上門服務(wù)的人數(shù)約為287人,選擇自提點(diǎn)取貨的人數(shù)約為3763人。自提點(diǎn)取貨人數(shù)占到了總?cè)藬?shù)的929%。在現(xiàn)實(shí)生活中,客戶會(huì)更偏向于自提點(diǎn)取貨的模式,因此該數(shù)據(jù)結(jié)果也比較符合現(xiàn)實(shí)生活情況。表2表示1~31個(gè)客戶點(diǎn)前往5個(gè)自提點(diǎn)的客戶數(shù)量情況。
5結(jié)論
文章對(duì)客戶面臨不同取貨模式的選擇行為
進(jìn)行了抽象分析,并以此構(gòu)建了考慮客戶選擇意愿背景下的自提網(wǎng)絡(luò)模型,設(shè)計(jì)免疫算法對(duì)選址模型進(jìn)行了求解,并通過算例驗(yàn)證了模型和算法的有效性,同時(shí)證明了文章的模型具有良好的現(xiàn)實(shí)借鑒意義?,F(xiàn)實(shí)生活中的快遞企業(yè)可以依據(jù)企業(yè)自身的成本數(shù)據(jù)和服務(wù)標(biāo)準(zhǔn),參照本文的模型及算法,計(jì)算出最合理的自提點(diǎn)數(shù)量及其選址方案。
參考文獻(xiàn):
[1]WU H, SHAO D, NG W. Locating self-collection points for last-mile logistics using public transport data[M].CAO T, LIM E, ZHOU Z, et al. Berlin, Germany: Springer-Verlag,2015:9077:498-510.
[2]李梅.B2C物流配送自提模式的探討[J].物流工程與管理,2014,36(4):68-71.
[3]陳義友,韓珣,曾倩.考慮送貨上門影響的自提點(diǎn)多目標(biāo)選址問題[J].計(jì)算機(jī)集成制造系統(tǒng),2016,22(11):2679-2690.
[4]邱晗光,周愉峰.基于嵌套Logit選擇模型的城市配送自提柜選址-路徑問題[J].計(jì)算機(jī)應(yīng)用,2018,38(2):582-588.
[5]MAY M D, TU C Y. Location-routing based dynamic vehicle routing problem for express pick-up service[C]. IEEE International Conference on Industrial Engineering and Engineering Management. IEEE, 2009:1830 - 1834.
[6]CHAN F T S, SHEKHAR P, TIWARI M K. Dynamic scheduling of oil tankers with splitting of cargo at pickup and delivery locations: a multi-objective Ant Colony-based approach[J]. International Journal of Production Research, 2014, 52(24):7436-7453.
[7]陳彥光,劉繼生.基于引力模型的城市空間互相關(guān)和功率譜分析——引力模型的理論證明、函數(shù)推廣及應(yīng)用實(shí)例[J].地理研究,2002(6):742-752.
[8]晏莉穎,孟祥佩.軌道交通對(duì)居民交通方式選擇的影響研究[J].鐵道運(yùn)輸與經(jīng)濟(jì),2018,40(1):100-105.
[9]XU, JUNJIE, JIANG, LING Consumer choice features for self-pickup service: an empirical study on chinese e-retailing market[J]. Geomatics and Information Science of Wuhan University, 2014,39: 235-238.
[10]時(shí)曼曼,張守健,吳婉弘.基于P中值模型的村鎮(zhèn)文化體育設(shè)施配置研究[J].工程管理學(xué)報(bào),2014,28(1):36-40.
[11]張輝,王裕明,姚興華,等.NP難解問題的教學(xué)方法探討[J].軟件導(dǎo)刊(教育技術(shù)),2018,17(4):82-83.