Nevicata improvvisa: suggerimenti per la variante 2

In questa seconda variante dobbiamo considerare due veicoli e quindi due insiemi variabili di flusso riferite al primo e al secondo veicolo: $x^1_{ij}, x^2_{ij} \geq 0, (i,j) \in A$. Per entrambi gli insiemi di variabili imponiamo la conservazione del flusso:

$$\sum_{j: (j,i) \in A} x^h_{ji} + = \sum_{j: (i,j) \in A} x_{ij} = 0\;\;\;\; \forall i\in N, h=1,2$$

Il vincolo che almeno un veicolo passi per un arco diventa:

$$x^1_{ij} + x^1_{ij} \geq1 \;\;\;\;\; \forall (i,j) \in A$$

Avendo due veicoli, a differenza che nel caso di un singolo veicolo, è indispensabile imporre che entrambi gli itinerari includano il nodo deposito (0).

$$\sum_{j: (0,j) \in A} x^1_{0,j} \geq 1$$

$$\sum_{j: (0,j) \in A} x^2_{0,j} \geq 1$$

Inoltre è necessario imporre la connessione degli itinerari, cosa che richiede un numero esponenziale di vincoli. Considerando un qualsiasi sottoinsieme di nodi $S$ che non include il deposito 0, se un veicolo percorre archi all'interno di $S$ allora deve percorrere anche un arco con un estremo in $S$ e uno non in $S$.

$$\sum_{(i,j): i, j \in S} x^h_{ij} \leq M \sum_{(i,j): i \in ... ...h_{ij} \;\;\;\;\;\; \forall S \subset N \setminus \{0\}, h=1,2$$

La funzione obiettivo minimizza la lunghezza del massimo itinerario. Sia $d\geq 0$ una opportuna variabile:

$$d \geq \sum_{(i,j) \in A} t_{ij} x^h_{ij}, \;\;\;\;\; h=1,2$$

$$\min d$$