特殊TSP问题：每区块选一个出入口访问可否转换为普通TSP求解

转普通TSP的可行性及转换方法 #

完全可以转换为普通TSP求解，你遇到的这类问题本质是组旅行商问题（GTSP），标准转换方案如下：

• 先为每个区块B_i的所有出入口点位，分别创建独立的TSP普通节点，比如区块B_i有3个出入口，就拆为B_i_p1、B_i_p2、B_i_p33个独立节点
• 构造距离矩阵时按以下规则赋值：
  • 属于同一区块的拆分节点之间的距离设为无穷大（取值大于所有跨区块出入口距离的总和即可），强制求解器不会连续访问同一区块的两个节点，保证每个区块仅选一个出入口
  • 不同区块的拆分节点之间的距离，直接取两个对应出入口的实际通行距离
• 转换完成后传入普通TSP求解器即可，求解结果中每个区块仅会保留一个节点，就是你需要选择的出入口，节点的排列顺序就是区块的遍历顺序

Java/Kotlin 生态解决方案 #

方案1：直接用OptaPlanner（推荐，适合中大规模场景） #

OptaPlanner是JVM生态下成熟的约束求解库，原生支持Kotlin、Java，本身内置GTSP的求解能力，不需要你手动做TSP转换，直接定义两个约束即可：

1. 每个区块必须选择且仅选择一个出入口
2. 所有选中出入口的遍历总距离最小
   对于区块数在100以内的场景，求解效率非常高，还支持自定义软约束（比如高峰时段避堵、作业时长限制等），适配灵活度远高于手动转普通TSP。

方案2：用GraphHopper TSP模块（适合小规模场景） #

如果你的区块数量小于50，可以用GraphHopper的TSP模块，按上面的转换方法构造好节点和距离矩阵后直接传入求解即可，代码量极小。

方案3：手动实现动态规划（适合极小规模场景，无需引入第三方依赖） #

如果区块数量小于20，你可以直接手写动态规划求解，核心状态定义为dp[mask][lastPoint]，其中mask是用比特位表示的已访问区块集合，lastPoint是上一个选中的出入口点位，状态转移时仅允许跳转到未访问区块的出入口即可，Kotlin简单实现示例如下：

// 出入口点位定义
data class Point(val id: Int, val blockId: Int, val lng: Double, val lat: Double)

// 计算两个点位的距离，可替换为实际路网距离
fun calcDistance(p1: Point, p2: Point): Double {
    val dx = p1.lng - p2.lng
    val dy = p1.lat - p2.lat
    return Math.sqrt(dx * dx + dy * dy)
}

fun solveGTSP(points: List<Point>, blockCount: Int): Double {
    val pointCount = points.size
    val fullMask = (1 shl blockCount) - 1
    val INF = Double.MAX_VALUE / 2
    val dp = Array(1 shl blockCount) { DoubleArray(pointCount) { INF } }
    
    // 初始化：起点选任意区块的任意点位
    points.forEachIndexed { idx, p ->
        dp[1 shl p.blockId][idx] = 0.0
    }
    
    for (mask in 0 until (1 shl blockCount)) {
        for (lastIdx in 0 until pointCount) {
            if (dp[mask][lastIdx] == INF) continue
            val lastP = points[lastIdx]
            for (nextIdx in 0 until pointCount) {
                val nextP = points[nextIdx]
                if (mask and (1 shl nextP.blockId) != 0) continue // 跳过已访问的区块
                val newMask = mask or (1 shl nextP.blockId)
                val newDist = dp[mask][lastIdx] + calcDistance(lastP, nextP)
                if (newDist < dp[newMask][nextIdx]) {
                    dp[newMask][nextIdx] = newDist
                }
            }
        }
    }
    return dp[fullMask].minOrNull() ?: INF
}

内容的提问来源于stack exchange，提问作者Balage1551