pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
vrppdtw/src/pdp_solver.cpp
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 
24  *****list of files in this dir*******
25  pdp.cpp --> Main solver
26  pdp.h ---> Structures defined in this header file
27  Solution.h -----> It contains the Solution Class and Code related to Neighborhoods
28  Route.h -----> Explains all about Route Class.
29  pdp.c ---> Contains all the details on pgRouting integration.
30 
31  The main problem is in two steps. 1.)Getting the initial solutiion and 2.)Optimizing it.
32 
33  1.) "Initial solution":
34  A few heuristics are applied to find a feasible initial solution. Sequential Construction and Hill climbing. More implementation details are found here:: https://github.com/pgRouting/pgrouting/wiki/VRP-Pickup-Delivery-Problem
35 
36  2.) "Optimizing the Solution":
37  A reactive tabu search is applied on the initial solution to get a feasible optimized solution. TabuSearch comes under local search methods. We have three neighborhoods
38  i) Single Paired Insertion
39  ii) Swapping pairs between routes
40  iii)Within Route Insertion.
41  Tabu attributes plays an important role in giving the best solution(it includes TabuLength, A vector containing feasible solutions and a counter for number of solutions).
42  Reactive part discussed in the paper is to modify TabuLength based on the solution cycle.
43 
44  */
45 #ifdef __MINGW32__
46 #include <winsock2.h>
47 #include <windows.h>
48 #endif
49 
50 
51 #include <vector>
52 #include <map>
53 #include <queue>
54 #include <string>
55 #include <stdlib.h>
56 #include <iostream>
57 #include <algorithm>
58 #include <math.h>
59 #include <stdio.h>
60 #include <string.h>
61 #include <set>
62 //Headers Include
63 #include "./pdp.h"
64 #include "./Solution.h"
65 #include "./Route.h"
66 
67 
68 int PickupLength=0;
69 
70 //Depot
71 depot d;
72 //Vehicle
73 //Customer Data
74 customer *c=NULL;
75 pickup *p=NULL;
76 int len=0;
77 
78 int CustomerLength;
79 
80 
81 std::vector<Solution> T;
82 
83 Route *r=NULL;
84 //Definitions for a few functions
85 int TabuSearch();
86 //Vector containing solutions
87 
88 //Initial Solution
89 Solution S0;
90 
91 void result_struct();
92 int Solver(customer *c1,int total_tuples, int VehicleLength, int capacity , char **msg, path_element **results, int *length_results_struct)
93 {
94  CustomerLength= total_tuples-1;
95 
96  c = (customer *)malloc((CustomerLength+5)*sizeof(customer));
97  p = (pickup *)malloc((CustomerLength+5)*sizeof(pickup));
98  r = (Route *)malloc((CustomerLength+5)*sizeof(Route));
100  //Depot Data
101  d.id = c1[0].id;
102  d.x = c1[0].x;
103  d.y = c1[0].y;
104  d.demand = c1[0].demand;
105  d.Etime = c1[0].Etime;
106  d.Ltime = c1[0].Ltime;
107  d.Stime = c1[0].Stime;
108  d.Pindex = c1[0].Pindex;
109  d.Dindex = c1[0].Dindex;
110 
111 
112  //Customer Data
113  for(int i=1;i<=CustomerLength;i++)
114  {
115  c[i].id = c1[i].id;
116  c[i].x = c1[i].x;
117  c[i].y = c1[i].y;
118  c[i].Etime = c1[i].Etime;
119  c[i].demand = c1[i].demand;
120  c[i].Ltime = c1[i].Ltime;
121  c[i].Stime = c1[i].Stime;
122  c[i].Pindex = c1[i].Pindex;
123  c[i].Dindex = c1[i].Dindex;
124  c[i].Ddist= CalculateDistance(c[i].x, c[i].y ,d.x, d.y);
125  if(c[i].Pindex==0){
126  c[i].P=1;
127  c[i].D=0;
128  }
129  if(c[i].Dindex==0){
130  c[i].D=1;
131  c[i].P=0;
132  }
133  }
134 
135  //Vehicle Data
136 
137  Vehicle.given_vehicles = VehicleLength;
138  Vehicle.capacity = capacity;
139  Vehicle.speed = 1;
140  Vehicle.used_vehicles=0;
141 
142 
143 
144 
145  //From customers put aside all the pickup's;
146  for(int i=1;i<=CustomerLength;i++){
147  if(c[i].P==1){
148  PickupLength+=1;
149  p[PickupLength].id=PickupLength;
150  p[PickupLength].Did=c[i].Dindex;
151  p[PickupLength].Ddist=c[i].Ddist;
152  p[PickupLength].Pid=c[i].id;
153  }
154  }
155  // printf("Pickup Length=%d \n",PickupLength);
156 
157  //Sort Pickup's
158  int swap;
159  double swap1;
160  for(int i=1;i<=PickupLength;i++)
161  {
162  for(int j=1;j<=PickupLength-i;j++){
163  if(p[j].Ddist>p[j+1].Ddist){
164  swap1=p[j].Ddist;
165  p[j].Ddist=p[j+1].Ddist;
166  p[j+1].Ddist=swap1;
167  swap=p[j].Did;
168  p[j].Did=p[j+1].Did;
169  p[j+1].Did=swap;
170  swap=p[j].Pid;
171  p[j].Pid=p[j+1].Pid;
172  p[j+1].Pid=swap;
173  swap=p[j].id;
174  p[j].id=p[j+1].id;
175  p[j+1].id=swap;
176  }
177  }
178  p[i].checked=0;
179  }
180 
181 
182  for(int i=1;i<=PickupLength;i++)
183  {
184  // DBG("PickupID[%d]=%lf\n",p[i].id,p[i].Ddist);
185  }
186 
187  // int flag_complete=0;
188  int checked=0;
189  //Sequential Construction
190  for(int v=1;v<110;v++){
191  for(int i=PickupLength;i>=1;i--){
192  if(p[i].checked!=1){
193  State S;
194  S=r[v].append(c,p[i],d,CustomerLength,PickupLength,S);
195  int flag=r[v].HillClimbing(c,d,p[i]);
196  if(flag==1){
197  //Remove
198  p[i].checked=0;
199  r[v].remove(S);
200  }
201  else{
202  p[i].checked=1;
203  checked+=1;
204  }
205  }
206  //Requests complete
207  }
208  Vehicle.used_vehicles=v;
209  if(checked==PickupLength)
210  {
211  v=9999;
212  }
213  }
214  // *length_results_struct = d.Ltime;
215  int sum=0,rts=0;
216 
217  for(int i=1;i<=Vehicle.used_vehicles;i++){
218  // printf("%d, ",i);
219  // r[i].print();
220  sum+=r[i].dis;
221  if(r[i].dis!=0){
222  rts+=1;
223  }
224  Vehicle.cost=sum;
225  }
226  // printf("Sum=%d Routes=%d Vehicle.used_vehicles=%d\n",sum,rts,Vehicle.used_vehicles);
227 
228  //Storing Initial Solution (S0 is the Initial Solution)
229  for(int i=1;i<=Vehicle.used_vehicles;i++)
230  {
231  S0.cost_total+=r[i].cost();
232  S0.dis_total+=r[i].dis;
233  S0.twv_total+=r[i].twv;
234  S0.cv_total+=r[i].cv;
235  }
236  S0.route_length=Vehicle.used_vehicles;
237  for(int i=1;i<=Vehicle.used_vehicles;i++)
238  {
239  S0.r.push_back(r[i]);
240  }
241  // printf("Size =>> S0.r.size=%ld\n", S0.r.size());
242 
243 
244  //Starting Neighborhoods
245  // printf("\nNeighborhoods From now\n");
246  int sol_count=TabuSearch();
247 
248  //Copying back the results
249  // path_element->results , path_length { we need to send (results, length_results) backk ;
250  int nodes_count;
251  nodes_count= CustomerLength;
252  *results = (path_element *) malloc(sizeof(path_element) * (nodes_count + 5*VehicleLength));
253  int length_results=0;
254 
255 
256 
257  int *cost, *cost_nodes;
258  cost = (int *)malloc(1000*sizeof(int));
259  cost_nodes = (int *)malloc(1000*sizeof(int));
260  //Cost Calculation
261 
262  int copy_length=0;
263  // TAKE AN ARRAY EMBED EVERYTHING
264  for(int itr_route=0;itr_route<T[sol_count].route_length;itr_route++)
265  {
266  cost[copy_length]=d.id;
267  copy_length++;
268  for(int itr_node=0;itr_node<T[sol_count].r[itr_route].path_length;itr_node++)
269  {
270  cost[copy_length]=T[sol_count].r[itr_route].path[itr_node];
271  copy_length++;
272  }
273  cost[copy_length]=d.id;
274  copy_length++;
275  }
276 
277  copy_length-=1;
278  int temp_dis=0;
279  for(int i=0;i<copy_length;i++)
280  {
281  if(i==0)
282  {
283  cost_nodes[0]=0;
284  temp_dis=0;
285  }
286  else
287  {
288  //Depot to first node
289  if(cost[i-1]==d.id && cost[i]!=d.id )
290  {
291  temp_dis=0;
292  temp_dis+=sqrt(((c[cost[i]].x-d.x)*(c[cost[i]].x-d.x))+((c[cost[i]].y-d.y)*(c[cost[i]].y-d.y)));
293  if(temp_dis < c[cost[i]].Etime)
294  {
295  temp_dis=c[cost[i]].Etime;
296  }
297 
298  cost_nodes[i]=temp_dis;
299  }
300 
301  //Between nodes
302  else if(cost[i-1]!=d.id && cost[i]!=d.id)
303  {
304  temp_dis+=sqrt(((c[cost[i]].x-c[cost[i-1]].x)*(c[cost[i]].x-c[cost[i-1]].x))+((c[cost[i]].y-c[cost[i-1]].y)*(c[cost[i]].y-c [cost[i-1]].y)));
305 
306  if(temp_dis < c[cost[i]].Etime)
307  {
308  temp_dis=c[cost[i]].Etime;
309  }
310 
311  temp_dis+=c[cost[i-1]].Stime;
312  cost_nodes[i]=temp_dis;
313  }
314  else if(cost[i]==d.id && cost[i-1]!=d.id)
315  {
316  temp_dis+=sqrt(((d.x-c[cost[i-1]].x)*(d.x-c[cost[i-1]].x))+((d.y-c[cost[i-1]].y)*(d.y-c[cost[i-1]].y)));
317  cost_nodes[i]=temp_dis;
318  temp_dis=0;
319  }
320  else if(cost[i]==d.id && cost[i-1]==d.id)
321  {
322  cost_nodes[i]=0;
323  temp_dis=0;
324  }
325  }
326  //Last node to deopt
327  }
328 
329  //Done cost calculation
330 
331 
332  for(int itr_route=0; itr_route<T[sol_count].route_length; itr_route++)
333  {
334  (*results)[length_results].seq = length_results;
335  (*results)[length_results].rid = itr_route+1;
336  (*results)[length_results].nid = d.id;
337  (*results)[length_results].cost = cost_nodes[length_results];
338  length_results++;
339 
340  //Loop for path elements.
341  for(int itr_node=0;itr_node < T[sol_count].r[itr_route].path_length;itr_node++)
342  {
343  (*results)[length_results].seq = length_results;
344  (*results)[length_results].rid = itr_route+1;
345  (*results)[length_results].nid = T[sol_count].r[itr_route].path[itr_node];
346  (*results)[length_results].cost = cost_nodes[length_results];
347  length_results++;
348  }
349 
350  (*results)[length_results].seq = length_results;
351  (*results)[length_results].rid = itr_route+1;
352  (*results)[length_results].nid = d.id;
353  (*results)[length_results].cost = cost_nodes[length_results];
354  length_results++;
355 
356  }
357 
358  *length_results_struct = length_results;
359  free(c);
360  free(p);
361  free(r);
362 
363 //Copying is done till here
364 
365  return 0;
366 }
367 int n=0,maxItr=30;
368 
369 
370 
371 /* TABU search helps us to store the solutions after every different move. The overview of TABU search will be a list containing list of solutions*/
372 
373 int TabuSearch()
374 {
375  // printf("TABU Called\n");
376  Solution S,SBest;
377  double CBest;
378  //Pseudo Code
379  /*
380 
381  **********Before*********
382  int n=0; //Counter
383 
384  Create Tabu List Vector of Solutions std::vector<Solution> T;
385 
386  **********After**********
387  Solution S,S0,SBest; //S0 is initial
388  S=S0;
389  Double CBest,SBest;
390  CBest = S.getCost();
391  SBest = S0;
392  n=0; //Counter
393  while(1)
394  {
395  S = S.getBextofNeighborhood();
396  if(S==NULL)
397  break;
398  if(S.getCost() < CBest){
399  SBest = S;
400  CBest = S.getCost();
401  }
402  T.push_back(S);
403  n++;
404  if(n>maxItr)
405  break;
406  }
407 
408  */
409 
410  S=S0;
411  CBest = S.getCost();
412  SBest = S0;
413  T.clear();
414  T.push_back(S0);
415  while(1)
416  {
417  S = S.getBestofNeighborhood(S,c,d,p,CustomerLength,PickupLength);
418  if(S.getCost()==0)
419  break;
420  if (S.getCost() < CBest){
421  SBest = S;
422  CBest = S.getCost();
423  T.push_back(S);
424  }
425  else if(S.getCost() == CBest )
426  {
427  // printf("\n****************Repeated Solution****************\n");
428  int k= ((12)*maxItr)/100;
429  maxItr = maxItr-k;
430  // printf("Maxitr after repeating %d k =%d\n",maxItr,k);
431  }
432  n++;
433  if (n > maxItr)
434  break;
435  }
436 #if 0
437  printf("Size of Tabu=%ld &&& n=%d maxItr=%d\n",T.size(),n,maxItr);
438  for(unsigned int itr=0;itr<T.size();itr++)
439  {
440  T[itr].dump();
441  }
442 #endif
443  return T.size()-1;
444 }
445 
Definition: pdp.hpp:44
Definition: pdp.hpp:57
Definition: pdp.hpp:31