贪婪和A—Star算法在物流配送中的应用及仿真

摘 要：在物流的各项成本中，配送成本占了相当高的比例。因此，物流配送中最优路径选择对物流企业增加利润起着关键作用。采用科学、合理的方法来进行物流配送路径的优化，是物流配送领域的重要研究内容。本文深入研究A-Star算法，结合贪婪算法的思想，在QT Creator平台上，采用Visual C++编程对物流配送中路径的选择问题进行模拟仿真。通过再现交通运输环境，模拟物流运输中的突发事件，优化物流配送的路线。根据需求，设计出最短路径和最少时间的配送方式，并在地图上显示其对应的路径。通过本软件模拟解决物流配送中各种情况，从而降低运输成本。这对于提高物流配送决策效率以及降低物流配送成本具有重要的意义。

关键字：最优路径选择；A-Star算法；贪婪算法；模拟仿真

中图分类号：TP301.6 文献标识码：A DOI：10.3969/j.issn.1003-6970.2013.06.012

0 前言

物流与国民经济及生活的诸多领域密切相关，越来越多得到重视，甚至被看作是企业“第三利润的源泉”，而在物流成本方面，运输费用占大约50% ，比重最大[1]。因此，物流配送中最优路径选择的研究具有巨大的经济意义。物流配送中的最优路径选择问题的研究和应用都相当广泛，近几十年，国内外均有大量企业机构、学者对该问题进行了大量而深入的研究，取得丰硕的学术成果。如1953年，Bodin，Golden 等人便撰文综述了该问题的有关研究进展情况，列举了几百余篇相关文献，这些文献成为了早期车辆路径问题研究资料，随后随着该问题不断研究深入，约束模型及条件不断变化，车辆路径问题研究的最新进展可见Alt- inkerner 和 Oavish，Laporte，Salhi 等人的综述性文章[2]。围绕该问题的解决也极大推动了计算机学科的发展，不断有新的模型和算法推出。针对物流配送车辆路径优化问题的求解方法很多，根据算法原理的不同大致可分为两大类：精确算法和智能式启发算法。精确算法是指可以车辆路径问题的数学模型可求出其最优解算法，但由于算法存在诸多缺陷，所以在实际中应用并不广泛。目前，启发式算法是解决物流配送中最优路径选择的主要方法和主向[3]。近年来，随着科学的发展，一些新的启发式方法被用在求解物流路径选择及优化问题上，可以通过使用启发式方法获得较快的收敛速度和较高质量的全局解，常用的算法有模拟退火算法、GA 算法等[4]。A*算法是人工智能中一种典型的启发式搜索算法，被广泛应用于最优路径求解和一些策略设计的问题中[5、6]。本文结合贪婪算法的思想，深入研究A-Star（A*）算法，在QT Creator平台上，采用Visual C++编程对物流配送问题进行模拟仿真，同时考虑最短时间和最短路径两个方面，以此来解决物流配送中最优路径选择的问题，达到物流配送最优线路规划的目的。

1 需求分析

1.1 总体框架

在物流配送时，物流车装载当日需要配送的货品从仓库出发，按照事先规划好的最优配送路径为每一个客户进行配送，最后返回仓库。这就涉及在配送时配送路线的选择问题，而在配送之前，IT系统需要根据客户的配送地址间线路间距和经验路况分析计算出一条最优配送路径。并且在配送过程中，如果某路段发生堵车状况，需要动态调整配送路线，以达到最优配送的目的。为此，在QT Creator平台上，以面向对象的设计方式来开发最优物流配送的功能软件。通过再现交通运输环境，模拟物流运输中的突发事件，优化物流配送的路线，分别根据需求，设计出最短路径和最少时间两种配送方式，并通过二维动画的效果显示出来。通过此软件呆模拟解决物流配送中各种情况，从而降低运输成本。设计本软件的总体思路如图1所示。

1.2 功能设计

设计的软件从功能上来说，主要包括以下几点：

（1）载入一张已有地图（*.map的文件）或生成一张空白地图。用户可以在这张空白地图上操作，通过障碍物的增删来设置城市的道路。

（2）道路突发事件设置。

a.用户可以根据实际情况或主观意愿对地图进行规划。在地图中添加障碍物，设置道路前方的暂时封闭或者道路施工等未知路况。

b.也可以模拟城市人流量大的地方，通过在地图上，设置易堵车而导致前行速度下降的未知路况。

（3）设置仓库及客户点。

a.随机生成仓库及客户点。在地图中，用户可随机生成若干个客户点和仓库点。

b.指定生成仓库及客户点。在已生成或者模拟的地图上，根据用户的不同需求，可在地图上任意位置生成客户点和仓库点。

c.可以对仓库及客户点进行增删。

（4）计算路径及优化。

a.根据用户之前模拟的各种情况，计算其最短路径。根据用户载入或者自己规划的地图，模拟计算出最短路径，在界面的左上角显示其时间，并在地图上显示其路径。

b.根据用户之前模拟的各种情况，计算其最短时间。根据用户载入或者自己规划的地图，模拟计算出最短时间，在界面的左上角显示其时间，并在地图上显示其对应路径。

软件的大致功能如下图2所示。

图2 功能模块图

2 算法描述

2.1 贪婪算法

贪婪算法（Greedy algorithm）又叫登山法，它的根本思想是逐步到达山顶，即逐步获得最优解，是解决最优化问题时的一种简单但适用范围有限的策略[7]。

贪婪算法是基于邻域的搜索技术，它在计算过程中逐步构造最优解[8]。在构造解的过程中，每一步常以当前情况为基础根据某个优化测度（greedy criterion，贪婪准则，也称贪婪因子）作最优选择，而不考虑各种可能的整体情况，选择一旦做出就不再更改，这省去了为找最优解要穷尽所有可能而必须耗费的大量时间。它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，一般情况下只是近似最优解[9]。虽然贪婪法不是对所有问题都能得到整体最优解，但对范围相当广泛的求最优解问题来说，它是一种最直接的算法设计技术，通过一系列局部最优的选择，即贪婪选择可以产生整体最优解[10]。

对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择（贪婪选择）来达到。根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。它是一种改进了的分级处理方法。

2.2 A-Star算法

A*算法是人工智能中一种典型的启发式搜索算法，它是一种静态路网中求解最短路最优算法，其公式可表示为：

（1）

其中，是从初始点经由节点到目标点的估价函数；是在状态空间中从初始节点到节点的实际代价；是从到目标节点最佳路径的估计代价[11、12]。

在A*算法中，找到最短路径（最优解的）的关键在于估价函数的选取。当估价值到目标节点的距离实际值时，搜索的点数多，搜索范围大，效率低，但能得到最优解；当估价值到目标节点的距离实际值时，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解[13、14]。

A*算法的难点在于建立一个合适的估价函数，估价函数构造得越准确，则A*算法搜索的时间就越短[15]。A*算法的估价函数可表示为：

（2）

这里，是估价函数，是起点到节点的最短路径值，是到目标的最短路径的启发值。由于这个其实是无法预先知道的，所以我们用前面的估价函数做近似。当时，可以代替（大多数情况下都是满足的，可以不用考虑），但只有在时，才能代替。可以证明，应用这样的估价函数能有效地找到最短路径。

本文综合贪婪算法和A*算法的思想来求解决物流配送中最优路径选择的问题。图3为综合算法的流程图。

3 实验仿真设计

3.1 软件概述

开发的软件要具有实用性，这就是说，能给企业带来效益，这就包了两方面的内容：企业能获得的利润和客户的满意程度。也就是说采用所建立的模型要设计出合理的物流配送路线，保证在较短的路程或时间内遍历所有的节点，从而保证货物按时送到。

从算法角度来看，为了保证算法的有效性和高效性，结合软件的功能，则该软件的设计目标[16]为：①路径最短或时间最短， ②满足实际中遍历节点的要求， ③算法高效性， ④软件的普度适用性。

软件操作流程具体步骤如下：

第一步.用户载入一张已有地图或生成一张空白地图。

第二步.设置相关参数及约束条件。

第三步.显示计算结果和最优路径。

该软件可运行于Windows 7操作系统，主要包括3个部分：地图文件的读取部分、算法部分和用户界面部分。

3.2 软件模拟实现

1.初始化

根据软件的需求分析，本软件初始产生一个空白的二维平面图，在该模块用户可以根据实际情况模拟出实际路况，提供两种方式来实现该功能：

（1）通过点击工具栏上面的初始化按钮自动初始化。

（2）通过鼠标右键选择初始化选项。

图4 系统初始化界面

2.道路的参数设置

在视图界面中，用户可以点击鼠标右键，选择生成障碍物或删除障碍物来模拟现实生活中城市道路可能发生的各种情况，如：

（1）用户可以根据实际情况，点击鼠标右键，在出现的下拉菜单中，选中添加障碍物，设置道路前方的暂时封闭或者道路施工等未知路况。

（2）也可以在地图上，点击鼠标右键来设置易堵车而导致前行速度下降的未知路况。

在地图中浅黄色的区域是模拟人流量大的闹市区。深褐色方块模拟障碍物。

图5 道路模拟图

3.仓库点及客户点的生成

客户点和仓库点的生成包括两种情况：

（1）随机生成客户点和仓库点。在视图界面中，通过顶端的输入框，输入生成客户点或仓库点的个数，点击生成客户点或仓库点按钮来随机生成客户点或仓库点。

（2）在指定位置生成客户点和仓库点。在已生成或者模拟的地图上，根据用户不同的需求，在地图指定位置生成客户点和仓库点。

在如图5的道路设计下，在地图上随机添加了10个客户点和1个仓库点，如图6所示。

图6 场景界面图

4.路径最短和时间最短的配送路径

根据图6所设计的场景，通过贪婪算法和A*算法，分别计算出路径最短和时间最短的配送路径，并在地图上显示其路径。图7依据最短路径实现物流配送的最优方案，主要从距离这个方面进行考虑；图8根据最短时间实现物流配送的最优方案，主要考虑的是在道路有突发状况发生时物流配送的时间最少。

图7 路径最短的配送路径

图8 时间最短的配送路径

4 认识与结论

通过对物流配送中的实际问题进行模拟研究，在QT Creator平台上采用Visual C++编程开发出针对物流配送中最优路径选择问题的软件，从最短时间和最短路程两方面考虑，为物流配送公司提供可靠有效的参考信息，使配送方案符合实际情况。同时，深入研究了贪婪算法和A*算法，从算法的角度对物流配送中的时间和路程进行分析，设计实现了物流配送中最优数学模型，以期达到最优路径的目的。通过本研究的结果来看，开发的模拟软件能解决物流运送过程中的时间、路径等实际问题，同时实现了二维图形的可视化，更加直观地体现了物流配送中存在的问题和解决方式，对物流配送企业提高运营效率、降低运营成本等具有重要意义。

参考文献

[1]黄中鼎. 现代物流管理学[M]. 上海： 上海财经大学出版社， 2004， 1-37.

[2]谢秉磊， 郭耀煌， 郭强. 动态车辆路径问题：现状与展望[J]. 系统工程理论方法应用， 2002， 11（2）： 116-120.

[3]邹挺. 基于蚁群和人工鱼群混合群智能算法在物流配送路径优化问题中的应用研究[D]. 苏州： 苏州大学， 2011， 3-7.

[4]吴云志， 乐毅， 王超， 等. 蚁群算法在物流路径优化中的应用及仿真[J]. 合肥工业大学学报（ 自然科学版）， 2009， 32（2）：211-214.

[5]王海梅， 周献中. 直线优化A*算法在最短路径问题中的高效实现[A]. 全国第计算机技术与应用（CACIS）学术会议论文集（下册）[C]， 2008， 932-936.

[6]陈和平， 张前哨. A*算法在游戏地图寻径中的应用与实现[J]. 计算机应用与软件， 2005， 22（12）：94-96.

[7]晏杰. Matlab 中贪婪算法求解背包问题的研究与应用[J]. 赤峰学院学报（自然科学版）， 2012， 28（9）：23-24.

[8]刘纪岸， 周康渠， 宁李俊， 等. 基于贪婪算法的摩托车生产物流配送规则优化[J]. 制造业自动化， 2010， 32（5）：97-99.

[9]蒋建国， 李勇， 夏娜. 一种求解单任务Agent联盟生成的贪婪算法[J]. 系统仿真学报， 2008， 20（8）：1961-1964.

[10]江朝勇， 陈子庆， 谢赞福. 基于优先级贪婪算法的排课系统排研究与实现[J]. 信息技术， 2008， 24（7）：173-176.

[11]徐伟， 孙士兵. 基于A-Star算法警用地图查询系统的设计与实现[J]. 信息安全与技术， 2011. 5-2：52-56.

[12]王敬东， 李佳. A*算法在地图寻径中的实用性优化[J]. 电脑开发与应用， 2007， 20（7）：24-25.

[13]（美）Stuart Russell，（美）Peter Norvig. 人工智能——一种现代方法[M]. 姜哲，译. 北京：人民邮电出版社， 2004， 76-83.

[14]王文杰， 叶世伟. 人工智能原理与应用[M]. 北京：人民邮电出版社， 2004， 115-121.

[15]章冲， 李代伟， 黄明. 基于A-star算法的矿井事故救援研究[J]. 成都信息工程学院学报， 2010， 25（3）：64-68.

[16]宋鸽， 王子牛. 蚁群算法优化车辆路径问题的研究[J]. 贵州大学学报（自然科学版）， 2010， 27（2）：115-118.