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 // SEARCH 00017 bool TwoPointMove::search(class VRP *V, int j, int rules) 00018 { 00025 00026 VRPMove M; 00027 VRPMove BestM; 00028 BestM.savings=VRP_INFINITY; 00029 int i,k; 00030 int accept_type; 00031 00032 if(j==VRPH_DEPOT) 00033 return false; 00034 00035 if(rules & VRPH_FIXED_EDGES) 00036 { 00037 i=VRPH_MAX(V->pred_array[j],VRPH_DEPOT); 00038 k=VRPH_MAX(V->next_array[j],VRPH_DEPOT); 00039 00040 // Make sure we aren't disturbing fixed edges 00041 00042 if( V->fixed[i][j] || V->fixed[j][k] ) 00043 return false; 00044 } 00045 00046 accept_type=VRPH_FIRST_ACCEPT;//default 00047 00048 if( (rules & VRPH_FIRST_ACCEPT) > 0) 00049 accept_type=VRPH_FIRST_ACCEPT; 00050 if( (rules & VRPH_BEST_ACCEPT) > 0) 00051 accept_type=VRPH_BEST_ACCEPT; 00052 if( (rules & VRPH_LI_ACCEPT) > 0) 00053 accept_type=VRPH_LI_ACCEPT; 00054 00055 int *old_sol=NULL; 00056 if(rules & VRPH_TABU) 00057 { 00058 // Remember the original solution 00059 old_sol=new int[V->num_original_nodes+2]; 00060 V->export_solution_buff(old_sol); 00061 } 00062 00063 // Create the search_space 00064 V->create_search_neighborhood(j, rules); 00065 00066 for(i=0;i<V->search_size;i++) 00067 { 00068 k=V->search_space[i]; 00069 00070 if(k!=VRPH_DEPOT && k!=j) 00071 { 00072 // VRPH_DEPOT not allowed in TwoPointMove 00073 00074 if(evaluate(V,j,k,rules,&M)==true) 00075 { 00076 // Feasible move found 00077 if(accept_type==VRPH_FIRST_ACCEPT || (accept_type==VRPH_LI_ACCEPT && M.savings<-VRPH_EPSILON) ) 00078 { 00079 // make the move 00080 00081 if(move(V, &M)==false) 00082 report_error("%s: move error 1\n",__FUNCTION__); 00083 else 00084 { 00085 if(!(rules & VRPH_TABU)) 00086 return true; 00087 else 00088 { 00089 // Check VRPH_TABU status of move - return true if its ok 00090 // or revert to old_sol if not and continue to search. 00091 if(V->check_tabu_status(&M, old_sol)) 00092 { 00093 delete [] old_sol; 00094 return true; // The move was ok 00095 } 00096 00097 } 00098 } 00099 } 00100 00101 00102 00103 if(accept_type==VRPH_BEST_ACCEPT || accept_type==VRPH_LI_ACCEPT ) 00104 { 00105 // compare to best move so far 00106 if(M.is_better(V, &BestM, rules)) 00107 BestM=M; 00108 00109 } 00110 00111 } 00112 } 00113 } 00114 00115 00116 00117 if(accept_type==VRPH_FIRST_ACCEPT) 00118 { 00119 if(old_sol) 00120 delete [] old_sol; 00121 return false; 00122 } 00123 00124 if(BestM.savings==VRP_INFINITY) 00125 { 00126 if(old_sol) 00127 delete [] old_sol; 00128 return false; 00129 } 00130 // else we found a move - make it 00131 00132 if(move(V,&BestM)==true) 00133 { 00134 if(!(rules & VRPH_TABU)) 00135 return true; 00136 } 00137 00138 if(rules & VRPH_TABU) 00139 { 00140 // Check VRPH_TABU status of move - return true if its ok 00141 // or revert to old_sol if not and return 00142 if(V->check_tabu_status(&M, old_sol)) 00143 { 00144 delete [] old_sol; 00145 return true; // The move was ok 00146 } 00147 else 00148 { 00149 delete [] old_sol; 00150 return false; 00151 } 00152 } 00153 00154 00155 report_error("%s: best move false!\n",__FUNCTION__); 00156 00157 00158 return false; 00159 } 00160 00161 00162 bool TwoPointMove::route_search(class VRP *V, int r1, int r2, int rules) 00163 { 00168 00169 00170 VRPMove M; 00171 VRPMove BestM; 00172 int j,k; 00173 int accept_type; 00174 00175 BestM.savings=VRP_INFINITY; 00176 00177 if(r1==r2) 00178 { 00179 fprintf(stderr,"TPM::%d==%d???\n",r1,r2); 00180 report_error("%s: called with r1==r2\n",__FUNCTION__); 00181 } 00182 00183 if( (rules & VRPH_USE_NEIGHBOR_LIST) > 0) 00184 report_error("%s: ROUTE_BASED search does not use neighbor_list\n",__FUNCTION__); 00185 00186 accept_type=VRPH_FIRST_ACCEPT;//default 00187 00188 if( (rules & VRPH_FIRST_ACCEPT) > 0) 00189 accept_type=VRPH_FIRST_ACCEPT; 00190 if( (rules & VRPH_BEST_ACCEPT) > 0) 00191 accept_type=VRPH_BEST_ACCEPT; 00192 if( (rules & VRPH_LI_ACCEPT) > 0) 00193 accept_type=VRPH_LI_ACCEPT; 00194 00195 00196 j= V->route[r1].start; 00197 while(j!=VRPH_DEPOT) 00198 { 00199 00200 k= V->route[r2].start; 00201 while(k!=VRPH_DEPOT) 00202 { 00203 // Try to swap nodes j and k 00204 if(evaluate(V,j,k,rules,&M)==true) 00205 { 00206 // valid move found 00207 if(accept_type == VRPH_FIRST_ACCEPT || (accept_type==VRPH_LI_ACCEPT && M.savings<-VRPH_EPSILON) ) 00208 { 00209 // make the move 00210 if(move(V,&M)==false) 00211 report_error("%s: first accept move is false!\n",__FUNCTION__); 00212 else 00213 return true; 00214 } 00215 00216 if( (accept_type == VRPH_LI_ACCEPT) || (accept_type==VRPH_BEST_ACCEPT) ) 00217 { 00218 00219 // See if it's the best so far... 00220 if(M.is_better(V, &BestM, rules)) 00221 BestM=M; 00222 } 00223 00224 00225 } 00226 // Advance the route r2 node 00227 k=VRPH_MAX(V->next_array[k],0); 00228 } 00229 // Advance the route r1 node 00230 j=VRPH_MAX(V->next_array[j],0); 00231 } 00232 00233 00234 if(accept_type==VRPH_FIRST_ACCEPT) 00235 return false; // No moves found 00236 if(BestM.savings == VRP_INFINITY) 00237 return false; 00238 00239 if( (accept_type == VRPH_LI_ACCEPT) || (accept_type == VRPH_BEST_ACCEPT)) 00240 { 00241 00242 // We found a move -- make it... 00243 if(move(V,&BestM)==false) 00244 report_error("%s: best move is false!\n",__FUNCTION__); 00245 else 00246 return true; 00247 00248 } 00249 00250 report_error("%s: shouldn't be here...\n",__FUNCTION__); 00251 00252 return false; 00253 00254 } 00255 00256 bool TwoPointMove::evaluate(class VRP *V, int j, int b, int rules, VRPMove *M) 00257 { 00264 00265 V->num_evaluations[TWO_POINT_MOVE_INDEX]++; 00266 00267 if(V->routed[j]==false || V->routed[b]==false || j==b) 00268 return false; 00269 00270 if(rules & VRPH_FIXED_EDGES) 00271 { 00272 // Make sure we aren't disturbing fixed edges 00273 int i,k,a,c; 00274 00275 a=VRPH_MAX(V->pred_array[b],VRPH_DEPOT); 00276 c=VRPH_MAX(V->next_array[b],VRPH_DEPOT); 00277 00278 i=VRPH_MAX(V->pred_array[j],VRPH_DEPOT); 00279 k=VRPH_MAX(V->next_array[j],VRPH_DEPOT); 00280 00281 if( V->fixed[a][b] || V->fixed[b][c] || V->fixed[i][j] || V->fixed[j][k] ) 00282 return false; 00283 } 00284 00285 M->evaluated_savings=false;// false until we check 00286 00287 00288 class Swap swap; 00289 00290 if(V->routed[j]==false || V->routed[b]==false) 00291 return false; 00292 00293 if(j==VRPH_DEPOT || b==VRPH_DEPOT || j==b) 00294 { 00295 fprintf(stderr,"TPM::j=%d, b=%d\n",j,b); 00296 report_error("%s: evaluate() called with bad arguments??\n",__FUNCTION__); 00297 } 00298 00299 if((rules & VRPH_INTER_ROUTE_ONLY) && (V->route_num[j]==V->route_num[b]) ) 00300 return false; 00301 00302 if((rules & VRPH_INTRA_ROUTE_ONLY) && (V->route_num[j]!=V->route_num[b]) ) 00303 return false; 00304 00305 00306 if( (swap.evaluate(V,j,b,M)==true) && (V->check_move(M, rules)==true)) 00307 { 00308 return true; 00309 // The move is good 00310 } 00311 else 00312 { 00313 // Not allowed 00314 return false; 00315 } 00316 00317 } 00318 00319 00320 bool TwoPointMove::move(class VRP *V, VRPMove *M) 00321 { 00322 00326 00327 if(M->move_type!=SWAP) 00328 report_error("%s: Unknown move type\n",__FUNCTION__); 00329 00330 class Swap swap; 00331 00332 if(swap.move(V,M->move_arguments[0], M->move_arguments[1])==false) 00333 { 00334 // This is an error 00335 report_error("%s: TPM::swap.move evaluates to false!!\n",__FUNCTION__); 00336 00337 } 00338 00339 V->capture_best_solution(); 00340 V->num_moves[TWO_POINT_MOVE_INDEX]++; 00341 00342 return true; 00343 00344 } 00345