如何使用Optaplanner解决旅行商问题（TSP）？

站长

2024年04月06日 17:46 · 阅读数 14

引言

这次来学习Optaplanner中TSP（traveling salesman problem）旅行推销员问题。旅行推销员问题是一个著名的组合优化问题，被定义为在访问给定的一组城市并回到起点的情况下，寻找最短的路径。这个问题在计算机科学、数学和运筹学等领域都有着广泛的应用。如何使用Optaplanner解决旅行商问题（TSP）？

Optaplanner中的TSP

TSP例子在Optaplanner里很重要吗？学习 OptaPlanner 时，理解Chained Planning Variable（链式规划变量）这一重要概念非常必要。通过 TSP 例子的学习，可以深入了解链式规划变量在路径优化中的高效应用。此外，掌握链式规划变量可以为后续学习 Chained Through Time 模式（也称作 Chain of Custody 或 Time Chain是一种用于解决顺序规划问题的模式）提供帮助，因为这种模式也是用于解决顺序规划问题的一种重要模式。

TSP定义与挑战

**问题定义：**给定一个城市列表，寻找一个旅行商访问每个城市恰好一次的最短路径。虽然旅行商问题的定义很简单，但它是一个非常具有挑战性的问题，因为它属于 NP-hard 问题，这意味着即使对于问题规模较小的数据集，也需要耗费大量的时间和计算资源才能找到最优解。此外，当稍微改变数据集时，最优解也可能会发生很大变化，这让解决该问题变得更加困难。

问题规模

来看下官网给出的案例中的数据规模对应的搜索空间大小情况：

dj38 has 38 cities with a search space of 10^43.
europe40 has 40 cities with a search space of 10^46.
st70 has 70 cities with a search space of 10^98.
pcb442 has 442 cities with a search space of 10^976.
lu980 has 980 cities with a search space of 10^2504.

TSP问题的波动性如下图所示：如何使用Optaplanner解决旅行商问题（TSP）？在上图的三个案例中，我们可以看到，当增加一个新位置时，最优解会发生多大的变化是不同的。从左到右，随着数据集规模的增大，新位置对最优解的影响也会逐渐增强。尤其是在最右侧的案例中，可以清楚地看到其影响几乎是呈现出雪球效应的趋势。

如何在OptaPlanner中建模TSP

虽然官方网站对于这个案例的介绍并不详尽，只有零星的部分会提到TSP相关的内容，但是我们可以通过研究官方提供的源代码来更深入地了解该案例。本文将以此为基础，探讨TSP在该案例中的应用。

模型设计

我们通过分析源代码得到了TSP模型的类图设计，如下所示：如何使用Optaplanner解决旅行商问题（TSP）？通过对类图的分析，我们可以更好地理解TSP模型的结构和关系。

Solution

TspSolution是用于求解旅行商问题（TSP）的求解类。

ProblemFact

TSP问题中，Location和Domicile是极其重要的ProblemFact（问题事实类）。其中，"Domicile"指的是旅行商的住所，而"Location"则指提供经纬度及距离等信息的位置对象。值得注意的是，"Location"作为"Domicile"的属性存在。

PlaninngEntity

Visit（访问）作为PlanningEntity（规划实体类），Standstill previousStandstill 作为PlanningVariable（规划变量）

核心点

特别需要关注以下两个核心点：

规划变量Standstill增加了注解@PlanningVariableGraphType.CHAINED，表示变量Standstill为“链式变量”（链式变量将在后续文章中详细介绍）。
规划变量Visit和Domicile均实现了Standstill接口。在TSPSolution中，规划变量的类型为StandStill接口，并且在Domicile domicile和List visitList的get方法上，存在@ValueRangeProvider注解，该注解提供了求解器用于规划变量值的获取。因此，previousStandstill的值可能是起始点Domicile居住所，也可能是上一个拜访的地方Visit。
PlanningEntity Visit本身也作为了规划变量Standstill的值提供者

这两个核心点是Optaplanner里“链式变量”的要求。

链式变量基本概念

在这里，我们先简单了解链式变量，详细的内容将在后续学习中讲解。链式规划变量允许规划实体（planning entities）相互指向并形成链。通过将问题建模为一组链（而不是一组树/循环），搜索空间被大大减少。一个链式的规划变量可以：

直接指向一个问题事实（problem fact）或规划实体（planning Entity)，这被称为锚点（anchor）。
指向具有相同规划变量的另一个规划实体，该实体递归地指向一个锚点。

如何使用Optaplanner解决旅行商问题（TSP）？这张图的内容我们会在后续进行解释，目前可以先了解在TSP中锚点（Anchor）指的是Domicile（起始点住所）。

约束设计

虽然TSP的约束设计相对简单，但其中存在一个小技巧点。由于“链式变量”的要求是组成一组链，而非循环结构，因此尾部Visit规划实体的下一个位置不能指向Domicile，这一点需要特别注意。

private Constraint distanceToPreviousStandstill(ConstraintFactory constraintFactory) {
    return constraintFactory.forEach(Visit.class)
    .penalizeLong(SimpleLongScore.ONE, Visit::getDistanceFromPreviousStandstill)
    .asConstraint("Distance to previous standstill");
}

private Constraint distanceFromLastVisitToDomicile(ConstraintFactory constraintFactory) {
    return constraintFactory.forEach(Visit.class)
        .ifNotExists(Visit.class,
                     Joiners.equal(visit -> visit, Visit::getPreviousStandstill))
        .join(Domicile.class)
        .penalizeLong(SimpleLongScore.ONE,
                      Visit::getDistanceTo)
        .asConstraint("Distance from last visit to domicile");
}

约束distanceToPreviousStandstill的目的是计算整个链路最短路径。
约束distanceFromLastVisitToDomicile的目的，则是要计算链路尾部的Visit（即最后一个拜访的地方）到住所的距离。

运行求解

在官方的例子里找到TspApp：如何使用Optaplanner解决旅行商问题（TSP）？运行main方法后会打开Java应用程序的界面：可以导入自己的维护的数据来进行求解。

结尾

通过此次内容，我们了解了Optaplanner中TSP问题的定义、挑战、建模、约束设计以及链式变量等相关知识。这些知识对于我们了解路径优化问题以及如何使用Optaplanner来解决实际问题非常重要。在接下来的分享中，我将分享一些简单的路线规划实际应用，例如拣货等。

如果需要转载文章，必须注明原出处和作者，感谢您的理解和支持。