VRPH  1.0
src/Flip.cpp
Go to the documentation of this file.
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 #include "VRPH.h"
00013 
00014 
00015 
00016 bool Flip::evaluate(class VRP *V, int start_point, int end_point, VRPMove *M)
00017 {    
00027 
00028     int post_start, pre_end, route_num;
00029     double old_cost, new_cost;
00030     double savings, route_len;
00031 
00032     //Check for VRPH_DEPOT nodes!
00033     if(start_point==VRPH_DEPOT || end_point==VRPH_DEPOT)
00034         report_error("%s: flip::called with VRPH_DEPOT node-ambiguous\n");
00035 
00036     route_num= V->route_num[start_point];
00037 
00038     if(V->route_num[end_point]!=route_num)
00039     {
00040         fprintf(stderr,"%d(route #=%d), %d(route #=%d)\n",start_point, route_num,
00041             end_point, V->route_num[end_point]);
00042 
00043         report_error("%s: flip attempted using different routes!\n");
00044     }
00045 
00046     if(V->next_array[start_point]==end_point)
00047         return false;
00048 
00049     post_start= VRPH_MAX(V->next_array[start_point],VRPH_DEPOT);
00050     pre_end= VRPH_MAX(V->pred_array[end_point],VRPH_DEPOT);
00051 
00052     if(post_start == pre_end || post_start==end_point || pre_end==start_point)
00053         return false;    // Nothing to reverse!
00054 
00055 
00056     // Need to compute the old costs and the new cost - 
00057 
00058     old_cost=(V->d[start_point][post_start]-1*V->nodes[post_start].service_time) + 
00059         (V->d[pre_end][end_point] -  1*V->nodes[end_point].service_time) ;
00060     new_cost=(V->d[start_point][pre_end]-1*V->nodes[pre_end].service_time) + 
00061         (V->d[post_start][end_point] - 1*V->nodes[end_point].service_time);
00062 
00063     savings=new_cost - old_cost;
00064     
00065     // The move satisfies the savings rules - now check feasibility...
00066 
00067     route_len= V->route[route_num].length;
00068 
00069     // Check feasibility
00070     route_len=route_len+savings;
00071 
00072     if(route_len>V->max_route_length)
00073         return false;    // infeasible
00074 
00075     // Otherwise it's feasible since no load change occurs
00076     M->num_affected_routes=1;
00077     M->savings=savings;
00078     M->route_nums[0]=route_num;
00079     M->route_lens[0]=route_len;
00080     M->route_loads[0]=V->route[route_num].load;
00081     M->route_custs[0]= V->route[route_num].num_customers; // no change
00082     M->new_total_route_length= V->total_route_length+savings;
00083     M->total_number_of_routes = V->total_number_of_routes;
00084     M->move_type=FLIP;
00085     M->num_arguments=2;
00086     M->move_arguments[0]=start_point;
00087     M->move_arguments[1]=end_point;
00088 
00089 
00090     return true;
00091 
00092 }
00093 
00094 bool Flip::move(VRP *V, int start_point, int end_point)
00095 {
00101 
00102     int current, old_next, cnt;
00103     int start, end, i, route_num;
00104     VRPMove M;
00105 
00106     if(start_point<=VRPH_DEPOT || end_point<=VRPH_DEPOT )
00107         report_error("%s: flip::reverse_partial_route called with VRPH_DEPOT or negative index\n");
00108 
00109     if(start_point==end_point)
00110         report_error("%s: flip::reverse_partial_route called with start==end\n");
00111 
00112     route_num= V->route_num[start_point];
00113 
00114     if(route_num!= V->route_num[end_point])
00115         report_error("%s: flip::not in the same route\n");
00116 
00117     // evaluate the move
00118     if(evaluate(V,start_point,end_point, &M)==false)
00119         return false;
00120 
00121     V->update(&M);
00122 
00123     // Now update the arrays
00124 
00125     i=0;
00126 
00127     start = start_point;
00128     end = end_point;
00129     // Assume the orientation is correct to avoid checking again!!
00130 
00131     // Special case!  next(start) = end
00132     if(VRPH_MAX(VRPH_DEPOT,V->next_array[start])==end)
00133     {
00134         int pre_start= V->pred_array[start];
00135 
00136         if(pre_start<0)
00137             report_error("%s: flip::pre_start <0 in special case!!\n");
00138 
00139         old_next= V->next_array[end];
00140 
00141         V->next_array[end]=start;
00142         V->pred_array[start]=end;
00143 
00144         V->next_array[start]=old_next;
00145         V->pred_array[old_next]=start;
00146 
00147         V->next_array[pre_start]=end;
00148         V->pred_array[end]=pre_start;
00149 
00150 #if FLIP_VERIFY
00151         V->verify_routes("flip 1\n");
00152 #endif
00153 
00154         return true;
00155 
00156     }
00157 
00158     // Otherwise we have only a single case to handle
00159     current= V->next_array[start];        //n1
00160     old_next= V->next_array[current];    //n2
00161 
00162 
00163     V->next_array[current]=end;        //next[n1]=end
00164     V->pred_array[end]=current;        //pred[end]=n1;
00165     V->pred_array[current]=old_next;    //pred[n1]=n2;
00166     current=old_next;                            //current=n2
00167     old_next= V->next_array[current];    //old_next=n3
00168 
00169     cnt=0;
00170 
00171     while(old_next != end)
00172     {
00173 
00174         V->next_array[current] = V->pred_array[current];
00175         V->pred_array[current]=old_next;
00176         current = old_next;
00177         old_next = V->next_array[current];
00178         cnt++;
00179         if(cnt>V->num_nodes)
00180             report_error("%s: flip::Impossible loop encountered\n");
00181 
00182     }
00183     V->next_array[current]= V->pred_array[current];
00184     V->pred_array[current]=start;
00185     V->next_array[start]=current;
00186 
00187     return true;
00188 }