如何计算中继配送系统中起点与终点间最短路径上的中继点？

问题背景 #

你需要实现从指定起点到终点的最短路径规划，筛选最优中继点满足接力配送需求，已提供的点位参数如下：

可选中继点坐标 #

let coordinates = [
    [77.676247, 12.926031, "Bellandur"],
    [77.697418, 12.959172, "Marathalli"],
    [77.749947, 12.9698, "Whitefield"],
    [77.623344, 12.917654, "Silkboard signal"],
    [77.60457, 12.95029, "Lalbagh Garden"],
];

起点与终点定义 #

let origin = [77.666847, 12.926131, "Origin"];
let destination = [77.746061, 12.957973, "Destination"];

理想输出的最短路径示例：

[
    [77.666847, 12.926131, "Origin"],
    [77.676247, 12.926031, "Bellandur"],
    [77.697418, 12.959172, "Marathalli"],
    [77.749947, 12.9698, "Whitefield"],
    [77.746061, 12.957973, "Destination"]
]

路径效果参考：

实现步骤 #

1. 经纬度距离计算 #

采用Haversine公式计算地球球面两点距离，避免平面坐标计算的误差，单位可自定义为公里/米：

// 计算两个经纬度点的距离，返回单位：公里
function getDistance(lat1, lon1, lat2, lon2) {
    const R = 6371; // 地球半径，单位公里
    const dLat = (lat2 - lat1) * Math.PI / 180;
    const dLon = (lon2 - lon1) * Math.PI / 180;
    const a = 
        Math.sin(dLat/2) * Math.sin(dLat/2) +
        Math.cos(lat1 * Math.PI / 180) * Math.cos(lat2 * Math.PI / 180) * 
        Math.sin(dLon/2) * Math.sin(dLon/2); 
    const c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
    return R * c;
}

2. 筛选有效中继点 #

排除偏离起点到终点主路径的点位：计算每个可选点到起点-终点连线的垂直距离，超过设定阈值（可根据业务调整，比如2公里）的直接排除，本场景下Silkboard signal、Lalbagh Garden会被过滤。

3. 最短路径规划 #

因为点位数量少，直接用Dijkstra算法求解从起点到终点的最短路径，每个点位作为图的节点，节点间的边权值为两点的实际距离：

function planRelayRoute(origin, destination, candidates) {
    // 所有节点合并：起点 + 候选中继 + 终点
    const nodes = [origin, ...candidates, destination];
    const n = nodes.length;
    // 距离矩阵
    const dist = Array(n).fill(Infinity);
    const prev = Array(n).fill(-1);
    const visited = Array(n).fill(false);
    dist[0] = 0; // 起点距离为0

    for (let i = 0; i < n; i++) {
        // 找当前未访问的最短距离节点
        let u = -1;
        let minDist = Infinity;
        for (let j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                u = j;
            }
        }
        if (u === -1) break;
        visited[u] = true;
        // 到达终点提前退出
        if (u === n - 1) break;

        // 更新相邻节点距离
        for (let v = 0; v < n; v++) {
            if (!visited[v]) {
                const d = getDistance(nodes[u][1], nodes[u][0], nodes[v][1], nodes[v][0]);
                if (dist[v] > dist[u] + d) {
                    dist[v] = dist[u] + d;
                    prev[v] = u;
                }
            }
        }
    }

    // 回溯路径
    const path = [];
    let cur = n - 1;
    while (cur !== -1) {
        path.unshift(nodes[cur]);
        cur = prev[cur];
    }
    return path;
}

4. 业务优化（可选） #

如果是实际生产环境使用，可以额外增加以下限制：

• 单段配送距离上限，避免单个配送员配送距离过长
• 中继点是否有存储能力、运营时间限制
• 结合实时路况调整节点间的边权值

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