Validi Lower Bound al Single Truck and Trailer Routing Problem

Il Single Truck and Trailer Routing Problem (STTRP) consiste nel servire un insieme di clienti con una richiesta conosciuta utilizzando un veicolo localizzato in un deposito centrale. Questo veicolo è composto da una motrice ed un rimorchio. A causa di vincoli di accessibilità alcuni clienti possono essere raggiunti soltanto dalla motrice, quindi, il veicolo prima di poterli servire deve lasciare il rimorchio in un'area di parcheggio appropriata. Il STTRP ha diverse applicazioni pratiche soprattutto nella distribuzione in aree rurali, come ad esempio la raccolta del latte dalle fattorie, ma anche in ambienti urbani dove utilizzare veicoli di grande dimensione è difficile o proibito. La letteratura descrive diversi metodi euristici e pochi metodi esatti ognuno dei quali affronta una variante del problema leggermente diversa. In questa tesi è presentata una nuova formulazione matematica con un numero esponenziale di variabili che è utilizzata per calcolare due diversi lower bound ed un metodo esatto che risolve problemi con fino a 50 vertici ed un'istanza da 100 vertici finora non risolta all'ottimo. I risultati di calcolo preliminari ottenuti su un insieme di istanze prese dalla letteratura mostrano come i lower bound calcolati dominino quelli disponibili. La tesi termina infine con la descrizione di alcune possibili future direzioni di ricerca che mirano a migliorare i metodi proposti.