第2240篇：物流调度AI——路径规划和实时动态调度的工程实现
2026/4/30大约 8 分钟
第2240篇：物流调度AI——路径规划和实时动态调度的工程实现
适读人群：物流技术工程师、Java后端开发者、配送系统架构师 | 阅读时长：约17分钟 | 核心价值：从VRP问题的本质出发，实现一套支持实时动态调整的物流调度系统，覆盖路径规划算法选型和工程落地全流程
做物流调度系统之前，我一直以为这是个纯算法问题——把VRP（车辆路径规划问题）解好就行了。直到真正接手一个城市配送平台的调度系统改造项目，才发现现实中的物流调度要复杂得多。
客户下单时间是随机的，骑手位置在变，路上会堵车，商家出餐时间飘忽不定，偶尔还有骑手突然离线。理论上最优的静态路径方案，在动态的现实世界里可能跑着跑着就"最优"不了了。
这个项目最大的挑战不是算法，是如何在几秒钟内做出"足够好"的决策，而不是在几分钟内做出"最优"的决策。
调度问题的工程定义
在动手写代码之前，先把问题定义清楚。我们面对的是一个动态多约束VRP（DVRP）：
- 新订单实时到达，需要分配给骑手
- 骑手容量有限（最多同时携带N单）
- 每单有时间窗约束（必须在X分钟内送达）
- 骑手当前有在途订单，新订单需要插入现有路径
- 路况实时变化，旅行时间不确定
算法选型：不同场景用不同算法
对于VRP问题，没有一个算法在所有场景下都是最好的：
| 算法 | 适用场景 | 优点 | 缺点 |
|---|---|---|---|
| 贪心算法 | 实时单量插入 | 极快（ms级） | 解质量差 |
| 模拟退火 | 中等规模批量优化 | 解质量好 | 参数敏感 |
| 遗传算法 | 大规模离线规划 | 全局搜索 | 慢，不适合实时 |
| LKH3（LK启发式） | 高质量离线TSP | 接近最优解 | 只能离线 |
| 强化学习（PPO/DQN） | 动态实时调度 | 学习复杂策略 | 训练成本高 |
我们的架构是：实时层用贪心+局部优化，批量层用模拟退火，周期性全局重优化。
核心数据模型
// 骑手状态
@Data
public class Rider {
private String riderId;
private String name;
private GeoPoint currentLocation;
private RiderStatus status; // IDLE/BUSY/OFFLINE
private int maxCapacity; // 最大携带单数
private List<Task> pendingTasks; // 当前在途任务（已分配未完成）
private Instant lastUpdateTime;
// 可用容量
public int getAvailableCapacity() {
return maxCapacity - pendingTasks.size();
}
// 估算完成当前任务的时间（用于插单时的窗口判断）
public Instant estimatedFreeTime(TravelTimeEstimator estimator) {
if (pendingTasks.isEmpty()) return Instant.now();
// 按当前路径，计算最后一单完成时间
return estimator.estimateRouteCompletionTime(currentLocation, pendingTasks);
}
}
// 配送任务
@Data
@Builder
public class Task {
private String taskId;
private String orderId;
private GeoPoint pickupLocation; // 取货点（商家）
private GeoPoint deliveryLocation; // 送货点（客户）
private TaskType type; // PICKUP / DELIVERY
private Instant expectedPickupTime; // 预计取货时间（商家出餐时间）
private Instant deadlineTime; // 必须完成时间
private TaskStatus status;
private String assignedRiderId;
}
// 路径规划结果
@Data
@Builder
public class DispatchPlan {
private String riderId;
private List<Task> orderedTasks; // 按执行顺序排列的任务列表
private double totalDistance;
private Duration totalTime;
private Map<String, Instant> estimatedArrivalTimes; // 每个任务点的预计到达时间
private double planScore; // 方案质量分数
}实时调度引擎：新订单的即时分配
新订单到达时，需要在秒级内完成分配：
@Service
public class RealTimeDispatchEngine {
@Autowired
private RiderRepository riderRepo;
@Autowired
private TravelTimeEstimator travelTimeEstimator;
@Autowired
private RouteOptimizer routeOptimizer;
// 分布式锁，防止同一骑手被并发分配
@Autowired
private RedissonClient redisson;
/**
* 新订单到达时的实时分配
* 目标：在3秒内完成分配
*/
public DispatchResult dispatch(Order order) {
long start = System.currentTimeMillis();
Task pickupTask = createPickupTask(order);
Task deliveryTask = createDeliveryTask(order);
// 1. 获取候选骑手（附近N公里内，有空余容量）
List<Rider> candidates = riderRepo.findAvailableRidersNearby(
order.getPickupLocation(),
3.0, // 3km范围
2 // 至少还有2个容量空位
);
if (candidates.isEmpty()) {
log.warn("订单{}附近无可用骑手", order.getOrderId());
return DispatchResult.noRiderAvailable(order.getOrderId());
}
// 2. 对每个候选骑手，计算插单后的方案质量
List<InsertionOption> options = candidates.parallelStream()
.map(rider -> evaluateInsertion(rider, pickupTask, deliveryTask))
.filter(Objects::nonNull)
.sorted(Comparator.comparingDouble(InsertionOption::getCost))
.collect(Collectors.toList());
if (options.isEmpty()) {
return DispatchResult.noFeasibleOption(order.getOrderId());
}
// 3. 选择最优方案，使用分布式锁执行分配
for (InsertionOption option : options) {
RLock lock = redisson.getLock("rider:" + option.getRiderId());
try {
if (lock.tryLock(100, 500, TimeUnit.MILLISECONDS)) {
// 再次验证骑手状态（防止并发修改）
Rider rider = riderRepo.findById(option.getRiderId())
.orElse(null);
if (rider == null || rider.getAvailableCapacity() < 2) continue;
// 执行分配
executeAssignment(rider, pickupTask, deliveryTask, option.getNewRoute());
long elapsed = System.currentTimeMillis() - start;
log.info("订单{}分配成功, 骑手{}, 耗时{}ms",
order.getOrderId(), option.getRiderId(), elapsed);
return DispatchResult.success(order.getOrderId(), option.getRiderId());
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
} finally {
if (lock.isHeldByCurrentThread()) lock.unlock();
}
}
return DispatchResult.lockContention(order.getOrderId());
}
/**
* 评估将新订单插入骑手现有路径的代价
* 插入代价 = 新路径时间 - 原路径时间
*/
private InsertionOption evaluateInsertion(Rider rider, Task pickup, Task delivery) {
List<Task> currentTasks = new ArrayList<>(rider.getPendingTasks());
// 遍历所有可能的插入位置
double bestCost = Double.MAX_VALUE;
List<Task> bestRoute = null;
// pickup必须在delivery之前
for (int i = 0; i <= currentTasks.size(); i++) {
for (int j = i; j <= currentTasks.size(); j++) {
List<Task> candidate = new ArrayList<>(currentTasks);
candidate.add(i, pickup);
candidate.add(j + 1, delivery);
// 检查时间窗可行性
if (!isTimeWindowFeasible(rider, candidate)) continue;
// 计算路径代价
double cost = calculateRouteCost(rider.getCurrentLocation(), candidate);
if (cost < bestCost) {
bestCost = cost;
bestRoute = candidate;
}
}
}
if (bestRoute == null) return null;
return InsertionOption.builder()
.riderId(rider.getRiderId())
.newRoute(bestRoute)
.cost(bestCost)
.build();
}
/**
* 检查路径是否满足所有时间窗约束
*/
private boolean isTimeWindowFeasible(Rider rider, List<Task> tasks) {
GeoPoint currentPos = rider.getCurrentLocation();
Instant currentTime = Instant.now();
for (Task task : tasks) {
GeoPoint destination = task.getType() == TaskType.PICKUP
? task.getPickupLocation() : task.getDeliveryLocation();
Duration travelTime = travelTimeEstimator.estimate(currentPos, destination);
Instant arrivalTime = currentTime.plus(travelTime);
// 等待时间（如果到达早于商家出餐时间）
if (task.getType() == TaskType.PICKUP &&
task.getExpectedPickupTime() != null &&
arrivalTime.isBefore(task.getExpectedPickupTime())) {
arrivalTime = task.getExpectedPickupTime();
}
// 超过截止时间则不可行
if (task.getDeadlineTime() != null &&
arrivalTime.isAfter(task.getDeadlineTime())) {
return false;
}
currentPos = destination;
currentTime = arrivalTime.plusSeconds(60); // 每个任务点操作时间1分钟
}
return true;
}
}批量优化：周期性全局重规划
每隔5分钟，对所有在途任务做一次全局重优化，利用最新的路况数据：
@Service
public class BatchOptimizationService {
@Autowired
private RiderRepository riderRepo;
@Scheduled(fixedDelay = 300000) // 每5分钟执行一次
public void globalReoptimization() {
log.info("开始全局路径重优化");
List<Rider> activeRiders = riderRepo.findByStatus(RiderStatus.BUSY);
// 对每个骑手，用模拟退火优化当前路径
activeRiders.parallelStream().forEach(rider -> {
if (rider.getPendingTasks().size() > 2) {
optimizeRiderRoute(rider);
}
});
}
/**
* 模拟退火优化单骑手路径
*/
private void optimizeRiderRoute(Rider rider) {
List<Task> tasks = new ArrayList<>(rider.getPendingTasks());
// 固定约束：已在取货点等待的PICKUP任务不能移动
List<Task> fixedTasks = tasks.stream()
.filter(t -> t.getStatus() == TaskStatus.WAITING_PICKUP)
.collect(Collectors.toList());
List<Task> movableTasks = tasks.stream()
.filter(t -> !fixedTasks.contains(t))
.collect(Collectors.toList());
if (movableTasks.size() <= 1) return; // 无法优化
// 模拟退火
double temperature = 100.0;
double coolingRate = 0.995;
double minTemperature = 0.1;
List<Task> currentSolution = new ArrayList<>(movableTasks);
double currentCost = calculateTotalCost(rider, fixedTasks, currentSolution);
List<Task> bestSolution = new ArrayList<>(currentSolution);
double bestCost = currentCost;
while (temperature > minTemperature) {
// 随机交换两个可移动任务的顺序
List<Task> neighbor = new ArrayList<>(currentSolution);
int i = ThreadLocalRandom.current().nextInt(neighbor.size());
int j = ThreadLocalRandom.current().nextInt(neighbor.size());
Collections.swap(neighbor, i, j);
// 检查约束（pickup必须在对应delivery之前）
if (!isPrecedenceValid(neighbor)) continue;
double neighborCost = calculateTotalCost(rider, fixedTasks, neighbor);
double delta = neighborCost - currentCost;
// 接受更好的解，或以一定概率接受更差的解
if (delta < 0 || Math.random() < Math.exp(-delta / temperature)) {
currentSolution = neighbor;
currentCost = neighborCost;
if (currentCost < bestCost) {
bestSolution = new ArrayList<>(currentSolution);
bestCost = currentCost;
}
}
temperature *= coolingRate;
}
// 如果优化后有明显改善，更新骑手路径
if (bestCost < calculateTotalCost(rider, fixedTasks, movableTasks) * 0.95) {
List<Task> newRoute = new ArrayList<>(fixedTasks);
newRoute.addAll(bestSolution);
updateRiderRoute(rider, newRoute);
log.info("骑手{}路径优化，成本降低{:.1f}%",
rider.getRiderId(),
(1 - bestCost / currentCost) * 100);
}
}
}旅行时间预测：超越简单距离计算
物流调度中，路程时间的准确预测比路径优化算法更重要。用历史数据学习不同时段、不同路段的旅行时间：
@Service
public class TravelTimeEstimator {
@Autowired
private TravelTimeModelClient modelClient; // 调用Python训练的模型
/**
* 预测两点间的旅行时间
* 考虑：时段、星期几、实时路况
*/
public Duration estimate(GeoPoint from, GeoPoint to) {
LocalDateTime now = LocalDateTime.now();
TravelTimePredictionRequest request = TravelTimePredictionRequest.builder()
.fromLat(from.getLat())
.fromLng(from.getLng())
.toLat(to.getLat())
.toLng(to.getLng())
.hourOfDay(now.getHour())
.dayOfWeek(now.getDayOfWeek().getValue())
.isRushHour(isRushHour(now.getHour()))
.straightLineDistance(GeoUtils.haversineDistance(from, to))
.build();
TravelTimePredictionResponse response = modelClient.predict(request);
return Duration.ofSeconds((long) response.getPredictedSeconds());
}
private boolean isRushHour(int hour) {
return (hour >= 7 && hour <= 9) || (hour >= 17 && hour <= 19);
}
}实际效果与踩坑记录
这套系统上线后的数据：
- 平均配送时长从42分钟降到35分钟，下降17%
- 骑手单均里程下降12%，油费/电费节省明显
- 超时率从8%降到3.5%
踩的几个坑：
坑1：骑手位置数据精度问题。App上报的GPS坐标有漂移，地下停车场、高楼密集区尤其严重。调度决策基于错误位置，分配了很远的骑手，而附近的骑手却没被选到。解决方法：引入卡尔曼滤波对骑手轨迹做平滑，并设置位置更新间隔和异常跳变过滤。
坑2：商家出餐时间预测误差大。模型预测出餐时间30分钟，实际可能50分钟，骑手到了干等着，后续任务全部超时。这个问题我们是通过给商家设置"历史准时率"标签，对不靠谱商家预留更大缓冲时间来缓解的。
坑3：骑手抵制系统分配。部分骑手觉得系统分配的单"不公平"，私下拒单。这是人机协作的问题，不是纯技术问题，最终通过透明化调度逻辑和增加骑手申诉机制解决。