本文为《算法》课程上的作业,研究和实现容量设备选址问题求解的几个解决方案。本文涉及到了贪心法、局部搜索、模拟退火。
Description
带容量的设备选址问题(CFLP)是一个求解最优解问题,属于NP类问题。由于解的可能非常多,不可能一一枚举,在给定的有限时间内,只能求出接近最优解的解。
带容量的设备选址问题给定了数量$n$个设备和$m$个人,其中每个设备都有开设的费用和容纳容量两个属性,而每个人有需求、到每一个设备的费用两个属性。设备可以选择开或者不开,但是每个人必须都有所对应的设备,并且设备要满足人的需求。
假设有10个设备和50个人,那么就一共有$50^{10}$种解,每个人都可以选择其中一个设备。除去大部分非法的解(即不满足容量限制),剩下的解的数量也是非常庞大的。CFLP问题就是在这些合法的解中找到最优解,但是所需要的时间是非常长的。因此我们退而求其次,找到一个看起来比较接近最优解的解即可。
求解设备选址问题,通常采用启发式搜索,即我们选择一个初始解,按一定的策略进行启发式搜索,让我们所搜索到的解越来越接近最优解。启发式搜索的关键在于,如何定义搜索的策略。启发式搜索最终求得的解一定程度受初始解和搜索的策略的影响。当然,贪心法也可以求解CFLP问题,但是贪心法的关键在于如何定义贪心的策略。贪心法的解受贪心策略的影响,因此在策略固定的时候,贪心法的解是固定不变的。
接下来,我们首先设计好程序的数据结构、输入处理、输出处理。
Structure
Types
按照CFLP的内容,我们需要定义设备类型、消费者类型、解类型。
struct Facility {
int capacity;
int openingCost;
};
struct Customer {
int demand;
std::vector<int> assignmentCost;
};
struct Result {
int cost;
std::vector<bool> status;
std::vector<size_t> assignment;
};
其中,解类型包含了一切我们需要输出的数据。不过,为了防止数据错误,我们应该编写一个验证解类型的正确性的函数。
bool check(const std::vector<Facility> &f, const std::vector<Customer> &c, const Result res) {
int cost = 0, capacity[f.size()] = {0};
for (size_t i = 0; i < f.size(); i++) {
if (res.status[i]) {
cost += f[i].openingCost;
}
}
for (size_t i = 0; i < c.size(); i++) {
capacity[res.assignment[i]] += c[i].demand;
if (capacity[res.assignment[i]] > f[res.assignment[i]].capacity) {
return false;
}
cost += c[i].assignmentCost[res.assignment[i]];
}
return cost == res.cost;
}
在任意一种方法求解到解之后,都可以使用check
函数来验证解的合法性。
Input
在CFLP中,我们需要处理的输入有两类:一个是CFLP的数据输入,一个是CFLP的当前最优解输入。
前者是CFLP的数据来源,而后者是CFLP的解。每次求得CFLP的解,都与当前最优解对比,如果CFLP的解比当前最优解更加好,那么就将我们求得的解存储到本地中,以提供给下一次求CFLP解进行对比。因为设备选址问题的启发式策略可能是随机的,将当前最优解存储下来有利于数据的对比。
std::pair<Result, std::pair<std::vector<Facility>, std::vector<Customer>>> input(int testcase) {
size_t facilityNum, customerNum;
std::vector<Facility> facilities;
std::vector<Customer> customers;
Result result;
// 数据输入
std::ifstream in("testcases/p" + std::to_string(testcase));
in >> facilityNum >> customerNum;
for (size_t i = 0; i < facilityNum; i++) {
Facility facility;
in >> facility.capacity >> facility.openingCost;
facilities.push_back(facility);
}
for (size_t i = 0; i < customerNum; i++) {
Customer customer;
double val;
in >> val;
customer.demand = (int) val;
customers.push_back(customer);
}
for (size_t i = 0; i < facilityNum; i++) {
for (size_t j = 0; j < customerNum; j++) {
double val;
in >> val;
customers[j].assignmentCost.push_back((int) val);
}
}
in.close();
// 当前最优解输入
std::ifstream rin("best/p" + std::to_string(testcase));
if (rin.is_open()) {
rin >> result.cost;
for (size_t i = 0; i < facilityNum; i++) {
bool val;
rin >> val;
result.status.push_back(val);
}
for (size_t i = 0; i < customerNum; i++) {
size_t val;
rin >> val;
result.assignment.push_back(val);
}
} else {
result.cost = 0;
}
rin.close();
return std::make_pair(result, std::make_pair(facilities, customers));
}
Output
与输入一样,输出也需要处理两类数据,一个是将求得的解输出到控制台中,另一个是将求得的解和当前最优解对比,如果当前最优解不够好,那么就更新本地存储的当前最优解。
void output(int testcase, Result best, Result res) {
// 解输出
std::cout << res.cost << std::endl;
if (res.status.size() != 0) {
std::cout << res.status[0];
for (size_t i = 1; i < res.status.size(); i++) {
std::cout << ' ' << res.status[i];
}
std::cout << std::endl;
}
if (res.assignment.size() != 0) {
std::cout << res.assignment[0];
for (size_t i = 1; i < res.assignment.size(); i++) {
std::cout << ' ' << res.assignment[i];
}
std::cout << std::endl;
}
// 对比、存储当前最优解
if (best.cost < res.cost && best.cost != 0) {
std::cout << "Compare with best cost " << best.cost << ", percentage " << (float)(res.cost - best.cost) / best.cost * 100 << '%' << std::endl;
} else {
std::cout << "Get the best cost" << std::endl;
std::ofstream out("best/p" + std::to_string(testcase));
out << res.cost << std::endl;
if (res.status.size() != 0) {
out << res.status[0];
for (size_t i = 1; i < res.status.size(); i++) {
out << ' ' << res.status[i];
}
out << std::endl;
}
if (res.assignment.size() != 0) {
out << res.assignment[0];
for (size_t i = 1; i < res.assignment.size(); i++) {
out << ' ' << res.assignment[i];
}
out << std::endl;
}
out.close();
}
}
当然,我们还需要记录一下程序执行的时间,以完成我们的数据记录表。
void test(int testcase, std::function<Result(std::vector<Facility>, std::vector<Customer>)> fn) {
std::cout << "Test " << testcase << ":" << std::endl;
std::pair<Result, std::pair<std::vector<Facility>, std::vector<Customer>>> data = input(testcase);
auto start = std::chrono::system_clock::now();
Result res = fn(data.second.first, data.second.second);
auto stop = std::chrono::system_clock::now();
output(testcase, data.first, res);
std::ofstream out("best/markdown", std::ios_base::app);
out << "| p" << testcase << " | " << res.cost << " | " << (double) std::chrono::duration_cast<std::chrono::milliseconds>(stop - start).count() / 1000 << " |" << std::endl;
out.close();
std::cout << std::endl;
}
Approach #1 Greedy
Intuition
贪心法是解决设备选址问题的其中一种方法,应该也算是最简单的方法了(除了随机法)。但是贪心法求得的解很大程度取决于贪心策略,通常和最优解有蛮大程度的差距。
贪心法的核心在于如何制定贪心策略,一个贪心策略的好坏决定了解的好坏。而且,贪心法通常只能考虑到一般情况,如果有特殊测试样例,可能贪心法还不如随机法。
我们知道,设备可以选择开与不开,而人必须要选择一个设备。因此,最简单的贪心策略就是让人去选择最优的设备。为了让程序更简单,我们可以按输入数据的人的顺序来选择设备。
$Solution = \Sigma Facility.openingCost + \Sigma Min(Customer.assignmentCost)$
当然,我们要加一下限制,必须让解合法,也就是将人的安排费用从小到大排序,优先选择费用小的并且容量足够的设备。
不过,如果你实现了这种策略之后,就会发现,基本所有设备都被开启了。这样会产生大量的费用,因为某些人即使选择比最小费用差一点的设备,而使得设备空闲下来,可能总费用比选择最小费用的设备还要低。为了减弱这种情况对解的影响,我们将设备所使用的容量排序,每次删去已使用容量最少的设备,然后再重新按之前的策略进行设备分配。
如果删去了某个设备,所求得的解比之前的解更加好,那么就保持这种设备开启情况,并且继续删去下一个设备。如果所求得的解比之前的更坏,那么我们可以恢复之前删去的设备,并去删去下一个设备。这样,就可以将大部分设备关闭。
以上的贪心策略总结起来就是两条规则:
- 策略1:将每个人分配到费用最低且容量足够的设备上。
- 策略2:尝试删去容量分配最少的设备,重新执行策略1。
虽然删去设备、恢复设备这些操作看起来比较像是启发式搜索,不过由于策略是固定的,每次所得到的解也是固定的。
Algorithm
首先实现一个带设备过滤限制的贪心函数,该函数可以将部分设备过滤掉,从剩下的设备种执行策略1。
Result greedyWithFilter(const std::vector<Facility> &f, const std::vector<Customer> &c, std::vector<std::pair<int, size_t>> &capacity, const std::vector<bool> &filter) {
Result res;
res.cost = 0;
res.status = std::vector<bool>(f.size());
res.assignment = std::vector<size_t>(c.size());
std::vector<std::vector<std::pair<int, size_t>>> cost(c.size());
for (size_t i = 0; i < c.size(); i++) {
for (size_t j = 0; j < c[i].assignmentCost.size(); j++) {
cost[i].push_back(std::make_pair(c[i].assignmentCost[j], j));
}
std::sort(cost[i].begin(), cost[i].end(), [](std::pair<int, size_t> a, std::pair<int, size_t> b) -> bool {
return a.first < b.first;
});
}
for (size_t i = 0; i < f.size(); i++) {
capacity.push_back(std::make_pair(0, i));
}
for (size_t i = 0; i < c.size(); i++) {
size_t index = 0;
while (index < cost[i].size() && (filter[cost[i][index].second] == false ||
capacity[cost[i][index].second].first + c[i].demand > f[cost[i][index].second].capacity)) {
index++;
}
if (index == cost[i].size()) {
res.cost = 0;
break;
}
if (res.status[cost[i][index].second] == false) {
res.status[cost[i][index].second] = true;
res.cost += f[cost[i][index].second].openingCost;
}
res.assignment[i] = cost[i][index].second;
res.cost += cost[i][index].first;
capacity[cost[i][index].second].first += c[i].demand;
}
return res;
}
接下来,实现贪心函数,负责实现设备删去、设备恢复等逻辑。
Result Greedy(const std::vector<Facility> &f, const std::vector<Customer> &c) {
std::vector<bool> filter(f.size());
for (size_t i = 0; i < f.size(); i++) {
filter[i] = true;
}
std::set<size_t> s;
Result best;
best.cost = 0;
size_t last = (size_t) -1;
while (s.size() != f.size()) {
std::vector<std::pair<int, size_t>> capacity;
Result res = greedyWithFilter(f, c, capacity, filter);
if ((res.cost != 0 && res.cost <= best.cost) || best.cost == 0) {
best = res;
} else if (last != (size_t)-1 || res.cost == 0) {
filter[last] = true;
}
std::sort(capacity.begin(), capacity.end(), [](std::pair<int, size_t> a, std::pair<int, size_t> b) -> bool {
return a.first < b.first;
});
size_t index = 0;
while (index < capacity.size() && (filter[capacity[index].second] == false || s.count(capacity[index].second))) {
index++;
}
if (index == capacity.size()) {
break;
}
last = capacity[index].second;
filter[last] = false;
s.insert(last);
}
if (check(f, c, best) == false) {
std::cout << "Error Result" << std::endl;
std::exit(-1);
}
return best;
}
Result
Test Case | Result | Time(s) |
---|---|---|
p1 | 9142 | 0.001 |
p2 | 8104 | 0.001 |
p3 | 9824 | 0.001 |
p4 | 11261 | 0.002 |
p5 | 9348 | 0.001 |
p6 | 8061 | 0.001 |
p7 | 9990 | 0.001 |
p8 | 11790 | 0.003 |
p9 | 8598 | 0.002 |
p10 | 7617 | 0.002 |
p11 | 9064 | 0.001 |
p12 | 10301 | 0.001 |
p13 | 8544 | 0.007 |
p14 | 7307 | 0.007 |
p15 | 9276 | 0.007 |
p16 | 11076 | 0.008 |
p17 | 8579 | 0.007 |
p18 | 7342 | 0.008 |
p19 | 9174 | 0.008 |
p20 | 10774 | 0.007 |
p21 | 8397 | 0.008 |
p22 | 7330 | 0.007 |
p23 | 8943 | 0.009 |
p24 | 10543 | 0.008 |
p25 | 12167 | 0.044 |
p26 | 11086 | 0.045 |
p27 | 12886 | 0.046 |
p28 | 14686 | 0.047 |
p29 | 14307 | 0.047 |
p30 | 12852 | 0.046 |
p31 | 15252 | 0.045 |
p32 | 17439 | 0.045 |
p33 | 12224 | 0.045 |
p34 | 11232 | 0.047 |
p35 | 12883 | 0.046 |
p36 | 14483 | 0.048 |
p37 | 11521 | 0.055 |
p38 | 10594 | 0.046 |
p39 | 12067 | 0.045 |
p40 | 13273 | 0.046 |
p41 | 6847 | 0.003 |
p42 | 5843 | 0.013 |
p43 | 5401 | 0.021 |
p44 | 7585 | 0.003 |
p45 | 6523 | 0.012 |
p46 | 6123 | 0.022 |
p47 | 6634 | 0.003 |
p48 | 5615 | 0.013 |
p49 | 5567 | 0.022 |
p50 | 9454 | 0.004 |
p51 | 7576 | 0.017 |
p52 | 9588 | 0.003 |
p53 | 8795 | 0.013 |
p54 | 9702 | 0.003 |
p55 | 8159 | 0.014 |
p56 | 22166 | 0.06 |
p57 | 27266 | 0.061 |
p58 | 39554 | 0.064 |
p59 | 30232 | 0.064 |
p60 | 20974 | 0.071 |
p61 | 25172 | 0.065 |
p62 | 33549 | 0.062 |
p63 | 27319 | 0.065 |
p64 | 20840 | 0.064 |
p65 | 24994 | 0.063 |
p66 | 32442 | 0.067 |
p67 | 27048 | 0.069 |
p68 | 20840 | 0.063 |
p69 | 25005 | 0.065 |
p70 | 33829 | 0.061 |
p71 | 27022 | 0.061 |
Approach #2 Local Search(Hill Climbing)
Intuition
设备选址问题可以用启发式搜索求解,其中局部搜索是一种方法。在这里我采用爬山法来求解CFLP,爬山法属于局部搜索中的一种。
所谓的爬山法,就是从一个初始解出发,从当前解的邻域中找到比该解更好的解,然后将这个更好的解视为当前解。这样一直循环迭代下去,最终会趋于稳定,得到一个局部最优解。因为当前解是一直朝着更低的费用前进,只有向上的行为,所以叫爬山法。
不过局部搜索有一个缺点,就是最终解是一个局部最优解,可能不是整个问题的最优解。
局部搜索的关键在于初始解的生成和搜索策略的实现。通常情况下,初始解是可以随机生成的,但是,局部搜索的收敛速度是很慢的,我们可以基于一个比较好的解出发,而不是随机生成初始解。这里我们采用方法一贪心法所生成的解作为初始解,这样就能保证局部搜索的解一定比贪心法的解要好。
搜索策略的实现就是如何找邻域的问题,在TSP问题中我们可以简单的通过K-opt法来找邻域,但是在CFLP问题中,由于限制比较多,邻域的定义也不那么直观。
我们定义一下的策略来随机生成某个解的邻域:
- 策略1:将1个人从某个设备移动到另一个设备。
- 策略2:将不同设备的2个人相互交换。
- 策略3:将2个设备安排的所有人相互交换。
以上3种策略所生成的解,我们都认为它是当前解的邻解。在局部搜索的每一次迭代中,寻找当前解的邻域中的某个解,通过对比这两个解的费用,来决定当前解是否修改。
Algorithm
这里,我们不再采用前面贪心法修改解的方法,虽然它依靠check
来检测错误可以很好找到打码时留下的BUG。我们实现一个setNewCost
函数,根据解的消费者安排情况和设备开启情况,来计算新的总费用,并返回该解是否合法。
bool setNewCost(const std::vector<Facility> &f, const std::vector<Customer> &c, Result &res) {
int cost = 0, capacity[f.size()] = {0};
for (size_t i = 0; i < f.size(); i++) {
if (res.status[i]) {
cost += f[i].openingCost;
}
}
for (size_t i = 0; i < c.size(); i++) {
capacity[res.assignment[i]] += c[i].demand;
if (capacity[res.assignment[i]] > f[res.assignment[i]].capacity) {
return false;
}
cost += c[i].assignmentCost[res.assignment[i]];
}
res.cost = cost;
return true;
}
然后根据上述所提及的3个搜索策略,编写生成邻域的解的代码。生成邻域需要用上随机数生成函数,并使用当前时间作为随机种子。
Result generateNeighborSolution(const std::vector<Facility> &f, const std::vector<Customer> &c, Result best) {
std::default_random_engine random(std::chrono::system_clock::now().time_since_epoch().count());
unsigned type = random() % 3;
Result res;
size_t count = 0;
bool flag = false;
switch (type + 1) {
case 1: // 移动1个人
do {
// i - 人, j - 设备
size_t i = random() % c.size(), j = random() % f.size();
if (best.assignment[i] == j) {
flag = true;
continue;
} else {
flag = false;
}
res = best;
size_t last = res.assignment[i];
res.assignment[i] = j;
bool empty = true;
for (size_t k = 0; k < c.size(); k++) {
if (res.assignment[k] == last) {
empty = false;
break;
}
}
if (empty) {
res.status[last] = false;
}
count++;
} while (count < 100 && (flag || setNewCost(f, c, res) == false));
break;
case 2: // 交换2个人
do {
// i - 人A, j - 人B
size_t i = random() % c.size(), j = random() % c.size();
if (i == j || best.assignment[i] == best.assignment[j]) {
flag = true;
continue;
} else {
flag = false;
}
res = best;
size_t tmp = res.assignment[i];
res.assignment[i] = res.assignment[j];
res.assignment[j] = tmp;
count++;
} while (count < 100 && (flag || setNewCost(f, c, res) == false));
break;
case 3: // 交换2个设备
do {
// i - 设备A, j - 设备B
size_t i = random() % f.size(), j = random() % f.size();
if (i == j) {
flag = true;
continue;
} else {
flag = false;
}
res = best;
for (size_t k = 0; k < c.size(); k++) {
if (res.assignment[k] == i) {
res.assignment[k] = j;
} else if (res.assignment[k] == j) {
res.assignment[k] = i;
}
}
count++;
} while (count < 100 && (flag || setNewCost(f, c, res) == false));
break;
}
return res;
}
接下来实现局部搜索的迭代部分,循环次数我们可以设置为$30*(|Facility|+|Customer|)$,这样可以保证不同大小的数据都能得到适合的迭代次数。
Result LocalSearch(const std::vector<Facility> &f, const std::vector<Customer> &c) {
Result best = Greedy(f, c);
for (size_t i = 0; i < 30 * (f.size() + c.size()); i++) {
Result res = generateNeighborSolution(f, c, best);
if (best.cost > res.cost) {
best = res;
}
}
return best;
}
Result
Test Case | Result | Time(s) |
---|---|---|
p1 | 9055 | 0.017 |
p2 | 8017 | 0.02 |
p3 | 9550 | 0.021 |
p4 | 10778 | 0.02 |
p5 | 9213 | 0.016 |
p6 | 7995 | 0.017 |
p7 | 9913 | 0.018 |
p8 | 11655 | 0.016 |
p9 | 8598 | 0.016 |
p10 | 7617 | 0.017 |
p11 | 9064 | 0.016 |
p12 | 10138 | 0.017 |
p13 | 8544 | 0.027 |
p14 | 7200 | 0.026 |
p15 | 9249 | 0.026 |
p16 | 11049 | 0.026 |
p17 | 8459 | 0.027 |
p18 | 7246 | 0.026 |
p19 | 9058 | 0.029 |
p20 | 10712 | 0.028 |
p21 | 8173 | 0.025 |
p22 | 7330 | 0.025 |
p23 | 8943 | 0.024 |
p24 | 10543 | 0.024 |
p25 | 12036 | 0.129 |
p26 | 10951 | 0.13 |
p27 | 12662 | 0.146 |
p28 | 14541 | 0.129 |
p29 | 13343 | 0.13 |
p30 | 12001 | 0.137 |
p31 | 14296 | 0.133 |
p32 | 16108 | 0.137 |
p33 | 11849 | 0.134 |
p34 | 11011 | 0.132 |
p35 | 12474 | 0.132 |
p36 | 14079 | 0.133 |
p37 | 11329 | 0.131 |
p38 | 10594 | 0.124 |
p39 | 12067 | 0.126 |
p40 | 13070 | 0.125 |
p41 | 6847 | 0.038 |
p42 | 5772 | 0.046 |
p43 | 5373 | 0.055 |
p44 | 7485 | 0.042 |
p45 | 6515 | 0.045 |
p46 | 6016 | 0.055 |
p47 | 6482 | 0.04 |
p48 | 5613 | 0.045 |
p49 | 5369 | 0.056 |
p50 | 8911 | 0.048 |
p51 | 7545 | 0.063 |
p52 | 9588 | 0.05 |
p53 | 8795 | 0.06 |
p54 | 9296 | 0.052 |
p55 | 8158 | 0.058 |
p56 | 21848 | 0.216 |
p57 | 27189 | 0.199 |
p58 | 39046 | 0.231 |
p59 | 29222 | 0.222 |
p60 | 20934 | 0.182 |
p61 | 25036 | 0.186 |
p62 | 33358 | 0.201 |
p63 | 27241 | 0.183 |
p64 | 20620 | 0.185 |
p65 | 24888 | 0.181 |
p66 | 32155 | 0.203 |
p67 | 26234 | 0.196 |
p68 | 20720 | 0.193 |
p69 | 24899 | 0.201 |
p70 | 33514 | 0.211 |
p71 | 26933 | 0.204 |
Approach #3 Simulated Annealing
Intuition
通过上面两种方法,可以发现爬山法的费用跟贪心的费用相比有10%~15%的提升。不过,爬山法这类局部搜索方案很容易达到局部最优解,而没有办法求解更加好的解。
模拟退火是在局部搜索的基础上进行优化的启发式搜索方法,能够使得当前解有一定概率恶化,从而避免局部最优解。
我们可以设置一个初始温度,每次求邻域的解之后,对比当前解和邻域中的解的能量差。如果能量差为负,那就允许当前解变化。如果能量差为正,根据当前温度计算出一个概率值,有一定概率允许当前解变化。此时,当前解的费用是低于邻域解的,因此这种解的变化实际上是一种恶化。
我们取$R$为$[0,1]$中的任意一个实数,即随机值,取$P=e^{- \frac{\Delta E}{T} }$。如果$R<P$,那么我们就认为当前解可以恶化。
每次处理完解之后,当前温度将按降温系数的限制来降温,当温度降低到一定程度之后,即达到了终止温度之后,迭代结束。
模拟退火比较繁琐的一步是选取初始温度和降温系数,这里采用的初始温度为500,降温系数为0.96。
Algorithm
模拟退火是在局部搜索的基础上优化的,实际上,生成邻域的代码可以完全照搬局部搜索的,我们只需要修改迭代一部分的代码。
首先定义初始温度、终止温度、降温系数。
namespace simulated_annealing {
const double T_START = 500; // 初始温度
const double T_END = 0.000001; // 终止温度
const double Q = 0.9; // 降温系数
}
接下来实现降温操作、解恶化等。
Result SimulatedAnnealing(const std::vector<Facility> &f, const std::vector<Customer> &c) {
Result best = Greedy(f, c);
double t = T_START;
while (t > T_END) {
for (size_t i = 0; i < 10 * (f.size() + c.size()); i++) {
Result res = generateNeighborSolution(f, c, best);
if (best.cost > res.cost) {
best = res;
} else {
std::default_random_engine random(std::chrono::system_clock::now().time_since_epoch().count());
std::uniform_real_distribution<> dist(0, 1);
double r = dist(random);
double p = std::exp((double)(best.cost - res.cost) / t);
if (r < p) {
best = res;
}
}
}
t *= Q;
}
return best;
}
Result
Test Case | Result | Time(s) |
---|---|---|
p1 | 8985 | 1.379 |
p2 | 7926 | 1.372 |
p3 | 9513 | 1.363 |
p4 | 11121 | 1.528 |
p5 | 9198 | 1.249 |
p6 | 7887 | 1.376 |
p7 | 9887 | 1.235 |
p8 | 11522 | 1.285 |
p9 | 8477 | 1.15 |
p10 | 7648 | 1.092 |
p11 | 9361 | 1.145 |
p12 | 10826 | 1.149 |
p13 | 8842 | 1.591 |
p14 | 7520 | 1.559 |
p15 | 9288 | 1.596 |
p16 | 11091 | 1.814 |
p17 | 8452 | 1.614 |
p18 | 7279 | 1.572 |
p19 | 9113 | 1.529 |
p20 | 11298 | 1.579 |
p21 | 8144 | 1.5 |
p22 | 7316 | 1.497 |
p23 | 9182 | 1.476 |
p24 | 11274 | 1.497 |
p25 | 12689 | 6.996 |
p26 | 11603 | 6.664 |
p27 | 14009 | 6.644 |
p28 | 16423 | 6.698 |
p29 | 12651 | 7.061 |
p30 | 11896 | 6.813 |
p31 | 14598 | 6.842 |
p32 | 17774 | 6.755 |
p33 | 12028 | 6.887 |
p34 | 11581 | 6.441 |
p35 | 14468 | 6.808 |
p36 | 16381 | 6.492 |
p37 | 12200 | 6.428 |
p38 | 11282 | 6.353 |
p39 | 13978 | 6.334 |
p40 | 15680 | 6.694 |
p41 | 6945 | 2.669 |
p42 | 7334 | 2.696 |
p43 | 6655 | 2.806 |
p44 | 7159 | 3.063 |
p45 | 6679 | 2.708 |
p46 | 7002 | 3.161 |
p47 | 6316 | 3.158 |
p48 | 6238 | 2.821 |
p49 | 5825 | 2.871 |
p50 | 9275 | 3.472 |
p51 | 8132 | 3.91 |
p52 | 9449 | 3.545 |
p53 | 9628 | 3.369 |
p54 | 9273 | 3.783 |
p55 | 8157 | 3.552 |
p56 | 23056 | 9.787 |
p57 | 30896 | 10.34 |
p58 | 46768 | 9.59 |
p59 | 36127 | 9.55 |
p60 | 22741 | 9.691 |
p61 | 30648 | 9.682 |
p62 | 46425 | 9.557 |
p63 | 31937 | 9.388 |
p64 | 23346 | 9.413 |
p65 | 30361 | 9.376 |
p66 | 45389 | 9.597 |
p67 | 34301 | 9.263 |
p68 | 22609 | 9.889 |
p69 | 29729 | 11.412 |
p70 | 47755 | 10.906 |
p71 | 31295 | 13.429 |
Solution Result
以上是局部搜索的样例1-5的输出,其中每个样例的前三行为当前解,而最后一行为与本程序执行的最优解做比较。
如果需要查看其他样例的最优解,可以前往GitHub查看。
可执行脚本编译运行程序。
$ ./build.sh
$ ./cflp
Conclusion
本次用了贪心法、爬山法、模拟退火三种方法来解决CFLP问题,其中,基于贪心法的解作为初始解的爬山法的解是最优的,并且相比贪心法,费用降低了10%~15%左右。
而基于爬山法的模拟退火,可能是因为初始温度和温度系数的把控不当,模拟退火的解实际比爬山法还要差,并且及其不稳定。有时候模拟退火的解非常接近爬山法的解,而有时候解比贪心法还要差。
在经过多次修改之后,部分样例的模拟退火法可以求得更好的解,但是接近一半的样例还是比爬山法要差。不过相比贪心法已经有了一定提升。