一種新的同時(shí)取送貨車輛路徑問題方法研究

劉玲　栗雅清　王蘊(yùn)默

摘 要：隨著國家的富強(qiáng)，社會經(jīng)濟(jì)實(shí)力的持續(xù)增長，我國人民群眾的日常生活水平也越來越高，所以人們的網(wǎng)購熱情也隨之提高。由此以來，隨著人們網(wǎng)購的種類和數(shù)量不斷增多，網(wǎng)購時(shí)的取貨和送貨問題也浮出水面，成為了一種被廣大學(xué)者重點(diǎn)研究的問題。本文針對同時(shí)取送貨車路徑的問題，基于用戶畫像相關(guān)方法建立了雙目標(biāo)模型，隨后設(shè)計(jì)了蟻群算法對靜態(tài)和動(dòng)態(tài)問題進(jìn)行相關(guān)解析，實(shí)驗(yàn)結(jié)果可得，該方法在具體問題中的求解速度以及對外界環(huán)境不良因素的抗干擾能力較強(qiáng)，為以后的相關(guān)研究奠定了理論基礎(chǔ)。

關(guān)鍵詞：同時(shí)取送貨 車輛路徑 雙目標(biāo) 蟻群算法

1 引言

同時(shí)送貨的時(shí)效性、客戶的滿意程度以及各種具有不確定因素的相關(guān)問題正隨著國家及社會高速發(fā)展慢慢的浮出水面[1]。而如今，隨著計(jì)算機(jī)以及相關(guān)技術(shù)的快速普及，國家為了應(yīng)對各場景下精確滿足客戶需求，完善相關(guān)配送規(guī)范和配送能力。

末端配送的主要問題是VRPSPD問題，以配送網(wǎng)絡(luò)為應(yīng)用場景，結(jié)合用戶畫像理論對取送貨問題進(jìn)行研究，具有現(xiàn)實(shí)意義。當(dāng)前結(jié)合用戶畫像對同時(shí)取送貨問題研究的文獻(xiàn)相對較少，研究具有高復(fù)雜度的NP-hard問題，具有重要學(xué)術(shù)價(jià)值[2-3]，研究成果應(yīng)用于各個(gè)領(lǐng)域，車輛路徑問題的求解方法框架及技術(shù)路線示意如圖1-2

所示。

2 末端配送概念的相關(guān)概述

我國末端配送以不同的配送需求主體與配送客體劃分，可以將配送服務(wù)分為三大類，分別是B2B、B2C、C2C。

3 用戶畫像流程及方法

構(gòu)架邏輯，其中用戶平時(shí)在配送服務(wù)中的行為數(shù)據(jù)如：評論參與情況，平臺瀏覽量，進(jìn)行用戶畫像。

4 取送貨需求用戶畫像體系構(gòu)建

取送貨用戶畫像標(biāo)簽體系，其中標(biāo)簽獲取及處理步驟如下：

（1）標(biāo)簽獲取，根據(jù)相關(guān)問卷調(diào)查，獲得了150份相關(guān)數(shù)據(jù)資料。對最底層事實(shí)標(biāo)簽數(shù)據(jù)進(jìn)行定量處理和歸一化處理，即可進(jìn)行下一步數(shù)據(jù)的收集和分析。

（2）對問卷數(shù)據(jù)的處理步驟共有三步：

①分析各個(gè)標(biāo)簽，構(gòu)建指標(biāo)評價(jià)矩陣Xij。

②歸一化處理，消除不同量綱之間的影響得到X'ij。歸一化式子[4]如（1）所示，其中Z'是標(biāo)準(zhǔn)化后的數(shù)值，Z表示初始值，Zmin該指標(biāo)極小值，Zmax該指標(biāo)的最大值：

（1）

③熵值法求解高級標(biāo)簽下各個(gè)指標(biāo)的影響權(quán)重。

5 雙目標(biāo)蟻群算法要點(diǎn)及流程

蟻群算法是受自然界螞蟻群體的覓食行為啟發(fā)而發(fā)展起來的進(jìn)化算法，蟻群算法最初被應(yīng)用于旅行商問題（travelling salesman problem，TSP），取得了很好的實(shí)驗(yàn)結(jié)果。近年來蟻群優(yōu)化（antcolony optimization， ACO）方法被廣泛應(yīng)用于車輛路徑問題。

本文提出的基于用戶畫像的同時(shí)取送貨模型為路徑最小和客戶滿意度懲罰最小的雙目標(biāo)模型，并不存在絕對最優(yōu)解。雙目標(biāo)蟻群算法[5]流程結(jié)合用戶基本數(shù)據(jù)及用戶畫像得到的四組客戶進(jìn)行仿真驗(yàn)證，蟻群算法參數(shù)設(shè)置如表1所示。列出基于時(shí)空聚類的區(qū)域劃分客戶點(diǎn)的數(shù)據(jù)。對每一個(gè)區(qū)域內(nèi)的客戶進(jìn)行求解，分析每一區(qū)域非劣解偏向不同目標(biāo)函數(shù)的解及是否采用時(shí)空距離對配送區(qū)域進(jìn)行劃分，可以得出如下結(jié)論：

（1）對比有畫像下有無聚類的求解結(jié)果，可見有畫像有聚類的計(jì)算效率約為有畫像無聚類的兩倍。（2）對比有畫像有聚類是區(qū)域分別求解還是一起求解的結(jié)果可見，一起求解的無懲罰客戶占比要高于分別求解。（3）對比無聚類下是否畫像對結(jié)果影響，無聚類下有畫像的結(jié)果求解時(shí)間明顯縮短。（4）對比有聚類下有無用戶畫像對結(jié)果的影響。

6 結(jié)語

本文在用戶畫像及配送區(qū)域劃分的基礎(chǔ)上，進(jìn)行路徑優(yōu)化。建立VRPSPD基本模型，提出基于用戶畫像的VRPSPD雙目標(biāo)問題， 模型考慮車輛容量和最大行駛距離限制的同時(shí)， 構(gòu)建了最小化總行駛距離和最小化不同車輛行駛距離最大差以平衡各車輛的工作負(fù)荷的雙目標(biāo)模型，并且考慮了需求點(diǎn)客戶用戶價(jià)值和用戶時(shí)間敏感度對時(shí)間窗下滿意度懲罰的影響。最后通過算例驗(yàn)證了算法的有效性，從是否雙目標(biāo)、有無聚類等角度，對比分析算法優(yōu)化效果，為以后的實(shí)際應(yīng)用提供了夯實(shí)的理論研究基礎(chǔ)。

參考文獻(xiàn)：

[1]孔源.基于海量浮動(dòng)車數(shù)據(jù)和社交網(wǎng)絡(luò)興趣點(diǎn)的時(shí)空軌跡挖掘[D].北京：清華大學(xué)，2017.

[2]Li J，Pardalos P M，Sun H.adaptive neighborhood selection approach for the multi-depot vehicle routing problem with simultaneous deliveries and pickups[J].Iterated local search embedded Expert systems with applications an international journal，2015，42（7）：3551-3561.

[3]Wang J，Ying z，Wang w.Multiobjective vehicle routing problems with simultaneous delivery and pickup and time windows：formulation，instances and algorithms[J]. IEEE Transactions on Cy bernetics，2016，46（3）：582-594.

[4]Branke J，Middendorf M，Noeth G.Waiting strategies for dynamic vehicle routing[J].Transportation science，2005，39（3）：298-312.

[5]Reed M，Yiannakou A，Evering R. An ant colony algorithm for the multi-compartment vehicle routing problem[J].Applied Soft Computing，2014，15：169-176.