VRPSolverEasy
==============================
.. image:: https://github.com/inria-UFF/VRPSolverEasy/actions/workflows/python-package.yml/badge.svg
:target: https://github.com/inria-UFF/VRPSolverEasy/actions/workflows/python-package.yml
VRPSolverEasy is a Python package which provides a **simple interface
for** `VRPSolver <https://vrpsolver.math.u-bordeaux.fr/>`__, which is a
state-of-the-art Branch-Cut-and-Price exact solver for vehicle routing
problems (VRPs). The simplified interface is accessible for **users
without operations research background**, i.e., you do not need to know
how to model your problem as an Integer Programming problem. As a price
to pay for the simplicity, this interface is restricted to some standard
VRP variants, which involve the following features and their
combinations:
* capacitated vehicles,
* customer time windows,
* heterogeneous fleet,
* multiple depots,
* open routes,
* optional customers with penalties,
* parallel links to model transition time/cost trade-off,
* incompatibilities between vehicles and customers,
* customers with alternative locations and/or time windows.
To our knowledge, VRPSolver is the most efficient **exact** solver
available for VRPs. Its particularity is to focus on finding and
improving a **lower bound** on the optimal solution value of your
instance. It is less efficient in finding feasible solutions but still
can be better than available heuristic solvers for non-classic VRP
variants. One can expect to find **provably optimal solutions** for
most instances with up to 100 customers. A significant number of instances
in the range of 101-200 customers may be solved too. A few even larger
instances may be solved, but usually, this requires very long runs.
The performance of VRPSolver improves when very good initial upper bounds,
obtained by an external heuristic solver, are provided.
VRPSolver is based on a research proof-of-concept code prone to issues.
Use it only for research, teaching, testing, and R&D purposes at your
own risk. It is not suited for use in production. Please use Issues
section in this repository to report bugs and issues, and to give
suggestions.
License
-------
The VRPSolverEasy package itself is open-source and free to use. It
includes compiled libraries of
`BaPCod <https://bapcod.math.u-bordeaux.fr/>`__, its VRPSolver
extension, and COIN-OR CLP solver. These libraries are also free to use.
For better performance, it is possible to use VRPSolverEasy together
with CPLEX MIP solver. This combination called *academic version*
requires an access to the source code of BaPCod available with an
`academic-use-only
license <https://bapcod.math.u-bordeaux.fr/#licence>`__. The academic
version of VRPSolverEasy additionally includes a MIP-based (slow)
heuristic which is useful for finding feasible solutions in the absence
of an external heuristic solver.
Accompanying paper
------------------
The paper presents the motivation to create VRPSolverEasy, the interface of
the package, the solution approach (optional to read), the computational
results for the three classic VRP variants (CVRP, VRPTW, HFVRP), and possible
future extensions of the model.
For the moment, the paper is available as a preprint :
\N. Errami, E. Queiroga, R. Sadykov, E. Uchoa. "VRPSolverEasy: a Python
library for the exact solution of a rich vehicle routing problem",
`Technical report HAL-04057985 <https://hal.inria.fr/hal-04057985/document>`__, 2023.
Please cite it if you use VRPSolverEasy in your research.
Installation
------------
.. image:: https://upload.wikimedia.org/wikipedia/commons/c/c3/Python-logo-notext.svg
``VRPSolverEasy`` requires a version of python >= 3.6
.. warning::
Before starting the installation, we invite you to update
your version of pip by running this command: ::
python -m pip install --upgrade pip
There is two different way to install ``VRPSolverEasy`` :
The first way is to install it with ``pip``::
python -m pip install VRPSolverEasy
The second way is to follow these steps:
- Download the package and extract it into a local directory
- Move to this local directory and enter : ::
python pip install .
Installation instructions for Mac computers with Apple ARM processors,
as well as for the academic version, are given in the documentation.
Copy binaries
-------------
Once the package is installed you will need to request the Bapcod distribution here: https://bapcod.math.u-bordeaux.fr/
Once you have downloaded the distribution. You just have to go to the ``VRPSolverEasy`` folder and copy the system folder corresponding to your computer and copy it into the ``lib`` folder of the ``VRPSolverEasy`` python package.
For example if your computer is a Mac you will copy and replace the ``Darwin`` folder, you will then have ``VRPSolverEasy/lib/Darwin``.
Example
-------
A simple example that shows how to use the VRPSolverEasy package:
.. code:: python
import VRPSolverEasy as vrpse
import math
def compute_euclidean_distance(x_i, x_j, y_i, y_j):
"""compute the euclidean distance between 2 points from graph"""
return round(math.sqrt((x_i - x_j)**2 +
(y_i - y_j)**2), 3)
# Data
cost_per_distance = 10
begin_time = 0
end_time = 5000
nb_point = 7
# Map with names and coordinates
coordinates = {"Wisconsin, USA": (44.50, -89.50), # depot
"West Virginia, USA": (39.000000, -80.500000),
"Vermont, USA": (44.000000, -72.699997),
"Texas, the USA": (31.000000, -100.000000),
"South Dakota, the US": (44.500000, -100.000000),
"Rhode Island, the US": (41.742325, -71.742332),
"Oregon, the US": (44.000000, -120.500000)
}
# Demands of points
demands = [0, 500, 300, 600, 658, 741, 436]
# Initialisation
model = vrpse.Model()
# Add vehicle type
model.add_vehicle_type(
id=1,
start_point_id=0,
end_point_id=0,
name="VEH1",
capacity=1100,
max_number=6,
var_cost_dist=cost_per_distance,
tw_end=5000)
# Add depot
model.add_depot(id=0, name="D1", tw_begin=0, tw_end=5000)
coordinates_keys = list(coordinates.keys())
# Add customers
for i in range(1, nb_point):
model.add_customer(
id=i,
name=coordinates_keys[i],
demand=demands[i],
tw_begin=begin_time,
tw_end=end_time)
# Add links
coordinates_values = list(coordinates.values())
for i in range(0, 7):
for j in range(i + 1, 7):
dist = compute_euclidean_distance(coordinates_values[i][0],
coordinates_values[j][0],
coordinates_values[i][1],
coordinates_values[j][1])
model.add_link(
start_point_id=i,
end_point_id=j,
distance=dist,
time=dist)
# solve model
model.solve()
model.export()
if model.solution.is_defined():
print(model.solution)
Documentation
-------------
Documentation, explanation of demos (CVRP, VRPTW, HFVRP, and MDVRP), and
the solver API are accessible here: https://vrpsolvereasy.readthedocs.io/en/latest/.
You can also build the documentation locally by following this
instructions from the source folder : ::
cd docs
python -m pip install -r requirements.txt
cd ..
make html
The HTML pages will be in the folder ``build\html``.
Raw data
{
"_id": null,
"home_page": "https://github.com/inria-UFF/VRPSolverEasy",
"name": "VRPSolverEasy",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.6",
"maintainer_email": "",
"keywords": "['VRP','Branch-Cut-&Price','Operations Research','Optimization','Linear Programming','Routing problems','Solver','Supply chain']",
"author": "\"UCHOA Eduardo SADYKOV Ruslan QUEIROGA Eduardo ERRAMI Najib\"",
"author_email": "\"najib.errami@inria.fr\"",
"download_url": "https://files.pythonhosted.org/packages/2a/92/2be14e8526762dcbe15d8c287c5b133154757fbbb7d3cc969613cafb9a2d/VRPSolverEasy-0.1.4.tar.gz",
"platform": null,
"description": "VRPSolverEasy \n==============================\n.. image:: https://github.com/inria-UFF/VRPSolverEasy/actions/workflows/python-package.yml/badge.svg\n :target: https://github.com/inria-UFF/VRPSolverEasy/actions/workflows/python-package.yml\n\nVRPSolverEasy is a Python package which provides a **simple interface\nfor** `VRPSolver <https://vrpsolver.math.u-bordeaux.fr/>`__, which is a\nstate-of-the-art Branch-Cut-and-Price exact solver for vehicle routing\nproblems (VRPs). The simplified interface is accessible for **users\nwithout operations research background**, i.e., you do not need to know\nhow to model your problem as an Integer Programming problem. As a price\nto pay for the simplicity, this interface is restricted to some standard\nVRP variants, which involve the following features and their\ncombinations:\n\n* capacitated vehicles, \n* customer time windows, \n* heterogeneous fleet,\n* multiple depots,\n* open routes,\n* optional customers with penalties,\n* parallel links to model transition time/cost trade-off,\n* incompatibilities between vehicles and customers,\n* customers with alternative locations and/or time windows.\n\nTo our knowledge, VRPSolver is the most efficient **exact** solver\navailable for VRPs. Its particularity is to focus on finding and\nimproving a **lower bound** on the optimal solution value of your\ninstance. It is less efficient in finding feasible solutions but still\ncan be better than available heuristic solvers for non-classic VRP\nvariants. One can expect to find **provably optimal solutions** for\nmost instances with up to 100 customers. A significant number of instances \nin the range of 101-200 customers may be solved too. A few even larger \ninstances may be solved, but usually, this requires very long runs.\nThe performance of VRPSolver improves when very good initial upper bounds, \nobtained by an external heuristic solver, are provided. \n\nVRPSolver is based on a research proof-of-concept code prone to issues.\nUse it only for research, teaching, testing, and R&D purposes at your\nown risk. It is not suited for use in production. Please use Issues\nsection in this repository to report bugs and issues, and to give\nsuggestions.\n\nLicense\n-------\n\nThe VRPSolverEasy package itself is open-source and free to use. It\nincludes compiled libraries of\n`BaPCod <https://bapcod.math.u-bordeaux.fr/>`__, its VRPSolver\nextension, and COIN-OR CLP solver. These libraries are also free to use.\n\nFor better performance, it is possible to use VRPSolverEasy together\nwith CPLEX MIP solver. This combination called *academic version*\nrequires an access to the source code of BaPCod available with an\n`academic-use-only\nlicense <https://bapcod.math.u-bordeaux.fr/#licence>`__. The academic\nversion of VRPSolverEasy additionally includes a MIP-based (slow)\nheuristic which is useful for finding feasible solutions in the absence\nof an external heuristic solver.\n\nAccompanying paper\n------------------\n\nThe paper presents the motivation to create VRPSolverEasy, the interface of \nthe package, the solution approach (optional to read), the computational \nresults for the three classic VRP variants (CVRP, VRPTW, HFVRP), and possible\nfuture extensions of the model. \nFor the moment, the paper is available as a preprint :\n \n \\N. Errami, E. Queiroga, R. Sadykov, E. Uchoa. \"VRPSolverEasy: a Python \n library for the exact solution of a rich vehicle routing problem\", \n `Technical report HAL-04057985 <https://hal.inria.fr/hal-04057985/document>`__, 2023.\n\nPlease cite it if you use VRPSolverEasy in your research.\n\nInstallation\n------------\n\n.. image:: https://upload.wikimedia.org/wikipedia/commons/c/c3/Python-logo-notext.svg\n\n``VRPSolverEasy`` requires a version of python >= 3.6\n\n.. warning::\n Before starting the installation, we invite you to update \n your version of pip by running this command: ::\n\n python -m pip install --upgrade pip\n\nThere is two different way to install ``VRPSolverEasy`` :\n\nThe first way is to install it with ``pip``::\n\n python -m pip install VRPSolverEasy\n\nThe second way is to follow these steps:\n\n- Download the package and extract it into a local directory\n- Move to this local directory and enter : ::\n\n python pip install .\n\nInstallation instructions for Mac computers with Apple ARM processors,\nas well as for the academic version, are given in the documentation.\n\nCopy binaries\n-------------\n\nOnce the package is installed you will need to request the Bapcod distribution here: https://bapcod.math.u-bordeaux.fr/\nOnce you have downloaded the distribution. You just have to go to the ``VRPSolverEasy`` folder and copy the system folder corresponding to your computer and copy it into the ``lib`` folder of the ``VRPSolverEasy`` python package.\nFor example if your computer is a Mac you will copy and replace the ``Darwin`` folder, you will then have ``VRPSolverEasy/lib/Darwin``.\n\n\nExample\n-------\n\nA simple example that shows how to use the VRPSolverEasy package:\n\n.. code:: python\n\n\n import VRPSolverEasy as vrpse\n import math\n\n def compute_euclidean_distance(x_i, x_j, y_i, y_j):\n \"\"\"compute the euclidean distance between 2 points from graph\"\"\"\n return round(math.sqrt((x_i - x_j)**2 +\n (y_i - y_j)**2), 3)\n\n # Data\n cost_per_distance = 10\n begin_time = 0\n end_time = 5000\n nb_point = 7\n\n # Map with names and coordinates\n coordinates = {\"Wisconsin, USA\": (44.50, -89.50), # depot\n \"West Virginia, USA\": (39.000000, -80.500000),\n \"Vermont, USA\": (44.000000, -72.699997),\n \"Texas, the USA\": (31.000000, -100.000000),\n \"South Dakota, the US\": (44.500000, -100.000000),\n \"Rhode Island, the US\": (41.742325, -71.742332),\n \"Oregon, the US\": (44.000000, -120.500000)\n }\n\n # Demands of points\n demands = [0, 500, 300, 600, 658, 741, 436]\n\n # Initialisation\n model = vrpse.Model()\n\n # Add vehicle type\n model.add_vehicle_type(\n id=1,\n start_point_id=0,\n end_point_id=0,\n name=\"VEH1\",\n capacity=1100,\n max_number=6,\n var_cost_dist=cost_per_distance,\n tw_end=5000)\n\n # Add depot\n model.add_depot(id=0, name=\"D1\", tw_begin=0, tw_end=5000)\n\n coordinates_keys = list(coordinates.keys())\n # Add customers\n for i in range(1, nb_point):\n model.add_customer(\n id=i,\n name=coordinates_keys[i],\n demand=demands[i],\n tw_begin=begin_time,\n tw_end=end_time)\n\n # Add links\n coordinates_values = list(coordinates.values())\n for i in range(0, 7):\n for j in range(i + 1, 7):\n dist = compute_euclidean_distance(coordinates_values[i][0],\n coordinates_values[j][0],\n coordinates_values[i][1],\n coordinates_values[j][1])\n model.add_link(\n start_point_id=i,\n end_point_id=j,\n distance=dist,\n time=dist)\n\n # solve model\n model.solve()\n model.export()\n\n if model.solution.is_defined():\n print(model.solution)\n\nDocumentation\n-------------\n\nDocumentation, explanation of demos (CVRP, VRPTW, HFVRP, and MDVRP), and\nthe solver API are accessible here: https://vrpsolvereasy.readthedocs.io/en/latest/.\n\nYou can also build the documentation locally by following this\ninstructions from the source folder : ::\n\n cd docs\n python -m pip install -r requirements.txt\n cd ..\n make html\n\nThe HTML pages will be in the folder ``build\\html``.\n\n",
"bugtrack_url": null,
"license": "",
"summary": "'VRPSolverEasy is a simplified modeler solving routing problems by using a Branch-Cut-and-Price approach on a solver like CLP or CPLEX'",
"version": "0.1.4",
"project_urls": {
"Homepage": "https://github.com/inria-UFF/VRPSolverEasy"
},
"split_keywords": [
"['vrp'",
"'branch-cut-&price'",
"'operations research'",
"'optimization'",
"'linear programming'",
"'routing problems'",
"'solver'",
"'supply chain']"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "4561bf450c59762b4cb6e0d962f7c5ec23f9945d93e50393049af9385db4caed",
"md5": "34f68b8b298f41cd967ecb0b874689d6",
"sha256": "ff1881f7ffd404760711842e29f2a7eab19939b47fd6ce02c6ed01158fb63a65"
},
"downloads": -1,
"filename": "VRPSolverEasy-0.1.4-py3-none-any.whl",
"has_sig": false,
"md5_digest": "34f68b8b298f41cd967ecb0b874689d6",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.6",
"size": 530409,
"upload_time": "2023-11-11T15:19:22",
"upload_time_iso_8601": "2023-11-11T15:19:22.453951Z",
"url": "https://files.pythonhosted.org/packages/45/61/bf450c59762b4cb6e0d962f7c5ec23f9945d93e50393049af9385db4caed/VRPSolverEasy-0.1.4-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "2a922be14e8526762dcbe15d8c287c5b133154757fbbb7d3cc969613cafb9a2d",
"md5": "cc55388426a824c3d3e7ac0bab03a3dc",
"sha256": "170ba20ce23066934558f804c204af26852e1fd735836eefe1603867868a3a9b"
},
"downloads": -1,
"filename": "VRPSolverEasy-0.1.4.tar.gz",
"has_sig": false,
"md5_digest": "cc55388426a824c3d3e7ac0bab03a3dc",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.6",
"size": 268745,
"upload_time": "2023-11-11T15:19:27",
"upload_time_iso_8601": "2023-11-11T15:19:27.828066Z",
"url": "https://files.pythonhosted.org/packages/2a/92/2be14e8526762dcbe15d8c287c5b133154757fbbb7d3cc969613cafb9a2d/VRPSolverEasy-0.1.4.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-11-11 15:19:27",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "inria-UFF",
"github_project": "VRPSolverEasy",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "vrpsolvereasy"
}
JSON
