Affordable Access

Heuristic algorithms for the travelling deliveryman problem

Authors
Publication Date
Keywords
  • Tdp
  • Travelling Deliveryman Problem
  • Algoritmi Di Ottimizzazione
  • Scuola :: 843884 :: Ingegneria E Architettura
  • Cds :: 0234 :: Ingegneria Informatica [Ls-Dm509]
  • Sessione :: Terza

Abstract

UNIVERSITÀ DEGLI STUDI DI BOLOGNA ALMA MATER STUDIORUM - UNIVERSITÀ DI BOLOGNA SCUOLA DI INGEGNERIA E ARCHITETTURA DIPARTIMENTO DI INGEGNERIA DELL‟ENERGIA ELETTRICA E DELL‟INFORMAZIONE “GUGLIELMO MARCONI” - DEI CORSO DI LAUREA SPECIALISTICA IN INGEGNERIA INFORMATICA TESI DI LAUREA in Algoritmi di ottimizzazione L-S Heuristic Algorithms for the Travelling Deliveryman Problem CANDIDATO RELATORE: Ahmad Hariri Chiar.mo Prof. Paolo Toth CORRELATORE Dott. Roberto Roberti Anno Accademico 2012/13 Sessione III INDICE 1. Introduzione al problema-------------------------------------------p.3 2. Letteratura------------------------------------------------------------p.8 3. Generalized VNS---------------------------------------------------p.11 4. Implementazione GVNS------------------------------------------p.22 5. Risultati computazionali-------------------------------------------p.26 6. Conclusioni----------------------------------------------------------p.33 7. Referenze------------------------------------------------------------p.34 8. Ringraziamenti------------------------------------------------------p.35 9. Appendice-----------------------------------------------------------p.36 CAPITOLO 1 INTRODUZIONE AL PROBLEMA 1.1- Descrizione del problema: Il Travelling Deliveryman Problem (TDP) è un problema NP-difficile, in cui si deve determinare un circuito che visiti una sola volta tutti i nodi di un grafo (circuito Hamiltoniano) in modo da minimizzare il tempo totale di attesa dei nodi clienti per essere visitati, cioè il “peso” di un arco dipende dal suo “costo” e dalla sua posizione nel circuito. Alcune applicazioni del TDP possono essere trovate nei problemi di schedulazione

There are no comments yet on this publication. Be the first to share your thoughts.