Skip to content

南邮大创项目,旨在用超启发式算法解决CVRP问题

License

Notifications You must be signed in to change notification settings

Ellsom1945/Routing-problem--CVRP

Repository files navigation

Routing-problem--CVRP


项目准备阶段

准备相关论文,设计准备数据集,最终决定采用CVRPLIB上的标准数据集作为实验用数据。

项目第一阶段

参考论文用各种元启发式算法求解CVRP问题

采取的算法主要有:

在实验前期出现的问题主要有:

  • 遗传和粒子群算法由于参数过多,时间复杂度高,且收敛不稳定

  • 贪心策略设计过于简单,效果很一般,但好在时间复杂度低

  • 禁忌在前期的表现最优,其原因在于该算法的设计原理是找初始解的局部最优解,搜索域相较于整个解空间要小很多,其次选用贪心的结果作为初始解,部分问题的最优解特征与贪心的结果路径特征较为一致,导致在项目前期贪心+禁忌的组合效果一直最好

第一阶段的项目效果可参考表格

项目第二阶段

项目第二阶段采取针对不同的算法进行优化,并加入一些其他种类的算法作为尝试

采取的算法主要有:

这阶段的各个算法的问题主要有:

  • 改进粒子群在时间复杂度和效果和上次比都有很大提升,但当数量级达到103的时候,时间还是很不理想

  • 遗传-退火

  • 快速贪心主要采用了KD-Tree+最小堆的,主要算法思想就是利用KD-Tree来聚类,再利用最小堆,以边为操作对象,拼出若干条路径,这个算法的思路是我觉得现阶段最合理的,先聚类再分别解决每条路径,首先时间复杂度很低,用于解决较大数量级问题是个不错的选择,其次,这个算法的思想也很合理,比较符合现代物流分层的设计方式,可惜实现的时候技术欠佳,未能达到该算法的本来效果

  • 改进蚁群主要是加入了负反馈机制,效果比原先的蚁群算法是要好上不少,但这类元启发算法仍存在参数多时间复杂度高这一问题

  • 粒子群-禁忌就是在改进粒子群的基础上加一个局部搜索得到

  • ortools 是利用Google的开源框架ortools实现的,ortools是一套约束问题、线性规划、图形算法工具包,这套算法其实已经足够优秀,这套工具包已经足够优秀,在规模处于103以内的问题基本都能输出最优解,而且时间足够优秀,但由于算法都是利用的内置的足够优秀的模型求解该问题,而且由于底层互相引用过于复杂,导致我花了很长时间都未能成功了解该模型的求解流程,且我们的项目目标是构建超启发式算法,无奈只能放弃这个完美答案,但如果要真正求解该类问题,这个工具包一定是我首选的方法

第二阶段的项目效果可参考表格

项目第三阶段

着手搭建超启发式算法框架

主要利用的算法是:

该阶段主要问题有:

  • 由于从未涉足过深度学习,神经网络等领域,要想从头搭建网络框架难度过大,于是又只能求助于各种深度学习开源框架,现阶段主流框架有TensorFlowkerascaffeMicrosoft Cognitive ToolkitPyTorch...,鉴于各大框架的上手难度以及开源项目数量,最终选择TensorFlow来搭建DQN神经网络,没错这个TenserFlow又是谷歌的团队开发的

  • 接口也是一个问题,由于DQN网络的输入是固定的action+state格式,需要将CVRP模型的部分特征提取为state,这里主要参考论文

项目第四阶段

设计适合该超启发式算法框架的底层算子

主要算子参考论文

该阶段作为项目的收尾阶段,我总结一下整个项目和CVRP问题研究心得:

About

南邮大创项目,旨在用超启发式算法解决CVRP问题

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages