How to extend solver

This section's intention is to give a very brief explanation of some key concepts which might be needed for adding an extra feature on top of existing logic. For more detailed information, check the corresponding main crates documentation or source code

Constrains & objectives

A Vehicle Routing Problem used to consist of various constraints and objectives functions, such as:

  • capacity constraint
  • time window constraint
  • job's total value maximization
  • cost/duration/distance minimization
  • etc.

Internally, they can be divided into different groups:

  • hard constraints: a problem invariants which must be hold. Examples: vehicle capacity, job time window.
  • soft constraints: a problem variants which should be either maximized or minimized. Examples: job assignment, served job's total value.
  • objectives: an objective of optimization. Typically, it is hierarchical: first, try to assign all jobs, then reduce the total cost of serving them
  • state: an auxiliary logic to cache some important state and retrieve it faster during search

Under the hood, a feature concept combines all these groups. This is based on observation, that many features requires constraint and objective defined at the same time.

A feature concept

Let's take a brief look at some example: a total job value feature, which purpose to maximize value of assigned jobs. Here, each job has some associated value (or zero if it is not specified) and the purpose is to maximize it.

The following code below utilizes FeatureBuilder to construct the feature:

    FeatureBuilder::default()
        .with_name(name)
        .with_objective(MaximizeTotalValueObjective {
            estimate_value_fn: Arc::new({
                let job_read_value_fn = job_read_value_fn.clone();
                let sign = -1.;
                move |route_ctx, job| {
                    sign * match &job_read_value_fn {
                        JobReadValueFn::Left(left_fn) => (left_fn)(job),
                        JobReadValueFn::Right(right_fn) => (right_fn)(route_ctx.route().actor.as_ref(), job),
                    }
                }
            }),
        })
        .with_constraint(MaximizeTotalValueConstraint { merge_code, job_read_value_fn, job_write_value_fn })
        .build()

This builder gets:

  • a unique feature name
  • dedicated objective function which counts value and prefers solutions where it is maximized
  • a dedicated constraint which enforces some problem invariants regarding job value (in this case, only for proximity clustering)

Additionally, the builder accepts FeatureState. Check existing features and vrp-core/examples for more details.

TODO: expand example