Capacitated Facility Location Problem
Suppose there are n facilities and m customers. We wish to...
Capacitated Facility Location Problem
Suppose there are n facilities and m customers. We wish to choose:
(1) which of the n facilities to open
(2) 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.
There are currently 71 data files. The format of these data files is:
|J| |I|
s_1 f_1
s_2 f_2
…
s_|J| f_|J|
d_1 d_2 d_3 … d_|I|
c_{11} c_{12} c_{13} … c_{1|I|}
c_{21} c_{22} c_{23} … c_{2|I|}
… … … …
c_{|J|1} c_{|J|2} c_{|J|3} … c_{|J||I|}
where:
|J| is the number of potential facility locations;
|I| is the number of customers;
s_j (j=1,…,|J|) is the capacity of facility j;
f_j (j=1,…,|J|) is the fixed cost of opening facility j;
d_i (i=1,…,|I|) is the demand of customer i;
c_{ji} (j=1,…,|J|), (i=1,…,|I|) is the cost of allocating all the demand of customer i to facility j.
算法如下
//测试文件与结果文件的读写
#ifndef _FILE_H_
#define _FILE_H_
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
using namespace std;
//字符串分割
vector<string> split(const string& str, const string& delim) {
vector<string> res;
if(\"\" == str) return res;
char * strs = new char[str.length() + 1];
strcpy(strs, str.c_str());
char * d = new char[delim.length() + 1];
strcpy(d, delim.c_str());
char *p = strtok(strs, d);
while(p) {
string s = p;
res.push_back(s);
p = strtok(NULL, d);
}
return res;
}
//测试数据获取
void getData(string path, int &fnum, int &cnum, vector<int> &_capacity, vector<int> &_open_cost, vector<int> &_demand, vector<int> &_ass_cost) {
ifstream in(path);
if (!in.is_open()) {
cout << \"open error!\" << endl;
}
string str;
getline(in, str);
vector<string> sv;
sv = split(str, \" \");
int num[2];
stringstream ss;
for (int i = 0; i < 2; i++) {
ss << sv[i];
ss >> num[i];
ss.clear();
}
int capacity[num[0]], open_cost[num[0]];
for (int i = 0; i < num[0]; i++) {
getline(in, str);
sv = split(str, \" \");
ss << sv[0];
ss >> capacity[i];
_capacity.push_back(capacity[i]);
ss.clear();
ss << sv[1];
ss >> open_cost[i];
_open_cost.push_back(open_cost[i]);
ss.clear();
}
int demand[num[1]], flag = (num[1]+9)/10;
for (int i = 0; i < flag; i++) {
getline(in, str);
int pos;
if((pos = str.find(\".\")) != string::npos) {
sv = split(str, \".\");
}
else {
sv = split(str, \" \");
}
for (int j = 0; j < sv.size(); j++) {
ss << sv[j];
ss >> demand[i*10+j];
_demand.push_back(demand[i*10+j]);
ss.clear();
}
}
flag = (num[0]*num[1]+9)/10;
int ass_cost[num[0]*num[1]];
for (int i = 0; i < flag; i++) {
getline(in, str);
int pos;
if((pos = str.find(\".\")) != string::npos) {
sv = split(str, \".\");
}
else {
sv = split(str, \" \");
}
for (int j = 0; j < sv.size(); j++) {
ss << sv[j];
ss >> ass_cost[i*10+j];
_ass_cost.push_back(ass_cost[i*10+j]);
ss.clear();
}
}
fnum = num[0];
cnum = num[1];
in.close();
}
//67号测试文件读取
void get67Data(string path, int &fnum, int &cnum, vector<int> &_capacity, vector<int> &_open_cost, vector<int> &_demand, vector<int> &_ass_cost) {
ifstream in(path);
if (!in.is_open()) {
cout << \"open error!\" << endl;
}
string str;
getline(in, str);
vector<string> sv;
sv = split(str, \" \");
int num[2];
stringstream ss;
for (int i = 0; i < 2; i++) {
ss << sv[i];
ss >> num[i];
ss.clear();
}
//cout << num[0] << \" \" << num[1] << endl;
int capacity[num[0]], open_cost[num[0]];
for (int i = 0; i < num[0]; i++) {
getline(in, str);
sv = split(str, \" \");
ss << sv[0];
ss >> capacity[i];
_capacity.push_back(capacity[i]);
ss.clear();
ss << sv[1];
ss >> open_cost[i];
_open_cost.push_back(open_cost[i]);
ss.clear();
}
int _size = 0;
int demand[num[1]], flag = 40;
for (int i = 0; i < flag; i++) {
getline(in, str);
int pos;
if((pos = str.find(\".\")) != string::npos) {
sv = split(str, \".\");
}
else {
sv = split(str, \" \");
}
for (int j = 0; j < sv.size(); j++) {
ss << sv[j];
ss >> demand[_size];
_demand.push_back(demand[_size]);
_size++;
ss.clear();
}
}
flag = 1200;
int ass_cost[num[0]*num[1]];
_size = 0;
for (int i = 0; i < flag; i++) {
getline(in, str);
int pos;
if((pos = str.find(\".\")) != string::npos) {
sv = split(str, \".\");
}
else {
sv = split(str, \" \");
}
for (int j = 0; j < sv.size(); j++) {
ss << sv[j];
ss >> ass_cost[_size];
_ass_cost.push_back(ass_cost[_size]);
_size++;
ss.clear();
}
}
fnum = num[0];
cnum = num[1];
in.close();
}
//两个结果文件写入
void writeData(string str, int flag) {
if (flag == 0) {
ofstream out(\"result/time.txt\", ios::app);
if (out.is_open()) {
out << str;
out << \"\\n\";
}
out.close();
}
else if (flag == 1) {
ofstream out(\"result/answer.txt\", ios::app);
if (out.is_open()) {
out << str;
out << \"\\n\";
}
out.close();
}
}
#endif
//main.cpp
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
#include <algorithm>
#include <ctime>
#include \"file.h\"
#include <windows.h>
using namespace std;
//设施
struct facility {
int capacity; //设施容量
int remain_capacity; //剩余容量
int open_cost; //开启设施的开销
bool isopen = false; //设施是否打开
};
//客户开销
struct cost{
int cost; //客户开销
int facility; //对应的设施
};
//客户
struct customer {
int demand; //客户对设施容量的需求
vector<cost> cost; //客户开销
int facilityIndex = 0; //客户所选择的设施编号（主要用于输出结果）
};
//核心算法
int greedy(int fnum, int cnum, facility fac[], customer cus[]) {
int min_cost = 0; //最小开销总和
for (int i = 0; i < cnum; i++) { //遍历所有客户
for (int j = 0; j < fnum; j++) { //遍历所有的设施
//找到最小开销的设施编号
int facilityIndex = cus[i].cost[j].facility;
//判断设施容量是否足够
if (fac[facilityIndex].remain_capacity >= cus[i].demand) {
//判断设施是否已经启动
if (!fac[facilityIndex].isopen) {
//未启动则启动设施，并计算启动设施的开销
fac[facilityIndex].isopen = true;
min_cost += fac[facilityIndex].open_cost;
}
//计算开销总和
min_cost += cus[i].cost[j].cost;
//剩余容量减小
fac[facilityIndex].remain_capacity -= cus[i].demand;
cus[i].facilityIndex = facilityIndex;
break; //退出循环
}
}
}
return min_cost;
}
//用于结构体对比排序
bool compare(const cost &a, const cost &b) {
return a.cost < b.cost;
}
//int转string
void intToStr(const int &int_temp,string &string_temp) {
stringstream stream;
stream<<int_temp;
string_temp=stream.str();
}
int main() {
/*string path;
cout << \"please input the file path: \";
cin >> path;
string _path = \"instances/\"+path;*/
int run = 1;
//循环测试71个数据样例
while (run < 72) {
//获取文件路径
stringstream ss;
string temp;
ss << run;
ss >> temp;
ss.clear();
string path = \"instances/p\"+temp;
//获取文件数据
int fnum;
int cnum;
vector<int> capacity;
vector<int> open_cost;
vector<int> demand;
vector<int> ass_cost;
if (run == 67) {
get67Data(path, fnum, cnum, capacity, open_cost, demand, ass_cost);
}
else {
getData(path, fnum, cnum, capacity, open_cost, demand, ass_cost);
}
//计时器
LARGE_INTEGER BegainTime;
LARGE_INTEGER EndTime;
LARGE_INTEGER Frequency;
QueryPerformanceFrequency(&Frequency);
QueryPerformanceCounter(&BegainTime);
//初始化设施
facility fac[fnum];
for (int i = 0; i < fnum; i++) {
fac[i].capacity = capacity[i];
fac[i].remain_capacity =@font-face {
font-family: "autolinktags";
src: url("https://www.seowoai.com/zb_users/plugin/AutoLinkTags/style/fonts/iconfont.woff2") format("woff2"),
url("https://www.seowoai.com/zb_users/plugin/AutoLinkTags/style/fonts/iconfont.woff") format("woff"),
url("https://www.seowoai.com/zb_users/plugin/AutoLinkTags/style/fonts/iconfont.ttf") format("truetype");
font-weight:normal;
font-style:normal;
}.tagslink::after { content:"\e613"; margin:2px 0 0 0px; font-size:12px; font-family:"autolinktags"; display:inline-block; vertical-align:top; } 版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
上一篇：IDEA使用总结 下一篇：vue.js之获取当前点击对象
