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

趙琨 史艷華 史曉霞

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

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

中圖分類號：F25文獻標識碼：Adoi：10.19311/j.cnki.1672-3198.2019.05.014

1引言

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

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

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

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

3結(jié)論

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

參考文獻

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

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

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

[4]郭會朋.基于改進遺傳算法的物流配送路徑優(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的動態(tài)出租車拼車調(diào)度算法[J].電腦知識與技術(shù)，2011，（28）：7019-7023.

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

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

[10]丁冉.出租車動態(tài)合乘匹配問題研究[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.