Data

Tools

Indexes

Applications

Experiments

Open Source Science

lkh

A super simple Python wrapper for the constrained traveling salesman and vehicle routing problem solver LKH-3.

https://github.com/ben-hudson/pylkh

Science Score: 44.0%

This score indicates how likely this project is to be science-related based on various indicators:

  • ✓
    CITATION.cff file
    Found CITATION.cff file
  • ✓
    codemeta.json file
    Found codemeta.json file
  • ✓
    .zenodo.json file
    Found .zenodo.json file
  • ○
    DOI references
  • ○
    Academic publication links
  • ○
    Committers with academic emails
  • ○
    Institutional organization owner
  • ○
    JOSS paper metadata
  • ○
    Scientific vocabulary similarity
    Low similarity (10.1%) to scientific vocabulary

Keywords

python tsp tsp-problem tsp-solver vrp vrp-solver
Last synced: 6 months ago · JSON representation ·

Repository

A super simple Python wrapper for the constrained traveling salesman and vehicle routing problem solver LKH-3.

Basic Info
Statistics
  • Stars: 39
  • Watchers: 1
  • Forks: 8
  • Open Issues: 0
  • Releases: 0
Topics
python tsp tsp-problem tsp-solver vrp vrp-solver
Created about 5 years ago · Last pushed 11 months ago
Metadata Files
Readme License Citation

README.md

PyLKH

This is a super simple Python wrapper for the constrained traveling salesman and vehicle routing problem solver called LKH-3.

If you want to use this wrapper, you need to install LKH-3 first. For example, on Ubuntu: wget http://akira.ruc.dk/~keld/research/LKH-3/LKH-3.0.6.tgz tar xvfz LKH-3.0.6.tgz cd LKH-3.0.6 make sudo cp LKH /usr/local/bin

LKH-3 expects problems in the TSPLIB format. It extends the format to support VRPs.

Using PyLKH you can solve problems represented as Python objects or files.

CAUTION: distances are represented by integer values in the TSPLIB format. This can produce unexpected behaviour for some problems, like those with all nodes within the unit square. You can use the EXACT_2D distance to avoid rounding issues.

Install

pip install lkh

Example

``` import requests import lkh

problemstr = requests.get('http://vrp.atd-lab.inf.puc-rio.br/media/comvrp/instances/A/A-n32-k5.vrp').text problem = lkh.LKHProblem.parse(problem_str)

solverpath = '../LKH-3.0.6/LKH' lkh.solve(solverpath, problem=problem, maxtrials=10000, runs=10) ``` Output (values correspond to nodes, which are 1-indexed, _not node indicies, which are 0-indexed): [[27, 8, 14, 18, 20, 32, 22], [25, 28], [15, 29, 12, 5, 24, 4, 3, 7], [30, 19, 9, 10, 23, 16, 11, 26, 6, 21], [13, 2, 17, 31]]

API

lkh.solve(solver='LKH', problem=None, problem_file=None, **kwargs)

Solve a problem instance.

Parameters

  • solver (optional): Path to LKH-3 executable. Defaults to LKH.

  • problem (optional): Problem object. LKHProblem is preferred but tsplib95.models.StandardProblem also works. problem or problem_file is required.

  • problem_file (optional): Path to TSPLIB-formatted problem. problem or problem_file is required.

  • kwargs (optional): Any LKH-3 parameter described here (pg. 5-7) or here (pg. 6-8). Lowercase works. For example: runs=10.

Returns

routes: List of lists of nodes (nodes, not node indicies).

class lkh.LKHProblem

A problem that can be solved by LKH-3. Fields are (partially) described here (pg. 4-6). Inherits from tsplib95.models.StandardProblem.

The available specification fields are: * CAPACITY * COMMENT * DEMAND_DIMENSION * DIMENSION * DISPLAY_DATA_TYPE * DISTANCE * EDGE_DATA_FORMAT * EDGE_WEIGHT_FORMAT * EDGE_WEIGHT_TYPE * NAME * NODE_COORD_TYPE * RISK_THRESHOLD * SALESMEN * SCALE * SERVICE_TIME * TYPE * VEHICLES

The available data fields are: * BACKHAUL_SECTION * CTSP_SET_SECTION * DEMAND_SECTION * DEPOT_SECTION * DISPLAY_DATA_SECTION * DRAFT_LIMIT_SECTION * EDGE_DATA_SECTION * EDGE_WEIGHT_SECTION * FIXED_EDGES_SECTION * NODE_COORD_SECTION * PICKUP_AND_DELIVERY_SECTION * REQUIRED_NODES_SECTION * SERVICE_TIME_SECTION * TIME_WINDOW_SECTION

You probably want to initialize a problem instance using one of the following class methods:

#### classmethod load(filepath, **options)

Load a problem instance from a text file.

Inherited from tsplib95.problems.Problem.load.

#### classmethod parse(text, **options)

Parse text into a problem instance.

Inherited from tsplib95.problems.Problem.parse.

#### classmethod read(fp, **options)

Read a problem instance from a file-like object.

Inherited from tsplib95.problems.Problem.read.

## Citation If you use PyLKH in your research, please cite it. You can generate an APA or BibTeX citation by clicking "Cite this repository" in the About section. Read more about citation files on GitHub here.

Owner

  • Name: Ben Hudson
  • Login: ben-hudson
  • Kind: user
  • Location: Montreal

All of my models are wrong, some are useful

Citation (CITATION.cff) 

# This CITATION.cff file was generated with cffinit.
# Visit https://bit.ly/cffinit to generate yours today!

cff-version: 1.2.0
title: PyLKH
message: >-
  If you use this software, please cite it using the
  metadata from this file.
type: software
authors:
  - given-names: Benjamin
    family-names: Hudson
repository-code: 'https://github.com/ben-hudson/pylkh'
url: 'https://pypi.org/project/lkh'
abstract: >-
  A super simple Python wrapper for the constrained
  traveling salesman and vehicle routing problem solver
  LKH-3.
keywords:
  - python
  - vrp
  - tsp
  - tsp-solver
  - vrp-solver

GitHub Events

Total
  • Issues event: 1
  • Watch event: 5
  • Issue comment event: 2
  • Push event: 1
  • Pull request event: 1
  • Pull request review event: 1
  • Fork event: 1
Last Year
  • Issues event: 1
  • Watch event: 5
  • Issue comment event: 2
  • Push event: 1
  • Pull request event: 1
  • Pull request review event: 1
  • Fork event: 1

Committers

Last synced: almost 3 years ago

All Time
  • Total Commits: 22
  • Total Committers: 2
  • Avg Commits per committer: 11.0
  • Development Distribution Score (DDS): 0.045
Top Committers
Name Email Commits
Ben Hudson b****n@h****m 21
Christian 3****l@u****m 1
Committer Domains (Top 20 + Academic)
hudsonsathome.com: 1

Issues and Pull Requests

Last synced: 7 months ago

All Time
  • Total issues: 6
  • Total pull requests: 2
  • Average time to close issues: 3 months
  • Average time to close pull requests: 5 months
  • Total issue authors: 6
  • Total pull request authors: 2
  • Average comments per issue: 2.17
  • Average comments per pull request: 0.0
  • Merged pull requests: 2
  • Bot issues: 0
  • Bot pull requests: 0
Past Year
  • Issues: 1
  • Pull requests: 0
  • Average time to close issues: N/A
  • Average time to close pull requests: N/A
  • Issue authors: 1
  • Pull request authors: 0
  • Average comments per issue: 2.0
  • Average comments per pull request: 0
  • Merged pull requests: 0
  • Bot issues: 0
  • Bot pull requests: 0
View more stats
Top Authors
Issue Authors
  • beatriz1215 (1)
  • elimkyl (1)
  • silent790 (1)
  • RachaBen (1)
  • navidaftabi (1)
Pull Request Authors
  • elimkyl (1)
  • christianll9 (1)
  • ben-hudson (1)
Top Labels
Issue Labels
Pull Request Labels

Packages

  • Total packages: 1
  • Total downloads:
    • pypi 237 last-month
  • Total dependent packages: 1
  • Total dependent repositories: 2
  • Total versions: 8
  • Total maintainers: 1
pypi.org: lkh

Super simple Python wrapper for LKH-3

  • Versions: 8
  • Dependent Packages: 1
  • Dependent Repositories: 2
  • Downloads: 237 Last month
Rankings
Dependent packages count: 7.5%
Dependent repos count: 12.0%
Average: 13.3%
Forks count: 13.4%
Stargazers count: 13.7%
Downloads: 19.8%
Maintainers (1)
ben-hudson
Last synced: 6 months ago

Dependencies

Pipfile pypi
  • ipython * develop
  • poetry * develop
  • pytest * develop
  • pytest-xdist * develop
  • twine * develop
  • lkh *
pyproject.toml pypi
  • pytest ^7.4.2 develop
  • pytest-xdist ^3.3.1 develop
  • twine ^4.0.2 develop
  • Click ^6.0
  • Deprecated ~1.2.9
  • networkx ^2.1
  • python ^3.3
  • tabulate ~0.8.7