Vehicle Routing Problems

Modelli di Programmazione Lineare Intera

Stefano Gualandi / @famo2spaghi / stefano.gualandi@gmail.com

Traveling Salesman Problem

• Dato un grafo orientato $G=(N,A)$, un circuito Hamiltoniano e` un circuito che visita ogni nodo di $G$ una sola volta.

• Dato un costo $c_a$ per ogni arco $a\in A$, il problema del commesso viaggiatore consiste nel trovare il circuito Hamiltoniano di costo totale minimo.

Notazione

Dato un insieme di citta` $S \subseteq V$, siano:

• $\delta(S)^+ = \{(i,j) \in A: i \in S, j \notin S \}$
• $\delta(S)^- = \{(i,j) \in A: i \notin S, j \in S \}$

Sia inoltre $x_{ij}$ una variabile in $\{0,1\}$ tale che: $\begin{equation} x_{ij} = \left\{ \begin{array}{ll} 1 & \mbox{se la citta` $j$ viene visitata subito dopo $i$} \\ 0 & \mbox{altrimenti} \end{array} \right. \end{equation}$

Modello di Program. Lineare Intera

$\begin{align} \min \quad & \sum_{(i,j) \in A} c_{ij} x_{ij} \\ \mbox{s.t.} \quad & \sum_{(i,j) \in \delta^+(i)} x_{ij} = 1 & \forall i \in N \quad \mbox{(3.1)} \\ & \sum_{(j,i) \in \delta^-(i)} x_{ji} = 1 & \forall i \in N \quad \mbox{(3.2)} \\ & \sum_{(i,j) \in \delta^+(S)} x_{ij} \geq 1 & \forall S: \emptyset \subset S \subset N \quad \mbox{(3.3)} \\ & x_{ij} \in \{0,1\} & \forall (i,j) \in A. \end{align}$

Subtour Elimination Constraints

• Sommando tutti i vincoli (3.1) per ogni $i \in S$ e sottraendo il vincolo (3.3) si ottiene una formulazione equivalente per i vincoli di subtour elimination:

$$\sum_{i \in S, j \in S: (i,j) \in A} x_{ij} \leq |S| - 1 \quad \forall S: \emptyset \subset S \subset N $$

Miller, Tucker and Zemlin (MTZ)

• Questa formulazione ha delle variabili supplementari $u_i$ intere che indicano la posizione del nodo $i$ nella soluzione. Assumendo che il circuito inizia al nodo 1, abbiamo che $u_1 =1$. La formulazione MTZ sostuisce il vincolo (subtour) con il vincolo: $$u_i - u_j + 1 \leq n(1-x_{ij}) \quad \forall (i,j) \in A, i,j \neq 1. \quad (3.4)$$
• DOMANDA: Come si mostra che la formulazione e` corretta?

Confronto di formulazioni

Si considerino i due seguenti poliedri:

• $P_{MTZ} = \{(x,u) \in \mathbb{R}^A \times \mathbb{R}^{V \setminus \{1\}}: (x,u) \mbox{ soddisfa } (3.1),(3.2),(3.4) \}$
• $P_{\mbox{subtour}} = \{ x \in \mathbb{R}^A: \mbox{ soddisfa } (3.1),(3.2),(3.3) \}$

Si dimostra che: $$P_{\mbox{subtour}} \subset \mbox{proj}_x(P_{MTZ})$$

Rilassamenti Continuo: $P_{MTZ}$

$\begin{align} \min \quad & \sum_{(i,j) \in A} c_{ij} x_{ij} \\ \mbox{s.t.} \quad & \sum_{(i,j) \in \delta^+(i)} x_{ij} = 1 & \forall i \in N \quad \mbox{(3.1)} \\ & \sum_{(j,i) \in \delta^-(i)} x_{ji} = 1 & \forall i \in N \quad \mbox{(3.2)} \\ & u_i - u_j + 1 \leq n(1-x_{ij}) & \forall (i,j) \in A, i,j \neq 1. \quad (3.4) \\ & 0 \leq x_{ij} \leq 1, u_i \geq 0, u_1 = 1 & \forall (i,j) \in A. \end{align}$

Rilassamenti Continuo: $P_{\mbox{subtour}}$

$\begin{align} \min \quad & \sum_{(i,j) \in A} c_{ij} x_{ij} \\ \mbox{s.t.} \quad & \sum_{(i,j) \in \delta^+(i)} x_{ij} = 1 & \forall i \in N \quad \mbox{(3.1)} \\ & \sum_{(j,i) \in \delta^-(i)} x_{ji} = 1 & \forall i \in N \quad \mbox{(3.2)} \\ & \sum_{(i,j) \in \delta^+(S)} x_{ij} \geq 1 & \forall S: \emptyset \subset S \subset N \quad \mbox{(3.3)} \\ & 0 \leq x_{ij} \leq 1 & \forall (i,j) \in A. \end{align}$

Confronto di formulazioni

Si considerino i due seguenti poliedri:

• $P_{MTZ} = \{(x,u) \in \mathbb{R}^A \times \mathbb{R}^{V \setminus \{1\}}: (x,u) \mbox{ soddisfa } (3.1),(3.2),(3.4) \}$
• $P_{\mbox{subtour}} = \{ x \in \mathbb{R}^A: \mbox{ soddisfa } (3.1),(3.2),(3.3) \}$

Si dimostra che: $$P_{\mbox{subtour}} \subset \mbox{proj}_x(P_{MTZ})$$

Tempo di calcolo

Capacitated Vehicle Routing Problem (CVRP)

• Sia $K$ un insieme di veicoli con capacita` $C$.
• Sia dato un grafo orientato $G=(N,A)$, con $N=\{0, 1, \dots, n\}$, in cui 0 rappresenta il deposito.
• Ogni nodo $i \in N \setminus \{0\}$ ha una domanda pari a $d_i \leq C$. Sia $d(S) = \sum_{i \in S} d_i$.
• Ogni arco $(i,j) \in A$ ha un costo (distanza) $c_{ij}$. Se $c_{ij} = c_{ji}$ si parla di VRP simmetrico.
• Il problema e` ammissibile se $K \geq K_{min}$, dove $K_{min}$ e` il numero minimo di veicoli necessario per soddisfare la somma delle domande su tutti i nodi.

Determinazione di K$_{min}$: Bin Packing

• Sia $x_{xk} = \left\{ \begin{array}{ll} 1 & \mbox{se il cliente $i$ e` servito dal veicolo $k$} \\ 0 & \mbox{altrimenti} \end{array} \right.$
• Sia $y_k = \left\{ \begin{array}{ll} 1 & \mbox{se viene usato il veicolo $k$} \\ 0 & \mbox{altrimenti} \end{array} \right.$
• Sia $\gamma(S)$ il numero minimo di veicoli necessari per servire i clienti $i \in S \subseteq N$.

Determinazione di K$_{min}$: Bin Packing

$\begin{align} \gamma(N) = \min \quad & \sum_{k \in K} y_k \\ \mbox{s.t.} \quad & \sum_{k \in K} x_{ik} = 1 & \forall I \in N \\ & \sum_{i \in N} d_i x_{ik} \leq C y_k & \forall k \in K \\ & x_{ik} \in \{0,1\}, y_k \in \{0,1\} & \forall i \in N, k \in K. \end{align}$

DOMANDA: Potete determinare un lower bound per $\gamma(N)$?

Vehicle Flow Based Formulation

• Sia $x^k_{ij} = \left\{ \begin{array}{ll} 1 & \mbox{se $i$ e` servito subito dopo $j$ dal veicolo $k$} \\ 0 & \mbox{altrimenti} \end{array} \right.$


• Una prima formulazione e` la seguente: $$\begin{align} \min \quad & \sum_{(i,j) \in A} \sum_{k \in K} c_{ij} x^k_{ij} \\ & \sum_{k \in K} \sum_{(i,j) \in A} x^k_{ij} = 1 & \forall i \in N \quad \mbox(1.1) \\ & \sum_{k \in K} \sum_{(i,j) \in A} x^k_{ij} = 1 & \forall j \in N \quad \mbox(1.2)\\ \end{align} $$

$$\begin{align} &\sum_{(i,h) \in A} x^k_{ih} - \sum_{(h,j) \in A} x^k_{hj} = 0 & \forall h \in N \setminus \{0\}, \forall k \in K \quad \mbox(1.3)\\ & \sum_{(0,j) \in A} x^k_{0j} \leq 1 & \forall k \in K \quad \mbox(1.4) \\ & \sum_{i \in N} d_i (\sum_{(i,j) \in A} x^k_{ij}) \leq C & \forall k \in K \quad \mbox(1.5)\\ &\sum_{i \in S, j \in S} x^k_{ij} \leq |S| - 1 & \forall k \in K, \forall \emptyset \subset S \subset N \quad \mbox{(1.6)} \\ & x^k_{ij} \in \{0,1\} & \forall k \in K, \forall (i,j) \in A. \quad \mbox{(1.7)} \end{align} $$

Commodity Flow Based Formulation

• Sia $x_{ij} = \left\{ \begin{array}{ll} 1 & \mbox{se $i$ e` servito subito dopo $j$} \\ 0 & \mbox{altrimenti} \end{array} \right.$
• Sia $y^k_{ij}\geq 0$ la quantita` di domanda destinata al punto $k$ trasportata da $i$ a $j$.

Commodity Flow Based Formulation

Commodity Flow Based Formulation

$$\begin{align} & \sum_{k \in N} y^k_{ij} \leq C x_{ij} & \forall (i,j) \in A \quad (2.4)\\ &\sum_{(i,h) \in A} y^k_{ih} - \sum_{(h,j) \in A} y^k_{hj} = D_k & \forall h \in N, \forall k \in K \quad (2.5) \end{align}$$

In cui: $$ D_k = \left\{ \begin{array}{ll} d_j & \mbox{ se $j = k$} \\ 0 & \mbox{se $j\neq 0$, $j \neq k$} \end{array} \right.$$

CVRP: Two-index Formulation

$\begin{align} \min \quad & \sum_{(i,j) \in A} c_{ij} x_{ij} \\ \mbox{s.t.} \quad & \sum_{(i,j) \in \delta^+(i)} x_{ij} = 1 & \forall i \in N \setminus \{0\} \quad \mbox{(3.1)} \\ & \sum_{(j,i) \in \delta^-(i)} x_{ji} = 1 & \forall i \in N \setminus \{0\} \quad \mbox{(3.2)} \\ & \sum_{i \in N} x_{i0} = K, \sum_{i \in N} x_{0i} = K & \quad (3.3) \\ & \sum_{(i,j) \in \delta^+(S)} x_{ij} \geq \gamma(S) & \forall S: \emptyset \subset S \subset N \quad (3.4) \\ & x_{ij} \in \{0,1\} & \forall (i,j) \in A. \end{align}$

Generalized Subtour Elimination

• Per i vincoli di grado abbiamo: $$\sum_{i \notin S, j \in S} x_{ij} = \sum_{i \notin S, j \in S} x_{ij}, \quad \forall S: \emptyset \subset S \subset N \quad \mbox{(subtour)}$$ In pratica ogni taglio $(V \setminus S, S)$ viene attraversato lo stesso numero di volte in entrambe le direzioni.
• Utilizzando la relazione precedente, possiamo riscrevere il vincolo (*) come: $$\sum_{i \notin S, j \in S} x_{ij} \geq \gamma(V\setminus S), \quad \forall S \subset V, S \in \{0 \}$$

Generalized Subtour Elimination

• Utilizzando i vincoli di grado possiamo scrivere: $$\sum_{i \in S, j \in S} x_{ij} \leq |S| - \gamma(S), \quad \forall S \subseteq N \setminus \{0\}$$ che impone che almeno $\gamma(S)$ archi lasciano l'insieme di nodi $S$.

DOMANDA: Potete trovare una formulazione con un numero polinomiale di vincoli?

Estensione di MZT al CVRP

Sia $u_i$, $i \in N \setminus \{0\}$, il carico del veicolo dopo aver visitato il cliente $i$, e si introducano i vincoli seguenti: