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 00016 bool OrOpt::search(class VRP *V, int a, int len, int rules) 00017 { 00022 00023 00024 VRPMove M, BestM; 00025 BestM.savings=VRP_INFINITY; 00026 int i,b,c,d; 00027 int string_end; 00028 int str[10]; 00029 00030 int accept_type; 00031 00032 //default setting 00033 accept_type=VRPH_FIRST_ACCEPT; 00034 00035 if( (rules & VRPH_FIRST_ACCEPT) > 0) 00036 accept_type=VRPH_FIRST_ACCEPT; 00037 if( (rules & VRPH_BEST_ACCEPT) > 0) 00038 accept_type=VRPH_BEST_ACCEPT; 00039 if( (rules & VRPH_LI_ACCEPT) > 0) 00040 accept_type=VRPH_LI_ACCEPT; 00041 00042 string_end = V->get_string_end(a,len); 00043 00044 if(string_end==-1) 00045 { 00046 // We couldn't get a string of the right length 00047 return false; 00048 } 00049 00050 if(rules & VRPH_FIXED_EDGES) 00051 { 00052 // Make sure we aren't disturbing fixed edges 00053 i=VRPH_MAX(V->pred_array[a],VRPH_DEPOT); 00054 00055 if( V->fixed[i][a] ) 00056 return false; 00057 00058 i=VRPH_MAX(V->next_array[string_end],VRPH_DEPOT); 00059 if( V->fixed[string_end][i]) 00060 return false; 00061 } 00062 00063 00064 // Load the string into the str array to look for the VRPH_DEPOT 00065 str[0]=a; 00066 for(i=1;i<len;i++) 00067 { 00068 str[i]= V->next_array[str[i-1]]; 00069 if(str[i]<=VRPH_DEPOT) 00070 return false; 00071 } 00072 00073 V->create_search_neighborhood(a, rules); 00074 00075 int *old_sol=NULL; 00076 if(rules & VRPH_TABU) 00077 { 00078 // Remember the original solution 00079 old_sol=new int[V->num_original_nodes+2]; 00080 V->export_solution_buff(old_sol); 00081 } 00082 00083 for(i=0;i<V->search_size;i++) 00084 { 00085 c=V->search_space[i]; 00086 00087 if(c!=VRPH_DEPOT) 00088 { 00089 00090 d=VRPH_MAX(V->next_array[c],0); 00091 b=VRPH_MAX(V->pred_array[c],0); 00092 00093 int flag=0; 00094 if(d==VRPH_DEPOT) 00095 flag=1; 00096 00097 // Look for overlap 00098 00099 for(int j=0;j<len;j++) 00100 { 00101 if(str[j]==c || str[j]==d) 00102 // Either c or d is already in the string that starts at a 00103 flag=1; 00104 } 00105 if(flag==0) 00106 { 00107 00108 // Try the move 00109 if(evaluate(V,a,len,c,d,rules, &M)==true) 00110 { 00111 // The move is good--make it 00112 if(accept_type == VRPH_FIRST_ACCEPT || (accept_type==VRPH_LI_ACCEPT && M.savings<-VRPH_EPSILON)) 00113 { 00114 if(move(V, &M)==false) 00115 report_error("%s: move error 1\n",__FUNCTION__); 00116 else 00117 { 00118 if(!(rules & VRPH_TABU)) 00119 return true; 00120 else 00121 { 00122 // Check VRPH_TABU status of move - return true if its ok 00123 // or revert to old_sol if not and continue to search. 00124 if(V->check_tabu_status(&M, old_sol)) 00125 { 00126 delete [] old_sol; 00127 return true; // The move was ok 00128 } 00129 // else we reverted back - continue the search for a move 00130 } 00131 } 00132 } 00133 00134 if(accept_type == VRPH_BEST_ACCEPT || accept_type==VRPH_LI_ACCEPT) 00135 { 00136 if(M.is_better(V, &BestM, rules))//if(M.savings<best_savings) 00137 BestM=M; 00138 00139 } 00140 00141 if(accept_type == VRPH_LI_ACCEPT) 00142 { 00143 // Move if downhill 00144 if(M.savings<-VRPH_EPSILON) 00145 { 00146 if(move(V, &M)==false) 00147 report_error("%s: move error 2\n",__FUNCTION__); 00148 else 00149 { 00150 if(!(rules & VRPH_TABU)) 00151 return true; 00152 else 00153 { 00154 // Check VRPH_TABU status of move - return true if its ok 00155 // or revert to old_sol if not and continue to search. 00156 if(V->check_tabu_status(&M, old_sol)) 00157 { 00158 delete [] old_sol; 00159 return true; // The move was ok 00160 } 00161 // else we reverted back - continue the search for a move 00162 } 00163 } 00164 } 00165 else 00166 { 00167 // Uphill move - see if it's the best so far 00168 if(M.is_better(V, &BestM, rules))//if(M.savings<BestM.savings) 00169 BestM=M; 00170 } 00171 } 00172 } 00173 } 00174 } 00175 } 00176 00177 if(accept_type == VRPH_FIRST_ACCEPT || BestM.savings==VRP_INFINITY) 00178 { 00179 if(old_sol) 00180 delete [] old_sol; 00181 return false ; // No moves found 00182 } 00183 00184 if(move(V,&BestM)==true) 00185 { 00186 if(!(rules & VRPH_TABU)) 00187 return true; 00188 } 00189 00190 if(rules & VRPH_TABU) 00191 { 00192 // Check VRPH_TABU status of move - return true if its ok 00193 // or revert to old_sol if not and return 00194 if(V->check_tabu_status(&BestM, old_sol))// was &M?? 00195 { 00196 delete [] old_sol; 00197 return true; // The move was ok 00198 } 00199 else 00200 { 00201 delete [] old_sol; 00202 return false; 00203 } 00204 } 00205 00206 // Should have already returned 00207 report_error("%s: move error\n",__FUNCTION__); 00208 return false; 00209 00210 00211 } 00212 00213 bool OrOpt::route_search(VRP *V, int r1, int r2, int len, int rules) 00214 { 00220 00221 VRPMove M, BestM; 00222 BestM.savings=VRP_INFINITY; 00223 int c,d; 00224 int accept_type; 00225 00226 //default setting 00227 accept_type=VRPH_FIRST_ACCEPT; 00228 00229 if( (rules & VRPH_FIRST_ACCEPT) > 0) 00230 accept_type=VRPH_FIRST_ACCEPT; 00231 if( (rules & VRPH_BEST_ACCEPT) > 0) 00232 accept_type=VRPH_BEST_ACCEPT; 00233 if( (rules & VRPH_LI_ACCEPT) > 0) 00234 accept_type=VRPH_LI_ACCEPT; 00235 00236 int j; 00237 j= V->route[r1].start; 00238 while(j!=VRPH_DEPOT) 00239 { 00240 // Loop through r1 and r2 00241 c= V->route[r2].start; 00242 while(c!=VRPH_DEPOT) 00243 { 00244 d=VRPH_MAX(V->next_array[c],0); 00245 if(evaluate(V,j,len,c,d,rules, &M)==true) 00246 { 00247 if(accept_type==VRPH_FIRST_ACCEPT || (accept_type==VRPH_LI_ACCEPT && M.savings<-VRPH_EPSILON) ) 00248 { 00249 // Make the move 00250 if(move(V,&M)==false) 00251 report_error("%s: first accept move returns false",__FUNCTION__); 00252 else 00253 return true; 00254 } 00255 00256 00257 if(accept_type == VRPH_LI_ACCEPT || accept_type == VRPH_BEST_ACCEPT) 00258 { 00259 if(M.is_better(V, &BestM, rules)) 00260 BestM=M; 00261 00262 } 00263 00264 } 00265 00266 // Advance r2 node 00267 c=d; 00268 } 00269 00270 // Advance r1 node 00271 j=VRPH_MAX(V->next_array[j],0); 00272 } 00273 00274 if(accept_type==VRPH_FIRST_ACCEPT) 00275 return false; // No moves found 00276 00277 if(BestM.savings==VRP_INFINITY) 00278 return false; 00279 00280 if(accept_type==VRPH_BEST_ACCEPT || accept_type==VRPH_LI_ACCEPT) 00281 { 00282 00283 // Make the move 00284 if(move(V,&BestM)==false) 00285 report_error("%s: first accept move returns false\n",__FUNCTION__); 00286 else 00287 return true; 00288 00289 } 00290 00291 report_error("%s: shouldn't get here...\n",__FUNCTION__); 00292 00293 return false; 00294 00295 } 00296 00297 bool OrOpt::evaluate(class VRP *V, int a, int len, int c, int d, int rules, VRPMove *M) 00298 { 00303 00304 V->num_evaluations[OR_OPT_INDEX]++; 00305 00306 M->evaluated_savings=false; 00307 00308 if(rules & VRPH_FIXED_EDGES) 00309 { 00310 // Make sure we aren't disturbing fixed edges 00311 if( V->fixed[c][d] ) 00312 return false; 00313 } 00314 00315 if(V->routed[a]==false || V->routed[c]==false || 00316 V->routed[d]==false ) 00317 return false; 00318 00319 int a_route, c_route; 00320 00321 M->eval_arguments[0]=a;M->eval_arguments[1]=len; 00322 M->eval_arguments[2]=c;M->eval_arguments[3]=d; 00323 00324 // First make sure the edge c-d exists 00325 if(c!=VRPH_DEPOT && VRPH_MAX(V->next_array[c],0)!=d ) 00326 report_error("%s: c-d not an edge!\n",__FUNCTION__); 00327 00328 00329 if(c==VRPH_DEPOT && VRPH_MAX(V->pred_array[d],0)!=c) 00330 report_error("%s: c-d not an edge!\n",__FUNCTION__); 00331 00332 00333 a_route= V->route_num[a]; 00334 if(c!=VRPH_DEPOT) 00335 c_route= V->route_num[c]; 00336 else 00337 c_route= V->route_num[d]; 00338 00339 00340 if( (rules & VRPH_INTER_ROUTE_ONLY) && (a_route ==c_route)) 00341 return false; 00342 00343 if((rules & VRPH_INTRA_ROUTE_ONLY) && a_route !=c_route) 00344 return false; 00345 00346 // Construct the appropriate string; 00347 00348 int string_end = V->get_string_end(a, len); 00349 if(string_end==-1) 00350 // The string of length len beginning at a is not contained in a single route 00351 return false; 00352 00353 if(rules & VRPH_FIXED_EDGES) 00354 { 00355 // Make sure we aren't disturbing fixed edges 00356 int z,b; 00357 00358 z=VRPH_MAX(V->pred_array[a],VRPH_DEPOT); 00359 b=VRPH_MAX(V->next_array[string_end],VRPH_DEPOT); 00360 00361 if( V->fixed[z][a] || V->fixed[string_end][b] ) 00362 return false; 00363 00364 00365 } 00366 00367 // Now just use MoveString to evaluate 00368 00369 MoveString MS; 00370 00371 if(MS.evaluate(V,c,d,a,string_end, M)==true) 00372 { 00373 if(V->check_move(M,rules)==true) 00374 return true; 00375 else 00376 return false; 00377 00378 } 00379 00380 00381 return false; 00382 00383 00384 } 00385 00386 00387 00388 bool OrOpt::move(class VRP *V, VRPMove *M) 00389 { 00394 00395 int a,len,c,d; 00396 00397 a=M->eval_arguments[0]; 00398 len=M->eval_arguments[1]; 00399 c=M->eval_arguments[2]; 00400 d=M->eval_arguments[3]; 00401 00402 int string_end = V->get_string_end(a, len); 00403 if(string_end==-1) 00404 { 00405 report_error("%s: no string end in move??\n",__FUNCTION__); 00406 00407 } 00408 00409 MoveString MS; 00410 00411 if( MS.move(V,c,d,a,string_end)==false) 00412 { 00413 report_error("%s: MS.move is false!\n",__FUNCTION__); 00414 00415 } 00416 00417 V->num_moves[OR_OPT_INDEX]++; 00418 V->capture_best_solution(); 00419 return true; 00420 }