下午四点,一批批运输请求同时涌来:重卡要送钻井工具,皮卡要接送作业人员,有时还得把设备从一座钻井平台转到另一座。Luis Fernando Pérez Armas 回忆,他在 2015—2016 年参与委内瑞拉东部油田调度时,每月要支持约 50 项钻井作业;高峰日大约有十余辆重卡和十余辆皮卡出车。他常用纸笔和 Excel 花几个小时安排第二天路线,早晨却仍可能发现某条路线根本走不通。
难点不只是找最短路。每件货必须先取后送;车辆沿途任何时刻都不能超载;车辆还可能从前一天的不同终点出发。各站又有服务时段,晚上 8 点后原则上禁止行车。换句话说,调度员既要决定“谁去哪里”,也要同时排好取送顺序、载荷变化和到达时间。任何一处调整,都可能让整条路线失效。这正是带取送配对、容量与时间窗的车辆路径问题:任务一多,候选排列迅速膨胀,靠逐条试很难稳妥完成。供稿节选主要呈现问题现场,未披露作者最终采用的算法及量化效果。