optimize_driver.cpp File Reference

#include "drivers/optimize_driver.h"
#include <cstring>
#include <sstream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include "problem/pickDeliver.h"
#include "c_types/pickDeliveryOrders_t.h"
#include "c_types/short_vehicle_rt.h"
#include "c_types/vehicle_t.h"
#include "problem/matrix.h"
#include "cpp_common/pgr_assert.h"
#include "cpp_common/pgr_messages.h"
#include "initialsol/tabu.h"
#include "optimizers/tabu.h"
#include "c_common/pgr_alloc.hpp"
#include "cpp_common/interruption.h"

Include dependency graph for optimize_driver.cpp:

Go to the source code of this file.

Namespaces
	anonymous_namespace{optimize_driver.cpp}

Functions
void	do_optimize (PickDeliveryOrders_t *shipments_arr, size_t total_shipments, Vehicle_t *vehicles_arr, size_t total_vehicles, Matrix_cell_t *matrix_cells_arr, size_t total_cells, Time_multipliers_t *multipliers_arr, size_t total_multipliers, double factor, int max_cycles, int64_t execution_date, bool check_triangle_inequality, bool subdivide, bool subdivide_by_vehicle, Short_vehicle_rt **return_tuples, size_t *return_count, char **log_msg, char **notice_msg, char **err_msg)
std::vector< Short_vehicle >	anonymous_namespace{optimize_driver.cpp}::get_initial_stops (Vehicle_t *vehicles_arr, size_t total_vehicles)
	get the original stops More...
std::vector< Short_vehicle >	anonymous_namespace{optimize_driver.cpp}::one_processing (PickDeliveryOrders_t *shipments_arr, size_t total_shipments, Vehicle_t *vehicles_arr, size_t total_vehicles, std::vector< Short_vehicle > new_stops, const vrprouting::problem::Matrix &time_matrix, int max_cycles, int64_t execution_date)
	Executes an optimization with the input data. More...
Identifiers< TTimestamp >	anonymous_namespace{optimize_driver.cpp}::processing_times_by_shipment (PickDeliveryOrders_t *shipments_arr, size_t total_shipments)
	: extract the times where the shipments opens or closes More...
Identifiers< TTimestamp >	anonymous_namespace{optimize_driver.cpp}::processing_times_by_vehicle (Vehicle_t *vehicles_arr, size_t total_vehicles)
	: extract the times where the vehicle opens or closes More...
std::vector< Short_vehicle >	anonymous_namespace{optimize_driver.cpp}::subdivide_processing (PickDeliveryOrders_t *shipments_arr, size_t total_shipments, Vehicle_t *vehicles_arr, size_t total_vehicles, const vrprouting::problem::Matrix &time_matrix, int max_cycles, int64_t execution_date, bool subdivide_by_vehicle, std::ostringstream &log)
	Executes an optimization by subdivision of data. More...
void	anonymous_namespace{optimize_driver.cpp}::update_stops (std::vector< Short_vehicle > &the_stops, const std::vector< Short_vehicle > new_values)
	Update the vehicle stops to the new values. More...

Function Documentation

do_optimize()

void do_optimize	(	PickDeliveryOrders_t *	shipments_arr,
		size_t	total_shipments,
		Vehicle_t *	vehicles_arr,
		size_t	total_vehicles,
		Matrix_cell_t *	matrix_cells_arr,
		size_t	total_cells,
		Time_multipliers_t *	multipliers_arr,
		size_t	total_multipliers,
		double	factor,
		int	max_cycles,
		int64_t	execution_date,
		bool	check_triangle_inequality,
		bool	subdivide,
		bool	subdivide_by_vehicle,
		Short_vehicle_rt **	return_tuples,
		size_t *	return_count,
		char **	log_msg,
		char **	notice_msg,
		char **	err_msg
	)

Parameters

[in]	shipments_arr	A C Array of pickup and dropoff shipments
[in]	total_shipments	size of the shipments_arr
[in]	vehicles_arr	A C Array of vehicles
[in]	total_vehicles	size of the vehicles_arr
[in]	matrix_cells_arr	A C Array of the (time) matrix cells
[in]	total_cells	size of the matrix_cells_arr
[in]	multipliers_arr	A C Array of the multipliers
[in]	total_multipliers	size of the multipliers_arr
[in]	optimize	flag to control optimization
[in]	factor	A global multiplier for the (time) matrix cells
[in]	max_cycles	number of cycles to perform during the optimization phase
[in]	stop_on_all_served	Indicator to stop optimization when all shipments are served
[in]	execution_date	Value used for not moving shipments that are before this date
[out]	return_tuples	C array of contents to be returned to postgres
[out]	return_count	number of tuples returned
[out]	log_msg	special log message pointer
[out]	notice_msg	special message pointer to be returned as NOTICE
[out]	err_msg	special message pointer to be returned as ERROR

Returns

void

Precondition

The messages: log_msg, notice_msg, err_msg must be empty (=nullptr)

The C arrays: shipments_arr, vehicles_arr, matrix_cells_arr must not be empty

The C array: return_tuples must be empty

Only matrix cells (i, i) can be missing and are considered as 0 (time units)

Postcondition

The C arrays: shipments_arr, vehicles_arr, matrix_cells_arr Do not change

The C array: return_tuples contains the result for the problem given

The return_tuples array size is return_count

err_msg is empty if no throw from the process is catched

log_msg contains some logging

notice_msg is empty

Definition at line 350 of file optimize_driver.cpp.

                    {
  std::ostringstream log;
  std::ostringstream notice;
  std::ostringstream err;
  try {
    /*
     * verify preconditions
     */
    pgassert(!(*log_msg));
    pgassert(!(*notice_msg));
    pgassert(!(*err_msg));
    pgassert(total_shipments);
    pgassert(total_vehicles);
    pgassert(total_cells);
    pgassert(*return_count == 0);
    pgassert(!(*return_tuples));
 
    *return_tuples = nullptr;
    *return_count = 0;
 
    Identifiers<Id> node_ids;
    Identifiers<Id> shipments_in_stops;
 
    /*
     * Remove vehicles not going to be optimized and sort remaining vehicles
     * 1. sort by id
     * 2. remove duplicates
     *   - data comes from query that could possibly give a duplicate
     * 3. remove vehicles that closes(end) before the execution time
     */
    std::sort(vehicles_arr, vehicles_arr + total_vehicles,
        [](const Vehicle_t& lhs, const Vehicle_t& rhs){return lhs.id < rhs.id;});
 
    total_vehicles = static_cast<size_t>(std::distance(vehicles_arr,
      std::unique(vehicles_arr, vehicles_arr + total_vehicles,
          [&](const Vehicle_t& lhs, const Vehicle_t& rhs){return lhs.id == rhs.id;})));
 
    total_vehicles = static_cast<size_t>(std::distance(vehicles_arr,
      std::remove_if(vehicles_arr, vehicles_arr + total_vehicles,
          [&](const Vehicle_t& v){return v.end_close_t < execution_date;})));
 
    /*
     * Remove shipments not involved in optimization
     * 1. get the shipments on the stops of the vehicles
     *   - getting the node_ids in the same cycle
     * 2. Remove duplicates
     * 2. Remove shipments not on the stops
     */
    for (size_t i = 0; i < total_vehicles; ++i) {
      node_ids += vehicles_arr[i].start_node_id;
      node_ids += vehicles_arr[i].end_node_id;
      for (size_t j = 0; j < vehicles_arr[i].stops_size; ++j) {
        shipments_in_stops += vehicles_arr[i].stops[j];
      }
    }
 
    std::sort(shipments_arr, shipments_arr + total_shipments,
        [](const PickDeliveryOrders_t& lhs, const PickDeliveryOrders_t& rhs){return lhs.id < rhs.id;});
 
    total_shipments = static_cast<size_t>(std::distance(shipments_arr,
      std::unique(shipments_arr, shipments_arr + total_shipments,
          [&](const PickDeliveryOrders_t& lhs, const PickDeliveryOrders_t& rhs){return lhs.id == rhs.id;})));
 
    total_shipments = static_cast<size_t>(std::distance(shipments_arr,
        std::remove_if(shipments_arr, shipments_arr + total_shipments,
        [&](const PickDeliveryOrders_t& s){return !shipments_in_stops.has(s.id);})));
 
    /*
     * Verify shipments complete data
     */
    if (shipments_in_stops.size() != total_shipments) {
      for (size_t i = 0; i < total_shipments; ++i) {
        shipments_in_stops -= shipments_arr[i].id;
      }
      std::ostringstream hint;
      err << "Missing shipments for processing ";
      hint << "Shipments missing: " << shipments_in_stops << log.str();
      *log_msg = pgr_msg(hint.str());
      *err_msg = pgr_msg(err.str());
      return;
    }
 
    /*
     * Finish getting the node ids involved on the process
     */
    for (size_t i = 0; i < total_shipments; ++i) {
      node_ids += shipments_arr[i].pick_node_id;
      node_ids += shipments_arr[i].deliver_node_id;
    }
 
    /*
     * Dealing with time matrix:
     * - Create the unique time matrix to be used for all optimizations
     * - Verify matrix triangle inequality
     * - Verify matrix cells preconditions
     */
    vrprouting::problem::Matrix time_matrix(
        matrix_cells_arr, total_cells,
        multipliers_arr, total_multipliers,
        node_ids, static_cast<Multiplier>(factor));
 
    if (check_triangle_inequality && !time_matrix.obeys_triangle_inequality()) {
      log << "\nFixing Matrix that does not obey triangle inequality "
        << time_matrix.fix_triangle_inequality() << " cycles used";
 
      if (!time_matrix.obeys_triangle_inequality()) {
        log << "\nMatrix Still does not obey triangle inequality ";
      }
    }
 
    if (!time_matrix.has_no_infinity()) {
      err << "\nAn Infinity value was found on the Matrix";
      *err_msg = pgr_msg(err.str());
      *log_msg = pgr_msg(log.str());
      return;
    }
 
    /*
     * get the solution
     */
    auto solution = subdivide?
      subdivide_processing(
          shipments_arr, total_shipments,
          vehicles_arr, total_vehicles,
          time_matrix,
          max_cycles, execution_date,
          subdivide_by_vehicle,
          log) :
      one_processing(
          shipments_arr, total_shipments,
          vehicles_arr, total_vehicles, {},
          time_matrix,
          max_cycles, execution_date);
 
    /*
     * Prepare results
     */
    if (!solution.empty()) {
      (*return_tuples) = pgr_alloc(total_shipments * 2, (*return_tuples));
 
      size_t seq = 0;
      for (const auto &row : solution) {
        for (const auto &o_id : row.stops) {
          (*return_tuples)[seq].vehicle_id = row.id;
          (*return_tuples)[seq].order_id = o_id;
          ++seq;
        }
      }
    }
 
    (*return_count) = total_shipments * 2;
 
    pgassert(*err_msg == nullptr);
    *log_msg = log.str().empty()?
      nullptr :
      pgr_msg(log.str());
    *notice_msg = notice.str().empty()?
      nullptr :
      pgr_msg(notice.str());
  } catch (AssertFailedException &except) {
    err << except.what() << log.str();
    *err_msg = pgr_msg(err.str());
  } catch (std::exception& except) {
    err << except.what() << log.str();
    *err_msg = pgr_msg(err.str());
  } catch (const std::pair<std::string, std::string>& ex) {
    err << ex.first;
    log.str("");
    log.clear();
    log << ex.second;
    *err_msg = pgr_msg(err.str().c_str());
    *log_msg = pgr_msg(log.str().c_str());
  } catch(...) {
    err << "Caught unknown exception!" << log.str();
    *err_msg = pgr_msg(err.str());
  }
}

References PickDeliveryOrders_t::deliver_node_id, Vehicle_t::end_close_t, Vehicle_t::end_node_id, vrprouting::base::Base_Matrix::fix_triangle_inequality(), Identifiers< T >::has(), vrprouting::base::Base_Matrix::has_no_infinity(), Vehicle_t::id, PickDeliveryOrders_t::id, vrprouting::base::Base_Matrix::obeys_triangle_inequality(), anonymous_namespace{optimize_driver.cpp}::one_processing(), pgassert, pgr_alloc(), pgr_msg(), PickDeliveryOrders_t::pick_node_id, Identifiers< T >::size(), Vehicle_t::start_node_id, Vehicle_t::stops, Vehicle_t::stops_size, anonymous_namespace{optimize_driver.cpp}::subdivide_processing(), and AssertFailedException::what().

Referenced by process().