Validi Lower Bound al Single Truck and Trailer Routing Problem

Accorsi, Luca (2017) Validi Lower Bound al Single Truck and Trailer Routing Problem. [Laurea magistrale], Università di Bologna, Corso di Studio in Ingegneria e scienze informatiche [LM-DM270] - Cesena, Documento full-text non disponibile
Il full-text non è disponibile per scelta dell'autore. (Contatta l'autore)

Abstract

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.

Abstract
Tipologia del documento
Tesi di laurea (Laurea magistrale)
Autore della tesi
Accorsi, Luca
Relatore della tesi
Correlatore della tesi
Scuola
Corso di studio
Ordinamento Cds
DM270
Parole chiave
ottimizzazione combinatoria,metodi column generation,rilassamento lagrangiano,programmazione a numeri interi,vehicle routing
Data di discussione della Tesi
5 Ottobre 2017
URI

Altri metadati

Gestione del documento: Visualizza il documento

^