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/masterThe installation provides a VeRyPycommand, which reads, e.g., TSPLIB95 formatted files. Solving a problem instance is simple:
VeRyPy -a all E-n51-k5.vrpNote: an alternative invocation
python -O -m verypydoes 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.pyGoals 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
- Implementations of 15+ CVRP heuristics that are:
- deterministic,
- classical (from 60ies to mid 90ies, well-cited),
- constructive (as opposed to improvement heuristics), and which are
- tested on a comprehensive set of 454 well-known CVRP benchmark instances.
- The correctness of implementation is shown through replication of the original results, where
- the results are replicated perfectly or near perfectly for 11 of the classical heuristics, but
- for 4 of the classical heuristics, the results are bit ambigious.
- For a full list, see the heuristics list with references.
- Collection of local search heuristics:
- intra route: 2-opt, 3-opt, relocate, exchange
- inter route: insert, 2-opt*, 3-opt*1, one-point-move, two-point-swap, redistribute, chain
- Wrappers for LKH, ACOTSP, and Gurobi TSP solvers
- Command Line user Interface (CLI) for using the library and algorithm codes
- Integration, replication, and even some unit tests
- Imports TSPLIB compatible CVRP and TSP files
- Exports VRPH compatible solutions
- Visualizer for many of the 15 heuristics
- Included is an example that uses Bing maps API to use street addresses, calculate distances in a real road network, and solve the related CVRP truck/delivery dispatching task.
- Most of the algorithms are able to solve CVRP instances up to 1000 customers in under an hour
- The fastest of the algorithms can tackle problems with over 10 000 customers in a reasonable time
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!
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/masterThere 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:
- Report bugs using Github issues, and, while doing so, be specific and show how to reproduce the bug
- Use a consistent Pythonic coding style (PEP 8)
- The comments and docstrings have to be written in NumPy Style
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: [email protected].
If you are itching to get started, please refer to the todo list below:
- Package project for
pipto make it easier to install - Transform all docstrings to NumPy format and generate restructured documentation (work ongoing by yorak)
- Implement the inter-route 3-opt* that only operates on the selected 2 or 3 routes (as opposed to the proven solution-based version can be used as an reference). This work has been started, but not completed.
- Consider verifing the support for asymmetric problems. Most of the algorithms should support this already, but more tests should be written to verify this.
- Consider adding support for time windows (VRPTW). This would probably lead to a major refactoring, but could be an interesting exercise.
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.