Class that optimizes a solution. More...

#include "tabu.h"

Inheritance diagram for vrprouting::optimizers::tabu::Optimize:

Collaboration diagram for vrprouting::optimizers::tabu::Optimize:

[legend]

Public Member Functions
	Optimize (const problem::Solution &solution, size_t times, bool stop_on_all_served, bool)
	Optimization operation. More...

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...

TInterval	duration () const
	Total duration of the solution. More...

const std::deque< Vehicle_pickDeliver > &	fleet () const
	Get the current fleet solution. More...

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...

bool	is_feasible () const
	is the solution feasible? More...

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
problem::Solution	best_solution
	The best solution so far. More...

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 Member Functions
void	delete_empty_truck ()
	deletes phony vehicles that are empty More...

bool	diversify ()
	Diversify the search. More...

void	intensify ()
	Intensify the search. More...

bool	move_2_real ()
	moves orders from phony vehicles to a real vehicle More...

void	save_if_best ()
	save a new found solution only if it is best More...

void	set_tabu_list_length ()
	set tabu length More...

bool	single_pair_insertion (bool intensify, bool diversify)
	Single Pair Insertion: move order from one vehicle to another that reduces objective value. More...

void	sort_by_size (bool asc)

bool	swap_between_routes (bool intensify, bool diversify)
	Swapping pairs Between Routes: initiate directed or undirected swaps of orders between vehicles. More...

void	tabu_search ()
	Main optimization controller. More...

Private Attributes
size_t	m_max_cycles
	Maximum number of cycles on the optimization process. More...

bool	m_optimize
	Flag to just build a solution and not optimize it. More...

size_t	m_standard_limit = 30
	Limit for a cycle. More...

bool	m_stop_on_all_served
	Flag to stop when all orders are in real vehicles. More...

Identifiers< size_t >	m_unassignedOrders
	Set of unassigned orders. More...

TabuList	tabu_list
	Tabu lists of the problem. More...

Detailed Description

Class that optimizes a solution.

How to use:

// Given a solution in solution_to_optimize
// in this example it is one cycle and to stop when all orders are served
 
Solution optimized_solution = Optimize(solution_to_optimize, 1, true);

Definition at line 51 of file optimizers/tabu.h.

Constructor & Destructor Documentation

◆ Optimize()

vrprouting::optimizers::tabu::Optimize::Optimize	(	const problem::Solution &	old_solution,
		size_t	max_cycles,
		bool	stop_on_all_served,
		bool	optimize
	)

Optimization operation.

Parameters

[in]	old_solution	- solution to be optimized
[in]	max_cycles	- number of times to perform a single tabu search (optimization) cycle
[in]	stop_on_all_served	- a stopping condition: stop when all orders are served
[in]	optimize	- a stopping condition when false: only add orders; do not optimize

Postcondition: this solution's fleet has the best solution found

Definition at line 95 of file optimizers/tabu.cpp.

                        :
         problem::Solution(old_solution),
         best_solution(old_solution),
         m_max_cycles(max_cycles),
         m_stop_on_all_served(stop_on_all_served),
         m_optimize(optimize) {
     ENTERING(msg());
  
     /*
      * this function does the actual work
      */
     tabu_search();
  
     /*
      * delete empty phony trucks
      */
     delete_empty_truck();
  
     /*
      * Save best fleet/order structure found
      */
     this->m_fleet = best_solution.fleet();
  
     msg().log << tau("Best solution found");
     EXITING(msg());
 }

References best_solution, delete_empty_truck(), ENTERING, EXITING, vrprouting::problem::Solution::fleet(), vrprouting::Pgr_messages::log, vrprouting::problem::Solution::m_fleet, vrprouting::problem::Solution::msg(), tabu_search(), 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.

                      {
   TInterval total_duration(0);
   TInterval total_wait_time(0);
   TInterval total_tt(0);
   int total_twv(0);
   int total_cv(0);
   /*
    * Cycle the fleet
    */
   for (const auto& v : m_fleet) {
     total_duration += v.duration();
     total_wait_time += v.total_wait_time();
     total_twv += v.twvTot();
     total_cv += v.cvTot();
     total_tt += v.total_travel_time();
   }
   /*
    * build the tuple
    */
   return std::make_tuple(
       total_twv, total_cv, m_fleet.size(),
       total_wait_time, total_duration,
       total_tt);
 }

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.

                          {
   /*
    * get the cost
    */
   auto s_cost(cost());
   std::ostringstream log;
  
   /*
    * Build the string
    */
   log << std::fixed << std::setprecision(4)
     << "twv=" << std::get<0>(s_cost)
     << " cv=" << std::get<1>(s_cost)
     << " wait=" << std::get<3>(s_cost)
     << " duration=" << std::get<4>(s_cost)
     << " tt=" << std::get<5>(s_cost);
  
   return log.str();
 }

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.

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

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

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

◆ delete_empty_truck()

void vrprouting::optimizers::tabu::Optimize::delete_empty_truck ( )

private

deletes phony vehicles that are empty

Postcondition: the fleet does not have phony empty vehicles; does not remove real vehicles; the fleet size is reduced

Definition at line 788 of file optimizers/tabu.cpp.

                              {
     /*
      * remove from the fleet vehicles that are phony and empty
      */
     m_fleet.erase(std::remove_if(
             m_fleet.begin(),
             m_fleet.end(),
             [](const problem::Vehicle_pickDeliver &v){
                 return v.orders_in_vehicle().empty() && v.is_phony();}),
                   m_fleet.end());
 }

Referenced by Optimize(), and tabu_search().

◆ diversify()

bool vrprouting::optimizers::tabu::Optimize::diversify ( )

private

Diversify the search.

diversify

diversifies the search by moving into a solution space that has never been visited before
returns true if diversification was successful.

Definition at line 437 of file optimizers/tabu.cpp.

                     {
     /*
      * set the number of maximum swaps between routes for diversification
      */
     size_t max_swaps = std::min(m_fleet.size(), orders().size() / 10);
     size_t s = 0;
     bool swaps_were_done = true;
     while (swaps_were_done && s < max_swaps) {
         swaps_were_done = single_pair_insertion(false, true);
         if (!swaps_were_done) {
             swaps_were_done = swap_between_routes(false, true);
         }
         if (!swaps_were_done) {
             swaps_were_done = swap_between_routes(false, false);
         }
         if (swaps_were_done) if (!are_all_served(m_unassignedOrders)) move_2_real();
         s++;
     }
     return swaps_were_done;
 }

References anonymous_namespace{tabu.cpp}::are_all_served(), vrprouting::problem::Solution::m_fleet, m_unassignedOrders, move_2_real(), vrprouting::problem::Solution::orders(), single_pair_insertion(), and swap_between_routes().

Referenced by single_pair_insertion(), swap_between_routes(), and tabu_search().

◆ 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.

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

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

Referenced by vrprouting::problem::Solution::get_postgres_result(), vrprouting::optimizers::simple::Optimize::save_if_best(), and vrprouting::optimizers::simple::Optimize::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 intensify(), and Optimize().

◆ 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.

                                     {
   std::vector<Solution_rt> result;
  
   /* postgres numbering starts with 1 */
   int i(1);
  
   for (auto v : m_fleet) {
     v.evaluate(0);
     auto data = v.get_postgres_result(i);
     /*
      * Results adjusted for the depot and the first stop
      * So the vehicle waits on the depot not on the first stop
      */
     data[1].arrivalTime = data[1].operationTime;
     data[0].waitDuration = data[1].waitDuration;
     data[1].waitDuration = 0;
     data[0].departureTime = data[0].arrivalTime + data[0].waitDuration;
  
  
     result.insert(result.end(), data.begin(), data.end());
     ++i;
   }
  
   Solution_rt aggregates = {
     /*
      * Vehicle id = -2 indicates its an aggregate row
      *
      * (twv, cv, fleet, wait, duration)
      */
     -2,  // summary row on vehicle_number
     twvTot(),  // on vehicle_id
     cvTot(),   // on vehicle_seq
     -1,  // on order_id
     -1,  // on stop_id
     -2,  // on stop_type (gets increased later by one so it gets -1)
     -1,  // not accounting total loads
     static_cast<int64_t>(total_travel_time()),
     -1,  // not accounting arrival_travel_time
     static_cast<int64_t>(wait_time()),
     -1,  // not accounting operation time
     static_cast<int64_t>(total_service_time()),
     static_cast<int64_t>(duration()),
     cvTot(),
     twvTot()
   };
   result.push_back(aggregates);
  
   return result;
 }

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.

                           {
   std::vector<Short_vehicle> result;
   for (auto v : m_fleet) {
     result.push_back(Short_vehicle{v.id(), v.get_stops()});
   }
   return result;
 }

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

◆ intensify()

void vrprouting::optimizers::tabu::Optimize::intensify ( )

private

Intensify the search.

intensify

Intensifies the search by returning to the current best solution and only focusing on moves that improve the current best solution.

Definition at line 408 of file optimizers/tabu.cpp.

                     {
     m_fleet = best_solution.fleet();
  
     bool do_spi = true;
     bool do_sbr = true;
  
     int max_iter = 20;
     int i = 0;
     while (do_spi && i < max_iter) {
         do_spi = single_pair_insertion(true, false);
         if (do_spi) if (!are_all_served(m_unassignedOrders)) move_2_real();
         i++;
     }
     i = 0;
     while (do_sbr && i < max_iter) {
         do_sbr = swap_between_routes(true, false);
         if (do_spi) if (!are_all_served(m_unassignedOrders)) move_2_real();
         i++;
     }
 }

References anonymous_namespace{tabu.cpp}::are_all_served(), best_solution, vrprouting::problem::Solution::fleet(), vrprouting::problem::Solution::m_fleet, m_unassignedOrders, move_2_real(), single_pair_insertion(), and swap_between_routes().

Referenced by single_pair_insertion(), swap_between_routes(), and tabu_search().

◆ 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.

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

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

Referenced by vrprouting::optimizers::simple::Optimize::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_2_real()

bool vrprouting::optimizers::tabu::Optimize::move_2_real ( )

private

moves orders from phony vehicles to a real vehicle

move_2_real

moving orders from a phony vehicle to a real vehicle
vehicles can be unordered
returns true if unassigned orders were assigned to a (real) vehicle

Definition at line 134 of file optimizers/tabu.cpp.

                       {
     ENTERING(msg());
     /*
      * nothing to do:
      * - No orders pending on phony vehicle
      */
     if (are_all_served(m_unassignedOrders)) return false;
     pgassert(!are_all_served(m_unassignedOrders));
  
     bool moves_were_done(false);
  
     /*
      * cycling to find phony vehicles
      */
     for (auto &phony_vehicle : m_fleet) {
         /*
          * skip
          * - real vehicle
          * - empty vehicle
          */
         if (phony_vehicle.is_real() || phony_vehicle.empty()) continue;
         pgassert(phony_vehicle.is_phony() && !phony_vehicle.empty());
  
  
         auto orders_in_phony_vehicle = phony_vehicle.orders_in_vehicle();
         for (const auto o_id : orders_in_phony_vehicle) {
             /*
              * get the order to be inserted on a real vehicle
              */
             double best_score = 0;
             auto order = orders()[o_id];
  
             auto best_vehicle_ref = &phony_vehicle;
  
             for (auto &real_vehicle : m_fleet) {
                 /*
                  * skip when:
                  *  - destination vehicle is the current vehicle
                  *  - destination vehicle is phony
                  *  - When current order is not feasible on real vehicle
                  */
                 if (&phony_vehicle == &real_vehicle) continue;
                 if (real_vehicle.is_phony()) continue;
                 if (!real_vehicle.feasible_orders().has(o_id)) continue;
                 if (real_vehicle.has_order(order)) continue;
  
                 pgassert(&phony_vehicle != &real_vehicle);
                 pgassert(real_vehicle.is_real());
  
                 /*
                  * setup local working vehicles
                  */
                 auto real_vehicle_copy = real_vehicle;
  
                 /* current travel_time */
                 auto curr_travel_time = phony_vehicle.total_travel_time() + real_vehicle_copy.total_travel_time();
  
                 /*
                  * insert order on destination vehicle
                  */
                 pgassert(!real_vehicle_copy.has_order(order));
                 real_vehicle_copy.hillClimb(order);
  
                 // either the to vehicle has the and is feasible OR it does not have the order
                 pgassert((real_vehicle_copy.has_order(order) && real_vehicle_copy.is_feasible())
                         || !real_vehicle_copy.has_order(order));
  
                 /*
                  * Skip to next order if the order wasnt inserted
                  */
                 if (!real_vehicle_copy.has_order(order)) continue;
                 pgassert(real_vehicle_copy.has_order(order));
  
                 auto new_travel_time = phony_vehicle.total_travel_time() + real_vehicle_copy.total_travel_time();
                 auto delta_travel_time = new_travel_time - curr_travel_time;
  
                 auto delta_objective = delta_travel_time;
                 auto estimated_objective = objective() + static_cast<double>(delta_objective);
  
  
                 if (best_score == 0 || estimated_objective < best_score) {
                     best_score = estimated_objective;
                     best_vehicle_ref = &real_vehicle;
                 }
             }   // to_v
  
             if (best_score != 0) {
                 pgassert(best_vehicle_ref != &phony_vehicle);
                 phony_vehicle.erase(order);
                 best_vehicle_ref->hillClimb(order);
                 m_unassignedOrders -= order.idx();
                 best_solution = (*this);
                 moves_were_done = true;
             }
         }  // orders
     }  // from phony
     EXITING(msg());
     if (moves_were_done) tabu_list.clear();
     return moves_were_done;
 }

References anonymous_namespace{tabu.cpp}::are_all_served(), best_solution, vrprouting::optimizers::tabu::TabuList::clear(), ENTERING, EXITING, vrprouting::problem::Solution::m_fleet, m_unassignedOrders, vrprouting::problem::Solution::msg(), vrprouting::problem::Solution::objective(), vrprouting::problem::Solution::orders(), pgassert, and tabu_list.

Referenced by diversify(), intensify(), and tabu_search().

◆ 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(), vrprouting::optimizers::simple::Optimize::inter_swap(), move_2_real(), vrprouting::initialsol::simple::Initial_solution::one_truck_all_orders(), vrprouting::optimizers::simple::Optimize::Optimize(), Optimize(), vrprouting::initialsol::tabu::Initial_solution::process_unassigned(), vrprouting::optimizers::simple::Optimize::save_if_best(), and 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 move_2_real(), single_pair_insertion(), swap_between_routes(), and tabu_search().

◆ operator<()

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

inherited

Definition at line 267 of file solution.cpp.

                                                {
   auto lhs(cost());
   auto rhs(s_rhs.cost());
  
   /*
    * time window violations
    */
   if (std::get<0>(lhs) < std::get<0>(rhs))
     return true;
   if (std::get<0>(lhs) > std::get<0>(rhs))
     return false;
  
   /*
    * capacity violations
    */
   if (std::get<1>(lhs) < std::get<1>(rhs))
     return true;
   if (std::get<1>(lhs) > std::get<1>(rhs))
     return false;
  
   /*
    * fleet size
    */
   if (std::get<2>(lhs) < std::get<2>(rhs))
     return true;
   if (std::get<2>(lhs) > std::get<2>(rhs))
     return false;
  
   /*
    * waiting time
    */
   if (std::get<3>(lhs) < std::get<3>(rhs))
     return true;
   if (std::get<3>(lhs) > std::get<3>(rhs))
     return false;
  
   /*
    * duration
    */
   if (std::get<4>(lhs) < std::get<4>(rhs))
     return true;
   if (std::get<4>(lhs) > std::get<4>(rhs))
     return false;
  
   return false;
 }

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 vrprouting::optimizers::simple::Optimize::decrease_truck(), diversify(), move_2_real(), vrprouting::initialsol::tabu::Initial_solution::process_given_solution_from_user(), vrprouting::initialsol::tabu::Initial_solution::process_unassigned(), set_tabu_list_length(), single_pair_insertion(), and swap_between_routes().

◆ save_if_best()

void vrprouting::optimizers::tabu::Optimize::save_if_best ( )

private

save a new found solution only if it is best

Save as best solution when objective function value is smaller.

Definition at line 805 of file optimizers/tabu.cpp.

                        {
     if (objective() < best_solution.objective()) {
         best_solution = (*this);
         msg().log << "\t***  best objective " << best_solution.cost_str();
     }
 }

Referenced by single_pair_insertion(), and swap_between_routes().

◆ set_tabu_list_length()

void vrprouting::optimizers::tabu::Optimize::set_tabu_list_length ( )

private

set tabu length

set_tabu_list_length

Sets the tabu list max length

Definition at line 241 of file optimizers/tabu.cpp.

                                {
     auto max_length = std::max(orders().size(), m_standard_limit);
     tabu_list.set_max_length(max_length);
 }

References m_standard_limit, vrprouting::problem::Solution::orders(), vrprouting::optimizers::tabu::TabuList::set_max_length(), and tabu_list.

Referenced by tabu_search().

◆ single_pair_insertion()

bool vrprouting::optimizers::tabu::Optimize::single_pair_insertion	(	bool	intensify,
		bool	diversify
	)

private

Single Pair Insertion: move order from one vehicle to another that reduces objective value.

Single Pair Insertion.

Returns: false when a single pair insertion was not successful; true when a single pair insertion was successful

Parameters

[in]	intensify	to declare an intensification phase single pair insertion
[in]	diversify	to declare an diversification phase single pair insertion

Definition at line 468 of file optimizers/tabu.cpp.

                                                               {
     sort_by_size(true);
     auto best_to_v = &m_fleet[0];
     auto best_from_v = &m_fleet[0];
     double best_score = intensify ? objective() : 0;
     double best_to_score;
     double best_from_score;
     bool moved = false;
     auto best_order = orders()[0];
     bool has_phony = false;
  
     std::string best_candidate;
  
     for (auto &from_vehicle : m_fleet) {
         if (from_vehicle.is_phony() || from_vehicle.empty()) continue;
  
         auto first_order_set = from_vehicle.orders_in_vehicle();
         for (const auto o_id : first_order_set) {
             auto order = orders()[o_id];
             for (auto &to_v : m_fleet) {
                 if (&from_vehicle == &to_v) continue;
                 if (to_v.is_phony()) {
                     has_phony = true;
                 }
                 if (to_v.is_phony()) continue;
                 if (!has_phony && to_v.empty()) continue;
  
                 if (!to_v.feasible_orders().has(o_id)) continue;
  
                 std::ostringstream ss;
  
                 ss << to_v.path_str() << ":" << o_id;
  
                 std::string candidate = ss.str();
  
                 if (tabu_list.has_infeasible(candidate)) continue;
  
                 if (diversify && tabu_list.has_seen(candidate)) continue;
  
                 /*
                  * setup local working vehicles
                  */
                 auto to_v_copy = to_v;
                 auto from_v_copy = from_vehicle;
  
                 /* current travel_time */
                 auto curr_travel_time = from_v_copy.total_travel_time() + to_v_copy.total_travel_time();
  
                 /*
                  * insert order on destination vehicle
                  */
                 pgassert(!to_v_copy.has_order(order));
                 to_v_copy.hillClimb(order);
  
                 // either the to vehicle has the order and is feasible OR it does not have the order
                 pgassert((to_v_copy.has_order(order) && to_v_copy.is_feasible()) || !to_v_copy.has_order(order));
  
                 /*
                  * Skip to next order if the order wasn't inserted
                  */
                 if (!to_v_copy.has_order(order)) {
                     tabu_list.add_infeasible(candidate);
                     continue;
                 }
  
                 from_v_copy.erase(order);
                 if (from_v_copy.has_order(order) || !from_v_copy.is_feasible()) continue;
  
                 auto new_travel_time = from_v_copy.total_travel_time() + to_v_copy.total_travel_time();
                 auto delta_travel_time = new_travel_time - curr_travel_time;
  
                 auto delta_objective = delta_travel_time;
                 auto estimated_objective = objective() + static_cast<double>(delta_objective);
  
                 /*
                  * evaluate the move
                  */
                 if (estimated_objective >= best_score && !from_v_copy.empty() && best_score != 0) continue;
  
                 if (tabu_list.has_move(
                             from_v_copy, to_v_copy, order, to_v_copy.objective(),
                             from_v_copy.objective())
                         && estimated_objective >= best_solution.objective()
                         && !from_v_copy.empty()) continue;
  
                 if (estimated_objective < best_score || from_v_copy.empty() || best_score == 0) {
                     moved = true;
                     best_score = estimated_objective;
                     best_to_score = to_v.objective();
                     best_from_score = from_vehicle.objective();
                     best_to_v = &to_v;
                     best_from_v = &from_vehicle;
                     best_order = order;
                     best_candidate = candidate;
                 }
             }  // to vehicles
         }  // orders
     }  // from vehicles
  
     if (moved) {
         tabu_list.add(Move((*best_from_v), (*best_to_v), best_order, best_to_score, best_from_score));
         best_to_v->hillClimb(best_order);
         best_from_v->erase(best_order);
         tabu_list.add_seen(best_candidate);
         if (best_from_v->is_phony()) m_unassignedOrders -= best_order.idx();
         save_if_best();
     }
     return moved;
 }

References vrprouting::optimizers::tabu::TabuList::add(), vrprouting::optimizers::tabu::TabuList::add_infeasible(), vrprouting::optimizers::tabu::TabuList::add_seen(), best_solution, diversify(), vrprouting::optimizers::tabu::TabuList::has_infeasible(), vrprouting::optimizers::tabu::TabuList::has_move(), vrprouting::optimizers::tabu::TabuList::has_seen(), intensify(), vrprouting::problem::Solution::m_fleet, m_unassignedOrders, vrprouting::problem::Solution::objective(), vrprouting::problem::Solution::orders(), pgassert, save_if_best(), sort_by_size(), and tabu_list.

Referenced by diversify(), intensify(), and tabu_search().

◆ sort_by_size()

void vrprouting::optimizers::tabu::Optimize::sort_by_size ( bool asc )

private

Postcondition: pv1.size <= pv2.size ... <= pvN.size v1.size <= v2.size ... <= vN.size

Definition at line 742 of file optimizers/tabu.cpp.

                                {
     /*
      * sort by number of orders on the vehicles
      */
     if (asc) {
         std::sort(m_fleet.begin(), m_fleet.end(), []
                 (const problem::Vehicle_pickDeliver &lhs, const problem::Vehicle_pickDeliver &rhs)
                 -> bool {
             if (lhs.orders_in_vehicle().size() == rhs.orders_in_vehicle().size()) {
                 return lhs.id() < rhs.id();
             } else {
                 return lhs.orders_in_vehicle().size() < rhs.orders_in_vehicle().size();
             }
         });
     } else {
         std::sort(m_fleet.begin(), m_fleet.end(), []
                 (const problem::Vehicle_pickDeliver &lhs, const problem::Vehicle_pickDeliver &rhs)
                 -> bool {
             if (lhs.orders_in_vehicle().size() == rhs.orders_in_vehicle().size()) {
                 return lhs.id() > rhs.id();
             } else {
                 return lhs.orders_in_vehicle().size() > rhs.orders_in_vehicle().size();
             }
         });
     }
  
  
     /*
      * Leave the phony vehicles at the beginning
      */
     std::stable_partition(m_fleet.begin(), m_fleet.end(), []
             (const problem::Vehicle_pickDeliver &v)
             -> bool {
             return v.id() < 0;
             });
 }

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

Referenced by single_pair_insertion(), swap_between_routes(), and tabu_search().

◆ swap_between_routes()

bool vrprouting::optimizers::tabu::Optimize::swap_between_routes	(	bool	intensify,
		bool	diversify
	)

private

Swapping pairs Between Routes: initiate directed or undirected swaps of orders between vehicles.

Swap Between Routes.

Returns: false when a swap between routes was not successful; true when a swap between routes was successful

Parameters

[in]	intensify	to declare an intensification phase swap between routes
[in]	diversify	to declare an diversification phase swap between routes

Definition at line 587 of file optimizers/tabu.cpp.

                                                             {
     sort_by_size(false);
     auto best_to_v = &m_fleet[0];
     auto best_from_v = &m_fleet[0];
     double best_score = intensify ? objective() : 0;
     double best_to_score;
     double best_from_score;
     bool swapped = false;
     auto best_from_order = orders()[0];
     auto best_to_order = orders()[0];
  
     std::string best_candidate1;
     std::string best_candidate2;
  
     for (size_t i = 0; i < m_fleet.size(); ++i)  {
         problem::Vehicle_pickDeliver &from_vehicle = m_fleet[i];
         if (from_vehicle.is_phony() || from_vehicle.empty()) continue;
  
         auto first_order_set = from_vehicle.orders_in_vehicle();
         for (const auto o_id1 : first_order_set) {
             auto order1 = orders()[o_id1];
             for (size_t j = i + 1; j < m_fleet.size(); ++j) {
                 problem::Vehicle_pickDeliver &to_v = m_fleet[j];
                 if (&from_vehicle == &to_v) continue;
                 if (to_v.is_phony() || to_v.empty()) continue;
                 if (!to_v.feasible_orders().has(o_id1)) continue;
  
  
                 /*
                  * cycle through to orders for swap
                  */
                 auto second_order_set = to_v.orders_in_vehicle();
                 for (const auto o_id2 : second_order_set) {
                     auto order2 = orders()[o_id2];
                     if (!from_vehicle.feasible_orders().has(o_id2)) continue;
  
                     auto curr_from_objective = from_vehicle.objective();
                     auto curr_to_objective = to_v.objective();
  
                     /*
                      * setup local working vehicles
                      */
                     auto from_v_copy = from_vehicle;
                     auto to_v_copy = to_v;
  
  
                     pgassert(from_v_copy.has_order(order1));
                     pgassert(to_v_copy.has_order(order2));
  
  
                     /*
                      * do one truck at a time
                      */
                     to_v_copy.erase(order2);
                     if (to_v_copy.orders_in_vehicle().has(o_id2) || !to_v_copy.is_feasible()) continue;
  
                     std::ostringstream ss1;
                     ss1 << to_v_copy.path_str() << ":" << o_id1;
  
                     std::string candidate1 = ss1.str();
  
                     if (tabu_list.has_infeasible(candidate1)) continue;
  
                     from_v_copy.erase(order1);
                     if (from_v_copy.orders_in_vehicle().has(o_id1) || !from_v_copy.is_feasible()) continue;
  
                     std::ostringstream ss2;
                     ss2 << from_v_copy.path_str() << ":" << o_id2;
  
                     std::string candidate2 = ss2.str();
  
                     if (diversify && tabu_list.has_seen(candidate1) && tabu_list.has_seen(candidate2)) continue;
  
                     if (tabu_list.has_infeasible(candidate2)) continue;
  
                     to_v_copy.hillClimb(order1);
                     if (!to_v_copy.has_order(order1) || !to_v_copy.is_feasible()) {
                         tabu_list.add_infeasible(candidate1);
                         continue;
                     }
  
  
                     from_v_copy.hillClimb(order2);
                     if (!from_v_copy.has_order(order2) || !from_v_copy.is_feasible()) {
                         tabu_list.add_infeasible(candidate2);
                         continue;
                     }
  
  
                     /*
                      * Evaluate the swap
                      */
                     auto new_from_objective = from_v_copy.objective();
                     auto new_to_objective = to_v_copy.objective();
  
                     auto estimated_delta =
                             +(new_to_objective + new_from_objective)
                             - (curr_from_objective + curr_to_objective);
  
                     auto estimated_objective = objective() + estimated_delta;
                     /*
                      * dont swap if there is no improvement in either vehicle
                      */
                     if (estimated_objective >= best_score && best_score != 0) continue;
  
                     if (tabu_list.has_swap(
                                 from_v_copy, to_v_copy, order1, order2, from_v_copy.objective(),
                                 to_v_copy.objective())
                         && estimated_objective >= best_solution.objective()) continue;
  
  
                     if (estimated_objective < best_score || best_score == 0) {
                         swapped = true;
                         best_from_score = from_vehicle.objective();
                         best_to_score = to_v.objective();
                         best_score = estimated_objective;
                         best_to_v = &to_v;
                         best_from_v = &from_vehicle;
                         best_from_order = order1;
                         best_to_order = order2;
                         best_candidate1 = candidate1;
                         best_candidate2 = candidate2;
                     }
                 }
             }  // to vehicles
         }  // orders
     }  // from vehicles
     if (swapped) {
         tabu_list.add(
                 Move((*best_from_v), (*best_to_v), best_from_order, best_to_order, best_to_score, best_from_score));
         best_from_v->erase(best_from_order);
         best_to_v->erase(best_to_order);
         best_from_v->hillClimb(best_to_order);
         best_to_v->hillClimb(best_from_order);
         tabu_list.add_seen(best_candidate1);
         tabu_list.add_seen(best_candidate2);
         if (best_from_v->is_phony()) {
             m_unassignedOrders -= best_from_order.idx();
             m_unassignedOrders += best_to_order.idx();
         }
         if (best_to_v->is_phony()) {
             m_unassignedOrders -= best_to_order.idx();
             m_unassignedOrders += best_from_order.idx();
         }
         save_if_best();
     }
     return swapped;
 }

References vrprouting::optimizers::tabu::TabuList::add(), vrprouting::optimizers::tabu::TabuList::add_infeasible(), vrprouting::optimizers::tabu::TabuList::add_seen(), best_solution, diversify(), vrprouting::problem::Vehicle_pickDeliver::empty(), vrprouting::problem::Vehicle_pickDeliver::feasible_orders(), Identifiers< T >::has(), vrprouting::optimizers::tabu::TabuList::has_infeasible(), vrprouting::optimizers::tabu::TabuList::has_seen(), vrprouting::optimizers::tabu::TabuList::has_swap(), intensify(), vrprouting::problem::Vehicle::is_phony(), vrprouting::problem::Solution::m_fleet, m_unassignedOrders, vrprouting::problem::Solution::objective(), vrprouting::problem::Vehicle_pickDeliver::objective(), vrprouting::problem::Solution::orders(), vrprouting::problem::Vehicle_pickDeliver::orders_in_vehicle(), pgassert, save_if_best(), sort_by_size(), and tabu_list.

Referenced by diversify(), intensify(), and tabu_search().

◆ tabu_search()

void vrprouting::optimizers::tabu::Optimize::tabu_search ( )

private

Main optimization controller.

tabu_search will find the best solution.

The best solution is one that either:

adds an order
meets the evaluation criteria. It searches until either (terminating conditions):

all cycles are complete
all possible orders are served without optimization and optimize is set to false
all orders are served and stop_on_all_served is set to true The stopping condition stop_on_all_served exists in order to give a fast response to the user. Note:

Phony vehicles (if exist) have orders that have not been served

The vehicle sort results on: [pv1, pv2, pv3, ... pvK, rv1 rv2 ... rvN] Phony vehicles (if exist) have orders that have not been served where:

[pv1, pv2, ... pvK] are phony vehicles
[rv1 ... rvN] are real vehicles And within the real vehicles for i < j : rv(i).size < rv(j).size

Loop through cycles of tabu search Exit the loop when:

all orders are served if stop_on_all_served
maximum number of cycles is reached

Definition at line 274 of file optimizers/tabu.cpp.

                       {
     ENTERING(msg());
  
     sort_by_size(true);
  
     m_unassignedOrders = set_unassignedOrders(m_fleet);
  
     move_2_real();
     delete_empty_truck();
     /*
      * stop if no optimization is asked
      */
     if (!m_optimize) return;
  
     /*
      * stop if all orders are served
      */
     if (m_stop_on_all_served && are_all_served(m_unassignedOrders)) return;
  
     set_tabu_list_length();
     /*
      * Do the cycles
      */
     /*
      * initialize the iterator counter
      */
     size_t iter = 0;
  
     int no_moves = 0;
  
     int max_no_moves = 2;
  
     int max_no_swaps = 2;
  
     bool diversification = true;
  
     bool intensification = false;
  
     bool do_spi = true;
  
     int could_not_spi = 0;
  
     int stuck_counter = 0;
  
     int wander_counter = 0;
  
     int max_no_improvement = 1000;
  
     std::string neighborhood;
  
     int wander_length = 100;
  
     while (iter < m_max_cycles) {
         double curr_best = best_solution.objective();
  
         if (stuck_counter == max_no_improvement) {
             intensify();
             if (best_solution.objective() == curr_best)
                 break;
         }
  
         if (no_moves < max_no_moves && do_spi) {
             neighborhood = "spi";
         } else {
             neighborhood = "sbr";
         }
  
         bool moved;
  
         if (neighborhood == "spi") {
             moved = single_pair_insertion(false, false);
             delete_empty_truck();
             if (moved) {
                 if (!are_all_served(m_unassignedOrders)) move_2_real();
             }
         } else {
             moved = swap_between_routes(false, false);
             if (moved) {
                 if (!are_all_served(m_unassignedOrders)) move_2_real();
             }
         }
  
         if (m_stop_on_all_served && are_all_served(m_unassignedOrders)) break;
  
         if (!moved) {
             no_moves += 1;
             if (neighborhood == "spi") {
                 could_not_spi += 1;
             }
             if (neighborhood == "sbr") {
                 intensify();
             }
         } else {
             no_moves = 0;
         }
  
         if (no_moves >= max_no_swaps + max_no_moves) break;
  
         if (m_stop_on_all_served && are_all_served(m_unassignedOrders)) break;
  
         /*
          * check for aimless wandering ...
          */
         if (curr_best == best_solution.objective()) {
             stuck_counter += 1;
             wander_counter += 1;
             if (stuck_counter % wander_length == 0) {
                 intensification = !intensification;
                 diversification = !diversification;
  
                 if (intensification) {
                     intensify();
                 }
                 if (diversification) {
                     diversify();
                 }
             }
         } else {
             // if it is not the same then it must be better!
             stuck_counter = 0;
         }
         iter++;
     }
     EXITING(msg());
 }

References anonymous_namespace{tabu.cpp}::are_all_served(), best_solution, delete_empty_truck(), diversify(), ENTERING, EXITING, intensify(), vrprouting::problem::Solution::m_fleet, m_max_cycles, m_optimize, m_stop_on_all_served, m_unassignedOrders, move_2_real(), vrprouting::problem::Solution::msg(), vrprouting::problem::Solution::objective(), set_tabu_list_length(), anonymous_namespace{tabu.cpp}::set_unassignedOrders(), single_pair_insertion(), sort_by_size(), and swap_between_routes().

Referenced by Optimize().

◆ tau()

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

inherited

writing the solution in compact form into a string

Parameters

[in] title Title to Use for the tau

Returns: The solution in one compacted string

Definition at line 116 of file solution.cpp.

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

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

Referenced by vrprouting::optimizers::simple::Optimize::inter_swap(), vrprouting::optimizers::simple::Optimize::Optimize(), and 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.

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

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.

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

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.

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

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.

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

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

problem::Solution vrprouting::optimizers::tabu::Optimize::best_solution

The best solution so far.

Definition at line 57 of file optimizers/tabu.h.

Referenced by intensify(), move_2_real(), Optimize(), single_pair_insertion(), swap_between_routes(), and tabu_search().

◆ m_fleet

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

protectedinherited

The current solution.

Definition at line 125 of file solution.h.

◆ m_max_cycles

size_t vrprouting::optimizers::tabu::Optimize::m_max_cycles

private

Maximum number of cycles on the optimization process.

Definition at line 87 of file optimizers/tabu.h.

Referenced by tabu_search().

◆ 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_optimize

bool vrprouting::optimizers::tabu::Optimize::m_optimize

private

Flag to just build a solution and not optimize it.

Definition at line 93 of file optimizers/tabu.h.

Referenced by tabu_search().

◆ 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_standard_limit

size_t vrprouting::optimizers::tabu::Optimize::m_standard_limit = 30

private

Limit for a cycle.

Definition at line 96 of file optimizers/tabu.h.

Referenced by set_tabu_list_length().

◆ m_stop_on_all_served

bool vrprouting::optimizers::tabu::Optimize::m_stop_on_all_served

private

Flag to stop when all orders are in real vehicles.

Definition at line 90 of file optimizers/tabu.h.

Referenced by tabu_search().

◆ m_trucks

Fleet vrprouting::problem::Solution::m_trucks

protectedinherited

Definition at line 129 of file solution.h.

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

◆ m_unassignedOrders

Identifiers<size_t> vrprouting::optimizers::tabu::Optimize::m_unassignedOrders

private

Set of unassigned orders.

Definition at line 105 of file optimizers/tabu.h.

Referenced by diversify(), intensify(), move_2_real(), single_pair_insertion(), swap_between_routes(), and tabu_search().

◆ tabu_list

TabuList vrprouting::optimizers::tabu::Optimize::tabu_list

private

Tabu lists of the problem.

Definition at line 61 of file optimizers/tabu.h.

Referenced by move_2_real(), set_tabu_list_length(), single_pair_insertion(), and swap_between_routes().

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

Public Member Functions

Public Attributes

Protected Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Optimize()

Member Function Documentation

◆ cost()

◆ cost_str()

◆ cvTot()

◆ delete_empty_truck()

◆ diversify()

◆ duration()

◆ fleet()

◆ get_postgres_result()

◆ get_stops()

◆ intensify()

◆ is_feasible()

◆ move_2_real()

◆ msg()

◆ objective()

◆ operator<()

◆ orders()

◆ save_if_best()

◆ set_tabu_list_length()

◆ single_pair_insertion()

◆ sort_by_size()

◆ swap_between_routes()

◆ tabu_search()

◆ tau()

◆ total_service_time()

◆ total_travel_time()

◆ twvTot()

◆ vehicles()

◆ wait_time()

Member Data Documentation

◆ best_solution

◆ m_fleet

◆ m_max_cycles

◆ m_msg

◆ m_optimize

◆ m_orders

◆ m_standard_limit

◆ m_stop_on_all_served

◆ m_trucks

◆ m_unassignedOrders

◆ tabu_list