VRP context model

1. Overview

The VRP context defines customers, depots, vehicle types, routes, and resource semantics shared by route generation and route compilation. It validates data and routes; it does not build the restricted master problem.

1. Dependent Contexts

Input adapters supply a unit-normalized instance. Calculation policies supply distance, travel time, and cost.

2. Concepts / Entities

1. Customers and Depots

$q_{i}$ : Demand of customer $i$ , measured in a common load unit.

$[e_{i}, l_{i}]$ : Permitted service-start window of customer $i$ ; $s_{i}$ is its service duration.

Depots define route endpoints and applicable time ranges. They are not customers requiring coverage.

2. Vehicle Types and Routes

$Q_{v}$ : Capacity of vehicle type $v$ ; $m_{v}$ is the available vehicle count; $f_{v}$ is the fixed cost of using one vehicle.

Route $r$ is a depot-to-depot visit sequence for a specified vehicle type. $a_{i r}$ records whether it visits customer $i$ .

3. Variables

1. Decision Variables

This context declares no solver decision variables. Route usage $x_{r}$ belongs to route compilation.

2. Auxiliary Variables

This context declares no auxiliary solver variables. Route load, service times, and cost are domain calculations, not additional master variables.

4. Predicates

$customer (n)$ : Node $n$ is a customer.

$depot (n)$ : Node $n$ is a depot.

$visits (r, i)$ : Route $r$ visits customer $i$ .

$elementary (r)$ : Route $r$ visits no customer more than once.

5. Sets

$C$ : Customers; $V$ : vehicle types; $N$ : customer and depot nodes.

$A_{v}$ : Directed arcs permitted for vehicle type $v$ .

$R_{v}$ : Feasible routes of type $v$ ; $R$ is their union.

$C_{r}$ : Customers visited by route $r$ ; $A_{r}$ : its ordered traversed arcs.

6. Intermediate Values

1. Load and Coverage Coefficients

Route load is the total demand of its visited customers. Coverage coefficients are route data, not binary master variables.

L_{r} = \sum_{i \in C_{r}} q_{i}, a_{i r} = {\begin{cases} 1, & i \in C_{r}, \\ 0, & i \notin C_{r} . \end{cases}

2. Arrival, Waiting, and Service

Given travel time $τ_{i j}^{v}$ for vehicle type $v$ , arrival, service start, and departure at node $j$ after node $i$ are:

t_{j}^{a r r} = t_{i}^{d e p} + τ_{i j}^{v}, t_{j}^{s t a r t} = max {t_{j}^{a r r}, e_{j}}, t_{j}^{d e p} = t_{j}^{s t a r t} + s_{j} .

Early arrival permits waiting. A service-start window must not be interpreted as a prohibition on early arrival.

3. Route Cost

Route cost combines fixed cost and arc costs. Distance need not equal travel time or cost.

c_{r} = f_{v} + \sum_{(i, j) \in A_{r}} c_{i j}^{v}, r \in R_{v} .

7. Assertions

Inputs and policies must preserve compatible units, nonnegative demand, and ordered time windows:

\forall i \in C : q_{i} \geq 0 \land e_{i} \leq l_{i} \land s_{i} \geq 0.

Let $n_{k} (r)$ denote the $k$ th node of route $r$ . An elementary route visits each customer at most once:

\forall r \in R, \forall i \in C : # {k : n_{k} (r) = i} \leq 1.

8. Constraints

1. Route Resource Feasibility [路线资源可行性]

Description: Routes must satisfy capacity and service-start windows, departing from and returning to permitted depots.

L_{r} \leq Q_{v}, e_{i} \leq t_{i}^{s t a r t} \leq l_{i}, \forall r \in R_{v}, \forall i \in C_{r} .

These are route-construction and validation rules, not additional rows registered in the restricted master by this context. Cross-route customer coverage and fleet limits belong to route compilation.

9. Objective Function (if applicable)

This context has no independent optimization objective. It supplies route cost $c_{r}$ for phase II of route compilation. Route generation uses the phase objective and dual prices to calculate reduced cost.

10. Algorithm References

Algorithm	Referenced In	Description
Route validation	Input and result analysis	Checks depots, visits, capacity, service times, and units
Route resource recurrence	Section 6	Accumulates load and computes waiting and service in visit order
Calculation policies	Section 6	Supply distance, travel time, and cost

Kotlin VRP context source; Kotlin/Rust example entry points.

11. Ubiquitous Language

Term	Symbol	Definition
Customer	$i \in C$	Demand node requiring service
Vehicle type	$v \in V$	Capacity, fixed cost, and available count
Route	$r \in R_{v}$	Feasible visit sequence for a vehicle type
Service start	$t_{i}^{s t a r t}$	Time service starts after arrival and waiting
Coverage coefficient	$a_{i r}$	Whether a route visits a customer

12. Design Decisions

Decision	Alternative	Rationale
Treat routes as domain objects	Redefine arc variables in every context	Shares semantics across generation, compilation, and validation
Separate arrival from service start	Disallow arrival before the ready time	Models waiting correctly
Separate resource validation from master rows	Expand route resources again in the master	Preserves route-column decomposition

13. Change Log

Version	Change	Reason
1.1	Aligned bilingual structure, time semantics, and variable ownership	Avoid treating domain attributes as solver variables

VRP context model ​

1. Overview ​

1. Dependent Contexts ​

2. Concepts / Entities ​

1. Customers and Depots ​

2. Vehicle Types and Routes ​

3. Variables ​

1. Decision Variables ​

2. Auxiliary Variables ​

4. Predicates ​

5. Sets ​

6. Intermediate Values ​

1. Load and Coverage Coefficients ​

2. Arrival, Waiting, and Service ​

3. Route Cost ​

7. Assertions ​

8. Constraints ​

1. Route Resource Feasibility [路线资源可行性] ​

9. Objective Function (if applicable) ​

10. Algorithm References ​

11. Ubiquitous Language ​

12. Design Decisions ​

13. Change Log ​