pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
pickDeliver/src/pdp_solver.cpp
1 /*PGR-GNU*****************************************************************
2 
3 Copyright (c) 2014 Manikata Kondeti
4 mani.iiit123@gmail.com
5 
6 ------
7 
8 This program is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
12 
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17 
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21 
22 ********************************************************************PGR-GNU*/
23 
24 /*
25 
26  *****list of files in this dir*******
27  pdp.cpp --> Main solver
28  pdp.h ---> Structures defined in this header file
29  Solution.h -----> It contains the Solution Class and Code related to Neighborhoods
30  Route.h -----> Explains all about Route Class.
31  pdp.c ---> Contains all the details on pgRouting integration.
32 
33  The main problem is in two steps. 1.)Getting the initial solutiion and 2.)Optimizing it.
34 
35  1.) "Initial solution":
36  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
37 
38  2.) "Optimizing the Solution":
39  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
40  i) Single Paired Insertion
41  ii) Swapping pairs between routes
42  iii)Within Route Insertion.
43  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).
44  Reactive part discussed in the paper is to modify TabuLength based on the solution cycle.
45 
46  */
47 #ifdef __MINGW32__
48 #include <winsock2.h>
49 #include <windows.h>
50 #endif
51 
52 
53 #include <vector>
54 #include <algorithm>
55 
56 #include "./pdp.h"
57 #include "./pdp.hpp"
58 #include "./Solution.h"
59 #include "./Route.h"
60 
61 
62 //forward declaration
63 static
64 int
65 TabuSearch(
66  const std::vector<Customer> &customers,
67  const std::vector<Pickup> &pickups,
68  int maxIter,
69  std::vector<Solution> &T);
70 
71 static
72 void
73 get_result(
74  Solution &solution,
75  const std::vector < Customer > &customers,
76  const Depot &depot,
77  int64_t VehicleLength,
78  std::vector< path_element > &result);
79 
80 int64_t Solver(Customer *c1,
81  size_t total_tuples,
82  int64_t VehicleLength,
83  int64_t capacity,
84  char **msg,
85  path_element **results,
86  size_t *length_results_struct) {
87  std::vector<Customer> customers(c1, c1 + total_tuples);
88  std::vector<Pickup> pickups;
89  std::vector<Route> routes;
90 
91  Depot depot({c1[0].id, c1[0].x, c1[0].y,
92  c1[0].demand,
93  c1[0].Etime, c1[0].Ltime, c1[0].Stime,
94  c1[0].Pindex, c1[0].Dindex
95  });
96 
97  if (total_tuples != 107) {
98  return 0;
99  }
100 
101 
102  // Customer Data
103  for (auto &c : customers) {
104  if (c.id == 0) continue;
105  c.Ddist = CalculateDistance(c, depot);
106  if (c.Pindex == 0) {
107  // From Customers put aside all the Pickup's;
108  Pickup pickup({c.id, c.Ddist, c.Dindex});
109  pickups.push_back(pickup);
110  }
111  }
112 
113  if (pickups.size() != 53) {
114  (*results) = NULL;
115  (*length_results_struct) = 0;
116  return 0;
117  }
118 
119  /* Sort Pickup's
120  * The sequential construction inserts from largest distance to smallest
121  * but he had it ordered from smallest to largest
122  */
123  std::sort(pickups.begin(), pickups.end(),
124  [] (const Pickup &p1, const Pickup &p2)
125  {return p2.Ddist < p1.Ddist;});
126 
127 
128  // Sequential Construction
129  size_t v = 0;
130  Route route(capacity, depot);
131  routes.push_back(route);
132  for (auto &pickup : pickups) {
133  int OK = 0;
134  OK = routes[v].insertOrder(customers, pickup);
135  if (OK) continue;
136  Route route(capacity, depot);
137  routes.push_back(route);
138  /* adding a new vehicle*/
139  ++v;
140  routes[v].insertOrder(customers, pickup);
141  }
142 
143 
144  std::sort(pickups.begin(), pickups.end(),
145  [] (const Pickup &p1, const Pickup &p2)
146  {return p1.Ddist < p2.Ddist;});
147 
148  // Initial Solution
149  Solution S0;
150  S0.routes = routes;
151  //S0.UpdateSol(customers);
152 
153  std::vector<Solution> T;
154  T.push_back(S0);
155 
156  // Starting the TABU SEARCH
157 
158  TabuSearch(customers, pickups, 30, T);
159 
160 
161  std::vector< path_element > result;
162 #ifdef DEBUG
163  for (auto &solution: T) {
164  get_result(solution, customers, depot, VehicleLength, result);
165  }
166 #else
167  T.back().UpdateSol(customers);
168  get_result(T.back(), customers, depot, VehicleLength, result);
169 #endif
170 
171 
172 
173  // Getting memory to store results
174  *results = static_cast<path_element *>(malloc(sizeof(path_element) * (result.size())));
175 
176  //store the results
177  int seq = 0;
178  for (const auto &row : result) {
179  (*results)[seq] = row;
180  ++seq;
181  }
182 
183  *length_results_struct = result.size();
184 
185  (*msg) = NULL;
186  return 0;
187 }
188 
189 
190 
191 
192 
193 
194 
195 /* TABU search helps us to store the solutions after every different move.
196  * The overview of TABU search will be a list containing list of solutions
197 
198  **********Before*********
199  int n = 0; //Counter
200 
201  Create Tabu List Vector of Solutions std::vector<Solution> T;
202 
203  **********After**********
204  Solution S,S0,SBest; //S0 is initial
205  S = S0;
206  Double CBest,SBest;
207  CBest = S.getCost();
208  SBest = S0;
209  n = 0; //Counter
210  while(1)
211  {
212  S = S.getBextofNeighborhood();
213  if (S ==NULL)
214  break;
215  if (S.getCost() < CBest){
216  SBest = S;
217  CBest = S.getCost();
218  }
219  T.push_back(S);
220  n++;
221  if (n>maxItr)
222  break;
223  }
224 
225 */
226 static
227 int
228 TabuSearch(const std::vector<Customer> &customers,
229  const std::vector<Pickup> &pickups,
230  int maxItr,
231  std::vector<Solution> &T) {
232  Solution S;
233  Solution SBest;
234  double CBest;
235  S = T[0];
236  CBest = S.getCost();
237  SBest = S;
238 
239  S.UpdateSol(customers);
240 
241  int n = 0;
242  while (n++ < maxItr) {
243  S = S.getBestofNeighborhood(S, customers, pickups);
244  S.UpdateSol(customers);
245  T.push_back(S);
246  if (S.getCost() == 0) break;
247  if (S.getCost() < CBest) {
248  SBest = S;
249  CBest = S.getCost();
250  } else if (S.getCost() == CBest) {
251  // printf("\n****************Repeated Solution****************\n");
252  int k = ((12)*maxItr)/100;
253  maxItr = maxItr-k;
254  // printf("Maxitr after repeating %d k = %d\n",maxItr,k);
255  }
256  }
257  T.push_back(SBest);
258  return T.size()-1;
259 }
260 
261 
262 /*
263  * For each route in the solution:
264  * For each node in the route in the solution:
265  * this is the route.
266  * d, p0, p1 .... pn, d
267  * (rid, nid, cost)
268  * (1, d, 0)
269  * (1, p0, 0 + dist(d, p0) OR etime)
270  */
271 static
272 void
273 get_result(
274  Solution &solution,
275  const Customers &customers,
276  const Depot &depot,
277  int64_t VehicleLength,
278  std::vector< path_element > &result) {
279 #if DEBUG
280  double last_cost = 0;
281  int twv = 0;
282  int cv = 0;
283 #endif
284  int route_id = 0;
285  int seq = 1;
286  solution.UpdateSol(customers);
287  for (const auto &route : solution.routes) {
288  double agg_cost = 0;
289  double distance = 0;
290  int agg_load = 0;
291  result.push_back({seq, route_id, depot.id, agg_cost});
292  ++seq;
293 
294  int prev_node = -1;
295  for (const auto &node : route.path) {
296 
297  if (node == route.path.front()) {
298  /*
299  * Is the first node or last node in the path
300  */
301  distance = CalculateDistance(depot, customers[node]);
302  agg_cost += distance;
303  } else {
304  /*
305  * Between nodes
306  */
307  distance = CalculateDistance(customers[prev_node], customers[node]);
308  agg_cost += distance;
309  }
310 
311  if (agg_cost < customers[node].Etime) {
312  /*
313  * Arrving before the opening time, adjust time, moving it to the opening time
314  */
315  agg_cost = customers[node].Etime;
316  }
317 
318  agg_load += customers[node].demand;
319 
320  result.push_back({
321  seq,
322  route_id,
323  customers[node].id,
324  agg_cost});
325 #ifdef DEBUG
326  result.push_back({
327  customers[node].id,
328  customers[node].Etime,
329  customers[node].Ltime,
330  distance});
331  result.push_back({
332  seq,
333  agg_cost > customers[node].Ltime? ++twv: twv,
334  agg_load > 200? ++cv: cv,
335  0});
336  last_cost = agg_cost;
337 #endif
338  agg_cost += customers[node].Stime;
339  prev_node = node;
340  ++seq;
341  }
342  /*
343  * Going back to the depot
344  */
345  agg_cost += CalculateDistance(customers[prev_node], depot);
346  result.push_back({seq, route_id, depot.id, agg_cost});
347  ++seq;
348  ++route_id;
349 #if 1
350  if (VehicleLength < route_id) break;
351 #endif
352  }
353  result.push_back({0, 0, 0, solution.getCost()});
354 }
355 
Definition: pdp.hpp:44
Definition: pdp.hpp:31