66 vector<vector<int> >& dist
69 static const string DIMENSION =
"DIMENSION";
70 static const string DEMAND_SECTION =
"DEMAND_SECTION";
71 static const string DEPOT_SECTION =
"DEPOT_SECTION";
72 static const string EDGE_WEIGHT_TYPE =
"EDGE_WEIGHT_TYPE";
73 static const string EUC_2D =
"EUC_2D";
74 static const string EXPLICIT =
"EXPLICIT";
75 static const string LOWER_DIAG_ROW =
"LOWER_DIAG_ROW";
76 static const string EDGE_WEIGHT_FORMAT =
"EDGE_WEIGHT_FORMAT";
77 static const string EDGE_WEIGHT_SECTION =
"EDGE_WEIGHT_SECTION";
78 static const string NODE_COORD_SECTION =
"NODE_COORD_SECTION";
79 static const string CAPACITY =
"CAPACITY";
81 ifstream file(filename);
85 cerr <<
"Cannot open file " << filename << endl;
89 string edge_weight_type =
"";
90 string edge_weight_format =
"";
103 if ( key == DIMENSION )
108 demand.resize(num_nodes, 0);
109 dist.resize(num_nodes);
110 for (
int i = 0; i < num_nodes; ++i)
111 dist[i].resize(i, 0);
114 if ( key == CAPACITY )
119 else if ( key == EDGE_WEIGHT_TYPE )
122 file >> edge_weight_type;
123 if ( edge_weight_type != EUC_2D && edge_weight_type != EXPLICIT )
125 cerr <<
"Wrong " << EDGE_WEIGHT_TYPE <<
" " << edge_weight_type << endl;
128 if ( edge_weight_type == EUC_2D )
130 x.resize(num_nodes, 0);
131 y.resize(num_nodes, 0);
134 else if ( key == EDGE_WEIGHT_FORMAT )
137 file >> edge_weight_format;
139 else if ( key == EDGE_WEIGHT_FORMAT +
":" )
141 file >> edge_weight_format;
143 else if ( key == EDGE_WEIGHT_SECTION )
145 if ( edge_weight_type != EXPLICIT || edge_weight_format != LOWER_DIAG_ROW )
147 cerr <<
"Error. Unsupported edge length type." << endl;
150 for (
int i = 0; i < num_nodes; ++i)
152 for (
int j = 0; j < i; ++j)
160 else if ( key == NODE_COORD_SECTION )
162 if ( edge_weight_type != EUC_2D )
164 cerr <<
"Error. Data file contains " << EDGE_WEIGHT_TYPE <<
" " << edge_weight_type <<
" and " << NODE_COORD_SECTION << endl;
167 for (
int i = 0; i < num_nodes; ++i)
175 cerr <<
"Error reading " << NODE_COORD_SECTION << endl;
181 for (
int i = 0; i < num_nodes; ++i)
183 for (
int j = 0; j < i; ++j)
185 int dx = x[i] - x[j];
186 int dy = y[i] - y[j];
187 dist[i][j] = int(
sqrt((
double)dx*dx + dy*dy) + 0.5 );
191 else if ( key == DEMAND_SECTION )
193 for (
int i = 0; i < num_nodes; ++i)
200 cerr <<
"Error reading " << DEMAND_SECTION << endl;
206 else if ( key == DEPOT_SECTION )
208 for (
int i = 0; i != -1 ;)
211 if ( i != -1 && i != 1 )
213 cerr <<
"Error: This file specifies other depots than 1." << endl;
220 (void) getline(file, dummy);
234 cout <<
"Solving the vehicle routing problem using SCIP." << endl;
235 cout <<
"Implemented by Andreas Bley." << endl << endl;
237 if ( argc != 2 && argc != 3 )
239 cerr <<
"Usage: vrp [-h] datafile" << endl;
240 cerr <<
"Options:" << endl;
241 cerr <<
" -h Uses hop limit instead of capacity limit for tours."<< endl;
250 static const char* VRP_PRICER_NAME =
"VRP_Pricer";
252 vector<vector<int> > dist;
257 if (
read_problem(argv[argc-1], num_nodes, capacity, demand, dist) )
259 cerr <<
"Error reading data file " << argv[argc-1] << endl;
263 cout <<
"Number of nodes: " << num_nodes << endl;
267 if (
string(
"-h") != argv[1] )
269 cerr <<
"Unknow option " << argv[2] << endl;
273 int total_demand = 0;
274 for (
int i = 1; i< num_nodes; ++i)
275 total_demand += demand[i];
277 if( total_demand == 0.0 )
279 cerr <<
"Total demand is zero!" << endl;
283 capacity = (num_nodes - 1) * capacity / total_demand;
284 demand.assign(num_nodes, 1);
286 cout <<
"Max customers per tour: " << capacity << endl << endl;
289 cout <<
"Max demand per tour: " << capacity << endl << endl;
317 vector< vector<SCIP_VAR*> > arc_var( num_nodes );
318 for (
int i = 0; i < num_nodes; ++i)
321 for (
int j = 0; j < i; ++j)
335 NULL, NULL, NULL, NULL, NULL) );
343 vector< vector<SCIP_CONS*> > arc_con( num_nodes );
344 for (
int i = 0; i < num_nodes; ++i)
347 for (
int j = 0; j < i; ++j)
372 for (
int i = 1; i < num_nodes; ++i)
390 for (
int j = 0; j < num_nodes; ++j)
402 for (
int i = 1; i < num_nodes; ++i)
425 arc_var, arc_con, part_con);
456 for (
int i = 0; i < num_nodes; ++i)
462 for (
int j = 0; j < i; ++j)
477 int main(
int argc,
char** argv)
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
#define BMScheckEmptyMemory()
static SCIP_RETCODE execmain(int argc, char **argv)
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_PRICER * SCIPfindPricer(SCIP *scip, const char *name)
enum SCIP_Retcode SCIP_RETCODE
SCIP_RETCODE SCIPincludeObjPricer(SCIP *scip, scip::ObjPricer *objpricer, SCIP_Bool deleteobject)
SCIP_RETCODE SCIPsolve(SCIP *scip)
SCIP_RETCODE SCIPprintBestSol(SCIP *scip, FILE *file, SCIP_Bool printzeros)
C++ wrapper for default SCIP plugins.
SCIP_RETCODE SCIPcreate(SCIP **scip)
SCIPInterval sqrt(const SCIPInterval &x)
C++ wrapper classes for SCIP.
void SCIPprintVersion(SCIP *scip, FILE *file)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
int main(int argc, char **argv)
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_RETCODE SCIPcreateProb(SCIP *scip, const char *name, SCIP_DECL_PROBDELORIG((*probdelorig)), SCIP_DECL_PROBTRANS((*probtrans)), SCIP_DECL_PROBDELTRANS((*probdeltrans)), SCIP_DECL_PROBINITSOL((*probinitsol)), SCIP_DECL_PROBEXITSOL((*probexitsol)), SCIP_DECL_PROBCOPY((*probcopy)), SCIP_PROBDATA *probdata)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
static int read_problem(const char *filename, int &num_nodes, int &capacity, vector< int > &demand, vector< vector< int > > &dist)
int SCIPsnprintf(char *t, int len, const char *s,...)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_RETCODE SCIPactivatePricer(SCIP *scip, SCIP_PRICER *pricer)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPfree(SCIP **scip)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)