vrpRouting  0.3
Public Member Functions | Public Attributes | Protected Attributes | Private Types | Private Member Functions | Private Attributes | List of all members
vrprouting::optimizers::simple::Optimize Class Reference

#include "simple.h"

Inheritance diagram for vrprouting::optimizers::simple::Optimize:
Inheritance graph
[legend]
Collaboration diagram for vrprouting::optimizers::simple::Optimize:
Collaboration graph
[legend]

Public Member Functions

 Optimize (const problem::Solution &solution, size_t times, const Initials_code &)
 
std::tuple< int, int, size_t, TInterval, TInterval, TInterval > cost () const
 Get all statistics in one cycle. More...
 
std::string cost_str () const
 
int cvTot () const
 Total number of capacity constraint violations of the solution. More...
 
void decrease_truck ()
 
TInterval duration () const
 Total duration of the solution. More...
 
const std::deque< Vehicle_pickDeliver > & fleet () const
 Get the current fleet solution. More...
 
Initials_code get_kind () const
 
std::vector< Solution_rt > get_postgres_result () const
 get solution like postgres needs it More...
 
std::vector< Short_vehicle > get_stops () const
 get solution like postgres needs it More...
 
void inter_swap (size_t times)
 
bool is_feasible () const
 is the solution feasible? More...
 
void move_duration_based ()
 
void move_wait_time_based ()
 
Pgr_messages & msg ()
 
double objective () const
 Get the value of the objective function. More...
 
bool operator< (const Solution &) const
 
const Orders & orders () const
 
std::string tau (const std::string &title="Tau") const
 writing the solution in compact form into a string More...
 
TInterval total_service_time () const
 Total service time of the solution. More...
 
TInterval total_travel_time () const
 Total travel time of the solution. More...
 
int twvTot () const
 Total number of time windows constraint violations of the solution. More...
 
Fleet & vehicles ()
 
TInterval wait_time () const
 Total waiting time of the solution. More...
 

Public Attributes

Solution best_solution
 

Protected Attributes

std::deque< Vehicle_pickDeliver > m_fleet
 The current solution. More...
 
Pgr_messages m_msg
 
Orders m_orders
 the problem info More...
 
Fleet m_trucks
 

Private Types

using Initials_code = initialsol::simple::Initials_code
 

Private Member Functions

bool decrease_truck (size_t)
 
void delete_empty_truck ()
 
bool inter_swap ()
 
bool move_order (problem::Order order, problem::Vehicle_pickDeliver &from_truck, problem::Vehicle_pickDeliver &to_truck)
 moves an order to an non empty vehicle More...
 
bool move_reduce_cost (problem::Vehicle_pickDeliver &from, problem::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 (problem::Order from_order, problem::Vehicle_pickDeliver &from_truck, problem::Order to_order, problem::Vehicle_pickDeliver &to_truck)
 
bool swap_worse (problem::Vehicle_pickDeliver &from, problem::Vehicle_pickDeliver &to)
 

Private Attributes

Initials_code m_kind
 

Detailed Description

Definition at line 40 of file optimizers/simple.h.

Member Typedef Documentation

◆ Initials_code

using vrprouting::optimizers::simple::Optimize::Initials_code = initialsol::simple::Initials_code
private

Definition at line 41 of file optimizers/simple.h.

Constructor & Destructor Documentation

◆ Optimize()

vrprouting::optimizers::simple::Optimize::Optimize ( const problem::Solution &  solution,
size_t  times,
const Initials_code &  p_kind 
)

Definition at line 42 of file optimizers/simple.cpp.

45  :
46  problem::Solution(old_solution),
47  best_solution(old_solution),
48  m_kind(p_kind) {
49  inter_swap(times);
50  this->m_fleet = best_solution.fleet();
51  msg().log << tau("bestSol before sort by size");
52  sort_by_size();
53  msg().log << tau("bestSol after sort by size");
54  msg().log << tau();
55  }

References best_solution, inter_swap(), vrprouting::Pgr_messages::log, vrprouting::problem::Solution::m_fleet, vrprouting::problem::Solution::msg(), sort_by_size(), and vrprouting::problem::Solution::tau().

Member Function Documentation

◆ cost()

std::tuple< int, int, size_t, TInterval, TInterval, TInterval > Solution::cost ( ) const
inherited

Get all statistics in one cycle.

Returns
totals of
idx variable
0 twv
1 cv
2 fleet size
3 waiting time
4 duration
5 travel time
std::get<idx>

Definition at line 218 of file solution.cpp.

218  {
219  TInterval total_duration(0);
220  TInterval total_wait_time(0);
221  TInterval total_tt(0);
222  int total_twv(0);
223  int total_cv(0);
224  /*
225  * Cycle the fleet
226  */
227  for (const auto& v : m_fleet) {
228  total_duration += v.duration();
229  total_wait_time += v.total_wait_time();
230  total_twv += v.twvTot();
231  total_cv += v.cvTot();
232  total_tt += v.total_travel_time();
233  }
234  /*
235  * build the tuple
236  */
237  return std::make_tuple(
238  total_twv, total_cv, m_fleet.size(),
239  total_wait_time, total_duration,
240  total_tt);
241 }

References vrprouting::problem::Solution::m_fleet.

Referenced by vrprouting::problem::Solution::cost_str(), and vrprouting::problem::Solution::operator<().

◆ cost_str()

std::string Solution::cost_str ( ) const
inherited
Returns
The costs in one string

Definition at line 246 of file solution.cpp.

246  {
247  /*
248  * get the cost
249  */
250  auto s_cost(cost());
251  std::ostringstream log;
252 
253  /*
254  * Build the string
255  */
256  log << std::fixed << std::setprecision(4)
257  << "twv=" << std::get<0>(s_cost)
258  << " cv=" << std::get<1>(s_cost)
259  << " wait=" << std::get<3>(s_cost)
260  << " duration=" << std::get<4>(s_cost)
261  << " tt=" << std::get<5>(s_cost);
262 
263  return log.str();
264 }

References vrprouting::problem::Solution::cost().

Referenced by vrprouting::problem::Solution::tau().

◆ cvTot()

int Solution::cvTot ( ) const
inherited

Total number of capacity constraint violations of the solution.

Returns
Total number of capacity violations The total capacity violations of the solution is the sum of the capacity violations of all vehicles

Definition at line 196 of file solution.cpp.

196  {
197  return std::accumulate(begin(m_fleet), end(m_fleet), 0,
198  [](int i, const Vehicle_pickDeliver& v) {return v.cvTot() + i;});
199 }

References vrprouting::problem::Vehicle::cvTot(), and vrprouting::problem::Solution::m_fleet.

Referenced by vrprouting::problem::Solution::get_postgres_result().

◆ decrease_truck() [1/2]

void vrprouting::optimizers::simple::Optimize::decrease_truck ( )

Definition at line 534 of file optimizers/simple.cpp.

534  {
535  bool decreased(false);
536  for (size_t i = 1; i < m_fleet.size(); ++i) {
537  decreased = decrease_truck(i) || decreased;
538  }
539  if (decreased) {
540  delete_empty_truck();
541  save_if_best();
542  decrease_truck();
543  }
544  save_if_best();
545 }

References delete_empty_truck(), vrprouting::problem::Solution::m_fleet, and save_if_best().

Referenced by inter_swap().

◆ decrease_truck() [2/2]

bool vrprouting::optimizers::simple::Optimize::decrease_truck ( size_t  cycle)
private

Definition at line 548 of file optimizers/simple.cpp.

548  {
549  auto position = cycle;
550  for (auto orders = m_fleet[position].orders_in_vehicle();
551  !orders.empty();
552  orders.pop_front()) {
553  /* Step 2: grab an order */
554  auto order = m_fleet[position].orders()[orders.front()];
555  pgassert(order.idx() == orders.front());
556 
557 
558  /* Step 3:
559  * cycle the fleet
560  * insert in first truck possible
561  */
562 
563  for (size_t i = 0; i < position; ++i) {
564  m_fleet[i].hillClimb(order);
565  pgassert((m_fleet[i].has_order(order) && m_fleet[i].is_feasible()) || !m_fleet[i].has_order(order));
566  if (m_fleet[i].has_order(order)) {
567  /*
568  * delete the order from the current truck
569  */
570  m_fleet[position].erase(order);
571  break;
572  }
573  }
574  }
575  return m_fleet[position].orders_in_vehicle().empty();
576 }

References vrprouting::problem::Solution::is_feasible(), vrprouting::problem::Solution::m_fleet, vrprouting::problem::Solution::orders(), and pgassert.

◆ delete_empty_truck()

void vrprouting::optimizers::simple::Optimize::delete_empty_truck ( )
private

Definition at line 363 of file optimizers/simple.cpp.

363  {
364  m_fleet.erase(std::remove_if(
365  m_fleet.begin(),
366  m_fleet.end(),
367  [](const problem::Vehicle_pickDeliver &v){
368  return v.orders_in_vehicle().empty();}),
369  m_fleet.end());
370  save_if_best();
371 }

References vrprouting::problem::Solution::m_fleet, and save_if_best().

Referenced by decrease_truck(), and inter_swap().

◆ duration()

TInterval Solution::duration ( ) const
inherited

Total duration of the solution.

Returns
the solution's duration

The solution duration is the sum of the durations of all vehicles

Definition at line 140 of file solution.cpp.

140  {
141  return std::accumulate(begin(m_fleet), end(m_fleet), static_cast<TInterval>(0),
142  [](TInterval i, const Vehicle_pickDeliver& v) {return v.duration() + i;});
143 }

References vrprouting::problem::Vehicle::duration(), and vrprouting::problem::Solution::m_fleet.

Referenced by vrprouting::problem::Solution::get_postgres_result(), save_if_best(), and swap_worse().

◆ fleet()

const std::deque<Vehicle_pickDeliver>& vrprouting::problem::Solution::fleet ( ) const
inlineinherited

Get the current fleet solution.

Definition at line 107 of file solution.h.

107 {return m_fleet;}

References vrprouting::problem::Solution::m_fleet.

Referenced by vrprouting::optimizers::tabu::Optimize::intensify(), and vrprouting::optimizers::tabu::Optimize::Optimize().

◆ get_kind()

Initials_code vrprouting::optimizers::simple::Optimize::get_kind ( ) const
inline

Definition at line 56 of file optimizers/simple.h.

56 {return m_kind;}

References m_kind.

Referenced by move_order(), move_reduce_cost(), swap_order(), and swap_worse().

◆ get_postgres_result()

std::vector< Solution_rt > Solution::get_postgres_result ( ) const
inherited

get solution like postgres needs it

Returns
container for postgres

Definition at line 61 of file solution.cpp.

61  {
62  std::vector<Solution_rt> result;
63 
64  /* postgres numbering starts with 1 */
65  int i(1);
66 
67  for (auto v : m_fleet) {
68  v.evaluate(0);
69  auto data = v.get_postgres_result(i);
70  /*
71  * Results adjusted for the depot and the first stop
72  * So the vehicle waits on the depot not on the first stop
73  */
74  data[1].arrivalTime = data[1].operationTime;
75  data[0].waitDuration = data[1].waitDuration;
76  data[1].waitDuration = 0;
77  data[0].departureTime = data[0].arrivalTime + data[0].waitDuration;
78 
79 
80  result.insert(result.end(), data.begin(), data.end());
81  ++i;
82  }
83 
84  Solution_rt aggregates = {
85  /*
86  * Vehicle id = -2 indicates its an aggregate row
87  *
88  * (twv, cv, fleet, wait, duration)
89  */
90  -2, // summary row on vehicle_number
91  twvTot(), // on vehicle_id
92  cvTot(), // on vehicle_seq
93  -1, // on order_id
94  -1, // on stop_id
95  -2, // on stop_type (gets increased later by one so it gets -1)
96  -1, // not accounting total loads
97  static_cast<int64_t>(total_travel_time()),
98  -1, // not accounting arrival_travel_time
99  static_cast<int64_t>(wait_time()),
100  -1, // not accounting operation time
101  static_cast<int64_t>(total_service_time()),
102  static_cast<int64_t>(duration()),
103  cvTot(),
104  twvTot()
105  };
106  result.push_back(aggregates);
107 
108  return result;
109 }

References vrprouting::problem::Solution::cvTot(), vrprouting::problem::Solution::duration(), vrprouting::problem::Solution::m_fleet, vrprouting::problem::Solution::total_service_time(), vrprouting::problem::Solution::total_travel_time(), vrprouting::problem::Solution::twvTot(), and vrprouting::problem::Solution::wait_time().

◆ get_stops()

std::vector< Short_vehicle > Solution::get_stops ( ) const
inherited

get solution like postgres needs it

Returns
container for postgres

Definition at line 49 of file solution.cpp.

49  {
50  std::vector<Short_vehicle> result;
51  for (auto v : m_fleet) {
52  result.push_back(Short_vehicle{v.id(), v.get_stops()});
53  }
54  return result;
55 }

References Short_vehicle::id, and vrprouting::problem::Solution::m_fleet.

◆ inter_swap() [1/2]

bool vrprouting::optimizers::simple::Optimize::inter_swap ( )
private

Definition at line 87 of file optimizers/simple.cpp.

87  {
88  msg().log
89  << "\n" <<tau("before inter swap");
90  delete_empty_truck();
91  auto swapped_f = false;
92  /*
93  * .. to ... from ....
94  */
95  for (auto &from : m_fleet) {
96  for (auto &to : m_fleet) {
97  if (&from == &to) break;
98 
99 #if 0
100  msg().log
101  << "\n to " << to.id()
102  << "from " << from.id();
103  auto swapped = false;
104 #endif
105  swap_worse(to, from);
106  move_reduce_cost(from, to);
107 #if 0
108  msg().log << "++++++++" << p_swaps;
109 #endif
110  }
111  }
112 
113 #if 0
114  while (!p_swaps.empty()) {
115  swapped_f = swap_order() || swapped_f;
116  }
117 #endif
118 
119  msg().log
120  << "\n" <<tau("after");
121  delete_empty_truck();
122 
123  return swapped_f;
124 }

References delete_empty_truck(), vrprouting::Pgr_messages::log, vrprouting::problem::Solution::m_fleet, move_reduce_cost(), vrprouting::problem::Solution::msg(), swap_order(), swap_worse(), and vrprouting::problem::Solution::tau().

Referenced by inter_swap(), and Optimize().

◆ inter_swap() [2/2]

void vrprouting::optimizers::simple::Optimize::inter_swap ( size_t  times)

Definition at line 59 of file optimizers/simple.cpp.

59  {
60  msg().log << tau("before sort by size");
61  sort_by_size();
62  msg().log << tau("before decrease");
63  decrease_truck();
64  msg().log << tau("after decrease");
65  sort_by_size();
66  msg().log << tau("after sort by size");
67 
68  size_t i = 0;
69  while (i++ < times) {
70  msg().log << "\n*************************** CYCLE" << i;
71  inter_swap();
72  msg().log << tau("after inter swap");
73  std::rotate(m_fleet.begin(), m_fleet.begin() + 1, m_fleet.end());
74  msg().log << tau("before next cycle");
75  }
76 }

References decrease_truck(), inter_swap(), vrprouting::Pgr_messages::log, vrprouting::problem::Solution::m_fleet, vrprouting::problem::Solution::msg(), sort_by_size(), and vrprouting::problem::Solution::tau().

◆ is_feasible()

bool Solution::is_feasible ( ) const
inherited

is the solution feasible?

The solution is feasible when all vehicles are feasible.

Returns
true when all vehicles in solution are feasible

Definition at line 129 of file solution.cpp.

129  {
130  return std::find_if(m_fleet.begin(), m_fleet.end(),
131  [] (const Vehicle_pickDeliver& v) -> bool {return !v.is_feasible();}) == m_fleet.end();
132 }

References vrprouting::problem::Solution::m_fleet.

Referenced by decrease_truck(), vrprouting::initialsol::simple::Initial_solution::do_while_feasible(), vrprouting::initialsol::simple::Initial_solution::do_while_foo(), vrprouting::initialsol::tabu::Initial_solution::Initial_solution(), vrprouting::initialsol::tabu::Initial_solution::process_given_solution_from_user(), and vrprouting::initialsol::tabu::Initial_solution::process_unassigned().

◆ move_duration_based()

void vrprouting::optimizers::simple::Optimize::move_duration_based ( )

◆ move_order()

bool vrprouting::optimizers::simple::Optimize::move_order ( problem::Order  order,
problem::Vehicle_pickDeliver &  from_truck,
problem::Vehicle_pickDeliver &  to_truck 
)
private

moves an order to an non empty vehicle

order: order to be moved from_truck: here is the order to truck: truck to put the order

to check if the order was inserted: to_truck.has_order(order)

Returns
bool: when move was done

Definition at line 467 of file optimizers/simple.cpp.

470  {
471  pgassert(from_truck.has_order(order));
472  pgassert(!to_truck.has_order(order));
473  /*
474  * don't move to empty truck
475  */
476  if (to_truck.empty()) return false;
477 
478  /*
479  * don't move from a real truck to a phoney truck
480  */
481  if (!from_truck.is_phony() && to_truck.is_phony()) return false;
482 
483  /*
484  * Don't move from a vehicle with more orders
485  */
486  if (from_truck.size() > to_truck.size()) return false;
487 
488  /*
489  * insert the order
490  */
491  get_kind() == initialsol::simple::Initials_code::OneDepot?
492  to_truck.semiLIFO(order) :
493  to_truck.hillClimb(order);
494 
495  if (to_truck.has_order(order)) {
496  from_truck.erase(order);
497 
498  pgassert(!(from_truck.has_order(order) && to_truck.has_order(order)));
499  pgassert(!from_truck.has_order(order));
500  pgassert(to_truck.has_order(order));
501  return true;
502  }
503 
504  pgassert(!(from_truck.has_order(order) && to_truck.has_order(order)));
505  pgassert(from_truck.has_order(order));
506  pgassert(!to_truck.has_order(order));
507  return false;
508 }

References vrprouting::problem::Vehicle_pickDeliver::empty(), vrprouting::problem::Vehicle_pickDeliver::erase(), get_kind(), vrprouting::problem::Vehicle_pickDeliver::has_order(), vrprouting::problem::Vehicle_pickDeliver::hillClimb(), vrprouting::problem::Vehicle::is_phony(), vrprouting::initialsol::simple::OneDepot, pgassert, and vrprouting::problem::Vehicle_pickDeliver::semiLIFO().

Referenced by swap_worse().

◆ move_reduce_cost()

bool vrprouting::optimizers::simple::Optimize::move_reduce_cost ( problem::Vehicle_pickDeliver &  from,
problem::Vehicle_pickDeliver &  to 
)
private

Definition at line 385 of file optimizers/simple.cpp.

387  {
388  pgassert(&from != &to);
389 
390  auto from_truck = from;
391  auto to_truck = to;
392  /*
393  * don't move to empty truck
394  */
395  if (to_truck.empty()) return false;
396 
397  /*
398  * don't move from a real truck to a phoney truck
399  */
400  if (!from_truck.is_phony() && to_truck.is_phony()) {
401  return false;
402  }
403 
404  auto moved = false;
405 
406  auto from_orders = from_truck.orders_in_vehicle();
407  for (const auto o_id : from_orders) {
408  /*
409  * removing an order decreases the duration
410  */
411  auto order = from_truck.orders()[o_id];
412 
413  auto curr_duration = from_truck.duration() + to_truck.duration();
414  /*
415  * insert it in the "to" truck
416  */
417  pgassert(!to_truck.has_order(order));
418  get_kind() == initialsol::simple::Initials_code::OneDepot?
419  to_truck.semiLIFO(order) :
420  to_truck.hillClimb(order);
421  pgassert((to_truck.has_order(order) && to_truck.is_feasible()) || !to_truck.has_order(order));
422 
423  if (to_truck.has_order(order)) {
424  from_truck.erase(order);
425 
426  auto new_duration = from_truck.duration() + to_truck.duration();
427 
428  /*
429  * cost is reduced
430  */
431  if (new_duration < curr_duration
432  || from_truck.empty()
433  || new_duration < best_solution.duration()) {
434  moved = true;
435  save_if_best();
436  continue;
437  }
438 
439  /*
440  * cost is not reduced
441  * revert changes
442  */
443  to_truck.erase(order);
444  get_kind() == initialsol::simple::Initials_code::OneDepot?
445  from_truck.semiLIFO(order) :
446  from_truck.hillClimb(order);
447  }
448  }
449  return moved;
450 }

References best_solution, get_kind(), vrprouting::initialsol::simple::OneDepot, vrprouting::problem::Vehicle_pickDeliver::orders_in_vehicle(), pgassert, and save_if_best().

Referenced by inter_swap().

◆ move_wait_time_based()

void vrprouting::optimizers::simple::Optimize::move_wait_time_based ( )

◆ msg()

Pgr_messages& vrprouting::problem::Solution::msg ( )
inlineinherited

Definition at line 119 of file solution.h.

119 {return m_msg;}

References vrprouting::problem::Solution::m_msg.

Referenced by vrprouting::initialsol::simple::Initial_solution::do_while_foo(), inter_swap(), vrprouting::optimizers::tabu::Optimize::move_2_real(), vrprouting::initialsol::simple::Initial_solution::one_truck_all_orders(), Optimize(), vrprouting::optimizers::tabu::Optimize::Optimize(), vrprouting::initialsol::tabu::Initial_solution::process_unassigned(), save_if_best(), and vrprouting::optimizers::tabu::Optimize::tabu_search().

◆ objective()

double vrprouting::problem::Solution::objective ( ) const
inlineinherited

Get the value of the objective function.

Definition at line 110 of file solution.h.

110 {return static_cast<double>(total_travel_time());}

References vrprouting::problem::Solution::total_travel_time().

Referenced by vrprouting::optimizers::tabu::Optimize::move_2_real(), vrprouting::optimizers::tabu::Optimize::single_pair_insertion(), vrprouting::optimizers::tabu::Optimize::swap_between_routes(), and vrprouting::optimizers::tabu::Optimize::tabu_search().

◆ operator<()

bool Solution::operator< ( const Solution &  s_rhs) const
inherited

Definition at line 267 of file solution.cpp.

267  {
268  auto lhs(cost());
269  auto rhs(s_rhs.cost());
270 
271  /*
272  * time window violations
273  */
274  if (std::get<0>(lhs) < std::get<0>(rhs))
275  return true;
276  if (std::get<0>(lhs) > std::get<0>(rhs))
277  return false;
278 
279  /*
280  * capacity violations
281  */
282  if (std::get<1>(lhs) < std::get<1>(rhs))
283  return true;
284  if (std::get<1>(lhs) > std::get<1>(rhs))
285  return false;
286 
287  /*
288  * fleet size
289  */
290  if (std::get<2>(lhs) < std::get<2>(rhs))
291  return true;
292  if (std::get<2>(lhs) > std::get<2>(rhs))
293  return false;
294 
295  /*
296  * waiting time
297  */
298  if (std::get<3>(lhs) < std::get<3>(rhs))
299  return true;
300  if (std::get<3>(lhs) > std::get<3>(rhs))
301  return false;
302 
303  /*
304  * duration
305  */
306  if (std::get<4>(lhs) < std::get<4>(rhs))
307  return true;
308  if (std::get<4>(lhs) > std::get<4>(rhs))
309  return false;
310 
311  return false;
312 }

References vrprouting::problem::Solution::cost().

◆ orders()

const Orders& vrprouting::problem::Solution::orders ( ) const
inlineinherited

Definition at line 120 of file solution.h.

120 {return m_orders;}

References vrprouting::problem::Solution::m_orders.

Referenced by decrease_truck(), vrprouting::optimizers::tabu::Optimize::diversify(), vrprouting::optimizers::tabu::Optimize::move_2_real(), vrprouting::initialsol::tabu::Initial_solution::process_given_solution_from_user(), vrprouting::initialsol::tabu::Initial_solution::process_unassigned(), vrprouting::optimizers::tabu::Optimize::set_tabu_list_length(), vrprouting::optimizers::tabu::Optimize::single_pair_insertion(), and vrprouting::optimizers::tabu::Optimize::swap_between_routes().

◆ save_if_best()

void vrprouting::optimizers::simple::Optimize::save_if_best ( )
private

Definition at line 579 of file optimizers/simple.cpp.

579  {
580  if (duration() < best_solution.duration()) {
581  best_solution = (*this);
582  msg().log << "\n*********** best by duration"
583  << best_solution.cost_str();
584 #if 0
585  msg().dbg_log << best_solution.tau("best by duration");
586 #endif
587  }
588  if (m_fleet.size() < best_solution.fleet().size()) {
589  best_solution = (*this);
590  msg().log << "\n*********** best by fleet size"
591  << best_solution.cost_str();
592 #if 0
593  msg().dbg_log << best_solution.tau("best by fleet size");
594 #endif
595  }
596 }

References best_solution, vrprouting::problem::Solution::duration(), vrprouting::Pgr_messages::log, vrprouting::problem::Solution::m_fleet, and vrprouting::problem::Solution::msg().

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

◆ sort_by_duration()

void vrprouting::optimizers::simple::Optimize::sort_by_duration ( )
private

Definition at line 354 of file optimizers/simple.cpp.

354  {
355  std::sort(m_fleet.begin(), m_fleet.end(), []
356  (const problem::Vehicle_pickDeliver &lhs, const problem::Vehicle_pickDeliver &rhs)
357  -> bool {
358  return lhs.duration() > rhs.duration();
359  });
360 }

References vrprouting::problem::Solution::m_fleet.

Referenced by sort_by_size().

◆ sort_by_id()

void vrprouting::optimizers::simple::Optimize::sort_by_id ( )
private

Definition at line 333 of file optimizers/simple.cpp.

333  {
334  std::sort(m_fleet.begin(), m_fleet.end(), []
335  (const problem::Vehicle_pickDeliver &lhs, const problem::Vehicle_pickDeliver &rhs)
336  -> bool {
337  return lhs.orders_in_vehicle().size()
338  > rhs.orders_in_vehicle().size();
339  });
340 }

References vrprouting::problem::Solution::m_fleet.

◆ sort_by_size()

void vrprouting::optimizers::simple::Optimize::sort_by_size ( )
private

Definition at line 343 of file optimizers/simple.cpp.

343  {
344  sort_by_duration();
345  std::stable_sort(m_fleet.begin(), m_fleet.end(), []
346  (const problem::Vehicle_pickDeliver &lhs, const problem::Vehicle_pickDeliver &rhs)
347  -> bool {
348  return lhs.orders_in_vehicle().size()
349  > rhs.orders_in_vehicle().size();
350  });
351 }

References vrprouting::problem::Solution::m_fleet, and sort_by_duration().

Referenced by inter_swap(), and Optimize().

◆ sort_for_move()

void vrprouting::optimizers::simple::Optimize::sort_for_move ( )
private

Definition at line 511 of file optimizers/simple.cpp.

511  {
512  std::sort(m_fleet.begin(), m_fleet.end(), []
513  (const problem::Vehicle_pickDeliver &lhs, const problem::Vehicle_pickDeliver &rhs)
514  -> bool {
515  return lhs.total_wait_time() > rhs.total_wait_time();
516  });
517 
518  std::stable_sort(m_fleet.begin(), m_fleet.end(), []
519  (const problem::Vehicle_pickDeliver &lhs, const problem::Vehicle_pickDeliver &rhs)
520  -> bool {
521  return lhs.orders_size() > rhs.orders_size();
522  });
523 }

References vrprouting::problem::Solution::m_fleet.

◆ swap_order() [1/2]

bool vrprouting::optimizers::simple::Optimize::swap_order ( )
private

Referenced by inter_swap().

◆ swap_order() [2/2]

bool vrprouting::optimizers::simple::Optimize::swap_order ( problem::Order  from_order,
problem::Vehicle_pickDeliver &  from_truck,
problem::Order  to_order,
problem::Vehicle_pickDeliver &  to_truck 
)
private

Definition at line 269 of file optimizers/simple.cpp.

273  {
274  if (!from_truck.has_order(from_order)
275  || !to_truck.has_order(to_order)) {
276  return false;
277  }
278 
279  pgassert(from_truck.has_order(from_order));
280  pgassert(to_truck.has_order(to_order));
281 
282  from_truck.erase(from_order);
283  to_truck.erase(to_order);
284 
285  /*
286  * insert them in the other truck
287  */
288  if (get_kind() == initialsol::simple::Initials_code::OneDepot) {
289  from_truck.semiLIFO(to_order);
290  to_truck.semiLIFO(from_order);
291  } else {
292  from_truck.hillClimb(to_order);
293  to_truck.hillClimb(from_order);
294  }
295 
296  pgassert((from_truck.has_order(to_order) && from_truck.is_feasible()) || !from_truck.has_order(to_order));
297  pgassert((to_truck.has_order(from_order) && to_truck.is_feasible()) || !to_truck.has_order(from_order));
298 
299  if (!from_truck.has_order(to_order) || !to_truck.has_order(from_order)) {
300  /*
301  * swap generates a violation: restore trucks
302  */
303  if (from_truck.has_order(to_order)) from_truck.erase(to_order);
304  if (to_truck.has_order(from_order)) to_truck.erase(from_order);
305 
306  pgassert(!from_truck.has_order(to_order));
307  pgassert(!from_truck.has_order(from_order));
308  pgassert(!to_truck.has_order(from_order));
309  pgassert(!to_truck.has_order(to_order));
310 
311  /*
312  * insert them again in the truck
313  */
314  if (get_kind() == initialsol::simple::Initials_code::OneDepot) {
315  from_truck.semiLIFO(from_order);
316  to_truck.semiLIFO(to_order);
317  } else {
318  from_truck.hillClimb(from_order);
319  to_truck.hillClimb(to_order);
320  }
321  pgassert((from_truck.has_order(from_order) && from_truck.is_feasible()) || !from_truck.has_order(from_order));
322  pgassert((to_truck.has_order(to_order) && to_truck.is_feasible()) || !to_truck.has_order(to_order));
323 
324  return false;
325  }
326 
327  pgassert(from_truck.has_order(to_order));
328  pgassert(to_truck.has_order(from_order));
329  return true;
330 }

References vrprouting::problem::Vehicle_pickDeliver::erase(), get_kind(), vrprouting::problem::Vehicle_pickDeliver::has_order(), vrprouting::problem::Vehicle_pickDeliver::hillClimb(), vrprouting::problem::Vehicle_pickDeliver::is_feasible(), vrprouting::initialsol::simple::OneDepot, pgassert, and vrprouting::problem::Vehicle_pickDeliver::semiLIFO().

◆ swap_worse()

bool vrprouting::optimizers::simple::Optimize::swap_worse ( problem::Vehicle_pickDeliver &  from,
problem::Vehicle_pickDeliver &  to 
)
private

Definition at line 132 of file optimizers/simple.cpp.

132  {
133  /*
134  * working on a copy of the vehicles
135  */
136  auto from_truck = from;
137  auto to_truck = to;
138 
139  auto swapped = false;
140 
141  /*
142  * To avoid invalidation of cycles
143  */
144  auto o_from_orders = from_truck.orders_in_vehicle();
145  auto o_to_orders = to_truck.orders_in_vehicle();
146 
147  pgassert((o_from_orders * o_to_orders).empty());
148 
149  for (auto from_orders = from_truck.orders_in_vehicle();
150  !from_orders.empty();
151  from_orders.pop_front()) {
152  auto from_order = from_truck.orders()[from_orders.front()];
153 
154  pgassert(from_truck.has_order(from_order));
155 
156  if (move_order(from_order, from_truck, to_truck)) {
157  pgassert(!from_truck.has_order(from_order));
158  pgassert(to_truck.has_order(from_order));
159  /*
160  * The order could be moved to "to" truck
161  */
162  to = to_truck;
163  from = from_truck;
164  /*
165  * go to next order
166  */
167  pgassert(!from.has_order(from_order));
168  pgassert(to.has_order(from_order));
169  pgassert(!from_truck.has_order(from_order));
170  pgassert(to_truck.has_order(from_order));
171  pgassert(!(from.has_order(from_order) && to.has_order(from_order)));
172  pgassert(from.has_order(from_order) || to.has_order(from_order));
173  continue;
174  }
175 
176  pgassert(from_truck.has_order(from_order));
177  auto curr_from_duration = from_truck.duration();
178 
179  for (auto to_order_id : o_to_orders) {
180  auto to_order = to.orders()[to_order_id];
181  /*
182  * The orders might have being swapped before
183  */
184  if (!to_truck.has_order(to_order)) continue;
185  // if (!from_truck.has_order(from_order)) break; // TODO delete line
186 
187  pgassert(from_truck.has_order(from_order));
188  pgassert(to_truck.has_order(to_order));
189 
190  auto curr_to_duration = to_truck.duration();
191 
192  /*
193  * delete from_order, and to order from their trucks
194  */
195  pgassert(from_truck.has_order(from_order));
196  from_truck.erase(from_order);
197  pgassert(to_truck.has_order(to_order));
198  to_truck.erase(to_order);
199 
200  /*
201  * insert them in the other truck
202  */
203  if (get_kind() == initialsol::simple::Initials_code::OneDepot) {
204  from_truck.semiLIFO(to_order);
205  to_truck.semiLIFO(from_order);
206  } else {
207  from_truck.hillClimb(to_order);
208  to_truck.hillClimb(from_order);
209  }
210 
211  pgassert((from_truck.has_order(to_order) && from_truck.is_feasible()) || !from_truck.has_order(to_order));
212  pgassert((to_truck.has_order(from_order) && to_truck.is_feasible()) || !to_truck.has_order(from_order));
213 
214  if (from_truck.has_order(to_order) && to_truck.has_order(from_order)) {
215  auto new_from_duration = from_truck.duration();
216  auto new_to_duration = to_truck.duration();
217 
218  auto estimated_delta =
219  - (curr_from_duration + curr_to_duration)
220  + (new_to_duration + new_from_duration);
221 
222  auto estimated_duration = duration() + estimated_delta;
223 
224  /*
225  * Can swap when:
226  * - or from_truck duration is reduced
227  * - the total fleet duration is reduced
228  * - or the new fleet duration is better than best_solution duration
229  */
230  if (new_from_duration < curr_from_duration ||
231  estimated_delta < 0 ||
232  estimated_duration < best_solution.duration()) {
233  /*
234  * this acctually makes the swapping
235  */
236  to = to_truck;
237  from = from_truck;
238 
239  pgassert(!(from.has_order(from_order) && to.has_order(from_order)));
240  pgassert(from.has_order(from_order) || to.has_order(from_order));
241  pgassert(!(from.has_order(to_order) && to.has_order(to_order)));
242  pgassert(from.has_order(to_order) || to.has_order(to_order));
243 
244  swapped = true;
245  break;
246  }
247  }
248  /*
249  * Can't swap, restore vehicles
250  */
251  to_truck = to;
252  from_truck = from;
253 
254  pgassert(!(from.has_order(from_order) && to.has_order(from_order)));
255  pgassert(from.has_order(from_order) || to.has_order(from_order));
256  pgassert(!(from.has_order(to_order) && to.has_order(to_order)));
257  pgassert(from.has_order(to_order) || to.has_order(to_order));
258  }
259  }
260 
261  return false && swapped;
262 }

References best_solution, vrprouting::problem::Solution::duration(), get_kind(), vrprouting::problem::Vehicle_pickDeliver::has_order(), move_order(), vrprouting::initialsol::simple::OneDepot, vrprouting::problem::Vehicle_pickDeliver::orders(), vrprouting::problem::Vehicle_pickDeliver::orders_in_vehicle(), and pgassert.

Referenced by inter_swap().

◆ tau()

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

writing the solution in compact form into a string

Parameters
[in]titleTitle to Use for the tau
Returns
The solution in one compacted string

Definition at line 116 of file solution.cpp.

116  {
117  std::string str {"\n" + title + ": " + '\n'};
118  for (const auto& v : m_fleet) str += ("\n" + v.tau());
119  str += "\n" + cost_str() + "\n";
120  return str;
121 }

References vrprouting::problem::Solution::cost_str(), and vrprouting::problem::Solution::m_fleet.

Referenced by inter_swap(), Optimize(), and vrprouting::optimizers::tabu::Optimize::Optimize().

◆ total_service_time()

TInterval Solution::total_service_time ( ) const
inherited

Total service time of the solution.

Returns
the total service time of the solution

The total service time of the solution is the sum of the service times of all vehicles

Definition at line 174 of file solution.cpp.

174  {
175  return std::accumulate(begin(m_fleet), end(m_fleet), static_cast<TInterval>(0),
176  [](TInterval i, const Vehicle_pickDeliver& v) {return v.total_service_time() + i;});
177 }

References vrprouting::problem::Solution::m_fleet, and vrprouting::problem::Vehicle::total_service_time().

Referenced by vrprouting::problem::Solution::get_postgres_result().

◆ total_travel_time()

TInterval Solution::total_travel_time ( ) const
inherited

Total travel time of the solution.

Returns
the total waiting time

The total travel time of the solution is the sum of the travel times of all vehicles

Definition at line 162 of file solution.cpp.

162  {
163  return std::accumulate(begin(m_fleet), end(m_fleet), static_cast<TInterval>(0),
164  [](TInterval i, const Vehicle_pickDeliver& v) {return v.total_travel_time() + i;});
165 }

References vrprouting::problem::Solution::m_fleet, and vrprouting::problem::Vehicle::total_travel_time().

Referenced by vrprouting::problem::Solution::get_postgres_result(), and vrprouting::problem::Solution::objective().

◆ twvTot()

int Solution::twvTot ( ) const
inherited

Total number of time windows constraint violations of the solution.

Returns
the total number of time window violations

The total time window violations of the solution is the sum of the time window violations of all vehicles

Definition at line 185 of file solution.cpp.

185  {
186  return std::accumulate(begin(m_fleet), end(m_fleet), 0,
187  [](int i, const Vehicle_pickDeliver& v) {return v.twvTot() + i;});
188 }

References vrprouting::problem::Solution::m_fleet, and vrprouting::problem::Vehicle::twvTot().

Referenced by vrprouting::problem::Solution::get_postgres_result().

◆ vehicles()

Fleet& vrprouting::problem::Solution::vehicles ( )
inlineinherited

Definition at line 121 of file solution.h.

121 {return m_trucks;}

References vrprouting::problem::Solution::m_trucks.

Referenced by vrprouting::initialsol::simple::Initial_solution::do_while_foo(), vrprouting::initialsol::tabu::Initial_solution::Initial_solution(), vrprouting::initialsol::simple::Initial_solution::one_truck_all_orders(), vrprouting::initialsol::tabu::Initial_solution::process_given_solution_from_user(), and vrprouting::initialsol::tabu::Initial_solution::process_unassigned().

◆ wait_time()

TInterval Solution::wait_time ( ) const
inherited

Total waiting time of the solution.

Returns
the total waiting time

The total waiting time of the solution is the sum of the waiting time of all vehicles

Definition at line 151 of file solution.cpp.

151  {
152  return std::accumulate(begin(m_fleet), end(m_fleet), static_cast<TInterval>(0),
153  [](TInterval i, const Vehicle_pickDeliver& v) {return v.total_wait_time() + i;});
154 }

References vrprouting::problem::Solution::m_fleet, and vrprouting::problem::Vehicle::total_wait_time().

Referenced by vrprouting::problem::Solution::get_postgres_result().

Member Data Documentation

◆ best_solution

Solution vrprouting::optimizers::simple::Optimize::best_solution

Definition at line 54 of file optimizers/simple.h.

Referenced by move_reduce_cost(), Optimize(), save_if_best(), and swap_worse().

◆ m_fleet

std::deque<Vehicle_pickDeliver> vrprouting::problem::Solution::m_fleet
protectedinherited

The current solution.

Definition at line 125 of file solution.h.

Referenced by vrprouting::problem::Solution::cost(), vrprouting::problem::Solution::cvTot(), decrease_truck(), delete_empty_truck(), vrprouting::optimizers::tabu::Optimize::diversify(), vrprouting::initialsol::simple::Initial_solution::do_while_foo(), vrprouting::problem::Solution::duration(), vrprouting::problem::Solution::fleet(), vrprouting::problem::Solution::get_postgres_result(), vrprouting::problem::Solution::get_stops(), vrprouting::initialsol::tabu::Initial_solution::Initial_solution(), vrprouting::optimizers::tabu::Optimize::intensify(), inter_swap(), vrprouting::problem::Solution::is_feasible(), vrprouting::optimizers::tabu::Optimize::move_2_real(), vrprouting::initialsol::simple::Initial_solution::one_truck_all_orders(), Optimize(), vrprouting::optimizers::tabu::Optimize::Optimize(), vrprouting::initialsol::tabu::Initial_solution::process_given_solution_from_user(), vrprouting::initialsol::tabu::Initial_solution::process_unassigned(), save_if_best(), vrprouting::optimizers::tabu::Optimize::single_pair_insertion(), sort_by_duration(), sort_by_id(), sort_by_size(), vrprouting::optimizers::tabu::Optimize::sort_by_size(), sort_for_move(), vrprouting::optimizers::tabu::Optimize::swap_between_routes(), vrprouting::optimizers::tabu::Optimize::tabu_search(), vrprouting::problem::Solution::tau(), vrprouting::problem::Solution::total_service_time(), vrprouting::problem::Solution::total_travel_time(), vrprouting::problem::Solution::twvTot(), and vrprouting::problem::Solution::wait_time().

◆ m_kind

Initials_code vrprouting::optimizers::simple::Optimize::m_kind
private

Definition at line 83 of file optimizers/simple.h.

Referenced by get_kind().

◆ m_msg

Pgr_messages vrprouting::problem::Solution::m_msg
protectedinherited

Definition at line 130 of file solution.h.

Referenced by vrprouting::problem::Solution::msg().

◆ m_orders

Orders vrprouting::problem::Solution::m_orders
protectedinherited

the problem info

Definition at line 128 of file solution.h.

Referenced by vrprouting::initialsol::simple::Initial_solution::do_while_feasible(), and vrprouting::problem::Solution::orders().

◆ m_trucks

Fleet vrprouting::problem::Solution::m_trucks
protectedinherited

Definition at line 129 of file solution.h.

Referenced by vrprouting::problem::Solution::vehicles().

The documentation for this class was generated from the following files:
vrprouting::problem::Solution::orders
const Orders & orders() const
Definition: solution.h:120
vrprouting::Pgr_messages::log
std::ostringstream log
Stores the hint information.
Definition: pgr_messages.h:91
vrprouting::problem::Solution::total_service_time
TInterval total_service_time() const
Total service time of the solution.
Definition: solution.cpp:174
vrprouting::problem::Solution::m_fleet
std::deque< Vehicle_pickDeliver > m_fleet
The current solution.
Definition: solution.h:125
vrprouting::problem::Solution::cvTot
int cvTot() const
Total number of capacity constraint violations of the solution.
Definition: solution.cpp:196
vrprouting::problem::Solution::total_travel_time
TInterval total_travel_time() const
Total travel time of the solution.
Definition: solution.cpp:162
vrprouting::optimizers::simple::Optimize::decrease_truck
void decrease_truck()
Definition: optimizers/simple.cpp:534
Short_vehicle::id
Id id
Definition: short_vehicle.h:42
vrprouting::problem::Solution::twvTot
int twvTot() const
Total number of time windows constraint violations of the solution.
Definition: solution.cpp:185
vrprouting::optimizers::simple::Optimize::save_if_best
void save_if_best()
Definition: optimizers/simple.cpp:579
vrprouting::initialsol::simple::OneDepot
@ OneDepot
Push front order that allows more orders to be inserted at the front.
Definition: initialsol/initials_code.h:45
vrprouting::optimizers::simple::Optimize::sort_by_duration
void sort_by_duration()
Definition: optimizers/simple.cpp:354
pgassert
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:95
vrprouting::problem::Solution::wait_time
TInterval wait_time() const
Total waiting time of the solution.
Definition: solution.cpp:151
vrprouting::optimizers::simple::Optimize::get_kind
Initials_code get_kind() const
Definition: optimizers/simple.h:56
vrprouting::problem::Solution::duration
TInterval duration() const
Total duration of the solution.
Definition: solution.cpp:140
Short_vehicle
short_vehicle
Definition: short_vehicle.h:41
vrprouting::optimizers::simple::Optimize::move_reduce_cost
bool move_reduce_cost(problem::Vehicle_pickDeliver &from, problem::Vehicle_pickDeliver &to)
Definition: optimizers/simple.cpp:385
Solution_rt
Solution schedule when twv & cw are hard restrictions.
Definition: solution_rt.h:56
vrprouting::problem::Solution::msg
Pgr_messages & msg()
Definition: solution.h:119
vrprouting::problem::Solution::tau
std::string tau(const std::string &title="Tau") const
writing the solution in compact form into a string
Definition: solution.cpp:116
vrprouting::optimizers::simple::Optimize::sort_by_size
void sort_by_size()
Definition: optimizers/simple.cpp:343
vrprouting::problem::Solution::m_msg
Pgr_messages m_msg
Definition: solution.h:130
vrprouting::problem::Solution::cost
std::tuple< int, int, size_t, TInterval, TInterval, TInterval > cost() const
Get all statistics in one cycle.
Definition: solution.cpp:218
vrprouting::problem::Solution::is_feasible
bool is_feasible() const
is the solution feasible?
Definition: solution.cpp:129
vrprouting::optimizers::simple::Optimize::delete_empty_truck
void delete_empty_truck()
Definition: optimizers/simple.cpp:363
vrprouting::optimizers::simple::Optimize::swap_order
bool swap_order()
TInterval
int64_t TInterval
Definition: typedefs.h:72
vrprouting::optimizers::simple::Optimize::swap_worse
bool swap_worse(problem::Vehicle_pickDeliver &from, problem::Vehicle_pickDeliver &to)
Definition: optimizers/simple.cpp:132
vrprouting::optimizers::simple::Optimize::inter_swap
bool inter_swap()
Definition: optimizers/simple.cpp:87
vrprouting::problem::Solution::m_trucks
Fleet m_trucks
Definition: solution.h:129
vrprouting::problem::Solution::m_orders
Orders m_orders
the problem info
Definition: solution.h:128
vrprouting::optimizers::simple::Optimize::m_kind
Initials_code m_kind
Definition: optimizers/simple.h:83
vrprouting::optimizers::simple::Optimize::move_order
bool move_order(problem::Order order, problem::Vehicle_pickDeliver &from_truck, problem::Vehicle_pickDeliver &to_truck)
moves an order to an non empty vehicle
Definition: optimizers/simple.cpp:467
vrprouting::optimizers::simple::Optimize::best_solution
Solution best_solution
Definition: optimizers/simple.h:54
vrprouting::problem::Solution::cost_str
std::string cost_str() const
Definition: solution.cpp:246