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

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

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

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

1 引言

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

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

所示。

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

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

3 用戶(hù)畫(huà)像流程及方法

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

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

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

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

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

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

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

（1）

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

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

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

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

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

6 結(jié)語(yǔ)

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

參考文獻(xiàn)：

[1]孔源.基于海量浮動(dòng)車(chē)數(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.