Modellare il Problema del Commesso Viaggiatore dai primi principi

Guida pratica per risolvere il problema del commesso viaggiatore con metodi fondamentali

Un approccio centrato sui concetti e meno sulla matematica per modellare il problema di routing più noto nell’Operations Research

👁️ Questo è l’articolo n. 2 della serie che copre il progetto “An Intelligent Decision Support System for Tourism in Python“. Ti incoraggio a darci un’occhiata per avere una panoramica generale dell’intero progetto. Se sei interessato solo a modellare il TSP, sei comunque nel posto giusto, poiché questo articolo è autocontenuto. Se sei interessato anche a risolvere il problema, non solo a modellarlo, amerai i prossimi 5 articoli della serie. Fidati di me, ti forniranno ciò di cui hai bisogno e ciò che non sapevi di aver bisogno 😉

Indice

1. Motivazione e scopo

2. Comprensione dei dati

3. Definire un modello concettuale dalla descrizione del problema

4. Costruire un modello matematico dal modello concettuale

• 4.1. Mettere i dati in Set e Parametri
• 4.2. Codifica delle decisioni nelle Variabili
• 4.3. Definizione dell’Obiettivo
• 4.4. Creazione dei Vincoli

1. Motivazione e scopo

Questo articolo prosegue da dove si è interrotto il precedente articolo per lo sprint 1. Non è necessario averlo letto per capire ciò che faremo qui, ma permettimi di fare un breve riassunto (sentiti libero di passare alla sezione 2 se hai letto l’articolo precedente). In poche parole, abbiamo individuato i problemi comuni che i turisti affrontano quando pianificano un viaggio e abbiamo deciso di costruire un sistema che possa aiutarci a pianificare viaggi in modo più efficace, accelerando la presa di decisioni o addirittura automatizzando completamente l’itinerario per qualsiasi viaggio desiderato. Abbiamo osservato che così formulato, il problema è troppo complesso, quindi lo abbiamo scomposto e siamo arrivati alla sua versione essenziale, a cui abbiamo dato il nome di problema minimo valido. Alla fine, abbiamo concluso che assume la forma del Problema del Commesso Viaggiatore (TSP), dove le “città” che il proverbiale commesso deve visitare corrispondono, nella nostra versione, ai “siti di interesse” di una città che un turista desidera visitare.

Quindi, per iniziare, dobbiamo prima formulare e risolvere il TSP e una volta fatto ciò, avremo basi solide per progredire verso una soluzione più sofisticata e generale per il nostro problema di pianificazione del viaggio. Abbiamo scelto questo approccio perché questa serie di articoli insegna anche un approccio agile alla modellazione nell’Operations Research (OR), quindi molti degli insegnamenti, consigli e trucchi che troverai qui sono applicabili a qualsiasi tipo di problema che potresti affrontare nell’OR in generale.

Tornando al nostro problema, abbiamo la descrizione del problema del TSP:

• Tutto ciò che devi sapere per sviluppare con l’uso di grandi modelli di linguaggio
• Grafica Data Science per i dati tabulari
• Introduzione all’entropia e all’indice di Gini

• Obiettivo: camminare la distanza minore possibile
• Requisiti: visitare ogni sito solo una volta e tornare al punto di partenza originale (nel nostro caso, l’hotel).

Dato che sappiamo che questo problema non è il nostro vero problema, ma una semplice approssimazione ad esso, vogliamo costruire un modello del problema, poiché un modello può essere affinato, ampliato e modificato; e sappiamo che dovremo farlo per arrivare a una soluzione al nostro vero problema. Pertanto, il nostro obiettivo è costruire un modello, invece di trovare una soluzione diretta ad esso o ideare qualche tipo di algoritmo euristico che trovi una soluzione per te. Una volta imparato come ragionare fino a un modello del genere, avrai una buona comprensione per andare a leggere l’articolo dello sprint successivo, dove implementeremo il modello in Python.

2. Comprensione dei dati

Se ti ricordi dal nostro ultimo sprint, l’input di base per il TSP è semplicemente un elenco di luoghi che vogliamo visitare in un solo giorno. In questo poof di concetto, stiamo utilizzando Parigi, quindi ho scelto questi otto famosi luoghi che devono essere visitati:

• Sacre Coeur
• Louvre
• Montmartre
• Port de Suffren
• Arco di Trionfo
• Av. Champs Élysées
• Notre Dame
• Tour Eiffel

Dal momento che il problema consiste nel trovare un percorso di distanza minima, i dati effettivi di cui abbiamo bisogno sono i dati di distanza, che dipendono dai luoghi e dalle loro posizioni geografiche relative. Come calcolare i dati di distanza dalle posizioni geografiche sarà affrontato nello sprint 4, poiché coprirlo ora comporterebbe un diversivo (gioco di parole) che distoglierebbe l’attenzione dal focus principale qui: la costruzione del modello.

Quindi, per ora, considera di avere le distanze tra tutte le possibili coppie. Saranno fornite come file CSV nello prossimo sprint quando implementeremo il modello in Python. I dati sono simili a questi:

Chiameremo questa tabella la matrice delle distanze. Nota che, sebbene non particolarmente degno di una cartolina, l’hotel è incluso anche nella matrice, poiché conta come un altro luogo che deve essere nel tour finale. Per questo MVP, manteniamo le cose semplici e utilizziamo una matrice di distanze simmetrica, che è un modo elegante per dire che la distanza da A a B è la stessa distanza da B a A, per qualsiasi A e B. In contesti più avanzati, ciò non deve necessariamente essere vero in misura rilevante, rendendo questa approssimazione inefficace.

3. Definire un modello concettuale dalla descrizione del problema

Adesso siamo allo stadio rappresentato dal blocco verde nel diagramma di flusso qui sotto:

Lo scopo del modello concettuale è esprimere il problema usando parole, ma in un formato standardizzato, affinché la corrispondenza tra “frasi” e “oggetti matematici” diventi chiara nella successiva fase (formulazione del modello matematico). Possiamo formulare il nostro modello concettuale in questo modo:

(Sapendo)

Dati (insiemi e parametri):

• L’elenco dei luoghi da visitare
• La distanza tra ogni coppia di luoghi

(Dobbiamo decidere)

Decisioni: In quale ordine visitare i luoghi

(In modo tale che)

Obiettivo: Ridurre al minimo la distanza totale percorsa

(In modo tale che)

Vincoli:

• Tutti i luoghi vengono visitati
• Ogni luogo viene visitato solo una volta
• Ultimo luogo visitato è il luogo da cui siamo partiti (effettuiamo un tour chiuso)

👁️ Segui buone pratiche e, nella pratica, la bontà ti seguirà

Potresti aver pensato che il modello concettuale sembra piuttosto banale e non molto diverso dalla dichiarazione di problema “semplice” con cui abbiamo iniziato l’articolo. E avresti ragione. Per problemi piccoli come questo, può essere un passaggio ripetitivo. Ma per problemi più grandi, questa fase è indispensabile e tentare di costruire un modello matematico senza avere prima un modello concettuale di solito si traduce in caos (requisiti poco chiari o vaghi, formulazioni errate, codice con difetti, modelli impraticabili, ecc.). Pertanto, è fondamentale che costruiamo la disciplina ora e attraversiamo anche questa fase qui, anche se il valore marginale nel nostro caso semplice è molto basso. Concentrati su buone abitudini e i buoni risultati seguiranno.

4. Costruzione di un modello matematico dal modello concettuale

Abbiamo appena raggiunto “fase 3” del flusso di lavoro, in verde di seguito. La “fase del modello matematico“, probabilmente la fase più impegnativa di tutte, è dove il linguaggio naturale diventa matematica.

È in questa fase che non è permessa nemmeno la minima ambiguità.

Un modello matematico ben definito vale cento chiarimenti

In questa fase del nostro flusso di lavoro, costruiamo un modello puro per il TSP e nella fase successiva (coperta da “sprint 3”) costruiremo un’istanza del modello a partire dal dataset CSV che abbiamo spiegato in precedenza, con l’aiuto di Python.

📝 Ripasso della teoria: “modello astratto” vs “istanza del modello”

I modelli matematici (in OR) sono composti da “componenti”. Questi sono tutti gli elementi (equazioni, dati, ecc.) che rappresentano collettivamente un problema di una certa struttura. Ciò che definisce veramente un modello è la sua struttura, ovvero come i suoi componenti si relazionano tra loro, indipendentemente dai valori numerici particolari che questi componenti assumono in qualsiasi esempio specifico.

Un’istanza del modello è una “materializzazione” specifica di un “modello astratto” con dati concreti. Pertanto, di solito definiamo modelli astratti, quindi li riempiamo con dati di scenari particolari, il che genera istanze del modello. Sono queste istanze del modello che ottimizziamo per ottenere risultati concreti.

Nelle sottosezioni seguenti, toccherò brevemente i componenti che compongono un modello e i loro scopi, mentre li definisco. Sentiti libero di saltare queste spiegazioni e passare direttamente alle definizioni matematiche se non sei un principiante e conosci già le funzioni dei componenti del modello.

4.1. Mettere i dati in Set e Parametri

Tutti i dati di cui abbiamo bisogno risiedono nel dataframe mostrato nella Figura 2.1. Potremmo mantenere i dati solo lì, prelevando tutti i numeri da quel dataframe durante la creazione dei vincoli e dell’obiettivo del modello. In effetti, molte persone fanno così, ma è una cattiva abitudine che non scala bene con la dimensione del modello. Man mano che complessità del modello cresce, questo approccio richiede un codice di incollaggio sempre crescente (per gestire le operazioni sul dataframe) che potrebbe essere evitato se i dati fossero organizzati in altre strutture dati più orientate alla costruzione di modelli di ottimizzazione. Queste strutture dati sono gli insiemi e i parametri di un modello.

💡 Diverse strutture dati per soddisfare diverse esigenze

In caso tu ti stessi chiedendo “Perché creare insiemi e parametri, quando abbiamo già i dati di cui abbiamo bisogno in una tabella?“, la risposta breve è: perché farlo rende la costruzione del modello più facile, più generale e meno incline agli errori.

“Insiemi” sono i componenti del modello utilizzati per memorizzare le principali “entità” o “elementi” di un problema, mentre i “parametri” vengono utilizzati per memorizzare le proprietà numeriche di quelle entità o delle loro relazioni. Nel nostro esempio, i siti sono le principali “entità”, quindi saranno memorizzati in un insieme, mentre le distanze tra le coppie di siti sono le “proprietà numeriche” delle loro relazioni, quindi saranno memorizzate come parametri. A livello di implementazione, è anche molto utile fare questa categorizzazione perché ogni componente serve una funzione diversa che faciliterà la costruzione del modello:

• La funzione degli insiemi è la memorizzazione e manipolazione comoda degli indici. Questi indici sono gli ID o i nomi che rappresentano le diverse “entità” del problema e vengono utilizzati per indicizzare i parametri in modi comodi per la creazione di vincoli e obiettivi.

• La funzione dei parametri è la memorizzazione e manipolazione comoda delle proprietà numeriche delle “entità” da cui sono indicizzati, e questi sono i numeri che effettivamente compaiono nei vincoli e negli obiettivi.

Dal nostro modello concettuale, abbiamo:

• L’elenco dei siti da visitare, che definiamo come l’Insieme 𝕊:

La frase “indicizzati da 𝑖, 𝑗” è posta accanto alla definizione dell’insieme per segnalare che ogni volta che gli indici 𝑖 o 𝑗 vengono utilizzati nel modello, rappresentano membri di 𝕊. In questo modo, quando abbiamo vari insiemi e quindi più indici in uso, è più facile ricordare il significato di ogni indice.

• La distanza tra ogni coppia di siti, che definiamo come il parametro indicizzato 𝐷ᵢⱼ:

Il parametro è chiamato “indicizzato” semplicemente per indicare che non è un parametro scalare (ossia un singolo numero), ma una matrice 2-D di numeri. Per recuperare un numero da questo parametro indicizzato, è necessario specificare due indici, 𝑖 e 𝑗, che a loro volta verranno prelevati dall’insieme 𝕊.

𝕊 e 𝐷ᵢⱼ sono gli unici “componenti dati” presenti nel modello concettuale. Ma ciò non dovrebbe limitare la nostra capacità di pensare ad altri insiemi o parametri che si rivelano utili nella costruzione di un modello.

A titolo esemplificativo, si noti che gli indici di 𝐷ᵢⱼ, 𝑖 e 𝑗, sono membri di 𝕊 ma non possono coincidere. Se coincidessero, la distanza sarebbe zero, che è un dato banale. Inoltre, non andremmo mai da un luogo a sé stesso, quindi è inutile considerare le coppie (𝑖, 𝑖) del tutto. Pertanto, è utile limitare le combinazioni che le coppie (𝑖, 𝑗) possono assumere, in modo che la modellizzazione diventi più facile (e gli errori meno probabili). A tal fine, creiamo ora un altro insieme, 𝔸, derivato da 𝕊, che contiene tutte le coppie (𝑖, 𝑗) di siti diversi. Ogni coppia rappresenta un arco che collega il sito 𝑖 al sito 𝑗, da cui il simbolo 𝔸.

📝 Un arco è semplicemente un “collegamento diretto” tra due nodi di una “rete”. Pensate a un arco (𝑖, 𝑗) come a un vettore che parte da 𝑖 e termina a 𝑗. Quando il “collegamento” tra due nodi non è diretto (ossia, la direzione è irrilevante), si usa il termine “spigolo”, poiché dire “arco non diretto” tutto il tempo sarebbe troppo verboso. Anche le persone nella Teoria dei Grafi vogliono essere efficienti.

Una buona proprietà di 𝔸 è che rappresenta il dominio su cui 𝐷ᵢⱼ è definito, e come vedremo durante l’implementazione del modello in Python, definire esplicitamente un tale dominio lo rende riutilizzabile per altri componenti del modello, ed è anche conveniente.

• Insieme di archi possibili tra siti diversi:

4.2. Codifica delle decisioni nelle variabili

Dal momento che stiamo costruendo un modello in modo che possa indicarci quali azioni dovremmo intraprendere, e queste azioni prescritte ci sono sconosciute prima che il modello venga ottimizzato, dobbiamo codificare in variabili tutte le azioni potenziali che potremmo intraprendere.

Ma come definiamo tali azioni potenziali? Dal nostro modello concettuale, la “decisione” generica che dobbiamo prendere è l'”ordine in cui visitare i siti”. Questo “ordine” si riferisce a un percorso tra tutti i percorsi possibili che potremmo seguire durante un tour. L’idea chiave è che un percorso è costituito da una sequenza di archi che collegano nodi individuali (cioè siti). Pertanto, decidere di fare un determinato percorso significa effettivamente decidere di percorrere una determinata sequenza di archi. Queste “decisioni atomiche” su se attraversare o meno un determinato arco che collega due siti sono le decisioni che vogliamo codificare come variabili.

“Se andare o meno dal sito A al sito B” è chiaramente una decisione binaria: o vado, o non vado. A causa di questa natura, le variabili decisionali devono essere binarie (cioè prendere solo i valori 0 o 1) e sono definite solo per gli archi validi (per i quali il derivato 𝔸 è utile ora). In termini matematici:

C’è una variabile decisionale unica per ogni arco possibile (𝑖, 𝑗), ma quando il modello è ottimizzato, saremo interessati solo alle variabili che assumono il valore 1, poiché indicano quali archi devono essere attraversati. Ad esempio, se la variabile 𝛿ᵢⱼ, con 𝑖=hotel e 𝑗=Louvre, assume il valore 1, significa che dovremmo andare dall’hotel al Louvre come parte del nostro tour.

4.3. Definizione dell’obiettivo

Immaginiamo di avere 4 punti, 𝑎, 𝑏, 𝑐, 𝑑, e seguiamo il percorso 𝑎 → 𝑏 → 𝑐, in cui il punto 𝑑 non viene visitato. La sua distanza totale è la somma delle distanze dei suoi archi: 𝐷ᵃᵇ + 𝐷ᵇᶜ. Ma, se non sappiamo in anticipo quale percorso seguire, come rappresentiamo la distanza totale di questo percorso sconosciuto?

💡 Proprio perché il percorso ottimale è sconosciuto, abbiamo bisogno di un’espressione che copra tutti i percorsi possibili, ma che si riduca alla distanza del “miglior percorso” quando il modello è ottimizzato.

Sfruttando il fatto che ogni arco attraversato (𝑖, 𝑗) avrà 𝛿ᵢⱼ = 1, e ogni arco non attraversato (𝑖′,𝑗′) avrà 𝛿ᵢᑊⱼᑊ = 0, possiamo creare un’espressione che, una volta decise le variabili, si riduca alla distanza totale del percorso percorso. Il modo per farlo è “sommare tutte le potenzialità”, cioè fare la somma su tutte le possibili distanze degli archi 𝐷ᵢⱼ pesate dalle loro “variabili di arco” binarie 𝛿ᵢⱼ, e lasciare che gli 0 e gli 1 che quelle variabili assumeranno decidano quali distanze rimangono (𝐷ᵢⱼ × 1 = 𝐷ᵢⱼ) e quali svaniscono (𝐷ᵢⱼ × 0 = 0), nell’espressione per la distanza totale. Questa “somma delle potenzialità” rappresenta la distanza totale che il tour finale coprirà, quindi sarà il nostro obiettivo (denominato 𝑍) da minimizzare.

Matematicamente, questo si esprime come:

Nota come la sommatoria a destra sia diventata più semplice da leggere (e implementare) grazie all’uso di 𝔸, il dominio (insieme degli indici) sia per 𝐷ᵢⱼ che per 𝛿ᵢⱼ.

Inoltre, notiamo che l’obiettivo costituisce la nostra definizione di bontà. Poiché vogliamo minimizzarlo, un valore più basso è meglio di un valore più alto, quindi ovviamente, il valore minimo è il valore migliore. I valori delle variabili decisionali 𝛿ᵢⱼ che corrispondono a questo valore “migliore” dell’obiettivo costituiscono la soluzione (ottimale) al problema e saranno trovati dal processo di ottimizzazione.

4.4. Creazione dei vincoli

Dal nostro modello concettuale, abbiamo:

1. Tutti i siti vengono visitati.
2. Ogni sito viene visitato una sola volta.
3. Ultimo sito visitato è il sito da cui siamo partiti (facciamo un tour chiuso).

Rendiamoci conto che il requisito (1) è già “incluso” nel requisito (2), poiché se ogni sito viene visitato solo una volta, ciò implica che ogni sito viene visitato e quindi tutti i siti vengono visitati. Quindi, scartiamo la necessità di un vincolo separato per il requisito (1) e ci concentriamo su come modellare il requisito (2) come un vincolo.

Dire che “ogni sito viene visitato una sola volta” è lo stesso che dire che “ogni sito viene visitato e lasciato una sola volta”. E quella frase, a sua volta, è equivalente a queste due frasi insieme: “ogni sito viene visitato solo una volta” e “ogni sito viene lasciato solo una volta”. Modelliamo separatamente le “frasi”:

• Ogni sito viene visitato solo una volta:

È utile leggere l’intera espressione da destra a sinistra. Se prima vedi su quali indici è definito il vincolo, sarà più facile interpretare il significato della definizione del vincolo sul lato sinistro. Leggerei questo vincolo ad alta voce come:

per ogni sito 𝑗 appartenente all’insieme di tutti i siti 𝕊, la somma di tutti gli archi potenziali 𝛿ᵢⱼ che arrivano a 𝑗 deve essere uguale a 1, il che significa che deve avvenire solo un arco entrante a 𝑗. O, in modo più colloquiale: ogni sito deve essere visitato solo da un altro sito.

• Ogni sito viene lasciato solo una volta:

Leggerei questo vincolo come:

per ogni sito 𝑖 appartenente all’insieme di tutti i siti 𝕊, la somma di tutti gli archi potenziali 𝛿ᵢⱼ che partono da 𝑖 deve essere uguale a 1, il che significa che deve avvenire solo un arco uscente da 𝑖. O, in modo più colloquiale: ogni sito deve partire solo verso un altro sito.

Ci resta solo il requisito (3). Afferma che il percorso ottimale deve finire nello stesso sito da cui è iniziato, o equivalentemente, che il percorso deve essere un tour (un circuito chiuso). Ecco una possibile linea di ragionamento che si può avere a prima vista: “Poiché abbiamo già creato dei vincoli per garantire che ogni sito sia entrato e uscito una volta, ciò implica che il percorso risultante deve essere chiuso, poiché è impossibile che un sito sia un”pozzo” (ossia un sito ha un arco entrante ma nessun arco uscente) o che sia una”fonte” (ossia un sito ha un arco uscente ma nessun arco entrante). Pertanto, i due vincoli precedenti, presumibilmente, costringono la traiettoria finale ad essere un circuito chiuso”.

È corretta questa linea di ragionamento? Adottiamo un approccio sperimentale. Supponiamo che questa ragionamento sia corretto e proviamo a risolvere il modello così com’è adesso. Quando osserviamo la soluzione, vedremo se sembra giusta o se c’è qualcosa di sbagliato. Se i risultati sono sbagliati (o non hanno senso in alcun modo), possiamo sempre tornare indietro e rivedere la nostra logica (cosa che accade spesso nei progetti reali). L’implementazione, la soluzione e la “validazione sperimentale” sono ciò che viene trattato nel nostro “prossimo sprint”, in cui viene creato un modello Python, risolto, ispezionato e riformulato in base ai risultati ottenuti.

Quindi, concludiamo qui (in modo provvisorio) la fase di “formulazione del modello matematico”. Prossima tappa: l’implementazione del “modello informatico”, eseguita in Implementazione, risoluzione e visualizzazione del Problema del Commesso Viaggiatore con Python.

Arriveranno altri articoli di “sprint” in futuro, quindi se sei desideroso di accompagnarmi in questo viaggio, resta sintonizzato e controlla la timeline del progetto nella sezione 3 del primo articolo di questa serie, per accedere direttamente allo sprint desiderato e seguire il lavoro svolto.

Inoltre, sentiti libero di seguirmi, farmi domande nei commenti, farmi dei feedback, o contattarmi su LinkedIn.

Grazie per aver letto e ci vediamo nel prossimo articolo! 📈😊

Riferimenti:

• Wikipedia. Il Problema del Commesso Viaggiatore