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