Using custom matrix from JSON-object instead of OSRM.

[PattyDePuh]

Hey folks,
On my fork i implemented the first iteration of the json-uploader, another option to provide Cost-matrix, instead of OSRM. With the json-uploader, you can use the matrix from the JSON object, that is given to the application. Run the application with the -j flag to unlock the feature:
Usage example: ./vroom -i /path/to/json.txt -j
test8u.json.txt
Output with above file:
{"routes":[{"steps":[0,2,3,7,6,1,4,5,8],"cost":8362,"vehicle":1}],"solution":{"computing_times":{"loading":0,"solving":0},"cost":8362},"code":0}
(VROOM found one of the optimal solutions for the above instance.)
Because there are no location coordinates necessary in this case, the "jobs"-key becomes obsolet and the "vehicles"-key provides with "start" and "end" the desired start and end-points associated with the columns from the matrix.
For roundtrips currently you can't simply set "start" = "end" because of an assert in one of the solvers; Gonna' look on this one...

[jcoupey]

Hey, thanks for sharing this!

This feature might be a useful addition. My concerns here are:

1. The TSPLIB format support is the way this is currently implemented. Maybe you have use-cases in mind where it is not possible to use it? So far, this looks really the same as displaying the explicit matrix in a plain TSPLIB file with the additional keywords: START: 0 and END: 8.
2. This breaks the API defined at https://github.com/VROOM-Project/vroom/blob/master/docs/API.md ; I think we would need to keep a jobs array in input. Maybe make the locations optional if a matrix is provided, and require that ids actually describe matrix indexes. This is mandatory if we need to add other keys in jobs for future features.
   Ideally, parsing a file with a matrix key should reuse the same existing code for json parsing (currently in osrm_loader) and just add the matrix stuff on top. I realize this is not possible at the moment but should be easier in the future with Problem and heuristics refactor #44 where I plan to separate the input parsing and the different loaders.

Thanks for your input, I'm happy to discuss this further!

[PattyDePuh]

1. The use-case in my opinion are comin'up, when we are able to use VROOM as a framwork in other applications and production-chains. JSON is simplicity and comfort - there are dozens of libraries, which parse appropriate JSON-Outputs with a blink of code in any convinient coding language. Taking for Example JSON for modern C++, where you can simply put a src::vector into a JSON to build wide-range arrays. Couldn't say the same to the TSPLIB format.
   With the available features in VROOM 1.0 so far - yes, TSPLIB covers everything, what the features and options demand. But if we start to expand the repertoire like multi-vehicle, timeframes etc. Does the convention of TSPLIB still cover that? Or was the START and END parameter already a custom convention?

[jcoupey]

I agree on your arguments in favour of a json implementation for this. Yet redundancy bothers me.

The reason of the tsplib_loader's existence is that it was a way to easily benchmark the code (and then it also became a way to provide custom matrices). But yes START and END are custom keywords. Maintaining TSPLIB support in parallel of the json API for "extra-TSP" features like open trips has already proven to be a pain in the ass. And supporting other slighty different benchmark formats for CVRPs and such problems would probably be painful too.

So I think the wise choice here would be to remove the TSPLIB format support altogether, replacing it as you suggest with an optional matrix key in json input. Then we have to think about it thoroughly in term of API (see 2. above).

Using other benchmarks sources would only be a matter of setting an ad-hoc conversion to json, which is not a problem.

[PattyDePuh]

About the concern 2. above:
We could get it clean with location-like keywords for the jobs and vehicles, that describes the respective column in the matrix instead of the coordinates, which remain optional, so it won't conflict that hard with the current API:

{
 "vehicle": [
    { "id":0, "m_start":0, "m_end":3 }
  ],
  "jobs": [
    { "id":0, "m_location":1 },
    { "id":1, "m_location":2 }
  ],
  "matrix": [
    [0, 34, 15, 23]
    [32, 0, 53, 18]
    [16, 51, 0, 27]
    [23, 17, 29, 0]
  ]
}

So if matrix is available, then m_location, m_start and m_end become mandatory. Else if you want to get the table from OSRM, then location, start, and end are the desired ones. And still you can give as option the coordinates along, while the matrix is still provided, in cases, that the costs represent a different kind of traveling cost, which OSRM don't provide.

[jcoupey]

I guess this would be the best approach. Maybe something like start_index, end_index and location_index would be clearer.

I'm also concerned about the output consistency for the step objects. If a matrix is provided, type and job are still relevant and location would become optional. So we would have to add an index key to each step.

The downside of this is that the way the output should be parsed (and the expected keys) becomes input-dependant.

[jcoupey]

Ok let's plan this. I hope to be able to work on #48 and #44 soon. This should clear the way and make it easier.

[jcoupey]

I'm done with the refactoring in #44 so I plan to release v1.1.0 as soon as #56 is done. In this prospect, I've merged the develop branch into master for good, and I'm postponing this to v1.2.0.

[jcoupey]

@PattyDePuh if you still feel like working on this (sorry for the delay), you can start off from the last commit in master. There is already an entry point at https://github.com/VROOM-Project/vroom/blob/master/src/utils/input_parser.cpp#L79.

[PattyDePuh]

Got a first working version for the json-matrix-import.
https://github.com/PattyDePuh/vroom/tree/json-matrix%2347
("Working" - don't guarantee yet, that it is "stable")

I've touched several classes for it:

• parsing of the json-matrix and added SanityChecks acordingling in input_parser.cpp.
• enabled vector::push_back in matrix.cpp. (Can be avoidable somehow, if undesired)
• added a bool-flag to indicate, that a custom matrix is provided in input_parser.cpp.
• skipping get_matrix part in tsp.cpp, if the custom matrix is provided.

Since i couldn't use start/end attributes for the matrix-row-identifier, i added two alternative attributes start_id and end_id. This effected the following classes:

• input.cpp gained an overloaded funtion add_vehicle for the above attributes.
• vehicle.h gained attributes and constructor accordingly, as another was to check for force_start and force_end.
• added the alternative force_start, force_end handling to tsp.cpp.
• added export cases for the start/end steps, which don't have coordinates in output_json.cpp.

My questions @jcoupey :

1. Should it be possible to gain a route-geometry back from OSRM, if coordinates for jobs/start/end provided, but custom matrix also? At some point i thought, that the custom matrix doesn't have to exclude the osrm-feature, but so far for the above situation, there is no usecase on my mind.
2. Which branch should i target for a future pull-request?
3. Is there a desired place for the guideline, i should then extend in mind of the new official feature?

[jcoupey]

Thanks for the work and sharing details! A few quick thoughts:

• start index and end index should both be optional (what is mandatory is having at least one of them). There is already a check for this.

• I think you can avoid touching the matrix structure altogether by using the existing constructor with expected size, as in the routing part. Removing push_back also avoids potential vector resizing.

• You should be able to use the vehicle start and end attribute to store the matrix index using this location attribute. It's actually currently hidden by the use of _location_number to decide of the current index in input.cpp. Your new add_vehicle function (with start_index and end_index) could do all the work, providing the correct matrix index, and the other version could call it with the appropriate value using _location_number. Same for add_job(id, coords, index) and add_job(id, coords). Let me know what you think, or if this is even clear enough!

[jcoupey]

About the questions.

1. Could be interesting. Probably better to deal with this later though. ;-)

2. you should target master, I'm dropping the develop branch thing and I try to make things clearer in the guidelines, but those are not merged to master yet. What you can do is submit a PR even for a work in progress so we can work together and discuss things directly in the PR.

3. the docs/API.md will have to be updated at some point if this is what you have in mind.

[jcoupey]

@PattyDePuh I just merged the documentation/guidelines branch. As it contains some cleanup with regard to the coding standard, you may experience conflicts (perhaps need to rebase your working branch on current master head). Sorry for the inconvenience.

[jcoupey]

Landed with #59 merge.