出行规划算法 #02：多标签 Pareto Dijkstra

多标签 Pareto Dijkstra 为每个节点维护一组「非支配标签」（Pareto 前沿），同时优化多个目标（如时间和费用），输出所有满足"没有其他方案在所有维度都更优"的解集，是携程可拼票、OTA 多目标排序的算法基础。

相关文章：RAPTOR · 可拼票 DP · Connection Scan Algorithm

目录

为什么需要多目标优化

出行规划面临天然的多目标冲突：

用户的真实需求是："给我看所有合理方案，我自己权衡"——这正是 Pareto 前沿的价值。

单目标 Dijkstra 的局限：固定权重 w×time + (1-w)×cost 只能找到单条"最优"路径，无法输出完整的权衡空间。

Pareto 支配关系

定义

标签 A = (c₁, t₁) 支配 标签 B = (c₂, t₂)，当且仅当：

c₁ ≤ c₂  且  t₁ ≤ t₂  且  (c₁ < c₂  或  t₁ < t₂)

即 A 在所有维度上不比 B 差，且至少一个维度严格更好。

Pareto 前沿（非支配解集）

方案          费用    时间    被支配？
直飞          ¥300    3.5h   ❌ 不被支配（时间最短）
高铁 G1       ¥450    2.0h   ❌ 不被支配（时间极短，费用居中）
高铁 G7       ¥600    1.5h   ❌ 不被支配（时间最短）
拼票方案      ¥180    6.0h   ❌ 不被支配（费用最低）
次优方案      ¥520    2.8h   ✅ 被 G1(¥450,2.0h) 支配 → 剪除

被支配的方案对任何理性用户都不会是最优选择，可安全从结果中剔除。

多标签 Dijkstra 算法

数据结构

每个节点 v 维护一个标签集 L[v]，集合中的每个标签 (cost, time, path) 代表一条到 v 的非支配路径：

// 每个节点的标签集
Map<Integer, List<Label>> labels = new HashMap<>();

record Label(double cost, double time, int prevNode, Label prevLabel)
    implements Comparable<Label> {
    // 按 cost 主排序（优先队列用）
    public int compareTo(Label o) { return Double.compare(this.cost, o.cost); }
}

核心操作：插入新标签（支配检查）

/**
 * 尝试将 newLabel 加入节点 v 的标签集。
 * 若 newLabel 被现有标签支配 → 拒绝。
 * 否则 → 加入，并删除被 newLabel 支配的旧标签。
 * 返回是否真正插入（用于决定是否继续松弛）。
 */
boolean tryInsert(int v, Label newLabel) {
    List<Label> ls = labels.computeIfAbsent(v, k -> new ArrayList<>());

    // 检查是否被现有标签支配
    for (Label existing : ls) {
        if (dominates(existing, newLabel)) return false;
    }

    // 删除被 newLabel 支配的旧标签
    ls.removeIf(existing -> dominates(newLabel, existing));
    ls.add(newLabel);
    return true;
}

boolean dominates(Label a, Label b) {
    return a.cost <= b.cost && a.time <= b.time
        && (a.cost < b.cost || a.time < b.time);
}

主循环

PriorityQueue<Label> pq = new PriorityQueue<>();
pq.offer(new Label(0, 0, source, null));

while (!pq.isEmpty()) {
    Label cur = pq.poll();
    int u = cur.prevNode;  // 当前节点

    // 如果 cur 已被支配，跳过（lazy deletion）
    if (isDominated(u, cur)) continue;

    if (u == target) continue;  // 可继续找更多 Pareto 解，不立即终止

    for (Edge e : graph.get(u)) {
        Label next = new Label(
            cur.cost + e.cost,
            cur.time + e.time,
            e.to, cur
        );
        if (tryInsert(e.to, next)) {
            pq.offer(next);
        }
    }
}

// 目标节点的标签集即为 Pareto 前沿
return labels.get(target);

Java 实现

import java.util.*;

public class ParetoRouter {

    record Edge(int to, double cost, double time) {}
    record Label(double cost, double time, int node, Label parent)
        implements Comparable<Label> {
        public int compareTo(Label o) { return Double.compare(cost, o.cost); }
    }

    private final List<List<Edge>> graph;

    public ParetoRouter(int n) {
        graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    }

    public void addEdge(int u, int v, double cost, double time) {
        graph.get(u).add(new Edge(v, cost, time));
    }

    public List<Label> query(int src, int dst) {
        int n = graph.size();
        List<List<Label>> labels = new ArrayList<>();
        for (int i = 0; i < n; i++) labels.add(new ArrayList<>());

        PriorityQueue<Label> pq = new PriorityQueue<>();
        Label start = new Label(0, 0, src, null);
        labels.get(src).add(start);
        pq.offer(start);

        while (!pq.isEmpty()) {
            Label cur = pq.poll();
            // lazy deletion：若已被支配则跳过
            if (isDominated(labels.get(cur.node), cur)) continue;

            for (Edge e : graph.get(cur.node)) {
                Label next = new Label(cur.cost + e.cost, cur.time + e.time, e.to, cur);
                if (tryInsert(labels.get(e.to), next)) {
                    pq.offer(next);
                }
            }
        }
        return labels.get(dst);
    }

    private boolean tryInsert(List<Label> ls, Label newL) {
        for (Label l : ls) if (dominates(l, newL)) return false;
        ls.removeIf(l -> dominates(newL, l));
        ls.add(newL);
        return true;
    }

    private boolean isDominated(List<Label> ls, Label l) {
        return ls.stream().anyMatch(x -> dominates(x, l) && x != l);
    }

    private boolean dominates(Label a, Label b) {
        return a.cost <= b.cost && a.time <= b.time
            && (a.cost < b.cost || a.time < b.time);
    }
}

标签集大小分析

实践中通常给标签集设上限（如 50），超过时按支配性剪枝，保留最有价值的解。

扩展到三个目标

加入「换乘次数」作为第三维：

record Label(double cost, double time, int transfers, int node, Label parent) {}

boolean dominates(Label a, Label b) {
    return a.cost <= b.cost && a.time <= b.time && a.transfers <= b.transfers
        && (a.cost < b.cost || a.time < b.time || a.transfers < b.transfers);
}

三维 Pareto 前沿更大，但剪枝效果依然显著——大多数用户不会接受换乘 4 次的方案，可预先过滤。

实际应用

携程可拼票

携程的「拼票」功能（A→C + C→B 两张单独机票）本质上是在以价格和时间为两个目标的图上运行 Pareto Dijkstra：

• 节点：城市 + 时间窗口
• 边权：票价 + 飞行时间
• 约束：中转时间 ≥ 最短换乘时间（通常 60～90 分钟）

去哪儿 / 飞猪

OTA 的"智能排序"并非单纯最低价，而是展示 Pareto 前沿上的几个代表性方案（极速到达、最低价格、综合推荐），由用户在 UI 上拖动滑块权衡。

OpenTripPlanner

OTP 的多模式规划（公交+自行车+步行）使用三维 Pareto 优化（到达时间、步行距离、换乘次数）。

参考资料

参考资料

• Hansen, Bicriterion Path Problems (1980) — 多标签 Dijkstra 奠基论文
• RAPTOR（RAPTOR 的多目标扩展 McRAPTOR 也使用 Pareto 标签集）
• 可拼票 DP（携程具体应用：带约束的 Pareto 最短路）