Using OSRM v4.9.1 and current master of VROOM.

We're getting the following error when passing ~950 points, along with -s and -g options.

vroom: structures/../loaders/osrm_wrapper.h:259: virtual void osrm_wrapper::get_route_infos(const std::list<short unsigned int>&, rapidjson::Document&) const: Assertion `infos.HasMember("route_summary")' failed. 

OSRM is running with --max-table-size and --max-matching-size set to 9999.

We don't have any issues when using a smaller number of points, so I'm wondering is there some option get need to set when running osrm-routed?

Thanks in advance.

While trying to proceed with #47 i tumbled over an exception, that the 'use_libosrm' flag was missing in
https://github.com/VROOM-Project/vroom/blob/master/src/structures/typedefs.h#L30
used in
https://github.com/VROOM-Project/vroom/blob/master/src/utils/input_parser.cpp#L32
preventing to compile on the master-branch.

@jcoupey I don't know, if it is intended or not, if LibOSRM is still a thing.
My guess is, that was a mistake, that the bool variable is missing, so i have added it into the struct, but without an activation flag.
Foundable in this branch

hello , i'm facing an error i don't understand
=> `
utils/../../include/rapidjson/document.h:1038:29: error: call of overloaded 'GenericValue(long unsigned int&)' is ambiguous
GenericValue v(value);
^
utils/../../include/rapidjson/document.h:536:14: note: candidate: rapidjson::GenericValue<Encoding, Allocator>::GenericValue(double) [with Encoding = rapidjson::UTF8<>; Allocator = rapidjson::MemoryPoolAllocator<>]
explicit GenericValue(double d) RAPIDJSON_NOEXCEPT : data_(), flags_(kNumberDoubleFlag) { data_.n.d = d; }
utils/../../include/rapidjson/document.h:525:14: note: candidate: rapidjson::GenericValue<Encoding, Allocator>::GenericValue(uint64_t) [with Encoding = rapidjson::UTF8<>; Allocator = rapidjson::MemoryPoolAllocator<>; uint64_t = long long unsigned int]
explicit GenericValue(uint64_t u64) RAPIDJSON_NOEXCEPT : data_(), flags_(kNumberUint64Flag) {
^
utils/../../include/rapidjson/document.h:511:14: note: candidate: rapidjson::GenericValue<Encoding, Allocator>::GenericValue(int64_t) [with Encoding = rapidjson::UTF8<>; Allocator = rapidjson::MemoryPoolAllocator<>; int64_t = long long int]
explicit GenericValue(int64_t i64) RAPIDJSON_NOEXCEPT : data_(), flags_(kNumberInt64Flag) {
^
utils/../../include/rapidjson/document.h:504:14: note: candidate: rapidjson::GenericValue<Encoding, Allocator>::GenericValue(unsigned int) [with Encoding = rapidjson::UTF8<>; Allocator = rapidjson::MemoryPoolAllocator<>]
explicit GenericValue(unsigned u) RAPIDJSON_NOEXCEPT : data_(), flags_(kNumberUintFlag) {
^
utils/../../include/rapidjson/document.h:497:14: note: candidate: rapidjson::GenericValue<Encoding, Allocator>::GenericValue(int) [with Encoding = rapidjson::UTF8<>; Allocator = rapidjson::MemoryPoolAllocator<>]
explicit GenericValue(int i) RAPIDJSON_NOEXCEPT : data_(), flags_(kNumberIntFlag) {
^
utils/../../include/rapidjson/document.h:447:5: note: candidate: rapidjson::GenericValue<Encoding, Allocator>::GenericValue(const rapidjson::GenericValue<Encoding, Allocator>&) [with Encoding = rapidjson::UTF8<>; Allocator = rapidjson::MemoryPoolAllocator<>]
GenericValue(const GenericValue& rhs);
^
utils/../../include/rapidjson/document.h:440:5: note: candidate: rapidjson::GenericValue<Encoding, Allocator>::GenericValue(rapidjson::GenericValue<Encoding, Allocator>&&) [with Encoding = rapidjson::UTF8<>; Allocator = rapidjson::MemoryPoolAllocator<>]
GenericValue(GenericValue&& rhs) RAPIDJSON_NOEXCEPT : data_(rhs.data_), flags_(rhs.flags_) {
^
make: *** [utils/logger.o] Error 1

`
sounds like he's looking for a value but don't know which one take

Drop lat,lon order in both input and output would make things more consistent w.r.t.:

• the geojson standard;
• OSRM move to lon,lat as of v5;
• results output with TSPLIB mode (normal x,y order).

Currently the input class contains all the data to model the problem (jobs, vehicles) and is responsible for computing and storing the matrix.

Yet, a copy of the matrix is made at

We should avoid this copy while still allowing the tsp class to use a customized version of the matrix, and several different adaptations should be possible (think creating several tsp instances to solve sub-problems with different start/end, without copying or modifying the initial matrix).

There is probably a good way to do this by designing a wrapper around the current matrix structure. It could hold a reference to the one and only initial matrix and return its values except when start/end adjustments related to a vehicle are to be made.

Use of std::cerr in place of std::cout when the ouput is about error or info in the normal process.
Goal: have only expected result on cout. json to cout, into and error to cerr.

The verbose output (-v option) is mostly a list of debug/development information that still needs a good cleanup.

Maybe use several logging levels to easily filter the most user-pertinent information.

The initial table used to compute the matrix also returns hints. When retrieving all information to format the solution, these hints could be used to speed-up the route request.

On some problem vroom fail with:

vroom: heuristics/../algorithms/munkres.h:309: std::unordered_map<short unsigned int, short unsigned int> greedy_symmetric_approx_mwpm(const matrix<T>&) [with T = unsigned int]: Assertion `m.size() % 2 == 0' failed.

Do you plan to load arbitrary matrix or TSPLIB file format ?

Hey everyone,
just heard of the framework few days ago and its nice to see an opensource TSP-solution, that actually beats my current internal creation by 10% better results.
Today i've been trying out the 1.0 release candidate branch and found it quite curious, that the roundtrip result and the strict end result "with -e Parameter" were the same, if you load a custom cost-matrix instead of using OSRM:
used Sample: http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/swiss42.tsp
Output for the default roundtrip:
' /vroom/bin$ ./vroom -i ../swiss42.tsp.txt '

{"routes":[{"steps":[{"type":"start","job":0},{"type":"job","job":32},{"type":"job","job":34},{"type":"job","job":33},{"type":"job","job":20},{"type":"job","job":35},{"type":"job","job":36},{"type":"job","job":31},{"type":"job","job":17},{"type":"job","job":7},{"type":"job","job":37},{"type":"job","job":15},{"type":"job","job":16},{"type":"job","job":14},{"type":"job","job":19},{"type":"job","job":13},{"type":"job","job":5},{"type":"job","job":26},{"type":"job","job":18},{"type":"job","job":12},{"type":"job","job":11},{"type":"job","job":25},{"type":"job","job":10},{"type":"job","job":8},{"type":"job","job":9},{"type":"job","job":41},{"type":"job","job":23},{"type":"job","job":40},{"type":"job","job":24},{"type":"job","job":21},{"type":"job","job":39},{"type":"job","job":22},{"type":"job","job":38},{"type":"job","job":30},{"type":"job","job":29},{"type":"job","job":28},{"type":"job","job":27},{"type":"job","job":2},{"type":"job","job":3},{"type":"job","job":4},{"type":"job","job":6},{"type":"job","job":1},{"type":"end","job":0}],"cost":1273,"vehicle":0}],"solution":{"computing_times":{"loading":3,"solving":0},"cost":1273},"code":0}

And with the strict end flag:
/vroom/bin$ ./vroom -i ../swiss42.tsp.txt -e

{"routes":[{"steps":[{"type":"start","job":0},{"type":"job","job":32},{"type":"job","job":34},{"type":"job","job":33},{"type":"job","job":20},{"type":"job","job":35},{"type":"job","job":36},{"type":"job","job":31},{"type":"job","job":17},{"type":"job","job":7},{"type":"job","job":37},{"type":"job","job":15},{"type":"job","job":16},{"type":"job","job":14},{"type":"job","job":19},{"type":"job","job":13},{"type":"job","job":5},{"type":"job","job":26},{"type":"job","job":18},{"type":"job","job":12},{"type":"job","job":11},{"type":"job","job":25},{"type":"job","job":10},{"type":"job","job":8},{"type":"job","job":9},{"type":"job","job":41},{"type":"job","job":23},{"type":"job","job":40},{"type":"job","job":24},{"type":"job","job":21},{"type":"job","job":39},{"type":"job","job":22},{"type":"job","job":38},{"type":"job","job":30},{"type":"job","job":29},{"type":"job","job":28},{"type":"job","job":27},{"type":"job","job":2},{"type":"job","job":3},{"type":"job","job":4},{"type":"job","job":6},{"type":"job","job":1},{"type":"end","job":0}],"cost":1273,"vehicle":0}],"solution":{"computing_times":{"loading":0,"solving":0},"cost":1273},"code":0}

where i thought, that the step with job-id 41 should be at the end on the second output.

I have hardly looked through the code by now; Maybe it isn't implemented yet. Maybe i don't know good enough, how to use VROOM properly. But it sure is a thing to mention and look up.

A CONTRIBUTING file is missing to help people get started with coding conventions, branching model etc.

Probably relevant to have a good code cleanup at the same time to make sure the current code-base adheres to the guidelines...

Discussion initiated from PR #22. Related commits to be found in branch experimental_huge_instances.

Some instances (not all) produce a segfault. Probably related to the change introduced in f1b8edc.

Use a library like rapidjson to handle properly the json output from OSRM.

Some atsp sample from http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ ends in seg fault caused by stack overflow.

With
gcc version 6.1.1 20160501 (GCC)
boost 1.60

Some compiling problems

g++ -std=c++14 -Wpedantic -Wall -O3 -DBOOST_LOG_DYN_LINK -c heuristics/local_search.cpp -o heuristics/local_search.o
heuristics/local_search.cpp: In constructor 'local_search::local_search(const matrix<unsigned int>&, bool, const std::__cxx11::list<short unsigned int>&, unsigned int)':
heuristics/local_search.cpp:41:3: error: 'iota' is not a member of 'std'
   std::iota(_rank_limits.begin(), _rank_limits.end(), 0);
   ^~~
heuristics/local_search.cpp:71:5: error: 'iota' is not a member of 'std'
     std::iota(number_of_lookups.rbegin(),
     ^~~
heuristics/local_search.cpp:76:5: error: 'partial_sum' is not a member of 'std'
     std::partial_sum(number_of_lookups.begin(),
     ^~~
makefile:28: recipe for target 'heuristics/local_search.o' failed

g++ -std=c++14 -Wpedantic -Wall -O3 -DBOOST_LOG_DYN_LINK -o ../bin/vroom main.o heuristics/mst_heuristic.o heuristics/heuristic.o heuristics/tsp_strategy.o heuristics/christo_heuristic.o heuristics/local_search.o structures/tsp.o utils/exceptions.o utils/logger.o -lboost_system -lboost_regex -lboost_log -lboost_log_setup -lpthread -lboost_thread 
structures/tsp.o: In function `__gnu_cxx::__normal_iterator<char const*, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > boost::re_detail_106000::re_is_set_member<__gnu_cxx::__normal_iterator<char const*, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, char, boost::regex_traits<char, boost::cpp_regex_traits<char> >, unsigned int>(__gnu_cxx::__normal_iterator<char const*, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, __gnu_cxx::__normal_iterator<char const*, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >, boost::re_detail_106000::re_set_long<unsigned int> const*, boost::re_detail_106000::regex_data<char, boost::regex_traits<char, boost::cpp_regex_traits<char> > > const&, bool)':
tsp.cpp:(.text._ZN5boost16re_detail_10600016re_is_set_memberIN9__gnu_cxx17__normal_iteratorIPKcNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEEEEcNS_12regex_traitsIcNS_16cpp_regex_traitsIcEEEEjEET_SH_SH_PKNS0_11re_set_longIT2_EERKNS0_10regex_dataIT0_T1_EEb[_ZN5boost16re_detail_10600016re_is_set_memberIN9__gnu_cxx17__normal_iteratorIPKcNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEEEEcNS_12regex_traitsIcNS_16cpp_regex_traitsIcEEEEjEET_SH_SH_PKNS0_11re_set_longIT2_EERKNS0_10regex_dataIT0_T1_EEb]+0x16a): undefined reference to `boost::re_detail_106000::cpp_regex_traits_implementation<char>::transform_primary[abi:cxx11](char const*, char const*) const'
tsp.cpp:(.text._ZN5boost16re_detail_10600016re_is_set_memberIN9__gnu_cxx17__normal_iteratorIPKcNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEEEEcNS_12regex_traitsIcNS_16cpp_regex_traitsIcEEEEjEET_SH_SH_PKNS0_11re_set_longIT2_EERKNS0_10regex_dataIT0_T1_EEb[_ZN5boost16re_detail_10600016re_is_set_memberIN9__gnu_cxx17__normal_iteratorIPKcNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEEEEcNS_12regex_traitsIcNS_16cpp_regex_traitsIcEEEEjEET_SH_SH_PKNS0_11re_set_longIT2_EERKNS0_10regex_dataIT0_T1_EEb]+0x365): undefined reference to `boost::re_detail_106000::cpp_regex_traits_implementation<char>::transform[abi:cxx11](char const*, char const*) const'
collect2: error: ld returned 1 exit status
makefile:24: recipe for target '../bin/vroom' failed

There is room for improvement in the memory load related to matrix storing (see inputs in #22 and #23). This is a general concern, not limited to the use cases from #23.

Todo: track and optimize the matrices use throughout the execution and refactor the tsp structure.

We should allow to use libOSRM (rather than osrm-routed) as an option. This could hopefully really speed-up things, saving:

• the http request time;
• the table and route result serialization (within OSRM);
• the above results parsing before use in the codebase.

This might be really significant as for small and middle-sized instances the solving time (heuristic + local search) is really very small compared to the times required to retrieve the table and detailed route geometry.

For most operators involved in the local search phase, the strategy is to examine all possible moves and to pick the best improvement.
A significant speed-up might be achieved by looking up the potential move gain in parallel (the computations are independent).

OSRM server address and port are hard-coded to the default values in tsp::get_route_summary so command-line arguments are not used.

Code check DIMENSION is 2, but the as TSPLIB spec write: "Dimension is the numbers of nodes"
http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/DOC.PS

The input should be safer (and also easier) to parse for further feature additions, dropping the query-like input to switch to json.

The syntax is yet to be defined, but should remain easy to maintain and enhance for new features.

Hello,
Error while compiling with mingw32-make:
Main.cpp: 14: 30: fatal error: boost / log / core.hpp
The folder "boost" is yet added to the folder "src"
Thank you for your help,
cordially

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...

I got en error ruining your french_towns.req test set.

terminate called after throwing an instance of 'std::invalid_argument'
  what():  stoul
Abandon (core dumped)

vroom -a 127.0.0.1 -p 5000 -i french_towns.req
terminate called after throwing an instance of 'std::invalid_argument'
  what():  stoul

Program received signal SIGABRT, Aborted.
0x00007ffff71d45f8 in raise () from /usr/lib/libc.so.6
(gdb) where
#0  0x00007ffff71d45f8 in raise () from /usr/lib/libc.so.6
#1  0x00007ffff71d5a7a in abort () from /usr/lib/libc.so.6
#2  0x00007ffff7ae8b3d in __gnu_cxx::__verbose_terminate_handler ()
    at /build/gcc-multilib/src/gcc-5.2.0/libstdc++-v3/libsupc++/vterminate.cc:95
#3  0x00007ffff7ae6996 in __cxxabiv1::__terminate (handler=<optimized out>)
    at /build/gcc-multilib/src/gcc-5.2.0/libstdc++-v3/libsupc++/eh_terminate.cc:47
#4  0x00007ffff7ae69e1 in std::terminate () at /build/gcc-multilib/src/gcc-5.2.0/libstdc++-v3/libsupc++/eh_terminate.cc:57
#5  0x00007ffff7ae6bf8 in __cxxabiv1::__cxa_throw (obj=obj@entry=0x6c7ef0, tinfo=0x7ffff7dcdaa8 <typeinfo for std::invalid_argument>, 
    dest=0x7ffff7afc140 <std::invalid_argument::~invalid_argument()>)
    at /build/gcc-multilib/src/gcc-5.2.0/libstdc++-v3/libsupc++/eh_throw.cc:87
#6  0x00007ffff7b0f9df in std::__throw_invalid_argument (__s=0x425626 "stoul")
    at /build/gcc-multilib/src/gcc-5.2.0/libstdc++-v3/src/c++11/functexcept.cc:82
#7  0x0000000000412fa0 in osrm_wrapper::load_matrix(std::vector<std::pair<double, double>, std::allocator<std::pair<double, double> > > const&) ()
#8  0x000000000040f497 in tsp::tsp(cl_args_t const&) ()
#9  0x00000000004081cc in solve_atsp(cl_args_t const&) ()
#10 0x0000000000403a47 in main ()

For future evolutions, the code structure should allow to:

• define and expose different types of problems in an extensible way;
• add dedicated solving strategies as "plugins", or somehow bind each strategy to the relevant problem.

The current TSP-solving code should be refactored as the first plugin. This probably means adding classes to describe objects that don't exist as such so far (e.g. solutions, maybe routes, jobs, vehicles...).

Dear jcoupey,

Do you plan to add the functionnality to indicate multiple vehicles ?
The best option might be to have a automatic a map zoning with the number of vehicles and calculate the routing of every zones.

Thankyou for your response.

wrong repo

wrong repo

OSRM v5.* API has changed completely. The current code in develop supports both v4 and v5 API but maintaining both is not a long-term option. The question is to decide whether to drop support for v4 in the upcoming v1.0.0 release.

Pros are:

• simplify client code for OSRM queries (and ease maintenance);
• most people that have not switched yet to v5 are in the process to do so;
• the v4 API support has to go at some point, so let's drop it on a major release;
• the ability to use libosrm currently in development in #34 is only compatible with v5. When libosrm has been installed from v4, the build will fail due to missing include files.
• v5 is much better, says the OSRM team ;-)

Cons:

• users stuck with v4 won't be able to use VROOM v1.0.0.

Any views are welcome here.

Add route to JSON result from problem solved with OSRM. Rematching the lat/lon number truncated with the initial input data is not so simple. Please can you output the route attribut as well, something like in the TSP loader.

    route += "\"tour\":[";
    for(auto const& step: tour){
      // Using rank rather than index to describe places.
      route += std::to_string(step + 1) + ",";
    }
    route.pop_back();          // Remove trailing comma.
    route += "],";

Hey, love your work.

vroom -h says -a=ADDRESS -p=PORT, etc, but it should be -a ADDRESS -p PORT

I've been using an older version of vroom for 6 months, now I'm moving all my map stuff into docker containers, and there have been some updates to osrm and vroom since I last compiled them. I worked out osrm api changed and I need to use the vroom develop branch, but it took me a while to workout the exact command to feed into vroom. so here's an example that might help save someone a few minutes.

vroom -a 127.0.0.1 -p 5000 -m car -t 8 '{"vehicles": [{"start": [151.1237, -34.0221], "round_trip": true, "id": 1}], "jobs": [{"id": 1, "location": [151.1237, -34.0221]}, {"id": 2, "location": [151.1578653, -33.8030746]}, {"id": 3, "location": [151.1353032, -33.7160608]}]}'

I'm looking forward to see where you go with this. I started using vroom because it allowed me a to specify a start and end location, at the time osrm didn't let me do that, or I couldn't work out how to make it. Now I see we can specify multiple vehicles, which is starting getting really exciting. When we can specify a time range for a job, and have the ability to pin a job to a vehicle, we will be able to use it for even more work.

Lots of meaty computer science concepts in this project. I'd love to help, but It's a way above my level atm.

It will be interesting to build vroom as library containing only the solver and have the main, tsplib and osrm loaders in a command linked with the lib.

Really pleased to see this - it looks like a great fit with OSRM. Though I'm happy with jsprit (which I use at the moment) I'd love to have something that doesn't require Java.

For my VRP project the following would be good:

• Multiple vehicles
  • ideally with clustering support or similar
  • prefer small number of vehicles with full days (jsprit sometimes issues many vehicles with half-days)
  • start from/return to depot
• Delivery windows (start/end times for each destination)
• Service times (delay at each destination)

I must be missing a library or something? I was cleaning up my dockerfile so I could publish it, and noticed I didn't have pkg-config installed while compiling vroom, so previously vroom built ok, but it didn't build the libosrm part? not sure, but now with pkg-config installed, this is the command being run to build vroom.

g++ -std=c++14 -Wextra -Wpedantic -Wall -O3 -DBOOST_LOG_DYN_LINK -DBOOST_TEST_DYN_LINK -DBOOST_SPIRIT_USE_PHOENIX_V3 -DBOOST_RESULT_OF_USE_DECLTYPE -DBOOST_FILESYSTEM_NO_DEPRECATED -flto=4 -Wall -Wextra -pedantic -Wuninitialized -Wunreachable-code -Wstrict-overflow=1 -D_FORTIFY_SOURCE=2 -fdiagnostics-color=auto -fPIC -ffunction-sections -fdata-sections -std=c++1y -fopenmp -I/usr/local/include -I/usr/local/include/osrm -I/src/osrm-backend/third_party/libosmium/include -I/usr/include/luabind -I/usr/include/lua5.2 -D LIBOSRM=true -c main.cpp -o main.o

and this is the bottom of the output

                 from /usr/include/c++/5/bits/char_traits.h:39,
                 from /usr/include/c++/5/ios:40,
                 from /usr/include/c++/5/istream:38,
                 from /usr/include/c++/5/sstream:38,
                 from main.cpp:10:
/usr/include/c++/5/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_pred<_Predicate>::operator()(_Iterator) [with _Iterator = __gnu_cxx::__normal_iterator<tsplib_loader::Node*, std::vector<tsplib_loader::Node> >; _Predicate = tsplib_loader::tsplib_loader(const string&)::<lambda(const int&)>]':
/usr/include/c++/5/bits/stl_algo.h:120:14:   required from '_RandomAccessIterator std::__find_if(_RandomAccessIterator, _RandomAccessIterator, _Predicate, std::random_access_iterator_tag) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<tsplib_loader::Node*, std::vector<tsplib_loader::Node> >; _Predicate = __gnu_cxx::__ops::_Iter_pred<tsplib_loader::tsplib_loader(const string&)::<lambda(const int&)> >]'
/usr/include/c++/5/bits/stl_algo.h:161:23:   required from '_Iterator std::__find_if(_Iterator, _Iterator, _Predicate) [with _Iterator = __gnu_cxx::__normal_iterator<tsplib_loader::Node*, std::vector<tsplib_loader::Node> >; _Predicate = __gnu_cxx::__ops::_Iter_pred<tsplib_loader::tsplib_loader(const string&)::<lambda(const int&)> >]'
/usr/include/c++/5/bits/stl_algo.h:3815:28:   required from '_IIter std::find_if(_IIter, _IIter, _Predicate) [with _IIter = __gnu_cxx::__normal_iterator<tsplib_loader::Node*, std::vector<tsplib_loader::Node> >; _Predicate = tsplib_loader::tsplib_loader(const string&)::<lambda(const int&)>]'
./loaders/tsplib_loader.h:215:41:   required from here
/usr/include/c++/5/bits/predefined_ops.h:234:30: error: no match for call to '(tsplib_loader::tsplib_loader(const string&)::<lambda(const int&)>) (tsplib_loader::Node&)'
  { return bool(_M_pred(*__it)); }
                              ^
In file included from main.cpp:21:0:
./loaders/tsplib_loader.h:213:68: note: candidate: tsplib_loader::tsplib_loader(const string&)::<lambda(const int&)>
                                        [input_start] (const auto& n){
                                                                    ^
./loaders/tsplib_loader.h:213:68: note:   no known conversion for argument 1 from 'tsplib_loader::Node' to 'const int&'
In file included from /usr/include/c++/5/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/5/bits/char_traits.h:39,
                 from /usr/include/c++/5/ios:40,
                 from /usr/include/c++/5/istream:38,
                 from /usr/include/c++/5/sstream:38,
                 from main.cpp:10:
/usr/include/c++/5/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_pred<_Predicate>::operator()(_Iterator) [with _Iterator = __gnu_cxx::__normal_iterator<tsplib_loader::Node*, std::vector<tsplib_loader::Node> >; _Predicate = tsplib_loader::tsplib_loader(const string&)::<lambda(const int&)>]':
/usr/include/c++/5/bits/stl_algo.h:120:14:   required from '_RandomAccessIterator std::__find_if(_RandomAccessIterator, _RandomAccessIterator, _Predicate, std::random_access_iterator_tag) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<tsplib_loader::Node*, std::vector<tsplib_loader::Node> >; _Predicate = __gnu_cxx::__ops::_Iter_pred<tsplib_loader::tsplib_loader(const string&)::<lambda(const int&)> >]'
/usr/include/c++/5/bits/stl_algo.h:161:23:   required from '_Iterator std::__find_if(_Iterator, _Iterator, _Predicate) [with _Iterator = __gnu_cxx::__normal_iterator<tsplib_loader::Node*, std::vector<tsplib_loader::Node> >; _Predicate = __gnu_cxx::__ops::_Iter_pred<tsplib_loader::tsplib_loader(const string&)::<lambda(const int&)> >]'
/usr/include/c++/5/bits/stl_algo.h:3815:28:   required from '_IIter std::find_if(_IIter, _IIter, _Predicate) [with _IIter = __gnu_cxx::__normal_iterator<tsplib_loader::Node*, std::vector<tsplib_loader::Node> >; _Predicate = tsplib_loader::tsplib_loader(const string&)::<lambda(const int&)>]'
./loaders/tsplib_loader.h:241:41:   required from here
/usr/include/c++/5/bits/predefined_ops.h:234:30: error: no match for call to '(tsplib_loader::tsplib_loader(const string&)::<lambda(const int&)>) (tsplib_loader::Node&)'
  { return bool(_M_pred(*__it)); }
                              ^
In file included from main.cpp:21:0:
./loaders/tsplib_loader.h:239:66: note: candidate: tsplib_loader::tsplib_loader(const string&)::<lambda(const int&)>
                                        [input_end] (const auto& n){
                                                                  ^
./loaders/tsplib_loader.h:239:66: note:   no known conversion for argument 1 from 'tsplib_loader::Node' to 'const int&'
makefile:38: recipe for target 'main.o' failed
make: *** [main.o] Error 1

Probably due to a local search operator being applied in a context where it doesn't make sense.

The TSP-solving code is basically unaware of anything going on before-hand with regard to input parsing and modelling with jobs and vehicles. It just operates on the provided matrix, dealing with indexes that are relative to this matrix.

In some contexts, we might want to only deal with a sub-problem, so we should be able to run the TSP approach on a sub-matrix.

Goals are to:

• address concerns expressed in #59 (comment)
• maybe remove the need for #57

Adapt the OSRM wrapper for the new server API to be released in v5.

Do you plan to support open tour ?

• with different fixed start and stop
• more general case, with fixed or not start and stop

This error is raised if there is a newline before the end of file. It would be much more convenient to allow this when parsing the locations.

I just came around your project and skimmed the code. Good job over all! :)

Here are two minor details I found:

The undirected_graph's constructor takes a matrix<T> by value:

https://github.com/jcoupey/vroom/blob/dc008cd6fdae3b741c1b071a0447f615e75c52ac/src/structures/undirected_graph.h#L39

From what I can tell, you only need a read-only view on the matrix, so taking it by-values creates an unnecessary copy of the matrix. Taking the matrix by const & would suffice for that.

A few lines below the second constructor takes the edges by value and then stores a copy in the member sink attribute:

https://github.com/jcoupey/vroom/blob/dc008cd6fdae3b741c1b071a0447f615e75c52ac/src/structures/undirected_graph.h#L55-L56

This also creates an unnecessary copy that you could avoid by moving the edges into their sink, like _edges{std::move(edges)}. From what I can tell you are only using std::list to efficiently insert at the front, in the matrix-taking constructor. If that is the only reason, then I guess it is more efficient to just use a contiguous std::vector, insert at the end and reverse it once. That is, I would try to avoid std::list where ever possible, and prefer contiguous containers like std::vector.

Hope that helps,
Daniel J H

The reasons for this are discussed in #47.

TL;DR the ability to provide a custom matrix should go into the json API.

Can you figure why the solution is not good on this problem ?

DIMENSION: 4                                                                                                                                
EDGE_WEIGHT_TYPE: EXPLICIT                                                                                                                  
EDGE_WEIGHT_FORMAT: FULL_MATRIX                                                                                                             
EDGE_WEIGHT_SECTION                                                                                                                         
0 2609 2564 2622                                                                                                                            
2750 0 461 13                                                                                                                               
2795 45 0 58                                                                                                                                
2737 493 448 0                                                                                                                              
EOF 

I get

{"computing_times":{"matrix_loading":0,"route":{"heuristic":0,"local_search":0}},"tour":[2,3,4,1],"solution_cost":5865}

But there is a better solution at 5359.

In the symmetric case, trying the move with edges (e_2, e_1) is the same as with (e_1, e_2). So better stop at some point to avoid testing pairs in both orders. This would improve timing on all problems (as even asymmetric instances use this at some point) and might be a huge speed-up for big instances, where local search is the most time-consuming phase.

The change should be made with caution as:

• the two loops should go through the edges in the same order to easily avoid duplicates, without having to remember every pair;
• in the inner loop, going through the edges in the order of the current tour IS mandatory for efficient computation of the cost of the part that has to be reversed (asymmetric case).

Some checks are missing in input_parser, e.g. providing a string as vehicle or job id triggers a rapidjson assert. An explicit error message should be reported.

It would be interesting to evaluate a bit seriously the overall gain provided by using libosrm over osrm-routed. A discussion on this started at #34. Thoughts:

• Comparing on a single instance doesn't make much sense (#34 (comment)).
• The gain is likely problem-size dependant.

Possible benchmarking protocol would be:

1. Pick a set of problem sizes (say every now and then from 20 to 5000 points).
2. Generate a significant bunch of random instances for each size.
3. Solve all using both libosrm and osrm-routed on the same osrm files.
4. Compare all relevant indicators: overall computing time, loading time (includes table request) and routing time (for route request).

The demo page doesn't work. I tried both Chrome and Firefox, and clicking or uploading a file with Lat, Lng and it doesn't do nothing.

Could someone check it?