VRPH
1.0
|
00001 00002 // // 00003 // This file is part of the VRPH software package for // 00004 // generating solutions to vehicle routing problems. // 00005 // VRPH was developed by Chris Groer (cgroer@gmail.com). // 00006 // // 00007 // (c) Copyright 2010 Chris Groer. // 00008 // All Rights Reserved. VRPH is licensed under the // 00009 // Common Public License. See LICENSE file for details. // 00010 // // 00012 00013 #include "VRPH.h" 00014 00015 void VRP::read_TSPLIB_file(const char *node_file) 00016 { 00023 00024 00025 char *temp; 00026 char line[VRPH_STRING_SIZE]; 00027 char *temp2; 00028 int max_id = -VRP_INFINITY; 00029 00030 int ans; 00031 int x,y,i,j; 00032 float a, b; 00033 double s; 00034 00035 bool has_depot=false; 00036 bool has_nodes=false; 00037 00038 FILE *infile; 00039 00040 infile = fopen(node_file, "r"); 00041 00042 if (infile==NULL) 00043 report_error("%s: file error\n",__FUNCTION__); 00044 00045 00046 this->edge_weight_format=-1; 00047 this->edge_weight_type=-1; 00048 00049 for(;;) 00050 { 00051 fgets(line, 100, infile); 00052 00053 #if TSPLIB_DEBUG 00054 printf("Next line is %s\n",line); 00055 #endif 00056 00057 temp=strtok(line,":"); 00058 00059 00060 00061 #if TSPLIB_DEBUG 00062 printf("line begins with %s\n",temp); 00063 #endif 00064 00065 if( (ans=VRPCheckTSPLIBString(temp))<=0 ) 00066 { 00067 if(ans==0) 00068 fprintf(stderr,"Unknown string %s found\n",temp); 00069 else 00070 fprintf(stderr,"TSPLIB string %s not supported\n",temp); 00071 00072 report_error("%s\n",__FUNCTION__); 00073 } 00074 00075 #if TSPLIB_DEBUG 00076 printf("ans is %d\n",ans); 00077 #endif 00078 00079 // Otherwise, we know the string - process it accordingly 00080 switch(ans) 00081 { 00082 case 1: 00083 // NAME 00084 00085 temp2=strtok(NULL," "); 00086 strcpy(name,temp2); 00087 // Trim the ANNOYING \n if necessary... 00088 for(i=0;i<(int)strlen(name);i++) 00089 { 00090 if(name[i]=='\n' || name[i]=='\r') 00091 { 00092 name[i]=0x00; 00093 break; 00094 } 00095 } 00096 00097 00098 00099 #if TSPLIB_DEBUG 00100 printf("Name is %s\n",name); 00101 #endif 00102 break; 00103 00104 case 2: 00105 // TYPE 00106 temp2=strtok(NULL," "); 00107 00108 #if TSPLIB_DEBUG 00109 printf("Problem type is\n%s\n",temp2); 00110 #endif 00111 if( (strncmp(temp2,"TSP",3)!= 0) && (strncmp(temp2,"CVRP",4)!=0) 00112 && (strncmp(temp2,"DCVRP",5)!=0) ) 00113 { 00114 fprintf(stderr,"Unknown type %s encountered\n",temp2); 00115 report_error("%s\n",__FUNCTION__); 00116 } 00117 00118 if( strncmp(temp2,"TSP",3)== 0) 00119 problem_type=VRPH_TSP; 00120 if(strncmp(temp2,"CVRP",4)==0 || (strncmp(temp2,"DCVRP",5)!=0) ) 00121 problem_type=VRPH_CVRP; 00122 00123 break; 00124 00125 00126 case 3: 00127 // BEST_KNOWN 00128 temp2=strtok(NULL,""); 00129 this->best_known=atof(temp2); 00130 break; 00131 case 4: 00132 // DIMENSION 00133 num_nodes=atoi(strtok(NULL,"")); 00134 num_nodes--; 00135 matrix_size= num_nodes; 00136 // num_nodes is the # of non-VRPH_DEPOT nodes 00137 // The value of DIMENSION includes the VRPH_DEPOT! 00138 dummy_index = 1+num_nodes; 00139 00140 break; 00141 00142 case 5: 00143 // CAPACITY 00144 max_veh_capacity=atoi(strtok(NULL,"")); 00145 orig_max_veh_capacity=max_veh_capacity; 00146 00147 #if TSPLIB_DEBUG 00148 printf("veh capacity is %d\n",max_veh_capacity); 00149 #endif 00150 break; 00151 case 6: 00152 // DISTANCE 00153 max_route_length=(double)atof(strtok(NULL,"")); 00154 orig_max_route_length=max_route_length; 00155 00156 #if TSPLIB_DEBUG 00157 printf("max length is %f\n",max_route_length); 00158 #endif 00159 break; 00160 case 7: 00161 // EDGE_WEIGHT_FORMAT - sets edge_weight_format 00162 temp2=strtok(NULL," "); 00163 edge_weight_format=-1; 00164 00165 if(strncmp(temp2,"UPPER_ROW",9)==0) 00166 { 00167 edge_weight_format=VRPH_UPPER_ROW; 00168 } 00169 00170 if(strncmp(temp2,"FULL_MATRIX",11)==0) 00171 { 00172 edge_weight_format=VRPH_FULL_MATRIX; 00173 } 00174 00175 if(strncmp(temp2,"FUNCTION",8)==0) 00176 { 00177 edge_weight_format=VRPH_FUNCTION; 00178 00179 } 00180 if(strncmp(temp2,"LOWER_ROW",9)==0) 00181 { 00182 edge_weight_format=VRPH_LOWER_ROW; 00183 00184 } 00185 if(strncmp(temp2,"UPPER_DIAG_ROW",14)==0) 00186 { 00187 edge_weight_format=VRPH_UPPER_DIAG_ROW; 00188 00189 } 00190 if(strncmp(temp2,"LOWER_DIAG_ROW",14)==0) 00191 { 00192 edge_weight_format=VRPH_LOWER_DIAG_ROW; 00193 00194 } 00195 00196 if(edge_weight_format == -1) 00197 { 00198 // We didn't find a known type 00199 fprintf(stderr,"Unknown/Unsupported EDGE_WEIGHT_FORMAT %s encountered\n",temp2); 00200 report_error("%s\n",__FUNCTION__); 00201 } 00202 break; 00203 case 8: 00204 // EDGE_WEIGHT_TYPE 00205 edge_weight_type = -1; 00206 temp2=strtok(NULL," "); 00207 00208 00209 #if TSPLIB_DEBUG 00210 printf("Weight type is %s\n",temp2); 00211 #endif 00212 00213 // Determine the type of weight format 00214 if(strncmp(temp2,"EXPLICIT",8)==0) 00215 { 00216 edge_weight_type=VRPH_EXPLICIT; 00217 } 00218 00219 if(strncmp(temp2,"EUC_2D",6)==0) 00220 { 00221 edge_weight_type=VRPH_EUC_2D; 00222 } 00223 00224 if(strncmp(temp2,"EUC_3D",6)==0) 00225 { 00226 edge_weight_type=VRPH_EUC_3D; 00227 00228 } 00229 00230 if(strncmp(temp2,"MAX_2D",6)==0) 00231 { 00232 edge_weight_type=VRPH_MAX_2D; 00233 00234 } 00235 00236 if(strncmp(temp2,"MAX_3D",6)==0) 00237 { 00238 edge_weight_type=VRPH_MAX_3D; 00239 00240 } 00241 00242 if(strncmp(temp2,"MAN_2D",6)==0) 00243 { 00244 edge_weight_type=VRPH_MAN_2D; 00245 00246 } 00247 00248 if(strncmp(temp2,"MAN_3D",6)==0) 00249 { 00250 edge_weight_type=VRPH_MAN_3D; 00251 00252 } 00253 00254 if(strncmp(temp2,"MAN_3D",6)==0) 00255 { 00256 edge_weight_type=VRPH_MAN_3D; 00257 00258 } 00259 00260 if(strncmp(temp2,"CEIL_2D",7)==0) 00261 { 00262 edge_weight_type=VRPH_CEIL_2D; 00263 } 00264 00265 if(strncmp(temp2,"GEO",3)==0) 00266 { 00267 edge_weight_type=VRPH_GEO; 00268 00269 } 00270 00271 if(strncmp(temp2,"EXACT_2D",8)==0) 00272 { 00273 edge_weight_type=VRPH_EXACT_2D; 00274 00275 } 00276 00277 if(edge_weight_type == -1) 00278 { 00279 // We didn't find a known type 00280 fprintf(stderr,"Unknown/Unsupported EDGE_WEIGHT_TYPE %s encountered\n",temp2); 00281 report_error("%s\n",__FUNCTION__); 00282 } 00283 00284 break; 00285 case 9: 00286 // NODE_COORD_TYPE - we don't really care about this one 00287 temp2=strtok(NULL," "); 00288 if( (strncmp(temp2,"TWOD_COORDS",11)!=0) && (strncmp(temp2,"THREED_COORDS",13)!=0) ) 00289 { 00290 fprintf(stderr,"Unknown coordinate type %s encountered",temp2); 00291 report_error("%s\n",__FUNCTION__); 00292 } 00293 00294 break; 00295 case 10: 00296 // EOF - clean up and exit 00297 fclose(infile); 00298 00299 #if TSPLIB_DEBUG 00300 fprintf(stderr,"Found EOF completing calculations...\n"); 00301 #endif 00302 00303 this->max_theta= -VRP_INFINITY; 00304 this->min_theta= VRP_INFINITY; 00305 00306 // Now normalize everything to put the VRPH_DEPOT at the origin 00307 // if it is a standard EXACT_2D problem or EUC_2D problem 00308 if( (this->edge_weight_type==VRPH_EXACT_2D || this->edge_weight_type==VRPH_EUC_2D) && has_nodes && has_depot && true) 00309 { 00310 00311 this->depot_normalized=true; 00312 double depot_x=nodes[0].x; 00313 double depot_y=nodes[0].y; 00314 00315 #if TSPLIB_DEBUG 00316 fprintf(stderr,"Normalizing...(%f,%f)\n",depot_x,depot_y); 00317 #endif 00318 00319 for(i=0;i<=this->num_nodes+1;i++) 00320 { 00321 nodes[i].x -= depot_x; 00322 nodes[i].y -= depot_y; 00323 // Translate everyone 00324 00325 // Calculate the polar coordinates as well 00326 if(nodes[i].x==0 && nodes[i].y==0) 00327 { 00328 nodes[i].r=0; 00329 nodes[i].theta=0; 00330 } 00331 else 00332 { 00333 00334 nodes[i].r=sqrt( ((nodes[i].x)*(nodes[i].x)) + ((nodes[i].y)*(nodes[i].y)) ); 00335 nodes[i].theta=atan2(nodes[i].y,nodes[i].x); 00336 // We want theta in [0 , 2pi] 00337 // If y<0, add 2pi 00338 if(nodes[i].y<0) 00339 nodes[i].theta+=2*VRPH_PI; 00340 } 00341 00342 // Update min/max theta across all nodes - don't include the VRPH_DEPOT/dummy 00343 if(i!=0 && i!=(this->num_nodes+1)) 00344 { 00345 if(nodes[i].theta>this->max_theta) 00346 max_theta=nodes[i].theta; 00347 if(nodes[i].theta<this->min_theta) 00348 min_theta=nodes[i].theta; 00349 } 00350 00351 } 00352 } 00353 00354 #if TSPLIB_DEBUG 00355 fprintf(stderr,"Creating neighbor lists...\n"); 00356 #endif 00357 00358 // Create the neighbor_lists-we may use a smaller size depending on the parameter 00359 // but we will construct the largest possible here... 00360 this->create_neighbor_lists(VRPH_MIN(MAX_NEIGHBORLIST_SIZE,num_nodes)); 00361 00362 #if TSPLIB_DEBUG 00363 fprintf(stderr,"Done w/ calculations...\n"); 00364 #endif 00365 return; 00366 00367 case 11: 00368 // NODE_COORD_SECTION 00369 // Import the data 00370 this->can_display=true; 00371 00372 #if TSPLIB_DEBUG 00373 printf("num_nodes is %d\n",num_nodes); 00374 #endif 00375 00376 i=0; 00377 x=0; 00378 while(i<=num_nodes) 00379 { 00380 fscanf(infile,"%d",&x); 00381 fscanf(infile,"%f",&a); 00382 fscanf(infile,"%f\n",&b); 00383 00384 nodes[i].id= x; 00385 00386 nodes[i].x=(double) a; 00387 nodes[i].y=(double) b; 00388 00389 00390 i++; 00391 00392 } 00393 has_nodes=true; 00394 00395 break; 00396 00397 case 12: 00398 // DEPOT_SECTION 00399 // Load in the Depot Coordinates 00400 fscanf(infile,"%d\n",&x); 00401 if(x!=1) 00402 { 00403 fprintf(stderr,"Expected VRPH_DEPOT to be entry 1 - VRPH does not currently support" 00404 " multiple DEPOTs\n"); 00405 report_error("%s\n",__FUNCTION__); 00406 } 00407 00408 #if TSPLIB_DEBUG 00409 printf("VRPH_DEPOT has coordinates: %f, %f\n",a,b); 00410 #endif 00411 //nodes[0].x=a; 00412 //nodes[0].y=b; 00413 //nodes[0].id=0; 00414 00415 has_depot=true; 00416 fscanf(infile,"%d\n",&x); 00417 if(x!= -1) 00418 { 00419 fprintf(stderr, "Expected -1 at end of DEPOT_SECTION. Encountered %d instead\n",x); 00420 report_error("%s\n",__FUNCTION__); 00421 } 00422 00423 // Now set the dummy node id to the VRPH_DEPOT! 00424 nodes[num_nodes+1].x=nodes[0].x; 00425 nodes[num_nodes+1].y=nodes[0].y; 00426 nodes[num_nodes+1].id=0; 00427 00428 // Now calculate distance matrix 00429 if(edge_weight_format==VRPH_FUNCTION || edge_weight_type!=VRPH_EXPLICIT) 00430 { 00431 00432 #if TSPLIB_DEBUG 00433 printf("Creating distance matrix using edge_weight_type %d\n",edge_weight_type); 00434 #endif 00435 00436 //Allocate memory for the distance matrix 00437 if(d==NULL) 00438 { 00439 int n= num_nodes; 00440 00441 d = new double* [n+2]; 00442 d[0] = new double [(n+2)*(n+2)]; 00443 for(i = 1; i < n+2; i++) 00444 d[i] = d[i-1] + (n+2) ; 00445 } 00446 00447 00448 00449 // Create the distance matrix using the appropriate 00450 // distance function... 00451 create_distance_matrix(edge_weight_type); 00452 } 00453 00454 break; 00455 case 13: 00456 00457 #if TSPLIB_DEBUG 00458 printf("in case 13: DEMAND_SECTION w/ problem type %d # num_days=%d\n",problem_type, 00459 this->num_days); 00460 #endif 00461 // DEMAND_SECTION 00462 // Read in the demands 00463 00464 if(this->num_days<=1) 00465 { 00466 i=0; 00467 while(i<= num_nodes+1) 00468 { 00469 00470 fscanf(infile,"%d %d\n",&x,&y); 00471 nodes[i].id=x; 00472 nodes[i].demand=y; 00473 00474 if(nodes[i].id>max_id) 00475 max_id=nodes[i].id; 00476 00477 if(has_service_times==false) 00478 nodes[i].service_time=0; 00479 i++; 00480 } 00481 nodes[num_nodes+1].demand=0; 00482 if(has_service_times==false) 00483 nodes[num_nodes+1].service_time=0; 00484 00485 } 00486 else 00487 { 00488 // We have multiple days worth of demands 00489 i=0; 00490 while(i<=num_nodes+1) 00491 { 00492 fscanf(infile,"%d",&x); 00493 nodes[i].id=x; 00494 for(j=1;j<this->num_days;j++) 00495 { 00496 fscanf(infile,"%d",&y); 00497 this->nodes[i].daily_demands[j]=y; 00498 00499 } 00500 fscanf(infile,"%d\n",&y); 00501 this->nodes[i].daily_demands[this->num_days]=y; 00502 i++; 00503 00504 } 00505 this->nodes[num_nodes+1].demand=0; 00506 for(j=1;j<=this->num_days;j++) 00507 this->nodes[num_nodes+1].daily_demands[j]=0;// Dummmy node 00508 00509 #if TSPLIB_DEBUG 00510 printf("Done with multiple day demands\n"); 00511 #endif 00512 } 00513 00514 00515 break; 00516 00517 case 14: 00518 00519 #if TSPLIB_DEBUG 00520 printf("Case 14\n"); 00521 #endif 00522 00523 // EDGE_WEIGHT_SECTION 00524 00525 // Make sure distance matrix is allocated 00526 if(d==NULL) 00527 { 00528 d = new double* [num_nodes+2]; 00529 d[0] = new double [(num_nodes+2)*(num_nodes+2)]; 00530 for(i = 1; i < num_nodes+2; i++) 00531 d[i] = d[i-1] + (num_nodes+2) ; 00532 } 00533 00534 if(edge_weight_format==VRPH_UPPER_DIAG_ROW) 00535 { 00536 // The zeros on the diagonal should be in the matrix! 00537 for(i=0;i<= num_nodes;i++) 00538 { 00539 for(j=i;j<= num_nodes;j++) 00540 { 00541 fscanf(infile,"%lf",&(d[i][j])); 00542 d[j][i]=d[i][j]; 00543 } 00544 // Add in column for the dummy-assumed to live at the VRPH_DEPOT 00545 d[i][num_nodes+1]=d[i][0]; 00546 } 00547 // Now add a row for the dummy 00548 for(j=0;j<=num_nodes+1;j++) 00549 d[num_nodes+1][j]=d[0][j]; 00550 00551 } 00552 00553 if(edge_weight_format==VRPH_FULL_MATRIX) 00554 { 00555 this->symmetric=false; 00556 00557 for(i=0;i<= num_nodes;i++) 00558 { 00559 for(j=0;j<= num_nodes;j++) 00560 { 00561 fscanf(infile,"%lf",&(d[i][j])); 00562 } 00563 // Add in column for the dummy-assumed to live at the VRPH_DEPOT 00564 d[i][num_nodes+1]=d[i][0]; 00565 00566 } 00567 // Now add a row for the dummy 00568 for(j=0;j<=num_nodes+1;j++) 00569 d[num_nodes+1][j]=d[0][j]; 00570 00571 } 00572 00573 // LOWER_DIAG_ROW format 00574 if(edge_weight_format==VRPH_LOWER_DIAG_ROW) 00575 { 00576 // The zeros on the diagonal should be in the matrix! 00577 for(i=0;i<= num_nodes;i++) 00578 { 00579 for(j=0;j<= i;j++) 00580 { 00581 fscanf(infile,"%lf",&(d[i][j])); 00582 d[j][i]=d[i][j]; 00583 } 00584 // Add in column for the dummy-assumed to live at the VRPH_DEPOT 00585 d[i][num_nodes+1]=d[i][0]; 00586 00587 } 00588 // Now add a row for the dummy 00589 for(j=0;j<=num_nodes+1;j++) 00590 d[num_nodes+1][j]=d[0][j]; 00591 00592 } 00593 00594 // UPPER_ROW format - no diagonal 00595 if(edge_weight_format==VRPH_UPPER_ROW) 00596 { 00597 for(i=0;i<=num_nodes;i++) 00598 { 00599 for(j=i+1;j<= num_nodes;j++) 00600 { 00601 fscanf(infile,"%lf",&(d[i][j])); 00602 d[j][i]=d[i][j]; 00603 } 00604 // Add in column for the dummy-assumed to live at the VRPH_DEPOT 00605 d[i][num_nodes+1]=d[i][0]; 00606 d[i][i]=0; 00607 00608 } 00609 // Now add a row for the dummy 00610 for(j=0;j<=num_nodes+1;j++) 00611 d[num_nodes+1][j]=d[0][j]; 00612 00613 } 00614 00615 // LOWER_ROW format 00616 if(edge_weight_format==VRPH_LOWER_ROW) 00617 { 00618 for(i=0;i<= num_nodes;i++) 00619 { 00620 for(j=0;j<i;j++) 00621 { 00622 fscanf(infile,"%lf",&(d[i][j])); 00623 d[j][i]=d[i][j]; 00624 } 00625 d[i][i]=0; 00626 // Add in column for the dummy-assumed to live at the VRPH_DEPOT 00627 d[i][num_nodes+1]=d[i][0]; 00628 00629 } 00630 // Now add a row for the dummy 00631 for(j=0;j<=num_nodes+1;j++) 00632 d[num_nodes+1][j]=d[0][j]; 00633 } 00634 00635 // The last fscanf doesn't get the newline... 00636 fscanf(infile,"\n"); 00637 break; 00638 00639 case 15: 00640 00641 #if TSPLIB_DEBUG 00642 printf("Case 15\n"); 00643 #endif 00644 00645 // SERVICE_TIME 00646 00647 s =(double)(atof(strtok(NULL,""))); 00648 fixed_service_time=s; 00649 #if TSPLIB_DEBUG 00650 printf("Setting service time to %f for all nodes\n"); 00651 #endif 00652 total_service_time=0; 00653 for(i=1;i<=num_nodes;i++) 00654 { 00655 // Set the service time to s for each non-depot node 00656 nodes[i].service_time=s;//+lcgrand(0) - use to test service times! 00657 total_service_time+=nodes[i].service_time; 00658 } 00659 nodes[VRPH_DEPOT].service_time=0; 00660 nodes[num_nodes+1].service_time=0; 00661 00662 has_service_times=true; 00663 00664 break; 00665 00666 case 16: 00667 00668 #if TSPLIB_DEBUG 00669 printf("Case 16\n"); 00670 #endif 00671 00672 // VEHICLES 00673 00674 min_vehicles=atoi(strtok(NULL,"")); 00675 // This is not currently used 00676 #if TSPLIB_DEBUG 00677 printf("Setting min_vehicles to %d\n",min_vehicles); 00678 00679 #endif 00680 break; 00681 00682 case 17: 00683 00684 // NUM_DAYS 00685 this->num_days=atoi(strtok(NULL,"")); 00686 break; 00687 00688 case 18: 00689 // SVC_TIME_SECTION 00690 has_service_times=true; 00691 00692 if(this->num_days<=1)// 8/15/2010 - used to be ==0 ! 00693 { 00694 i=0; 00695 while(i<= num_nodes) 00696 { 00697 00698 fscanf(infile,"%d %lf\n",&x,&s); 00699 nodes[i].id=x; 00700 nodes[i].service_time=s; 00701 total_service_time+=nodes[i].service_time; 00702 00703 if(nodes[i].id>max_id) 00704 max_id=nodes[i].id; 00705 i++; 00706 } 00707 nodes[num_nodes+1].service_time=0; 00708 00709 00710 } 00711 else 00712 { 00713 // We have multiple days worth of service times 00714 i=0; 00715 while(i<=num_nodes) 00716 { 00717 fscanf(infile,"%d",&x); 00718 nodes[i].id=x; 00719 for(j=1;j<this->num_days;j++) 00720 { 00721 fscanf(infile,"%lf",&s); 00722 this->nodes[i].daily_service_times[j]=s; 00723 } 00724 fscanf(infile,"%lf\n",&s); 00725 this->nodes[i].daily_service_times[this->num_days]=s; 00726 i++; 00727 00728 } 00729 this->nodes[num_nodes+1].service_time=0; 00730 for(j=1;j<=this->num_days;j++) 00731 this->nodes[num_nodes+1].daily_service_times[j]=0;// Dummmy node 00732 00733 } 00734 00735 00736 break; 00737 case 19: 00738 // TIME_WINDOW_SECTION 00739 i=0; 00740 while(i<= num_nodes+1) 00741 { 00742 fscanf(infile,"%d %f %f\n",&x,&a,&b); 00743 nodes[i].start_tw=a; 00744 nodes[i].end_tw=b; 00745 i++; 00746 } 00747 00748 break; 00749 case 20: 00750 // COMMENT 00751 // Don't care 00752 break; 00753 case 21: 00754 // DISPLAY_DATA_SECTION 00755 // Overwrite node's x and y coords with this data 00756 00757 this->can_display=true; 00758 i=0; 00759 x=0; 00760 while(i<=num_nodes) 00761 { 00762 fscanf(infile,"%d",&x); 00763 fscanf(infile,"%f",&a); 00764 fscanf(infile,"%f\n",&b); 00765 00766 nodes[x-1].x=(double) a; 00767 nodes[x-1].y=(double) b; 00768 i++; 00769 00770 } 00771 00772 break; 00773 case 22: 00774 // TWOD_DISPLAY 00775 break; 00776 case 23: 00777 // DISPLAY_DATA_TYPE 00778 00779 break; 00780 case 24: 00781 // NO_DISPLAY 00782 break; 00783 case 25: 00784 // COORD_DISPLAY 00785 break; 00786 } 00787 } 00788 00789 } 00790 00791 00792 void VRP::write_TSPLIB_file(const char *outfile) 00793 { 00798 00799 FILE *out; 00800 int i; 00801 00802 if( (out=fopen(outfile,"w"))==NULL) 00803 { 00804 report_error("%s: Can't open file for writing...\n",__FUNCTION__); 00805 } 00806 00807 fprintf(out,"NAME: %s\n",name); 00808 fprintf(out,"TYPE: CVRP\n"); 00809 if(this->best_known!=-1) 00810 fprintf(out,"BEST_KNOWN: %5.3f\n", this->best_known); 00811 fprintf(out,"DIMENSION: %d\n",num_nodes+1); 00812 fprintf(out,"CAPACITY: %d\n",max_veh_capacity); 00813 if(max_route_length!=VRP_INFINITY) 00814 fprintf(out,"DISTANCE: %4.5f\n",max_route_length); 00815 if(min_vehicles!=-1) 00816 fprintf(out,"VEHICLES: %d\n",min_vehicles); 00817 fprintf(out,"EDGE_WEIGHT_TYPE: FUNCTION\n"); 00818 fprintf(out,"EDGE_WEIGHT_FORMAT: EXACT_2D\n"); 00819 fprintf(out,"NODE_COORD_TYPE: TWOD_COORDS\n"); 00820 fprintf(out,"NODE_COORD_SECTION\n"); 00821 00822 // Start numbering at 1!! 00823 fprintf(out,"%d %4.5f %4.5f\n",1,nodes[0].x,nodes[0].y); 00824 for(i=1;i<=num_nodes;i++) 00825 { 00826 fprintf(out,"%d %4.5f %4.5f\n",i+1,nodes[i].x,nodes[i].y); 00827 } 00828 00829 fprintf(out,"DEMAND_SECTION\n"); 00830 // Start numbering at 1!! 00831 fprintf(out,"1 0\n"); 00832 for(i=1;i<=num_nodes;i++) 00833 { 00834 fprintf(out,"%d %d\n",i+1,nodes[i].demand); 00835 } 00836 00837 fprintf(out,"DEPOT_SECTION\n"); 00838 fprintf(out,"1\n-1\n"); 00839 00840 fprintf(out,"EOF\n"); 00841 00842 fclose(out); 00843 00844 } 00845 00846 00847 00848 void VRP::write_solution_file(const char *filename) 00849 { 00862 00863 00864 00865 int n, current; 00866 FILE *out; 00867 00868 int *sol; 00869 00870 // Open the file 00871 if( (out = fopen(filename,"w"))==NULL) 00872 { 00873 fprintf(stderr,"Error opening %s for writing\n",filename); 00874 report_error("%s\n",__FUNCTION__); 00875 } 00876 00877 // First, determine the # of nodes in the Solution -- this could be different than the 00878 // VRP.num_nodes value if we are solving a subproblem 00879 00880 n=0; 00881 current=VRPH_ABS(next_array[VRPH_DEPOT]); 00882 while(current!=VRPH_DEPOT) 00883 { 00884 current=VRPH_ABS(next_array[current]); 00885 n++; 00886 } 00887 // We have n non-VRPH_DEPOT nodes in the problem 00888 sol=new int[n+2]; 00889 // Canonicalize 00890 this->export_canonical_solution_buff(sol); 00891 this->import_solution_buff(sol); 00892 fprintf(out,"%d ",n); 00893 00894 00895 // Now output the ordering - this is actually just the sol buffer 00896 current=next_array[VRPH_DEPOT]; 00897 fprintf(out,"%d ",current); 00898 while(current!=VRPH_DEPOT) 00899 { 00900 current=next_array[VRPH_ABS(current)]; 00901 fprintf(out,"%d ",current); 00902 00903 } 00904 00905 fprintf(out,"\n\n\n"); 00906 00907 00908 fflush(out); 00909 fprintf(out,"\n\n\nOBJ=\n%5.3f\nBEST_KNOWN=\n%5.3f",this->total_route_length-this->total_service_time, 00910 this->best_known); 00911 00912 fflush(out); 00913 fclose(out); 00914 00915 delete [] sol; 00916 return; 00917 } 00918 00919 void VRP::write_solutions(int num_sols, const char *filename) 00920 { 00925 00926 int i,n, current; 00927 FILE *out; 00928 int *sol; 00929 00930 sol=new int[this->num_original_nodes+2]; // should be big enough 00931 00932 // Open the file 00933 if( (out = fopen(filename,"w"))==NULL) 00934 { 00935 fprintf(stderr,"Error opening %s for writing\n",filename); 00936 report_error("%s\n",__FUNCTION__); 00937 } 00938 00939 for(i=0;i<num_sols;i++) 00940 { 00941 if(i>this->solution_wh->num_sols) 00942 report_error("%s: too many solutions!\n",__FUNCTION__); 00943 00944 // Import this solution and then write it out 00945 this->import_solution_buff(this->solution_wh->sols[i].sol); 00946 this->export_canonical_solution_buff(sol); 00947 this->import_solution_buff(sol); 00948 00949 00950 // First, determine the # of nodes in the Solution -- this could be different than the 00951 // VRP.num_nodes value if we are solving a subproblem 00952 00953 n=0; 00954 current=VRPH_ABS(next_array[VRPH_DEPOT]); 00955 while(current!=VRPH_DEPOT) 00956 { 00957 current=VRPH_ABS(next_array[current]); 00958 n++; 00959 } 00960 // We have n non-VRPH_DEPOT nodes in the problem 00961 fprintf(out,"%d ",n); 00962 00963 // Now output the ordering 00964 current=next_array[VRPH_DEPOT]; 00965 fprintf(out,"%d ",current); 00966 while(current!=VRPH_DEPOT) 00967 { 00968 current=next_array[VRPH_ABS(current)]; 00969 fprintf(out,"%d ",current); 00970 00971 } 00972 fprintf(out,"\n"); 00973 } 00974 00975 fflush(out); 00976 fclose(out); 00977 return; 00978 00979 } 00980 00981 00982 void VRP::write_tex_file(const char *filename) 00983 { 00989 00990 int i; 00991 00992 FILE *out; 00993 if( (out=fopen(filename,"w"))==NULL) 00994 { 00995 fprintf(stderr,"Error opening %s for writing\n",filename); 00996 report_error("%s\n",__FUNCTION__); 00997 00998 } 00999 01000 // The headers for the first page and pages thereafter 01001 fprintf(out,"%% TeX file automatically generated by VRPH for problem %s\n\n",this->name); 01002 fprintf(out,"\\renewcommand{\\baselinestretch}{1}\n"); 01003 fprintf(out,"\\footnotesize\n"); 01004 fprintf(out,"\\begin{center}\n"); 01005 fprintf(out,"\\begin{longtable}{|c|r|r|p{4 in}|}\n"); 01006 01007 fprintf(out,"\\hline\n"); 01008 fprintf(out,"Route&\\multicolumn{1}{c|}{Length}&\\multicolumn{1}{c|}{Load}&\\multicolumn{1}{c|}{Ordering}\\\\\n"); 01009 fprintf(out,"\\hline\n"); 01010 fprintf(out,"\\endhead\n"); 01011 fprintf(out,"\\hline\n"); 01012 fprintf(out,"\\multicolumn{3}{|l|}{Problem}&%s\\\\\n",this->name); 01013 fprintf(out,"\\hline\n"); 01014 fprintf(out,"\\endfirsthead\n"); 01015 fprintf(out,"\\endfoot\n"); 01016 fprintf(out,"\\endlastfoot\n"); 01017 fprintf(out,"\\multicolumn{3}{|l|}{Vehicle capacity}&%d\\\\\n",this->max_veh_capacity); 01018 if(this->max_route_length!=VRP_INFINITY) 01019 fprintf(out,"\\multicolumn{3}{|l|}{Maximum route length}&%5.3f\\\\\n",this->max_route_length); 01020 else 01021 fprintf(out,"\\multicolumn{3}{|l|}{Maximum route length}&N/A\\\\\n"); 01022 if(this->total_service_time>0) 01023 fprintf(out,"\\multicolumn{3}{|l|}{Total service time}&%5.3f\\\\\n",this->total_service_time); 01024 fprintf(out,"\\multicolumn{3}{|l|}{Number of nodes}&%d\\\\\n",this->num_nodes); 01025 fprintf(out,"\\multicolumn{3}{|l|}{Total route length}&%5.3f\\\\\n",this->total_route_length- 01026 this->total_service_time); 01027 fprintf(out,"\\multicolumn{3}{|l|}{Total number of routes}&%d\\\\\n",this->total_number_of_routes); 01028 fprintf(out,"\\hline\n"); 01029 fprintf(out,"Route&\\multicolumn{1}{c|}{Length}&\\multicolumn{1}{c|}{Load}&\\multicolumn{1}{c|}{Ordering}\\\\\n"); 01030 fprintf(out,"\\hline\n"); 01031 01032 for(i=1;i<=this->total_number_of_routes;i++) 01033 { 01034 fprintf(out,"%d&%5.3f&%d&(0",i,this->route[i].length,this->route[i].load); 01035 int current=this->route[i].start; 01036 while(current>=0) 01037 { 01038 fprintf(out,", %d",current); 01039 current=this->next_array[current]; 01040 01041 } 01042 fprintf(out,", 0)\\\\\n"); 01043 fprintf(out,"\\hline\n"); 01044 } 01045 fprintf(out,"\\caption{The best solution found for problem %s}\n",this->name); 01046 fprintf(out,"\\end{longtable}\n"); 01047 fprintf(out,"\\end{center}\n"); 01048 fprintf(out,"\\renewcommand{\\baselinestretch}{2}\n"); 01049 fprintf(out,"\\normalsize\n"); 01050 fclose(out); 01051 } 01052 01053 01054 void VRP::read_solution_file(const char *filename) 01055 { 01060 01061 FILE *in; 01062 01063 if( (in=fopen(filename,"r"))==NULL) 01064 { 01065 fprintf(stderr,"Error opening %s for reading\n",filename); 01066 report_error("%s\n",__FUNCTION__); 01067 } 01068 01069 int *new_sol; 01070 int i,n; 01071 fscanf(in,"%d",&n); 01072 new_sol=new int[n+2]; 01073 new_sol[0]=n; 01074 for(i=1;i<=n+1;i++) 01075 fscanf(in,"%d",new_sol+i); 01076 01077 // Import the buffer 01078 this->import_solution_buff(new_sol); 01079 fclose(in); 01080 delete [] new_sol; 01081 01082 this->verify_routes("After read_solution_file\n"); 01083 01084 memcpy(this->best_sol_buff,this->current_sol_buff,(this->num_nodes+2)*sizeof(int)); 01085 01086 return; 01087 01088 } 01089 01090 01091 01092 void VRP::import_solution_buff(int *sol_buff) 01093 { 01099 01100 01101 int i, n, rnum, current, next, load, num_in_route; 01102 double len; 01103 01104 next=-1; //to avoid warning... 01105 01106 // Set all nodes to unrouted 01107 for(i=1;i<=this->num_original_nodes;i++) 01108 routed[i]=false; 01109 01110 len=0; 01111 load=0; 01112 01113 total_route_length=0; 01114 01115 this->num_nodes = sol_buff[0]; 01116 01117 n=this->num_nodes; 01118 num_in_route=0; 01119 01120 rnum=1; 01121 01122 current=VRPH_ABS(sol_buff[1]); 01123 routed[current]=true; 01124 next_array[VRPH_DEPOT]=sol_buff[1]; 01125 route_num[VRPH_ABS(current)]=rnum; 01126 route[rnum].start=VRPH_ABS(current); 01127 load+=nodes[VRPH_ABS(current)].demand; 01128 len+=d[VRPH_DEPOT][VRPH_ABS(current)]; 01129 num_in_route++; 01130 01131 for(i=2;i<=n;i++) 01132 { 01133 next=sol_buff[i]; 01134 routed[VRPH_ABS(next)]=true; 01135 01136 if(next<0) 01137 { 01138 // end of route - current is the last node in this route 01139 // next is the first node in the next route 01140 01141 len+=d[VRPH_ABS(current)][VRPH_DEPOT]; 01142 01143 route[rnum].end=VRPH_ABS(current); 01144 route[rnum].length=len; 01145 route[rnum].load=load; 01146 route[rnum].num_customers=num_in_route; 01147 total_route_length+=len; 01148 01149 if(rnum>n) 01150 { 01151 fprintf(stderr,"%d>%d: rnum too big in import solution buff!\n",rnum,n); 01152 for(i=0;i<=n;i++) 01153 fprintf(stderr,"%d ",sol_buff[i]); 01154 01155 report_error("%s\n",__FUNCTION__); 01156 } 01157 01158 01159 rnum++; 01160 num_in_route=0; 01161 len=0; 01162 load=0; 01163 len+=d[VRPH_DEPOT][VRPH_ABS(next)]; 01164 route_num[VRPH_ABS(next)]=rnum; 01165 route[rnum].start=VRPH_ABS(next); 01166 } 01167 else 01168 // Not at the end of a route 01169 len+=d[VRPH_ABS(current)][VRPH_ABS(next)]; 01170 01171 01172 01173 next_array[VRPH_ABS(current)]=next; 01174 current=next; 01175 01176 load+=nodes[VRPH_ABS(current)].demand; 01177 num_in_route++; 01178 01179 route_num[VRPH_ABS(current)]=rnum; 01180 } 01181 01182 01183 next_array[VRPH_ABS(next)]=VRPH_DEPOT; 01184 route_num[VRPH_ABS(next)]=rnum; 01185 01186 len+=d[VRPH_ABS(next)][VRPH_DEPOT]; 01187 01188 route[rnum].end=VRPH_ABS(next); 01189 route[rnum].length=len; 01190 route[rnum].load=load; 01191 route[rnum].num_customers=num_in_route; 01192 total_route_length+=len; 01193 total_number_of_routes=rnum; 01194 create_pred_array(); 01195 01196 // Make sure everything imported successfully! 01197 verify_routes("After import sol_buff\n"); 01198 01199 // Mark all the nodes as "routed" 01200 for(i=1;i<=sol_buff[0];i++) 01201 routed[VRPH_ABS(sol_buff[i])]=true; 01202 01203 routed[VRPH_DEPOT]=true; 01204 01205 route_num[VRPH_DEPOT]=0; 01206 01207 memcpy(this->current_sol_buff,sol_buff,(this->num_nodes+2)*sizeof(int)); 01208 01209 return; 01210 01211 } 01212 void VRP::export_solution_buff(int *sol_buff) 01213 { 01217 01218 int i, current; 01219 01220 sol_buff[0]=num_nodes; 01221 01222 // Now output the ordering 01223 current=next_array[VRPH_DEPOT]; 01224 sol_buff[1]=current; 01225 i=2; 01226 01227 while(current!=VRPH_DEPOT) 01228 { 01229 current=next_array[VRPH_ABS(current)]; 01230 sol_buff[i]=current; 01231 i++; 01232 } 01233 01234 return; 01235 } 01236 01237 void VRP::export_canonical_solution_buff(int *sol_buff) 01238 { 01246 01247 int i,j,next; 01248 int *start_buff; 01249 01250 start_buff=new int[total_number_of_routes]; 01251 01252 this->normalize_route_numbers(); 01253 01254 // First orient each route properly 01255 for(i=1;i<=total_number_of_routes;i++) 01256 { 01257 if(route[i].end<route[i].start) 01258 reverse_route(i); 01259 01260 start_buff[i-1]=route[i].start; 01261 } 01262 01263 01264 // Sort the start_buff 01265 qsort(start_buff, total_number_of_routes, sizeof(int), VRPIntCompare); 01266 01267 sol_buff[0]=this->num_nodes; 01268 01269 // Now order the routes themselves 01270 j=1; 01271 for(i=0;i<total_number_of_routes;i++) 01272 { 01273 sol_buff[j]=-start_buff[i]; 01274 for(;;) 01275 { 01276 next=this->next_array[VRPH_ABS(sol_buff[j])]; 01277 if(next<=0) 01278 break; // next route 01279 01280 j++; 01281 sol_buff[j]=next; 01282 } 01283 j++; 01284 } 01285 01286 sol_buff[j]=VRPH_DEPOT; 01287 01288 delete [] start_buff; 01289 01290 return; 01291 01292 } 01293 01294 void VRP::show_routes() 01295 { 01299 01300 01301 int i, cnt; 01302 int route_start; 01303 int next_node_number; 01304 int current_node, current_route; 01305 int total_load = 0; 01306 01307 01308 printf("-----------------------------------------------\n"); 01309 printf("Total route length: %5.2f\n",total_route_length); 01310 i = 1; 01311 cnt = 0; 01312 route_start = -next_array[VRPH_DEPOT]; 01313 current_node = route_start; 01314 current_route = route_num[current_node]; 01315 total_load+= route[current_route].load; 01316 01317 01318 printf("\nRoute %04d(routenum=%d)[0-%d...%d-0, %5.2f, %d, %d]: \n",i,current_route, 01319 nodes[route[current_route].start].id, 01320 nodes[route[current_route].end].id, 01321 route[current_route].length, 01322 route[current_route].load, 01323 route[current_route].num_customers); 01324 01325 printf("%d-%d-",VRPH_DEPOT,nodes[route_start].id); 01326 01327 cnt++; 01328 01329 while(route_start != 0 && i<num_nodes+1) 01330 { 01331 // When we finally get a route beginning at 0, this is the last route 01332 // and there is no next route, so break out 01333 if(next_array[current_node]==0) 01334 { 01335 printf("%d\n",VRPH_DEPOT); 01336 printf("End of routes. Totals: (%d routes,%d nodes,%d total load)\n",i,cnt,total_load); 01337 printf("-----------------------------------------------\n"); 01338 if(cnt!= num_nodes) 01339 { 01340 fprintf(stderr,"Not enough nodes! counted=%d; claimed=%d\n",cnt,num_nodes); 01341 report_error("%s\n",__FUNCTION__); 01342 } 01343 01344 return; 01345 } 01346 01347 if(next_array[current_node]>0) 01348 { 01349 // Next node is somewhere in the middle of a route 01350 next_node_number = next_array[current_node]; 01351 printf("%d-",nodes[next_node_number].id); 01352 01353 current_node=next_node_number; 01354 cnt++; 01355 01356 if(cnt>num_nodes) 01357 { 01358 fprintf(stderr,"Too many nodes--cycle?\n"); 01359 fprintf(stderr,"Count is %d, num_nodes is %d\n",cnt,num_nodes); 01360 show_next_array(); 01361 report_error("%s\n",__FUNCTION__); 01362 } 01363 } 01364 else 01365 { 01366 // We must have a non-positive "next" node indicating the beginning of a new route 01367 i++; 01368 printf("%d",VRPH_DEPOT); 01369 01370 route_start = - (next_array[current_node]); 01371 current_route = route_num[route_start]; 01372 current_node = route_start; 01373 01374 printf("\n\nRoute %04d(routenum=%d)[0-%d...%d-0, %3.2f, %d, %d]: \n",i,current_route, 01375 nodes[route[current_route].start].id, 01376 nodes[route[current_route].end].id, 01377 route[current_route].length, 01378 route[current_route].load, 01379 route[current_route].num_customers); 01380 01381 01382 // Print out the beginning of this route 01383 total_load += route[current_route].load; 01384 printf("%d-%d-",VRPH_DEPOT,nodes[current_node].id); 01385 cnt++; 01386 } 01387 } 01388 01389 01390 } 01391 01392 01393 01394 01395 void VRP::show_route(int k) 01396 { 01400 01401 int current_node; 01402 int i=0; 01403 if(k<=0) 01404 report_error("%s: called with non-positive route number\n",__FUNCTION__); 01405 01406 printf("\nRoute %03d[0-%03d...%03d-0, %5.3f, %d, %d]: \n",k, 01407 route[k].start, 01408 route[k].end, 01409 route[k].length, 01410 route[k].load, 01411 route[k].num_customers); 01412 01413 printf("%d-",VRPH_DEPOT); 01414 01415 current_node= route[k].start; 01416 while(current_node != route[k].end) 01417 { 01418 printf("%03d-",current_node); 01419 current_node= next_array[current_node]; 01420 i++; 01421 if(i>num_nodes) 01422 report_error("%s: encountered too many nodes!!\n",__FUNCTION__); 01423 } 01424 printf("%03d-%d\n\n",current_node,VRPH_DEPOT); 01425 01426 } 01427 01428 void VRP::summary() 01429 { 01433 01434 int i, cnt; 01435 int route_start; 01436 int next_node_number; 01437 int current_node, current_route; 01438 int total_load = 0; 01439 int num_in_route=0; 01440 int total_nodes=0; 01441 int cust_count=0; 01442 bool feasible=true; 01443 01444 printf("\n------------------------------------------------\n"); 01445 printf("Solution for problem %s\n",this->name); 01446 printf("Total route length: %5.2f\n",total_route_length-this->total_service_time); 01447 if(this->best_known!=VRP_INFINITY) 01448 printf("Best known solution: %5.2f\n",this->best_known); 01449 printf("Total service time: %5.2f\n",this->total_service_time); 01450 if(this->max_route_length!=VRP_INFINITY) 01451 printf("Vehicle max route length: %5.2f\n",this->max_route_length); 01452 else 01453 printf("Vehicle max route length: N/A\n"); 01454 printf("Vehicle capacity: %d\n",this->max_veh_capacity); 01455 printf("Number of nodes visited: %d\n",this->num_nodes); 01456 printf("------------------------------------------------\n"); 01457 i = 1; 01458 cnt = 0; 01459 route_start = -next_array[VRPH_DEPOT]; 01460 current_node = route_start; 01461 current_route = route_num[current_node]; 01462 total_load+= route[current_route].load; 01463 01464 01465 printf("\nRoute %03d[0-%03d...%03d-0\tlen=%03.2f\tload=%04d\t#=%03d]",i,route[current_route].start, 01466 route[current_route].end,route[current_route].length, 01467 route[current_route].load,route[current_route].num_customers); 01468 // Check feasibility 01469 if(route[current_route].length>this->max_route_length || 01470 route[current_route].load > this->max_veh_capacity) 01471 feasible=false; 01472 cust_count+= route[current_route].num_customers; 01473 01474 if(current_node!= dummy_index) 01475 num_in_route=1; 01476 01477 total_nodes++; 01478 01479 cnt++; 01480 01481 while(route_start != 0 && i<num_nodes+1) 01482 { 01483 // When we finally get a route beginning at 0, this is the last route 01484 // and there is no next route, so break out 01485 if(next_array[current_node]==0) 01486 { 01487 num_in_route=0; 01488 if(cnt!= num_nodes) 01489 { 01490 fprintf(stderr,"Not enough nodes: counted=%d; claimed=%d!\n",cnt,num_nodes); 01491 report_error("%s\n",__FUNCTION__); 01492 } 01493 01494 printf("\n\n"); 01495 if(!feasible) 01496 printf("\nWARNING: Solution appears to be infeasible!\n"); 01497 return; 01498 } 01499 01500 if(next_array[current_node]>0) 01501 { 01502 // Next node is somewhere in the middle of a route 01503 next_node_number = next_array[current_node]; 01504 if(current_node!= dummy_index) 01505 num_in_route++; 01506 01507 total_nodes++; 01508 current_node=next_node_number; 01509 cnt++; 01510 } 01511 else 01512 { 01513 // We must have a non-positive "next" node indicating the beginning of a new route 01514 i++; 01515 total_nodes++; 01516 num_in_route=0; 01517 01518 route_start = - (next_array[current_node]); 01519 current_route = route_num[route_start]; 01520 current_node = route_start; 01521 01522 printf("\nRoute %03d[0-%03d...%03d-0\tlen=%03.2f\tload=%04d\t#=%03d]",i,route[current_route].start, 01523 route[current_route].end,route[current_route].length, 01524 route[current_route].load,route[current_route].num_customers); 01525 cust_count+= route[current_route].num_customers; 01526 01527 if(route[current_route].length>this->max_route_length || 01528 route[current_route].load > this->max_veh_capacity) 01529 feasible=false; 01530 01531 total_load += route[current_route].load; 01532 cnt++; 01533 if(current_node!= dummy_index) 01534 num_in_route++; 01535 } 01536 } 01537 } 01538