蚁群算法在外卖配送路径规划中的应用

黄心++吴学群++袁清冽

摘要： 随着我国经济的快速发展，生活节奏的提高，外卖成为了年轻人生活的一部分，而快速有效的送货速度成为了几个外卖公司的竞争重点之一。外卖送货人员如何能够在有限的时间对外卖进行分配节约劳动成本根据的是送货人员的经验。本文通过蚁群算法对不同地址的收货点进行路径进行规划，并利用MATLAB软件，为送货人员设计出了最短时间路径规划。

Abstract： With the rapid development of China's economy and the improvement of the pace of life， takeaway became a part of young people's lives. Fast and effective delivery speed has become one of the competitive priorities of several takeaway companies. How do the delivery personnel distribute the takeaways in a limited time to sell the labor cost is based on the experience of delivery personnel. In this paper， ant colony algorithm is used to carry out the path planning for different address receiving points， and the shortest path planning is designed for the delivery personnel by using MATLAB software.

关键词： 外卖；送货；蚁群算法；路径规划；MATLAB

Key words： takeaway；deliver goods；ant colony algorithm；path planning；MATLAB

中图分类号：U116.2 文献标识码：A 文章编号：1006-4311（2017）05-0065-03

0 引言

近年来，外卖行业日趋火爆，百度外卖、饿了么、美团、大众等几大公司的竞争日趋激烈。外卖O2O的发展与消费者的快速收到外卖心态的矛盾越发明显。“网站+送餐”的模式分为轻模式和重模式，区别在于配送团队是第三方配送还是自建配送团队。无论是轻模式还是重模式，配送团队的重要性不言而喻。配送团队的工作效率，服务的态度是各个公司考虑的几个关键问题之一。与之相应，配送人员的工资也与配送单数有关，如何提高配送人员的工作效率，提高服务水平是目前较为热点的问题。从商店出发到各个地址进行配送，再回到商店可以看作是一个经典NP难问题。关于此类的解决方法有很多种：蚁群算法、多尺度路径算法、模拟退火法、粒子群算法等。考虑到蚁群算法的并行性、鲁棒性且可以很早避免早熟收敛等问题。本文通过蚁群算法对外卖人员配送路径进行规划，并取得了较好的结果。

1 蚁群算法

人工蚁群算法（Ant Colony Algorithm）简称蚁群算法，由意大利学者Dorigo M提出。该算法通过模拟蚂蚁觅食行为而设计[1]。1990 Deneubourg J.L等自发进行蚁群觅食的研究行动。通过实验最后得出蚁群觅食的路径选择和信息素浓度有关系，通过对信息素浓度的感知而选择路径，一般情况下蚂蚁会趋向于信息素高的地方移动。实验表明，路径越短的路径，信息素浓度越高，因而这条路径会逐渐逼近最优最短路径[2]。

图1是蚂蚁觅食图，如图1（a）所示，蚂蚁从巢穴出发寻找食物，有左右两条路径，从左右两条路径出发的蚂蚁数量相同。在某个时刻，当往右边路径出发寻找食物的蚂蚁寻找到食物时，左边路径上的蚂蚁还未寻找到食物，如图1（b）。当左边路径上的蚂蚁寻找到食物时，右边路径上的蚂蚁已经在返回巢穴的路上，如图1（c）。我们可以推断，在某个N个时间段后，右边路径上的信息素浓度比左边路径上的信息素浓度高，此时从巢穴出来的蚂蚁会更趋向于右边路径。

2 蚁群算法实现

初始时刻，各条路径上的信息素浓度相同，设tij（0）=C（C为常数）。蚂蚁k（k=1，2，3，…，m）在运动过程中根据各条路径上的信息素浓度决定方向。蚂蚁系统所使用的状态转移规则被称为随机比例规则，它给出了位于位置i的蚂蚁k转移到位置j的概率。在t時刻，蚂蚁k在位置i选择位置j的转移概率如公式（1）：

4 结语

综上所述，本文借鉴国内外相关路径优化的思想和理念，结合国内实际的配送的情况，将蚁群算法应用于配送路径中，为配送人员设计了一种提高工作效率且符合现实的路径，体现了配送路径规划的智能化和人性化。

参考文献：

[1]Colorni A，Dorigo M and Maniezo V. Distributed optimization by ant colonies[A]. Proc of lst European Conf. Artificial Life.Pans，France：Elsevier，1991，134-142.

[2]Deneubourg J.L.，Aron S.，Goss S.，and Pasteels J.M.The self-organizing exploratory pattern of the argentine ant [J]，Journal of Insect Behavior，1990，3：159-168.

[3]李山，王慧，王峥，等.中国观光旅游线路设计中的游时研究[J].人文地理，2005，20（2）：51-56.

[4]肇勇.改进蚁群算法的理论及方法研究[D].西南石油学院，2004.

[5]龚延成，郭晓汾，尤晓铃，等.基于遗传算法的物流配送车辆调度间题研究[J].数学的实践与认识，2004，34（6）：93-97.

[6]Dantzig G，Ramser J，The trunk dispatching problem [J]. Management Science，1959（6）：80-91.

[7]吴斌，史忠植.一种基于蚁群算法的TSP问题分段求解算法[J].计算机学报，2001，24（12）：1328-1333.

[8]张纪会，徐心和.一种新的进化算法-蚁群算法[J].系统工程理论与实践，1999（3）：84-87.