PGROUTING  2.5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
pgrouting::vrp::Optimize Class Reference

#include "optimize.h"

Inheritance diagram for pgrouting::vrp::Optimize:
Collaboration diagram for pgrouting::vrp::Optimize:

Public Member Functions

 Optimize (const Solution &solution)
 
 Optimize (const Solution &solution, size_t times)
 
Vehicle::Cost cost () const
 
std::string cost_str () const
 
int cvTot () const
 
void decrease_truck ()
 
double duration () const
 
size_t fleet_size () const
 
std::vector
< General_vehicle_orders_t
get_postgres_result () const
 
void inter_swap (size_t times)
 
bool is_feasable () const
 
void move_duration_based ()
 
void move_wait_time_based ()
 
bool operator< (const Solution &s_rhs) const
 
std::string tau (const std::string &title="Tau") const
 
double total_service_time () const
 
double total_travel_time () const
 
int twvTot () const
 
double wait_time () const
 

Public Attributes

Solution best_solution
 

Static Public Attributes

static Pgr_messages msg
 

Protected Attributes

double EPSILON
 
std::deque< Vehicle_pickDeliverfleet
 
Fleet trucks
 

Static Protected Attributes

static Pgr_pickDeliverproblem
 

Private Member Functions

bool decrease_truck (size_t)
 
void delete_empty_truck ()
 
bool inter_swap ()
 
void move_order (Order order, Vehicle_pickDeliver &from_truck, Vehicle_pickDeliver &to_truck)
 
bool move_reduce_cost (Vehicle_pickDeliver &from, Vehicle_pickDeliver &to)
 
void save_if_best ()
 
void sort_by_duration ()
 
void sort_by_id ()
 
void sort_by_size ()
 
void sort_for_move ()
 
bool swap_order ()
 
bool swap_order (Order from_order, Vehicle_pickDeliver &from_truck, Order to_order, Vehicle_pickDeliver &to_truck)
 
bool swap_worse (Vehicle_pickDeliver &from, Vehicle_pickDeliver &to)
 

Private Attributes

Swap_bk p_swaps
 

Detailed Description

Definition at line 42 of file optimize.h.

Constructor & Destructor Documentation

pgrouting::vrp::Optimize::Optimize ( const Solution solution)
explicit

Definition at line 42 of file optimize.cpp.

References decrease_truck(), pgrouting::vrp::Solution::fleet, inter_swap(), and pgassert.

43  :
44  Solution(old_solution),
45  best_solution(old_solution) {
46  pgassert(false);
48  inter_swap(fleet.size());
49  }
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81

Here is the call graph for this function:

pgrouting::vrp::Optimize::Optimize ( const Solution solution,
size_t  times 
)

Definition at line 51 of file optimize.cpp.

References best_solution, pgrouting::vrp::Solution::fleet, inter_swap(), pgrouting::Pgr_messages::log, pgrouting::vrp::PD_problem::msg, sort_by_size(), and pgrouting::vrp::Solution::tau().

53  :
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  }
std::ostringstream log
Stores the hint information.
Definition: pgr_messages.h:102
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49
std::string tau(const std::string &title="Tau") const
Definition: solution.cpp:153
static Pgr_messages msg
Definition: pd_problem.h:48

Here is the call graph for this function:

Member Function Documentation

Vehicle::Cost pgrouting::vrp::Solution::cost ( ) const
inherited

Definition at line 119 of file solution.cpp.

References pgrouting::vrp::Solution::fleet.

Referenced by pgrouting::vrp::Solution::cost_str(), pgrouting::vrp::Solution::operator<(), and pgrouting::vrp::Solution::tau().

119  {
120  double total_duration(0);
121  double total_wait_time(0);
122  int total_twv(0);
123  int total_cv(0);
124  for (const auto v : fleet) {
125  total_duration += v.duration();
126  total_wait_time += v.total_wait_time();
127  total_twv += v.twvTot();
128  total_cv += v.cvTot();
129  }
130  return std::make_tuple(
131  total_twv, total_cv, fleet.size(),
132  total_wait_time, total_duration);
133 }
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49

Here is the caller graph for this function:

std::string pgrouting::vrp::Solution::cost_str ( ) const
inherited

Definition at line 138 of file solution.cpp.

References pgrouting::vrp::Solution::cost().

Referenced by save_if_best(), and pgrouting::vrp::Solution::tau().

138  {
139  Vehicle::Cost s_cost(cost());
140  std::ostringstream log;
141 
142  log << "(twv, cv, fleet, wait, duration) = ("
143  << std::get<0>(s_cost) << ", "
144  << std::get<1>(s_cost) << ", "
145  << std::get<2>(s_cost) << ", "
146  << std::get<3>(s_cost) << ", "
147  << std::get<4>(s_cost) << ")";
148 
149  return log.str();
150 }
Vehicle::Cost cost() const
Definition: solution.cpp:119
std::tuple< int, int, size_t, double, double > Cost
Definition: vehicle.h:86

Here is the call graph for this function:

Here is the caller graph for this function:

int pgrouting::vrp::Solution::cvTot ( ) const
inherited

Definition at line 110 of file solution.cpp.

References pgrouting::vrp::Solution::fleet.

110  {
111  int total(0);
112  for (const auto v : fleet) {
113  total += v.cvTot();
114  }
115  return total;
116 }
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49
void pgrouting::vrp::Optimize::decrease_truck ( )

Definition at line 582 of file optimize.cpp.

References delete_empty_truck(), pgrouting::vrp::Solution::fleet, and save_if_best().

Referenced by inter_swap(), and Optimize().

582  {
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 }
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49

Here is the call graph for this function:

Here is the caller graph for this function:

bool pgrouting::vrp::Optimize::decrease_truck ( size_t  cycle)
private

Definition at line 596 of file optimize.cpp.

References pgrouting::vrp::Solution::fleet, pgrouting::vrp::Solution::is_feasable(), and pgassert.

596  {
597 
598  auto position = cycle;
599  for (auto orders = fleet[position].orders_in_vehicle();
600  !orders.empty();
601  orders.pop_front()) {
602  /* Step 2: grab an order */
603  auto order = fleet[position].orders()[orders.front()];
604  pgassert(order.idx() == orders.front());
605 
606 
607  /* Step 3:
608  * cycle the fleet
609  * insert in first truck possible
610  */
611 
612  for (size_t i = 0; i < position; ++i) {
613  fleet[i].insert(order);
614  if (fleet[i].is_feasable()) {
615  /*
616  * delete the order from the current truck
617  */
618  fleet[position].erase(order);
619  break;
620  } else {
621  fleet[i].erase(order);
622  }
623  }
624  }
625  return fleet[position].orders_in_vehicle().empty();
626 }
bool is_feasable() const
Definition: solution.cpp:56
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81

Here is the call graph for this function:

void pgrouting::vrp::Optimize::delete_empty_truck ( )
private

Definition at line 361 of file optimize.cpp.

References pgrouting::vrp::Solution::fleet, and save_if_best().

Referenced by decrease_truck(), and inter_swap().

361  {
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 }
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49

Here is the call graph for this function:

Here is the caller graph for this function:

double pgrouting::vrp::Solution::duration ( ) const
inherited

Definition at line 65 of file solution.cpp.

References pgrouting::vrp::Solution::fleet.

Referenced by save_if_best(), and swap_worse().

65  {
66  double total(0);
67  for (const auto v : fleet) {
68  total += v.duration();
69  }
70  return total;
71 }
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49

Here is the caller graph for this function:

size_t pgrouting::vrp::Solution::fleet_size ( ) const
inlineinherited

Definition at line 102 of file solution.h.

References pgrouting::vrp::Solution::fleet.

102 {return fleet.size();}
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49
std::vector< General_vehicle_orders_t > pgrouting::vrp::Solution::get_postgres_result ( ) const
inherited

Definition at line 39 of file solution.cpp.

References pgrouting::vrp::Solution::fleet.

39  {
40  std::vector<General_vehicle_orders_t> result;
41  /* postgres numbering starts with 1 */
42  int i(1);
43  for (const auto truck : fleet) {
44  std::vector<General_vehicle_orders_t> data =
45  truck.get_postgres_result(i);
46  result.insert(result.end(), data.begin(), data.end());
47 
48  ++i;
49  }
50  return result;
51 }
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49
void pgrouting::vrp::Optimize::inter_swap ( size_t  times)

Definition at line 67 of file optimize.cpp.

References decrease_truck(), pgrouting::vrp::Solution::fleet, inter_swap(), pgrouting::Pgr_messages::log, pgrouting::vrp::PD_problem::msg, sort_by_size(), and pgrouting::vrp::Solution::tau().

67  {
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 }
std::ostringstream log
Stores the hint information.
Definition: pgr_messages.h:102
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49
std::string tau(const std::string &title="Tau") const
Definition: solution.cpp:153
static Pgr_messages msg
Definition: pd_problem.h:48

Here is the call graph for this function:

bool pgrouting::vrp::Optimize::inter_swap ( )
private

Definition at line 94 of file optimize.cpp.

References delete_empty_truck(), pgrouting::vrp::Swap_bk::empty(), pgrouting::vrp::Solution::fleet, pgrouting::Pgr_messages::log, move_reduce_cost(), pgrouting::vrp::PD_problem::msg, p_swaps, swap_order(), swap_worse(), and pgrouting::vrp::Solution::tau().

Referenced by inter_swap(), and Optimize().

94  {
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 }
bool swap_worse(Vehicle_pickDeliver &from, Vehicle_pickDeliver &to)
Definition: optimize.cpp:137
std::ostringstream log
Stores the hint information.
Definition: pgr_messages.h:102
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49
std::string tau(const std::string &title="Tau") const
Definition: solution.cpp:153
static Pgr_messages msg
Definition: pd_problem.h:48
bool move_reduce_cost(Vehicle_pickDeliver &from, Vehicle_pickDeliver &to)
Definition: optimize.cpp:461

Here is the call graph for this function:

Here is the caller graph for this function:

bool pgrouting::vrp::Solution::is_feasable ( ) const
inherited

Definition at line 56 of file solution.cpp.

References pgrouting::vrp::Solution::fleet.

Referenced by decrease_truck(), and pgrouting::vrp::Initial_solution::do_while_foo().

56  {
57  for (const auto v : fleet) {
58  if (v.is_feasable()) continue;
59  return false;
60  }
61  return true;
62 }
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49

Here is the caller graph for this function:

void pgrouting::vrp::Optimize::move_duration_based ( )
void pgrouting::vrp::Optimize::move_order ( Order  order,
Vehicle_pickDeliver from_truck,
Vehicle_pickDeliver to_truck 
)
private

Definition at line 544 of file optimize.cpp.

References pgrouting::vrp::Vehicle_pickDeliver::erase(), pgrouting::vrp::Vehicle_pickDeliver::has_order(), pgrouting::vrp::Vehicle_pickDeliver::insert(), and pgassert.

Referenced by move_reduce_cost().

547  {
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 }
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81

Here is the call graph for this function:

Here is the caller graph for this function:

bool pgrouting::vrp::Optimize::move_reduce_cost ( Vehicle_pickDeliver from,
Vehicle_pickDeliver to 
)
private

Definition at line 461 of file optimize.cpp.

References pgrouting::Pgr_messages::dbg_log, pgrouting::vrp::Solution::fleet, pgrouting::Identifier::id(), pgrouting::Pgr_messages::log, move_order(), pgrouting::vrp::PD_problem::msg, pgassert, and save_if_best().

Referenced by inter_swap().

463  {
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 }
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
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49
std::ostringstream dbg_log
Definition: pgr_messages.h:108
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
static Pgr_messages msg
Definition: pd_problem.h:48

Here is the call graph for this function:

Here is the caller graph for this function:

void pgrouting::vrp::Optimize::move_wait_time_based ( )
bool pgrouting::vrp::Solution::operator< ( const Solution s_rhs) const
inherited

Definition at line 187 of file solution.cpp.

References pgrouting::vrp::Solution::cost().

187  {
188  Vehicle::Cost lhs(cost());
189  Vehicle::Cost rhs(s_rhs.cost());
190 
191  /*
192  * capacity violations
193  */
194  if (std::get<0>(lhs) < std::get<0>(rhs))
195  return true;
196  if (std::get<0>(lhs) > std::get<0>(rhs))
197  return false;
198 
199  /*
200  * time window violations
201  */
202  if (std::get<1>(lhs) < std::get<1>(rhs))
203  return true;
204  if (std::get<1>(lhs) > std::get<1>(rhs))
205  return false;
206 
207  /*
208  * fleet size
209  */
210  if (std::get<2>(lhs) < std::get<2>(rhs))
211  return true;
212  if (std::get<2>(lhs) > std::get<2>(rhs))
213  return false;
214 
215  /*
216  * waiting time
217  */
218  if (std::get<3>(lhs) < std::get<3>(rhs))
219  return true;
220  if (std::get<3>(lhs) > std::get<3>(rhs))
221  return false;
222 
223  /*
224  * duration
225  */
226  if (std::get<4>(lhs) < std::get<4>(rhs))
227  return true;
228  if (std::get<4>(lhs) > std::get<4>(rhs))
229  return false;
230 
231  return false;
232 }
Vehicle::Cost cost() const
Definition: solution.cpp:119
std::tuple< int, int, size_t, double, double > Cost
Definition: vehicle.h:86

Here is the call graph for this function:

void pgrouting::vrp::Optimize::save_if_best ( )
private

Definition at line 629 of file optimize.cpp.

References best_solution, pgrouting::vrp::Solution::cost_str(), pgrouting::Pgr_messages::dbg_log, pgrouting::vrp::Solution::duration(), pgrouting::vrp::Solution::fleet, pgrouting::Pgr_messages::log, pgrouting::vrp::PD_problem::msg, and pgrouting::vrp::Solution::tau().

Referenced by decrease_truck(), delete_empty_truck(), move_reduce_cost(), and swap_order().

629  {
630  if (duration() < best_solution.duration()) {
631  best_solution = (*this);
632  msg.log << "\n*********** best by duration"
633  << best_solution.cost_str();
634 #ifndef NDEBUG
635  msg.dbg_log << best_solution.tau("best by duration");
636 #endif
637  }
638  if (fleet.size() < best_solution.fleet.size()) {
639  best_solution = (*this);
640  msg.log << "\n*********** best by fleet size"
641  << best_solution.cost_str();
642 #ifndef NDEBUG
643  msg.dbg_log << best_solution.tau("best by fleet size");
644 #endif
645  }
646 }
std::ostringstream log
Stores the hint information.
Definition: pgr_messages.h:102
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49
std::ostringstream dbg_log
Definition: pgr_messages.h:108
std::string tau(const std::string &title="Tau") const
Definition: solution.cpp:153
static Pgr_messages msg
Definition: pd_problem.h:48
std::string cost_str() const
Definition: solution.cpp:138
double duration() const
Definition: solution.cpp:65

Here is the call graph for this function:

Here is the caller graph for this function:

void pgrouting::vrp::Optimize::sort_by_duration ( )
private

Definition at line 352 of file optimize.cpp.

References pgrouting::vrp::Vehicle::duration(), and pgrouting::vrp::Solution::fleet.

Referenced by sort_by_size().

352  {
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 }
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49

Here is the call graph for this function:

Here is the caller graph for this function:

void pgrouting::vrp::Optimize::sort_by_id ( )
private

Definition at line 331 of file optimize.cpp.

References pgrouting::vrp::Solution::fleet, pgrouting::vrp::Vehicle_pickDeliver::orders_in_vehicle(), and Identifiers< T >::size().

331  {
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 }
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49

Here is the call graph for this function:

void pgrouting::vrp::Optimize::sort_by_size ( )
private

Definition at line 341 of file optimize.cpp.

References pgrouting::vrp::Solution::fleet, pgrouting::vrp::Vehicle_pickDeliver::orders_in_vehicle(), Identifiers< T >::size(), and sort_by_duration().

Referenced by inter_swap(), and Optimize().

341  {
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 }
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49

Here is the call graph for this function:

Here is the caller graph for this function:

void pgrouting::vrp::Optimize::sort_for_move ( )
private

Definition at line 559 of file optimize.cpp.

References pgrouting::vrp::Solution::fleet, pgrouting::vrp::Vehicle_pickDeliver::orders_size(), and pgrouting::vrp::Vehicle::total_wait_time().

559  {
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 }
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49

Here is the call graph for this function:

bool pgrouting::vrp::Optimize::swap_order ( )
private

Definition at line 253 of file optimize.cpp.

References pgrouting::vrp::Swap_bk::empty(), pgrouting::vrp::Solution::fleet, pgrouting::Pgr_messages::log, pgrouting::vrp::PD_problem::msg, p_swaps, pgassert, pgrouting::vrp::Swap_bk::pop(), save_if_best(), and pgrouting::vrp::Swap_bk::top().

Referenced by inter_swap().

253  {
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 }
std::ostringstream log
Stores the hint information.
Definition: pgr_messages.h:102
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
static Pgr_messages msg
Definition: pd_problem.h:48

Here is the call graph for this function:

Here is the caller graph for this function:

bool pgrouting::vrp::Optimize::swap_order ( Order  from_order,
Vehicle_pickDeliver from_truck,
Order  to_order,
Vehicle_pickDeliver to_truck 
)
private

Definition at line 305 of file optimize.cpp.

References pgrouting::vrp::Vehicle_pickDeliver::erase(), pgrouting::vrp::Vehicle_pickDeliver::has_order(), pgrouting::vrp::Vehicle_pickDeliver::insert(), and pgassert.

309  {
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 }
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81

Here is the call graph for this function:

bool pgrouting::vrp::Optimize::swap_worse ( Vehicle_pickDeliver from,
Vehicle_pickDeliver to 
)
private

Definition at line 137 of file optimize.cpp.

References best_solution, pgrouting::vrp::Solution::duration(), Identifiers< T >::front(), pgrouting::Identifier::idx(), pgrouting::Pgr_messages::log, pgrouting::vrp::PD_problem::msg, pgrouting::vrp::Vehicle_pickDeliver::orders(), pgrouting::vrp::Vehicle_pickDeliver::orders_in_vehicle(), p_swaps, pgassert, pgrouting::vrp::Swap_bk::push(), and Identifiers< T >::size().

Referenced by inter_swap().

137  {
138 #if 0
139  pgassert(from.orders_in_vehicle().size() <= to.orders_in_vehicle().size());
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 }
std::ostringstream log
Stores the hint information.
Definition: pgr_messages.h:102
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
static Pgr_messages msg
Definition: pd_problem.h:48
double duration() const
Definition: solution.cpp:65
void push(const Swap_info &data)
Definition: book_keeping.h:125

Here is the call graph for this function:

Here is the caller graph for this function:

std::string pgrouting::vrp::Solution::tau ( const std::string &  title = "Tau") const
inherited

Definition at line 153 of file solution.cpp.

References pgrouting::vrp::Solution::cost(), pgrouting::vrp::Solution::cost_str(), and pgrouting::vrp::Solution::fleet.

Referenced by inter_swap(), pgrouting::vrp::operator<<(), Optimize(), pgrouting::vrp::Pgr_pickDeliver::optimize(), and save_if_best().

153  {
154  Vehicle::Cost s_cost(cost());
155  std::ostringstream log;
156 
157  log << "\n" << title << ": " << std::endl;
158  for (const auto v : fleet) {
159  log << "\n" << v.tau();
160  }
161  log << "\n" << cost_str() << "\n";
162  return log.str();
163 }
Vehicle::Cost cost() const
Definition: solution.cpp:119
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49
std::string cost_str() const
Definition: solution.cpp:138
std::tuple< int, int, size_t, double, double > Cost
Definition: vehicle.h:86

Here is the call graph for this function:

Here is the caller graph for this function:

double pgrouting::vrp::Solution::total_service_time ( ) const
inherited

Definition at line 101 of file solution.cpp.

References pgrouting::vrp::Solution::fleet.

101  {
102  double total(0);
103  for (const auto v : fleet) {
104  total += v.total_service_time();
105  }
106  return total;
107 }
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49
double pgrouting::vrp::Solution::total_travel_time ( ) const
inherited

Definition at line 92 of file solution.cpp.

References pgrouting::vrp::Solution::fleet.

92  {
93  double total(0);
94  for (const auto v : fleet) {
95  total += v.total_travel_time();
96  }
97  return total;
98 }
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49
int pgrouting::vrp::Solution::twvTot ( ) const
inherited

Definition at line 74 of file solution.cpp.

References pgrouting::vrp::Solution::fleet.

74  {
75  int total(0);
76  for (const auto v : fleet) {
77  total += v.twvTot();
78  }
79  return total;
80 }
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49
double pgrouting::vrp::Solution::wait_time ( ) const
inherited

Definition at line 83 of file solution.cpp.

References pgrouting::vrp::Solution::fleet.

83  {
84  double total(0);
85  for (const auto v : fleet) {
86  total += v.total_wait_time();
87  }
88  return total;
89 }
std::deque< Vehicle_pickDeliver > fleet
Definition: solution.h:49

Member Data Documentation

Solution pgrouting::vrp::Optimize::best_solution
double pgrouting::vrp::Solution::EPSILON
protectedinherited

Definition at line 48 of file solution.h.

Referenced by pgrouting::vrp::Solution::operator=().

Swap_bk pgrouting::vrp::Optimize::p_swaps
private

Definition at line 82 of file optimize.h.

Referenced by inter_swap(), swap_order(), and swap_worse().


The documentation for this class was generated from the following files: