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