Having an easy way to plot solutions is very convenient for debugging/benchmarking. By easy, I mean just rendering the solution layout with ordered routes as straight lines. This is especially relevant for benchmark instances relying on euclidean distance, but can also be useful for real-life instances.

I already have a functioning python script based on matplotlib for this, I would need to tidy it up before publishing.

The various *_to_json.py scripts we have to parse *.tsp and *.vrp files and format them to json still use keys that are now deprecated:

• job.amount
• matrix

Now that we have deterministic formatting in place (#22), we could push the logic and add PEP8 compliance checks.

The DLP dataset (https://perso.isima.fr/~lacomme/hvrp/hvrp.html) for HVRP instances has a major drawback: it comes with the cost matrix but no location for vehicle start and jobs.

While this is fine in theory since the cost matrix is all we need, there are two problems:

• it makes it a pain to debug and visually analyze solutions on those instances;
• the dataset can't make use of the local search operator pruning techniques we've recently introduced in VROOM.

Especially the last point is frustrating because we can't really benchmark the impact of those changes (quality/computing time) on this dataset.

Trying to execute add_ors_matrix.py returns error: ImportError: cannot import name 'add_matrix' from 'utils.matrix'

Changing 'add_matrix' into 'add_matrices' (which is used in add_osrm_matrix.py) rise more errors.

We need to format classic VRPTW benchmark files to serve as a set of reference instances while developing VROOM-Project/vroom#113.

The reference benchmarks used in the literature are from Solomon and later Gehring and Homberger. All instances are described in plain text here along with some reports of best known solutions.

A python script similar to the current tsplib_to_json.py and cvrplib_to_json.py would probably be enough.

The API evolved to allow passing several matrices in input for multiple profile. We should update the add_osrm_matrix.py script to account for this.

We already have an add_osrm_matrix.py script to create a standalone problem embedding the durations in the problem instance and setting relevant location_index values. It could be useful to have a similar script for Openrouteservice.

There is a set of 10,000 CVRP instances with 100 jobs each available on CVRPLIB. They are modeled on the X generation pattern and were primarily designed as a framework for evaluating ML approaches as all optimal solutions are known, see this paper for the rationale.

It would be interesting to test on those.

When generating a random instance with random_problem.py, it would be convenient to be able to pin the depot to the center of the bbox.

It would be nice to have a code formatter for the python scripts in place in order to set a deterministic standard and focus on content.

Hi there,

I've been experimenting with the asap.py file for minimizing the completion time for a group of jobs to be serviced around a city.

My current use case is to optimize the routes on the fly as jobs has being created already before the optimization call, and I was wondering if there could be a possibility to also allow negative time constraint strictly to indicate how long ago was a job already available to be serviced. Doing this, would make a lot of sense when it comes to minimizing the job completion time no?

Lines 23 and 89 of plot.py should be changed to use 'in' since has_key is deprecated with Python 3.x

Ref: https://stackoverflow.com/questions/1323410/should-i-use-has-key-or-in-on-python-dicts

Solution:
23: if(not 'routes' in solution):
89: if('routing' in solution['summary']['computing_times']):

I was checking out this issue #31. But when I tried running the script it had two minor issues

1. Incorrect import: due to the change in add_matrix function name change introduced in ee9ef52
2. Incorrect space when building args for vroom specifically in threads(-t) and exploration level(-x)

Here is a random MDVRP instance example.txt and the corresponding JSON file example.json.zip generated using the vroom-script.

Solution generated contains 16 unassigned jobs, even though there are no time constraints. I noticed the same issue with few more randomly generated MDVRP instances without time windows. What is the issue here?

Also, does the solver consist of any time limit parameter (or any other input parameters apart from the instance features) which can be adjusted to obtain better quality solution?

Thank you for the great package and the scripts!

I'd like to try a (somehow brutal) way to answer VROOM-Project/vroom#466 without changing the default optimization objective in the core solving approach. The idea would be to solve the same problem iteratively with various planning horizons to come up with a set of trade-offs between completion time and overall cost.

Of course this means solving several times (variants of) the same problem so the impact on computing times may be far from negligible but this may do the job for some use-cases. Also this would highly depend on how we adjust the planning horizon. A simplistic approach of reducing iteratively might result in lots of calls but a dichotomic search of the sweet spot may be all we need in the end.

Another interest of this is that instead of delivering a single "minimum completion" solution, we could actually provide a set of different trade-offs between computing time and cost in the form of a Pareto front. There are indeed situations where the actual smallest completion time may not be the desirable outcome if it means a huge increase in cost.

It's convenient for debugging or solution analysis to be able to plot a gantt-like timeline for vehicle activity (start, end, travel times, service times along with timing constraints).

I have a working version I've extensively used for plan mode that also shows violations. I want to clean it up and add it to the set of existing scripts.

It would be nice to be able to test on instances with backhauls. I'm thinking in particular of instances derived from the X class of CVRPLIB found in https://hal.inria.fr/hal-02379008/file/Queiroga_etall_LOGIS19.pdf.

Dear @jcoupey ,

Thank you so much for working on #31 . This is extremely helpful for what I've been attempting to accomplish!

Pardon my question but I'm a noob when it comes to all this and I desperately want to utilize your solution. I'm using vroom in a docker container, which receives HTTP API requests. How would I incorporate this script into such a configuration?

When creating a standalone problem in add_osrm_matrix.py, we add all start/end vehicle locations then all job locations, then fire an OSRM table request. There are unnecessary duplicates both in the request and the resulting matrix rows and column, especially in single depot settings with a high number of vehicles.

Locations already set for the matrix request should be reused with their index assigned to matching locations.

We have everything in place in term of features to test VROOM against the MDVRP instances from Cordeau et al..

I actually already looked this dataset up a while back but stumbled upon the lack of documentation. Turns out other instances for MDVRPTW share the same formatting so generating json instances is pretty straightforward.

To plot vehicle routes with different colors, we use a list generated from matplotlib.colors.cnames with the vehicle id as rank in the list. This works fine for benchmark examples with small number of vehicles but obviously breaks for higher id values.

With the support for distances matrix in VROOM comes the need to include those matrices in the standalone instances we generate with the add_*_matrix scripts.

For now the HVRP instances we have are limited to scaling durations (via speed_factor) but we could not handle instances with fixed costs. For the sake of benchmarking VROOM-Project/vroom#788 it would be handy to have a greater variety of sources here. In particular from https://perso.isima.fr/~lacomme/hvrp/hvrp.html:

• VFMP-F instances;
• VFMP-FV instances;
• DLP instances.

In order to best analyse solutions, it would be useful to have a script generating simple statistics on vehicle usage. Off the top of my head:

• max load on each amount component
• ratio of vehicle occupancy based on max load
• route duration/ratio of time window occupancy
• ratio of time spent in travel, service or waiting time

Vehicle fleet mix problem (VFMP) are a class of HVRP (Heterogeneous VRP) problems that aim at deciding how to choose the fleet from an unlimited number of resources with different capacity and costs in order to assign all jobs. Cost differences across vehicles are usually described as 1. a different fixed cost for using a vehicle and 2. a multiplicative factor on top of the same cost matrix.

VFMP instances come in various flavors:

• VFMP-F have fixed costs only;
• VFMP-V have variable costs only;
• VFMP-FV have both.

Along with other HVRP instances, there are a few examples of those at https://perso.isima.fr/~lacomme/hvrp/hvrp.html.

Because we don't currently handle fixed costs, the only class we can easily work with is VFMP-V, which I've used during the work on VROOM-Project/vroom#450.

We should make available everything required to reproduce tests on the VFMP-V instances.

I've recently discovered that the jobs completion time are equivalent when using profiles of cycling-electric and cycling-regular from ORS, is there any explanation as to why it is? Because I highly doubt that this two profiles would be traveling at the same speed or same roads.

The plot script does a good job geographically displaying the routes we produce in a simple way, but it usually also helps to have an understanding of vehicle schedules to better understand optimization outcome.

It would be convenient to have some kind of overall schedule plot with a timeline for all vehicles at a glance, including visual representation of different route actions: travel, service, waiting etc.

We need to format classic PDPTW benchmark files to serve as a set of reference instances while developing VROOM-Project/vroom#189.

The Li & lim benchmarks are described in plain text here along with some reports of best known solutions (as usual with a slightly different optimization objective).

We also need a python script similar to *_to_json.py for PDPTW.

tried changing
backend : TkAgg -->backend : agg

in /usr/local/lib64/python2.7/site-packages/matplotlib/mpl-data/matplotlibrc file to compensate for AWS headless environment.

Traceback (most recent call last):
File "plot.py", line 100, in
plot_routes(f)
File "plot.py", line 26, in plot_routes
xmin = solution['routes'][0]['steps'][0]['location'][0]
KeyError: 'location'

Some scripts need to be adjusted or improved for use with the new shipments objects from the vroom API.

Are you able to upload the results of these benchmarking scripts here?

I see it should be easy to run your scripts, but it'd be super helpful if you could upload the results here as well so I can validate my results.

Thanks!