Il commesso viaggiatore… Alla scoperta della Programmazione Lineare

Amazon riceve decine di milioni di nuovi ordini ogni giorno. Un numero che solo a pensarlo può dare un senso di stordimento.

Mettiamoci nei panni di uno dei servizi di spedizione a cui questa grande compagnia si appoggia. Il flusso di pacchi da gestire è enorme e per aumentare al massimo il profitto bisogna trovare un modo per ridurre al minimo il percorso di ogni spedizioniere.

Qui salta fuori il famoso problema del “Commesso viaggiatore”, ossia come trovare il tragitto più breve che passi per un insieme finito di punti nello spazio.

In questo post cercheremo di cogliere la reale complessità del problema e di risolverlo andando così… alla scoperta della Programmazione Lineare.

Il commesso viaggiatore

Cos’è il Travelling Salesman Problem?

Nell’introduzione abbiamo visto come il problema che stiamo analizzando nasca da un contesto prettamente concreto. Per cercare di capire come risolverlo la prima cosa da fare è sempre la stessa: fare conoscenza con il problema. Per fare questo, solitamente, i matematici non seguono alla lettera le regole del galateo, ma si mettono a dividere tutto in pezzi e a dare un nome ad ogni componente.

Noi da aspiranti matematici faremo lo stesso!

Definiamo quindi un insieme contenente tutti i punti da raggiungere, P = \{ p_{1} ,  ... , \ p_{n} \} e un insieme T che rappresenti i possibili tragitti con la loro lunghezza: n=t_{ij} \in T se esiste un percorso che va da p_{i} a   \ p_{j} di lunghezza n.

Utilizzando il vettore \vec{x}, di cui ogni componente rappresenta un tragitto all’interno del percorso considerato (vedremo poi meglio come è fatto), definiamo una funzione \tau: \vec{x} \ \rightarrow \mathbb{R} che assegna ad ogni percorso la sua lunghezza.

Il problema si può ora vedere in modo più formale come: trovare il vettore \vec{x}  tale per cui \tau (\vec{x})  sia minimo.

Forse tutto questo matematichese ti ha confuso un po’, ma se provi a rileggere il tutto con attenzione ti accorgerai che non abbiamo fatto altro che riscrivere in formula il problema di prima.

Ora puoi dire che come era scritto inizialmente era molto più semplice (e ti daremmo ragione), ma questa nuova veste dà al quesito un aspetto più trattabile da un punto di vista matematico/computazionale.

 

Per trovare una soluzione al problema del commesso viaggiatore andiamo a scoprire uno degli strumenti più potenti nel campo dell’ottimizzazione lineare: la Programmazione Lineare.

Preliminari alla Programmazione Lineare

Prima di riuscire a riscrivere il problema dobbiamo introdurre il concetto di funzione lineare.

Diciamo funzione lineare una funzione del tipo f ( x_1 , ... \ , x_n ) = \sum_{j=1}^{n} a_{j} \times x_{j} dove a_j \in \mathbb{R} .

Guardandola bene possiamo capire che il termine lineare significa semplicemente che l’argomento della funzione è di primo grado.

Analogamente diciamo che un vincolo è lineare se è nella forma \sum_{j=1}^{n} a_{j} \times x_{j} \le b dove a_j e b \in \mathbb{R} .

 

Ricerchiamo l’ottimo con la PL

A questo punto vogliamo esprimere un percorso tramite il vettore \vec{x} . Come facciamo?

Una possibile soluzione è la seguente: definiamo una variabile per ogni possibile tragitto. Ad esempio x_{ij} identifica il tragitto dal punto p_i  al punto p_j . Ora poniamo x_{ij} uguale a 1 se il tragitto è compreso nel percorso considerato, 0 altrimenti.

Ricordandoci del significato di  T possiamo finalmente costruire la nostra tanto sudata funzione lineare \tau(\vec{x}) = \sum_{i=1}^{n} \sum_{j=1}^{n} t_{ij} \times x_{ij} .

Ci resta soltanto da porre delle condizioni che obblighino il percorso analizzato a passare per tutti i punti.

Ne servono 3!

\sum_{i=1}^{n}  x_{ij} = 1 \  \forall j \in \{1 , ... , n\} , ossia ogni punto ha solo un percorso “entrante” …

\sum_{j=1}^{n}  x_{ij} = 1 \  \forall i \in \{1 , ... , n\} , ossia ogni punto ha solo un percorso “uscente”….

e

x_{ij} \in \{ 0 , 1 \} , ossia le uniche possibilità sono utilizzare un tragitto (1) o non considerarlo (0).

(Per correttezza si dovrebbe utilizzare una quarta condizione per evitare la presenza di sottocircuiti non connessi che però qui tralasciamo per semplicità).

 

Formalizzazione del problema del commesso viaggiatore

Riassumendo tutto quello che abbiamo detto il Travelling Salesman Problem diventa:

min \sum_{i=1}^{n} \sum_{j=1}^{n} t_{ij} \times x_{ij} 

sotto le condizioni

\sum_{i=1}^{n}  x_{ij} = 1 \ \forall j \in \{1 ,  ... , n\}

\sum_{j=1}^{n}  x_{ij} = 1 \  \forall i \in \{1 , ... , n\} 

x_{ij} \in \{ 0 , 1 \}

 

Molto bene… E ora?

Abbiamo dato una veste molto elegante al nostro problema, ma come lo risolviamo?

Il bello della programmazione lineare è proprio questo, “non ci interessa”!

Una volta scritto il problema secondo questo formalismo è sufficiente delegarlo ad un buon risolutore.

Qui trovate una spiegazione di come risolvere problemi del genere utilizzando Excel.

Per capire cosa succede all’interno di questi applicativi bisognerebbe aprire una lunghissima e complessa parentesi sul metodo del simplesso. Lascio ai più curiosi l’occasione di approfondire (poi se serve un aiuto scriveteci pure 🙂 ).

 

Il lato oscuro del commesso viaggiatore

Siamo quasi alla fine e sembra ormai che per i servizi di spedizione il problema delle consegne sia stato risolto. Tutto va bene finché il numero di punti di consegna non aumenta e il nostro metodo non riesce più a fornire una soluzione.

La modellizzazione che abbiamo fatto è infatti NP-completa e quindi il tempo di esecuzione del nostro metodo cresce in modo non polinomiale (e quindi MOLTO velocemente) al crescere del numero di punti analizzati.

E’ proprio questa difficoltà che apre lo scenario ad altre tecniche di risoluzione. L’ideale sarebbe trovare un algoritmo polinomiale, ma non sappiamo ancora se questo è possibile (l’argomento della NP vs P è stato accennato recentemente qui).

Per ora sembra che, nel caso in cui il percorso debba passare per un numero elevato di punti, non si possa trovare la soluzione ottima al problema del commesso viaggiatore in tempi ragionevoli. In pratica quindi si deve abbandonare la speranza di trovare l’ottimo ed accontentarsi di una sua approssimazione.

 

Futuri viaggi del commesso

Entriamo così nel mondo dell’euristica dove si va a cercare di trovare dei buoni candidati per ottenere l’ottimo utilizzando tecniche di tipo probabilistico/stocastico.

Queste metodologie sono molto interessanti e suggestive. Nel futuro andremo quindi a richiamare il nostro commesso per partire con lui in un nuovo viaggio… alla scoperta del Calcolo Stocastico!

 

Come abbiamo visto in questo articolo spesso molti problemi della vita quotidiana vengono affrontati facendo uso del sapere matematico.

Questo mi fa pensare che chi dedica la vita allo studio della matematica non sia poi così folle!

Spero che l’articolo ti sia piaciuto, a presto 😉

Marco

 

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *