Research Software

VRPy

Nov 16, 2020. | By: @tabakg

Today we’ll take a detour (pun intended) into the vehicle routing problem, and present VRPy, a Python library for solving several variants of this problem.

/rseng/assets/img/posts/showcase/vrpy.png

Are you already familiar with VRPy? We encourage you to contribute to the research software encyclopedia and annotate the respository:

otherwise, keep reading!

What is VRPy?
How do I cite it?
How do I get started?
How do I contribute to the software survey
Where can I learn more?

What is VRPy?

The basic question that VRPy aims to solve is how to route a fleet of vehicles to transport a number of customers to their destination (in the most basic formulation all vehicles start at a source, end at a sink, and must visit each customer exactly once).

There are a number of variants of the problem, for example the ‘capacitated’ version presents a vehicle with a maximum carrying capacity. There are also different possible objectives, like the total distance traveled or maximum distance traveled by each vehicle. The image at the top of this post is a solution to the basic capacitative problem with four vehicles minimizing total distance on a grid (the numbers outside the circles represent each customer’s capacity – the maximum is 15 per vehicle). The source and sink are both the central red point.

VRPy is an extremely easy-to-use Python library built on top of NetworkX (a well-known Python graph library). Basically, all you have to do to use it is set up a graph and choose a few options. See their docs for examples!

Why is it useful?

While this isn’t the first library to address the routing problem (it is even inspired by Google’s OR-tools), it is entirely implemented in Python and has a very accessible API (The performance still seems to be similar to OR-Tools according to VRPy’s benchmarks). This would be especially useful for researchers who want to tinker with new algorithms. Vehicle routing has been an active field of research for decades, and with self-driving cars around the corner I wouldn’t expect it to slow down!

How do I cite it?

There is an accompanying paper, which you can cite using:

@article{montagne2020vrpy,
  title={VRPy: A Python package for solving a range of vehicle routing problems with a column generation approach},
  author={Montagn{\'e}, Romain and Sanchez, David Torres and Storbugt, Halvard Olsen},
  journal={Journal of Open Source Software},
  volume={5},
  number={55},
  pages={2408},
  year={2020}
}

How do I get started?

README Documentation is always a good place to start.
JOSS paper.

How do I contribute to the software survey?

or read more about annotation here. You can clone the software repository to do bulk annotation, or annotation any repository in the software database, We want annotation to be fun, straight-forward, and easy, so we will be showcasing one repository to annotate per week. If you’d like to request annotation of a particular repository (or addition to the software database) please don’t hesitate to open an issue or even a pull request.

Where can I learn more?

You might find these other resources useful:

The Research Software Database on GitHub
RSEpedia Documentation
Google Docs Manuscript you are invited to contribute to.
Annotation Documentation for RSEpedia
Annotation Tutorial in RSEng docs

For any resource, you are encouraged to give feedback and contribute!