PGROUTING  2.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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 "./../../common/src/pgr_assert.h"
32 
33 #include "./solution.h"
34 #include "./optimize.h"
35 #include "./pgr_pickDeliver.h"
36 
37 namespace pgrouting {
38 namespace vrp {
39 
40 
42  int kind,
43  const Solution &old_solution) :
44  Solution(old_solution),
45  best_solution(old_solution) {
46  switch (kind) {
47  case 0:
49  break;
50  case 1:
52  break;
53  case 2:
55  break;
56  case 3:
58  break;
59  case 4:
60  inter_swap();
61  break;
62  }
63  this->fleet = best_solution.fleet;
66  }
67 
68 
69 void
71  auto local_limit(fleet.size());
72  size_t i(0);
73  while (inter_swap(false) && (++i < local_limit)) {
74  }
75  i = 0;
76  while (inter_swap(true) && (++i < local_limit)) {
77  }
80  this->fleet = best_solution.fleet;
81 }
82 
83 bool
84 Optimize::inter_swap(bool reversed) {
85 // problem->log << tau("before sort");
88  save_if_best();
89  if (reversed) {
90  std::reverse(fleet.begin(), fleet.end());
91  }
92 // problem->log << tau("after sort");
93  auto swapped = false;
94  size_t from_pos(fleet.size()-1);
95  while (from_pos > 1) {
96  for (size_t to_pos = 0; to_pos < from_pos; ++to_pos) {
97  swapped = swap_worse(from_pos, to_pos)? true : swapped;
98  swapped = move_reduce_cost(from_pos, to_pos)? true : swapped;
99  }
101  --from_pos;
102  }
103  return swapped;
104 }
105 
106 bool
107 Optimize::swap_worse(size_t from_pos, size_t to_pos) {
108  pgassert(to_pos < from_pos);
109  auto from_truck = fleet[from_pos];
110  auto to_truck = fleet[to_pos];
111  auto swapped(false);
112  auto from_orders(from_truck.orders_in_vehicle);
113  auto to_orders(to_truck.orders_in_vehicle);
114  auto local_limit(from_orders.size() * to_orders.size() + 1);
115 
116  while (!from_orders.empty() && --local_limit > 0) {
117  auto from_order(from_truck.get_worse_order(from_orders));
118  from_orders.erase(from_order.id());
119 
120  while (!to_orders.empty()) {
121  auto to_order(to_truck.get_worse_order(to_orders));
122  to_orders.erase(to_order.id());
123 
124  /*
125  * delete from_order, and to order from their trucks
126  */
127  auto curr_from_duration(from_truck.duration());
128  auto curr_to_duration(to_truck.duration());
129 
130  from_truck.erase(from_order);
131  to_truck.erase(to_order);
132 
133  /*
134  * insert them in the other truck
135  */
136  from_truck.insert(to_order);
137  to_truck.insert(from_order);
138 
139  if (from_truck.is_feasable() && to_truck.is_feasable()) {
140  /*
141  * Can swap but:
142  * - only swap when the total duration is reduced
143  * - or from_truck duration is reduced
144  */
145 
146  if (((from_truck.duration() + to_truck.duration())
147  < (curr_from_duration + curr_to_duration))
148  || (from_truck.duration() < curr_from_duration)) {
149  problem->log
150  << "\n Swap order " << from_order.id()
151  << " from truck " << from_truck.id()
152  << " with order " << to_order.id() << " of truck " << to_truck.id();
153 #ifndef NDEBUG
154  problem->dbg_log << "\nswappping before:";
155  problem->dbg_log << "\n" << fleet[to_pos].tau();
156  problem->dbg_log << "\n" << fleet[from_pos].tau();
157 #endif
158 
159  swap_order(from_order, fleet[from_pos], to_order, fleet[to_pos]);
160  swapped = true;
161  save_if_best();
162  from_orders.insert(to_order.id());
163 #ifndef NDEBUG
164  problem->dbg_log << "\nswappping after:";
165  problem->dbg_log << "\n" << fleet[to_pos].tau();
166  problem->dbg_log << "\n" << fleet[from_pos].tau();
167 #endif
168  break;
169  }
170  }
171  /*
172  * wasn't swapped
173  */
174  to_truck = fleet[to_pos];
175  from_truck = fleet[from_pos];
176  }
177  }
178  return swapped;
179 }
180 
181 /*
182  * from_truck: position of the truck where the order is
183  * to truck: truck to put the order
184  */
185 void
187  const Order from_order,
188  Vehicle_pickDeliver &from_truck,
189  const Order to_order,
190  Vehicle_pickDeliver &to_truck) {
191  pgassert(from_truck.has_order(from_order));
192  pgassert(to_truck.has_order(to_order));
193 
194  from_truck.erase(from_order);
195  to_truck.erase(to_order);
196 
197  from_truck.insert(to_order);
198  to_truck.insert(from_order);
199 
200 
201  pgassert(from_truck.has_order(to_order));
202  pgassert(to_truck.has_order(from_order));
203 }
204 
205 void
207  std::sort(fleet.begin(), fleet.end(), []
208  (const Vehicle_pickDeliver &lhs, const Vehicle_pickDeliver &rhs)
209  -> bool {
210  return lhs.duration() > rhs.duration();
211  });
212 }
213 
214 void
216  while (fleet.back().empty()) {
217  problem->log << "\nEmpty truck";
218  fleet.pop_back();
219  save_if_best();
220  }
221  save_if_best();
222 }
223 
224 void
226  auto local_limit(fleet.size());
227  size_t i(0);
228 
230  problem->log << tau("\nmove duration based");
231  while (move_reduce_cost() && (++i < local_limit)) { }
233 
234  i = 0;
236  std::reverse(fleet.begin(), fleet.end());
237  problem->log << tau("\nmove duration based");
238  while (move_reduce_cost() && (++i < local_limit)) { }
241  this->fleet = best_solution.fleet;
242 }
243 
244 
245 void
247  this->fleet = best_solution.fleet;
248 
249  auto local_limit(fleet.size());
250  size_t i(0);
251 
252  sort_for_move();
253  problem->log << tau("\nmove wait_time based");
254  while (move_reduce_cost() && (++i < local_limit)) { }
256 
257  i = 0;
258  sort_for_move();
259  std::reverse(fleet.begin(), fleet.end());
260  problem->log << tau("\nmove wait_time based");
261  while (move_reduce_cost() && (++i < local_limit)) { }
264  this->fleet = best_solution.fleet;
265 }
266 
267 /*
268  * On the current order of the fleet
269  * T1 .......Tn-1 Tn Tn+1...... Tsize
270  * Tn tries to move orders to trucks
271  * T1 .... Tn-1
272  * So that it gets space for the orders given by
273  * Tn+1 .... Tsize
274  * On the first move possible it returns
275  *
276  * When a truck is emptied, then it removes the truck from the fleet
277  *
278  * Returns true: when a move was possible
279  * Returns false: when a move was not possible
280  */
281 
282 
283 bool
285  if (fleet.size() < 2) return false;
286 
287  size_t from_pos(fleet.size() - 1);
288  while (from_pos > 1) {
289  for (size_t to_pos = 0; to_pos < from_pos; ++to_pos) {
290  // problem->log << "\nmove_reduce_cost (" << fleet[from_pos].id() << ", " << fleet[to_pos].id() << ")";
291  if (move_reduce_cost(from_pos, to_pos)) {
292  if (fleet[from_pos].empty()) {
293  fleet.erase(fleet.begin() + from_pos);
294  save_if_best();
295  }
296  return true;
297  }
298  }
299  --from_pos;
300  }
301  return false;
302 }
303 
304 /*
305  * from_truck trying to make from_truck's duration smaller
306  * - maybe all orders can be moved
307  * - if that is the case, the from_truck could be removed
308  *
309  * Deleting an order on the from_truck
310  * - number of truck remains the same
311  * - from_truk duration() can not get larger
312  * - the overall duration can get larger
313  *
314  */
315 bool
316 Optimize::move_reduce_cost(size_t from_pos, size_t to_pos) {
317  pgassert(to_pos < from_pos);
318  auto from_truck = fleet[from_pos];
319  auto to_truck = fleet[to_pos];
320  auto moved(false);
321 
322  auto orders(from_truck.orders_in_vehicle);
323  while (!orders.empty()) {
324  /*
325  * get the order that decreases the duration the most
326  * (there is always a worse)
327  */
328  auto order = from_truck.get_worse_order(orders);
329  orders.erase(order.id());
330 
331  /*
332  * insert it in the next truck
333  */
334  to_truck.insert(order);
335  if (to_truck.is_feasable()) {
336  problem->log
337  << "\n Move order " << order.id()
338  << " from truck " << from_truck.id()
339  << " to truck " << to_truck.id();
340 #ifndef NDEBUG
341  problem->dbg_log << "\nMove before:";
342  problem->dbg_log << "\n" << fleet[to_pos].tau();
343  problem->dbg_log << "\n" << fleet[from_pos].tau();
344 #endif
345 
346  from_truck.erase(order);
347  move_order(order, fleet[from_pos], fleet[to_pos]);
348  moved = true;
349  save_if_best();
350 
351 #ifndef NDEBUG
352  problem->dbg_log << "\nMove after:";
353  problem->dbg_log << "\n" << fleet[to_pos].tau();
354  problem->dbg_log << "\n" << fleet[from_pos].tau();
355 #endif
356  }
357  }
358  return moved;
359 }
360 
361 
362 
363 /*
364  * from_truck: position of the truck where the order is
365  * to truck: truck to put the order
366  */
367 void
369  Order order,
370  Vehicle_pickDeliver &from_truck,
371  Vehicle_pickDeliver &to_truck) {
372  pgassert(from_truck.has_order(order));
373  pgassert(!to_truck.has_order(order));
374 
375  from_truck.erase(order);
376  to_truck.insert(order);
377 
378  pgassert(!from_truck.has_order(order));
379  pgassert(to_truck.has_order(order));
380 }
381 
382 void
384  std::sort(fleet.begin(), fleet.end(), []
385  (const Vehicle_pickDeliver &lhs, const Vehicle_pickDeliver &rhs)
386  -> bool {
387  return lhs.total_wait_time() > rhs.total_wait_time();
388  });
389 
390  std::stable_sort(fleet.begin(), fleet.end(), []
391  (const Vehicle_pickDeliver &lhs, const Vehicle_pickDeliver &rhs)
392  -> bool {
393  return lhs.orders_size() > rhs.orders_size();
394  });
395 }
396 
397 
398 /*
399  * Optimize decreasing truck
400  *
401  * - Objective: try to remove truck with less duration
402  *
403  * Step 1: Sort the fleet, duration DESC
404  * Step 2: grab an order from the back of the the fleet
405  * Step 3: cycle the fleet & insert in best truck possible
406  */
407 void
409  bool decreased(true);
410  while (decreased) {
411  decreased = false;
413  std::reverse(fleet.begin(), fleet.end());
414  decrease_truck(fleet.size(), decreased);
415  }
416  this->fleet = best_solution.fleet;
417 }
418 
419 void
420 Optimize::decrease_truck(size_t cycle, bool &decreased) {
421  /* end recursion */
422  if (cycle == 0) return;
423 
424  std::ostringstream err_log;
425  err_log << " --- Cycle " << cycle << "\n";
426 
427  /* the front truck move to back */
428  std::rotate(fleet.begin(), fleet.begin() + 1, fleet.end());
429  err_log << "\n after rotate" << tau();
430 
431  auto orders(fleet.back().orders_in_vehicle);
432  while (!orders.empty()) {
433  /* Step 2: grab an order */
434  auto order(problem->orders()[*orders.begin()]);
435  orders.erase(orders.begin());
436  err_log << "\n truck with order: " << fleet.back().tau();
437  err_log << "\nOrder" << order << "\n";
438 
439  /* Step 3: delete the order from the back of the fleet */
440  pgassertwm(fleet.back().has_order(order), err_log.str());
441  fleet.back().erase(order);
442  pgassertwm(!fleet.back().has_order(order), err_log.str());
443 
444  /* Step 3: cycle the fleet & insert in best truck possible */
445  /* current truck is tried last */
446  err_log << " trying ";
447  auto best_truck(fleet.size() - 1);
448  auto current_duration(duration());
449  auto min_delta_duration = (std::numeric_limits<double>::max)();
450  size_t t_i(0);
451  for (auto &truck : fleet) {
452  truck.insert(order);
453  if (!truck.is_feasable()) {
454  err_log << "\n" << truck.tau();
455  } else {
456  err_log << "\n ******* success " << truck.tau() << "\n";
457  auto delta_duration = duration()-current_duration;
458  if (t_i != fleet.size() - 1
459  && (delta_duration < min_delta_duration)) {
460  min_delta_duration = delta_duration;
461  best_truck = t_i;
462  }
463  }
464  truck.erase(order);
465  ++t_i;
466  }
467  fleet[best_truck].insert(order);
468  save_if_best();
469  }
470 
471  if (fleet.back().empty()) {
472  decreased = true;
473  fleet.pop_back();
474  save_if_best();
475  }
476  decrease_truck(--cycle, decreased);
477 }
478 
479 void
481  if (duration() < best_solution.duration()) {
482  best_solution = (*this);
483  problem->log << "\n*********** best by duration" << best_solution.cost_str();
484 #ifndef NDEBUG
485  problem->dbg_log << best_solution.tau("best by duration");
486 #endif
487  }
488  if (fleet.size() < best_solution.fleet.size()) {
489  best_solution = (*this);
490  problem->log << "\n*********** best by fleet size" << best_solution.cost_str();
491 #ifndef NDEBUG
492  problem->dbg_log << best_solution.tau("best by fleet size");
493 #endif
494  }
495 }
496 
497 
498 } // namespace vrp
499 } // namespace pgrouting
bool has_order(const Order &order) const
#define pgassertwm(expr, msg)
Adds a message to the assertion.
Definition: pgr_assert.h:104
void move_order(Order order, Vehicle_pickDeliver &from_truck, Vehicle_pickDeliver &to_truck)
Definition: optimize.cpp:368
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:46
const Pgr_pickDeliver * problem
Definition: solution.h:49
double total_wait_time() const
Definition: vehicle.h:216
double duration() const
Definition: vehicle.h:213
bool swap_worse(size_t from_pos, size_t to_pos)
Definition: optimize.cpp:107
PGDLLEXPORT Datum vrp(PG_FUNCTION_ARGS)
Definition: VRP.c:732
void swap_order(Order from_order, Vehicle_pickDeliver &from_truck, Order to_order, Vehicle_pickDeliver &to_truck)
Definition: optimize.cpp:186
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
void insert(const Order &order)
Inserts an order.
std::string tau(const std::string &title="Tau") const
Definition: solution.cpp:151
std::string cost_str() const
Definition: solution.cpp:136
const std::vector< Order > & orders() const
double duration() const
Definition: solution.cpp:63
Optimize(int kind, const Solution &solution)
Definition: optimize.cpp:41