基于遗传算法的即时配送路径优化研究

赵琨 史艳华 史晓霞

摘要：即时配送吸引很多快递企业迅速进入这一新的业务领域，虽然快递企业组建了自己的专职配送团队，但是仍然面临很多问题，据此，在满足配送时间窗的前提下，确立以配送员每次配送的收入最大化问题，借此来降低运力数量，从而达到提高快递公司收益的目的。

关键词：即时配送;路径优化;销量需求预测;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.