2022年电工杯获奖,代码全,最终拿了二等奖。
本文针对一个类旅行商问题,并未沿用传统思路,而是将其视作一个车辆规划模型,
使用搜索的方式列出可能性,再通过启发式算法来对所有的可能性做出选择,能够在保
证准确率的同时,极大的缩短模型运行的时间,达到更高的效率。
问题一中,针对一个类旅行商问题,本文建立了一个基于模拟退火(SA)和深度优
先搜索(DFS)的类旅行商问题(TSP)求解模型,得出的最优解共计配送里程 582km。
问题二中,对于多个路径叠加的问题,本文建立了一个基于粒子群优化(PSO)的
广度优先搜索(BFS)模型,共计配送时间 380 分钟。
问题三中,针对并非常规的 TSP 问题,本文将其视作一个车辆路径问题(VRP),使
用 K-means 的方法进行划分,然后建立了一个基于遗传算法的车辆路径规划模型,最终
的结果有超过 50%的概率能够收敛到全局最优。
问题四中,对于一个更复杂的路径规划问题,依然先使用 K-means 的方法对整个图
进行分区,分区后再将每个区视作一共车辆路径规划问题,建立了一个基于遗传算法的
车辆路径规划模型。
本文最大的特色是本文选择带入