VRPH  1.0
src/Concatenate.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 
00013 #include "VRPH.h"
00014 
00015 bool Concatenate::evaluate(VRP *V, int i_route, int j_route, int rules, VRPMove *M)
00016 {
00017 
00030     
00031     
00032     double new_length, i_length, j_length;
00033     int new_load, i_load, j_load;
00034     int i,j;
00035 
00036     // First make sure that the routes are in the correct form
00037     // i must be after the VRPH_DEPOT and j must be before the VRPH_DEPOT
00038 
00039     i= V->route[i_route].start;
00040     j= V->route[j_route].end;
00041 
00042 
00043     if(VRPH_MAX(V->pred_array[i],0) != VRPH_DEPOT || VRPH_MAX(V->next_array[j],0)!=VRPH_DEPOT)
00044     {
00045         report_error("%s: Concatenate::error in the start/end nodes!\n");
00046     }
00047 
00048     i_length = V->route[i_route].length;
00049     j_length = V->route[j_route].length;
00050     i_load = V->route[i_route].load;
00051     j_load = V->route[j_route].load;
00052 
00053     new_length = j_length + i_length + V->d[j][i] - (V->d[VRPH_DEPOT][i] +
00054         V->d[j][VRPH_DEPOT]);
00055         
00056     new_load = i_load + j_load;
00057 
00058     
00059 
00060     M->num_affected_routes=2;
00061     M->route_nums[0]=i_route;
00062     M->route_nums[1]=j_route;
00063     M->savings = new_length - (i_length+j_length);//new - old
00064     // Lengths and loads are the same since we merged and there is really only one route now
00065     M->route_lens[0]=new_length;
00066     M->route_lens[1]=0;
00067     M->route_loads[0]=new_load;
00068     M->route_loads[1]=0;
00069     M->route_custs[0]= V->route[i_route].num_customers+V->route[j_route].num_customers;
00070     M->route_custs[1]=0;
00071     M->new_total_route_length= V->total_route_length+M->savings;
00072     M->total_number_of_routes= V->total_number_of_routes-1;// We destroyed a route!
00073     M->move_type=CONCATENATE;
00074     M->num_arguments=2;
00075     M->move_arguments[0]=i_route;
00076     M->move_arguments[1]=j_route;
00077 
00078     if(V->is_feasible(M, rules)==true)
00079         return true;
00080     else
00081         return false;
00082     
00083 }
00084 
00085 bool Concatenate::move(VRP *V, int i_route, int j_route)
00086 {
00090     
00091     VRPMove M;
00092     int i,j, pre_i, pre_j, post_i, post_j, end_i, start_j, route_after_i,
00093         route_after_j, route_before_i, route_before_j, current_node, next_node;
00094 
00095     i= V->route[i_route].start;
00096     j= V->route[j_route].end;
00097     // First, evaluate the move
00098 
00099     int rules=0; 
00100     if(evaluate(V,i_route,j_route, rules, &M)==false)
00101         return false;    // the move is not allowed
00102 
00103     // Otherwise, it's feasible - make the move
00104 
00105     V->update(&M);
00106 
00107     // Modify the arrays
00108     
00109     // pre_i is what used to be before i
00110     pre_i= V->pred_array[i];
00111     // post_i is what used to be after i
00112     post_i= V->next_array[i];
00113     // pre_j is what used to be before j
00114     pre_j= V->pred_array[j];
00115     // post_j is what used to be after j
00116     post_j= V->next_array[j];
00117 
00118     // i is the start of its own route!
00119     end_i= V->route[i_route].end;
00120 
00121     // j is the end of its own route!
00122     start_j= V->route[j_route].start;
00123     
00124     // This is the first node in the route that used to follow i
00125     route_after_i= V->next_array[end_i];
00126     // This is the last node in the route that used to precede i;
00127     route_before_i=pre_i;
00128     
00129     // This is the first node in the route that used to precede j
00130     route_before_j= V->pred_array[start_j];
00131     // This is the first node in the route that used to follow j
00132     route_after_j=post_j;
00133 
00134     // 1-i-a-b-c-...-x-1
00135     // and
00136     // 1-aa-bb-...-zz-j-1
00137     // becomes
00138     // 1-aa-bb-...-zz-j-i-a-b-c-...-x-1
00139 
00140     V->next_array[j]=i;
00141     V->pred_array[i]=j;
00142 
00143     if(VRPH_ABS(route_after_j)==i)
00144     {
00145         current_node=start_j;
00146         while( (next_node= V->next_array[current_node]) > 0)
00147         {
00148             V->route_num[current_node]=i_route;
00149 
00150             current_node=next_node;
00151         }
00152 
00153         V->route_num[current_node]=i_route;
00154         // Update i_route information
00155         V->route[i_route].end=end_i;
00156         V->route[i_route].start=start_j;
00157         
00158 #if CONCATENATE_VERIFY
00159         V->verify_routes("Concatenate 1\n");
00160 #endif
00161         
00162         return true;        
00163     }
00164 
00165     if(VRPH_ABS(route_after_i)!=start_j)
00166     {
00167         V->next_array[VRPH_ABS(route_before_i)]=route_after_i;
00168         V->pred_array[VRPH_ABS(route_after_i)]=route_before_i;
00169         V->next_array[VRPH_ABS(end_i)]=route_after_j;
00170         V->pred_array[VRPH_ABS(route_after_j)]=-end_i;
00171     }
00172     else
00173     {
00174         // Must have i in first position of its route
00175         // j is the very next route with j in last position
00176         V->next_array[VRPH_ABS(route_before_i)]=-start_j;
00177         V->pred_array[VRPH_ABS(start_j)]=route_before_i;
00178         V->next_array[VRPH_ABS(end_i)]=post_j;
00179         // changed!
00180         V->pred_array[VRPH_ABS(post_j)]=-end_i;
00181     }
00182 
00183     // So new start is start(j) and new end is end(i)
00184     // Now update the rest of the start and end arrays
00185     current_node=start_j;
00186     while( (next_node= V->next_array[current_node]) > 0)
00187     {
00188         V->route_num[current_node]=i_route;
00189         current_node=next_node;
00190     }
00191 
00192     V->route_num[current_node]=i_route;
00193     // Update route information
00194     V->route[i_route].end=end_i;
00195     V->route[i_route].start=start_j;
00196     
00197 
00198     
00199 #if CONCATENATE_VERIFY
00200     V->verify_routes("CWConcatenate 2\n");
00201 #endif
00202     
00203     return true;
00204 
00205 }
00206 
00207