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://www.di.unipi.it/optimize/Data/MEX.html
包含了问题的已知最优解
该解法代码文件位于src/SA.cpp
中。
就是普通的模拟退火,进行了如下的一些改进,并且参数经过了多次试验性的调整;
- 邻域搜索策略:
采用5种邻域搜索策略
- 随机将一个客户移动到另一个仓库
- 随机改变一个仓库的状态
- 若该仓库是打开的,那么尝试将该仓库的所有用户分配给其他仓库,然后关闭它;如果无法将所有用户都分配走,那么不恢复已被挪走的用户,也不改变该仓库的状态;
- 若该仓库是关闭的,那么将该仓库打开,并且给这个仓库随机分配一个客户;
- 随机选择2个客户交换仓库
- 随机选择3个客户轮换仓库
- 随机选择4个客户轮换仓库
以上的策略在执行后都会验证,如果被挪走客户的仓库此时没有任何一个其他客户使用,那么将其关闭。
- 额外的改进:
-
降温开始时记录一个阈值,在多次迭代不发生改变时,将温度升高至该阈值,然后阈值减半;
-
根据问题规模确定搜索次数(内循环次数),可以有效地处理问题规模增长后效果变差的情况。
参数 | 设置 | 备注 |
---|---|---|
初温 | 初始温度 | |
降温速率 | 每轮循环后 |
|
概率接受函数 | 随机数$r$小于该值时接受差解 | |
内循环次数 | 初值根据问题规模确定,每次增加到$1.0001$倍 |
该解法代码文件位于src/GreedyLocalSearch.cpp
中。
首先写了贪心的算法,贪心的算法在src/Greedy.cpp
文件可供查看;
然后写了局部搜索的算法,在src/LocalSearch.cpp
文件可供查看;
单独贪心和局部搜索的结果都不是很好,想到可以将两者结合起来进行计算。首先先使用贪心法求一个初始解,然后使用局部搜索在此初始解附近迭代,试图找到最优解;
局部搜索使用的邻域搜索策略和模拟退火是相同的。
额外的改进:
-
为了避免问题的规模增加后代码运行次数不足的情况,我增加了根据问题规模决定循环次数的代码;
int problemSize = instance.customerNum * instance.facilityNum; for (int _i; _i < problemSize * 2000; _i++) {...}
-
为了避免陷入局部最优,我增加了接受差解的代码,以期跳出局部最优;
- 首先将接受差解的概率设置为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
参数 | 设置 | 备注 |
---|---|---|
问题规模 | customerNum * facilityNum |
问题规模为客户数量乘以工厂的数量,用来衡量该问题的计算规模 |
差解接受概率 | 0 | 初值为0,不接受差解;每n次不产生新解则将其递增0.0001 |
每次从客户的角度出发,贪心离他最近的工厂;
其判断到每个工厂的代价,计算为
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。
链接如下:
模拟退火 | 贪心+局部搜索 | |
---|---|---|
所有实验解 | 模拟退火三次实验的所有结果 | 局部搜索三次实验的所有结果 |
所有最优解 | 模拟退火每个测例的最优解 | 局部搜索每个测例的最优解 |
结果汇总 | 模拟退火每个测例具体结果的汇总 | 局部搜索每个测例具体结果的汇总 |
结果表格 | 模拟退火实验结果的表格 | 局部搜索实验结果的表格 |
以下附结果表格
SA | Times(s) | LocalSearch | Times(s) | Greedy and Local search | Times(s) | Greedy | SA Times(s) | |
---|---|---|---|---|---|---|---|---|
p1 | 8848 | 8 | 9868 | 0.585294s | 8848 | 6s | 14918 | 0s |
p2 | 7914 | 8 | 8623 | 0.526403s | 7914 | 5s | 11406 | 0.002991s |
p3 | 9314 | 8 | 9757 | 0.595167s | 9314 | 6s | 14541 | 0.003021s |
p4 | 10795 | 6 | 12042 | 0.65691s | 10859 | 7s | 25049 | 0.002989s |
p5 | 8838 | 8 | 8838 | 0.575154s | 8838 | 6s | 15589 | 0.003017s |
p6 | 7777 | 7 | 7809 | 0.564817s | 7777 | 5s | 12768 | 0.002991s |
p7 | 9488 | 7 | 9488 | 0.618392s | 9488 | 6s | 18012 | 0.003019s |
p8 | 11088 | 7 | 11359 | 0.572739s | 11088 | 6s | 20676 | 0.003002s |
p9 | 8593 | 5 | 10586 | 0.625441s | 8462 | 7s | 13301 | 0.00402s |
p10 | 7627 | 7 | 8643 | 0.555457s | 7617 | 5s | 10659 | 0.002992s |
p11 | 8938 | 7 | 10678 | 0.535911s | 8932 | 6s | 15689 | 0.002991s |
p12 | 10252 | 8 | 10306 | 1.16598s | 10138 | 7s | 22682 | 0.002992s |
p13 | 8294 | 18 | 10190 | 1.22904s | 8252 | 13s | 14387 | 0.004986s |
p14 | 7137 | 17 | 8872 | 1.30775s | 7182 | 12s | 11730 | 0.005983s |
p15 | 8862 | 17 | 11166 | 0.614491s | 8862 | 14s | 15553 | 0.005984s |
p16 | 10524 | 20 | 12317 | 1.23131s | 10612 | 17s | 22122 | 0.004986s |
p17 | 8294 | 17 | 9765 | 1.28084s | 8227 | 13s | 15579 | 0.004986s |
p18 | 7152 | 16 | 8444 | 1.21642s | 7188 | 12s | 11281 | 0.006014s |
p19 | 8907 | 16 | 9123 | 1.26939s | 8887 | 12s | 18973 | 0.004986s |
p20 | 10514 | 17 | 12255 | 1.22301s | 10513 | 13s | 23806 | 0.005984s |
p21 | 8171 | 17 | 9057 | 1.44542s | 8068 | 13s | 13948 | 0.005986s |
p22 | 7178 | 16 | 8528 | 1.16183s | 7154 | 13s | 10693 | 0.005975s |
p23 | 8774 | 14 | 9392 | 0.406867s | 8806 | 13s | 18290 | 0.005015s |
p24 | 10463 | 19 | 10533 | 0.480043s | 10327 | 14s | 23120 | 0s |
p25 | 11639 | 106 | 13296 | 7.83371s | 11639 | 77s | 22348 | 0.01312s |
p26 | 10776 | 99 | 10785 | 9.47198s | 10781 | 78s | 18171 | 0.019947s |
p27 | 12336 | 101 | 13746 | 2.91528s | 12340 | 77s | 20208 | 0.016939s |
p28 | 13736 | 105 | 15198 | 2.70071s | 13736 | 79s | 37014 | 0.019919s |
p29 | 12548 | 102 | 13024 | 8.00301s | 12450 | 153s | 26112 | 0.013106s |
p30 | 11337 | 139 | 11442 | 2.88118s | 11391 | 155s | 22143 | 0.018908s |
p31 | 13378 | 189 | 13623 | 8.53265s | 13367 | 217s | 29909 | 0.009152s |
p32 | 15376 | 182 | 16597 | 14.3991s | 15387 | 245s | 34925 | 0.016131s |
p33 | 11632 | 101 | 13142 | 8.89691s | 11706 | 76s | 20875 | 0.019945s |
p34 | 10635 | 103 | 10636 | 8.51922s | 10635 | 73s | 19025 | 0.019945s |
p35 | 12235 | 100 | 12522 | 7.89342s | 12235 | 75s | 25803 | 0.020975s |
p36 | 13835 | 99 | 15245 | 8.22599s | 13835 | 75s | 33235 | 0.018322s |
p37 | 11326 | 99 | 13311 | 8.6374s | 11258 | 116s | 18508 | 0.022911s |
p38 | 10594 | 98 | 10841 | 7.61438s | 10551 | 48s | 19186 | 0.020972s |
p39 | 11951 | 107 | 12461 | 8.35518s | 11824 | 69s | 22812 | 0.015622s |
p40 | 13059 | 125 | 14669 | 7.62964s | 13024 | 72s | 28010 | 0.015623s |
p41 | 6737 | 11 | 7007 | 1.1323s | 6640 | 7s | 14970 | 0.004984s |
p42 | 5755 | 32 | 6695 | 5.26193s | 5750 | 14s | 13188 | 0.00798s |
p43 | 5302 | 32 | 6087 | 4.55689s | 5369 | 20s | 9825 | 0.01097s |
p44 | 7107 | 14 | 7986 | 1.59194s | 7462 | 7s | 14009 | 0.004988s |
p45 | 6580 | 25 | 7120 | 2.18661s | 6396 | 13s | 12474 | 0.007979s |
p46 | 5980 | 36 | 6619 | 1.02503s | 6083 | 20s | 10891 | 0.009964s |
p47 | 7077 | 13 | 7461 | 1.50559s | 6836 | 9s | 11727 | 0.004986s |
p48 | 6239 | 25 | 5991 | 2.20568s | 5910 | 14s | 8852 | 0.008945s |
p49 | 5609 | 38 | 6358 | 3.27401s | 5584 | 19s | 7943 | 0.003273s |
p50 | 8848 | 13 | 9237 | 3.157s | 8861 | 8s | 18520 | 0.005016s |
p51 | 7414 | 36 | 7601 | 0.913229s | 7471 | 17s | 17031 | 0s |
p52 | 9246 | 15 | 10910 | 1.5276s | 9253 | 7s | 17892 | 0.005985s |
p53 | 8531 | 38 | 9641 | 3.77231s | 8589 | 18s | 19483 | 0.009974s |
p54 | 8838 | 23 | 9610 | 4.64562s | 8834 | 19s | 12040 | 0s |
p55 | 7654 | 34 | 8514 | 0.858943s | 7663 | 21s | 12606 | 0.010969s |
p56 | 21748 | 140 | 24850 | 4.12567s | 22384 | 67s | 54407 | 0.025959s |
p57 | 26379 | 155 | 29835 | 15.1951s | 27321 | 68s | 76688 | 0.02594s |
p58 | 38059 | 160 | 41940 | 39.0419s | 38651 | 69s | 87888 | 0.027953s |
p59 | 27694 | 143 | 29453 | 4.66213s | 28015 | 69s | 80092 | 0.02593s |
p60 | 21241 | 137 | 29940 | 15.0043s | 23122 | 67s | 52296 | 0.019138s |
p61 | 25596 | 139 | 30463 | 13.0509s | 25995 | 66s | 77952 | 0.02593s |
p62 | 33662 | 143 | 37995 | 12.9666s | 34816 | 67s | 85652 | 0.023771s |
p63 | 25397 | 142 | 27126 | 21.562s | 25279 | 68s | 69398 | 0.026924s |
p64 | 21400 | 164 | 33688 | 16.8349s | 23637 | 66s | 51047 | 0.026929s |
p65 | 25794 | 137 | 30490 | 5.93459s | 25958 | 134s | 76163 | 0.0233s |
p66 | 32688 | 145 | 34887 | 12.249s | 33124 | 68s | 81005 | 0.012643s |
p67 | 25231 | 142 | 32586 | 35.3639s | 27487 | 68s | 72218 | 0.017105s |
p68 | 22086 | 137 | 25748 | 12.1449s | 22317 | 68s | 56007 | 0.026925s |
p69 | 26100 | 143 | 27008 | 11.958s | 25258 | 68s | 78451 | 0.0232s |
p70 | 33316 | 147 | 35590 | 13.4274s | 33102 | 68s | 86151 | 0.026926s |
p71 | 25679 | 144 | 28476 | 21.502s | 26433 | 71s | 70258 | 0.02024s |
Result | Times(s) | |
---|---|---|
p1 | 8848 | 8 |
p2 | 7914 | 8 |
p3 | 9314 | 8 |
p4 | 10795 | 6 |
p5 | 8838 | 8 |
p6 | 7777 | 7 |
p7 | 9488 | 7 |
p8 | 11088 | 7 |
p9 | 8593 | 5 |
p10 | 7627 | 7 |
p11 | 8938 | 7 |
p12 | 10252 | 8 |
p13 | 8294 | 18 |
p14 | 7137 | 17 |
p15 | 8862 | 17 |
p16 | 10524 | 20 |
p17 | 8294 | 17 |
p18 | 7152 | 16 |
p19 | 8907 | 16 |
p20 | 10514 | 17 |
p21 | 8171 | 17 |
p22 | 7178 | 16 |
p23 | 8774 | 14 |
p24 | 10463 | 19 |
p25 | 11639 | 106 |
p26 | 10776 | 99 |
p27 | 12336 | 101 |
p28 | 13736 | 105 |
p29 | 12548 | 102 |
p30 | 11337 | 139 |
p31 | 13378 | 189 |
p32 | 15376 | 182 |
p33 | 11632 | 101 |
p34 | 10635 | 103 |
p35 | 12235 | 100 |
p36 | 13835 | 99 |
p37 | 11326 | 99 |
p38 | 10594 | 98 |
p39 | 11951 | 107 |
p40 | 13059 | 125 |
p41 | 6737 | 11 |
p42 | 5755 | 32 |
p43 | 5302 | 32 |
p44 | 7107 | 14 |
p45 | 6580 | 25 |
p46 | 5980 | 36 |
p47 | 7077 | 13 |
p48 | 6239 | 25 |
p49 | 5609 | 38 |
p50 | 8848 | 13 |
p51 | 7414 | 36 |
p52 | 9246 | 15 |
p53 | 8531 | 38 |
p54 | 8838 | 23 |
p55 | 7654 | 34 |
p56 | 21748 | 140 |
p57 | 26379 | 155 |
p58 | 38059 | 160 |
p59 | 27694 | 143 |
p60 | 21241 | 137 |
p61 | 25596 | 139 |
p62 | 33662 | 143 |
p63 | 25397 | 142 |
p64 | 21400 | 164 |
p65 | 25794 | 137 |
p66 | 32688 | 145 |
p67 | 25231 | 142 |
p68 | 22086 | 137 |
p69 | 26100 | 143 |
p70 | 33316 | 147 |
p71 | 25679 | 144 |
Result | Times(s) | |
---|---|---|
p1 | 8848 | 6s |
p2 | 7914 | 5s |
p3 | 9314 | 6s |
p4 | 10859 | 7s |
p5 | 8838 | 6s |
p6 | 7777 | 5s |
p7 | 9488 | 6s |
p8 | 11088 | 6s |
p9 | 8462 | 7s |
p10 | 7617 | 5s |
p11 | 8932 | 6s |
p12 | 10138 | 7s |
p13 | 8252 | 13s |
p14 | 7182 | 12s |
p15 | 8862 | 14s |
p16 | 10612 | 17s |
p17 | 8227 | 13s |
p18 | 7188 | 12s |
p19 | 8887 | 12s |
p20 | 10513 | 13s |
p21 | 8068 | 13s |
p22 | 7154 | 13s |
p23 | 8806 | 13s |
p24 | 10327 | 14s |
p25 | 11639 | 77s |
p26 | 10781 | 78s |
p27 | 12340 | 77s |
p28 | 13736 | 79s |
p29 | 12450 | 153s |
p30 | 11391 | 155s |
p31 | 13367 | 217s |
p32 | 15387 | 245s |
p33 | 11706 | 76s |
p34 | 10635 | 73s |
p35 | 12235 | 75s |
p36 | 13835 | 75s |
p37 | 11258 | 116s |
p38 | 10551 | 48s |
p39 | 11824 | 69s |
p40 | 13024 | 72s |
p41 | 6640 | 7s |
p42 | 5750 | 14s |
p43 | 5369 | 20s |
p44 | 7462 | 7s |
p45 | 6396 | 13s |
p46 | 6083 | 20s |
p47 | 6836 | 9s |
p48 | 5910 | 14s |
p49 | 5584 | 19s |
p50 | 8861 | 8s |
p51 | 7471 | 17s |
p52 | 9253 | 7s |
p53 | 8589 | 18s |
p54 | 8834 | 19s |
p55 | 7663 | 21s |
p56 | 22384 | 67s |
p57 | 27321 | 68s |
p58 | 38651 | 69s |
p59 | 28015 | 69s |
p60 | 23122 | 67s |
p61 | 25995 | 66s |
p62 | 34816 | 67s |
p63 | 25279 | 68s |
p64 | 23637 | 66s |
p65 | 25958 | 134s |
p66 | 33124 | 68s |
p67 | 27487 | 68s |
p68 | 22317 | 68s |
p69 | 25258 | 68s |
p70 | 33102 | 68s |
p71 | 26433 | 71s |