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

See also

This problem is sourced from EvoCut [2].

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 \leq \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.
The source big-M constant \(M = 2 \max_{i,j} d_{ij}\) is not always valid: it ignores the time-window spread \(\tau^+_i - \tau^-_j\) and can cut off feasible solutions. We use \(M = 2 \max_{i,j} d_{ij} + \max_i \tau^+_i - \min_j \tau^-_j\).

NP-hard: yes

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 [2].

Note

This is the PDPTW formulation from v2 of Yazdani et al. [2].

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_{ii}\) 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} + \max_i \tau^+_i - \min_j \tau^-_j\)

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
Each time window is non-empty: the earliest permissible arrival is no later than the latest.	\(\tau^-_i \leq \tau^+_i \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 [2].

Note

This is the PDPTW formulation from v2 of Yazdani et al. [2] augmented with acceleration cut EC1.

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_{ii}\) 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} + \max_i \tau^+_i - \min_j \tau^-_j\)

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
Each time window is non-empty: the earliest permissible arrival is no later than the latest.	\(\tau^-_i \leq \tau^+_i \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 [2].

Note

This is the PDPTW formulation from v2 of Yazdani et al. [2] augmented with acceleration cut EC2.

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_{ii}\) 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 \(\mathcal{A}^-\)	\(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} + \max_i \tau^+_i - \min_j \tau^-_j\)

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
Each time window is non-empty: the earliest permissible arrival is no later than the latest.	\(\tau^-_i \leq \tau^+_i \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 [2].

Note

This is the PDPTW formulation from v2 of Yazdani et al. [2] augmented with acceleration cut EC3.

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_{ii}\) 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 \(\mathcal{A}^-\): subsets \(C\) of jobs such that every distinct pair \((i,j)\) in \(C\) has both \((i,j)\) and \((j,i)\) in \(\mathcal{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} + \max_i \tau^+_i - \min_j \tau^-_j\)

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
Each time window is non-empty: the earliest permissible arrival is no later than the latest.	\(\tau^-_i \leq \tau^+_i \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 [2].

Note

This is the PDPTW formulation from v2 of Yazdani et al. [2] augmented with acceleration cut EC4.

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_{ii}\) 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 \to k \to 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} + \max_i \tau^+_i - \min_j \tau^-_j\)

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
Each time window is non-empty: the earliest permissible arrival is no later than the latest.	\(\tau^-_i \leq \tau^+_i \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} \]

Reformulations¶

Each entry below pairs two formulations of this problem, records whether the second is a reformulation of the first, and gives the parameter map carrying the first formulation’s parameters to the second’s.

a → b (valid)¶

Note

Formulation b has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of `a`
`K`	\(K = K\)
`N`	\(N = N\)
`d`	\(d_{ij} = d_{ij}\)
`d0`	\(d0_{ij} = d0_{ij}\)
`dH`	\(dH_{ij} = dH_{ij}\)
`v`	\(v_{i} = v_{i}\)
`tau_min`	\(\tau^-_i = \tau^-_i\)
`tau_max`	\(\tau^+_i = \tau^+_i\)

a → c (valid)¶

Note

Formulation c has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of `a`
`K`	\(K = K\)
`N`	\(N = N\)
`d`	\(d_{ij} = d_{ij}\)
`d0`	\(d0_{ij} = d0_{ij}\)
`dH`	\(dH_{ij} = dH_{ij}\)
`v`	\(v_{i} = v_{i}\)
`tau_min`	\(\tau^-_i = \tau^-_i\)
`tau_max`	\(\tau^+_i = \tau^+_i\)

a → d (valid)¶

Note

Formulation d has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of `a`
`K`	\(K = K\)
`N`	\(N = N\)
`d`	\(d_{ij} = d_{ij}\)
`d0`	\(d0_{ij} = d0_{ij}\)
`dH`	\(dH_{ij} = dH_{ij}\)
`v`	\(v_{i} = v_{i}\)
`tau_min`	\(\tau^-_i = \tau^-_i\)
`tau_max`	\(\tau^+_i = \tau^+_i\)

a → e (valid)¶

Note

Formulation e has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of `a`
`K`	\(K = K\)
`N`	\(N = N\)
`d`	\(d_{ij} = d_{ij}\)
`d0`	\(d0_{ij} = d0_{ij}\)
`dH`	\(dH_{ij} = dH_{ij}\)
`v`	\(v_{i} = v_{i}\)
`tau_min`	\(\tau^-_i = \tau^-_i\)
`tau_max`	\(\tau^+_i = \tau^+_i\)

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¶

Reformulations¶

a → b (valid)¶

a → c (valid)¶

a → d (valid)¶

a → e (valid)¶

Formulation `a` (valid)¶

Formulation `b` (valid)¶

Formulation `c` (valid)¶

Formulation `d` (valid)¶

Formulation `e` (valid)¶