随着市场竞争加剧, 物流量逐步增长, 运输、仓储和配送一体化趋势日益明显。如何在有效降低物流配送费用的同时, 提高配送时效, 成为各物流公司和工商企业普遍关注的焦点。本文研究高效的仓储物流配送算法, 借助GIS技术, 采集、加工和处理物流节点地理位置和交通路线等信息, 充分发挥其强大的空间数据管理和空间分析能力, 动态优化配送路线并可视化输出, 从而提高物流配送服务水平、降低物流配送成本[1,2]。

车辆路线问题 (Vehicle Routing Problem, VRP) 发展至今已有50多年的历史, 是网络优化问题中最基本的问题之一。在VRP中, 有一定数量的客户, 分别有不同数量的货物需求, 由一个车队从配送中心向客户分送货物, 规划配送路径, 在一定的时间、成本约束下, 实现最优配送[3]。

按照求解精度不同, VRP方法可分为精确算法和近似算法[4,5]。前者包括分支界限法、动态规划法等;后者则进一步细分为构造启发式算法、两阶段启发式算法和智能化启发式算法。需要注意的是, 精确算法引入了严格的数学方法, 计算复杂度高, 问题规模稍大时将引发指数爆炸, 只适用于求解较小规模的问题, 且实际应用范围很有限。目前, 启发式算法是求解VRP问题的主要方法:构造启发式算法从初始解出发, 通过搜索邻域进行不断修正, 能够在较短的时间内求得可行的满意解, 但不一定是最优解;两阶段启发式算法在第一阶段使用构造启发式算法求得一个可行解, 在第二阶段通过插入法、两元素优化算法等改进目标函数, 加入人的主观能动作用, 但算法的优劣往往取决于算法设计者的实际经验;智能化启发式算法引入神经网络、遗传算法、蚁群算法等人工智能领域的经典理论来求解VRP问题, 涉及复杂的领域转换和求解策略, 算法复杂、运算量大, 问题规模较大时无法求得满意解。

对比各类VRP求解方法的特点及实用效果, 本文选取构造启发式算法中的节约里程法作为仓储物流配送路线优化设计的核心算法。由于节约里程法执行的初始条件是配送中心到各个客户的最短路线, 这里先结合GIS电子地图, 使用Dijkstra算法求得单源最短路线, 然后再使用节约里程法优化这些路线。

Dijkstra算法是经典的单源最短路线算法, 按路径长度递增的次序产生某个源点到其余各个终点的最短路径。给定带权有向图G= (V, E) 和源点v0, 求从v0到G中其余各顶点的最短路径。Dijkstra算法的基本思想是, 设置已求出最短路径的终点集合S (初始时只包含源点v0) , 其余顶点组成集合V-S (初始时为V-{v0}) 。算法将按各顶点与v0最短路径长度递增的次序, 逐个将集合V-S中的顶点加入到集合S中。在这个过程中, 总保持从v0到集合S中各顶点的路径长度始终不大于到集合V-S中各顶点的路径长度。

节约里程法是求解运输车辆数目不确定的VRP问题的最有名的启发式算法, 其原理简单 (三角形一边的长度小于另外两边之和) 、易于扩充。节约里程法的目标是使总的车辆运输的吨公里数最小, 根据配送中心的运输能力、配送中心到各个客户以及各个客户之间的距离来制定配送方案, 依次将运输问题中的两个回路合并为一个回路, 每次使合并后的总运输距离减小的幅度最大, 直到达到一辆车的装载限制时, 再进行下一辆车的优化。

基于GIS的配送路线优化设计方案如图1所示

图1 基于GIS的配送路线优化方案   

本文选用Arc GIS 9系列软件, 辅以二次开发工具Map Object控件及可视化编程语言Visual C#实现上述优化方案, 采用SQL Server 2000作为后台数据库[6]。某配送中心向8个客户配送货物, 从电子地图提取的道路网如图2中细线所示, 各客户点旁括号内的数字表示该客户的需求量 (t) 。配送中心有载重量为2和4t的两种车辆可供使用, 但车辆一次巡回的行驶距离不能超过30km。执行Dijkstra算法计算配送中心至各客户的最短可达路线, 如图2中粗线所示;在图2的基础上, 执行节约里程法优化配送中心至各客户的最短可达路线, 如图3所示, 共计节约51km配送里程。

图2 配送中心至各客户的最短可达路线   

配送路线的优化, 是配送优化中的一个关键环节, 直接影响配送速度、成本和服务质量。本文把GIS等地理信息技术引入物流配送和物流信息化解决方案, 实现了配送路线优化和可视化, 有效减少了配送里程、降低了车辆空载率。车辆路线问题的约束条件较多, 本文考虑了货物需求量、车辆容量限制、行驶里程限制等几个方面, 在今后的工作中将进一步考虑交发货时间、车辆数量等限制, 使基于GIS的仓储物流配送路线优化方案更加实用。

图3 优化后的配送路线