random-insertion
random-insertion is a Python library for performing fast random insertion on TSP (Travelling Salesman Problem) and SHPP (Shortest Hamiltonian Path Problem) instances, originally a part of the GLOP* codebase.
* Ye, H., Wang, J., Liang, H., Cao, Z., Li, Y., & Li, F. (2024). GLOP: Learning Global Partition and Local Construction for Solving Large-Scale Routing Problems in Real-Time. Proceedings of the AAAI Conference on Artificial Intelligence, 38(18), 20284-20292. https://doi.org/10.1609/aaai.v38i18.30009
Installation
Supported environments
- python >= 3.7
- numpy >= 1.21
- Linux and Windows
Install from PyPI
$ pip install random-insertion
Build from source
$ git clone https://github.com/Furffico/random-insertion.git
$ cd random-insertion
$ pip install . # add `-e` for development mode
Usages
For performing random insertion on multiple TSP instances in parallel:
import numpy as np
import random_insertion as insertion
problem_scale = 50
num_instances = 10
coordinates = np.random.randn(num_instances, problem_scale, 2)
routes = insertion.tsp_random_insertion_parallel(coordinates, threads=4)
for route in routes:
print(*route)
Despite the name, the program itself is deterministic in nature. Given the same instances and insertion orders, the program will output identical routes. If you would like to add stochasticity to the outputs, please provide shuffled insertion orders like this:
...
coordinates = np.random.randn(1, problem_scale, 2).repeat(num_instances, 0)
orders = np.arange(problem_scale, dtype=np.uint32).reshape(1, -1).repeat(num_instances, 0)
for i in range(num_instances):
np.random.shuffle(orders[i])
routes = insertion.tsp_random_insertion_parallel(coordinates, orders)
Available methods
# Recommended (threads=0 to automatically determine suitable values):
routes = tsp_random_insertion_parallel(coords, orders, threads=0)
routes = shpp_random_insertion_parallel(coords, orders, threads=0)
routes = atsp_random_insertion_parallel(distances, orders, threads=0)
routes = ashpp_random_insertion_parallel(distances, orders, threads=0)
routes = cvrp_random_insertion_parallel(coords, depot_coords, demands, capacity, order, threads=0)
# For backward compatibility with GLOP:
route, cost = tsp_random_insertion(coords, order)
route, cost = atsp_random_insertion(distances, order)
route = cvrp_random_insertion(coords, depot_pos, demands, capacity, order)
route = cvrplib_random_insertion(coords, demands, capacity, order)
Running tests
$ git clone https://github.com/Furffico/random-insertion.git
$ cd random-insertion
$ pip install -e . pytest
$ pytest # run tests
1 maintainer
Metadata
1 maintainer
Release files for random-insertion 0.3.0.post1
For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.
Source distribution (sdist)
| File | Size | Uploaded | |
|---|---|---|---|
| random_insertion-0.3.0.post1.tar.gz | 17.6 kB | Details |
Built distributions (wheels)
Total release size: 1.6 MB
Release files / random_insertion-0.3.0.post1.tar.gz
| Download URL | random_insertion-0.3.0.post1.tar.gz |
|---|---|
| Size | 17.6 kB |
| Tags | Source |
|
SHA-256 checksum How to use checksums |
275f05a97df6bbfdb6d39bf41314257c9b1d227b4f0271b8276c155d996f3b0d
|
|
BLAKE2b-256 checksum How to use checksums |
6161147bbacfccdf242a0e4e9d5f865fee375f6582856c71a060dc8b579366fe
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/6.1.0 CPython/3.12.9
|
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.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Apr 24, 2025.
Transparency logRelease files / random_insertion-0.3.0.post1-cp313-cp313-win_amd64.whl
| Download URL | random_insertion-0.3.0.post1-cp313-cp313-win_amd64.whl |
|---|---|
| Size | 23.7 kB |
| Tags | CPython 3.13 Windows x86-64 |
|
SHA-256 checksum How to use checksums |
aa342ef0a0153efa8c2b1a89420a66af8254da554749842878547e8ceff23072
|
|
BLAKE2b-256 checksum How to use checksums |
308744c8f83779b7f0e80a358e573fe6bb366b02acab582db636e5461db71640
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/6.1.0 CPython/3.12.9
|
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.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Apr 24, 2025.
Transparency logRelease files / random_insertion-0.3.0.post1-cp313-cp313-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
| Download URL | random_insertion-0.3.0.post1-cp313-cp313-manylinux_2_17_x86_64.manylinux2014_x86_64.whl |
|---|---|
| Size | 208.4 kB |
| Tags | CPython 3.13 Linux glibc 2.17+ x86-64 |
|
SHA-256 checksum How to use checksums |
d39c203016519d0795f4f8d1ac3f98179e7efbf6d163c01ddbedbb40ede18d1e
|
|
BLAKE2b-256 checksum How to use checksums |
07c09f7f05ec8dd2b3a3b15897170880a426dc3b293118d274420816617ac67a
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/6.1.0 CPython/3.12.9
|
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.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Apr 24, 2025.
Transparency logRelease files / random_insertion-0.3.0.post1-cp312-cp312-win_amd64.whl
| Download URL | random_insertion-0.3.0.post1-cp312-cp312-win_amd64.whl |
|---|---|
| Size | 23.7 kB |
| Tags | CPython 3.12 Windows x86-64 |
|
SHA-256 checksum How to use checksums |
537206a2c37d556fc5f3ee63f33656b6cb481e6f5e88784a02c3465c22bbd975
|
|
BLAKE2b-256 checksum How to use checksums |
8026332022408eb624297115e0f85d17cc40e8325b22daac2925786940f94c87
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/6.1.0 CPython/3.12.9
|
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.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Apr 24, 2025.
Transparency logRelease files / random_insertion-0.3.0.post1-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
| Download URL | random_insertion-0.3.0.post1-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl |
|---|---|
| Size | 208.6 kB |
| Tags | CPython 3.12 Linux glibc 2.17+ x86-64 |
|
SHA-256 checksum How to use checksums |
1748f3d23f5ed094f66c4a4182bc2fba46f7853a1a41854c8b82a1b14390550b
|
|
BLAKE2b-256 checksum How to use checksums |
ce434406de2b5271860d34773a128f4ce239556658d2261f12c75e9cf928e830
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/6.1.0 CPython/3.12.9
|
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.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Apr 24, 2025.
Transparency logRelease files / random_insertion-0.3.0.post1-cp311-cp311-win_amd64.whl
| Download URL | random_insertion-0.3.0.post1-cp311-cp311-win_amd64.whl |
|---|---|
| Size | 23.7 kB |
| Tags | CPython 3.11 Windows x86-64 |
|
SHA-256 checksum How to use checksums |
1f006ade3ff89eda5fdfa3016ad9fc3400947e88560af11d2119694f163ba293
|
|
BLAKE2b-256 checksum How to use checksums |
9fec4b47d9af0c97aafb0a863e2a92ca3fb89413f076c50823707b31a28bb0ea
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/6.1.0 CPython/3.12.9
|
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.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Apr 24, 2025.
Transparency logRelease files / random_insertion-0.3.0.post1-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
| Download URL | random_insertion-0.3.0.post1-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl |
|---|---|
| Size | 208.3 kB |
| Tags | CPython 3.11 Linux glibc 2.17+ x86-64 |
|
SHA-256 checksum How to use checksums |
b218da8f7ac17b1fbd3c9df7891bd688abb1073c9e45ddd6c21838fbf10d4805
|
|
BLAKE2b-256 checksum How to use checksums |
03192db3cbba00f1a8b0f819c9a8afb94b085b03970000e328f5ff9394692255
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/6.1.0 CPython/3.12.9
|
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.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Apr 24, 2025.
Transparency logRelease files / random_insertion-0.3.0.post1-cp310-cp310-win_amd64.whl
| Download URL | random_insertion-0.3.0.post1-cp310-cp310-win_amd64.whl |
|---|---|
| Size | 23.7 kB |
| Tags | CPython 3.10 Windows x86-64 |
|
SHA-256 checksum How to use checksums |
ab4fefd825fc275f56c68aeceab01cf2a3ae95cd5ba96809198a916080988fe9
|
|
BLAKE2b-256 checksum How to use checksums |
3634315190aebeb94f5fd20ed44d4d67ae97367217ae77fe3aa88d715c5420ff
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/6.1.0 CPython/3.12.9
|
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.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Apr 24, 2025.
Transparency logRelease files / random_insertion-0.3.0.post1-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
| Download URL | random_insertion-0.3.0.post1-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl |
|---|---|
| Size | 208.2 kB |
| Tags | CPython 3.10 Linux glibc 2.17+ x86-64 |
|
SHA-256 checksum How to use checksums |
c7d7ea3b2292eefe37dbc4296b7da0b14b6d539afd8af11ceceab22abaa9fa7d
|
|
BLAKE2b-256 checksum How to use checksums |
566e223bfc9ba75d87f6207b32db84b7b2689dd040ba23042d5d3a703eee602b
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/6.1.0 CPython/3.12.9
|
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.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Apr 24, 2025.
Transparency logRelease files / random_insertion-0.3.0.post1-cp39-cp39-win_amd64.whl
| Download URL | random_insertion-0.3.0.post1-cp39-cp39-win_amd64.whl |
|---|---|
| Size | 23.8 kB |
| Tags | CPython 3.9 Windows x86-64 |
|
SHA-256 checksum How to use checksums |
d30c32ce862cf0cd544f6284cc01aeaae7eb0f9488b20b564c517f8babe2bce7
|
|
BLAKE2b-256 checksum How to use checksums |
29889fcd801df09d9872a72afce3f72bdcfb2d8f2bb295299da8e29039cc5b44
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/6.1.0 CPython/3.12.9
|
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.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Apr 24, 2025.
Transparency logRelease files / random_insertion-0.3.0.post1-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
| Download URL | random_insertion-0.3.0.post1-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl |
|---|---|
| Size | 208.4 kB |
| Tags | CPython 3.9 Linux glibc 2.17+ x86-64 |
|
SHA-256 checksum How to use checksums |
ce57e1735d24dc93fb45c4d4610fee503db359954fd78f12d812d32d8a8ebdb1
|
|
BLAKE2b-256 checksum How to use checksums |
b07220b3e4b151c6ae63e19d9fc54b07ce90ba852c637c93362be18453f666bd
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/6.1.0 CPython/3.12.9
|
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.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Apr 24, 2025.
Transparency logRelease files / random_insertion-0.3.0.post1-cp38-cp38-win_amd64.whl
| Download URL | random_insertion-0.3.0.post1-cp38-cp38-win_amd64.whl |
|---|---|
| Size | 23.6 kB |
| Tags | CPython 3.8 Windows x86-64 |
|
SHA-256 checksum How to use checksums |
cca8f963bbfe21a5966dcc039737a5e56b66799a7be8683ec58fc71ab56ecd84
|
|
BLAKE2b-256 checksum How to use checksums |
2d557d2ffcc31fc6ff36ddde2b46e38594a6a1e29f9492a25abb928dfd70ba0a
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/6.1.0 CPython/3.12.9
|
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.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Apr 24, 2025.
Transparency logRelease files / random_insertion-0.3.0.post1-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
| Download URL | random_insertion-0.3.0.post1-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl |
|---|---|
| Size | 208.9 kB |
| Tags | CPython 3.8 Linux glibc 2.17+ x86-64 |
|
SHA-256 checksum How to use checksums |
1e53b50cc131070b16d1df7a2540b41dca04c93db5b6ad9aad32b961b90d40c1
|
|
BLAKE2b-256 checksum How to use checksums |
e2f89f5968b55b2a042a524edd3e693772360e1bb2325e78636d82a743207b91
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/6.1.0 CPython/3.12.9
|
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.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Apr 24, 2025.
Transparency logRelease files / random_insertion-0.3.0.post1-cp37-cp37m-win_amd64.whl
| Download URL | random_insertion-0.3.0.post1-cp37-cp37m-win_amd64.whl |
|---|---|
| Size | 23.1 kB |
| Tags | CPython 3.7 CPython 3.7 pymalloc Windows x86-64 |
|
SHA-256 checksum How to use checksums |
9fb4460c6010cd3cd3bec0e3ce05059b13fbe9551b837aaa095a35ad747eea52
|
|
BLAKE2b-256 checksum How to use checksums |
c1bb098619b158bcd00f1de39dbebcd1e299120fa03f8cce06f33b365362ef2d
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/6.1.0 CPython/3.12.9
|
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.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Apr 24, 2025.
Transparency logRelease files / random_insertion-0.3.0.post1-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
| Download URL | random_insertion-0.3.0.post1-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl |
|---|---|
| Size | 208.0 kB |
| Tags | CPython 3.7 CPython 3.7 pymalloc Linux glibc 2.17+ x86-64 |
|
SHA-256 checksum How to use checksums |
619cf76e9629f88c386df42caf100247595b2e8fd98d585da9e867fc92bfb491
|
|
BLAKE2b-256 checksum How to use checksums |
f1a880bf4ce9fa1e35f141e1bef4d70c0d4882ebc5b2aed019f9caa42c84d158
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/6.1.0 CPython/3.12.9
|
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.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Apr 24, 2025.
Transparency log
