Skip to main content

VRPLIB

PyPI version vrplib codecov

vrplib is a Python package for working with Vehicle Routing Problem (VRP) instances. The main features are:

  • reading VRPLIB and Solomon instances and solutions, and
  • writing VRPLIB-style instances and solutions.

Outline

Installation

vrplib works with Python 3.9+ and only depends on numpy. It may be installed in the usual way as

pip install vrplib

Example usage

Reading files

import vrplib

# Read VRPLIB formatted instances (default)
instance = vrplib.read_instance("/path/to/X-n101-k25.vrp")
solution = vrplib.read_solution("/path/to/X-n101-k25.sol")

# Read Solomon formatted instances
instance = vrplib.read_instance("/path/to/C101.txt", instance_format="solomon")
solution = vrplib.read_solution("/path/to/C101.sol") # only 1 solution format

instance and solution are dictionaries that contain all parsed data.

>>> instance.keys()
dict_keys(['name', ..., 'edge_weight'])

>>> solution.keys()
dict_keys(['routes', 'cost'])

Writing files

The functions write_instance and write_solution provide a simple interface to writing instances and solutions in VRPLIB-style:

  • write_instance adds indices to data sections when necessary (EDGE_WEIGHT_SECTION and DEPOT_SECTION are excluded).
  • write_solution adds the Route #{idx} prefix to routes.

Note that these functions do not validate instances: it is up to the user to write correct VRPLIB-style files.

Instances

import vrplib

instance_loc = "instance.vrp"
instance_data = {
    "NAME": "instance",
    "TYPE": "CVRP",
    "VEHICLES": 2,
    "DIMENSION": 1,
    "CAPACITY": 1,
    "EDGE_WEIGHT_TYPE": "EUC_2D",
    "NODE_COORD_SECTION": [[250, 250], [500, 500]],
    "DEMAND_SECTION": [1, 1],
    "DEPOT_SECTION": [1],
}

vrplib.write_instance(instance_loc, instance_data)
NAME: instance
TYPE: CVRP
VEHICLES: 2
DIMENSION: 1
CAPACITY: 1
EDGE_WEIGHT_TYPE: EUC_2D
NODE_COORD_SECTION
1	250	250
2	500	500
DEMAND_SECTION
1	1
2	1
DEPOT_SECTION
1
EOF

Solutions

import vrplib

solution_loc = "solution.sol"
routes = [[1], [2, 3], [4, 5, 6]]
solution_data = {"Cost": 42, "Vehicle types": [1, 2, 3]}

vrplib.write_solution(solution_loc, routes, solution_data)
Route #1: 1
Route #2: 2 3
Route #3: 4 5 6
Cost: 42
Vehicle types: [1, 2, 3]

Downloading from CVRPLIB

[!WARNING]
This functionality is deprecated and will be removed in the next major version.

import vrplib

# Download an instance and a solution file 
vrplib.download_instance("X-n101-k25", "/path/to/instances/")
vrplib.download_solution("X-n101-k25", "/path/to/solutions/")

# List all instance names that can be downloaded 
vrplib.list_names()                      # All instance names
vrplib.list_names(low=100, high=200)     # Instances with between [100, 200] customers
vrplib.list_names(vrp_type="cvrp")       # Only CVRP instances
vrplib.list_names(vrp_type="vrptw")      # Only VRPTW instances

Documentation

VRPLIB instance format

The VRPLIB format is the standard format for the Capacitated Vehicle Routing Problem (CVRP). An example VRPLIB instance looks as follows:

NAME: Example 
EDGE_WEIGHT_TYPE: EUC_2D
NODE_COORD_SECTION
1 0 0
2 5 5
SERVICE_TIME_SECTION
1 0
2 3
DEPOT_SECTION
1
EOF

A VRPLIB instance contains problem specifications and problem data.

  • Specifications are key-value pairs separated by a colon. In the example above, NAME and EDGE_WEIGHT_TYPE are the two data specifications.
  • Data are explicit array-like values such as customer coordinates or service times. Each data section should start with a header name that ends with _SECTION, e.g., NODE_COORD_SECTION and SERVICE_TIME_SECTION. It is then followed by rows of values and each row must start with an index representing the depot or customer. There are two exceptions: values in EDGE_WEIGHT_SECTION and DEPOT_SECTION should not start with an index.

Besides the rules outlined above, vrplib is not strict about the naming of specifications or sections. This means that you can use vrplib to read VRPLIB instances with custom specifications like MY_SPECIFICATION: SOME_VALUE and custom section names like MY_SECTION.

Reading the above example instance returns the following dictionary:

{'name': 'Example',
 'edge_weight_type': 'EUC_2D',
 'node_coord': array([[0, 0], [5, 5]]),
 'service_time': array([1, 3]),
 'depot': array([0]),
 'edge_weight': array([[0.  , 7.07106781], [7.07106781, 0.  ]])}

The depot section specifies which location index corresponds to the depot data. The convention is to let index 1 represent the depot. vrplib subtracts one from the depot value to make it easier to index.

Computing edge weights

Note that the example instance did not include any explicit information about the edge weights, yet the output includes edge weights data. This is because vrplib automatically computes the edge weights based on the instance specifications, if applicable. In the example, the edge weight type specification and node coordinates data are used to compute the Euclidean distance. You can set the compute_distances argument in read_instance to disable this feature.

Following the VRPLIB conventions, the edge weights are computed based on the EDGE_WEIGHT_TYPE specification, and in some cases the EDGE_WEIGHT_FORMAT specification. vrplib currently supports two categories of edge weight types:

  • *_2D: Euclidean distances based on the node coordinates data.
    • EUC_2D: Double precision distances without rounding.
    • FLOOR_2D: Round down all distances to down to an integer.
    • EXACT_2D: Multiply the distances by 1000, round to the nearest integer.
  • EXPLICIT: the distance data is explicitly provided, in partial or full form. The EDGE_WEIGHT_FORMAT specification must be present. We support the following two edge weight formats:
    • LOWER_ROW: Lower row triangular matrix without diagonal entries.
    • FULL_MATRIX: Explicit full matrix representation.

Line comments

Lines starting with # are interpreted as comments and not parsed when reading the instance.

More information about VRPLIB

The VRPLIB format is an extension of the TSPLIB95 format. Additional information about the VRPLIB format can be found here.

Solomon instance format

The Solomon format was used to introduce the Solomon instances for the Vehicle Routing Problem with Time Window (VRPTW) and also the extended instance set by Homberger and Gehring. A Solomon instance looks like this:

Example

VEHICLE
NUMBER     CAPACITY
  50          200

CUSTOMER
CUST NO.  XCOORD.    YCOORD.    DEMAND   READY TIME  DUE DATE   SERVICE TIME
    0      70         70          0          0       1351          0
    1      33         78         20        750        809         90

Reading this Solomon instance returns the following dictionary:

{'name': 'Example',
 'vehicles': 50,
 'capacity': 200,
 'node_coord': array([[70, 70], [33, 78]]),
 'demand': array([ 0, 20]),
 'time_window': array([[ 0, 1351], [ 750,  809]]),
 'service_time': array([ 0, 90]),
 'edge_weight': array([[ 0.  , 37.85498646], [37.85498646,  0.  ]])}

The edge weights are computed by default using the Euclidean distances.

Solution format

Here's an example of a solution format:

Route #1: 1 2 3
Route #2: 4 5
Cost: 100

A solution is represented by a set of routes, where each route specifies the sequence of customers to visit. Each route should start with "Route", followed by the route number, and followed by a colon. The customers to be served on the route are then listed. The solution file can also include other keywords like Cost, which will be separated on the first colon or whitespace.

The convention is that customer indices start counting from 1, but vrplib simply parses the file without strict requirements about those indices.

Reading the above example solution returns the following dictionary:

{'routes': [[1, 2, 3], [4, 5]], 'cost': 100}

Other remarks

  • The XML100 benchmark set is not listed in list_names and cannot be downloaded through this package. You can download these instances directly from CVRPLIB.
  • In the literature, some instances use rounding conventions different from what is specified in the instance. For example, X instance set proposed by Uchoa et al. (2017) assumes that the distances are rounded to the nearest integer. When you use the vrplib package to read this instance, it will return non-rounded Euclidean distances because the instance specifies the EUC_2D edge weight type which implies no rounding. To adhere to the convention used in the literature, you can manually round the distances matrix.
  • For large instances (>5000 customers) it's recommended to set the compute_edge_weights argument to False in read_instance.

Metadata

Release files for vrplib 1.5.1

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for vrplib 1.5.1
File Size Uploaded Provenance Actions
vrplib-1.5.1.tar.gz 23.0 kB Without provenance Details for vrplib-1.5.1.tar.gz

Built distribution (wheel)

Table of built distributions (wheels) for vrplib 1.5.1
File Interpreter ABI Platform Actions
vrplib-1.5.1-py3-none-any.whl Python 3 none any Details for vrplib-1.5.1-py3-none-any.whl

Total release size: 47.9 kB

Release files / vrplib-1.5.1.tar.gz

Download URL vrplib-1.5.1.tar.gz
Size 23.0 kB
Tags Source
SHA-256 checksum
How to use checksums
e10de1fad330c0b583e5130ce20032b1ac2c1ae1fcbcf868de9f553ae85d8c4d
BLAKE2b-256 checksum
How to use checksums
d0d106e54df3f144edea3c34c99bb6261692cb3f15c39186b086857703c47f5c
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via poetry/1.8.3 CPython/3.9.20 Linux/6.8.0-1015-azure

Release files / vrplib-1.5.1-py3-none-any.whl

Download URL vrplib-1.5.1-py3-none-any.whl
Size 24.9 kB
Tags Python 3
SHA-256 checksum
How to use checksums
5da270e40753ec64fbaef9adf423722bb3c41c4e63d0fa53e4d8ed7e25facd41
BLAKE2b-256 checksum
How to use checksums
d31b74f5996ef71871c3a36876842e45f115cb48ca34f720f6634030cf34769e
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via poetry/1.8.3 CPython/3.9.20 Linux/6.8.0-1015-azure

Security for vrplib 1.5.1

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

No provenance found

None of the files in this release were uploaded with provenance metadata.

A note on package security

PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.

To learn more about protecting yourself from malicious actors, visit our package security documentation.

Release history Release notifications | RSS feed

This release

1.5.1 This release

2 release files No provenance

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page