← Back
Home › Systems › Transport, logistics and mobility

vehicle-routing

vehicle route optimization

OR-Tools VRP

SystemTechniques · 10Primitives · 16 vehicle-routing Contraction hierarchies (shortcut-b…graphs · medium: Rank the nodes, remove them one by one while adding shortcut edges that keep distances intact, then answer queries with two tiny searches that only climb the ranking.›Column generationoptimization · medium: Solve a huge LP by keeping only a few columns and pricing new ones from a subproblem until none can improve; gives the Dantzig-Wolfe bound.›Constraint propagation (constraint…optimization · medium: Variables with finite domains, propagators that prune impossible values to a fixpoint, and backtracking search with trail undo between decisions.›Guided local searchoptimization · medium: Penalize frequent solution features to escape local optima in routing and schedulingLarge neighbourhood search (ruin an…optimization · medium: Repeatedly remove a chunk of a solution and rebuild it with a heuristic or exact solver; learn which operator pairs pay off.›Local search 2opt or optoptimization · medium: 2-opt, Or-opt, relocate and swap neighborhoods with fast delta evaluation for routesMixed-integer programming (branch a…optimization · medium: Solves LPs with integer variables by solving the LP relaxation, branching on a fractional variable, and pruning subtrees whose LP bound cannot beat the incumbent.›d-ary heapdata-structures · low: Array heap with d children per node (d = 4 typical): half the binary heap's depth, siblings in one cache line, faster priority queues.›Dijkstra's algorithmgraphs · low: Single-source shortest paths with non-negative edge weights by settling vertices in order of distance with a priority queue.›Simplex methodoptimization · low: Solves linear programs by walking along the edges of the feasible polytope from vertex to vertex, one basis swap (pivot) at a time; the workhorse behind MIP solvers.›PRNGs (PCG, xoshiro)numerics · low: Small, fast, statistically strong non-cryptographic generators: PCG32 and xoshiro256**, with seeding, parallel streams and unbiased ranges.›Savings algorithm clarke wrightoptimization · low: Clarke-Wright savings construction heuristic for vehicle routesTime-window feasibilityoptimization · low: Keep earliest/latest start and slack per segment so "does this insertion or move keep every window?" costs O(1) instead of a walk down the sequence.›Subset sum dpoptimization · low: Subset-sum / knapsack DP for matching one amount to a combination of manyInterval arithmeticnumerics · low: Rigorous bounds with outward rounding; root isolation and robust geometric testsTwo watched literalsoptimization · low: Unit propagation for SAT that watches just two literals per clause, so backtracking costs nothing and long clauses are rarely touched.›Journaled state revertstorage · low: Undo journal of state writes enabling nested checkpoints and cheap revertSwiss tabledata-structures · low: Open-addressing hash table that filters 8-16 slots at once with 1-byte hash tags and SIMD, giving fast lookups at 87.5 % load.›k-d treegeometry · low: A binary tree that splits k-dimensional points by one coordinate per level, giving fast nearest-neighbour and box queries on static low-dimensional data.›Floating-point errornumerics · low: How IEEE 754 rounding error accumulates and how to contain it: compensated (Kahan/Neumaier) and pairwise summation, error-free transformations with FMA, ULP comparisons.›Fast hash functionsdata-structures · low: Non-cryptographic hashes built from 64×64→128-bit multiplies and xor-shifts; pick by key size, trust level and whether the hash is persisted.›Sparse matrices (CSR)numerics · low: Compressed sparse row stores only nonzeros as row pointers, column indices and values; SpMV streams them once, so it is memory-bandwidth bound.›LU and Cholesky factorizationnumerics · low: Factor A = PLU (any square matrix, partial pivoting) or A = LLᵀ (SPD) once in O(n³), then solve each right-hand side in O(n²).›+ 3 more techniques

Similar systems

Share the most building blocks with this one.

traffic-sim 18 %hospital-scheduling 17 %transportation-management 17 %container-terminal 16 %constraint-solver 15 %

In-house systems

Named systems of this kind at large companies, with their paper or write-up.

ORIONUPS