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

CVRPSTW 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 = 20, num_nodes: int = 100, capacity: int = 50, service_times: int = 0.2, batch_size: Size | None = None, n_augment: int = 2, seed: int = None, device: str | None = 'cpu') → TensorDict[source]

Generate augmentated instance.

Parameters:

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

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

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

  • service_times (int) – Service time in the nodes. Defaults to 0.2.

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

get_time_windows(instance: TensorDict = None, batch_size: Size = None, seed: int = None) → tensor[source]

Get time windows to reach the nodes.

Parameters:

  • instance (TensorDict) – Data instance. Defaults to None.

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

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

Returns:

Nodes time windows.

Return type:

torch.Tensor

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 = 20, num_nodes: int = 100, capacity: int = 50, service_times: int = 0.2, 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 20.

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

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

  • service_times (int) – Total time of service. Defaults to 0.2.

  • batch_size (torch.Size, optional) – 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, capacity=50, service_times=0.2, 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.

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

  • service_times (int) – Service time in the nodes. Defaults to 0.2.

  • 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;