Vroom Versions Save

Added

Features

• Support for cost per km for vehicles (#908)
• Support for max_distance at vehicle level (#354)
• MAX_DISTANCE violation cause in plan mode (#995)
• Recommendation on how to cite in publications (#943)
• Changelog sub-categories (#1018)

Core solving

• PriorityReplace local search operator (#988)
• Experimental TSPFix local search operator (#737)

Internals

• Store distance matrices (#956)
• Default radius of 35km for OSRM snapping (#922)
• Support for URL path in host (#966)

Changed

Core solving

• Significant speedup by pruning local search moves (#509)
• Reduce compute_best_route_split_choice complexity (#962)
• Eval::operator< sorts on cost, then duration (#914)
• Improved vrptw::PDShift implementation (#852)
• Refactor heuristics to be able to operate on a subset of jobs and vehicles (#837)
• Account for vehicle/job compatibility in heuristic regrets values (#982)
• Slightly reduce computing times for SWAP* operator (#987)
• Refactor RouteSplit operator (#996)

Internals

• Switch to C++20 (#851)
• Exposed internal variables to get feature parity for pyvroom (#901)
• Improve some error messages (#848)
• Improved error messages for file-related IO errors (#553)
• Add job id to error message for unreachable step (#946)
• Reserve vector capacity whenever possible (#915)
• Distances in output are from internal matrices, not routing requests (#957)
• Remove unused tw_length member from Job and associated code
• Scale TimeWindow::length from UserDuration to Duration (#1015)

Routing

• ORS: (previously) hard-coded /ors/v2 slug now has to be added to the path using -a (#1036)

Dependencies

• Submodule and update Rapidjson (#929)
• Update polylineencoder to v2.0.1 (#931)
• Update polylineencoder to v2.0.2 (#1006)
• Update cxxopts to 3.1.1 (#997)

CI

• Update GitHub Actions (#857)
• Setup a clang-tidy workflow (#789)
• Add running apt-get update in CI jobs (#863)
• Update formatting script to use clang-format 14 (#894)
• Update gcc to version 12 in CI (#1002)
• Update clang to version 15 in CI (#1022)

Fixed

Core solving

• max_travel_time parameter not taken into account in edge case (#884)
• max_travel_time not accounted for with vehicle steps in solving mode (#954)
• max_travel_time not accounted for in RouteSplit (#941)
• Wrong capacity checks in RouteSplit (#981)
• Overflow related to scaling default time windows (#1020)

Internals

• Internal matrix problem with inconsistent location_index and location values (#909)
• Silent fail on invalid output file (#553)
• Comparison of index-based and coordinates-based locations (#935)
• Meaningless location_index provided in output for break steps (#877)

CI

• Address sonarcloud "bugs" reports (#984)
• Address some sonarcloud "code smell" reports (#986)

Added

• Support for max_travel_time at vehicle level (#273)
• Support for vehicle fixed costs (#528)
• Support for cost per hour for vehicles (#732)
• Support for max_load constraint at break level (#786)
• RouteSplit local search operator (#788)
• Advertise libvroom in README and wiki (#42)

Changed

• Use new struct to evaluate edges internally (#738)
• Use std::chrono::milliseconds for Timeout value (#728)
• Use struct for storing Coordinates instead of an std::array (#730)
• Refactor SolutionIndicators struct (#750)
• Do not duplicate local search for identical heuristic solutions (#750)
• Add message on invalid routing response (#764)
• Consistent exception type on invalid profile (#771)
• Pass zero amount directly instead of its size (#776)
• Add named constants for default threads number and exploration level (#805)
• Refactor TSP cost functions (#812)
• CI builds now use clang++ 14 and g++ 11 on Ubuntu 22.04 (#816)
• Refactor CVRP::solve and VRPTW::solve functions (#818)
• Refactor CostWrapper (#828)

Fixed

• Missing break validity check (#754)
• Unecessary waiting with multiple breaks and shipments (#840)
• Mark JobAmount and JobTime comparison operators as const (#724)
• Update ssl_send_and_receive to throw RoutingExceptions (#770)
• Timeout not observed with multiple long heuristics per thread (#792)
• Wrong validity check range in vrptw::MixedExchange (#821)
• Underflow in insertion regrets (#831)
• Crash with missing location coordinates and only costs custom matrix (#826)

Added

• IntraTwoOpt local search operator (#706)
• description key for unassigned tasks in output, if provided (#403)
• location_index key for unassigned tasks and each step, if provided (#625)
• Shared target to makefile, for creating Position Independent Code (#617)
• Exposing some internals for Python through compile flags (#640)
• Stats on local search operators use for dev/debug purposes (#658)
• Project can be compiled without routing support to limit dependencies (#676)
• Internal max_tasks constraints derived from input to speed up local-search (#648)

Changed

• Prune local search moves based on TW constraints (#583)
• Prune local search moves based on capacity constraints (#709)
• Refactor exception class (#639)
• CI builds now run against libosrm v5.26.0 (#651)
• Reduce computing time on PDPTW benchmarks by around 20% (#559)
• Change Input and parser signature to simplify downstream usage (#665)
• Consider move options in SWAP* that were previously wrongly discarded (#682)
• Use cxxopts as command line parser instead of getopt (#602)
• Change polylineencoder usage to submodule instead of plain header (#686)

Fixed

• Remove duplicate definition of LocalSearch (#638)
• Move priority check to Job constructor instead of input parser (#628)
• Wrong index values without custom matrix (#683)
• Assignments instead of equality checks in some plan mode assertions (#701)
• Initialization of single-entry matrix (#699)

Added

• setup key for tasks to refine service time modeling (#358)
• max_tasks key limiting route size at vehicle level (#421, #566)
• Support for custom cost matrices (#415)
• Number of routes in solution summary (#524)
• Implementation for extended SWAP* local search operator (#507)
• -l command-line flag for user-provided timeout (#594)
• Ability to start the search from user-defined solution (#376)
• Github Actions CI (#436)
• Check for libvroom example build in CI (#514)

Changed

• vehicle.steps are now used in solving mode (#606)
• CI builds now run on Ubuntu 20.04 (#455)
• Simplified time window handling logic in TWRoute (#557)

Removed

• Travis CI builds (#436)
• Exchange local search operator (#507)

Fixed

• "Infeasible route" error while an existing route plan exists (#506)
• Break omitted with no other time window (#497)
• Biased evaluation in try_job_additions (#572)
• Routing error with custom matrix and -g (#561)
• Crash on empty custom matrix (#570)
• Properly allow empty skills arrays (#586)
• Restrict speed_factor in the range (0, 5] (#591)

Added

• Support for heterogeneous vehicle routing profiles (#394) (#490)
• Optional speed_factor key for vehicle-level tuning (#450)
• Support Valhalla as routing engine (#306)
• Report type for unassigned tasks in output (#469)

Changed

• A mix of empty and non-empty skills arrays is allowed in input (#460)
• Formatting script updated to use version 10 of clang-format (#452)
• vroom will now read json input from stdin if no other input is specified (#457)
• Clearer error message with invalid json response from http routing request (#471)

Deprecated

• Top-level matrix key should be replaced using the new matrices syntax (#450)

Fixed

• Compatibility with Visual Studio 2019 (#448)
• The pd_shift operation can now insert a shipment at the end of a route (#462)
• Truncated distance value for end step (#463)
• Zero distance value for last break in open-ended route (#475)
• Multi-thread exception handling (#417, #478)

Added

• Ability to choose ETA and report violations for custom routes using -c (#430)
• Custom route description using new steps key for a vehicle in input (#430)
• A violations object is reported in output at step, route and summary level (#430)
• libglpk used as an optional dependency, required for -c (#430)

Changed

• Reduce computing time by refactoring LocalSearch::try_job_additions (#392)
• Reduce build time by refactoring includes (#425)
• Improve error message with wrong profile using libosrm (#397)
• Check for duplicate ids across tasks of the same type: job, pickup, delivery (#430)
• Check for duplicate ids across break tasks for the same vehicle (#430)
• Report service and waiting_time for all step objects in output (#430)
• Always report a start and end step for the route, regardless of vehicle description (#430)

Fixed

• Rapidjson assert on invalid syntax for first vehicle (#418)

Added

• Local search move removing a job in a route and adding an unassigned one (#324)
• Support for string description of vehicles and tasks (#235)
• Priority sum report in output (#390)

Changed

• Improved job earliest/latest dates handling internally (#330)

Fixed

• Break ordering problem (#385)
• Obvious suboptimal solution with many unassigned jobs (#319)
• Documentation mismatch (#361)
• Profile type not checked in input (#355)
• Error reported by UBSan (#371)

Added

• Support for (multiple) driver breaks at vehicle level (#186)
• Dependency to libasio, replacing boost/asio (#325)
• More details on features and workflow in README (#335)

Changed

• Switch to C++17 (#311)
• Use std::optional and drop dependency to boost/optional (#312)
• Refactor routing wrapper classes (#320)

Deprecated

• Steps job key is replaced by id for consistency with breaks

Removed

• Drop boost dependency (#325)

Fixed

• Erroneous call to TSP code with amount-less shipments (#333)
• Missing propagation of ealiest/latest dates in corner case (#339)

Added

• Support for pickup and delivery tasks (#274)
• shipments array in input (#274)
• Use https for routing requests over port 443 (#289)
• New local search operator for route exchange (#288)

Changed

• Steps type in json output can also have value pickup and delivery (#274)
• Extended range for valid priority values (#287)
• Use operator&& for short-circuit evaluation (#293)
• Earlier local search aborts based on incompatibilities (#281)
• Travis script update (#301)

Fixed

• Missing valid moves for intra Or-opt (#286)
• Unwanted routing engine request with 1x1 custom matrix (#291)
• Error on single-location table request (#295)

Added

• Support for mixing independent pickups and deliveries (#241)
• pickup and delivery keys for job in input and for route and summary in output (#262)
• load key at step level in output (#262)
• priority key for jobs to gain some control on which jobs are unassigned (#246)
• HttpWrapper class to factor code previously duplicated across routing wrappers (#224)

Changed

• Speed up solving by 25% for CVRP and up to 30% for VRPTW benchmark instances (#255)
• Update Travis configuration to use Ubuntu Bionic (#260)
• Cut down validity checks time (#266)

Deprecated

• amount key at job level in input and at summary and route level in output (#262)

Removed

• Clustering heuristics for CVRP (#267)

Fixed

• Implicit instantiation of undefined template error for macos g++ compiler (#231)
• Parsing vehicle ids as uint64_t (#228)
• osrm::EngineConfig initialization for use with recent libosrm versions (#259)