基于遺傳算法的即時(shí)配送路徑優(yōu)化研究

趙琨 史艷華 史曉霞

摘要：即時(shí)配送吸引很多快遞企業(yè)迅速進(jìn)入這一新的業(yè)務(wù)領(lǐng)域，雖然快遞企業(yè)組建了自己的專職配送團(tuán)隊(duì)，但是仍然面臨很多問(wèn)題，據(jù)此，在滿足配送時(shí)間窗的前提下，確立以配送員每次配送的收入最大化問(wèn)題，借此來(lái)降低運(yùn)力數(shù)量，從而達(dá)到提高快遞公司收益的目的。

關(guān)鍵詞：即時(shí)配送;路徑優(yōu)化;銷量需求預(yù)測(cè);VRPTW模型

中圖分類號(hào)：F25文獻(xiàn)標(biāo)識(shí)碼：Adoi：10.19311/j.cnki.1672-3198.2019.05.014

1引言

近年來(lái)，快遞行業(yè)隨著電商的發(fā)展而壯大，其市場(chǎng)競(jìng)爭(zhēng)也日趨激烈，許多快遞企業(yè)都面臨著轉(zhuǎn)型的問(wèn)題。與此同時(shí)，即時(shí)配送伴隨O2O經(jīng)濟(jì)和“懶人經(jīng)濟(jì)”迅速興起，具備著極大的市場(chǎng)發(fā)展?jié)摿ΑＲ虼耍承┟媾R轉(zhuǎn)型的快遞企業(yè)為了盡快搶占即時(shí)配送的市場(chǎng)份額，從而迅速開(kāi)拓了這一新的業(yè)務(wù)領(lǐng)域。因即時(shí)配送具有即時(shí)性、短距離、高頻次等特點(diǎn)，較之傳統(tǒng)快遞還有著很大的區(qū)別。所以，某些快遞企業(yè)雖然組建了自己的專職配送團(tuán)隊(duì)，卻因缺乏相關(guān)的經(jīng)驗(yàn)，造成其面臨著很多問(wèn)題：運(yùn)力投入不合理、配送路線雜亂、難以保證服務(wù)時(shí)效、配送成本居高不下等問(wèn)題。

楊子岳（2012）基于禁忌搜索算法建立了以配送成本最小為目標(biāo)的帶時(shí)間窗的路徑優(yōu)化模型，并將交通路況因素考慮進(jìn)去與未考慮交通路況的路徑優(yōu)化模型進(jìn)行了分析對(duì)比。范青（2014）提出了一種改進(jìn)的蟻群算法，并通過(guò)SOLOMON中的數(shù)據(jù)對(duì)其模型進(jìn)行了有效性驗(yàn)證。劉昌生（2014）從配送時(shí)間的隨機(jī)性與客戶的服務(wù)滿意度的角度出發(fā)，提出了一種改進(jìn)的遺傳算法，構(gòu)建了VRPSTW模型。郭會(huì)朋（2015）提出了一種改進(jìn)的遺傳算法。Nalepa J，Czech Z J（2014）構(gòu)建了以服務(wù)客戶的車輛數(shù)量和車輛行駛的總距離最小為目標(biāo)函數(shù)的帶時(shí)間窗的配送路徑優(yōu)化模型。Ghani NEA，Shariff SSR，Zahari SM（2016）構(gòu)建了以行駛總距離最小為目標(biāo)函數(shù)的帶時(shí)間窗的配送路徑優(yōu)化模型。馮田（2011）針對(duì)“多個(gè)起點(diǎn)到多個(gè)終點(diǎn) ”的特點(diǎn)，基于sufferage算法的原理，構(gòu)建出了一種動(dòng)態(tài)拼車的調(diào)度算法。邵增珍（2013）對(duì)車輛合乘匹配問(wèn)題進(jìn)行了研究，運(yùn)用兩階段聚類算法與改進(jìn)的遺傳算法，實(shí)現(xiàn)了搭乘需求匹配以及路徑優(yōu)化。劉鑫（2013）運(yùn)用改進(jìn)的聚類算法及位置近似算法以實(shí)現(xiàn)動(dòng)態(tài)拼車，并對(duì)其進(jìn)行了模擬仿真，結(jié)果表明拼車率及路程節(jié)省率得到了有效的提高。丁冉（2015）構(gòu)建了以出行時(shí)間和費(fèi)用成本最小為目標(biāo)的動(dòng)態(tài)合乘匹配模型，并用MATLAB進(jìn)行模型實(shí)例求解。趙興龍（2016）結(jié)合了動(dòng)態(tài)性的特點(diǎn)，建立了動(dòng)態(tài)配送路徑優(yōu)化模型，實(shí)現(xiàn)了配送需求的合并，并通過(guò)MATLAB進(jìn)行求解，驗(yàn)證了所構(gòu)建的模型具備合理性和有效性。G Nagy，S Salhi（2005）以行駛距離最小為目標(biāo)，構(gòu)建了 VRPPD模型，解決了靜態(tài)拼車的問(wèn)題。Tao C C，Chen C Y（2007）將貪婪算法與時(shí)空網(wǎng)絡(luò)算法進(jìn)行結(jié)合，解決了動(dòng)態(tài)拼車的問(wèn)題。Atay B（2010）以行駛距離最小為目標(biāo)，利用蟻群算法進(jìn)行求解模型。

2配送路徑優(yōu)化模型

通過(guò)對(duì)某快遞公司在該項(xiàng)業(yè)務(wù)上所消耗的人員成本情況進(jìn)行定量分析，發(fā)現(xiàn)快遞公司是通過(guò)投入大量的運(yùn)力資源，來(lái)達(dá)到保證即時(shí)配送準(zhǔn)時(shí)送達(dá)率的目的。所以，在保證服務(wù)時(shí)效的同時(shí)降低人員成本，從而提高快遞公司在該項(xiàng)業(yè)務(wù)上的收益，是快遞公司當(dāng)前所亟待解決的問(wèn)題。因此，在滿足配送時(shí)間窗的條件下，針對(duì)快遞公司現(xiàn)存問(wèn)題提出以配送員每次配送的收入最大為目標(biāo)函數(shù)，借此來(lái)降低運(yùn)力的數(shù)量，降低人員成本的支出，從而達(dá)到提高快遞公司收益的目的。假定（1）配送員的配送速度v均為同一定值;（2）配送員每次的配送量不能大于最高要求;（3）配送員每次的配送量不能小于最低要求;（4）配送員在取貨點(diǎn)取貨所消耗的時(shí)間均忽略不計(jì)。

3結(jié)論

因即時(shí)配具備強(qiáng)大的市場(chǎng)發(fā)展?jié)摿Γ晕撕芏嗟目爝f企業(yè)紛紛加進(jìn)入這一新的業(yè)務(wù)領(lǐng)域。即時(shí)配送相較于傳統(tǒng)快遞還是有著很大的區(qū)別，某些快遞企業(yè)雖然迅速組建了自己的專職配送團(tuán)隊(duì)，但是也仍然面臨很多問(wèn)題。因此，本文以開(kāi)展該項(xiàng)新業(yè)務(wù)的某快遞公司為切入點(diǎn)，先對(duì)快遞公司的現(xiàn)狀進(jìn)行分析，發(fā)現(xiàn)投入運(yùn)力的支出在收入中占據(jù)了極大的比重，從而確立以配送員每次配送的收入最大為目標(biāo)函數(shù)，借此降低運(yùn)力數(shù)量，從而提高快遞公司在該項(xiàng)業(yè)務(wù)上的收益。

參考文獻(xiàn)

[1]楊子岳.低碳視角下B2C電子商務(wù)配送路徑優(yōu)化研究[D].成都：西南交通大學(xué)，2012.

[2]范青.基于改進(jìn)蟻群算法的物流配送路徑優(yōu)化及應(yīng)用研究[D].西安：西安建筑科技大學(xué)，2014.

[3]劉昌生.隨機(jī)配送時(shí)間車輛路徑優(yōu)化模型及算法研究[D].蘭州：蘭州交通大學(xué)，2014.

[4]郭會(huì)朋.基于改進(jìn)遺傳算法的物流配送路徑優(yōu)化研究[D].西安：西安電子科技大學(xué)，2015.

[5]Nalepa J，Czech Z J.A Parallel Memetic Algorithm to Solve the Vehicle Routing Problem with Time Windows[J].Computer Science，2014，33（104）.

[6]Ghani NEA，Shariff SSR，Zahari SM.An Alternative Algorithm for Vehicle Routing Problem with Time Windows for Daily Deliveries[J].Advances in Pure Mathematics，2016，06（5）：342-350.

[7]馮田.基于sufferage的動(dòng)態(tài)出租車拼車調(diào)度算法[J].電腦知識(shí)與技術(shù)，2011，（28）：7019-7023.

[8]邵增珍.物流匹配問(wèn)題的調(diào)度模型和算法研究[D].臨沂：山東師范大學(xué)，2013.

[9]劉鑫.城市車輛動(dòng)態(tài)拼車調(diào)度機(jī)制的研究[D].南京：南京大學(xué)，2013.

[10]丁冉.出租車動(dòng)態(tài)合乘匹配問(wèn)題研究[D].南京：東南大學(xué)，2015.

[11]趙興龍.基于K-means遺傳算法的眾包配送網(wǎng)絡(luò)優(yōu)化研究[D].北京：北京交通大學(xué)，2016.

[12]Nagy G，Salhi S.Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries[J].European Journal of Operational Research，2005，162（1）：126-141.

[13]Tao C C，Chen C Y.Heuristic Algorithms for the Dynamic Taxipooling Problem Based on Intelligent Transportation System Technologies[C]// International Conference on Fuzzy Systems and Knowledge Discovery.IEEE Computer Society，2007：590-595.

[14]Atay B，lent.A new saving-based ant algorithm for the Vehicle Routing Problem with Simultaneous Pickup and Delivery[J].Expert Systems with Applications，2010，37（10）：6809-6817.