Stochastic Vehicle Scheduling

struct StochasticVehicleSchedulingBenchmark <: AbstractBenchmark

Data structure for a stochastic vehicle scheduling benchmark.

Fields

• nb_tasks::Int64: number of tasks in each instance

• nb_scenarios::Int64: number of scenarios in each instance

column_generation_algorithm(
    instance::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Instance;
    scenario_range,
    bounding,
    use_convex_resources,
    silent,
    close_gap
) -> DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Solution

Solve input instance using column generation.

compact_linearized_mip(
    instance::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Instance;
    scenario_range,
    model_builder,
    silent
) -> Any

Returns the optimal solution of the Stochastic VSP instance, by solving the associated compact MIP. Quadratic constraints are linearized using Mc Cormick linearization. Note: If you have Gurobi, use grb_model as model_builder instead of highs_model.

compact_mip(
    instance::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Instance;
    scenario_range,
    model_builder,
    silent
) -> Any

Returns the optimal solution of the Stochastic VSP instance, by solving the associated compact quadratic MIP. Note: If you have Gurobi, use grb_model as model_builder instead of highs_model.

deterministic_mip(
    instance::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Instance;
    model_builder,
    silent
) -> Any

Solves the deterministic version of the vehicle scheduling problem using a MIP model. Does not take into account the stochastic nature of the problem.

evaluate_solution(
    path_value::BitMatrix,
    instance::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Instance
) -> Any

Compute total weighted objective of solution.

evaluate_solution(
    solution::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Solution,
    instance::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Instance
) -> Any

Compute total weighted objective of solution.

is_feasible(
    solution::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Solution,
    instance::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Instance;
    verbose
) -> Bool

Check if solution is an admissible solution of instance.

local_search(
    instance::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Instance;
    num_iterations
) -> DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Solution

Very simple heuristic, using local_search initialised with the solution of the deterministic Linear program

plot_instance(
    ::StochasticVehicleSchedulingBenchmark,
    sample::DataSample{<:DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Instance{DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.City}};
    color_scheme,
    kwargs...
) -> Plots.Plot

plot_solution(
    ::StochasticVehicleSchedulingBenchmark,
    sample::DataSample{<:DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Instance{DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.City}};
    kwargs...
) -> Plots.Plot

generate_dataset(
    benchmark::StochasticVehicleSchedulingBenchmark,
    dataset_size::Int64;
    compute_solutions,
    seed,
    rng,
    algorithm,
    store_city,
    kwargs...
) -> Any

Create a dataset of dataset_size instances for the given StochasticVehicleSchedulingBenchmark. If you want to not add label solutions in the dataset, set compute_solutions=false. By default, they will be computed using column generation. Note that computing solutions can be time-consuming, especially for large instances. You can also use instead compact_mip or compact_linearized_mip as the algorithm to compute solutions. If you want to provide a custom algorithm to compute solutions, you can pass it as the algorithm keyword argument. If algorithm takes keyword arguments, you can pass them as well directly in kwargs.... If store_city=false, the coordinates and unnecessary information about instances will not be stored in the dataset.

generate_maximizer(
    bench::StochasticVehicleSchedulingBenchmark;
    model_builder
) -> DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.StochasticVechicleSchedulingMaximizer{typeof(DecisionFocusedLearningBenchmarks.Utils.highs_model)}

generate_statistical_model(
    ::StochasticVehicleSchedulingBenchmark;
    seed
) -> Flux.Chain{T} where T<:Tuple{Flux.Dense{typeof(identity), Matrix{Float32}}, typeof(vec)}

struct City

Data structure for a city in the vehicle scheduling problem. Contains all the relevant information to build an instance of the problem.

Fields

• width::Int64: city width (in minutes)

• vehicle_cost::Float64: cost of a vehicle in the objective function

• delay_cost::Float64: cost of one minute delay in the objective function

• nb_tasks::Int64: number of tasks to fulfill

• tasks::Vector{DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Task}: tasks list (see Task), that should be ordered by start time

• district_width::Int64: idth (in minutes) of each district

• districts::Matrix{DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.District}: districts matrix (see District), indices corresponding to their relative positions

• random_inter_area_factor::Distributions.LogNormal{Float64}: a log-normal distribution modeling delay between districts

• scenario_inter_area_factor::Matrix{Float64}: size (nb_scenarios, 24), each row correspond to one scenario, each column to one hour of the day

City(
;
    nb_scenarios,
    width,
    vehicle_cost,
    nb_tasks,
    tasks,
    district_width,
    districts,
    delay_cost,
    random_inter_area_factor,
    scenario_inter_area_factor
) -> DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.City

Constructor for City.

struct District

Data structure for a district in the vehicle scheduling problem.

Fields

• random_delay::Distributions.LogNormal{Float64}: log-normal distribution modeling the district delay

• scenario_delay::Matrix{Float64}: size (nb_scenarios, 24), observed delays for each scenario and hour of the day

District(; random_delay, nb_scenarios)

Constructor for District. Initialize a district with a given number of scenarios, with zeros in scenario_delay.

struct Instance{CC, G<:Graphs.AbstractGraph, M1<:(AbstractMatrix), M2<:(AbstractMatrix), F, C}

Instance of the stochastic VSP problem.

Fields

• graph::Graphs.AbstractGraph: graph computed from city with the create_VSP_graph(city::City) method

• features::Matrix: features matrix computed from city

• slacks::AbstractMatrix: slack matrix

• intrinsic_delays::AbstractMatrix: intrinsic delays scenario matrix

• vehicle_cost::Any: cost of a vehicle

• delay_cost::Any: cost of one minute delay

• city::Any: associated city

Instance(
;
    nb_tasks,
    nb_scenarios,
    rng,
    store_city,
    kwargs...
)

Constructor for Instance. Build an Instance for the stochatsic vehicle scheduling problem, with nb_tasks tasks and nb_scenarios scenarios.

struct Point

2D point data structure.

struct Solution

Should always be associated with an Instance.

Fields

• value::BitVector: for each graph edge of instance, 1 if selected, else 0

• path_value::BitMatrix: each row represents a vehicle, each column a task. 1 if task is done by the vehicle, else 0

Solution(
    path_value::BitMatrix,
    instance::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Instance
) -> DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Solution

Create a Solution from a BitMatrix path value.

Solution(
    value::BitVector,
    instance::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Instance
) -> DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Solution

Create a Solution from a BitVector value.

struct StochasticVechicleSchedulingMaximizer{M}

Deterministic vsp maximizer for the StochasticVehicleSchedulingBenchmark.

Apply the maximizer with the stored model builder.

struct Task

Data structure for a task in the vehicle scheduling problem.

Fields

• type::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.TaskType: type of the task (depot start, job, or depot end)

• start_point::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Point: starting location of the task

• end_point::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Point: end location of the task

• start_time::Float64: start time (in minutes) of the task

• end_time::Float64: end time (in minutes) of the task

• random_delay::Distributions.LogNormal{Float64}: lognormal distribution modeling the task start delay

• scenario_start_time::Vector{Float64}: size (nb_scenarios), observed delayed start times for each scenario

• scenario_end_time::Vector{Float64}: size (nb_scenarios), observed delayed end times for each scenario

Task(
;
    type,
    start_point,
    end_point,
    start_time,
    end_time,
    nb_scenarios,
    random_delay
)

Constructor for Task.

_local_search(
    solution::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Solution,
    instance::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Instance;
    nb_it
) -> Tuple{DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Solution, Any, Vector{Int64}, Vector}

Very simple local search heuristic, using the neighborhood defined by move_one_random_task

column_generation(instance::Instance)

Note: If you have Gurobi, use grb_model as model_builder instead of glpk_model.

compute_delays(
    city::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.City
) -> Matrix{Float64}

Compute delays for instance.

compute_features(
    city::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.City
) -> Matrix{Float32}

Returns a matrix of features of size (20, nb_edges). For each edge, compute the following features (in the same order):

• travel time
• vehicle_cost if edge is connected to source, else 0
• 9 deciles of the slack
• cumulative probability distribution of the slack evaluated in [-100, -50, -20, -10, 0, 10, 50, 200, 500]

compute_perturbed_end_times!(
    city::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.City
)

Compute the end times of the tasks for each scenario.

compute_slacks(
    city::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.City,
    graph::Graphs.AbstractGraph
) -> Any

Compute slack for instance. TODO: differentiate from other method

compute_slacks(
    city::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.City,
    old_task_index::Int64,
    new_task_index::Int64
) -> Vector{Float64}

Compute slack for features.

compute_solution_from_selected_columns(
    instance::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Instance,
    paths;
    bin,
    model_builder,
    scenario_range,
    silent
) -> Tuple{Float64, Any, Any}

Note: If you have Gurobi, use grb_model as model_builder instead od glpk_model.

create_VSP_graph(
    city::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.City
) -> Graphs.SimpleGraphs.SimpleDiGraph{Int64}

Return the acyclic directed graph corresponding to city. Each vertex represents a task. Vertices are ordered by start time of corresponding task. There is an edge from task u to task v the (end time of u + tie distance between u and v <= start time of v).

create_random_city(
;
    αᵥ_low,
    αᵥ_high,
    first_begin_time,
    last_begin_time,
    district_μ,
    district_σ,
    task_μ,
    task_σ,
    seed,
    rng,
    city_kwargs...
) -> DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.City

• Creates a city from city_kwargs
• Depot location at city center
• Randomize tasks, and add two dummy tasks : one source task at time=0 from the depot, and one destination task ending at time=end at depot
• Roll every scenario.

delay_sum(path, slacks, delays)

Evaluate the total delay along path.

distance(
    p₁::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Point,
    p₂::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Point
) -> Float64

Returns euclidean distance between p₁ and p₂.

draw_random_point(distrib::Distributions.Distribution; rng)

Returns a Point with random x and y, drawn from distrib.

evaluate_scenario(path_value::BitMatrix, instance::Instance, scenario_index::Int)

Compute total delay of scenario.

evaluate_scenario(
    solution::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Solution,
    instance::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Instance,
    scenario_index::Int64
) -> Any

Compute total delay of scenario.

evaluate_task(
    i_task::Integer,
    instance::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Instance,
    old_task_index::Integer,
    old_delay::Real,
    scenario::Int64
) -> Any

Evaluate the total delay of task i_task in scenario, knowing that current delay from task old_task_index is old_delay.

find_first_one(A::AbstractVector) -> Int64

Returns index of first non zero element of A.

generate_scenarios!(
    city::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.City;
    rng
)

Draw all delay scenarios for the city.

get_district(point::Point, city::City)

Return indices of the city district containing point.

get_features(
    instance::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Instance
) -> Matrix

Returns the feature matrix associated to instance.

get_nb_scenarios(
    city::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.City
) -> Int64

Returns the number of scenarios in city.

get_nb_scenarios(
    instance::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Instance
) -> Any

Returns the number of scenarios in instance.

get_nb_tasks(
    city::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.City
) -> Int64

Returns the number of tasks in city.

get_nb_tasks(
    instance::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Instance
) -> Any

Returns the number of tasks in instance.

get_perturbed_travel_time(
    city::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.City,
    old_task_index::Int64,
    new_task_index::Int64,
    scenario::Int64
) -> Float64

Compute the achieved travel time of scenario scenario from old_task_index to new_task_index.

hour_of(minutes::Real) -> Int64

Returns hour of the day corresponding to minutes amount.

init_districts!(
    city::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.City,
    district_μ::Distributions.Distribution,
    district_σ::Distributions.Distribution;
    rng
)

Initialize the districts of the city.

init_tasks!(
    city::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.City,
    αᵥ_low::Real,
    αᵥ_high::Real,
    first_begin_time::Real,
    last_begin_time::Real,
    task_μ::Distributions.Distribution,
    task_σ::Distributions.Distribution;
    rng
)

Draw the tasks of the city.

move_one_random_task!(
    path_value::BitMatrix,
    graph::Graphs.AbstractGraph
)

Select one random (uniform) task and move it to another random (uniform) feasible vehicle

nb_scenarios(
    task::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Task
) -> Int64

Return the number of scenarios for the given task.

roll(
    district::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.District,
    rng::Random.AbstractRNG
)

Populate scenario_delay with delays drawn from random_delay distribution for each (scenario, hour) pair.

roll(
    task::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Task,
    rng::Random.AbstractRNG
)

Populate scenario_start_time with delays drawn from the random_delay distribution of the given task for each scenario.

scenario_next_delay(
    previous_delay::Real,
    random_delay::Distributions.Distribution,
    rng::Random.AbstractRNG
) -> Any

Return one scenario of future delay given current delay and delay distribution.

solution_from_JuMP_array(
    x::AbstractArray,
    graph::Graphs.AbstractGraph
) -> Any

Create a Solution from a JuMP array.

solution_from_paths(
    paths,
    instance::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Instance
) -> DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Solution

Create a Solution from routes.

solve_deterministic_VSP(
    instance::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Instance;
    include_delays,
    model_builder,
    verbose
) -> Tuple{Union{Float64, Vector{Float64}}, Any}

Return the optimal solution of the deterministic VSP problem associated to instance. The objective function is vehicle_cost * nb_vehicles + include_delays * delay_cost * sum_of_travel_times Note: If you have Gurobi, use grb_model as model_builder instead od highs_model.

to_array(
    solution::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Solution,
    instance::DecisionFocusedLearningBenchmarks.StochasticVehicleScheduling.Instance
) -> Any

Returns a BitMatrix, with value true at each index (i, j) if corresponding edge of graph is selected in the solution

vsp_maximizer(
    θ::AbstractVector;
    instance,
    model_builder,
    silent
)

Given arcs weights θ, solve the deterministic VSP problem associated to instance.