基于路网配送路线优化教学软件开发

陈嘉楠 杨松 刘士广 侯一萌 应博智

南京农业大学工学院 210031

基于路网配送路线优化教学软件开发

陈嘉楠 杨松 刘士广 侯一萌 应博智

南京农业大学工学院 210031

当前，国外对于VRP问题的研究已经应用于生产，生活等多个领域。但是，VRP问题的研究，尽管摆在了高校的课本中，但是在教学演示方面遇到很大的问题，无法向学生形象生动的演示算法过程。为了提高教学质量，解决教学演示的相关难题，本项目设计了教学软件系统，达到了对该问题的分步演示及可视化, 改善了教学方法，并初步应用到了校内的教学演示，取得了良好的效果。

随机路网；VRP；节约算法；教学软件

1 研究背景

当前，现代物流已被公认为是企业在降低物质消耗，提高劳动生产率以外创造利润的第三个重要源泉，也是企业降低生产经营成本，提高产品市场竞争力的重要途径，而发展现代物流则需要一批高素质的物流专业人才队伍。高校本着与时代接轨的目的，纷纷开设物流相关专业，用以满足社会对物流人才的需求。

但目前，各高校对配送车辆路线优化问题的教学，仅仅流于刻板的理论教学的形式上，教学模式陈旧，局限于从有限的课本上获取物流方面的知识，未能直观的反映车辆路线问题的模型，造成专业人才的稀缺。正是基于这样的物流教学现状，我们利用了计算机软件Visual Basic，将VRP领域的算法进行分类比较，并最终选取了启发式算法中的节约算法，并将其算法步骤编程，开发出应用VRP模型教学的软件，具有重要的实际意义与现实意义。

2 软件的功能分析

制作软件的标准，以便于教学，直观反映问题为目标。为此，我们详细地调研分析了VRP问题在实际教学过程中所遇到的各种问题，并以此作为软件功能设计思路。

软件分为三大功能:

2.1 整体演示功能

此功能的想法初衷，是为了让使用者对VRP问题有个较为清晰的认识，软件界面的设计采用了选择菜单的多窗体，以尽可能的体现软件的强大功能为目的，加以操作软件的演示，形象直观的反映软件的功能与作用。

2.2 分步演示功能

作为软件设计的核心，分步演示功能是基于教学的应用考虑，将解决VRP问题的具体过程，体现在了软件的应用功能当中。在随机路网的生成的基础上，以随机节点数为20，客户数目为10，车辆载重量为4，为例，具体的软件的计算过程图为:

第一步:输出路权矩阵表。

第二步:输出最短距离矩阵。

第三步:输出节约矩阵。

第四步:用节约算法求配送路径的输出计算结果生成过程。

第五步:输出最终配送路径结果。

2.3 随机练习功能

在做完演示功能等作用之后，软件还考虑到学生的自学等因素，添加了随机练习功能。本作品避免了传统软件的冗杂的输入数据，采用随机数组，即:随机路网，随机需求量，默认配送中心等，并将得到的随机数据输出，方便了题目的设计，灵活多变，并根据做题过程的中间数据，完成自我的检测，给自我学习能力得到不小的提升。

3 软件开发的关键技术问题

随机配送路线网络图的生成，其核心思想在于将界面中的随机点，以连接最近点为原则，呈十字形连接，这样克服了以往随即连线会生成新节点，从而导致确定路权矩阵难的问题。

传统的随机路网同本作品的软件作图直观比较:

由此，可以直观地看到，传统的随机路网并没有解决随机连线的新节点所带来的路权矩阵混乱问题，由此说明，我们随机路网的科学性与突破性。

4 创新特色以及应用前景

4.1 创新特色

在基本车辆路线问题（VRP）的基础上，本作品将其延伸和作以相应的优化。具体体现在:随机需求车辆路线问题（vehicle routing problem with stochastic demand，VRPSD），在生成随机路网的前提下，本作品还加以极具创新的随机客户端，随机客户端需求量等。

本作品中随机路网的生成是先随机产生点，然后连接相邻几条不相交的线，克服了以往随机连线生成许多新节点，导致确定路权矩阵难的问题；采用Floyd算法计算最短路径；节约算法计算配送路径，保证软件计算的科学性与创新性。

本作品开发了图形化界面，增强了直观性，比单纯的数字讲解更易理解。能随机产生例题，克服例题少不好学的情况；能随机生产练习题，强化对问题的理解；能求解多车辆的VRP问题，比仅有单车辆TSP问题更接近实际。

4.2 应用前景

该作品作为辅助教学类软件，将提高教学质量作为软件开发的宗旨，更加贴切学生自主动手能力解决身边问题的教育思想。软件的需求说明书以及后期显著的实践教学，都充分说明了其广泛的应用前景，一经推广，必然会掀起一股高校的物流教学热，也是由于其让学生更加明晰理论知识，让教师授课更加生动形象。

该作品的使用范围为现阶段高校的物流教学相关的人群，将作品实物化，软件化，推广具有可行性，推广应用前景深远，有着良好的市场前景与经济效益。

[1] 张强，荆刚.车辆路线问题研究现状及发展方向.交通科技,2004，60-150

[2] 张学志,陈功玉.车辆路线安排的改进节约算法.系统工程, 2008.11

[3] 郎茂祥.配送车辆优化调度模型与算法.电子工业出版社,2009.3

[4] 聂艳芳.VRP的数学模型及算法分析.山西电子技术,2010.1

[5] Laporte G, GendreauM, Potvin J Y.Classical andMod2ern Heuristics for the Vehicle Routing Proble J ].IntlTrans in Oper Res, 2000, 7 (4 /5) : 285 - 300.

10.3969/j.issn.1001-8972.2012.13.046