实现物流配送路径选择仿真系统的关键性问题探讨

冯向科　邓莹

摘要：该文以物流配送路径选择为研究内容，通过分析实现仿真系统的关键性问题，提出可行性解决方法，进行实验论证，提出实现物流配送路径选择仿真系统的方案，并在实践中得到验证。

关键词：物流配送路径选择；遗传算法；grp矢量图形格式；双缓冲绘图

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）36-8644-02

随着市场经济的发展和物流技术专业化水平的提高，物流配送业得到了迅猛发展。配送路径的选择是否合理，对加快配送速度、提高服务质量、降低配送成本及增加经济效益都有较大影响。配送路径的优化问题是物流配送系统的一个主要问题，物流配送路径的优化就是以最低的运营成本、最快捷的响应速度、最短的配送运输时间，把货物运至用户手中，并且在三个指标之间实现平衡。

在B2C农产品电子商务物流配送时，物流车装载当日需要配送的货品从仓库出发，按照事先规划好的最优配送路径为每一个客户进行配送，最后返回仓库。在配送之前需要根据客户的配送地址间线路间距、经验路况做分析计算出一条最优配送路径。在配送过程中，如果某路段堵车，需要动态调整配送路线。

实现物流配送路径选择仿真系统时，面临如系统架构、算法选择、数据存储和系统仿真问题等一系列技术难题，下面将逐一理清这些关键问题。

1 系统设计思想

将物流配送路径选择系统从应用角度分为数据库、接口服务层和客户应用三个层次，如图1所示。

图1 系统架构

1） 数据库层为整个系统提供数据支撑服务，它所包含的数据有配送地图数据和行驶轨迹数据，其中配送地图数据是支撑整个系统运行的核心所在。

2） 接口服务层以接口形式为整个系统提供基础性功能，接口服务可以和系统外部平台实现数据共享、服务共享。

3） 客户应用层面向系统的各个终端用户，主要为终端用户提供配送网络图形处理和配送过程演示控制功能，以配送地图数据为支撑，提示可视化、个性化的操作界面。

仿真系统拟实现的功能如图2所示。

图2 功能结构

2 算法问题

实现多目的地的物流配送路径选择理论上可以选用枚举法、回溯试探法等常规算法解决。采用枚举算法时，对问题的所有可能答案一一列举，然后根据条件判断此答案是否合适，合适就保留，不合适就丢弃。采用回溯算法时，按照深度优先策略，从始发地出发搜索解空间树。算法搜索到解空间树的任意一点时，先判断该点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。采用枚举算法和回溯算法的时间复杂法分别为O（nn）、O（n2） ，当n→+∞时，时间开销不堪重负，实践证明也是如此，在实验环境下，当n>6时，得到最优解的时间超过60秒，已经无法达到实时处理要求。

采用遗传算法，多次调优，确定合适的种群规模、交叉因子和变异因子，科学计算迭代次数，确保搜索最优（次优）路径所用时间较短。算法原型如下所示：

public class GA {//遗传算法类

//判断一个图是否为连通图

bool IsLinkGraph（double[，] graph）；

//获取最短路径

public List GetShortPath（GraphicContent content， List historyPoint， int flag）

//计算最短路径

List GetShortPath（double[，] graph， int source， int target， List passList，List clientPoints）

//初始化种群

void InitShome（double[，] edge， int source， int target， List passPath， List clientPoints）

//计算路径的适应值

double GetFitness（List path， double[，] graph）

//选择计算

void Select（double[，] graph）

//变异计算

void Change（）

//交叉计算

void Inter（）

//交叉运算

List InterCouse（）

//计算未被包含的结点数目

public int IsContailsAll（List list， List subList）

//返回路径长度

protected double GetLength（List path，double[，] edge）

}

在实验环境（CPU双核2.9MHz，RAM 4GB，Windows XP，.NET Framework 2.0，DirectX 9.0）下经过实验证明，当配送地址数量≤65个时，算法所用的平均搜索时间<10.0秒；只有当配送地址数量≥90个时，算法所用的平均搜索时间才会有显著增加，但总体仍在可以接受的范围之内。

图3 平均搜索时间

3 数据存储问题

系统中所使用的物流配送网络以图形文件形式存储，采用自定义矢量图形格式（.grp），存储内容包括配送地址（坐标位置、是否必须送达）、仓库位置、各个配送地址之间的路径信息（包括距离与行驶速度）等信息。

为防止保存在本地位置的物流配送网络图形文件被非法打开、篡改，导致重要信息被泄露，系统采用一种以异或运算为基础的对称式加密方法，对保存的图形文件内容结合密钥进行加密，在读取图形文件内容后，结合密钥对其进行解密。

4 系统仿真问题

实现系统仿真时，采用所见即所得的模型较为合适，方便用户操作。基于.NET Framework的GDI+绘图对象进行图形绘图，为解决绘图闪烁问题，宜采用双缓冲技术绘图，即按照如下步骤绘图：①在内存中创建与画布一致的缓冲区；②在缓冲区画图；③将缓冲区位图拷贝到当前画布上；④释放内存缓冲区。

为了更好地模拟汽车的行驶过程，采用图像旋转算法对汽车进行旋转，使其行进方向始终与道路贴合平行。采用仪表盘模拟汽车的当前行驶速度和当前行驶距离。系统仿真效果如图5所示。

图5 系统仿真实现

5 小结

采用遗传算法解决系统性能问题，采用grp自定义矢量图形格式解决图形数据存储问题，采用双缓冲技术解决绘图仿真过程的图形闪烁问题后，物流配送路径选择系统的全部关键问题都得以解决，仿真实现成为可能。以此为积累，指导学生参加第二届中国大学生软件设计大赛获决赛优秀奖。

参考文献：

[1] 王华.一种物流配送最短路径混合算法[J].测绘科学，2013（11）.

[2] 赵若彤.一种物流配送车辆路径智能优化算法研究[J].计算机与数字工程，2013（4）.

[3] 张静，卫文学，刘倩.基于遗传算法的物流配送路径优化算法[J].中国科技信息，2013（1）.

图3 平均搜索时间

3 数据存储问题

系统中所使用的物流配送网络以图形文件形式存储，采用自定义矢量图形格式（.grp），存储内容包括配送地址（坐标位置、是否必须送达）、仓库位置、各个配送地址之间的路径信息（包括距离与行驶速度）等信息。

为防止保存在本地位置的物流配送网络图形文件被非法打开、篡改，导致重要信息被泄露，系统采用一种以异或运算为基础的对称式加密方法，对保存的图形文件内容结合密钥进行加密，在读取图形文件内容后，结合密钥对其进行解密。

4 系统仿真问题

实现系统仿真时，采用所见即所得的模型较为合适，方便用户操作。基于.NET Framework的GDI+绘图对象进行图形绘图，为解决绘图闪烁问题，宜采用双缓冲技术绘图，即按照如下步骤绘图：①在内存中创建与画布一致的缓冲区；②在缓冲区画图；③将缓冲区位图拷贝到当前画布上；④释放内存缓冲区。

为了更好地模拟汽车的行驶过程，采用图像旋转算法对汽车进行旋转，使其行进方向始终与道路贴合平行。采用仪表盘模拟汽车的当前行驶速度和当前行驶距离。系统仿真效果如图5所示。

图5 系统仿真实现

5 小结

采用遗传算法解决系统性能问题，采用grp自定义矢量图形格式解决图形数据存储问题，采用双缓冲技术解决绘图仿真过程的图形闪烁问题后，物流配送路径选择系统的全部关键问题都得以解决，仿真实现成为可能。以此为积累，指导学生参加第二届中国大学生软件设计大赛获决赛优秀奖。

参考文献：

[1] 王华.一种物流配送最短路径混合算法[J].测绘科学，2013（11）.

[2] 赵若彤.一种物流配送车辆路径智能优化算法研究[J].计算机与数字工程，2013（4）.

[3] 张静，卫文学，刘倩.基于遗传算法的物流配送路径优化算法[J].中国科技信息，2013（1）.

图3 平均搜索时间

3 数据存储问题

系统中所使用的物流配送网络以图形文件形式存储，采用自定义矢量图形格式（.grp），存储内容包括配送地址（坐标位置、是否必须送达）、仓库位置、各个配送地址之间的路径信息（包括距离与行驶速度）等信息。

为防止保存在本地位置的物流配送网络图形文件被非法打开、篡改，导致重要信息被泄露，系统采用一种以异或运算为基础的对称式加密方法，对保存的图形文件内容结合密钥进行加密，在读取图形文件内容后，结合密钥对其进行解密。

4 系统仿真问题

实现系统仿真时，采用所见即所得的模型较为合适，方便用户操作。基于.NET Framework的GDI+绘图对象进行图形绘图，为解决绘图闪烁问题，宜采用双缓冲技术绘图，即按照如下步骤绘图：①在内存中创建与画布一致的缓冲区；②在缓冲区画图；③将缓冲区位图拷贝到当前画布上；④释放内存缓冲区。

为了更好地模拟汽车的行驶过程，采用图像旋转算法对汽车进行旋转，使其行进方向始终与道路贴合平行。采用仪表盘模拟汽车的当前行驶速度和当前行驶距离。系统仿真效果如图5所示。

图5 系统仿真实现

5 小结

采用遗传算法解决系统性能问题，采用grp自定义矢量图形格式解决图形数据存储问题，采用双缓冲技术解决绘图仿真过程的图形闪烁问题后，物流配送路径选择系统的全部关键问题都得以解决，仿真实现成为可能。以此为积累，指导学生参加第二届中国大学生软件设计大赛获决赛优秀奖。

参考文献：

[1] 王华.一种物流配送最短路径混合算法[J].测绘科学，2013（11）.

[2] 赵若彤.一种物流配送车辆路径智能优化算法研究[J].计算机与数字工程，2013（4）.

[3] 张静，卫文学，刘倩.基于遗传算法的物流配送路径优化算法[J].中国科技信息，2013（1）.