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 VRPMove::VRPMove() 00016 { 00017 this->evaluated_savings=false; 00018 this->move_type=-1; 00019 this->new_total_route_length=VRP_INFINITY; 00020 this->num_affected_routes=-1; 00021 this->num_arguments=-1; 00022 this->savings=-1; 00023 this->total_number_of_routes=-1; 00024 00025 this->arrival_times=NULL; 00026 00027 } 00028 00029 VRPMove::VRPMove(int n) 00030 { 00031 this->evaluated_savings=false; 00032 this->move_type=-1; 00033 this->new_total_route_length=VRP_INFINITY; 00034 this->num_affected_routes=-1; 00035 this->num_arguments=-1; 00036 this->savings=-1; 00037 this->total_number_of_routes=-1; 00038 00039 this->arrival_times=new double[n]; // Set up for time windows for each customer 00040 } 00041 00042 VRPMove::~VRPMove() 00043 { 00044 if(this->arrival_times) 00045 delete [] this->arrival_times; 00046 } 00047 00048 00049 bool VRPMove::is_better(VRP *V, VRPMove *M2, int rules) 00050 { 00056 00057 if(M2->num_affected_routes==-1) 00058 { 00059 // M2 does not have meaningful information, so return true 00060 // Probably has savings=VRP_INFINITY 00061 return true; 00062 } 00063 00064 00065 // We are only concerned about the savings (increase/decrese) in total length 00066 // This is the default approach 00067 if(rules & VRPH_SAVINGS_ONLY) 00068 { 00069 // Decide in terms of total length only 00070 00071 if(this->savings <= M2->savings) 00072 return true; 00073 else 00074 return false; 00075 00076 } 00077 00078 00079 // We will try to maximize the sum of the squares of the # of customers on a route 00080 if(rules & VRPH_MINIMIZE_NUM_ROUTES) 00081 { 00082 // First check the # of routes in the solution produced by the two moves 00083 if(this->total_number_of_routes<M2->total_number_of_routes) 00084 return true; 00085 00086 if(this->total_number_of_routes>M2->total_number_of_routes) 00087 return false; 00088 00089 // Otherwise the # of routes remains the same 00090 // If the two moves affect diff. #'s of routes, then just use the total length 00091 if(this->num_affected_routes != M2->num_affected_routes) 00092 { 00093 if(this->savings < M2->savings) 00094 return true; 00095 else 00096 return false; 00097 } 00098 00099 // If they affect the same # of routes, minimize the sum of the squares 00100 // of the customers in the route 00101 00102 int i,sq, sq2; 00103 00104 sq=0; sq2=0; 00105 for(i=0;i<this->num_affected_routes;i++) 00106 sq+= (this->route_custs[i])*(this->route_custs[i]); 00107 00108 for(i=0;i<M2->num_affected_routes;i++) 00109 sq2+= (M2->route_custs[i])*(M2->route_custs[i]); 00110 00111 if(sq>sq2) 00112 // this move is better 00113 return true; 00114 if(sq2<sq) 00115 // M2 is better 00116 return false; 00117 00118 // Otherwise, sq==sq2, use the savings 00119 00120 if(this->savings <= M2->savings) 00121 return true; 00122 else 00123 return false; 00124 } 00125 00126 00127 // Shouldn't get here! 00128 report_error("%s: Reached bizarre place with rules=%08x\n",__FUNCTION__,rules); 00129 return false; 00130 00131 } 00132