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

See also

This problem is sourced from EvoCut.

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)¶

See also

This formulation is sourced from EvoCut.

Note

This is the MILP formulation given in Section F.5 of the v2 arXiv paper.

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)¶

See also

This formulation is sourced from EvoCut.

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)¶

See also

This formulation is sourced from EvoCut.

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)¶

See also

This formulation is sourced from EvoCut.

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)¶

See also

This formulation is sourced from EvoCut.

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} \]

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

Description¶

Formulations¶

Formulation a (valid)¶

Parameters¶

Definitions¶

Variables¶

Assumptions¶

Constraints¶

Objective¶

Formulation b (valid)¶

Parameters¶

Definitions¶

Variables¶

Assumptions¶

Constraints¶

Objective¶

Formulation c (valid)¶

Parameters¶

Definitions¶

Variables¶

Assumptions¶

Constraints¶

Objective¶

Formulation d (valid)¶

Parameters¶

Definitions¶

Variables¶

Assumptions¶

Constraints¶

Objective¶

Formulation e (valid)¶

Parameters¶

Definitions¶

Variables¶

Assumptions¶

Constraints¶

Objective¶

Formulation `a` (valid)¶

Formulation `b` (valid)¶

Formulation `c` (valid)¶

Formulation `d` (valid)¶

Formulation `e` (valid)¶