00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00012
00013 #include "VRPH.h"
00014
00015 struct sweep_node
00016 {
00017 double theta;
00018 int index;
00019 };
00020
00021 Sweep::Sweep()
00022 {
00023
00024 }
00025
00026 bool Sweep::Construct(class VRP *V)
00027 {
00035
00036
00037
00038 if(V->depot_normalized==false)
00039 report_error("%s: Node locations must be normalized to run sweep\n",__FUNCTION__);
00040
00041
00042 V->create_default_routes();
00043
00044 int i,pos;
00045 int n=V->num_original_nodes;
00046
00047
00048 double_int *T;
00049 T = new double_int[n+1];
00050 for(i=0;i<n;i++)
00051 {
00052 T[i].k=i+1;
00053 T[i].d=V->nodes[i+1].theta;
00054 }
00055
00056
00057 qsort(T,n,sizeof(double_int),double_int_compare);
00058
00059
00060
00061 int start = VRPH_MIN(V->num_original_nodes, (int)(n*(lcgrand(5))));
00062
00063 Postsert postsert;
00064 Presert presert;
00065 VRPMove M1, M2;
00066 bool post,pre;
00067
00068
00069 for(i=0;i<n;i++)
00070 {
00071 pos=start+i;
00072
00073 #if SWEEP_DEBUG
00074 printf("%5.2f: pos=%d: Trying to insert %d after %d\n",V->total_route_length,
00075 pos%n, T[(pos+1)%n].k, T[pos%n].k);
00076 #endif
00077
00078 post=postsert.evaluate(V,T[(pos+1)%n].k, T[pos%n].k, &M1);
00079 pre=presert.evaluate(V,T[(pos+1)%n].k, T[pos%n].k, &M2);
00080
00081 if(post || pre)
00082 {
00083
00084 if(post==true && pre==false)
00085 postsert.move(V,T[(pos+1)%n].k, T[pos%n].k);
00086 else
00087 {
00088 if(post==false && pre==true)
00089 presert.move(V,T[(pos+1)%n].k, T[pos%n].k);
00090 else
00091 {
00092
00093 if(M1.savings<=M2.savings)
00094 postsert.move(V,T[(pos+1)%n].k, T[pos%n].k);
00095 else
00096 presert.move(V,T[(pos+1)%n].k, T[pos%n].k);
00097 }
00098 }
00099 }
00100 else
00101 {
00102
00103
00104
00105
00106 }
00107 }
00108
00109
00110 return true;
00111 }
00112