PGROUTING  2.4
 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  if (truck.orders_size() !=0 ) {
441  fleet.push_back(truck);
442  }
443 }
444 
445 void
447  size_t v_id(0);
448  Vehicle_pickDeliver truck(
449  v_id++,
453  problem);
454  while (!unassigned.empty()) {
455  auto order(problem->orders()[*unassigned.begin()]);
456 
457  truck.push_front(order);
458  if (!truck.is_feasable()) {
459  truck.pop_front();
460  fleet.push_back(truck);
461  Vehicle_pickDeliver newtruck(
462  v_id++,
466  problem);
467  truck = newtruck;
468  } else {
469  assigned.insert(*unassigned.begin());
470  unassigned.erase(unassigned.begin());
471  }
472 
473  invariant();
474  }
475  if (truck.orders_size() !=0 ) {
476  fleet.push_back(truck);
477  }
478 }
479 
480 void
482  size_t v_id(0);
483  Vehicle_pickDeliver truck(
484  v_id++,
488  problem);
489  while (!unassigned.empty()) {
490  auto order(problem->orders()[*unassigned.begin()]);
491 
492  truck.push_back(order);
493  if (!truck.is_feasable()) {
494  truck.pop_back();
495  fleet.push_back(truck);
496  Vehicle_pickDeliver newtruck(
497  v_id++,
501  problem);
502  truck = newtruck;
503  } else {
504  assigned.insert(*unassigned.begin());
505  unassigned.erase(unassigned.begin());
506  }
507 
508  invariant();
509  }
510 
511  if (truck.orders_size() !=0 ) {
512  fleet.push_back(truck);
513  }
514 }
515 
516 
517 
518 void
520  size_t v_id(0);
521  while (!unassigned.empty()) {
522  auto order(problem->orders()[*unassigned.begin()]);
523 
524  Vehicle_pickDeliver truck(
525  v_id++,
529  problem);
530  truck.push_back(order);
531  fleet.push_back(truck);
532 
533  assigned.insert(*unassigned.begin());
534  unassigned.erase(unassigned.begin());
535 
536  invariant();
537  }
538 }
539 
540 
541 
542 
543 void
545  size_t v_id(0);
546  Vehicle_pickDeliver truck(
547  v_id++,
551  problem);
552  while (!unassigned.empty()) {
553  auto order(problem->orders()[*unassigned.begin()]);
554 
555  truck.insert(order);
556 
557  assigned.insert(*unassigned.begin());
558  unassigned.erase(unassigned.begin());
559 
560  invariant();
561  }
562  fleet.push_back(truck);
563 }
564 
565 
566 
567 
568 } // namespace vrp
569 } // 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:732
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