基于Java解决容量设施选址问题【100011779】

# 1.问题陈述 有容量限制的设施地址问题：假设有 n 个设施和 m 个顾客，我们可以作以下操作： ① 开启设施 ② 分配顾客到某设施 上述两个操作都有各自的成本，我们希望总成本最低，且分配到某设施的总需求不能超过其容量。 # 2.建立模型 为了方便问题的解决，我们首先建立模型，更具体地说，我们为设施、顾客创建一个具有相应属性的类。 我们以一个实例来更好地了解如何构建一个类：  由上图可知，设施有容量、开启费用、是否开启、服务某个顾客的费用四个属性；顾客有需求、被哪个设施服务两个属性，为了区分每个设施和顾客，我们用 ID 区分他们，由此建立 Facility，Customer 两个类：   # 3.读取文件及展示 在解决问题前，我们需要得到数据，以方便测试。一个样例的数据格式和第二部分的第一张图一样，输出结果的格式如下图：  我们为样例也构造一个类，格式如下：  我们用 List 保存每个顾客、每个设施、每个实例，以及记录他们的数量：  建立好数据结构后，我们编写读取文件和初始化每个对象的代码：  再编写用于展示的代码：   编写用于生成实例的代码：  # 4.问题思路及算法 ## 4.1 贪心算法 比较简单的解决办法是贪心算法，虽然不能够得到最优解，但它的思路最直接、最简单，实现起来简单，且时间复杂度不算高，下面说下贪心算法在该问题下的运用。 N 个用户，编号为 1-N，首先编号 1 选择服务费用最低的且容量足够的设施，编号 2 一样，只不过在 1 选择之后选择，以此类推，这并没有考虑到设施的开启费用，这是因为顾客的数量一般比设施多，所以如果设施开启的费用相对服务顾客的费用比较低的话，设施开启的费用是个次要矛盾，因为服务费用占的比例会大很多，当然，如果这个前提不成立的话，贪心算法的效果会差很多。 根据上面所说，我们编写代码：  具体效果在最后一同展示。 ## 4.2 模拟退火 模拟退火算法来源于固体退火原理，是一种基于概率的算法，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。 根据热力学规律并结合计算机对离散数据的处理, 我们定义: 如果当前温度为 T, 当前状态与新状态之间的能量差为 ΔE , 则发生状态转移的概率为:  伪代码如下图（来自一篇博客），还有一个比较好的例子来自另一个博客，下面代码的实现方式和这篇博客里面的应用类似：  如果得到新的状态 Y（i+1），在该问题下还不是十分清晰。换句话说，我们需要考虑如何得到邻近解，我采用的策略有两个：一是将两个顾客位置调换，即挑两个顾客出来，让一个顾客去另一个顾客的设施，另一个顾客去该顾客的设施。二是让一个顾客去另一个设施。顾客都是随机挑选的，两个策略在某个时刻时仅会执行一个。另外如果执行策略时，发现某些不合法的行为，就不会执行，直接放弃，例如某个设施容量不足。因为策略和顾客都是随机挑选的，且执行策略的次数会很大，所以放弃执行某次策略并不会影响整体效果。 综上，我们执行模拟退火的步骤如下： ① 为了方便，状态初始化为贪心算法里的结果，设定初始温度，终止温度，温度下降率。 ② 开始循环，在某个温度时（内循环），根据上述两种策略得到临近解，然后将得到的临近解和当前解进行比较，采取状态转移的步骤，由公式得到概率，决定是否向较差的情况转移。内循环结束后，将当前解与最优解比较，更新最优解。开始降温。 ③ 当温度降至终止温度时，结束循环。得到该算法下最有解。 代码如下：  # 5.运算结果 设施开启状态和顾客去了哪个设施的结果可以在————查看。 下面展示每个实例的运算时间和问题的结果（时间精度为毫秒）： | | result(SA) | Time(s) | result(Greedy) | Time(s) | | --- | ---------- | ------- | -------------- | ------- | | p1 | 8958 | 2.738 | 9440 | 0.001 | | p2 | 8010 | 2.187 | 8126 | 0 | | p3 | 9389 | 1.974 | 10126 | 0.001 | | p4 | 10714 | 1.978 | 12126 | 0 | | p5 | 9142 | 1.966 | 9375 | 0 | | p6 | 7809 | 1.985 | 8061 | 0.007 | | p7 | 9577 | 1.971 | 10061 | 0.001 | | p8 | 11173 | 1.931 | 12061 | 0 | | p9 | 8742 | 2.074 | 9040 | 0.001 | | p10 | 7617 | 2.045 | 7726 | 0.002 | | p11 | 9077 | 2.508 | 9726 | 0.002 | | p12 | 10132 | 2.066 | 11726 | 0 | | p13 | 8492 | 2.418 | 12032 | 0 | | p14 | 7526 | 2.391 | 9180 | 0.002 | | p15 | 8937 | 2.512 | 13180 | 0 | | p16 | 10764 | 2.458 | 17180 | 0.001 | | p17 | 8378 | 2.335 | 12032 | 0.002 | | p18 | 7152 | 2.351 | 9180 | 0.002 | | p19 | 9042 | 2.406 | 13180 | 0 | | p20 | 11071 | 2.417 | 17180 | 0 | | p21 | 8667 | 2.427 | 12032 | 0 | | p22 | 7194 | 2.402 | 9180 | 0.001 | | p23 | 8746 | 2.434 | 13180 | 0 | | p24 | 11483 | 2.394 | 17180 | 0 | | p25 | 13191 | 5.039 | 19197 | 0.002 | | p26 | 11022 | 4.95 | 16131 | 0.002 | | p27 | 13037 | 4.919 | 21531 | 0.002 | | p28 | 16410 | 4.925 | 26931 | 0.002 | | p29 | 13289 | 4.96 | 19305 | 0.001 | | p30 | 12171 | 4.893 | 16239 | 0.001 | | p31 | 14228 | 4.937 | 21639 | 0.001 | | p32 | 15903 | 5.005 | 27039 | 0.001 | | p33 | 12220 | 4.973 | 19055 | 0.