Solutions of capacitated facility location problems

[TOC]

• Suppose there are n facilities and m customers. We wish to choose:
  • which of the n facilities to open
  • the assignment of customers to facilities
• The objective is to minimize the sum of the opening cost and the assignment cost.
• The total demand assigned to a facility must not exceed its capacity.

这个网站：http:https://www.di.unipi.it/optimize/Data/MEX.html

包含了问题的已知最优解

该解法代码文件位于src/SA.cpp中。

就是普通的模拟退火，进行了如下的一些改进，并且参数经过了多次试验性的调整；

• 邻域搜索策略：

采用5种邻域搜索策略

1. 随机将一个客户移动到另一个仓库
2. 随机改变一个仓库的状态
   • 若该仓库是打开的，那么尝试将该仓库的所有用户分配给其他仓库，然后关闭它；如果无法将所有用户都分配走，那么不恢复已被挪走的用户，也不改变该仓库的状态；
   • 若该仓库是关闭的，那么将该仓库打开，并且给这个仓库随机分配一个客户；
3. 随机选择2个客户交换仓库
4. 随机选择3个客户轮换仓库
5. 随机选择4个客户轮换仓库

以上的策略在执行后都会验证，如果被挪走客户的仓库此时没有任何一个其他客户使用，那么将其关闭。

• 额外的改进：

1. 降温开始时记录一个阈值，在多次迭代不发生改变时，将温度升高至该阈值，然后阈值减半；

2. 根据问题规模确定搜索次数（内循环次数），可以有效地处理问题规模增长后效果变差的情况。

该解法代码文件位于src/GreedyLocalSearch.cpp中。

首先写了贪心的算法，贪心的算法在src/Greedy.cpp文件可供查看；

然后写了局部搜索的算法，在src/LocalSearch.cpp文件可供查看；

单独贪心和局部搜索的结果都不是很好，想到可以将两者结合起来进行计算。首先先使用贪心法求一个初始解，然后使用局部搜索在此初始解附近迭代，试图找到最优解；

局部搜索使用的邻域搜索策略和模拟退火是相同的。

额外的改进：

1. 为了避免问题的规模增加后代码运行次数不足的情况，我增加了根据问题规模决定循环次数的代码；

   int problemSize = instance.customerNum * instance.facilityNum;
   for (int _i; _i < problemSize * 2000; _i++) {...}

2. 为了避免陷入局部最优，我增加了接受差解的代码，以期跳出局部最优；

   • 首先将接受差解的概率设置为0；
   • 在限定的循环次数内，如果有一定次数没有发现更优的解，会线性的增加接受差解的概率；
   • 由于参数的设定机制，接受差解的概率最多不会超过0.2，在实践中，通常不会超过0.01。但是取得的效果是显著的，在陷入局部最优（可能是全局最优）后会以较大的概率跳出该解，整个解检索的过程大致呈锯齿状分布；

   接受差解概率 badAcception = 0 
   FOR i FROM 0 TO (problemSize * 2000)
       {生成新解}
       IF {新解效果好} THEN
           {接收新解}
           badAcception = 0
       ELSE 
           {以概率badAcception接受差解}
           IF {不改变的次数大于 problemSize} THEN
               badAcception += 0.0001;
           END IF
       END IF
   END FOR
   

每次从客户的角度出发，贪心离他最近的工厂；

其判断到每个工厂的代价，计算为

IF facility[j] is open THEN
	cost = assignment cost
ELSE
	cost = assignment cost + opening cost
END IF

每次判断一个用户，如果该用户得到的最小代价是一个未打开的工厂的，那么就把这个工厂打开；如果是一个已打开的工厂，那么就只需要把用户指向这个工厂就好了。

考虑到随机算法效果的随机性，为了充分考量算法的效果，我对每个测例进行了三次运行，结果放在结果文件夹的allSolutions文件夹中(命名为p1(1), p1(2)…)，并挑出了其中最好的解放在optimizeSolutions文件夹中。

结果表格请查看result.md文件；

我还额外提供了一个结果矩阵的汇总的，命名为 summary。

链接如下：

总的文件夹

以下附结果表格