【示例】应急物资配送的整数规划与路径优化

问题是什么？

选择开设哪些应急仓库。

使用什么模型？

0-1 整数规划

为什么使用这个模型？

开不开仓是离散决策，连续规划会得到“开 0.6 个仓”这种无意义结果。

核心公式是什么？

min ∑ f_i y_i + ∑ c_ij x_ij，s.t. 覆盖与容量约束

得到了什么结果？

示例中开设 3 个仓即可覆盖全部避难所。

问题是什么？

给出从仓库到需求点的配送路径。

使用什么模型？

最短路径

为什么使用这个模型？

边权明确是时间时，Dijkstra 能给出可执行路线。

核心公式是什么？

d(s) = 0，d(v) = min_u d(u)+w(u,v)

得到了什么结果？

最长配送时间下降到规定阈值以内。

问题是什么？

当点位增多时如何近似求解。

使用什么模型？

遗传算法

为什么使用这个模型？

精确求解随点数指数增长，启发式能在时限内给出近优方案。

核心公式是什么？

适应度 = 1 / (总时间 + 惩罚)

得到了什么结果？

多次实验后最优目标值波动小于 5%。