pgRouting
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
initial_solution.cpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 FILE: initial_solution.cpp
4 
5 Copyright (c) 2015 pgRouting developers
6 Mail: project@pgrouting.org
7 
8 ------
9 
10 This program is free software; you can redistribute it and/or modify
11 it under the terms of the GNU General Public License as published by
12 the Free Software Foundation; either version 2 of the License, or
13 (at your option) any later version.
14 
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License for more details.
19 
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
23 
24  ********************************************************************PGR-GNU*/
25 
26 
27 #include "./initial_solution.h"
28 #include <deque>
29 #include <algorithm>
30 #include <set>
31 #include "./../../common/src/pgr_assert.h"
32 #include "./solution.h"
33 #include "./pgr_pickDeliver.h"
34 
35 namespace pgrouting {
36 namespace vrp {
37 
38 void
40  std::set<size_t> orders(assigned);
41 
42  orders.insert(unassigned.begin(), unassigned.end());
43 
44  /* check the local book keeping is ok */
45  pgassert(all_orders == orders);
46 
47  /* this checks there is no order duplicated */
48  pgassert(all_orders.size() == orders.size());
49 }
50 
51 
53  int kind,
54  const Pgr_pickDeliver *p_problem) :
55  Solution(p_problem) {
56  for (const auto &order : problem->orders()) {
57  unassigned.insert(order.id());
58  }
60  assigned.clear();
61 
62  switch (kind) {
63  case 0:
65  break;
66  case 1:
68  break;
69  case 2:
71  break;
72  case 3:
74  break;
75  case 4:
77  break;
78  case 5:
80  break;
81  case 6:
83  break;
84  }
85  }
86 
87 
88 
89 void
91  Vehicle_pickDeliver &truck,
92  std::set<size_t> &possible_orders) {
93  invariant();
94  /*
95  * Precondition:
96  * truck.orders_in_vehicle intersection assigned == truck.orders_in_vehicle
97  * (all orders in the truck are in the assigned set)
98  */
99  std::set<size_t> invariant_set;
100  std::set_intersection(
101  truck.orders_in_vehicle.begin(),
102  truck.orders_in_vehicle.end(),
103  assigned.begin(), assigned.end(),
104  std::inserter(invariant_set, invariant_set.begin()));
105  pgassert(invariant_set == truck.orders_in_vehicle);
106 
107  invariant_set.clear();
108  /*
109  * Precondition:
110  * possible_orders intersection unassigned == possible_orders
111  * (all possible orders are not in the assigned set)
112  */
113  std::set_intersection(possible_orders.begin(), possible_orders.end(),
114  assigned.begin(), assigned.end(),
115  std::inserter(invariant_set, invariant_set.begin()));
116  pgassert(invariant_set.empty());
117 
118  /*
119  * termination of recursion
120  */
121  if (possible_orders.empty())
122  return;
123 
124  /*
125  * CODE
126  */
127  auto best_order = *possible_orders.begin();
128  size_t max_size(0);
129 
130  /*
131  * In the possible orders set look for the order that
132  * has more compatible orders with the current possible orders
133  */
134  for (auto &o : possible_orders) {
135  auto other_orders = problem->orders()[o].m_compatibleJ;
136  auto intersect_orders = problem->orders()[o].subsetJ(possible_orders);
137  if (max_size < intersect_orders.size()) {
138  max_size = intersect_orders.size();
139  best_order = o;
140  }
141  }
142  auto intersect_orders = problem->orders()[best_order].subsetJ(possible_orders);
143 
144  truck.insert(problem->orders()[best_order]);
145  if (!truck.is_feasable()) {
146  truck.erase(problem->orders()[best_order]);
147  } else {
148  assigned.insert(best_order);
149  unassigned.erase(unassigned.find(best_order));
150  }
151 
152  possible_orders.erase(possible_orders.find(best_order));
153  fill_truck_while_compatibleJ(truck, possible_orders);
154  invariant();
155 }
156 
157 
158 
159 
160 
161 
162 
163 
164 
165 
166 
167 
168 
169 
170 std::deque<size_t>
172  /*
173  * Sorted as:
174  * (| {I}|, | {J}|)
175  * orders: keep sorted based on the number of orders it is compatible with
176  */
177  std::deque<size_t> orders(unassigned.begin(), unassigned.end());
178  const Pgr_pickDeliver *prob = problem;
179  std::sort(orders.begin(), orders.end(), [&prob]
180  (const size_t &lhs, const size_t &rhs) -> bool
181  {return prob->orders()[lhs].m_compatibleJ.size()
182  < prob->orders()[rhs].m_compatibleJ.size();
183  });
184  std::stable_sort(orders.begin(), orders.end(), [&prob]
185  (const size_t &lhs, const size_t &rhs) -> bool
186  {return prob->orders()[lhs].m_compatibleI.size()
187  < prob->orders()[rhs].m_compatibleI.size();
188  });
189  return orders;
190 }
191 
192 
193 
194 
195 
196 void
198  problem->log << "\nInitial_solution::insert_while_compatible\n";
199  invariant();
200 
201 
202  size_t v_id(0);
203  Vehicle_pickDeliver truck(
204  v_id++,
208  problem);
209 
210  while (!unassigned.empty()) {
211  std::deque<size_t> orders(first_ordersIJ());
212 
213  if (truck.empty()) {
214  auto order(problem->orders()[orders.front()]);
215  truck.insert(order);
216  assigned.insert(order.id());
217  orders.pop_front();
218  unassigned.erase(unassigned.find(order.id()));
219  invariant();
220 
221  std::set<size_t> compatible_orders(
222  problem->orders()[order.id()].m_compatibleJ);
223  std::set<size_t> possible_orders;
224  std::set_intersection(
225  compatible_orders.begin(), compatible_orders.end(),
226  unassigned.begin(), unassigned.end(),
227  std::inserter(possible_orders, possible_orders.begin()));
228 
229 
230  fill_truck_while_compatibleJ(truck, possible_orders);
231  fleet.push_back(truck);
232 
233  if (unassigned.empty())
234  break;
235 
236  Vehicle_pickDeliver newtruck(
237  v_id++,
241  problem);
242  truck = newtruck;
243  }
244  invariant();
245  }
246 }
247 
248 
249 
250 void
252  Vehicle_pickDeliver &truck,
253  std::set<size_t> &possible_orders) {
254  invariant();
255  /*
256  * Precondition:
257  * truck.orders_in_vehicle intersection assigned == truck.orders_in_vehicle
258  * (all orders in the truck are in the assigned set)
259  */
260  std::set<size_t> invariant_set;
261  std::set_intersection(truck.orders_in_vehicle.begin(), truck.orders_in_vehicle.end(),
262  assigned.begin(), assigned.end(),
263  std::inserter(invariant_set, invariant_set.begin()));
264  pgassert(invariant_set == truck.orders_in_vehicle);
265 
266  invariant_set.clear();
267  /*
268  * Precondition:
269  * possible_orders intersection unassigned == possible_orders
270  * (all possible orders are not in the assigned set)
271  */
272  std::set_intersection(possible_orders.begin(), possible_orders.end(),
273  assigned.begin(), assigned.end(),
274  std::inserter(invariant_set, invariant_set.begin()));
275  pgassert(invariant_set.empty());
276 
277  /*
278  * termination of recursion
279  */
280  if (possible_orders.empty())
281  return;
282 
283  /*
284  * CODE
285  */
286  auto best_order = *possible_orders.begin();
287  size_t max_size(0);
288 
289  /*
290  * In the possible orders set look for the order that
291  * has more compatible orders with the current possible orders
292  */
293  for (auto &o : possible_orders) {
294  auto other_orders = problem->orders()[o].m_compatibleI;
295  auto intersect_orders = problem->orders()[o].subsetI(possible_orders);
296  if (max_size < intersect_orders.size()) {
297  max_size = intersect_orders.size();
298  best_order = o;
299  }
300  }
301  auto intersect_orders = problem->orders()[best_order].subsetI(possible_orders);
302 
303  truck.insert(problem->orders()[best_order]);
304  if (!truck.is_feasable()) {
305  truck.erase(problem->orders()[best_order]);
306  } else {
307  assigned.insert(best_order);
308  unassigned.erase(unassigned.find(best_order));
309  }
310 
311  possible_orders.erase(possible_orders.find(best_order));
312  fill_truck_while_compatibleI(truck, possible_orders);
313  invariant();
314 }
315 
316 
317 
318 
319 
320 
321 
322 
323 
324 
325 
326 std::deque<size_t>
328  /*
329  * Sorted as:
330  * (| {J}|, | {I}|)
331  * orders: keep sorted based on the number of orders it is compatible with
332  */
333  std::deque<size_t> orders(unassigned.begin(), unassigned.end());
334  const Pgr_pickDeliver *prob = problem;
335  std::sort(orders.begin(), orders.end(), [&prob]
336  (const size_t &lhs, const size_t &rhs) -> bool
337  {return prob->orders()[lhs].m_compatibleI.size()
338  < prob->orders()[rhs].m_compatibleI.size();
339  });
340  std::stable_sort(orders.begin(), orders.end(), [&prob]
341  (const size_t &lhs, const size_t &rhs) -> bool
342  {return prob->orders()[lhs].m_compatibleJ.size()
343  < prob->orders()[rhs].m_compatibleJ.size();
344  });
345  return orders;
346 }
347 
348 
349 
350 void
352  problem->log << "\nInitial_solution::insert_while_compatible\n";
353  invariant();
354 
355 
356  size_t v_id(0);
357  Vehicle_pickDeliver truck(
358  v_id++,
362  problem);
363 
364  while (!unassigned.empty()) {
365  std::deque<size_t> orders(first_ordersJI());
366 
367  if (truck.empty()) {
368  auto order(problem->orders()[orders.front()]);
369  truck.insert(order);
370  assigned.insert(order.id());
371  orders.pop_front();
372  unassigned.erase(unassigned.find(order.id()));
373  invariant();
374 
375  std::set<size_t> compatible_orders(
376  problem->orders()[order.id()].m_compatibleI);
377  std::set<size_t> possible_orders;
378  std::set_intersection(
379  compatible_orders.begin(), compatible_orders.end(),
380  unassigned.begin(), unassigned.end(),
381  std::inserter(possible_orders, possible_orders.begin()));
382 
383 
384  fill_truck_while_compatibleI(truck, possible_orders);
385  fleet.push_back(truck);
386 
387  if (unassigned.empty())
388  break;
389 
390  Vehicle_pickDeliver newtruck(
391  v_id++,
395  problem);
396  truck = newtruck;
397  }
398  invariant();
399  }
400 }
401 
402 
403 
404 
405 
406 void
408  invariant();
409 
410  size_t v_id(0);
411  Vehicle_pickDeliver truck(
412  v_id++,
416  problem);
417  problem->log << "\nInitial_solution::insert_while_feasable\n";
418  while (!unassigned.empty()) {
419  auto order(problem->orders()[*unassigned.begin()]);
420 
421  truck.insert(order);
422 
423  if (!truck.is_feasable()) {
424  truck.erase(order);
425  fleet.push_back(truck);
426  Vehicle_pickDeliver newtruck(
427  v_id++,
431  problem);
432  truck = newtruck;
433  } else {
434  assigned.insert(*unassigned.begin());
435  unassigned.erase(unassigned.begin());
436  }
437 
438  invariant();
439  }
440 }
441 
442 void
444  size_t v_id(0);
445  Vehicle_pickDeliver truck(
446  v_id++,
450  problem);
451  while (!unassigned.empty()) {
452  auto order(problem->orders()[*unassigned.begin()]);
453 
454  truck.push_front(order);
455  if (!truck.is_feasable()) {
456  truck.pop_front();
457  fleet.push_back(truck);
458  Vehicle_pickDeliver newtruck(
459  v_id++,
463  problem);
464  truck = newtruck;
465  } else {
466  assigned.insert(*unassigned.begin());
467  unassigned.erase(unassigned.begin());
468  }
469 
470  invariant();
471  }
472 }
473 
474 void
476  size_t v_id(0);
477  Vehicle_pickDeliver truck(
478  v_id++,
482  problem);
483  while (!unassigned.empty()) {
484  auto order(problem->orders()[*unassigned.begin()]);
485 
486  truck.push_back(order);
487  if (!truck.is_feasable()) {
488  truck.pop_back();
489  fleet.push_back(truck);
490  Vehicle_pickDeliver newtruck(
491  v_id++,
495  problem);
496  truck = newtruck;
497  } else {
498  assigned.insert(*unassigned.begin());
499  unassigned.erase(unassigned.begin());
500  }
501 
502  invariant();
503  }
504 }
505 
506 
507 
508 void
510  size_t v_id(0);
511  while (!unassigned.empty()) {
512  auto order(problem->orders()[*unassigned.begin()]);
513 
514  Vehicle_pickDeliver truck(
515  v_id++,
519  problem);
520  truck.push_back(order);
521  fleet.push_back(truck);
522 
523  assigned.insert(*unassigned.begin());
524  unassigned.erase(unassigned.begin());
525 
526  invariant();
527  }
528 }
529 
530 
531 
532 
533 void
535  size_t v_id(0);
536  Vehicle_pickDeliver truck(
537  v_id++,
541  problem);
542  while (!unassigned.empty()) {
543  auto order(problem->orders()[*unassigned.begin()]);
544 
545  truck.insert(order);
546 
547  assigned.insert(*unassigned.begin());
548  unassigned.erase(unassigned.begin());
549 
550  invariant();
551  }
552  fleet.push_back(truck);
553 }
554 
555 
556 
557 
558 } // namespace vrp
559 } // namespace pgrouting
void push_back(const Order &order)
puts an order at the end of the truck
void push_front(const Order &order)
Puts an order at the end front of the truck.
void fill_truck_while_compatibleI(Vehicle_pickDeliver &truck, std::set< size_t > &possible_orders)
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:46
const Pgr_pickDeliver * problem
Definition: solution.h:49
ID pop_back()
The order that is picked last is removed.
PGDLLEXPORT Datum vrp(PG_FUNCTION_ARGS)
Definition: VRP.c:730
Initial_solution(int kind, const Pgr_pickDeliver *problem)
std::deque< size_t > first_ordersJI() const
std::deque< size_t > first_ordersIJ() const
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
void insert(const Order &order)
Inserts an order.
bool empty() const
return true when no nodes are in the truck
Definition: vehicle.cpp:343
void fill_truck_while_compatibleJ(Vehicle_pickDeliver &truck, std::set< size_t > &possible_orders)
const std::vector< Order > & orders() const
bool is_feasable() const
Definition: vehicle.h:240