项目经历介绍

1. 长距离骑行路径规划应用

Java, Swing, Graphics2D, OpenStreetMap

基于OpenStreetMap开源地图数据，绘制地图瓦片，实现多级瓦片地图交互系统，动态显示地图。构建路网用于路径搜索，根据用户提供的起始点搜索路径，并能将路径结果导出至GPS设备。

1.1 绘制地图瓦片

基于OpenStreetMap开源地图数据，绘制地图瓦片。查看一个地图数据的样例。

1.2 调整绘图精度

针对地图的不同缩放级别，利用Douglas–Peucker算法调整绘图的精细度，从而加速地图瓦片的绘制速度。

1.3 地图瓦片的缓存机制

呈现地图时，为地图瓦片设计LRU缓存机制和预加载机制，降低I/O操作频率，提高应用响应速度。

1.4 降低搜索空间大小

压缩路网非岔路结点，将搜索空间降低约50%，减少了因搜索无效结点造成的时间浪费。

1.5 利用 k-d 树搜索临近结点

利用k-d树搜索二维路网的最近结点，将搜索时间复杂度从O(N)降至O(logN)

1.6 基于 A* 搜索 改进的近似算法

传统 A* 搜索算法的目标为寻找最优路线，依照优先级选择下一个访问点，优先级的计算方式为：

其中：

• $f(n)$ 是结点 n 的总优先级
• $g(n)$ 是从起始点到结点 n 的成本
• $h(n)$ 是结点 n 到目标结点的预估成本

项目中 $h(n)$ 被选定为结点 n 到目标结点的直线距离，此时预估距离小于等于实际最短距离，一定能找出全程最短路径。

通过将 $h(n)$ 增大到超过实际最短距离（可通过乘上一个固定的系数实现），可将算法变为近似算法。本项目中，$h(n)$ 在增大到 1.5 倍时，搜索速度平均提升了约15倍，与最优路径平均偏差约4%

1.7 搜索结果导出

可将搜索结果导出为GPX文件，并导入至GPS设备中使用

• GPX - 维基百科，自由的百科全书

• 户外骑行GPS设备样例：Garmin佳明 Edge520 PLUS

2. 利用随机局部搜索算法解决旅行推销员问题

目标：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。

• 问题复杂度为 O(N!)，无法在有限时间内得到最优解，可利用随机局部搜索算法获得次优解
• 使用模拟退火和禁忌搜索算法优化局部搜索，避开局部最优陷阱，所得结果与最优解偏差约 1%

3. 利用遗传算法解决航班编排问题

目标：在给定的航线集合中，选出最优航线子集，使得所有航段被覆盖一次且总费用最优。该问题属于集合覆盖问题，是NP完全问题。

• 针对杂交变异后生成的子代变为不可行解的问题，应用启发式改进算法（参考文献 [1]，p331 Algorithm 1），使其符合或接近条件限制
• 在子代种群排序时应用 Stochastic ranking 算法（参考文献 [2]，P5），引入随机因子，以一定概率提高不可行解的存活率，保证候选种群的多样化

测试数据

http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/sppnw41.txt

http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/sppnw42.txt

http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/sppnw43.txt

参考文献

[1] P.C. Chu, J.E. Beasley, Constraint Handling in Genetic Algorithms: The Set Partitioning Problem, Journal of Heuristics, 11: 323–357 (1998). 查看论文

[2] T.P. Runarsson, X. Yao Stochastic ranking for constrained evolutionary optimization, IEEE Trans. on Evolutionary Computation, 4(3): 284-294 (2000). 查看论文