vroom-project / vroom Goto Github PK
View Code? Open in Web Editor NEWVehicle Routing Open-source Optimization Machine
Home Page: http://vroom-project.org/
License: BSD 2-Clause "Simplified" License
Vehicle Routing Open-source Optimization Machine
Home Page: http://vroom-project.org/
License: BSD 2-Clause "Simplified" License
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
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.
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:
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:
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 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.
For future evolutions, the code structure should allow to:
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...).
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
Use a library like rapidjson to handle properly the json output from OSRM.
Drop lat,lon order in both input and output would make things more consistent w.r.t.:
geojson
standard;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:
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...
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.
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?
Some atsp sample from http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ ends in seg fault caused by stack overflow.
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 += "],";
The reasons for this are discussed in #47.
TL;DR the ability to provide a custom matrix should go into the json API.
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
vroom/src/problems/tsp/tsp.cpp
Line 17 in 9c138af
tsp
instance. This copy is currently mandatory as we don't want to mess the original and as the matrix is modified to handle the forced start and end cases. This comes at a cost on performance and memory requirements, especially for big instances.
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.
Discussion initiated from PR #22. Related commits to be found in branch experimental_huge_instances
.
OSRM server address and port are hard-coded to the default values in tsp::get_route_summary so command-line arguments are not used.
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.
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.
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).
wrong repo
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:
Adapt the OSRM wrapper for the new server API to be released in v5.
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
NAME: vroom
TYPE: ATSP
DIMENSION: 1
EDGE_WEIGHT_TYPE: EXPLICIT
EDGE_WEIGHT_FORMAT: FULL_MATRIX
EDGE_WEIGHT_SECTION
0
EOF
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 , 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
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 ()
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.
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.
Probably due to a local search operator being applied in a context where it doesn't make sense.
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.
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.
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
We should allow to use libOSRM (rather than osrm-routed) as an option. This could hopefully really speed-up things, saving:
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.
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:
wrong repo
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.
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.
Do you plan to load arbitrary matrix or TSPLIB file format ?
Do you plan to support open tour ?
Some instances (not all) produce a segfault. Probably related to the change introduced in f1b8edc.
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
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:
Possible benchmarking protocol would be:
libosrm
and osrm-routed
on the same osrm
files.table
request) and routing time (for route
request).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:
Cons:
Any views are welcome here.
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.
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...
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.