---
tocdepth: 3
---

# p10 | Pickup and Delivery Problem with Time Windows (PDPTW)

```{seealso}
This problem is sourced from [EvoCut](https://arxiv.org/abs/2508.11850).
```

```{note}
- We add implicit assumptions that travel times $d^k_{0i}, d^k_{iH} \geq 0$ and $d_{ij} > 0$, time windows $\tau^-_i, \tau^+_i \ge 0$ with $\tau^-_i \geq \tau^+_i$, and that travel times satisfy the triangle inequalities $d^k_{0i} \le d^k_{0j} + d_{ji}$ and $d_{ij} \le d_{im} + d_{mj}$.
- $d_{ij} > 0$ is necessary to eliminate 2-cycles and ensure there is a strict ordering of jobs in a route.
- EvoCut arXiv submission `v1` does not include this problem.
- EvoCut arXiv submission `v2` proposes four inequalities used to generate formulations `p10.b-e`.
```


## Description

Route a fleet of vehicles to serve pickup-and-delivery requests in precedence order, subject to time window constraints, minimizing total travel cost. Each request has a pickup location that must be served within a time window. Job rejection is permitted via self-loops with a penalty equal to the job's loaded travel time. Formulated as a MILP over a complete directed graph of truck and job nodes.

## Formulations
### Formulation `a` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850).
```

```{note}
- This is the MILP formulation given in Section F.5 of the [v2 arXiv paper](https://arxiv.org/abs/2508.11850v2).
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `K` | Number of trucks/vehicles in the fleet | integer | *scalar* |
| `N` | Number of pickup and delivery jobs | integer | *scalar* |
| `d` | Travel time from job i's return terminal to job j's pickup terminal; d[i][i] is the loaded time (rejection penalty) of job i | continuous | `[N, N]` |
| `d0` | Travel time from the home terminal of truck k to job i's pickup terminal | continuous | `[K, N]` |
| `dH` | Travel time from job i's return terminal to the home terminal of truck k | continuous | `[K, N]` |
| `v` | Time at which each truck becomes available | continuous | `[K]` |
| `tau_min` | Earliest permissible arrival time at each job's pickup terminal | continuous | `[N]` |
| `tau_max` | Latest permissible arrival time at each job's pickup terminal | continuous | `[N]` |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `M` | Big-M constant for arrival-time propagation: upper bound on any feasible arrival time | $M = 2 \max_{i,j \in \{0,\dots,N-1\}} d_{ij}$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `x` | 1 if arc (u,v) is selected in the routing cycle cover; x[K+i][K+i]=1 means job i is rejected | binary | `[K+N, K+N]` |
| `delta` | Arrival time at job i's pickup terminal | continuous | `[N]` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Number of trucks is at least one. | $K \geq 1$ | yes |
| Number of jobs is at least one. | $N \geq 1$ | yes |
| All travel times between jobs are strictly positive. | $d_{ij} > 0 \quad \forall i, j \in \{0,\dots,N-1\}$ | yes |
| Triangle inequality for depot-to-job travel: going directly to job i is no longer than going via job j first. | $d^k_{0i} \leq d^k_{0j} + d_{ji} \quad \forall k \in \{0,\dots,K-1\},\, i, j \in \{0,\dots,N-1\}$ | yes |
| Triangle inequality for job-to-job travel. | $d_{ij} \leq d_{im} + d_{mj} \quad \forall i, j, m \in \{0,\dots,N-1\}$ | yes |
| Truck available times are nonnegative. | $v^k \geq 0 \quad \forall k \in \{0,\dots,K-1\}$ | yes |
| Earliest permissible arrival times are nonnegative. | $\tau^-_i \geq 0 \quad \forall i \in \{0,\dots,N-1\}$ | yes |
| Latest permissible arrival times are nonnegative. | $\tau^+_i \geq 0 \quad \forall i \in \{0,\dots,N-1\}$ | yes |


#### Constraints

- Each node has exactly one outgoing arc.

  $$ \sum_{v=0}^{K+N-1} x_{uv} = 1 \quad \forall u \in \{0,\dots,K+N-1\} $$

- Each node has exactly one incoming arc.

  $$ \sum_{v=0}^{K+N-1} x_{vu} = 1 \quad \forall u \in \{0,\dots,K+N-1\} $$

- Arrival time at job i is at least the earliest possible arrival from any truck.

  $$ \delta_i - \sum_{k=0}^{K-1} (d^k_{0i} + v^k)\,x_{k,K+i} \ge 0 \quad \forall i \in \{0,\dots,N-1\} $$

- Arrival time propagation between consecutive jobs via big-M.

  $$ \delta_j - \delta_i - M\,x_{K+i,K+j} + (d_{ii}+d_{ij})\,x_{K+i,K+i} \ge d_{ii}+d_{ij}-M \quad \forall i,j \in \{0,\dots,N-1\} $$

- Time-window feasibility for each job's pickup.

  $$ \tau^-_i \le \delta_i \le \tau^+_i \quad \forall i \in \{0,\dots,N-1\} $$

#### Objective

Minimize total travel cost: deadhead from truck homes, inter-job travel, and returns to truck homes.

$$ \min \sum_{k=0}^{K-1}\sum_{i=0}^{N-1} d^k_{0i}\,x_{k,K+i} + \sum_{i=0}^{N-1}\sum_{j=0}^{N-1} d_{ij}\,x_{K+i,K+j} + \sum_{i=0}^{N-1}\sum_{k=0}^{K-1} d^k_{iH}\,x_{K+i,k} $$

### Formulation `b` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850).
```

```{note}
- Any arc from job $i$ to job $j$ whose travel time makes job $j$'s time window unreachable from job $i$ is fixed to zero.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `K` | Number of trucks/vehicles in the fleet | integer | *scalar* |
| `N` | Number of pickup and delivery jobs | integer | *scalar* |
| `d` | Travel time from job i's return terminal to job j's pickup terminal; d[i][i] is the loaded time (rejection penalty) of job i | continuous | `[N, N]` |
| `d0` | Travel time from the home terminal of truck k to job i's pickup terminal | continuous | `[K, N]` |
| `dH` | Travel time from job i's return terminal to the home terminal of truck k | continuous | `[K, N]` |
| `v` | Time at which each truck becomes available | continuous | `[K]` |
| `tau_min` | Earliest permissible arrival time at each job's pickup terminal | continuous | `[N]` |
| `tau_max` | Latest permissible arrival time at each job's pickup terminal | continuous | `[N]` |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `EST` | Earliest feasible arrival time at job i: maximum of the time-window lower bound and the earliest reachable time from any truck. | $\mathrm{EST}_i = \max\!\left(\tau^-_i,\, \min_{k \in \{0,\dots,K-1\}} (v^k + d^k_{0i})\right) \quad \forall i \in \{0,\dots,N-1\}$ |
| `A_minus` | Set of arc pairs (i, j) that are infeasible due to time windows: job j cannot be served after job i. | $\mathcal{A}^- = \{(i,j) \in \{0,\dots,N-1\}^2 : i \neq j \wedge \mathrm{EST}_i + d_{ii} + d_{ij} > \tau^+_j\}$ |
| `M` | Big-M constant for arrival-time propagation: upper bound on any feasible arrival time. | $M = 2 \max_{i,j \in \{0,\dots,N-1\}} d_{ij}$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `x` | 1 if arc (u,v) is selected in the routing cycle cover; x[K+i][K+i]=1 means job i is rejected | binary | `[K+N, K+N]` |
| `delta` | Arrival time at job i's pickup terminal | continuous | `[N]` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Number of trucks is at least one. | $K \geq 1$ | yes |
| Number of jobs is at least one. | $N \geq 1$ | yes |
| All travel times between jobs are strictly positive. | $d_{ij} > 0 \quad \forall i, j \in \{0,\dots,N-1\}$ | yes |
| Triangle inequality for depot-to-job travel: going directly to job i is no longer than going via job j first. | $d^k_{0i} \leq d^k_{0j} + d_{ji} \quad \forall k \in \{0,\dots,K-1\},\, i, j \in \{0,\dots,N-1\}$ | yes |
| Triangle inequality for job-to-job travel. | $d_{ij} \leq d_{im} + d_{mj} \quad \forall i, j, m \in \{0,\dots,N-1\}$ | yes |
| Truck available times are nonnegative. | $v^k \geq 0 \quad \forall k \in \{0,\dots,K-1\}$ | yes |
| Earliest permissible arrival times are nonnegative. | $\tau^-_i \geq 0 \quad \forall i \in \{0,\dots,N-1\}$ | yes |
| Latest permissible arrival times are nonnegative. | $\tau^+_i \geq 0 \quad \forall i \in \{0,\dots,N-1\}$ | yes |


#### Constraints

- Each node has exactly one outgoing arc.

  $$ \sum_{v=0}^{K+N-1} x_{uv} = 1 \quad \forall u \in \{0,\dots,K+N-1\} $$

- Each node has exactly one incoming arc.

  $$ \sum_{v=0}^{K+N-1} x_{vu} = 1 \quad \forall u \in \{0,\dots,K+N-1\} $$

- Arrival time at job i is at least the earliest possible arrival from any truck.

  $$ \delta_i - \sum_{k=0}^{K-1} (d^k_{0i} + v^k)\,x_{k,K+i} \ge 0 \quad \forall i \in \{0,\dots,N-1\} $$

- Arrival time propagation between consecutive jobs via big-M.

  $$ \delta_j - \delta_i - M\,x_{K+i,K+j} + (d_{ii}+d_{ij})\,x_{K+i,K+i} \ge d_{ii}+d_{ij}-M \quad \forall i,j \in \{0,\dots,N-1\} $$

- Time-window feasibility for each job's pickup.

  $$ \tau^-_i \le \delta_i \le \tau^+_i \quad \forall i \in \{0,\dots,N-1\} $$

- EC1: Fix to zero any arc from job i to job j that is infeasible due to time windows.

  $$ x_{K+i,K+j} = 0 \quad \forall (i,j) \in \mathcal{A}^- $$

#### Objective

Minimize total travel cost: deadhead from truck homes, inter-job travel, and returns to truck homes.

$$ \min \sum_{k=0}^{K-1}\sum_{i=0}^{N-1} d^k_{0i}\,x_{k,K+i} + \sum_{i=0}^{N-1}\sum_{j=0}^{N-1} d_{ij}\,x_{K+i,K+j} + \sum_{i=0}^{N-1}\sum_{k=0}^{K-1} d^k_{iH}\,x_{K+i,k} $$

### Formulation `c` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850).
```

```{note}
- For each pair of jobs $(i, j)$ that are individually feasible but where both sequencings can't both occur, at most one of $x_{K+i,K+j}$, $x_{K+j,K+i}$, or rejection self-loop $x_{K+i,K+i}$ may be active.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `K` | Number of trucks/vehicles in the fleet | integer | *scalar* |
| `N` | Number of pickup and delivery jobs | integer | *scalar* |
| `d` | Travel time from job i's return terminal to job j's pickup terminal; d[i][i] is the loaded time (rejection penalty) of job i | continuous | `[N, N]` |
| `d0` | Travel time from the home terminal of truck k to job i's pickup terminal | continuous | `[K, N]` |
| `dH` | Travel time from job i's return terminal to the home terminal of truck k | continuous | `[K, N]` |
| `v` | Time at which each truck becomes available | continuous | `[K]` |
| `tau_min` | Earliest permissible arrival time at each job's pickup terminal | continuous | `[N]` |
| `tau_max` | Latest permissible arrival time at each job's pickup terminal | continuous | `[N]` |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `EST` | Earliest start time for job i: maximum of its time-window lower bound and the earliest any truck can arrive | $\mathrm{EST}_i = \max\!\left(\tau^-_i,\, \min_{k \in \{0,\dots,K-1\}} (v^k + d^k_{0i})\right) \quad \forall i \in \{0,\dots,N-1\}$ |
| `A_minus` | Set of infeasible sequencing pairs (i,j): job j cannot follow job i without violating j's time window | $\mathcal{A}^- = \{(i,j) \in \{0,\dots,N-1\}^2 : i \ne j \wedge \mathrm{EST}_i + d_{ii} + d_{ij} > \tau^+_j\}$ |
| `F2` | Set of mutually feasible pairs: distinct jobs where neither sequencing direction is in A_minus | $F_2 = \{(i,j) \in \{0,\dots,N-1\}^2 : i \ne j,\, (i,j) \notin \mathcal{A}^-,\, (j,i) \notin \mathcal{A}^-\}$ |
| `M` | Big-M constant for arrival-time propagation: upper bound on any feasible arrival time | $M = 2 \max_{i,j \in \{0,\dots,N-1\}} d_{ij}$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `x` | 1 if arc (u,v) is selected in the routing cycle cover; x[K+i][K+i]=1 means job i is rejected | binary | `[K+N, K+N]` |
| `delta` | Arrival time at job i's pickup terminal | continuous | `[N]` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Number of trucks is at least one. | $K \geq 1$ | yes |
| Number of jobs is at least one. | $N \geq 1$ | yes |
| All travel times between jobs are strictly positive. | $d_{ij} > 0 \quad \forall i, j \in \{0,\dots,N-1\}$ | yes |
| Triangle inequality for depot-to-job travel: going directly to job i is no longer than going via job j first. | $d^k_{0i} \leq d^k_{0j} + d_{ji} \quad \forall k \in \{0,\dots,K-1\},\, i, j \in \{0,\dots,N-1\}$ | yes |
| Triangle inequality for job-to-job travel. | $d_{ij} \leq d_{im} + d_{mj} \quad \forall i, j, m \in \{0,\dots,N-1\}$ | yes |
| Truck available times are nonnegative. | $v^k \geq 0 \quad \forall k \in \{0,\dots,K-1\}$ | yes |
| Earliest permissible arrival times are nonnegative. | $\tau^-_i \geq 0 \quad \forall i \in \{0,\dots,N-1\}$ | yes |
| Latest permissible arrival times are nonnegative. | $\tau^+_i \geq 0 \quad \forall i \in \{0,\dots,N-1\}$ | yes |


#### Constraints

- Each node has exactly one outgoing arc.

  $$ \sum_{v=0}^{K+N-1} x_{uv} = 1 \quad \forall u \in \{0,\dots,K+N-1\} $$

- Each node has exactly one incoming arc.

  $$ \sum_{v=0}^{K+N-1} x_{vu} = 1 \quad \forall u \in \{0,\dots,K+N-1\} $$

- Arrival time at job i is at least the earliest possible arrival from any truck.

  $$ \delta_i - \sum_{k=0}^{K-1} (d^k_{0i} + v^k)\,x_{k,K+i} \ge 0 \quad \forall i \in \{0,\dots,N-1\} $$

- Arrival time propagation between consecutive jobs via big-M.

  $$ \delta_j - \delta_i - M\,x_{K+i,K+j} + (d_{ii}+d_{ij})\,x_{K+i,K+i} \ge d_{ii}+d_{ij}-M \quad \forall i,j \in \{0,\dots,N-1\} $$

- Time-window feasibility for each job's pickup.

  $$ \tau^-_i \le \delta_i \le \tau^+_i \quad \forall i \in \{0,\dots,N-1\} $$

- EC2: For each mutually feasible pair (i,j), at most one of the two sequencing directions or a rejection of i can hold.

  $$ x_{K+i,K+j} + x_{K+j,K+i} + x_{K+i,K+i} \le 1 \quad \forall (i,j) \in F_2 $$

#### Objective

Minimize total travel cost: deadhead from truck homes, inter-job travel, and returns to truck homes.

$$ \min \sum_{k=0}^{K-1}\sum_{i=0}^{N-1} d^k_{0i}\,x_{k,K+i} + \sum_{i=0}^{N-1}\sum_{j=0}^{N-1} d_{ij}\,x_{K+i,K+j} + \sum_{i=0}^{N-1}\sum_{k=0}^{K-1} d^k_{iH}\,x_{K+i,k} $$

### Formulation `d` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850).
```

```{note}
- For each clique $C$ in the time-window conflict graph (pairs of jobs that cannot share any truck route), at least $|C| - |K_C|$ jobs in $C$ must be rejected, where $|K_C|$ is the number of trucks that can serve any job in $C$.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `K` | Number of trucks/vehicles in the fleet | integer | *scalar* |
| `N` | Number of pickup and delivery jobs | integer | *scalar* |
| `d` | Travel time from job i's return terminal to job j's pickup terminal; d[i][i] is the loaded time (rejection penalty) of job i | continuous | `[N, N]` |
| `d0` | Travel time from the home terminal of truck k to job i's pickup terminal | continuous | `[K, N]` |
| `dH` | Travel time from job i's return terminal to the home terminal of truck k | continuous | `[K, N]` |
| `v` | Time at which each truck becomes available | continuous | `[K]` |
| `tau_min` | Earliest permissible arrival time at each job's pickup terminal | continuous | `[N]` |
| `tau_max` | Latest permissible arrival time at each job's pickup terminal | continuous | `[N]` |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `EST` | Earliest start time for each job: max of time window lower bound and earliest reachable time from any truck | $\mathrm{EST}_i = \max\!\left(\tau^-_i,\, \min_{k \in \{0,\dots,K-1\}} (v^k + d^k_{0i})\right) \quad \forall i \in \{0,\dots,N-1\}$ |
| `A_minus` | Set of directed job pairs (i,j) where job j cannot follow job i due to time window infeasibility | $\mathcal{A}^- = \{(i,j) \in \{0,\dots,N-1\}^2 : i \ne j \wedge \mathrm{EST}_i + d_{ii} + d_{ij} > \tau^+_j\}$ |
| `KC` | Set of trucks that can feasibly serve at least one job in clique C within its time window | $K_C = \{k \in \{0,\dots,K-1\} : \exists\, i \in C,\ v^k + d^k_{0i} \le \tau^+_i\} \quad \forall C \subseteq \{0,\dots,N-1\}$ |
| `C_set` | Family of cliques in the conflict graph induced by A^-: subsets C of jobs such that every distinct pair (i,j) in C has both (i,j) and (j,i) in A^- | $\mathcal{C} = \{C \subseteq \{0,\dots,N-1\} : \forall i, j \in C,\ i \ne j \Rightarrow (i,j) \in \mathcal{A}^- \wedge (j,i) \in \mathcal{A}^-\}$ |
| `M` | Big-M constant for arrival-time propagation: upper bound on any feasible arrival time | $M = 2 \max_{i,j \in \{0,\dots,N-1\}} d_{ij}$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `x` | 1 if arc (u,v) is selected in the routing cycle cover; x[K+i][K+i]=1 means job i is rejected | binary | `[K+N, K+N]` |
| `delta` | Arrival time at job i's pickup terminal | continuous | `[N]` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Number of trucks is at least one. | $K \geq 1$ | yes |
| Number of jobs is at least one. | $N \geq 1$ | yes |
| All travel times between jobs are strictly positive. | $d_{ij} > 0 \quad \forall i, j \in \{0,\dots,N-1\}$ | yes |
| Triangle inequality for depot-to-job travel: going directly to job i is no longer than going via job j first. | $d^k_{0i} \leq d^k_{0j} + d_{ji} \quad \forall k \in \{0,\dots,K-1\},\, i, j \in \{0,\dots,N-1\}$ | yes |
| Triangle inequality for job-to-job travel. | $d_{ij} \leq d_{im} + d_{mj} \quad \forall i, j, m \in \{0,\dots,N-1\}$ | yes |
| Truck available times are nonnegative. | $v^k \geq 0 \quad \forall k \in \{0,\dots,K-1\}$ | yes |
| Earliest permissible arrival times are nonnegative. | $\tau^-_i \geq 0 \quad \forall i \in \{0,\dots,N-1\}$ | yes |
| Latest permissible arrival times are nonnegative. | $\tau^+_i \geq 0 \quad \forall i \in \{0,\dots,N-1\}$ | yes |


#### Constraints

- Each node has exactly one outgoing arc.

  $$ \sum_{v=0}^{K+N-1} x_{uv} = 1 \quad \forall u \in \{0,\dots,K+N-1\} $$

- Each node has exactly one incoming arc.

  $$ \sum_{v=0}^{K+N-1} x_{vu} = 1 \quad \forall u \in \{0,\dots,K+N-1\} $$

- Arrival time at job i is at least the earliest possible arrival from any truck.

  $$ \delta_i - \sum_{k=0}^{K-1} (d^k_{0i} + v^k)\,x_{k,K+i} \ge 0 \quad \forall i \in \{0,\dots,N-1\} $$

- Arrival time propagation between consecutive jobs via big-M.

  $$ \delta_j - \delta_i - M\,x_{K+i,K+j} + (d_{ii}+d_{ij})\,x_{K+i,K+i} \ge d_{ii}+d_{ij}-M \quad \forall i,j \in \{0,\dots,N-1\} $$

- Time-window feasibility for each job's pickup.

  $$ \tau^-_i \le \delta_i \le \tau^+_i \quad \forall i \in \{0,\dots,N-1\} $$

- EC3: For each clique C in the conflict graph, at least |C|-|K_C| jobs in C must be rejected.

  $$ \sum_{i \in C} x_{K+i,K+i} \ge |C| - |K_C| \quad \forall C \in \mathcal{C}:\,|C|>|K_C| $$

#### Objective

Minimize total travel cost: deadhead from truck homes, inter-job travel, and returns to truck homes.

$$ \min \sum_{k=0}^{K-1}\sum_{i=0}^{N-1} d^k_{0i}\,x_{k,K+i} + \sum_{i=0}^{N-1}\sum_{j=0}^{N-1} d_{ij}\,x_{K+i,K+j} + \sum_{i=0}^{N-1}\sum_{k=0}^{K-1} d^k_{iH}\,x_{K+i,k} $$

### Formulation `e` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850).
```

```{note}
- For each triple $(i, k, j)$ where serving $k$ after $i$ and then $j$ after $k$ violates $j$'s time window, at most one of the two arcs $x_{K+i,K+k}$, $x_{K+k,K+j}$, or rejection self-loop $x_{K+k,K+k}$ may be active.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `K` | Number of trucks/vehicles in the fleet | integer | *scalar* |
| `N` | Number of pickup and delivery jobs | integer | *scalar* |
| `d` | Travel time from job i's return terminal to job j's pickup terminal; d[i][i] is the loaded time (rejection penalty) of job i | continuous | `[N, N]` |
| `d0` | Travel time from the home terminal of truck k to job i's pickup terminal | continuous | `[K, N]` |
| `dH` | Travel time from job i's return terminal to the home terminal of truck k | continuous | `[K, N]` |
| `v` | Time at which each truck becomes available | continuous | `[K]` |
| `tau_min` | Earliest permissible arrival time at each job's pickup terminal | continuous | `[N]` |
| `tau_max` | Latest permissible arrival time at each job's pickup terminal | continuous | `[N]` |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `EST` | Earliest start time for job i: the maximum of its time window lower bound and the earliest any truck can reach it | $\mathrm{EST}_i = \max\!\left(\tau^-_i,\, \min_{k \in \{0,\dots,K-1\}} (v^k + d^k_{0i})\right) \quad \forall i \in \{0,\dots,N-1\}$ |
| `A_minus` | Set of arc pairs (i,j) that are infeasible: serving j after i always violates j's time window upper bound | $\mathcal{A}^- = \{(i,j) \in \{0,\dots,N-1\}^2 : i \ne j \wedge \mathrm{EST}_i + d_{ii} + d_{ij} > \tau^+_j\}$ |
| `Q` | Set of incompatible triples (i,k,j): routing i->k->j always violates j's time window upper bound | $Q = \{(i,k,j) \in \{0,\dots,N-1\}^3 : i \ne k,\, k \ne j,\, (i,k) \notin \mathcal{A}^-,\, (k,j) \notin \mathcal{A}^-,\, \max(\mathrm{EST}_k,\, \mathrm{EST}_i + d_{ii} + d_{ik}) + d_{kk} + d_{kj} > \tau^+_j\}$ |
| `M` | Big-M constant for arrival-time propagation: upper bound on any feasible arrival time | $M = 2 \max_{i,j \in \{0,\dots,N-1\}} d_{ij}$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `x` | 1 if arc (u,v) is selected in the routing cycle cover; x[K+i][K+i]=1 means job i is rejected | binary | `[K+N, K+N]` |
| `delta` | Arrival time at job i's pickup terminal | continuous | `[N]` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Number of trucks is at least one. | $K \geq 1$ | yes |
| Number of jobs is at least one. | $N \geq 1$ | yes |
| All travel times between jobs are strictly positive. | $d_{ij} > 0 \quad \forall i, j \in \{0,\dots,N-1\}$ | yes |
| Triangle inequality for depot-to-job travel: going directly to job i is no longer than going via job j first. | $d^k_{0i} \leq d^k_{0j} + d_{ji} \quad \forall k \in \{0,\dots,K-1\},\, i, j \in \{0,\dots,N-1\}$ | yes |
| Triangle inequality for job-to-job travel. | $d_{ij} \leq d_{im} + d_{mj} \quad \forall i, j, m \in \{0,\dots,N-1\}$ | yes |
| Truck available times are nonnegative. | $v^k \geq 0 \quad \forall k \in \{0,\dots,K-1\}$ | yes |
| Earliest permissible arrival times are nonnegative. | $\tau^-_i \geq 0 \quad \forall i \in \{0,\dots,N-1\}$ | yes |
| Latest permissible arrival times are nonnegative. | $\tau^+_i \geq 0 \quad \forall i \in \{0,\dots,N-1\}$ | yes |


#### Constraints

- Each node has exactly one outgoing arc.

  $$ \sum_{v=0}^{K+N-1} x_{uv} = 1 \quad \forall u \in \{0,\dots,K+N-1\} $$

- Each node has exactly one incoming arc.

  $$ \sum_{v=0}^{K+N-1} x_{vu} = 1 \quad \forall u \in \{0,\dots,K+N-1\} $$

- Arrival time at job i is at least the earliest possible arrival from any truck.

  $$ \delta_i - \sum_{k=0}^{K-1} (d^k_{0i} + v^k)\,x_{k,K+i} \ge 0 \quad \forall i \in \{0,\dots,N-1\} $$

- Arrival time propagation between consecutive jobs via big-M.

  $$ \delta_j - \delta_i - M\,x_{K+i,K+j} + (d_{ii}+d_{ij})\,x_{K+i,K+i} \ge d_{ii}+d_{ij}-M \quad \forall i,j \in \{0,\dots,N-1\} $$

- Time-window feasibility for each job's pickup.

  $$ \tau^-_i \le \delta_i \le \tau^+_i \quad \forall i \in \{0,\dots,N-1\} $$

- EC4: For each triple (i,k,j) where serving k after i and j after k violates the time window of j, at most one of the two arcs or a rejection of k can hold.

  $$ x_{K+i,K+k} + x_{K+k,K+j} + x_{K+k,K+k} \le 1 \quad \forall (i,k,j) \in \mathcal{Q} $$

#### Objective

Minimize total travel cost: deadhead from truck homes, inter-job travel, and returns to truck homes.

$$ \min \sum_{k=0}^{K-1}\sum_{i=0}^{N-1} d^k_{0i}\,x_{k,K+i} + \sum_{i=0}^{N-1}\sum_{j=0}^{N-1} d_{ij}\,x_{K+i,K+j} + \sum_{i=0}^{N-1}\sum_{k=0}^{K-1} d^k_{iH}\,x_{K+i,k} $$