运筹学经典问题（六）：设施选址问题

问题描述

设施选址问题（Facility Location Problem, FLP）也成选址-分配问题，是企业面临的一类重要问题：在哪里建造设施？建造多少？以及将哪些客户分配给哪些设施去服务？

以物流业的航空站点选址为例，如果航空站点开通的很多，客户的服务质量会变好（更多的航空件可以保障更好的时效），但是显然企业的成本会上升。反之，如果开通的航空站点太少，虽然企业成本下降了，但客户服务质量会变差。因此，该问题本质上是在做服务质量和企业成本的权衡。

数学建模

集合：
$N$：设施集合；
$M$：客户集合；

常量：
$f_j$：开通设施$j（j\in N）$的固定成本；
$c_{ij}$：客户$i$被分配给设施$j$服务的运输成本；

决策变量：
$y_j$：是否开通设施$j$，0-1变量；
$x_{ij}$：是否将客户$i$分配给设施$j$。

$$\begin{gathered} \sum _{i\in N}\sum _{j\in M}{x}_{ij}{c}_{ij}+\sum _{j\in N}{f}_j \\ s.t.\sum _{j\in N}{x}_{ij}=1,?i\in M \\ {x}_{ij}\le y_j,?i\in M,j\in N \end{gathered}$$

1. 目标函数表示：最小化「运输成本」+「建设成本」；
2. 第一个约束表示每个用户只会被分配给一个设施；
3. 第二个约束表示只有当设施$j$被开通了，才会有用户被分配个这个设施。

参考资料

1. 运筹优化常用算法、模型及案例实战：Python+Java 实现. 刘兴禄，熊望祺，臧永森，段宏达，曾文佳，陈伟坚.