PGROUTING  2.6
optimize.cpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 FILE: optimize.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 <algorithm>
28 #include <limits>
29 #include <set>
30 
31 #include "cpp_common/pgr_assert.h"
32 
33 #include "vrp/solution.h"
34 #include "vrp/book_keeping.h"
35 #include "vrp/optimize.h"
36 #include "vrp/pgr_pickDeliver.h"
37 
38 namespace pgrouting {
39 namespace vrp {
40 
41 
43  const Solution &old_solution) :
44  Solution(old_solution),
45  best_solution(old_solution) {
46  pgassert(false);
48  inter_swap(fleet.size());
49  }
50 
52  const Solution &old_solution,
53  size_t times) :
54  Solution(old_solution),
55  best_solution(old_solution) {
56  inter_swap(times);
57 
58  this->fleet = best_solution.fleet;
59  msg.log << tau("bestSol before sort by size");
60  sort_by_size();
61  msg.log << tau("bestSol after sort by size");
62  msg.log << tau();
63  }
64 
65 
66 void
67 Optimize::inter_swap(size_t times) {
68  msg.log << tau("before sort by size");
69  sort_by_size();
70  msg.log << tau("before decrease");
72  msg.log << tau("after decrease");
73  sort_by_size();
74  msg.log << tau("after sort by size");
75 
76  size_t i = 0;
77  while ((i++ < times) && inter_swap()) {
78  msg.log << tau("after inter swap");
79  msg.log << "\n***************************" << i;
80  std::rotate(fleet.begin(), fleet.begin() + 1, fleet.end());
81  msg.log << tau("before next cycle");
82  }
83 }
84 
85 /*
86  * ordering the trucks by number of orders it has
87  * - the truck with more orders wants to:
88  * - make less time
89  * - do more orders
90  * The inter_swap objective is to make the trucks with more orders
91  * - less time consuming
92  */
93 bool
95  msg.log
96  << "\n" <<tau("before inter swap");
98  auto swapped_f = false;
99  /*
100  * .. to ... from ....
101  */
102  for (auto &from : fleet) {
103  for (auto &to : fleet) {
104  if (&from == &to) break;
105 
106 #if 0
107  msg.log
108  << "\n to " << to.id()
109  << "from " << from.id();
110  auto swapped = false;
111 #endif
112  swap_worse(to, from);
113  swapped_f = swap_order() || swapped_f;
114  move_reduce_cost(from, to);
115 #if 0
116  msg.log << "++++++++" << p_swaps;
117 #endif
118  }
119  }
120  while (!p_swaps.empty()) {
121  swapped_f = swap_order() || swapped_f;
122  }
123 
124  msg.log
125  << "\n" <<tau("after");
127 
128  return swapped_f;
129 }
130 
131 
132 
133 /*
134  * .. to ... from ....
135  */
136 bool
138 #if 0
140 #endif
141  auto from_truck = from;
142  auto to_truck = to;
143 
144  auto swapped = false;
145 
146 #if 0
147  auto best_from_order = from_truck.orders_in_vehicle().front();
148  auto best_to_order = to_truck.orders_in_vehicle().front();
149 #endif
150  for (auto from_orders = from_truck.orders_in_vehicle();
151  !from_orders.empty();
152  from_orders.pop_front()) {
153  auto from_order = from_truck.orders()[from_orders.front()];
154 #if 0
155  pgassert(from_truck.has_order(from_order));
156  msg.log << "\n" << from_orders;
157  msg.log << "\n from " << from_order.idx()
158  << "," << from_order.pickup().original_id();
159  pgassert(from_truck.has_order(from_order));
160 #endif
161  auto curr_from_duration = from_truck.duration();
162  pgassert(from_truck.has_order(from_order));
163 
164  for (auto to_orders = to_truck.orders_in_vehicle();
165  !to_orders.empty();
166  to_orders.pop_front()) {
167  pgassert(from_truck.has_order(from_order));
168 
169  auto to_order = to.orders()[to_orders.front()];
170 #if 0
171  msg.log << "\n" << to_orders;
172  msg.log << "\n To " << to_order.idx();
173 #endif
174  auto curr_to_duration = to_truck.duration();
175 
176  /*
177  * delete from_order, and to order from their trucks
178  */
179 #if 0
180  pgassert(from_truck.has_order(from_order));
181  msg.log << "\n" << from_truck.tau();
182  msg.log << "\n" << from_order.idx();
183  pgassert(from_truck.has_order(from_order));
184 #endif
185  from_truck.erase(from_order);
186  to_truck.erase(to_order);
187 
188  /*
189  * insert them in the other truck
190  */
191  from_truck.insert(to_order);
192  to_truck.insert(from_order);
193 
194  if (from_truck.is_feasable() && to_truck.is_feasable()) {
195  /*
196  * Can swap but:
197  * - only swap when the total duration is reduced
198  * - or from_truck duration is reduced
199  */
200 #if 0
201  msg.log << "\n Can swap";
202  msg.log << "\n Curr_from_duration " << curr_from_duration;
203  msg.log << " Curr_to_duration " << curr_to_duration;
204  msg.log << "\n new_from_duration "
205  << from_truck.duration();
206  msg.log << " new_to_duration " << to_truck.duration();
207 #endif
208  auto estimated_delta =
209  - (curr_from_duration + curr_to_duration)
210  + (to_truck.duration() + from_truck.duration());
211 
212 #if 1
213  auto estimated_duration = duration() + estimated_delta;
214 
215  if (from_truck.duration() < curr_from_duration ||
216  estimated_delta < 0 ||
217  estimated_duration < best_solution.duration()) {
218 #endif
219  msg.log
220  << "\n Found Swap order "
221  << from_order.pickup().id()
222  << " from truck " << from_truck.idx()
223  << " with order " << to_order.pickup().id()
224  << " of truck " << to_truck.idx();
225 
226  swapped = true;
227 #if 0
228  best_to_order = to_order.idx();
229  best_from_order = from_order.idx();
230 #endif
231  p_swaps.push(
232  Swap_info(
233  from,
234  to,
235  from_order.idx(),
236  to_order.idx(),
237  estimated_delta));
238 #if 1
239  }
240 #endif
241  }
242  to_truck = to;
243  from_truck = from;
244  }
245  from_truck = from;
246  }
247 
248  return false && swapped;
249 }
250 
251 
252 bool
254 #if 0
255  msg.log << "++++++++" << p_swaps;
256 #endif
257  while (!p_swaps.empty()) {
258  auto swap_data = p_swaps.top();
259  p_swaps.pop();
260  size_t from_pos = 0;
261  size_t to_pos = 0;
262 
263  for (; from_pos < fleet.size()
264  && fleet[from_pos].idx() != swap_data.from_truck.idx()
265  ; ++from_pos) {
266  }
267  pgassert(from_pos < fleet.size());
268  for (; to_pos < fleet.size()
269  && fleet[to_pos].idx() != swap_data.to_truck.idx()
270  ; ++to_pos) {
271  }
272  pgassert(to_pos < fleet.size());
273 
274  if (swap_order(
275  fleet[from_pos].orders()[swap_data.from_order], fleet[from_pos],
276  fleet[to_pos].orders()[swap_data.to_order], fleet[to_pos])) {
277  save_if_best();
278 #if 0
279  msg.log
280  << "\n Swapping order "
281  << fleet[from_pos].orders()[
282  swap_data.from_order].pickup().original_id()
283  << " from truck " << fleet[from_pos].id()
284  << " with order "
285  << fleet[to_pos].orders()[
286  swap_data.to_order].pickup().original_id()
287  << " of truck " << fleet[to_pos].id();
288 #endif
289 #if 0
290  msg.log << "\nswappping after:";
291  msg.log << "\n" << fleet[to_pos].tau();
292  msg.log << "\n" << fleet[from_pos].tau();
293 #endif
294  return true;
295  }
296  }
297  return false;
298 }
299 
300 /*
301  * from_truck: position of the truck where the order is
302  * to truck: truck to put the order
303  */
304 bool
306  const Order from_order,
307  Vehicle_pickDeliver &from_truck,
308  const Order to_order,
309  Vehicle_pickDeliver &to_truck) {
310  if (!from_truck.has_order(from_order)
311  || !to_truck.has_order(to_order)) {
312  return false;
313  }
314 
315  pgassert(from_truck.has_order(from_order));
316  pgassert(to_truck.has_order(to_order));
317 
318  from_truck.erase(from_order);
319  to_truck.erase(to_order);
320 
321  from_truck.insert(to_order);
322  to_truck.insert(from_order);
323 
324 
325  pgassert(from_truck.has_order(to_order));
326  pgassert(to_truck.has_order(from_order));
327  return true;
328 }
329 
330 void
332  std::sort(fleet.begin(), fleet.end(), []
333  (const Vehicle_pickDeliver &lhs, const Vehicle_pickDeliver &rhs)
334  -> bool {
335  return lhs.orders_in_vehicle().size()
336  > rhs.orders_in_vehicle().size();
337  });
338 }
339 
340 void
343  std::stable_sort(fleet.begin(), fleet.end(), []
344  (const Vehicle_pickDeliver &lhs, const Vehicle_pickDeliver &rhs)
345  -> bool {
346  return lhs.orders_in_vehicle().size()
347  > rhs.orders_in_vehicle().size();
348  });
349 }
350 
351 void
353  std::sort(fleet.begin(), fleet.end(), []
354  (const Vehicle_pickDeliver &lhs, const Vehicle_pickDeliver &rhs)
355  -> bool {
356  return lhs.duration() > rhs.duration();
357  });
358 }
359 
360 void
362  fleet.erase(std::remove_if(
363  fleet.begin(),
364  fleet.end(),
365  [](const Vehicle_pickDeliver &v){
366  return v.orders_in_vehicle().empty();}),
367  fleet.end());
368  save_if_best();
369 }
370 
371 #if 0
372 void
374  auto local_limit(fleet.size());
375  size_t i(0);
376 
378  msg.log << tau("\nmove duration based");
379  while (move_reduce_cost() && (++i < local_limit)) { }
381 
382  i = 0;
384  std::reverse(fleet.begin(), fleet.end());
385  msg.log << tau("\nmove duration based");
386  while (move_reduce_cost() && (++i < local_limit)) { }
389  this->fleet = best_solution.fleet;
390 }
391 
392 
393 void
395  this->fleet = best_solution.fleet;
396 
397  auto local_limit(fleet.size());
398  size_t i(0);
399 
400  sort_for_move();
401  msg.log << tau("\nmove wait_time based");
402  while (move_reduce_cost() && (++i < local_limit)) { }
404 
405  i = 0;
406  sort_for_move();
407  std::reverse(fleet.begin(), fleet.end());
408  msg.log << tau("\nmove wait_time based");
409  while (move_reduce_cost() && (++i < local_limit)) { }
412  this->fleet = best_solution.fleet;
413 }
414 #endif
415 
416 #if 0
417 /*
418  * On the current order of the fleet
419  * T1 .......Tn-1 Tn Tn+1...... Tsize
420  * Tn tries to move orders to trucks
421  * T1 .... Tn-1
422  * So that it gets space for the orders given by
423  * Tn+1 .... Tsize
424  * On the first move possible it returns
425  *
426  * When a truck is emptied, then it removes the truck from the fleet
427  *
428  * Returns true: when a move was possible
429  * Returns false: when a move was not possible
430  */
431 
432 
433 bool
435  if (fleet.size() < 2) return false;
436  bool moved = false;
437 
438  size_t from_pos(fleet.size() - 1);
439  while (from_pos > 1) {
440  for (size_t to_pos = 0; to_pos < from_pos; ++to_pos) {
441  moved = move_reduce_cost(from_pos, to_pos) || moved;
442  }
443  --from_pos;
444  }
445  return moved;
446 }
447 #endif
448 
449 /*
450  * from_truck trying to make from_truck's duration smaller
451  * - maybe all orders can be moved
452  * - if that is the case, the from_truck could be removed
453  *
454  * Deleting an order on the from_truck
455  * - number of truck remains the same
456  * - from_truk duration() can not get larger
457  * - the overall duration can get larger
458  *
459  */
460 bool
462  Vehicle_pickDeliver &from,
463  Vehicle_pickDeliver &to) {
464  auto from_truck = from;
465  auto to_truck = to;
466 
467  /*
468  * don't move from a real truck to a phoney truck
469  */
470  if (!from_truck.is_phony() && to_truck.is_phony()) {
471  return false;
472  }
473 #if 0
474  from.id() > to.id()
475  ? to : from;
476 #endif
477  size_t from_pos = 0;
478  size_t to_pos = 0;
479 
480  for (; from_pos < fleet.size()
481  && fleet[from_pos].idx() != from_truck.idx()
482  ; ++from_pos) {
483  }
484  pgassert(from_pos < fleet.size());
485  for (; to_pos < fleet.size()
486  && fleet[to_pos].idx() != to_truck.idx()
487  ; ++to_pos) {
488  }
489  pgassert(to_pos < fleet.size());
490 
491  auto moved = false;
492 
493  auto from_orders = from_truck.orders_in_vehicle();
494  while (!from_orders.empty()) {
495  /*
496  * removing an order decreases the duration
497  */
498  auto order = from_truck.orders()[from_orders.front()];
499  from_orders -= order.idx();
500 
501  /*
502  * insert it in the "to" truck
503  */
504  to_truck.insert(order);
505  if (to_truck.is_feasable()) {
506  msg.log
507  << "\n Move order " << order.pickup().id()
508  << " from truck " << from_truck.idx()
509  << " to truck " << to_truck.idx();
510 #ifndef NDEBUG
511  msg.dbg_log << "\nMove before:";
512  msg.dbg_log << "\n" << fleet[to_pos].tau();
513  msg.dbg_log << "\n" << fleet[from_pos].tau();
514 #endif
515 
516 #if 1
517  from_truck.erase(order);
518 #else
519  to_truck.insert(order);
520  move_order(order, fleet[from_pos], fleet[to_pos]);
521 #endif
522  moved = true;
523  save_if_best();
524 
525 #ifndef NDEBUG
526  msg.dbg_log << "\nMove after:";
527  msg.dbg_log << "\n" << fleet[to_pos].tau();
528  msg.dbg_log << "\n" << fleet[from_pos].tau();
529 #endif
530  } else {
531  to_truck.erase(order);
532  }
533  }
534  return moved;
535 }
536 
537 
538 
539 /*
540  * from_truck: position of the truck where the order is
541  * to truck: truck to put the order
542  */
543 void
545  Order order,
546  Vehicle_pickDeliver &from_truck,
547  Vehicle_pickDeliver &to_truck) {
548  pgassert(from_truck.has_order(order));
549  pgassert(!to_truck.has_order(order));
550 
551  from_truck.erase(order);
552  to_truck.insert(order);
553 
554  pgassert(!from_truck.has_order(order));
555  pgassert(to_truck.has_order(order));
556 }
557 
558 void
560  std::sort(fleet.begin(), fleet.end(), []
561  (const Vehicle_pickDeliver &lhs, const Vehicle_pickDeliver &rhs)
562  -> bool {
563  return lhs.total_wait_time() > rhs.total_wait_time();
564  });
565 
566  std::stable_sort(fleet.begin(), fleet.end(), []
567  (const Vehicle_pickDeliver &lhs, const Vehicle_pickDeliver &rhs)
568  -> bool {
569  return lhs.orders_size() > rhs.orders_size();
570  });
571 }
572 
573 
574 /*
575  * Optimize decreasing truck
576  *
577  * - Objective: try to remove truck with less duration
578  * - Secundary objective, acts like a shake operation
579  *
580  */
581 void
583  bool decreased(false);
584  for (size_t i = 1; i < fleet.size(); ++i) {
585  decreased = decrease_truck(i) || decreased;
586  }
587  if (decreased) {
589  save_if_best();
590  decrease_truck();
591  }
592  save_if_best();
593 }
594 
595 bool
597  auto position = cycle;
598  for (auto orders = fleet[position].orders_in_vehicle();
599  !orders.empty();
600  orders.pop_front()) {
601  /* Step 2: grab an order */
602  auto order = fleet[position].orders()[orders.front()];
603  pgassert(order.idx() == orders.front());
604 
605 
606  /* Step 3:
607  * cycle the fleet
608  * insert in first truck possible
609  */
610 
611  for (size_t i = 0; i < position; ++i) {
612  fleet[i].insert(order);
613  if (fleet[i].is_feasable()) {
614  /*
615  * delete the order from the current truck
616  */
617  fleet[position].erase(order);
618  break;
619  } else {
620  fleet[i].erase(order);
621  }
622  }
623  }
624  return fleet[position].orders_in_vehicle().empty();
625 }
626 
627 void
629  if (duration() < best_solution.duration()) {
630  best_solution = (*this);
631  msg.log << "\n*********** best by duration"
632  << best_solution.cost_str();
633 #ifndef NDEBUG
634  msg.dbg_log << best_solution.tau("best by duration");
635 #endif
636  }
637  if (fleet.size() < best_solution.fleet.size()) {
638  best_solution = (*this);
639  msg.log << "\n*********** best by fleet size"
640  << best_solution.cost_str();
641 #ifndef NDEBUG
642  msg.dbg_log << best_solution.tau("best by fleet size");
643 #endif
644  }
645 }
646 
647 
648 } // namespace vrp
649 } // namespace pgrouting
const PD_Orders & orders() const
bool is_feasable() const
Definition: solution.cpp:56
bool has_order(const Order &order) const
bool swap_worse(Vehicle_pickDeliver &from, Vehicle_pickDeliver &to)
Definition: optimize.cpp:137
void move_order(Order order, Vehicle_pickDeliver &from_truck, Vehicle_pickDeliver &to_truck)
Definition: optimize.cpp:544
std::ostringstream log
Stores the hint information.
Definition: pgr_messages.h:102
int64_t id() const
Definition: identifier.cpp:42
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49
double total_wait_time() const
Definition: vehicle.h:231
std::ostringstream dbg_log
Definition: pgr_messages.h:108
double duration() const
Definition: vehicle.h:228
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
Identifiers< size_t > orders_in_vehicle() const
void insert(const Order &order)
Inserts an order.
std::string tau(const std::string &title="Tau") const
Definition: solution.cpp:153
size_t size() const
Definition: identifiers.hpp:77
Optimize(const Solution &solution)
Definition: optimize.cpp:42
Book keeping class for swapping orders between vehicles.
Definition: basic_edge.cpp:28
Assertions Handling.
static Pgr_messages msg
Definition: pd_problem.h:48
T front() const
Definition: identifiers.hpp:79
std::string cost_str() const
Definition: solution.cpp:138
bool move_reduce_cost(Vehicle_pickDeliver &from, Vehicle_pickDeliver &to)
Definition: optimize.cpp:461
double duration() const
Definition: solution.cpp:65
size_t idx() const
Definition: identifier.cpp:37
void push(const Swap_info &data)
Definition: book_keeping.h:125