00001
00002
00003
00004
00005
00006
00007
00008
00009
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
00080 switch(ans)
00081 {
00082 case 1:
00083
00084
00085 temp2=strtok(NULL," ");
00086 strcpy(name,temp2);
00087
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
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
00128 temp2=strtok(NULL,"");
00129 this->best_known=atof(temp2);
00130 break;
00131 case 4:
00132
00133 num_nodes=atoi(strtok(NULL,""));
00134 num_nodes--;
00135 matrix_size= num_nodes;
00136
00137
00138 dummy_index = 1+num_nodes;
00139
00140 break;
00141
00142 case 5:
00143
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
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
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
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
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
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
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
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
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
00307
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
00324
00325
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
00337
00338 if(nodes[i].y<0)
00339 nodes[i].theta+=2*VRPH_PI;
00340 }
00341
00342
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
00359
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
00369
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
00399
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
00412
00413
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
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
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
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
00450
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
00462
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
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;
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
00524
00525
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
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
00545 d[i][num_nodes+1]=d[i][0];
00546 }
00547
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
00564 d[i][num_nodes+1]=d[i][0];
00565
00566 }
00567
00568 for(j=0;j<=num_nodes+1;j++)
00569 d[num_nodes+1][j]=d[0][j];
00570
00571 }
00572
00573
00574 if(edge_weight_format==VRPH_LOWER_DIAG_ROW)
00575 {
00576
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
00585 d[i][num_nodes+1]=d[i][0];
00586
00587 }
00588
00589 for(j=0;j<=num_nodes+1;j++)
00590 d[num_nodes+1][j]=d[0][j];
00591
00592 }
00593
00594
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
00605 d[i][num_nodes+1]=d[i][0];
00606 d[i][i]=0;
00607
00608 }
00609
00610 for(j=0;j<=num_nodes+1;j++)
00611 d[num_nodes+1][j]=d[0][j];
00612
00613 }
00614
00615
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
00627 d[i][num_nodes+1]=d[i][0];
00628
00629 }
00630
00631 for(j=0;j<=num_nodes+1;j++)
00632 d[num_nodes+1][j]=d[0][j];
00633 }
00634
00635
00636 fscanf(infile,"\n");
00637 break;
00638
00639 case 15:
00640
00641 #if TSPLIB_DEBUG
00642 printf("Case 15\n");
00643 #endif
00644
00645
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
00656 nodes[i].service_time=s;
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
00673
00674 min_vehicles=atoi(strtok(NULL,""));
00675
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
00685 this->num_days=atoi(strtok(NULL,""));
00686 break;
00687
00688 case 18:
00689
00690
00691 has_service_times=true;
00692
00693 if(this->num_days==0)
00694 {
00695 i=0;
00696 while(i<= num_nodes)
00697 {
00698
00699 fscanf(infile,"%d %lf\n",&x,&s);
00700 nodes[i].id=x;
00701 nodes[i].service_time=s;
00702 total_service_time+=nodes[i].service_time;
00703
00704 if(nodes[i].id>max_id)
00705 max_id=nodes[i].id;
00706 i++;
00707 }
00708 nodes[num_nodes+1].service_time=0;
00709
00710
00711 }
00712 else
00713 {
00714
00715 i=0;
00716 while(i<=num_nodes)
00717 {
00718 fscanf(infile,"%d",&x);
00719 nodes[i].id=x;
00720 for(j=1;j<this->num_days;j++)
00721 {
00722 fscanf(infile,"%lf",&s);
00723 this->nodes[i].daily_service_times[j]=s;
00724 }
00725 fscanf(infile,"%lf\n",&s);
00726 this->nodes[i].daily_service_times[this->num_days]=s;
00727 i++;
00728
00729 }
00730 this->nodes[num_nodes+1].service_time=0;
00731 for(j=1;j<=this->num_days;j++)
00732 this->nodes[num_nodes+1].daily_service_times[j]=0;
00733
00734 }
00735
00736
00737 break;
00738 case 19:
00739
00740 i=0;
00741 while(i<= num_nodes+1)
00742 {
00743 fscanf(infile,"%d %f %f\n",&x,&a,&b);
00744 nodes[i].start_tw=a;
00745 nodes[i].end_tw=b;
00746 i++;
00747 }
00748
00749 break;
00750 case 20:
00751
00752
00753 break;
00754 case 21:
00755
00756
00757
00758 this->can_display=true;
00759 i=0;
00760 x=0;
00761 while(i<=num_nodes)
00762 {
00763 fscanf(infile,"%d",&x);
00764 fscanf(infile,"%f",&a);
00765 fscanf(infile,"%f\n",&b);
00766
00767 nodes[x-1].x=(double) a;
00768 nodes[x-1].y=(double) b;
00769 i++;
00770
00771 }
00772
00773 break;
00774 case 22:
00775
00776 break;
00777 case 23:
00778
00779
00780 break;
00781 case 24:
00782
00783 break;
00784 case 25:
00785
00786 break;
00787 }
00788 }
00789
00790 }
00791
00792
00793 void VRP::write_TSPLIB_file(const char *outfile)
00794 {
00799
00800 FILE *out;
00801 int i;
00802
00803 if( (out=fopen(outfile,"w"))==NULL)
00804 {
00805 report_error("%s: Can't open file for writing...\n",__FUNCTION__);
00806 }
00807
00808 fprintf(out,"NAME: %s\n",name);
00809 fprintf(out,"TYPE: CVRP\n");
00810 if(this->best_known!=-1)
00811 fprintf(out,"BEST_KNOWN: %5.3f\n", this->best_known);
00812 fprintf(out,"DIMENSION: %d\n",num_nodes+1);
00813 fprintf(out,"CAPACITY: %d\n",max_veh_capacity);
00814 if(max_route_length!=VRP_INFINITY)
00815 fprintf(out,"DISTANCE: %4.5f\n",max_route_length);
00816 if(min_vehicles!=-1)
00817 fprintf(out,"VEHICLES: %d\n",min_vehicles);
00818 fprintf(out,"EDGE_WEIGHT_TYPE: FUNCTION\n");
00819 fprintf(out,"EDGE_WEIGHT_FORMAT: EXACT_2D\n");
00820 fprintf(out,"NODE_COORD_TYPE: TWOD_COORDS\n");
00821 fprintf(out,"NODE_COORD_SECTION\n");
00822
00823
00824 fprintf(out,"%d %4.5f %4.5f\n",1,nodes[0].x,nodes[0].y);
00825 for(i=1;i<=num_nodes;i++)
00826 {
00827 fprintf(out,"%d %4.5f %4.5f\n",i+1,nodes[i].x,nodes[i].y);
00828 }
00829
00830 fprintf(out,"DEMAND_SECTION\n");
00831
00832 fprintf(out,"1 0\n");
00833 for(i=1;i<=num_nodes;i++)
00834 {
00835 fprintf(out,"%d %d\n",i+1,nodes[i].demand);
00836 }
00837
00838 fprintf(out,"DEPOT_SECTION\n");
00839 fprintf(out,"1\n-1\n");
00840
00841 fprintf(out,"EOF\n");
00842
00843 fclose(out);
00844
00845 }
00846
00847
00848
00849 void VRP::write_solution_file(const char *filename)
00850 {
00863
00864
00865
00866 int n, current;
00867 FILE *out;
00868
00869 int *sol;
00870
00871
00872 if( (out = fopen(filename,"w"))==NULL)
00873 {
00874 fprintf(stderr,"Error opening %s for writing\n",filename);
00875 report_error("%s\n",__FUNCTION__);
00876 }
00877
00878
00879
00880
00881 n=0;
00882 current=VRPH_ABS(next_array[VRPH_DEPOT]);
00883 while(current!=VRPH_DEPOT)
00884 {
00885 current=VRPH_ABS(next_array[current]);
00886 n++;
00887 }
00888
00889 sol=new int[n+2];
00890
00891 this->export_canonical_solution_buff(sol);
00892 this->import_solution_buff(sol);
00893 fprintf(out,"%d ",n);
00894
00895
00896
00897 current=next_array[VRPH_DEPOT];
00898 fprintf(out,"%d ",current);
00899 while(current!=VRPH_DEPOT)
00900 {
00901 current=next_array[VRPH_ABS(current)];
00902 fprintf(out,"%d ",current);
00903
00904 }
00905
00906 fprintf(out,"\n\n\n");
00907
00908
00909 fflush(out);
00910 fprintf(out,"\n\n\nOBJ=\n%5.3f\nBEST_KNOWN=\n%5.3f",this->total_route_length-this->total_service_time,
00911 this->best_known);
00912
00913 fflush(out);
00914 fclose(out);
00915
00916 delete [] sol;
00917 return;
00918 }
00919
00920 void VRP::write_solutions(int num_sols, const char *filename)
00921 {
00926
00927 int i,n, current;
00928 FILE *out;
00929 int *sol;
00930
00931 sol=new int[this->num_original_nodes+2];
00932
00933
00934 if( (out = fopen(filename,"w"))==NULL)
00935 {
00936 fprintf(stderr,"Error opening %s for writing\n",filename);
00937 report_error("%s\n",__FUNCTION__);
00938 }
00939
00940 for(i=0;i<num_sols;i++)
00941 {
00942 if(i>this->solution_wh->num_sols)
00943 report_error("%s: too many solutions!\n",__FUNCTION__);
00944
00945
00946 this->import_solution_buff(this->solution_wh->sols[i].sol);
00947 this->export_canonical_solution_buff(sol);
00948 this->import_solution_buff(sol);
00949
00950
00951
00952
00953
00954 n=0;
00955 current=VRPH_ABS(next_array[VRPH_DEPOT]);
00956 while(current!=VRPH_DEPOT)
00957 {
00958 current=VRPH_ABS(next_array[current]);
00959 n++;
00960 }
00961
00962 fprintf(out,"%d ",n);
00963
00964
00965 current=next_array[VRPH_DEPOT];
00966 fprintf(out,"%d ",current);
00967 while(current!=VRPH_DEPOT)
00968 {
00969 current=next_array[VRPH_ABS(current)];
00970 fprintf(out,"%d ",current);
00971
00972 }
00973 fprintf(out,"\n");
00974 }
00975
00976 fflush(out);
00977 fclose(out);
00978 return;
00979
00980 }
00981
00982
00983 void VRP::write_tex_file(const char *filename)
00984 {
00990
00991 int i;
00992
00993 FILE *out;
00994 if( (out=fopen(filename,"w"))==NULL)
00995 {
00996 fprintf(stderr,"Error opening %s for writing\n",filename);
00997 report_error("%s\n",__FUNCTION__);
00998
00999 }
01000
01001
01002 fprintf(out,"%% TeX file automatically generated by VRPH for problem %s\n\n",this->name);
01003 fprintf(out,"\\renewcommand{\\baselinestretch}{1}\n");
01004 fprintf(out,"\\footnotesize\n");
01005 fprintf(out,"\\begin{center}\n");
01006 fprintf(out,"\\begin{longtable}{|c|r|r|p{4 in}|}\n");
01007
01008 fprintf(out,"\\hline\n");
01009 fprintf(out,"Route&\\multicolumn{1}{c|}{Length}&\\multicolumn{1}{c|}{Load}&\\multicolumn{1}{c|}{Ordering}\\\\\n");
01010 fprintf(out,"\\hline\n");
01011 fprintf(out,"\\endhead\n");
01012 fprintf(out,"\\hline\n");
01013 fprintf(out,"\\multicolumn{3}{|l|}{Problem}&%s\\\\\n",this->name);
01014 fprintf(out,"\\hline\n");
01015 fprintf(out,"\\endfirsthead\n");
01016 fprintf(out,"\\endfoot\n");
01017 fprintf(out,"\\endlastfoot\n");
01018 fprintf(out,"\\multicolumn{3}{|l|}{Vehicle capacity}&%d\\\\\n",this->max_veh_capacity);
01019 if(this->max_route_length!=VRP_INFINITY)
01020 fprintf(out,"\\multicolumn{3}{|l|}{Maximum route length}&%5.3f\\\\\n",this->max_route_length);
01021 else
01022 fprintf(out,"\\multicolumn{3}{|l|}{Maximum route length}&N/A\\\\\n");
01023 if(this->total_service_time>0)
01024 fprintf(out,"\\multicolumn{3}{|l|}{Total service time}&%5.3f\\\\\n",this->total_service_time);
01025 fprintf(out,"\\multicolumn{3}{|l|}{Number of nodes}&%d\\\\\n",this->num_nodes);
01026 fprintf(out,"\\multicolumn{3}{|l|}{Total route length}&%5.3f\\\\\n",this->total_route_length-
01027 this->total_service_time);
01028 fprintf(out,"\\multicolumn{3}{|l|}{Total number of routes}&%d\\\\\n",this->total_number_of_routes);
01029 fprintf(out,"\\hline\n");
01030 fprintf(out,"Route&\\multicolumn{1}{c|}{Length}&\\multicolumn{1}{c|}{Load}&\\multicolumn{1}{c|}{Ordering}\\\\\n");
01031 fprintf(out,"\\hline\n");
01032
01033 for(i=1;i<=this->total_number_of_routes;i++)
01034 {
01035 fprintf(out,"%d&%5.3f&%d&(0",i,this->route[i].length,this->route[i].load);
01036 int current=this->route[i].start;
01037 while(current>=0)
01038 {
01039 fprintf(out,", %d",current);
01040 current=this->next_array[current];
01041
01042 }
01043 fprintf(out,", 0)\\\\\n");
01044 fprintf(out,"\\hline\n");
01045 }
01046 fprintf(out,"\\caption{The best solution found for problem %s}\n",this->name);
01047 fprintf(out,"\\end{longtable}\n");
01048 fprintf(out,"\\end{center}\n");
01049 fprintf(out,"\\renewcommand{\\baselinestretch}{2}\n");
01050 fprintf(out,"\\normalsize\n");
01051 fclose(out);
01052 }
01053
01054
01055 void VRP::read_solution_file(const char *filename)
01056 {
01061
01062 FILE *in;
01063
01064 if( (in=fopen(filename,"r"))==NULL)
01065 {
01066 fprintf(stderr,"Error opening %s for reading\n",filename);
01067 report_error("%s\n",__FUNCTION__);
01068 }
01069
01070 int *new_sol;
01071 int i,n;
01072 fscanf(in,"%d",&n);
01073 new_sol=new int[n+2];
01074 new_sol[0]=n;
01075 for(i=1;i<=n+1;i++)
01076 fscanf(in,"%d",new_sol+i);
01077
01078
01079 this->import_solution_buff(new_sol);
01080 fclose(in);
01081 delete [] new_sol;
01082
01083 this->verify_routes("After read_solution_file\n");
01084
01085 memcpy(this->best_sol_buff,this->current_sol_buff,(this->num_nodes+2)*sizeof(int));
01086
01087 return;
01088
01089 }
01090
01091
01092
01093 void VRP::import_solution_buff(int *sol_buff)
01094 {
01100
01101
01102 int i, n, rnum, current, next, load, num_in_route;
01103 double len;
01104
01105 next=-1;
01106
01107
01108 for(i=1;i<=this->num_original_nodes;i++)
01109 routed[i]=false;
01110
01111 len=0;
01112 load=0;
01113
01114 total_route_length=0;
01115
01116 this->num_nodes = sol_buff[0];
01117
01118 n=this->num_nodes;
01119 num_in_route=0;
01120
01121 rnum=1;
01122
01123 current=VRPH_ABS(sol_buff[1]);
01124 routed[current]=true;
01125 next_array[VRPH_DEPOT]=sol_buff[1];
01126 route_num[VRPH_ABS(current)]=rnum;
01127 route[rnum].start=VRPH_ABS(current);
01128 load+=nodes[VRPH_ABS(current)].demand;
01129 len+=d[VRPH_DEPOT][VRPH_ABS(current)];
01130 num_in_route++;
01131
01132 for(i=2;i<=n;i++)
01133 {
01134 next=sol_buff[i];
01135 routed[VRPH_ABS(next)]=true;
01136
01137 if(next<0)
01138 {
01139
01140
01141
01142 len+=d[VRPH_ABS(current)][VRPH_DEPOT];
01143
01144 route[rnum].end=VRPH_ABS(current);
01145 route[rnum].length=len;
01146 route[rnum].load=load;
01147 route[rnum].num_customers=num_in_route;
01148 total_route_length+=len;
01149
01150 if(rnum>n)
01151 {
01152 fprintf(stderr,"%d>%d: rnum too big in import solution buff!\n",rnum,n);
01153 for(i=0;i<=n;i++)
01154 fprintf(stderr,"%d ",sol_buff[i]);
01155
01156 report_error("%s\n",__FUNCTION__);
01157 }
01158
01159
01160 rnum++;
01161 num_in_route=0;
01162 len=0;
01163 load=0;
01164 len+=d[VRPH_DEPOT][VRPH_ABS(next)];
01165 route_num[VRPH_ABS(next)]=rnum;
01166 route[rnum].start=VRPH_ABS(next);
01167 }
01168 else
01169
01170 len+=d[VRPH_ABS(current)][VRPH_ABS(next)];
01171
01172
01173
01174 next_array[VRPH_ABS(current)]=next;
01175 current=next;
01176
01177 load+=nodes[VRPH_ABS(current)].demand;
01178 num_in_route++;
01179
01180 route_num[VRPH_ABS(current)]=rnum;
01181 }
01182
01183
01184 next_array[VRPH_ABS(next)]=VRPH_DEPOT;
01185 route_num[VRPH_ABS(next)]=rnum;
01186
01187 len+=d[VRPH_ABS(next)][VRPH_DEPOT];
01188
01189 route[rnum].end=VRPH_ABS(next);
01190 route[rnum].length=len;
01191 route[rnum].load=load;
01192 route[rnum].num_customers=num_in_route;
01193 total_route_length+=len;
01194 total_number_of_routes=rnum;
01195 create_pred_array();
01196
01197
01198 verify_routes("After import sol_buff\n");
01199
01200
01201 for(i=1;i<=sol_buff[0];i++)
01202 routed[VRPH_ABS(sol_buff[i])]=true;
01203
01204 routed[VRPH_DEPOT]=true;
01205
01206 route_num[VRPH_DEPOT]=0;
01207
01208 memcpy(this->current_sol_buff,sol_buff,(this->num_nodes+2)*sizeof(int));
01209
01210 return;
01211
01212 }
01213 void VRP::export_solution_buff(int *sol_buff)
01214 {
01218
01219 int i, current;
01220
01221 sol_buff[0]=num_nodes;
01222
01223
01224 current=next_array[VRPH_DEPOT];
01225 sol_buff[1]=current;
01226 i=2;
01227
01228 while(current!=VRPH_DEPOT)
01229 {
01230 current=next_array[VRPH_ABS(current)];
01231 sol_buff[i]=current;
01232 i++;
01233 }
01234
01235 return;
01236 }
01237
01238 void VRP::export_canonical_solution_buff(int *sol_buff)
01239 {
01247
01248 int i,j,next;
01249 int *start_buff;
01250
01251 start_buff=new int[total_number_of_routes];
01252
01253 this->normalize_route_numbers();
01254
01255
01256 for(i=1;i<=total_number_of_routes;i++)
01257 {
01258 if(route[i].end<route[i].start)
01259 reverse_route(i);
01260
01261 start_buff[i-1]=route[i].start;
01262 }
01263
01264
01265
01266 qsort(start_buff, total_number_of_routes, sizeof(int), VRPIntCompare);
01267
01268 sol_buff[0]=this->num_nodes;
01269
01270
01271 j=1;
01272 for(i=0;i<total_number_of_routes;i++)
01273 {
01274 sol_buff[j]=-start_buff[i];
01275 for(;;)
01276 {
01277 next=this->next_array[VRPH_ABS(sol_buff[j])];
01278 if(next<=0)
01279 break;
01280
01281 j++;
01282 sol_buff[j]=next;
01283 }
01284 j++;
01285 }
01286
01287 sol_buff[j]=VRPH_DEPOT;
01288
01289 delete [] start_buff;
01290
01291 return;
01292
01293 }
01294
01295 void VRP::show_routes()
01296 {
01300
01301
01302 int i, cnt;
01303 int route_start;
01304 int next_node_number;
01305 int current_node, current_route;
01306 int total_load = 0;
01307
01308
01309 printf("-----------------------------------------------\n");
01310 printf("Total route length: %5.2f\n",total_route_length);
01311 i = 1;
01312 cnt = 0;
01313 route_start = -next_array[VRPH_DEPOT];
01314 current_node = route_start;
01315 current_route = route_num[current_node];
01316 total_load+= route[current_route].load;
01317
01318
01319 printf("\nRoute %04d(routenum=%d)[0-%d...%d-0, %5.2f, %d, %d]: \n",i,current_route,
01320 nodes[route[current_route].start].id,
01321 nodes[route[current_route].end].id,
01322 route[current_route].length,
01323 route[current_route].load,
01324 route[current_route].num_customers);
01325
01326 printf("%d-%d-",VRPH_DEPOT,nodes[route_start].id);
01327
01328 cnt++;
01329
01330 while(route_start != 0 && i<num_nodes+1)
01331 {
01332
01333
01334 if(next_array[current_node]==0)
01335 {
01336 printf("%d\n",VRPH_DEPOT);
01337 printf("End of routes. Totals: (%d routes,%d nodes,%d total load)\n",i,cnt,total_load);
01338 printf("-----------------------------------------------\n");
01339 if(cnt!= num_nodes)
01340 {
01341 fprintf(stderr,"Not enough nodes! counted=%d; claimed=%d\n",cnt,num_nodes);
01342 report_error("%s\n",__FUNCTION__);
01343 }
01344
01345 return;
01346 }
01347
01348 if(next_array[current_node]>0)
01349 {
01350
01351 next_node_number = next_array[current_node];
01352 printf("%d-",nodes[next_node_number].id);
01353
01354 current_node=next_node_number;
01355 cnt++;
01356
01357 if(cnt>num_nodes)
01358 {
01359 fprintf(stderr,"Too many nodes--cycle?\n");
01360 fprintf(stderr,"Count is %d, num_nodes is %d\n",cnt,num_nodes);
01361 show_next_array();
01362 report_error("%s\n",__FUNCTION__);
01363 }
01364 }
01365 else
01366 {
01367
01368 i++;
01369 printf("%d",VRPH_DEPOT);
01370
01371 route_start = - (next_array[current_node]);
01372 current_route = route_num[route_start];
01373 current_node = route_start;
01374
01375 printf("\n\nRoute %04d(routenum=%d)[0-%d...%d-0, %3.2f, %d, %d]: \n",i,current_route,
01376 nodes[route[current_route].start].id,
01377 nodes[route[current_route].end].id,
01378 route[current_route].length,
01379 route[current_route].load,
01380 route[current_route].num_customers);
01381
01382
01383
01384 total_load += route[current_route].load;
01385 printf("%d-%d-",VRPH_DEPOT,nodes[current_node].id);
01386 cnt++;
01387 }
01388 }
01389
01390
01391 }
01392
01393
01394
01395
01396 void VRP::show_route(int k)
01397 {
01401
01402 int current_node;
01403 int i=0;
01404 if(k<=0)
01405 report_error("%s: called with non-positive route number\n",__FUNCTION__);
01406
01407 printf("\nRoute %03d[0-%03d...%03d-0, %5.3f, %d, %d]: \n",k,
01408 route[k].start,
01409 route[k].end,
01410 route[k].length,
01411 route[k].load,
01412 route[k].num_customers);
01413
01414 printf("%d-",VRPH_DEPOT);
01415
01416 current_node= route[k].start;
01417 while(current_node != route[k].end)
01418 {
01419 printf("%03d-",current_node);
01420 current_node= next_array[current_node];
01421 i++;
01422 if(i>num_nodes)
01423 report_error("%s: encountered too many nodes!!\n",__FUNCTION__);
01424 }
01425 printf("%03d-%d\n\n",current_node,VRPH_DEPOT);
01426
01427 }
01428
01429 void VRP::summary()
01430 {
01434
01435 int i, cnt;
01436 int route_start;
01437 int next_node_number;
01438 int current_node, current_route;
01439 int total_load = 0;
01440 int num_in_route=0;
01441 int total_nodes=0;
01442 int cust_count=0;
01443 bool feasible=true;
01444
01445 printf("\n------------------------------------------------\n");
01446 printf("Solution for problem %s\n",this->name);
01447 printf("Total route length: %5.2f\n",total_route_length-this->total_service_time);
01448 if(this->best_known!=VRP_INFINITY)
01449 printf("Best known solution: %5.2f\n",this->best_known);
01450 printf("Total service time: %5.2f\n",this->total_service_time);
01451 if(this->max_route_length!=VRP_INFINITY)
01452 printf("Vehicle max route length: %5.2f\n",this->max_route_length);
01453 else
01454 printf("Vehicle max route length: N/A\n");
01455 printf("Vehicle capacity: %d\n",this->max_veh_capacity);
01456 printf("Number of nodes visited: %d\n",this->num_nodes);
01457 printf("------------------------------------------------\n");
01458 i = 1;
01459 cnt = 0;
01460 route_start = -next_array[VRPH_DEPOT];
01461 current_node = route_start;
01462 current_route = route_num[current_node];
01463 total_load+= route[current_route].load;
01464
01465
01466 printf("\nRoute %03d[0-%03d...%03d-0\tlen=%03.2f\tload=%04d\t#=%03d]",i,route[current_route].start,
01467 route[current_route].end,route[current_route].length,
01468 route[current_route].load,route[current_route].num_customers);
01469
01470 if(route[current_route].length>this->max_route_length ||
01471 route[current_route].load > this->max_veh_capacity)
01472 feasible=false;
01473 cust_count+= route[current_route].num_customers;
01474
01475 if(current_node!= dummy_index)
01476 num_in_route=1;
01477
01478 total_nodes++;
01479
01480 cnt++;
01481
01482 while(route_start != 0 && i<num_nodes+1)
01483 {
01484
01485
01486 if(next_array[current_node]==0)
01487 {
01488 num_in_route=0;
01489 if(cnt!= num_nodes)
01490 {
01491 fprintf(stderr,"Not enough nodes: counted=%d; claimed=%d!\n",cnt,num_nodes);
01492 report_error("%s\n",__FUNCTION__);
01493 }
01494
01495 printf("\n\n");
01496 if(!feasible)
01497 printf("\nWARNING: Solution appears to be infeasible!\n");
01498 return;
01499 }
01500
01501 if(next_array[current_node]>0)
01502 {
01503
01504 next_node_number = next_array[current_node];
01505 if(current_node!= dummy_index)
01506 num_in_route++;
01507
01508 total_nodes++;
01509 current_node=next_node_number;
01510 cnt++;
01511 }
01512 else
01513 {
01514
01515 i++;
01516 total_nodes++;
01517 num_in_route=0;
01518
01519 route_start = - (next_array[current_node]);
01520 current_route = route_num[route_start];
01521 current_node = route_start;
01522
01523 printf("\nRoute %03d[0-%03d...%03d-0\tlen=%03.2f\tload=%04d\t#=%03d]",i,route[current_route].start,
01524 route[current_route].end,route[current_route].length,
01525 route[current_route].load,route[current_route].num_customers);
01526 cust_count+= route[current_route].num_customers;
01527
01528 if(route[current_route].length>this->max_route_length ||
01529 route[current_route].load > this->max_veh_capacity)
01530 feasible=false;
01531
01532 total_load += route[current_route].load;
01533 cnt++;
01534 if(current_node!= dummy_index)
01535 num_in_route++;
01536 }
01537 }
01538 }
01539