基于遺傳算法的即時配送路徑優化研究

趙琨 史艷華 史曉霞

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

關鍵詞：即時配送;路徑優化;銷量需求預測;VRPTW模型

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

1引言

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

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

2配送路徑優化模型

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

3結論

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

參考文獻

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

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

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

[4]郭會朋.基于改進遺傳算法的物流配送路徑優化研究[D].西安：西安電子科技大學，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的動態出租車拼車調度算法[J].電腦知識與技術，2011，（28）：7019-7023.

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

[9]劉鑫.城市車輛動態拼車調度機制的研究[D].南京：南京大學，2013.

[10]丁冉.出租車動態合乘匹配問題研究[D].南京：東南大學，2015.

[11]趙興龍.基于K-means遺傳算法的眾包配送網絡優化研究[D].北京：北京交通大學，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.