软件说明书(珠穆朗玛队)-TSP.doc

第二届中国软件杯大学生软件设计大赛参赛作品
软件说明书
参赛题目: 物流配送中的最优路径规划模拟软件
团队名称: 珠穆朗玛队
队长: 唐少东
队员: 王焕桂、郭康龙
指导教师: 胡泽军
学校: 广东机电职业技术学院
2013年6月10日
目录
目录 1
第一篇软件设计说明书 3
1、我们的作品效果 3
2、项目背景 6
3、系统需求 6
4、系统技术路线 7
6、系统总体设计 9
9
12
7、系统功能设计 12
12
13
13
模拟运行 14
数据保存 14
8、核心算法设计 16
最短路径生成算法 16
狩猎算法 16
2-Opt算法 17
3-Opt算法 17
LK算法 18
单亲遗传算法 19
链路断路修复算法 21
第二篇需求规格说明书 23
1、项目背景 23
2、运行环境 24
24
硬件要求 24
: 24
3、功能需求 24
25
25
26
模拟运行 26
数据保存 27
4、非功能需求 27
27
27
27
28
第三篇软件测试说明书 29
1测试概述 29
2编写目的 30
3软件测试 31
31
31
31
31
32
: 32
: 32
4软件测试报告 36
36
36
50
berlin52 50
ch130 51
tsp225 52
54
berlin52() 54
ch130(最优解6110) 55
tsp225(最优解3859) 56
5测试结论 57
第一篇软件设计说明书
1、我们的作品效果
我们选择了德国海德堡大学提供的tsplib库中多个例子进行测试,图1是tsp225的规划结果和模拟运行的情景(最优解)。
图1 tsp225规划结果及模拟运行情景
作品特色一:软件规划效果非常好(见表1)
在有限且合理时间内得到结果
规划节点数量大( 7000个节点)
不要求最优解时,4GB内存可规划7000个节点。软件可以规划节点数仅受限于内存大小。
可求解300多个节点的最优解(国内领先水平)
(实例数据来自于德国海德堡大学公开的tsplib)。
表1、Tsplib测试数据
实例数据
节点数
当前最优解
我们的解
是否最优
lin318
318
42029
42029
最优
a280
280
2579
2579
最优
tsp225
225
3916
3916
最优
ch150
150
6528
6528
最优
pr144
144
58537
58537
最优
ch130
130
6110
6110
最优
kroA100
100


最优
eil76
76


最优
berlin52
52
7542
7542
最优
att48
48
33524
33524
最优
dantzig42
42
699
699
最优
作品特色二:软件运行速度非常快:
多核编程、并行计算
软件采用多核编程技术,充分利用硬件资源进行并行计算,加速规划过程。
C++语言实现(速度快)
软件采用C++语言编写、界面编写难,但运行速度明显高于其它语言编写的程序。
特色三:软件功能齐全、完全达到大赛的要求,并超出大赛要求:
标定客户坐标。
导入客户坐标。
随机生成客户坐标。
保存规划结果。
动态规划,模拟断路,并以不同颜色和线型表示堵车事件。
鲁棒性好(健壮性好,体现在堵车断路时)
2、项目背景
随着市场经济的发展和物流技术专业化水平的提高,物流配送业得到了迅猛发展。配送路径的选择是否合理,对加快配送速度、提高服务质量、降低配送成本及增加经济效益都有较大影响。配送路径的优化问题是