VRPH  1.0
src/VRPMove.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 VRPMove::VRPMove()
00016 {
00017     this->evaluated_savings=false;
00018     this->move_type=-1;
00019     this->new_total_route_length=VRP_INFINITY;
00020     this->num_affected_routes=-1;
00021     this->num_arguments=-1;
00022     this->savings=-1;
00023     this->total_number_of_routes=-1;
00024 
00025     this->arrival_times=NULL;
00026     
00027 }
00028 
00029 VRPMove::VRPMove(int n)
00030 {
00031     this->evaluated_savings=false;
00032     this->move_type=-1;
00033     this->new_total_route_length=VRP_INFINITY;
00034     this->num_affected_routes=-1;
00035     this->num_arguments=-1;
00036     this->savings=-1;
00037     this->total_number_of_routes=-1;
00038 
00039     this->arrival_times=new double[n]; // Set up for time windows for each customer
00040 }
00041 
00042 VRPMove::~VRPMove()
00043 {
00044     if(this->arrival_times)
00045         delete [] this->arrival_times;
00046 }
00047 
00048 
00049 bool VRPMove::is_better(VRP *V, VRPMove *M2, int rules)
00050 {
00056 
00057     if(M2->num_affected_routes==-1)
00058     {
00059         // M2 does not have meaningful information, so return true
00060         // Probably has savings=VRP_INFINITY
00061         return true;
00062     }
00063 
00064 
00065     // We are only concerned about the savings (increase/decrese) in total length
00066     // This is the default approach
00067     if(rules & VRPH_SAVINGS_ONLY)
00068     {
00069         // Decide in terms of total length only
00070 
00071         if(this->savings <= M2->savings)
00072             return true;
00073         else
00074             return false;
00075         
00076     }
00077 
00078 
00079     // We will try to maximize the sum of the squares of the # of customers on a route
00080     if(rules & VRPH_MINIMIZE_NUM_ROUTES)
00081     {
00082         // First check the # of routes in the solution produced by the two moves
00083         if(this->total_number_of_routes<M2->total_number_of_routes)
00084             return true;
00085 
00086         if(this->total_number_of_routes>M2->total_number_of_routes)
00087             return false;
00088 
00089         // Otherwise the # of routes remains the same
00090         // If the two moves affect diff. #'s of routes, then just use the total length
00091         if(this->num_affected_routes != M2->num_affected_routes)
00092         {
00093             if(this->savings < M2->savings)
00094                 return true;
00095             else
00096                 return false;    
00097         }
00098 
00099         // If they affect the same # of routes, minimize the sum of the squares
00100         // of the customers in the route
00101 
00102         int i,sq, sq2;
00103 
00104         sq=0; sq2=0;
00105         for(i=0;i<this->num_affected_routes;i++)
00106             sq+= (this->route_custs[i])*(this->route_custs[i]);
00107 
00108         for(i=0;i<M2->num_affected_routes;i++)
00109             sq2+= (M2->route_custs[i])*(M2->route_custs[i]);
00110 
00111         if(sq>sq2)
00112             // this move is better
00113             return true;
00114         if(sq2<sq)
00115             // M2 is better
00116             return false;
00117 
00118         // Otherwise, sq==sq2, use the savings
00119 
00120         if(this->savings <= M2->savings)
00121             return true;
00122         else
00123             return false;    
00124     }
00125 
00126 
00127     // Shouldn't get here!
00128     report_error("%s: Reached bizarre place with rules=%08x\n",__FUNCTION__,rules);
00129     return false;
00130 
00131 }
00132