Instance Generation

Instance generation follows the paper [Li21]:

  1. The depot and services’ \((x, y)\) locations are sampled uniformly from \([0, 1]^2\);

  2. Each service’s demand \(d_i\) is sampled uniformly from \({1, 2, ..., 9}\), and each vehicle has capacity \(C = 50\);

  3. For the time window constraint, we set the time window for the depot as \([b_0, e_0] = [0, 3]\), and the service time at each \(i\) to be \(s_i = 0.2\). We further set the time window for city node \(i\) by: (a) sampling the time window center \(ci ∼ U([b_0 + t_{0,i}, e_0 − t_{i,0} − s_i])\), where \(t_{0,i} = t_{i,0}\) is the travel time, equaling the Euclidean distance, from the depot to node \(i\); (b) sampling the time window half-width \(h_i\) uniformly at random from \([s_i/2, e_0/3] = [0.1, 1]\); (c) setting the time window for \(i\) as \([max(b_0, c_i − h_i), min(e_0, c_i + h_i)]\).

Instances generation settings are defined in file instances_generator.py.

InstanceGenerator

class maenvs4vrp.environments.mtvrp.instances_generator.InstanceGenerator(instance_type: str = 'validation', set_of_instances: set = None, device: str | None = 'cpu', batch_size: Size | None = None, seed: int = None)[source]

MTVRP instance generation class.

__init__(instance_type: str = 'validation', set_of_instances: set = None, device: str | None = 'cpu', batch_size: Size | None = None, seed: int = None) → None[source]

Constructor. Instance generator.

Parameters:

  • instance_type (str) – Instance type. Can be “validation” or “test”. Defaults to “validation”.

  • set_of_instances (set) – Set of instances file names. Defaults to None.

  • device (str, optional) – Type of processing. It can be “cpu” or “gpu”. Defaults to “cpu”.

  • batch_size (torch.Size, optional) – Batch size. If not specified, defaults to 1.

  • seed (int) – Random number generator seed. Defaults to None.

Returns:

None.

augment_generate_instance(num_agents: int = None, num_nodes: int = None, min_coords: float = None, max_coords: float = None, capacity: float = None, service_time: float = None, min_demands: int = None, max_demands: int = None, min_backhaul: int = None, max_backhaul: int = None, max_time: float = None, backhaul_ratio: float = None, backhaul_class: int = None, sample_backhaul_class: bool = None, max_distance_limit: float = None, speed: float = None, subsample: bool = True, variant_preset=None, use_combinations: bool = False, batch_size: Size | None = None, n_augment: int = 2, seed: int = None, device: str | None = 'cpu') → TensorDict[source]

Generate augmented instance.

Parameters:

  • num_agents (int) – Total number of agents. Defaults to None.

  • num_nodes (int) – Total number of nodes. Defaults to None.

  • min_coords (float) – Minimum number of coords. Defaults to None.

  • max_coords (float) – Maximum number of coords. Defaults to None.

  • capacity (int) – Vehicles’ capacity. Defaults to None.

  • service_time (float) – Service time. Defaults to None.

  • min_demands (int) – Minimum number of demands. Defaults to None.

  • max_demands (int) – Maximum number of demands. Defaults to None.

  • min_backhaul (int) – Minimum number of backhauls. Defaults to None.

  • max_backhaul (int) – Maximum number of backhauls. Defaults to None.

  • max_time (float) – Maximum route time. Defaults to None.

  • backhaul_ratio (float) – Ratio of backhaul demands. Defaults to None.

  • backhaul_class (int) – Class of backhaul problem. If 1, it’s unmixed, if 2, it’s mixed. Defaults to None.

  • sample_backhaul_class (bool) – If backhaul class is sampled across batches. Defaults to None.

  • max_distance_limit (float) – Route distance limits. Defaults to None.

  • speed (float) – Vehicles’ speed. Defaults to None.

  • subsample (bool) – If problem variants are to be sampled. Defaults to True.

  • variant_preset (str) – Variant preset to be sampled. Defaults to None.

  • use_combinations (bool) – It considers combinations for which sampling mask the instance is defined. Defaults to False.

  • force_visit (bool) – It forces the agent to visit all feasible nodes before going back to depot. Defaults to True.

  • batch_size (torch.Size, optional) – Batch size. Defaults to None.

  • n_augment (int) – Number of augmentations. Defaults to 2.

  • seed (int) – Random number generator seed. Defaults to None.

  • device (str, optional) – Type of processing. It can be “cpu” or “gpu”. Defaults to “cpu”.

Returns:

Instance data.

Return type:

TensorDict

generate_backhaul_class(shape: Tuple[int, int], sample: bool = False)[source]

Generate backhaul class.

Parameters:

  • shape (Tuple) – Tensor shape.

  • sample (bool) – Sample backhaul class. Defaults to False.

Returns:

Linehaul and backhaul demands.

Return type:

torch.Tensor

generate_demands(batch_size: int, num_nodes: int) → Tensor[source]

Generate demands.

Parameters:

  • batch_size (int) – Batch size.

  • num_nodes (int) – Number of nodes.

Returns:

Linehaul and backhaul demands.

Return type:

torch.Tensor

generate_distance_limit(shape: Tuple[int, int], coords: Tensor) → Tensor[source]

Generate distance limits.

Parameters:

  • shape (Tuple) – Tensor shape.

  • coords (torch.Tensor) – Nodes coordinates.

Returns:

Distance limits.

Return type:

torch.Tensor

generate_time_windows(coords: Tensor = None, speed: Tensor = None) → Tensor[source]

Generate time windows.

Parameters:

  • coords (torch.Tensor) – Nodes coordinates.

  • speed (torch.Tensor) – Agents speed.

Returns:

Time windows and service times.

Return type:

torch.Tensor

get_distance(x: Tensor, y: Tensor)[source]

Euclidean distance between two tensors of shape `[…, n, dim]. Taken from: https://github.com/ai4co/rl4co/blob/main/rl4co/utils/ops.py

Parameters:

  • x (torch.Tensor) – Point x.

  • y (torch.Tensor) – Point y.

Returns:

Distance between x and y.

Return type:

torch.Tensor

get_instance(instance_name: str, num_agents: int = None) → Dict[source]

Get an instance with custom number of agents.

Parameters:

  • instance_name (str) – Instance file name.

  • num_agents (int) – Number of agents. Defaults to None.

Returns:

Instance data.

Return type:

Dict

classmethod get_list_of_benchmark_instances(mixed: bool = True)[source]

Get list of generated instances.

Parameters:

mixed (bool) – If True, it gets all instances. If False, it gets only unmixed instances. Defaults to True.

Returns:

Generated instances.

Return type:

benchmark_instances(list)

load_set_of_instances(set_of_instances: set = None)[source]

Load every instance on set_of_instances set.

Parameters:

set_of_instances (set) – Set of instances file names. Defaults to None.

Returns:

None.

random_generate_instance(num_agents: int = None, num_nodes: int = None, min_coords: float = None, max_coords: float = None, capacity: float = None, service_time: float = None, min_demands: int = None, max_demands: int = None, min_backhaul: int = None, max_backhaul: int = None, max_time: float = None, backhaul_ratio: float = None, backhaul_class: int = None, sample_backhaul_class: bool = None, max_distance_limit: float = None, speed: float = None, subsample: bool = True, variant_preset=None, use_combinations: bool = False, batch_size: Size | None = None, seed: int = None, device: str | None = 'cpu') → TensorDict[source]

Generate random instance.

Parameters:

  • num_agents (int) – Total number of agents. Defaults to None.

  • num_nodes (int) – Total number of nodes. Defaults to None.

  • min_coords (float) – Minimum number of coords. Defaults to None.

  • max_coords (float) – Maximum number of coords. Defaults to None.

  • capacity (int) – Vehicles’ capacity. Defaults to None.

  • service_time (float) – Service time. Defaults to None.

  • min_demands (int) – Minimum number of demands. Defaults to None.

  • max_demands (int) – Maximum number of demands. Defaults to None.

  • min_backhaul (int) – Minimum number of backhauls. Defaults to None.

  • max_backhaul (int) – Maximum number of backhauls. Defaults to None.

  • max_time (float) – Maximum route time. Defaults to None.

  • backhaul_ratio (float) – Ratio of backhaul demands. Defaults to None.

  • backhaul_class (int) – Class of backhaul problem. If 1, it’s unmixed, if 2, it’s mixed. Defaults to None.

  • sample_backhaul_class (bool) – If backhaul class is sampled across batches. Defaults to None.

  • max_distance_limit (float) – Route distance limits. Defaults to None.

  • speed (float) – Vehicles’ speed. Defaults to None.

  • subsample (bool) – If problem variants are to be sampled. Defaults to True.

  • variant_preset (str) – Variant preset to be sampled. Defaults to None.

  • use_combinations (bool) – It considers combinations for which sampling mask the instance is defined. Defaults to False.

  • force_visit (bool) – It forces the agent to visit all feasible nodes before going back to depot. Defaults to True.

  • batch_size (torch.Size, optional) – Batch size. Defaults to None.

  • seed (int) – Random number generator seed. Defaults to None.

  • device (str, optional) – Type of processing. It can be “cpu” or “gpu”. Defaults to “cpu”.

Returns:

Instance data.

Return type:

TensorDict

read_instance_data(instance_name: str)[source]

Read instance data from file.

Parameters:

instance_name (str) – Instance file name.

Returns:

Instance data.

Return type:

Dict

sample_instance(num_agents: int = 2, num_nodes: int = 15, min_coords: float = 0.0, max_coords: float = 1.0, capacity: float = None, service_time: float = 0.2, min_demands: int = 1, max_demands: int = 10, min_backhaul: int = 1, max_backhaul: int = 10, max_time: float = 4.6, backhaul_ratio: float = 0.2, backhaul_class: int = 1, sample_backhaul_class: bool = False, max_distance_limit: float = 2.8, speed: float = 1.0, subsample: bool = True, variant_preset='all', use_combinations: bool = False, batch_size: Size | None = None, n_augment: int | None = 2, sample_type: str = 'random', instance_name: str = None, seed: int = None, device: str | None = 'cpu')[source]

Sample one instance from instance space.

Parameters:

  • num_agents (int) – Total number of agents. Defaults to 2.

  • num_nodes (int) – Total number of nodes. Defaults to 15.

  • min_coords (float) – Minimum number of coords. Defaults to 0.0.

  • max_coords (float) – Maximum number of coords. Defaults to 1.0.

  • capacity (int) – Vehicles’ capacity. Defaults to None.

  • service_time (float) – Service time. Defaults to 0.2.

  • min_demands (int) – Minimum number of demands. Defaults to 1.

  • max_demands (int) – Maximum number of demands. Defaults to 10.

  • min_backhaul (int) – Minimum number of backhauls. Defaults to 1.

  • max_backhaul (int) – Maximum number of backhauls. Defaults to 10.

  • max_time (float) – Maximum route time. Defaults to 4.6.

  • backhaul_ratio (float) – Ratio of backhaul demands. Defaults to 0.2.

  • backhaul_class (int) – Class of backhaul problem. If 1, it’s unmixed, if 2, it’s mixed. Defaults to 1.

  • sample_backhaul_class (bool) – If backhaul class is sampled across batches. Defaults to False.

  • max_distance_limit (float) – Route distance limits. Defaults to 2.8.

  • speed (float) – Vehicles’ speed. Defaults to 1.0.

  • subsample (bool) – If problem variants are to be sampled. Defaults to True.

  • variant_preset (str) – Variant preset to be sampled. Defaults to “all”.

  • use_combinations (bool) – It considers combinations for which sampling mask the instance is defined. Defaults to False.

  • batch_size (torch.Size, optional) – Batch size. Defaults to None.

  • n_augment (int) – Number of augmentations. Defaults to 2.

  • sample_type (str) – Sample type. It can be “random”, “augment” or “saved”. Defaults to “random”.

  • instance_name (str) – Instance file path. Defaults to None.

  • seed (int) – Random number generator seed. Defaults to None.

  • device (str, optional) – Type of processing. It can be “cpu” or “gpu”. Defaults to “cpu”.

Returns:

Instance data.

Return type:

TensorDict

sample_name_from_set(seed: int = None) → str[source]

Sample one instance from instance set.

Parameters:

seed (int) – Random number generator seed. Defaults to None.

Returns:

Instance name.

Return type:

str

subsample_variant(prob_open_routes: float = 0.5, prob_time_windows: float = 0.5, prob_limit: float = 0.5, prob_backhaul: float = 0.5, td: TensorDict = None, variant_preset=None) → Tensor[source]

Subsample variant. If variant_preset is specified, it loads that variant. Otherwise it samples variant’s parameters across batches based on probabilities.

Parameters:

  • prob_open_routes (float) – Probability of open routes. Defaults to 0.5.

  • prob_time_windows (float) – Probability of time windows. Defaults to 0.5.

  • prob_limit (float) – Probability of distance limits. Defaults to 0.5.

  • prob_backhaul (float) – Probability of backhaul. Defaults to 0.5.

  • td (TensorDict) – Environment instance tensor. Defaults to None.

  • variant_preset (TensorDict) – Variant preset. Defaults to None.

Returns:

Environment instance tensor.

Return type:

td(TensorDict)

References

[Li21]

Li, Z. Yan, C. Wu, “Learning to delegate for large-scale vehicle routing”, Thirty-Fifth Conference on Neural Information Processing Systems, 2021;