Example 17: Vehicle routing with time windows

Problem and data

This demo models a capacitated vehicle-routing problem with service time windows. The current source contains one origin node, 100 demand nodes, one end node, and 25 identical vehicles. The origin and end are both at $(40, 50)$ with time window $[0, 1236]$ . Each vehicle has capacity 200 and fixed-used cost 500. Every demand node has a positive integer demand, a source-provided time window, and service duration 90.

The source uses Euclidean geometry: Node.distance is the distance between the two Point2 positions, and both Node.cost and Node.time return that distance. Thus travel cost and travel time share the same distance unit; there is no independent cost or speed matrix.

Sets and parameters

Let $N$ be all 102 nodes, $O = {o}$ the origin, $E = {e}$ the end, $D = N ∖ (O \cup E)$ the 100 demand nodes, and $K$ the 25-vehicle set. Let

A = {(i, j) \in N^{2} : i \notin E, j \notin O, i \neq j} .

be the allowed arc set implemented by the source. For demand node $j$ , $q_{j}$ is its integer demand and $h_{j} = 90$ is its service duration; $q_{o} = q_{e} = 0$ and the origin/end service duration is zero. Each node has source data $(p o s i t i o n_{i}, [e_{i}, l_{i}])$ . For vehicle $k$ , $Q_{k} = 200$ and $F_{k} = 500$ .

Decision variables

For $(i, j) \in A$ and $k \in K$ :

x_{i j k} \in {0, 1}

indicates that vehicle k uses arc $i \to j$ . The source creates BinVariable3 over all node pairs and vehicles, fixes disallowed entries to false, and registers only the allowed entries.

For every $i \in N, k \in K$ , $s_{i k} \in R_{\geq 0}$ is the service-start time, implemented by URealVariable2. Every $s_{i k}$ is bounded again by the node's time-window constraints.

Intermediate values

For each vehicle $k$ and demand node $d$ :

O r i g i n_{k} = \sum_{j : (o, j) \in A} x_{o j k}, D e s t i n a t i o n_{k} = \sum_{i : (i, e) \in A} x_{i e k},

I n_{d k} = \sum_{i : (i, d) \in A} x_{i d k}, O u t_{d k} = \sum_{j : (d, j) \in A} x_{d j k} .

For each demand node $d$ :

S e r v i c e_{d} = \sum_{k \in K} \sum_{j : (d, j) \in A} x_{d j k} .

For each vehicle:

C a p a c i t y_{k} = \sum_{i \in N} \sum_{j \in N} q_{j} x_{i j k} .

The source registers two objectives:

U s e d C o s t = \sum_{k \in K} F_{k} O r i g i n_{k}, T r a v e l C o s t = \sum_{k \in K} \sum_{(i, j) \in A} d i s t a n c e_{i j} x_{i j k} .

Objective

Demo17 calls minimize twice, first for UsedCost and then for TravelCost. The source does not construct a weighted sum or document a scalar coefficient between them; the exact multi-objective handling is left to the current model/solver policy.

Constraints and domain

Vehicle use and route flow:

O r i g i n_{k} \leq 1, D e s t i n a t i o n_{k} \leq 1 (\forall k \in K),

I n_{d k} = O u t_{d k} (\forall d \in D, k \in K),

S e r v i c e_{d} = 1 (\forall d \in D) .

The source implements the equality $I n = O u t$ as both greater-than-or-equal and less-than-or-equal constraints. For each $i, j \in N$ and $k \in K$ , it adds the time implication with the source's big-M:

s_{i k} + h_{i} + d i s t a n c e_{i j} - M (1 - x_{i j k}) \leq s_{j k}, M = 1236.

For every node and vehicle:

e_{i} \leq s_{i k} \leq l_{i} (\forall i \in N, k \in K),

and for every vehicle:

C a p a c i t y_{k} \leq Q_{k} = 200.

Disallowed arcs are fixed to zero before these expressions are registered. The source still creates time constraints over all node pairs, exactly as shown; the fixed-zero entries make those implications inactive for disallowed arcs.

Implementation differences and notes

The source builds the model through initVariable, initSymbol, initObject, initConstraint, solve, and analyzeSolution. It uses current core symbols and solves with ScipLinearSolver configured with a 300-second time limit. The two objective registrations, the 1236 big-M value, the allowed-arc filtering, and the nonnegative real time variables are implementation facts. This core demo is not a generic VRPTW formulation with optional customers: every demand node is required exactly once.

Expected result

A successful solve returns routes and service times for all 100 demand nodes, respecting each source time window and each vehicle's capacity. The current build test verifies model construction only; it does not assert a route list, objective values, or a unique optimum. Running this instance can be expensive and is subject to the five-minute solver limit.

Minimal current Kotlin example

kotlin

import kotlin.time.Duration.Companion.seconds
import fuookami.ospf.kotlin.utils.concept.*
import fuookami.ospf.kotlin.multiarray.*
import fuookami.ospf.kotlin.math.*
import fuookami.ospf.kotlin.math.algebra.number.*
import fuookami.ospf.kotlin.math.algebra.value_range.*
import fuookami.ospf.kotlin.math.geometry.*
import fuookami.ospf.kotlin.math.geometry.point2
import fuookami.ospf.kotlin.math.symbol.operation.*
import fuookami.ospf.kotlin.math.symbol.polynomial.*
import fuookami.ospf.kotlin.core.model.intermediate.*
import fuookami.ospf.kotlin.core.model.mechanism.*
import fuookami.ospf.kotlin.core.solver.config.*
import fuookami.ospf.kotlin.core.solver.scip.*
import fuookami.ospf.kotlin.core.symbol.*
import fuookami.ospf.kotlin.core.variable.*
import fuookami.ospf.kotlin.example.solveLinearMetaModel

val model = LinearMetaModel<Flt64>("demo17", converter = flt64Converter)
val x = BinVariable3("x", Shape3(nodes.size, nodes.size, vehicles.size))
for (from in nodes) for (to in nodes) for (vehicle in vehicles) {
    val xi = x[from, to, vehicle]
    if (from !is EndNode && to !is OriginNode && from != to) model.add(xi)
    else xi.range.eq(false)
}
val s = URealVariable2("s", Shape2(nodes.size, vehicles.size))
model.add(s)
val origin = LinearIntermediateSymbols1<Flt64>("origin", Shape1(vehicles.size)) { i, _ ->
    LinearExpressionSymbol(
        sum(nodes.filterIsInstance<OriginNode>().flatMap { node -> x[node, _a, vehicles[i]] }),
        name = "origin_$i"
    )
}
val destination = LinearIntermediateSymbols1<Flt64>("destination", Shape1(vehicles.size)) { i, _ ->
    LinearExpressionSymbol(
        sum(nodes.filterIsInstance<EndNode>().flatMap { node -> x[_a, node, vehicles[i]] }),
        name = "destination_$i"
    )
}
val service = LinearIntermediateSymbols1<Flt64>("service", Shape1(nodes.size)) { i, _ ->
    LinearExpressionSymbol(
        sum(nodes.filterIsNotInstance<OriginNode, Node>().flatMap { node -> x[nodes[i], node, _a] }),
        name = "service_$i"
    )
}
val capacity = LinearIntermediateSymbols1<Flt64>("capacity", Shape1(vehicles.size)) { i, _ ->
    LinearExpressionSymbol(
        sum(nodes.flatMap { from ->
            nodes.mapNotNull { to -> (to as? DemandNode)?.demand?.let { it * x[from, to, vehicles[i]] } }
        }),
        name = "capacity_$i"
    )
}
model.add(origin)
model.add(destination)
model.add(service)
model.add(capacity)
model.minimize(sum(vehicles.map { it.fixedUsedCost * origin[it] }), "used cost")
model.minimize(
    sum(nodes.flatMap { from -> nodes.map { to -> from.cost(to) * sum(x[from, to, _a]) } }),
    "trans cost"
)
for (vehicle in vehicles) model.addConstraint(origin[vehicle] leq 1)
for (node in nodes.filterIsInstance<DemandNode>()) {
    model.addConstraint(service[node] eq 1)
    for (vehicle in vehicles) {
        model.addConstraint(inFlow[node, vehicle] geq outFlow[node, vehicle])
        model.addConstraint(inFlow[node, vehicle] leq outFlow[node, vehicle])
    }
}
for (vehicle in vehicles) {
    model.addConstraint(destination[vehicle] leq 1)
    model.addConstraint(capacity[vehicle] leq vehicle.capacity)
}
val m = nodes.filterIsInstance<EndNode>().maxOf { it.timeWindow.upperBound.value.unwrap() }
for (from in nodes) for (to in nodes) for (vehicle in vehicles) {
    model.addConstraint(
        s[from, vehicle] +
            ((from as? DemandNode)?.serviceTime ?: UInt64.zero).toFlt64() +
            from.time(to) -
            m.toFlt64() * (1 - x[from, to, vehicle]) leq s[to, vehicle]
    )
}
for (node in nodes) for (vehicle in vehicles) {
    model.addConstraint(s[node, vehicle] geq node.timeWindow.lowerBound.value.unwrap())
    model.addConstraint(s[node, vehicle] leq node.timeWindow.upperBound.value.unwrap())
}

suspend fun solve() = solveLinearMetaModel(
    ScipLinearSolver(config = SolverConfig(time = 300.seconds)),
    model
)

Source and verification

Kotlin/Rust correspondence

Rust counterpart: src/core/demo17.rs

The Rust file is an independent compact VRPTW sample: 4 customers, 3 vehicles (capacity 25, fixed cost 100), Big-M 500, and one combined cost objective. The current Kotlin implementation uses 100 customers/102 nodes, 25 vehicles (capacity 200, fixed cost 500), Big-M 1236, and separate used/travel objective registrations; do not share the data table or claim model-instance equivalence.

Kotlin

kotlin

// See the linked Kotlin implementation for the complete model.
`` 

```rust [Rust]
// See the linked Rust implementation for the equivalent model.
``

Example 17: Vehicle routing with time windows ​

Problem and data ​

Sets and parameters ​

Decision variables ​

Intermediate values ​

Objective ​

Constraints and domain ​

Implementation differences and notes ​

Expected result ​

Minimal current Kotlin example ​

Source and verification ​

Kotlin/Rust correspondence ​