VRPH  1.0
src/VRPUtils.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 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