API Reference

City

Contains all the relevant information for an instance of the stochastic VSP problem.

Fields

• width::Int: 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::Int: number of tasks to fulfill
• tasks::Vector{Task}: tasks list (see Task), that should be ordered by start time
• district_width::Int: width (in minutes) of each district
• districts::Matrix{District}: districts matrix (see District), indices corresponding to their relative positions
• random_inter_area_factor::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

CompactInstance{G<:AbstractGraph,M1,M2,C}

Instance of the stochastic VSP problem.

Fields

• graph::G: graph computed from city with the create_VSP_graph(city::City) method.
• features::Matrix{Float64}: features matrix computed from city
• slacks
• delays

CompactInstance(city::City)

Build a CompactInstance from a City, by computing its graph, features, slacks and delays.

District

Fields

• random_delay::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::LogNormal{Float64}, nb_scenarios::Int)

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

Instance{G<:AbstractGraph,M1,M2,C}

Instance of the stochastic VSP problem.

Fields

• city::City
• graph::G: graph computed from city with the create_VSP_graph(city::City) method.
• features::Matrix{Float64}: features matrix computed from city
• slacks
• delays

Instance(city::City)

Build an Instance from a City, by computing its graph, features, slacks and delays.

Pipeline

InferOpt pipeline container an encoder and a maximizer

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(value::BitVector, instance::AbstractInstance)

Create a Solution from a BitMatrix path value.

Solution(value::BitVector, instance::AbstractInstance)

Create a Solution from a BitVector value.

Task

Fields

• type::TaskType
• start_point::Point: starting location of the task
• end_point::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::LogNormal{Float64}: lognormal distribution modeling the task start delay
• scenario_start_time::Vector{Float64}: size (nb_scenarios), realized delayed start times for each scenario
• scenario_end_time::Vector{Float64}: size (nb_scenarios), realized delayed end times for each scenario

Trainer

Main structure used for training an InferOpt model.

basic_solution(graph::AbstractGraph)

Create a solution with one vehicle per task.

cbc_model()

Initialiaze a Cbc model with disabled logging.

column_generation(instance::Instance)

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

compute_delays(city)

Compute delays for instance.

compute_features(city::City)

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_slacks(city)

Compute slack for instance. TODO: differentiate from other method

compute_slacks(city, old_task_index, new_task_index)

Compute slack for features.

compute_solution_from_selected_columns(instance::AbstractInstance, paths[; bin=true])

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

compute_μ_σ(X::Vector{Instance})

Compute mean, standard deviation, and max values for each features in X instances.

create_VSP_graph(city::City)

Return a MetaDiGraph computed from 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). Every (u, v) edge has a :travel_time property, corresponding to time istance between u and v.

create_random_city(;
    αᵥ_low=default_αᵥ_low,
    αᵥ_high=default_αᵥ_high,
    first_begin_time=default_first_begin_time,
    last_begin_time=default_last_begin_time,
    district_μ=default_district_μ,
    district_σ=default_district_σ,
    task_μ=default_task_μ,
    task_σ=default_task_σ,
    city_kwargs...
)

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

create_random_instance([; city_kwargs])

Returns a random instance created with city_kwargs.

create_random_instance([; city_kwargs])

Returns a random instance created with city_kwargs.

delay_sum(path, slacks, delays)

Evaluate the total delay along path.

distance(p₁, p₂)

Returns euclidean distance between p₁ and p₂.

draw_random_point(distrib)

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

easy_problem(θ[; instance::AbstractInstance, model_builder])

Solves the easy problem of the learning pipeline given arcs weights θ. Note: If you have Gurobi, use grb_model as model_builder instead od cbc_model.

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

Compute total delay of scenario.

evaluate_scenario(solution::Solution, instance::AbstractInstance, scenario_index::Int)

Compute total delay of scenario.

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

Compute total weighted objective of solution.

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

Compute total weighted objective of solution.

evaluate_task(
    i_task::Integer,
    instance::AbstractInstance,
    old_task_index::Integer,
    old_delay::Real,
    scenario::Int,
)

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)

Returns index of first non zero element of A.

generate_dataset(
    dataset_folder::String,
    nb_train_samples::Integer,
    nb_val_samples::Integer,
    nb_test_samples::Integer;
    random_seed=67,
    labeled=true,
    heuristic=true,
    city_kwargs,
)

Create a dataset in dataset_folder, train/validation/test samples, one file per subdataset. Also create a config file in the same location with some information.

generate_samples(nb_samples::Integer[; heuristic=true, labeled=true, city_kwargs])

Generate nb_samples random instances with city_kwargs. If labeled, compute associated solutions for each instance: use local search if heuristic, else compute optimal solution.

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

Return indices of the city district containing point.

get_nb_scenarios(instance::AbstractInstance)

Returns the number of scenarios in instance.

get_nb_scenarios(city::City)

Returns the number of scenarios in city.

get_nb_tasks(instance::AbstractInstance)

Returns the number of tasks in instance.

get_nb_tasks(city::City)

Returns the number of tasks in city.

get_perturbed_travel_time(city::City, old_task_index::Int, new_task_index::Int, scenario::Int)

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

get_routes(solution::Solution)

Compute routes of solution.

glpk_model()

Initialize a GLPK model (with disabled logging).

heuristic_solution(instance::AbstractInstance; nb_it=100)

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

highs_model()

Initialize a HiGHS model (with disabled logging).

hour_of(minutes::Real)::Int

Returns hour of the day corresponding to minutes amount.

is_admissible(solution::Solution, instance::AbstractInstance)

Check if solution is an admissible solution of instance.

local_search(solution::Solution, instance::AbstractInstance; nb_it::Integer=100)

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

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

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

normalize_data!(X, μ, σ)

Standardize each feature of X by centering and reducing with μ and σ.

read_config(config_file::String)

Read a Yaml config into a NamedTuple.

recursive_convert(x)

Convert recursively a NamedTuple to a Dict.

recursive_namedtuple(x)

Convert recursively a Dict to a NamedTuple.

reduce_data!(X, σ)

Reduce X with σ, without centering it.

roll(task)

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

roll(task)

Populate scenario_start_time with delays drawn from random_delay distribution for each scenario.

save_config(config::Dict, save_path::String)

Save Dict config to yaml file.

save_config(config::NamedTuple, save_path::String)

Save a NamedTuple config to yaml file.

scenario_next_delay(previous_delay, random_delay)

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

solution_from_paths(paths, instance::AbstractInstance)

Create a Solution from a JuMP array.

solution_from_paths(paths, instance::AbstractInstance)

Create a Solution from routes.

solve_deterministic_VSP(instance::Instance; include_delays=true)

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

solve_scenarios(instance::AbstractInstance; model_builder)

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

to_array(solution::Solution, instance::AbstractInstance)

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