pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
vrppdtw/src/Route.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 
23 #ifndef _ROUTE_H
24 #define _ROUTE_H
25 
26 #include <vector>
27 #include <map>
28 #include <queue>
29 #include <string>
30 #include <stdlib.h>
31 #include <iostream>
32 #include <algorithm>
33 #include <math.h>
34 #include <stdio.h>
35 #include <string.h>
36 #include <set>
37 
38 class Route
39 {
40  public:
41  int twv;
42  int cv;
43  int dis;
44  int path[1200];
45  int order[1200];
46  int path_length;
47  Route()
48  {
49  twv=0;
50  cv=0;
51  dis=0;
52  path_length=0;
53  for(int i=0;i<1000;i++)
54  {
55  path[i]=0;
56  order[i]=0;
57  }
58  }
59  State append(customer *c, Pickup p, depot d,int CustomerLength, int PickupLength, State S);
60  void update(customer *c,depot d);
61  double cost();
62  int HillClimbing(customer *c,depot d,Pickup p);
63  int insertOrder(customer *c,depot d,Pickup p);
64  void remove(State S);
65  // void print();
66  int RemoveOrder(Pickup p);
67 };
68 
69 
70 
71 int Route::RemoveOrder(Pickup p){
72  int flag=0;
73  // printf("Remove Order with Pid=%d Did=%d\n",p.Pid,p.Did);
74  for(int i=0;i<path_length;i++)
75  {
76  if(path[i]==p.Pid || path[i]==p.Did)
77  {
78  flag=1;
79  path[i]=0;
80  order[i]=0;
81  }
82  }
83  int new_path[path_length+1],new_length=0,new_order[path_length+1];
84  if(flag==1)
85  {
86  //copy
87  for(int i=0;i<path_length;i++)
88  {
89  if(path[i]!=0)
90  {
91  // printf("path[%d]=%d \n",new_length,path[i]);
92  new_path[new_length]=path[i];
93  new_order[new_length]=order[i];
94  new_length++;
95  }
96  }
97  //Reverse Copy
98  for(int i=0;i<new_length;i++)
99  {
100  path[i]=new_path[i];
101  order[i]=new_order[i];
102  }
103  path_length=new_length;
104  return 1;
105  }
106  else
107  {
108  return 0;
109  }
110 }
111 State Route::append(customer *c, Pickup p, depot d, int CustomerLength, int PickupLength, State S){
112 
113  //Save State;
114  S.twv=twv;
115  S.cv=cv;
116  S.dis=dis;
117  S.path_length=path_length;
118  for(int i=0;i<path_length;i++)
119  {
120  S.path[i]=path[i];
121  S.order[i]=order[i];
122  }
123 
124  // Insert Order
125  path[path_length]=p.Pid;
126  order[path_length]=p.id;
127  path[path_length+1]=p.Did;
128  order[path_length+1]=p.id;
129  path_length+=2;
130 
131  return S;
132 }
133 void Route::update(customer *c, depot d)
134 {
135  dis=0,twv=0,cv=0;
136  int load=0;
137  for(int i=-1;i<path_length;i++)
138  {
139  //depot to first customer
140  if(i==-1)
141  {
142  dis+=sqrt(((d.x-c[path[i+1]].x)*(d.x-c[path[i+1]].x))+((d.y-c[path[i+1]].y)*(d.y-c[path[i+1]].y)));
143  if(dis<c[path[i+1]].Etime)
144  {
145  dis=c[path[i+1]].Etime;
146  }
147  else if(dis>c[path[i+1]].Ltime)
148  {
149  twv+=1;
150  }
151  dis+=c[path[i+1]].Stime;
152  load+=c[path[i+1]].demand;
153  }
154  //Last cusotmer to depot
155  if(i==path_length-1)
156  {
157  dis+=sqrt(((d.x-c[path[i]].x)*(d.x-c[path[i]].x))+((d.y-c[path[i]].y)*(d.y-c[path[i]].y)));
158  if(dis>d.Ltime)
159  {
160  twv+=1;
161  }
162  }
163  //Middle customers
164  if(i>=0 && i< path_length-1)
165  {
166  dis+=sqrt(((c[path[i]].x-c[path[i+1]].x)*(c[path[i]].x-c[path[i+1]].x))+((c[path[i]].y-c[path[i+1]].y)*(c[path[i]].y-c[path[i+1]].y)));
167  if(dis<c[path[i+1]].Etime)
168  {
169  dis=c[path[i+1]].Etime;
170  }
171  else if(dis>c[path[i+1]].Ltime)
172  {
173  twv+=1;
174  }
175  dis+=c[path[i+1]].Stime;
176  load+=c[path[i+1]].demand;
177  }
178 
179  if(load>200 || load<0)
180  {
181  cv+=1;
182  }
183  }
184  return;
185 }
186 double Route::cost()
187 {
188  return (0.3*dis)+(0.5*twv)+(0.2*cv);
189 }
190 int Route::insertOrder(customer *c, depot d, Pickup p)
191 {
192  // double cost1=0,cost2=0;
193  twv=0,cv=0,dis=0;
194  int swap=0;
195  update(c,d);
196  if(twv==0 && cv==0 && dis<d.Ltime)
197  return 0;
198 
199  for(int i=0;i<path_length;i++)
200  {
201  for(int j=0;j<path_length;j++)
202  {
203  if((c[path[i]].Ltime > c[path[j]].Ltime) ){
204  //Swap Path
205  swap=path[i];
206  path[i]=path[j];
207  path[j]=swap;
208  //Swap order
209  swap=order[i];
210  order[i]=order[j];
211  order[j]=swap;
212 
213  }
214  }
215  }
216  //After complete sort
217  int *temp=NULL;
218  int *tempo=NULL;
219  temp= (int *)malloc(1000*sizeof(int));
220  tempo= (int *)malloc(1000*sizeof(int));
221  for(int i=0;i<path_length;i++)
222  {
223  temp[i]=path[path_length-i-1];
224  tempo[i]=order[path_length-i-1];
225  }
226  for(int i=0;i<path_length;i++)
227  {
228  path[i]=temp[i];
229  order[i]=tempo[i];
230  }
231 
232  twv=0,cv=0,dis=0;
233  update(c,d);
234  // print();
235  if(twv>0 || cv>0 || dis> d.Ltime)
236  {
237  return 1;
238  }
239  return 0;
240 }
241 
242 int Route::HillClimbing(customer *c, depot d, Pickup p)
243 {
244  double cost1=0,cost2=0;
245  twv=0,cv=0,dis=0;
246  int swap=0;
247  update(c,d);
248  cost1=cost();
249  if(twv==0 && cv==0 && dis<d.Ltime)
250  return 0;
251 
252  for(int i=0;i<path_length;i++){
253  for(int j=0;j<path_length;j++){
254  int swap_flag=0,count_flag=0;
255  if((c[path[i]].Ltime > c[path[j]].Ltime) && (count_flag==0) ){
256  swap_flag=1;
257  count_flag=1;
258  //Swap Path
259  swap=path[i];
260  path[i]=path[j];
261  path[j]=swap;
262  //Swap order
263  swap=order[i];
264  order[i]=order[j];
265  order[j]=swap;
266 
267  }
268  update(c,d);
269  cost2=cost();
270  if(cost2>cost1){
271  if(swap_flag==1){
272  //Swap Path
273  swap=path[i];
274  path[i]=path[j];
275  path[j]=swap;
276  //Swap order
277  swap=order[i];
278  order[i]=order[j];
279  order[j]=swap;
280  // update(c,d);
281  }
282  }
283  }
284  }
285  //After complete sort
286  int *temp=NULL;
287  int *tempo=NULL;
288  temp= (int *)malloc(1000*sizeof(int));
289  tempo= (int *)malloc(1000*sizeof(int));
290  for(int i=0;i<path_length;i++)
291  {
292  temp[i]=path[path_length-i-1];
293  tempo[i]=order[path_length-i-1];
294  }
295  for(int i=0;i<path_length;i++)
296  {
297  path[i]=temp[i];
298  order[i]=tempo[i];
299  }
300 
301 
302  update(c,d);
303  if(twv>0 || cv>0 || dis> d.Ltime)
304  {
305  return 1;
306  }
307  return 0;
308 }
309 
310 
311 #if 0
312 void Route::print(){
313  printf("%d ",dis);
314  printf("%d ",twv);
315  printf("%d ",cv);
316  printf("%lf ",cost());
317  printf("[");
318  for(int i=0;i<path_length;i++)
319  {
320  printf("%d ",path[i]);
321  }
322  printf("] ");
323  printf("[");
324  for(int i=0;i<path_length;i++)
325  {
326  printf("%d ",order[i]);
327  }
328  printf("] \n");
329  return;
330 
331 }
332 #endif
333 
334 void Route::remove( State S){
335  twv=S.twv;
336  cv=S.cv;
337  dis=S.dis;
338  path_length=S.path_length;
339  for(int i=0;i<path_length;i++)
340  {
341  path[i]=S.path[i];
342  order[i]=S.order[i];
343  }
344  return;
345 }
346 
347 
348 #endif
Definition: pdp.hpp:44
Definition: pdp.hpp:57
Definition: pdp.hpp:31