物资调配建模实战：从台风“白海豚“逼近华东看运输问题与指派问题

# 物资调配建模实战从台风白海豚逼近华东看运输问题与指派问题8月8日今年第13号台风白海豚强台风级、曾达14级正在逼近华东预计8月9日下午至10日早晨以台风级或强台风级登陆浙江到福建一带沿海登陆后可能先西行再转向偏北浙江已启动应急响应上海、江苏、福建、安徽等地有强降雨需做好灾害防御央视网/中新网8月8日。中央气象台专家同时提醒台风登陆点和后期路径仍有不确定性西风槽、副热带高压、南亚高压的位置形态对路径起决定性作用。台风登陆前后最怕的是什么不是风大而是**该到的物资没到位**——帐篷、饮用水、发电机、方便食品一样都不能缺。物资从哪调、往哪送、谁去送、送多少这就是今天要讲的运输问题与指派问题也是国赛物流调度类赛题的核心骨架。## 一、台风还没登陆物资先要抢跑8月7日国家防灾减灾救灾委员会办公室、应急管理部会同多部门会商研判8月可能有2-3个台风登陆或影响我国松辽、海河、珠江流域汛情较重。台风白海豚登陆窗口就在8月9日下午至10日早晨留给各地的准备时间只有一两天。这个窗口期里物资调配必须抢跑省级储备库的物资要前置到可能受灾的市县市县的物资要提前装车运输力量要提前待命。这种场景下的调配问题跟平时做生意完全不同需求是**急的**几十小时内必须到位、路况是**动态的**台风登陆后道路可能中断、供给是**有限的**物资就那么多谁先谁后要排优先级。所以应急物资调配建模比普通物流题多一层时效的考虑。今天咱们就从最经典的运输问题讲起一路升级到带时效约束的0-1规划。## 二、运输问题多个供应点、多个需求点怎么调运输问题是运筹学里最经典的模型之一场景一句话**有若干个供应点每个供应点有一定量的物资有若干个需求点每个需求点有一定量的缺口从每个供应点运到每个需求点都有一个单位运费问怎么调运总运费最少。**这个模型有三个关键假设要先交代清楚第一物资是同质的——一箱水就是标准的一箱水从哪个仓库出来都一样第二单位运费已知——通常是按距离×单位运价折算也可以直接给出运费表第三供需总体平衡——所有供应点加起来能供应的量不少于所有需求点的缺口总量运输问题才能有可行解。国赛里出这类题通常还会附加一些坑某个供应点和需求点之间道路中断运费设成无穷大或者需求点有个最低供货量要求达不到就判为未满足。这些坑的处理方法后面统一讲先把基本模型搭起来。## 三、指派问题船、车、直升机谁去干哪个活调运方案定了下一个问题来了**谁来运** 省里有20辆卡车、5架直升机、3艘运输船要同时执行十几个任务——往甲市送帐篷、往乙镇送发电机、往丙村送急救包。卡车便宜但慢直升机快但贵且容量小运输船容量大但依赖水路。把哪个运力派给哪个任务最划算这就是**指派问题**n个任务、n个执行者或m个执行者选n个任务每个执行者做每个任务有一个效率值时间、成本、风险求总效果最优的匹配方案。指派问题有个很讨喜的性质任务和执行者是一一对应的一个执行者只干一个任务、一个任务只由一个执行者干。现实里不完全是这样一辆卡车可以跑两趟但国赛命题人就是喜欢把这个约束考出来因为它的求解思路非常清晰。应急场景里指派问题还能加优先级救命的药品任务必须指派给最快的直升机这就是加约束的指派问题。## 四、算例3个供应点、4个需求点算给你看理论讲完来一个完整算例。假设某省有3个物资储备库甲、乙、丙要向4个受灾县A、B、C、D调配饮用水供应量与需求量如下单位万箱| 储备库 | 供应量万箱 | 受灾县 | 需求量万箱 || --- | --- | --- | --- || 甲库 | 30 | A县 | 20 || 乙库 | 25 | B县 | 15 || 丙库 | 20 | C县 | 15 || 合计 | 75 | D县 | 25 |各库到各县的单位运输成本如下元/万箱| 从\到 | A县 | B县 | C县 | D县 || --- | --- | --- | --- | --- || 甲库 | 100 | 140 | 180 | 220 || 乙库 | 160 | 120 | 200 | 240 || 丙库 | 300 | 260 | 240 | 320 |注意丙库到A县的运费300元明显偏高可能因为线路绕远而甲库到D县220元也不便宜。最优方案的原则是就近、就便宜但要兼顾供应量约束——丙库20万箱总得运出去。用手工试算或最小元素法的思路先满足单位运费最低的格子可以得到这样一套方案| 调运路线 | 数量万箱 | 单位运费元 | 小计元 || --- | --- | --- | --- || 甲库→A县 | 20 | 100 | 2000 || 甲库→B县 | 10 | 140 | 1400 || 乙库→B县 | 5 | 120 | 600 || 乙库→D县 | 20 | 240 | 4800 || 丙库→C县 | 15 | 240 | 3600 || 丙库→D县 | 5 | 320 | 1600 |合计甲库运出30、乙库运出25、丙库运出20全部供应量用完A、B、C、D四个县分别收到20、15、15、25万箱需求全部满足。总运费为14000元。这个方案比各库就近全部满足相邻县的直觉方案省了不少——因为D县需求量大把乙库往D县多送、让丙库补B县缺口的做法正好避开了丙库到A、B县的高运费。这就是运输问题的价值**用全局优化替代局部直觉。**## 五、时效约束升级最晚到达限制与0-1规划上面的算例只考虑了钱没考虑时间。可应急场景里时间比钱贵。台风9日下午登陆某村卫生站的急救包必须8日晚上之前到位晚了就误事。怎么把时间塞进模型思路是升级变量不再问从甲库往A县运多少而是问甲库往A县发不发这趟车——每个发车决策用一个取值只有0或1的变量表示这就是**0-1规划**。升级后模型长这样决策变量是是否由运力k执行任务j取1或0约束条件包括每个任务至少被执行一次、每个运力最多执行一个任务、物资量满足需求、以及**每个任务的到达时间不能晚于最晚允许时间**由运力k的速度、出发时间、路况推算目标函数可以是最小化总成本也可以是最小化最大迟到时间这叫最小化瓶颈应急里特别常用。举个直观例子D县医院断电需要一台发电机最晚8日18时到位。直升机4小时能到但只能带1台卡车要14小时但能带5台。如果不加时效约束模型肯定选卡车加了18时前必须到位的约束直升机方案立刻变成可行解。**约束一加最优解就变了**——这就是时效约束的力量也是应急调度题和普通物流题最大的区别。## 六、供需缺口与应急分级模型之外的事模型算完还有一层现实必须面对物资总量可能不够。比如全省只有60万箱饮用水需求却有75万箱缺口15万箱运输问题连可行解都没有。这时候模型要升级成最大流或带缺口的运输问题目标变成总供应量最大化或总缺水量最小化并且要给缺口排优先级——受灾最重的县、老人儿童集中的安置点优先保障。这引出应急管理里一个非常重要的概念**分级响应**。物资保障按小时级、天级、周级分级台风登陆前24小时保的是饮用水、食品、手电筒这类救命物资登陆后一周保的是帐篷、被褥、消杀用品再往后是重建物资。不同等级配不同模型小时级用最快到达模型天级用成本最优模型周级用供需平衡模型。**把模型嵌进分级响应的框架里讲论文的格局立刻不一样**——这比单纯算出一个最优解高一个档次。## 七、国赛物资调度题的通用框架把台风应急物资调配吃透国赛里凡是物流调度、资源分配、任务指派类赛题都可以套这个框架**第一步列清单。** 供应点有哪些、各有多少货需求点有哪些、各缺多少运费/时间/路况数据表全部列清楚。数据表本身就是得分点。**第二步分问题。** 调运量问题用运输问题模型任务分配问题用指派问题模型两个往往叠加出现——先定运什么再定谁来运。**第三步加约束。** 时效限制、道路中断、运力限制、最低保障量一条条加进去每加一条说明一次为什么加模型随之升级为0-1规划或混合整数规划。**第四步讨论与扩展。** 供需缺口怎么处理、优先级怎么排、模型求解后方案在现实中是否可行、灵敏度运费变动/道路恢复时间变动对方案的影响。这四步走完一份标准的国赛论文骨架就出来了。## 国赛启示回头看这周的新闻8月7日会商研判8月可能有2-3个台风登陆或影响我国8月8日白海豚就带着不确定的路径直奔华东浙江应急响应已经启动物资、车辆、直升机都在窗口期里抢跑。中央气象台专家说得明白副热带高压、西风槽这些大尺度系统一变登陆点就可能改写——**不确定性才是应急管理的常态**。建模能做的不是消除不确定性而是把不确定性下的调配方案算清楚、排好序钱怎么省、时间怎么抢、缺口怎么补。国赛里遇到调度题记住今天的骨架运输问题定调运量指派问题定任务分配时效约束升级成0-1规划供需缺口用分级响应兜底。把为什么讲透比堆十个模型更值钱。资料来源央视网/中新网8月8日台风白海豚动态、中央气象台专家访谈8月8日、应急管理部等部门8月7日会商会报道。