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 double VRPDistance(int type, double x1, double y1, double x2, double y2) 00016 { 00020 00021 // This variation handles 2D cases 00022 // Type refers to the type of distance function used in the 00023 // problem instance. 00024 00025 double xd, yd; 00026 00027 switch(type) 00028 { 00029 case VRPH_CEIL_2D: 00030 return ceil(sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))); 00031 00032 case VRPH_MAX_2D: 00033 xd=VRPH_ABS(x1-x2); 00034 yd=VRPH_ABS(y1-y2); 00035 return VRPH_MAX(xd,yd); 00036 00037 case VRPH_MAN_2D: 00038 xd=VRPH_ABS(x1-x2); 00039 yd=VRPH_ABS(y1-y2); 00040 return xd+yd; 00041 00042 case VRPH_EUC_2D: 00043 xd=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))-floor(sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))); 00044 if(xd>=.5) 00045 return ceil(sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))); 00046 else 00047 return floor(sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))); 00048 00049 00050 case VRPH_GEO: 00051 // Taken from Concorde code 00052 double lat1, lat2, long1, long2; 00053 double q1, q2, q3, q4, q5; 00054 00055 lat1 = VRPH_PI * x1 / 180.0; 00056 lat2 = VRPH_PI * x2 / 180.0; 00057 00058 long1 = VRPH_PI * y1 / 180.0; 00059 long2 = VRPH_PI * y2 / 180.0; 00060 00061 q1 = cos (lat2) * sin(long1 - long2); 00062 q3 = sin((long1 - long2)/2.0); 00063 q4 = cos((long1 - long2)/2.0); 00064 q2 = sin(lat1 + lat2) * q3 * q3 - sin(lat1 - lat2) * q4 * q4; 00065 q5 = cos(lat1 - lat2) * q4 * q4 - cos(lat1 + lat2) * q3 * q3; 00066 return (VRPH_RRR * atan2(sqrt(q1*q1 + q2*q2), q5) + 1.0); 00067 // Note - divided this by 1000?? 00068 00069 case VRPH_EXACT_2D: 00070 return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); 00071 } 00072 00073 fprintf(stderr,"Unknown distance function specified: %d\n",type); 00074 report_error("%s\n",__FUNCTION__); 00075 return -1; 00076 } 00077 00078 int VRPDistanceCompare(const void *a, const void *b) 00079 { 00083 00084 double *d1; 00085 double *d2; 00086 00087 d1=(double *)a; 00088 d2=(double *)b; 00089 00090 if(d1>d2) 00091 return -1; 00092 else 00093 return 1; 00094 00095 } 00096 00097 int VRPIntCompare(const void *a, const void *b) 00098 { 00102 00103 return ( *(int*)a - *(int*)b ); 00104 00105 } 00106 00107 int double_int_compare(const void *a, const void *b) 00108 { 00112 00113 struct double_int *s1; 00114 struct double_int *s2; 00115 00116 s1=(struct double_int *)a; 00117 s2=(struct double_int *)b; 00118 00119 if(s1->d > s2->d) 00120 return 1; 00121 else 00122 return -1; 00123 } 00124 00125 00126 int int_int_compare(const void *a, const void *b) 00127 { 00131 00132 struct int_int *s1; 00133 struct int_int *s2; 00134 00135 s1=(struct int_int *)a; 00136 s2=(struct int_int *)b; 00137 00138 if(s1->j > s2->j) 00139 return 1; 00140 else 00141 return -1; 00142 } 00143 00144 int VRPSavingsCompare (const void *a, const void *b) 00145 { 00149 00150 class VRPSavingsElement *s1; 00151 class VRPSavingsElement *s2; 00152 00153 s1= (class VRPSavingsElement *)a; 00154 s2= (class VRPSavingsElement *)b; 00155 00156 if( s1->savings > s2->savings) 00157 return -1; 00158 else 00159 { 00160 if(s1->savings < s2->savings) 00161 return 1; 00162 else 00163 return 0; 00164 } 00165 00166 } 00167 00168 int VRPNeighborCompare (const void *a, const void *b) 00169 { 00173 00174 VRPNeighborElement *s1; 00175 VRPNeighborElement *s2; 00176 00177 s1= (VRPNeighborElement *)a; 00178 s2= (VRPNeighborElement *)b; 00179 00180 if( s1->val > s2->val) 00181 return 1; 00182 else 00183 { 00184 if( s1->val <= s2->val) 00185 return -1; 00186 else 00187 return 0; 00188 00189 } 00190 } 00191 00192 int VRPSolutionCompare(const void *a, const void *b) 00193 { 00197 VRPSolution *s1; 00198 VRPSolution *s2; 00199 00200 s1=(VRPSolution*)a; 00201 s2=(VRPSolution*)b; 00202 00203 if( s1->obj > s2->obj) 00204 return 1; 00205 00206 if( s1->obj <= s2->obj) 00207 return -1; 00208 else 00209 return 0; 00210 } 00211 00212 int VRPAlphaCompare(const void *a, const void *b) 00213 { 00217 00218 return( strcmp(*(char **)a, *(char **)b) ); 00219 } 00220 00221 int VRPRouteCompare(const void *a, const void *b) 00222 { 00223 00227 00228 VRPRoute *s1; 00229 VRPRoute *s2; 00230 00231 s1=(VRPRoute*)a; 00232 s2=(VRPRoute*)b; 00233 00234 if( s1->length> s2->length) 00235 return 1; 00236 00237 if( s1->length <= s2->length) 00238 return -1; 00239 else 00240 // impossible 00241 return 0; 00242 00243 00244 } 00245