Vai al contenuto

Formulazioni dei problemi di routing

Parte 2 · Formulazioni dei problemi e loro proprietà · Capitolo 13 · Dispensa, volume 2 (PDF) · Slide · Esercizi: Problemi di routing

Prerequisiti

Obiettivi

Alla fine di questo capitolo saremo in grado di:

  • scrivere il modello PLI del problema del commesso viaggiatore con le variabili di posizione di Miller-Tucker-Zemlin (MTZ) e spiegare come eliminano i sottogiri;

  • scrivere il modello PLI con i vincoli di eliminazione dei sottogiri di Dantzig-Fulkerson-Johnson (DFJ) e dimostrarne la correttezza;

  • contare le variabili e i vincoli dei due modelli;

  • confrontare i rilassamenti lineari dei due modelli sulla stessa istanza;

  • scrivere il modello PLI del TSP asimmetrico e spiegare perché il TSP metrico ha gli stessi modelli del TSP.

13.1 Panoramica della famiglia

  • Dato l'insieme \(\mathscr{V}=\{1,2,\dots,n\}\) delle città, i modelli di questo capitolo usano l'insieme degli archi orientati

    \[ A=\{(i,j):i,j\in\mathscr{V},~i\neq j\}. \]

    Ogni lato \(\{i,j\}\) del problema simmetrico è rappresentato dai due archi opposti \((i,j)\) e \((j,i)\), che hanno lo stesso costo \(d_{ij}=d_{ji}\).

  • I modelli PLI dei problemi di routing usano una variabile di arco binaria \(x_{ij}\) per ogni arco \((i,j) \in A\), uguale a \(1\) se il giro va dalla città \(i\) alla città \(j\).

  • I vincoli di grado impongono che da ogni città esca esattamente un arco e che in ogni città entri esattamente un arco; i modelli differiscono nei vincoli che eliminano i sottogiri.

I modelli di routing sono modelli di assegnamento sugli archi, con i vincoli di grado, più vincoli che vietano i sottogiri. La funzione obiettivo minimizza la distanza totale \(\sum_{(i,j) \in A} d_{ij}\,x_{ij}\).

  • La tabella elenca i membri della famiglia, con i nomi dei loro modelli PLI e le sezioni che li scrivono.
Problema Modello Eliminazione dei sottogiri Sezione
TSP \(\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{MTZ}}\) variabili di posizione \(u_i\) 13.3
TSP \(\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{DFJ}}\) un vincolo per ogni sottoinsieme di città 13.4
TSP metrico \(\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{MTZ}}\), \(\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{DFJ}}\) i modelli del TSP 13.6
ATSP \(\mathrm{ILP}_{\mathrm{ATSP}}\) i vincoli dei modelli del TSP 13.6

  • Panoramica

    Panoramica della famiglia

    Apri

  • 13.2 Modelli PLI per il problema del commesso viaggiatore

    Il rilassamento di assegnamento · Il rilassamento del modello MTZ · Il rilassamento del modello DFJ

    Apri

  • 13.6 Modelli PLI per il TSP metrico e asimmetrico

    In sintesi

    Apri

Avanti: 13.2 Modelli PLI per il problema del commesso viaggiatore

Esercizi su questo capitolo: Problemi di routing