取送货问题

取送货问题（pickup and delivery problem）为成对的取货点和送货点安排车辆、访问顺序及行驶路线。每一件货须由同一辆车先取后送，任何时刻的车载量不能超过容量。只有把这些要求写进路线的每一段，最短路程才有实际意义。

一辆车从直线坐标零的车库出发并返回。两件货各重一吨：第一件从坐标一运到四，第二件从二运到三；距离单位为千米，行驶距离为坐标差的绝对值，不计装卸时间。记取货为 $P_1,P_2$，送货为 $D_1,D_2$。经过某点不等于在该点执行任务，访问任务才改变载重。

路线顺序与载重守恒

对一条候选任务顺序 $v_1,\dots ,v_{2n}$，令 $\Delta (P_i)=w_i$、$\Delta (D_i)=-w_i$，车辆载重满足 $$\begin{array}{cc}{L}_0& =0,L_k=L_{k-1}+\Delta (v_k),\\ 0& \le L_k\le Q,L_{2n}=0.\end{array}$$ 另须逐件检查 $P_i$ 出现在 $D_i$ 之前。仅检查总载重非负仍不够：先送尚未取到的第一件、但车上恰好有第二件时，总载重可能合法，货的身份却错了。多车时还须显式约束一对任务归属同一车辆。

容量为一吨时，取第一件后必须先送到四，才能去取第二件。因此仅有两种合法顺序： $$\begin{array}{cc}0,P_1,D_1,P_2,D_2,0& :1+3+2+1+3=10,\\ 0,P_2,D_2,P_1,D_1,0& :2+1+2+3+4=12.\end{array}$$ 十千米方案的载重变化是 $0,1,0,1,0,0$，既满足逐件先后，又满足逐段容量。

上行是一吨容量的最优任务顺序，下行是两吨容量的最优顺序。箭头的纵向错开只为显示重复经过的区段。

容量变化与最优证书

容量增为两吨后，顺序 $P_1,P_2,D_2,D_1$ 可行，载重依次为一、二、一、零，路程为 $1+1+1+1+4=8$。任何闭合路线都必须到达坐标四，再返回零；仅这两段就至少八千米，故该方案全局最优。容量改变的是可行任务顺序，不是道路长度。

一般实例可用二元弧变量、任务归属和载重变量建模；时间窗还要求到达或开始服务时间落在指定区间。若用大常数连接“选弧”与“载重变化”，该常数必须由上下界推得；任意取一个极大值会削弱松弛并恶化数值稳定性。

小实例的完整核对

以下对单车、所有货物重量为一的模型枚举全部任务排列。输入坐标字典、任务对和整数容量；输出最短路程与任务顺序。代码每条候选中保持“已取货集合”和当前载重，货物身份与容量一起检查。

Python 3

from itertools import permutations
import math

def pickup_route(position, pairs, capacity, depot="O"):
    pairs = tuple(tuple(p) for p in pairs)
    tasks = tuple(v for p in pairs for v in p)
    if type(capacity) is not int or capacity < 1:
        raise ValueError("positive integer capacity required")
    if any(len(p) != 2 for p in pairs) or len(set(tasks)) != len(tasks):
        raise ValueError("distinct paired task labels required")
    if depot in tasks or any(v not in position for v in (depot,) + tasks):
        raise ValueError("missing position or invalid depot")
    if any(not math.isfinite(position[v]) for v in (depot,) + tasks):
        raise ValueError("finite positions required")
    pickup = {p:i for i,(p,d) in enumerate(pairs)}
    delivery = {d:i for i,(p,d) in enumerate(pairs)}
    best, route = math.inf, None
    for order in permutations(tasks):
        active, load = set(), 0
        for v in order:
            if v in pickup:
                active.add(pickup[v]); load += 1
            else:
                i = delivery[v]
                if i not in active:
                    break
                active.remove(i); load -= 1
            if load > capacity:
                break
        else:
            tour = (depot,) + order + (depot,)
            distance = sum(abs(position[b] - position[a])
                           for a,b in zip(tour, tour[1:]))
            if distance < best:
                best, route = distance, tour
    return best, route

pos = {"O":0, "P1":1, "D1":4, "P2":2, "D2":3}
print(pickup_route(pos, [("P1","D1"),("P2","D2")], 1))
print(pickup_route(pos, [("P1","D1"),("P2","D2")], 2))
# (10, ('O', 'P1', 'D1', 'P2', 'D2', 'O'))
# (8, ('O', 'P1', 'P2', 'D1', 'D2', 'O'))

代码在两吨容量时可返回另一条等长路线，先到四再到三仍是八千米。每一条合法路线都对应被枚举的一个排列，而代码恰好保留满足逐件先后与容量的排列，因此取最小值确为精确解。$n$ 对任务的时间为 $O(n(2n)!)$，额外空间为 $O(n)$；这段教学代码用于核对小数据，不适合大型调度。

变式。 若第二件货也要送到坐标四，容量二时可在一、二取货后到四依次交货，总距离仍为八。若只剩第一件任务，任意容量至少一的车辆都需 $1+3+4=8$ 千米。没有任务时返回零路程的车库原地路线。