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.dvrptw.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]

DVRPTW 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 = 25, num_nodes: int = 100, capacity: int = 200, min_cust_count: int | None = None, cust_loc_range: tuple = (0, 101), cust_dem_range: tuple = (5, 41), horizon: int = 480, service_times_range: tuple = (10, 31), tw_ratio: float = 0.5, cust_tw_range: tuple = (30, 91), dod: float = 0.5, d_early_ratio: float = 0.5, batch_size: Size | None = None, n_augment: int = 2, seed: int = None, device: str | None = 'cpu') → TensorDict[source]

Generate augmentated instance.

Args: :Parameters: * num_agents (int) – Total number of agents. Defaults to 25.

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

  • capacity (int) – Total capacity for each agent. Defaults to 200.

  • min_cust_count (Optional[int]) – Minimum customer count. Defaults to None.

  • cust_loc_range (tuple) – Range for customer locations. Defaults to (0, 101).

  • cust_dem_range (tuple) – Range for customer demands. Defaults to (5, 41).

  • horizon (int) – Planning horizon. Defaults to 480.

  • service_times_range (tuple) – Range for service times. Defaults to (10, 31).

  • tw_ratio (float) – Ratio of nodes with time windows. Defaults to 0.5.

  • cust_tw_range (tuple) – Range for customer time window widths. Defaults to (30, 91).

  • dod (float) – Ratio of dynamic nodes. Defaults to 0.5.

  • d_early_ratio (float) – Ratio of early dynamic nodes. Defaults to 0.5.

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

  • n_augment (int) – Data augmentation. Defaults to 2.

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

Returns:

Instance data.

Return type:

TensorDict

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()[source]

Get list of generated files.

Parameters:

n/a.

Returns:

None.

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 = 25, num_nodes: int = 100, capacity: int = 200, min_cust_count: int | None = None, cust_loc_range: tuple = (0, 101), cust_dem_range: tuple = (5, 41), horizon: int = 480, service_times_range: tuple = (10, 31), tw_ratio: float = 0.5, cust_tw_range: tuple = (30, 91), dod: float = 0.5, d_early_ratio: float = 0.5, batch_size: Size | None = None, seed: int = None, device: str | None = 'cpu') → TensorDict[source]

Generate random instance.

Follows https://gitlab.inria.fr/gbono/mardam/-/blob/master/problems/_data_sdtw.py

Parameters:

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

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

  • capacity (int) – Total capacity for each agent. Defaults to 200.

  • min_cust_count (Optional[int]) – Minimum customer count. Defaults to None.

  • cust_loc_range (tuple) – Range for customer locations. Defaults to (0, 101).

  • cust_dem_range (tuple) – Range for customer demands. Defaults to (5, 41).

  • horizon (int) – Planning horizon. Defaults to 480.

  • service_times_range (tuple) – Range for service times. Defaults to (10, 31).

  • tw_ratio (float) – Ratio of nodes with time windows. Defaults to 0.5.

  • cust_tw_range (tuple) – Range for customer time window widths. Defaults to (30, 91).

  • dod (float) – Ratio of dynamic nodes. Defaults to 0.5.

  • d_early_ratio (float) – Ratio of early dynamic nodes. Defaults to 0.5.

  • batch_size (Optional[torch.Size]) – Batch size. Defaults to None.

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

Returns:

Instance data.

Return type:

TensorDict

read_instance_data(instance_name: str) → Dict[source]

Read instance data from file.

Parameters:

instance_name (str) – instance file name.

Returns:

Instance data.

Return type:

Dict

sample_instance(num_agents=None, num_nodes=None, instance_name: str = None, sample_type: str = 'random', batch_size: Size | None = None, n_augment: int | None = None, seed: int = None, device: str | None = 'cpu') → Dict[source]

Sample one instance from instance space.

Parameters:

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

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

  • instance_name (str) – Instance name. Defaults to None.

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

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

  • n_augment (int, optional) – Data augmentation. Defaults to None.

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

Returns:

Instance data.

Return type:

Dict

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

References

[Li21]

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