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 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 // First make sure that we have normalized everything so that VRPH_DEPOT is at 00037 // origin 00038 if(V->depot_normalized==false) 00039 report_error("%s: Node locations must be normalized to run sweep\n",__FUNCTION__); 00040 00041 // Begin by creating default routes - only supports full problems for now 00042 V->create_default_routes(); 00043 00044 int i,pos; 00045 int n=V->num_original_nodes; 00046 00047 // Create a sorted list of nodes and thetas 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;// k is the index 00053 T[i].d=V->nodes[i+1].theta;// d is theta 00054 } 00055 00056 // Sort by theta 00057 qsort(T,n,sizeof(double_int),double_int_compare); 00058 00059 // We will start at a random place in this list and then "wrap around" 00060 // Pick a starting point 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 // At least 1 move is feasible 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 // Both feasible - pick the best move 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 // Couldn't add before or after - start a new route 00103 // We don't have to do anything here since we started w/ default 00104 // singleton routes 00105 00106 } 00107 } 00108 00109 00110 return true; 00111 } 00112