#include <routing_lp_scheduling.h>

Public Member Functions
	DimensionCumulOptimizerCore (const RoutingDimension *dimension, bool use_precedence_propagator)

DimensionSchedulingStatus	OptimizeSingleRouteWithResource (int vehicle, double solve_duration_ratio, const std::function< int64_t(int64_t)> &next_accessor, const RouteDimensionTravelInfo dimension_travel_info, const Resource resource, bool optimize_vehicle_costs, RoutingLinearSolverWrapper solver, std::vector< int64_t > cumul_values, std::vector< int64_t > break_values, int64_t cost_without_transit, int64_t *transit_cost, bool clear_lp=true)

DimensionSchedulingStatus	ComputeSingleRouteSolutionCostWithoutFixedTransits (int vehicle, double solve_duration_ratio, const std::function< int64_t(int64_t)> &next_accessor, const RouteDimensionTravelInfo dimension_travel_info, RoutingLinearSolverWrapper solver, absl::Span< const int64_t > solution_cumul_values, absl::Span< const int64_t > solution_break_values, int64_t cost_without_transits, int64_t cost_offset=nullptr, bool reuse_previous_model_if_possible=true, bool clear_lp=false, bool clear_solution_constraints=true, absl::Duration *solve_duration=nullptr)

std::vector< DimensionSchedulingStatus >	OptimizeSingleRouteWithResources (int vehicle, double solve_duration_ratio, const std::function< int64_t(int64_t)> &next_accessor, const std::function< int64_t(int64_t, int64_t)> &transit_accessor, const RouteDimensionTravelInfo dimension_travel_info, absl::Span< const Resource > resources, absl::Span< const int > resource_indices, bool optimize_vehicle_costs, RoutingLinearSolverWrapper solver, std::vector< std::vector< int64_t > > cumul_values, std::vector< std::vector< int64_t > > break_values, std::vector< int64_t > costs_without_transits, int64_t transit_cost, bool clear_lp=true)

DimensionSchedulingStatus	Optimize (const std::function< int64_t(int64_t)> &next_accessor, const std::vector< RouteDimensionTravelInfo > &dimension_travel_info_per_route, RoutingLinearSolverWrapper solver, std::vector< int64_t > cumul_values, std::vector< int64_t > break_values, std::vector< std::vector< int > > resource_indices_per_group, int64_t cost_without_transits, int64_t transit_cost, bool clear_lp=true, bool optimize_resource_assignment=true)

DimensionSchedulingStatus	OptimizeAndPack (const std::function< int64_t(int64_t)> &next_accessor, const std::vector< RouteDimensionTravelInfo > &dimension_travel_info_per_route, RoutingLinearSolverWrapper solver, std::vector< int64_t > cumul_values, std::vector< int64_t > *break_values)

DimensionSchedulingStatus	OptimizeAndPackSingleRoute (int vehicle, double solve_duration_ratio, const std::function< int64_t(int64_t)> &next_accessor, const RouteDimensionTravelInfo dimension_travel_info, const Resource resource, RoutingLinearSolverWrapper solver, std::vector< int64_t > cumul_values, std::vector< int64_t > *break_values)

const RoutingDimension *	dimension () const

Detailed Description

Utility class used in Local/GlobalDimensionCumulOptimizer to set the linear solver constraints and solve the problem.

Definition at line 698 of file routing_lp_scheduling.h.

Constructor & Destructor Documentation

◆ DimensionCumulOptimizerCore()

operations_research::DimensionCumulOptimizerCore::DimensionCumulOptimizerCore	(	const RoutingDimension *	dimension,
		bool	use_precedence_propagator )

Initialize vehicle_to_first_index_ so the variables of the breaks of vehicle v are stored from vehicle_to_first_index_[v] to vehicle_to_first_index_[v+1] - 1.

Definition at line 577 of file routing_lp_scheduling.cc.

Member Function Documentation

◆ ComputeSingleRouteSolutionCostWithoutFixedTransits()

DimensionSchedulingStatus operations_research::DimensionCumulOptimizerCore::ComputeSingleRouteSolutionCostWithoutFixedTransits	(	int	vehicle,
		double	solve_duration_ratio,
		const std::function< int64_t(int64_t)> &	next_accessor,
		const RouteDimensionTravelInfo *	dimension_travel_info,
		RoutingLinearSolverWrapper *	solver,
		absl::Span< const int64_t >	solution_cumul_values,
		absl::Span< const int64_t >	solution_break_values,
		int64_t *	cost_without_transits,
		int64_t *	cost_offset = nullptr,
		bool	reuse_previous_model_if_possible = true,
		bool	clear_lp = false,
		bool	clear_solution_constraints = true,
		absl::Duration *	solve_duration = nullptr )

Given some cumuls and breaks, computes the solution cost by solving the same model as in OptimizeSingleRouteWithResource() with the addition of constraints for cumuls and breaks.

Make sure SetRouteCumulConstraints will properly set the cumul bounds by looking at this route only.

Constrains the cumuls.

Constrains the breaks.

Definition at line 609 of file routing_lp_scheduling.cc.

◆ dimension()

const RoutingDimension * operations_research::DimensionCumulOptimizerCore::dimension ( ) const

inline

Definition at line 778 of file routing_lp_scheduling.h.

◆ Optimize()

DimensionSchedulingStatus operations_research::DimensionCumulOptimizerCore::Optimize	(	const std::function< int64_t(int64_t)> &	next_accessor,
		const std::vector< RouteDimensionTravelInfo > &	dimension_travel_info_per_route,
		RoutingLinearSolverWrapper *	solver,
		std::vector< int64_t > *	cumul_values,
		std::vector< int64_t > *	break_values,
		std::vector< std::vector< int > > *	resource_indices_per_group,
		int64_t *	cost_without_transits,
		int64_t *	transit_cost,
		bool	clear_lp = true,
		bool	optimize_resource_assignment = true )

In the Optimize() method, if both 'cumul_values' and 'cost' parameters are null, we don't optimize the cost and stop at the first feasible solution in the linear solver (since in this case only feasibility is of interest). When 'optimize_resource_assignment' is false, the resource var values are used to constrain the vehicle routes according to their assigned resource.

If both "cumul_values" and "costs_without_transits" parameters are null, we don't try to optimize the cost and stop at the first feasible solution.

Tighten the route start/end cumul wrt. resources assigned to it.

Todo: (user): In case the status is RELAXED_OPTIMAL_ONLY, check we can safely avoid filling variable and cost values.

Definition at line 966 of file routing_lp_scheduling.cc.

◆ OptimizeAndPack()

DimensionSchedulingStatus operations_research::DimensionCumulOptimizerCore::OptimizeAndPack	(	const std::function< int64_t(int64_t)> &	next_accessor,
		const std::vector< RouteDimensionTravelInfo > &	dimension_travel_info_per_route,
		RoutingLinearSolverWrapper *	solver,
		std::vector< int64_t > *	cumul_values,
		std::vector< int64_t > *	break_values )

Note: We pass a non-nullptr cost to the Optimize() method so the costs are optimized by the solver.

Subtle: Even if the status was RELAXED_OPTIMAL_ONLY we try to pack just in case packing manages to make the solution completely feasible.

Todo: (user): In case the status is RELAXED_OPTIMAL_ONLY, check we can safely avoid filling variable values.

Definition at line 1061 of file routing_lp_scheduling.cc.

◆ OptimizeAndPackSingleRoute()

DimensionSchedulingStatus operations_research::DimensionCumulOptimizerCore::OptimizeAndPackSingleRoute	(	int	vehicle,
		double	solve_duration_ratio,
		const std::function< int64_t(int64_t)> &	next_accessor,
		const RouteDimensionTravelInfo *	dimension_travel_info,
		const Resource *	resource,
		RoutingLinearSolverWrapper *	solver,
		std::vector< int64_t > *	cumul_values,
		std::vector< int64_t > *	break_values )

Todo: (user): Since there are 3 separate solves for packing, divide the input solve_duration_ratio by 3 before passing to the below functions? Or maybe divide by 2 and let PackRoutes() divide by 2 itself (since the 2 solves in PackRoutes() should start with a very good first solution hint).

Definition at line 1109 of file routing_lp_scheduling.cc.

◆ OptimizeSingleRouteWithResource()

DimensionSchedulingStatus operations_research::DimensionCumulOptimizerCore::OptimizeSingleRouteWithResource	(	int	vehicle,
		double	solve_duration_ratio,
		const std::function< int64_t(int64_t)> &	next_accessor,
		const RouteDimensionTravelInfo *	dimension_travel_info,
		const Resource *	resource,
		bool	optimize_vehicle_costs,
		RoutingLinearSolverWrapper *	solver,
		std::vector< int64_t > *	cumul_values,
		std::vector< int64_t > *	break_values,
		int64_t *	cost_without_transit,
		int64_t *	transit_cost,
		bool	clear_lp = true )

Finds an optimal (or just feasible) solution for the route for the given resource. If the resource is null, it is simply ignored.

Definition at line 721 of file routing_lp_scheduling.cc.

◆ OptimizeSingleRouteWithResources()

std::vector< DimensionSchedulingStatus > operations_research::DimensionCumulOptimizerCore::OptimizeSingleRouteWithResources	(	int	vehicle,
		double	solve_duration_ratio,
		const std::function< int64_t(int64_t)> &	next_accessor,
		const std::function< int64_t(int64_t, int64_t)> &	transit_accessor,
		const RouteDimensionTravelInfo *	dimension_travel_info,
		absl::Span< const Resource >	resources,
		absl::Span< const int >	resource_indices,
		bool	optimize_vehicle_costs,
		RoutingLinearSolverWrapper *	solver,
		std::vector< std::vector< int64_t > > *	cumul_values,
		std::vector< std::vector< int64_t > > *	break_values,
		std::vector< int64_t > *	costs_without_transits,
		int64_t *	transit_cost,
		bool	clear_lp = true )

Computes the optimal scheduling solution(s) for the route for each resource in 'resources' with an index in 'resource_indices'. If both 'resources' and 'resource_indices' are empty, computes the optimal solution for the route itself (without added resource constraints).

Make sure SetRouteCumulConstraints will properly set the cumul bounds by looking at this route only.

An unused empty vehicle doesn't require resources.

Note: When there are no resources to optimize for, we still solve the optimization problem for the route (without any added resource constraint).

Todo: (user): Consider taking 'num_solves' into account to re-adjust the solve_duration_ratio to make sure all sub-problems are given enough time.

The model's deadline has been reached, stop.

The resource attributes don't match this vehicle.

Definition at line 860 of file routing_lp_scheduling.cc.

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

ortools/constraint_solver/routing_lp_scheduling.h
ortools/constraint_solver/routing_lp_scheduling.cc

Public Member Functions