search

yorak / VeRyPy

A python library with implementations of 15 classical heuristics for the capacitated vehicle routing problem.
MIT License
263 stars 55 forks source link
bing-maps classical cvrp generalized-assignment-problem gurobipy heuristics insertion-algorithms lagrangian-relaxation local-search-algoirthms maximum-matching nearest-neighbor parallel-savings python-library savings-algorithm sweep-algorithm traveling-salesman-problem tsp tsp-solver vehicle-routing-problem vrp

readme

VeRyPy

License: MIT

Save your effort to where it matters. With VeRyPy you can avoid reimplementing the best-known classical VRP heuristic algorithms and concentrate on building atop of existing research.

Many planning tasks such as delivery truck route planning, grocery or meal deliveries, school bus routing, service visit routing, waste collection, and many others can be modeled as a Capaciated Vehicle Routing Problem (CVRP). VeRyPy is an easy to use Python library of classical algorithms for CVRPs with symmetric distances. Besides CVRPs, the enclosed implemented algorithms can also be used to solve travelling salesman problems (TSP).

The code is published with a very permissive MIT license, it has very few dependencies, and its code is very loosely coupled. This means you can take just the algorithms or the functionality you need. Be it in your studies, in your academic research project, or to actually solve the real-world logistics planning problems.

Quick Start

To install this package and its dependencies:

pip install https://github.com/yorak/VeRyPy/zipball/master

The installation provides a VeRyPycommand, which reads, e.g., TSPLIB95 formatted files. Solving a problem instance is simple:

VeRyPy -a all E-n51-k5.vrp

Note: some algorithms require additional dependencies such as Gurobi with Python bindings to be installed. See Dependencies and Installation below.

Note: an alternative invocation python -O -m verypy does the same but entirely disables __debug__ and logging.

A third typical way of using VeRyPy is to use it as a python module:

from verypy.cvrp_io import read_TSPLIB_CVRP
# Import the Clarke & Wright (1964) Savings heuristic
from verypy.classic_heuristics.parallel_savings import parallel_savings_init
from verypy.util import sol2routes

E_n51_k5_path = r"E-n51-k5.vrp"

problem = read_TSPLIB_CVRP(E_n51_k5_path)

solution = parallel_savings_init(
    D=problem.distance_matrix, 
    d=problem.customer_demands, 
    C=problem.capacity_constraint)

for route_idx, route in enumerate(sol2routes(solution)):
    print("Route #%d : %s"%(route_idx+1, route))

More such examples are in the examples folder. Run them with, e.g.,:

python examples/single_solve_example.py

Goals and Advantages

Compared to the existing heuristic and metaheuristic open source VRP libraries such as VRPH, Google OR-Tools, the focus in VeRyPy has been in reusability of the code and in faithful recreation of the original algorithms. Because of these specific goals, the enclosed algorithms can (mostly) replicate the existing results from the literature. Also, there is no architecture astronautery in VeRyPy. Instead, the focus is entirely on the Python functions that implement the classical algorithms. The lightness of the framework or shared code is very much intentional-Many existing libraries are complex beasts to reason about and understand, which severely limits their use in a more exploratory setting.

Limitations

Minimizing the shared code between the implemented algorithms has its downsides. For one, there is no central place for a constraint checker or objective function calculation in VeRyPy. Each of the implemented heuristics has its own conventions for constraint checking or updating objective function during the execution of the algorithm. In fact, sometimes the clever way of doing constraint checking is very much the core of the algorithm. This means that any additional side constraints need to be implemented separately for each heuristic.

The other limitations of VeRyPy are also related to the main aims of this project, that is, of replication and simplicity: it is not the fastest, the most sophisticated, nor the most effective library for solving these problems. For example, it being tested only on symmetric distances limits its real-world use. For an implementation of a state-of-the-art CVRP algorithm, please consider checking out, e.g., the HGS-CVRP from Thibaut Vidal.

However, if you are just looking for something simple, VeRyPy might be a perfect fit!

There is also the point to be made that an ensemble of relatively simple heuristics can be an effective and robust way to solve practical problems. Learning and experimenting on the advantages and disadvantages of the different approaches before rolling out a more specialized and sophisticated algorithm can be very fruitful. Furthermore, the quality of the solutions produced by the state-of-the-art metaheuristics often depend on the quality of the initial solutions and VeRyPy can be used to produce a varied set of initial solutions for these more advanced methods.

Features

1 In fact, due to its inherent complexity, this just might be the only open source implementation of the 3-opt* (3-opt-star aka. inter-route 3-opt aka. multiroute 3-opt) operation out there!

Gillet & Miller Sweep heuristic solving a 22 customer problem instance from Gaskell Example of Gillet & Miller Sweep heuristic solving a 22 customer problem instance from Gaskell

Citing VeRyPy

If you find VeRyPy useful in your research and use it to produce results for your publications please consider citing it as:

Rasku, J., Kärkkäinen, T., & Musliu, N. (2019). Meta-Survey and Implementations of Classical Capacitated Vehicle Routing Heuristics with Reproduced Results. In J. Rasku, Toward Automatic Customization of Vehicle Routing Systems (pp. 133-260). JYU Dissertations 113, University of Jyväskylä, Finland.

Dependencies and Installation

Currently, VeRyPy supports Python versions at least up to 3.8.10 and should still be compatible with Python 2.7. VeRyPy requires NumPy, and SciPy. Also, some algorithms have additional dependencies: MJ76-INS needs llist from PyPI; and FR76-1PLT , FG81-GAP, and DV89-MM require Gurobi with gurobipy. By default Be83-RFCS, SG82-LR3OPT, and Ty68-NN use LKH to solve TSPs, but they can be configured to use any other TSP solver (such as the internal one) if these external executables are not available. Note that LKH has non-free license. Refer to auxiliary documentation on how to compile and condifure LKH.

Installation with pip from this repository installs most of the dependencies (save Gurobi and LKH).

pip install https://github.com/yorak/VeRyPy/zipball/master

There are tutorial videos available that show the steps for installing VeRyPy on Windows on top of plain Python or PyCharm IDE. Note that in case you want to run the tests, skip pip installation. Instead, clone this repository and add the VeRyPy root folder to your PYTHONPATH environment variable.

Contributing and Contacting

Please consider contributing to VeRyPy. But, if this library does not meet your needs, please check the alternatives: VRPH, Google OR-Tools. In order to avoid reinventing (rewriting?) the wheel, please fight the NIH and consider the aforementioned options before rolling out your own VRP/TSP library.

All contributions including, but not limited to, improving the implemented algorithms, implementing new classical heuristics or metaheuristics, reporting bugs, fixing bugs, improving documentation, writing tutorials, or improving the usability of the library are welcome. However, please note that any contributions you make will be under the MIT Software License. Even if you are not that much into coding please note that blogging, tweeting, and just plain talking about VeRyPy will help the project to grow and prosper.

When contributing:

Feature requests can be made, but there is no guarantee that they will be addressed. For a more complex use cases one can contact Jussi Rasku who is the main author of this library: jussi.rasku@gmail.com.

If you are itching to get started, please refer to the todo list below:

Implemented Heuristics with References

cmt : Christofides, Mingozzi & Toth (1979) two phase heuristic.

CMT79-2P: Christofides, N., Mingozzi, A., and Toth, P. (1979). The vehicle routing problem. In Christofides, N., Mingozzi, A., Toth, P., and Sandi, C., editors, Combinatorial Optimization, chapter 11, pages 315-338. Wiley.

gap : Fisher & Jaikumar (1981) generalized assignment problem (GAP) heuristic. Requires Gurobi.

FJ81-GAP: Fisher, M. L. and Jaikumar, R. (1981). A generalized assignment heuristic for vehicle routing. Networks, 11(2):109-124.

gm : Gillett & Miller (1974) Sweep algorithm with emering route improvement step.

swp : Sweep algorithm without any route improvement heuristics.

GM74-SwRI: Gillett, B. E. and Miller, L. R. (1974). A heuristic algorithm for the vehicle-dispatch problem. Operations Research, 22(2):340-349.

gpl : Parallel savings algorithm with Gaskell (1967) with the 𝜋 and 𝜆 criteria.

Ga67-PS|𝜋𝜆: Gaskell, T. (1967). Bases for vehicle fleet scheduling. Journal of the Operational Research Society, 18(3):281-295.

gps : Paessens (1988) parametrized parallel savings algorithm.

Pa88-PS|G2P: Paessens, H. (1988). The savings algorithm for the vehicle routing problem. European Journal of Operational Research, 34(3):336-344.

ims : Holmes & Parker (1976) parallel savings supression algorithm.

HP76-PS|IMS: Holmes, R. and Parker, R. (1976). A vehicle scheduling procedure based upon savings and a solution perturbation scheme. Journal of the Operational Research Society, 27(1):83-92.

lr3o : Stewart & Golden (1984) 3-opt* heuristic with Lagrangian relaxations.

SG84-LR3OPT: Stewart, W. R. and Golden, B. L. (1984). A Lagrangean relaxation heuristic for vehicle routing. European Journal of Operational Research, 15(1):84-88.

mbsa : Desrochers and Verhoog (1989) maximum matching problem solution based savings algorithm. Requires Gurobi.

DV89-MM: Desrochers, M. and Verhoog, T. W. (1989). G-89-04 : A matching based savings algorithm for the vehicle routing problem. Technical report, GERAD, Montreal, Canada.

mj : Mole & Jameson (1976) sequential cheapest insertion heuristic with a route improvement phase.

MJ76-INS: Mole, R. and Jameson, S. (1976). A sequential route-building algorithm employing a generalised savings criterion. Journal of the Operational Research Society, 27(2):503-511.

ps : Clarke & Wright (1964) parallel savings algorithm.

CW64-PS:Clarke, G. and Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4):568-581.

ptl : Foster & Ryan (1976) Petal set covering algorithm. Requires Gurobi.

FR76-1PTL: Foster, B. A. and Ryan, D. M. (1976). An integer programming approach to the vehicle scheduling problem. Journal of the Operational Research Society, 27(2):367-384.

pi, vB94-PI : parallel insertion heuristic as described by van Breedam (1994, 2002).

pn, vB94-PNN : Parallel Nearest Neighbor construction heuristic.

si, vB94-SI : Sequential cheapest insertion heuristic without local search (van Breedam 1994, 2002).

sn, vB94-SNN : Sequential Nearest Neighbor construction heuristic as described by van Breedam (1994).

vB94: Van Breedam, A. (1994). An Analysis of the Behavior of Heuristics for the Vehicle Routing Problem for a Selectrion of Problems with Vehicle-related, Customer-related, and Time-related Constraints. PhD thesis, Faculty of Applied Economics, University of Antwerp, Belgium - RUCA.

and

Van Breedam, A. (2002). A parametric analysis of heuristics for the vehicle routing problem with side-constraints. European Journal of Operational Research, 137(2):348-370.

rfcs : Route-first-cluster-second heuristic of Beasley (1983).

Be83-RFCS: Beasley, J. E. (1983). Route first - cluster second methods for vehicle routing. Omega, 11(4):403-408.

ss : Webb (1964) sequential savings algorithm.

We64-SS: Webb, M. (1964). A study in transport routing. Glass Technology, 5:178-181.

ty : Tyagi (1968) Nearest Neighbor construction heuristic.

Ty68-NN: Tyagi, M. S. (1968). A practical method for the truck dispatching problem. Journal of the Operations Research Society of Japan, 10:76-92.

wh : Sweep heuristic with Wren and Holliday (1972) improvement procedures.

WH72-SwLS: Wren, A. and Holliday, A. (1972). Computer scheduling of vehicles from one or more depots to a number of delivery points. Journal of the Operational Research Society, 23(3):333-344.

License

VeRyPy is licensed under the MIT license.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.