物流配送中的最优路径规划模拟软件研究与开发

2014-09-24蒋秀莲张亚楠宋祎宁韩莉嵇杰

软件工程 2014年6期

蒋秀莲+张亚楠+宋祎宁+韩莉+嵇杰

摘要：信息社会，企业间的竞争日渐激烈。随着网络购物的普及，物流配送日渐发展壮大，已成为第三方利润源泉，受到物流等相关企业的高度重视。合理科学的物流配送路径，可实现快速配送、提高配送质量、降低配送成本，提高经济效益。使用软件模拟物流配送中的路径规划问题，对于物流企业选择优化的配送路径和信息化具有一定的意义。

关键词：路径优化；A Star算法；Java

中图分类号：G642 文献标识码：A

Research and Development of Simulation Software for Optimal Path

Planning in Logistics Distribution

JIANG Xiulian，ZHANG Yanan，SONG Yining，HAN Li，JI Jie

（School of Management，Xuzhou Institute of Technology，Xuzhou 221008，China）

Abstract：In the information society，the competition among enterprises is increasingly fierce.With the popularity of online shopping， logistics distribution gradually development and growth，has become the third profit source，subject to logistics and other related enterprises attach great importance.Reasonable and scientific logistics distribution path，which can realize fast delivery，improve the quality of distribution，reduce distribution costs，improve the economic benefit.Use software to simulate the path planning problem in logistics distribution，for logistics enterprises to select optimal distribution route and the information has certain significance.

Keywords：path optimization；A star algorithm；Java

1 引言（Introduction）

配送是物流中的关键环节，优化配送路径，可以较低的运送成本、快捷的响应速度、在最短的时间内，把货物送至用户手中。为达此目的，企业需要对配送过程进行科学合理的规划，此规划过程主要包括三方面的因素：时间因素，成本因素，环境因素。物流配送环节涉及的时间因素包括：对客户的要求给予及时快速响应、确保货物安全准时送达目的地；配送成本因素主要解决的问题是如何最大限度地减少运送车次，包括购置车辆成本及在货品运输中的损耗、配送工人工资等；环境因素主要包括最大限度地避免不必要的运输行驶，这样可减少交通拥堵以及空气、噪音的污染等。在当今不断发展的电子商务背景下，消费者网上购物次数较多，物流企业主要依赖电动车完成货物配送，存在较大的安全隐患。如何针对网络交易不断发展的新形式，降低配送成本，提高配送效率，减少安全隐患是摆在企业面前的重要问题。电子商务的蓬勃发展为使物流发展萌生了一系列新的特点，如信息化、自动化、柔性化、网络化、社会化、标准化等。面对这些变化，根据企业的实际能力和客户的现实需求建立强有力的配送系统是物流企业的现实选择。物流配送中涉及到的配送路径的选择、到达客户时间的选择等一系列问题都直接关系到企业的运作成本和信誉。如物流配送没有能够按照客户的要求进行，则货物可能被拒收甚至退货，这样就会对企业产生极为不利的影响，在信息化时代的网络购物不断发展的环境下更是如此。针对以上情况，本文着力开发一种物流配送最优路径规划模拟软件，以期能够更好的帮助物流企业解决当前普遍存在的配送成本高、路径选择难度大、顾客满意度低等一系列问题，解决好“最后一公里”问题，使物流企业能够对电子商务下的订单做出最快反应，不断提升企业的核心竞争力。

2 系统分析（System analysis）

在B2C电子商务物流配送中，配送运输车辆装载当天要配送的货品从仓库出发，按照规划好的最优配送路线为客户配送货品，最后返回仓库。IT系统在配送之前需要根据客户的配送地址间线路间距、经验路况做分析计算出一条最优配送路径。在配送过程中，如果某路段堵车，则需要动态调整配送路线。物流配送路径优化模拟软件按照物流配送日常流程进行设计，要保证系统运行流畅，并充分满足路径优化各方面需求。此外，界面应做到布局合理、模块清晰。

使用Java语言开发设计物流配送路径优化模拟软件，Java技术具有卓越的通用性、高效性、平台移植性和安全性[1]。模拟软件主要具有以下功能：可以自由选择起点，可以自由选择终点，可以根据实际情况修改障碍物的位置与数量，动态生成最优化路径。用户通过使用物流配送路径优化模拟软件，能高效完成路径的优化选择。通过模拟软件，能够避开障碍物陷阱，快速到达目的地。

物流配送路径优化模拟软件为普通物流配送提供了一个信息化的模拟平台，算法的效率直接影响路径选择的效率，算法应该能够避免现实路况中可能的陷阱。路径搜索是路径规划的首要问题，路径搜索和规划大致分为两类，全局规划方法和局部规划方法。在全局规划方法中将障碍物映射到构型空间，得到障碍区域和自由区域然后在自由区域里寻找最佳路径，在此基础上发展了许多智能算法，包括A Star算法，D Star算法，遗传算法，模拟退火算法和蚁群算法。本模拟软件路径选择优化采用A Star启发式搜索算法，对于路径搜索过程中的路径分支进行评估，以选择最佳分支，并且具有可采纳性，若存在问题的解，则一定能够找到[2]。endprint

3 A Star算法分析（A Star algorithm analysis）

A Star算法最初来源于DFS与BFS两种搜索策略，将各种不同的搜索问题抽象为搜索树的形式，为其后进行的优化打下基础。A Star算法作为启发式算法中重要的一种，被广泛应用在最优路径求解和一些策略设计的问题上。A Star算法的核心部分，是其中一个估值函数f（n）=g（n）+h（n）的设计。A Star算法的核心是每次选取下一个当前搜索点时，是从全部已探知的但未搜索过的点中，选取f值最小的结点进行展开。而所有“已探知的但未搜索过点”可以通过一个按f值升序的队列（即优先队列）进行排列。这样，在整体的搜索过程中，只要按照类似广度优先的算法框架，从优先队列中弹出队首元素（f值），对其可能子结点计算g、h和f值，直到优先队列为空（无解）或找到终止点为止[3]。A Star算法与BFS和DFS的关联在于，当g（n）=0时，类似于DFS，当h（n）=0时，类似于BFS。

4 软件程序类设计（Software program class design）

系统主要包含UML整体图、Main类、Map2D类、MapOperator类、MapTemp类、PathFinder类、TileAssemble类、TileObjectAbstract类等。在Main类里，通过构建run线程，控制程序界面的显示，加入键盘监听，用来显示菜单以及各类结点的显现。利用Map2D类初始化程序界面，设定界面的宽和高，并且规定了模拟中各节点的大小。使用MapOperator类设定宽度值、长度值以及地点、终点和障碍物的坐标，绘出界面背景以及路径。MapTemp类作为地图类，作用为初始化地图、障碍物等。PathFinder类为算法的核心类，用于构建OpenList与CloseList，增加寻找邻居节点方法、寻找周围最合适节点方法以及构建路径结构方法。TileAssemble继承TileObjectAbstract类，并构建了Start类、Empty类、Block类、Goal类、Path类，可以在面板上画出不同类型节点。TileObjectAbstract类作为一个抽象类，用来判断路径中所寻找的节点是否为障碍物，并且使用displayMyself方法绘出各种元素。

5 系统实现（System implementation）

为了使模拟软件更加易用，直接采用提示面板的方式，用空格键控制菜单的显示与消失。菜单内容上做到了简洁明了。

部分核心代码如下：

public class PathFinder {

private LinkedList m_openList；

private LinkedList m_closedList；

public PathFinder（）{

this.m_openList = new LinkedList（）；

this.m_closedList = new LinkedList（）； }

public LinkedList findPath（Map2D map） throws NullPointerException， ClassNotFoundException{

this.m_openList.clear（）；

this.m_closedList.clear（）；