pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
vrppdtw/src/Solution.h
1 /*PGR
2 
3 Copyright (c) 2014 Manikata Kondeti
4 mani.iiit123@gmail.com
5 
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10 
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15 
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
19 
20 */
21 
22 #ifndef _SOLUTION_H
23 #define _SOLUTION_H
24 
25 #include <vector>
26 #include <map>
27 #include <queue>
28 #include <string>
29 #include <stdlib.h>
30 #include <iostream>
31 #include <algorithm>
32 #include <math.h>
33 #include <stdio.h>
34 #include <string.h>
35 #include <set>
36 
37 #include "./Route.h"
38 
39 class Solution{
40  public:
41  Solution(){
42  route_length=0,cost_total=0,twv_total=0,cv_total=0,dis_total=0;
43  }
44  //Variables
45  int twv_total;
46  int cv_total;
47  int dis_total;
48  double cost_total;
49  std::vector<Route> r;
50  int route_length;
51  //Methods
52  void dump();
53  double getCost();
54  Solution getBestofNeighborhood(Solution S, customer *c, depot d, Pickup *p,int CustomerLength, int PickupLength);
55  void UpdateSol();
56 
57 };
58 class Neighborhoods{
59  public:
60  Neighborhoods(){}
61  Solution BestSPI(Solution S, customer *c, depot d, Pickup *p, int CustomerLength, int PickupLength);
62 };
63 
64 
65 
66 void Solution::UpdateSol()
67 {
68  cost_total=0,twv_total=0,cv_total=0,dis_total=0;
69  int routes_del=0;
70  for(int i=0;i<route_length;i++)
71  {
72  twv_total+=r[i].twv;
73  dis_total+=r[i].dis;
74  cv_total+=r[i].cv;
75  cost_total+=r[i].cost();
76  if(r[i].path_length==0)
77  {
78  routes_del++;
79  r.erase(r.begin()+i);
80  }
81  }
82  route_length=route_length-routes_del;
83  return;
84 }
85 
86 
87 //Methods in Solution
88 
89 #if 0
90 void Solution::dump(){
91  printf("Routes Length=%d ",route_length);
92  printf("Total Cost=%lf ",cost_total);
93  printf("Total Distance=%d \n",dis_total);
94  printf("Routes \n");
95  for(int i=0;i<route_length;i++)
96  {
97  printf("Route::%d ",i);
98  printf("TWV=%d CV=%d DIS=%d [ ",r[i].twv,r[i].cv,r[i].dis);
99  for(int j=0;j<r[i].path_length;j++)
100  {
101  printf("%d ",r[i].path[j]);
102  }
103  printf("]\n");
104  }
105  return;
106 }
107 #endif
108 
109 double Solution::getCost(){
110  cost_total=0;
111  for(unsigned int i=0;i<r.size();i++)
112  {
113  cost_total+=r[i].cost();
114  }
115  return cost_total;
116 }
117 
118 Solution Solution::getBestofNeighborhood(Solution S, customer *c, depot d, Pickup *p, int CustomerLength, int PickupLength){
119  // printf("twv_total=%lf\n",S.cost_total);
120  Neighborhoods N;
121  Solution S1;
122  S1=N.BestSPI(S,c,d,p,CustomerLength,PickupLength);
123  return S1;
124 }
125 
126 
127 
128 Solution Neighborhoods::BestSPI(Solution S, customer *c, depot d, Pickup *p, int CustomerLength, int PickupLength){
129  Solution CurrSol,BestSol,TempSol;
130  CurrSol=BestSol=S;
131  Pickup *OrderRequests=NULL;
132  OrderRequests= (Pickup *)malloc(2000*sizeof(Pickup));
133  int Ro_flag,Hc_flag;
134  State TempState;
135  //Copy Order requests from pickup's
136  for(int order=1;order<=PickupLength;order++)
137  {
138  OrderRequests[order]=p[order];
139  }
140 
141  //Main SPI
142  for(int order=1;order<=PickupLength;order++)
143  {
144  //Order Find and Remove it!
145  for(unsigned int route_remove=0;route_remove<CurrSol.r.size();route_remove++)
146  {
147  Ro_flag=CurrSol.r[route_remove].RemoveOrder(OrderRequests[order]);
148  TempSol=CurrSol;
149  if(Ro_flag==1)
150  {
151  //Insert, Total Cost, (if it is more copy back the solution) , (else store best=temp, checked=2, break )
152  for(unsigned int route=0;route<CurrSol.r.size();route++)
153  {
154  TempState=CurrSol.r[route].append(c,OrderRequests[order],d,CustomerLength, PickupLength,TempState);
155  Hc_flag=CurrSol.r[route].insertOrder(c,d,OrderRequests[order]);
156  // Hc flag tells us about insertion
157  if(Hc_flag==0)
158  {
159  if(CurrSol.r[route].cost() <= BestSol.r[route].cost())
160  {
161  CurrSol.UpdateSol();
162  BestSol=CurrSol;
163  }
164  }
165  TempSol.UpdateSol();
166  CurrSol=TempSol;
167  // CurrSol = BestSol;
168  }
169  BestSol.UpdateSol();
170  CurrSol = BestSol;
171  break;
172  }
173  else
174  {
175  continue;
176  }
177  }
178  }
179  BestSol.UpdateSol();
180  return BestSol;
181 }
182 
183 
184 
185 #endif
Definition: pdp.hpp:44
Definition: pdp.hpp:57
Definition: pdp.hpp:31