基于动态规划的自驾旅游最短路径

摘要

为探索从西安市出发的自驾游最佳路径，以实现费用最优和旅游体验最佳为目标，构建了各省旅游景点的最短路径数学规划模型，并利用遗传算法对该问题进行求解，得到了各省旅游的最短Hamilton圈.接着，建立了一个符合约束条件的单目标0-1规划数学模型，并采用遗传算法进行求解，得出了从西安出发游遍201个5A级景区所需的最少时间为10.37年，并提供了年度旅游线路安排建议.最后，建立了动态规划数学模型，并采用动态逆序法对每次旅行的路线出发地、行车时间、行车里程以及游览景区进行了详细的求解，并提供了具体的旅行行程安排.通过测算，旅游出行的满意度为0.81,表明旅游体验较高，假期利用率充足，行车时间较短.

关键词

Hamilton圈 / 遗传算法 / 0-1单目标规划 / 动态规划