DOCSEARCHbyAlgolia
Submit Docs

VRP Solver

repository·master·Indexed 19 days ago

https://github.com/reinterpretcat/vrp

A solver for various versions of the Vehicle Routing Problem (Rich VRP) featuring custom hyper- and meta-heuristic implementations. It provides a core API for defining custom constraints and objective functions, along with specialized crates for scientific benchmarks (solomon, lilim) and real-world pragmatic JSON formats. The solver is accessible via a Rust API, a command-line interface (vrp-cli), and interop bindings for Python, Java, Kotlin, and JavaScript.

Tokens
70.6K
Snippets
218
Records
353
Agent score
66%

What's inside vrp

  1. Overview of the vrp-core crate

    master
    The core crate provides the fundamental building blocks required to construct heuristics and metaheuristics for solving the Vehicle Routing Problem (VRP). It serves as the foundational layer for more specialized packages in the VRP ecosystem.

  2. Overview of vrp-pragmatic

    master
    The vrp-pragmatic crate is designed to solve real-world variations of the Vehicle Routing Problem (VRP). It provides a high-level interface that allows users to define and specify their routing problems using a simplified pragmatic JSON format, making it easier to model complex real-world constraints without deep algorithmic configuration.

  4. Use rosomaxa for generalized hyper heuristics

    master
    The rosomaxa crate provides generalized hyper heuristics and helper functionality designed to assist in building solvers for various optimization problems. It serves as a toolkit for implementing high-level heuristic strategies that can be applied across different problem domains.

  5. Use the VRP CLI for Vehicle Routing Problem solving

    master
    The vrp-cli crate provides a command-line interface to access the Vehicle Routing Problem (VRP) solver functionality. It allows users to interact with the solver directly from the terminal without writing custom code.

  6. What is the ROSOMAXA algorithm?

    master
    ROSOMAXA (Routing Optimizations with Self-Organizing Maps And EXtrAs) is a custom evolutionary algorithm designed to maintain population diversity and avoid premature convergence. It achieves this by using a Growing Self-Organizing Map (GSOM) to cluster diverse solutions and a dynamic hyper-heuristic powered by reinforcement learning to select appropriate meta-heuristics for a given problem formulation.

  7. What is the Vehicle Routing Problem (VRP)?

    master
    The Vehicle Routing Problem (VRP) is a combinatorial optimization and integer programming problem focused on determining the optimal set of routes for a fleet of vehicles to deliver to a specific set of customers. It is a generalization of the Traveling Salesman Problem (TSP). Because solving VRP optimally is NP-hard, this project provides tools to handle large-scale real-world problems, often utilizing heuristics to manage complexity and frequency.

  9. Design principles of the VRP project

    master

    The project is designed with a focus on performance and extensibility to support 'Rich VRP' (a wide range of VRP variations). Developers can extend the solver's capabilities through several key extension points:

    • Custom constraints: Define specific rules for vehicle movement or customer service.
    • Objective functions: Customize what the solver is trying to optimize (e.g., cost, time, load).
    • Acceptance criteria: Define the logic for accepting new solutions during the optimization process.

  10. Default objective behavior

    master

    The solver applies different default objective sets depending on the problem data:

    1. Standard Default: Minimizes unassigned jobs, then minimizes tours, then minimizes total cost.
    2. With Job Values: If any job has a non-zero value, the solver prioritizes maximize-value.
    3. With Job Order: If job task order is specified, it is added to the list after the minimize-tours objective.

  11. How ROSOMAXA uses GSOM for solution clustering

    master

    ROSOMAXA implements a custom Growing Self-Organizing Map (GSOM) to cluster discovered solutions. Unlike standard clustering that focuses on objectives, ROSOMAXA clusters based on solution geometry (characteristics).

    Key features include:

    • Elitist Nodes: Each node maintains a small population of solutions selected via an elitism approach.
    • Geometry-based Splitting: Nodes are created and split based on specific VRP domain characteristics (e.g., vehicle load variance, route durations, or amount of routes).
    • Network Compaction: To maintain a healthy exploration-exploitation ratio, the network is periodically rebalanced using a "decimation" approach, where specific columns/rows are removed and surviving cells are moved toward the center (coordinate (0, 0)).

  12. Understand constructive heuristics for initial solution building

    master

    To begin the optimization process, the solver uses constructive heuristics to build initial solutions from scratch. These algorithms insert jobs into tours to create a starting point for metaheuristics.

    Built-in constructive heuristics include:

    • Variations of the Clark & Wright Savings algorithm
    • Regret insertion
    • Insertion with blinks
    • Nearest neighbor
    • Random insertions

    For large-scale VRPs, the insertion algorithms use SelectionSamplingSearch to optimize job insertion evaluation and prevent the performance degradation associated with purely greedy evaluation.