出行规划算法 #03：可拼票 DP

可拼票 DP 将「A→B 直达票」与「A→C + C→B 两段票」的组合搜索建模为带时间约束的最短路 DP，通过枚举中转城市并剪枝，找出比直达更便宜的合法组合，是携程「拼票」功能的核心算法。

相关文章：RAPTOR · 多标签 Pareto Dijkstra

目录

问题定义

输入：

• 出发地 A、目的地 B、出发日期 D
• 可用中转城市集合 C = {C₁, C₂, ... Cₙ}（通常为全国有机场/高铁站的城市）
• 每对城市的最低票价矩阵 price[x][y][d]（x→y 在日期 d 附近的最低价）

约束：

1. 中转时间 ≥ MIN_TRANSIT（国内机场 60min，国际 90min）
2. 中转时间 ≤ MAX_TRANSIT（避免过夜中转，通常 ≤ 6h）
3. 总出行时间 ≤ THRESHOLD（通常 ≤ 直达时间 × 2）

目标：找出所有满足约束且总价 < 直达价格的组合，按价格排序展示。

DP 状态设计

两段拼票

dp[C] = 经城市 C 中转的最低总价

dp[C] = price[A][C][D₁] + price[C][B][D₂]

其中：
  D₁ = 出发日期（A→C 段）
  D₂ = 由 A→C 的最早落地时间 + MIN_TRANSIT 决定（C→B 段出发日期）

状态转移：

best = price_direct(A, B, D)         # 直达基准价
results = []

for C in all_cities:
    # 枚举 A→C 的所有班次
    for flight_AC in flights(A, C, D):
        earliest_depart_CB = flight_AC.arrival + MIN_TRANSIT
        latest_depart_CB   = flight_AC.arrival + MAX_TRANSIT

        # 找 C→B 在时间窗口内的最低价班次
        flight_CB = cheapest_flight(C, B,
                                    earliest_depart_CB,
                                    latest_depart_CB)
        if flight_CB is None:
            continue

        total = flight_AC.price + flight_CB.price
        if total < best:                         # 比直达便宜
            results.append((total, flight_AC, flight_CB))

results.sort()

剪枝策略

暴力枚举所有中转城市 × 所有班次组合的复杂度 O(N × F²)（N=城市数，F=班次数），需要多层剪枝：

地理剪枝

中转城市不能是"绕路"的——若 A 在北京、B 在上海，中转城市 C 应在 A-B 连线的合理地理范围内：

def is_geographic_valid(A, C, B):
    # 直线距离之和不超过直达距离的 K 倍（通常 K=1.5）
    return dist(A, C) + dist(C, B) <= dist(A, B) * 1.5

价格剪枝

若 A→C 的价格已超过直达价格，无论 C→B 多便宜都不可能更优：

if price_AC > price_direct * 0.9:   # 留 10% 安全边际
    continue

时间窗口剪枝

只查询 D-1 到 D+1 的班次，避免跨日中转。

中转城市预筛选

预计算每对城市的「历史最低价」，若 min_price[A][C] + min_price[C][B] ≥ price_direct 则整个城市 C 可跳过。

Java 实现

import java.util.*;
import java.time.*;

public class CombinedTicketDP {

    static final Duration MIN_TRANSIT = Duration.ofMinutes(60);
    static final Duration MAX_TRANSIT = Duration.ofHours(6);

    record Flight(String from, String to, LocalDateTime departure,
                  LocalDateTime arrival, double price) {}

    record CombinedTicket(Flight leg1, Flight leg2) {
        double totalPrice() { return leg1.price + leg2.price; }
        Duration transitTime() {
            return Duration.between(leg1.arrival, leg2.departure);
        }
    }

    /**
     * 搜索 A→B 的所有合法拼票组合（比 directPrice 更便宜）
     */
    public List<CombinedTicket> search(
            String origin, String dest, LocalDate date,
            double directPrice,
            FlightIndex index) {

        List<CombinedTicket> results = new ArrayList<>();

        for (String via : index.getAllCities()) {
            if (via.equals(origin) || via.equals(dest)) continue;

            // 地理剪枝
            if (!geographicFilter(origin, via, dest)) continue;

            // 获取 origin→via 的班次
            for (Flight leg1 : index.getFlights(origin, via, date)) {
                // 价格剪枝
                if (leg1.price >= directPrice * 0.9) continue;

                // 计算合法换乘时间窗口
                LocalDateTime earliest = leg1.arrival.plus(MIN_TRANSIT);
                LocalDateTime latest   = leg1.arrival.plus(MAX_TRANSIT);

                // 找 via→dest 在窗口内的最低价班次
                Flight leg2 = index.cheapestFlight(via, dest, earliest, latest);
                if (leg2 == null) continue;

                double total = leg1.price + leg2.price;
                if (total < directPrice) {
                    results.add(new CombinedTicket(leg1, leg2));
                }
            }
        }

        results.sort(Comparator.comparingDouble(CombinedTicket::totalPrice));
        return results;
    }

    private boolean geographicFilter(String a, String via, String b) {
        double dAV = haversine(a, via);
        double dVB = haversine(via, b);
        double dAB = haversine(a, b);
        return (dAV + dVB) <= dAB * 1.5;
    }

    // haversine 计算两城市直线距离（省略实现）
    private double haversine(String city1, String city2) { return 0; }
}

多段拼票扩展

三段拼票（A→C₁→C₂→B）组合数爆炸：

两段：N 个中转城市 → O(N) 枚举
三段：O(N²) 枚举，N=300 时已达 90,000 组合

工程解法：

1. 限制段数：携程最多拼 2 段（三段票），超过用户接受度低
2. 并行搜索：每个中转城市独立查询，天然并行
3. 缓存价格矩阵：预缓存 min_price[city1][city2][date]，避免实时调 GDS

工程挑战

实时价格与库存

拼票展示的是「低价估算」，用户下单时需要：

1. 分别锁定 A→C 和 C→B 的座位（两次独立预订）
2. 两段都成功才算拼票完成，否则需要回滚

风险：锁座之间存在时间窗口，可能出现"一段成功一段失败"的部分预订状态。携程的解法是先支付全款到托管账户，再异步完成两段预订，失败自动退款。

时区与夜间中转

国际拼票需处理时区转换。夜间中转（如落地 23:00，次日 06:00 出发）是否合法取决于是否有过夜酒店补贴政策。

参考资料

参考资料

• 多标签 Pareto Dijkstra（拼票 DP 的多目标扩展：同时优化价格和时间）
• RAPTOR（适用于有时刻表的公共交通路由，拼票 DP 的火车场景变体）