Vai al contenuto| Home page|

   Ti trovi in: HOME »Programmi, progetti e risultati »I progetti »PRIN - Programmi di ricerca di Rilevante Interesse Nazionale»Programma di ricerca
INIZIO_TESTO_DA_INDICIZZARE

PROGRAMMA DI RICERCA 2005

italiano - english
Unità di Ricerca
Programmi di ricerca simili:
Classificazione scientifico-disciplinare
Classificazione brevettuale
Classificazione geografica
Bibliografia
R.K. Ahuja, J.B. Orlin, S. Pallottino, M.G. Scutella', "Dynamic Shortest Paths Minimizing Travel Times and Costs", Networks 41 (2003) 197-205.

R. Baldacci, L. Bodin, A. Mingozzi, "The Multiple Disposal Facilities and Multiple Inventory Locations Rollon-Rolloff Vehicle Routing Problem", Computers and OR (to appear).

R. Baldacci, E.A. Hadjiconstantinou, A. Mingozzi, "An Exact Algorithm for the Traveling Salesman Problem with Deliveries and Collections", Networks 42 (2003) 26-41.

R. Baldacci, E.A. Hadjiconstantinou, A. Mingozzi. "An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-commodity Network Flow Formulation", Operations Research 52 (2004) 723-738.

R. Baldacci, V. Maniezzo, A. Mingozzi, "An Exact Method for the Car Pooling Problem Based on Lagrangian Column Generation", Operations Research 52 (2004) 422-439.

C. Berge, "Balanced Matrices", Mathematical Programming 2 (1972), 19-31.

N. Bianchessi, G. Righini, "Heuristic Algorithms for the Vehicle Routing Problem with Simultaneous Pick-up and Delivery", Computers & OR (to appear).

M.A. Boschetti, A. Mingozzi, "The Two-dimensional Finite Bin Packing Problem. Part I: New Lower Bounds for the Oriented Case", 4OR 1 (2003) 27-42.

M.A. Boschetti, A. Mingozzi, "The Two-dimensional Finite Bin Packing Problem. Part II: New Lower and Upper Bounds", 4OR 1 (2003) 135-148.

J. Bramel, D. Simchi-Levi, "Set-Covering Based Algorithms for the Capacitated VRP", in P. Toth, D. Vigo, eds., The Vehicle Routing Problem, Monographs on Discrete Mathematics and Applications, SIAM (2002) 85-106.

P. Cappanera, M.Trubian, "A Local-Search-Based Heuristic for the
Demand-Constrained Multidimensional Knapsack Problem", INFORMS Journal on Computing 17 (2005) 82-98.

A. Caprara, M. Monaci, "On the 2-Dimensional Knapsack Problem", Operations Research Letters 32 (2004) 5-14.

I.M. Chao, B.L. Golden, E.A. Wasil, "An Improved Heuristic for the Period Vehicle Routing Problem", Networks 26 (1997) 105-119.

M. Conforti, G. Cornuejols, "Balanced 0,+-1 matrices, Bicoloring and Total Dual Integrality", Mathematical Programming 71 (1995) 249-258.

M. Conforti, G. Cornuejols, A. Kapoor, K. Vuskovic, "Perfect Matchings in Balanced Hypergraphs", Combinatorica 16 (1996) 325-329.

M. Conforti, G. Cornuejols, M. R. Rao, "Decomposition of Balanced Matrices", Journal of Combinatorial Theory B 77 (1999), 292-406.

M. Conforti, A. Galluccio, G. Proietti, "Edge-connectivity Augmentation and Network Matrices", in J. Hromkovic, M. Nagl, B. Westfechtel eds., Graph-Theoretic Concepts in Computer Science, LNCS 3353, Springer Verlag (2004) 355-364.

J.F. Cordeau, M. Gendreau, G.Laporte, "A Tabu Search Heuristic for Periodic and Multi-Depot Vehicle Routing Problems", Networks 30 (1997) 105-119.

M. Dell'Amico, G. Righini, M. Salani, "A Branch-and-price Approach to the Vehicle Routing Problem with Simultaneous Distribution and Collection", Transportation Science (to appear).

O. Faroe, D. Pisinger, M. Zachariasen, "Guided Local Search for the Three-Dimensional Bin Packing Problem", INFORMS Journal on Computing 15 (2003) 267-283.

S.P. Fekete, J. Schepers. "A General Framework for Bounds for Higher-dimensional Orthogonal Packing Problems" Mathematical Methods of Operations Research, 60 (2004), 311-329.

S.P. Fekete, J. Schepers, "New Classes of Fast Lower Bounds for Bin Packing Problems", Mathematical Programming 91 (2001) 11-31.

S.P. Fekete, J.Schepers. "An Exact Algorithm for Higher-dimensional Orthogonal Packing", Operations Research (to appear).

C. Filippi, A. Agnetis, "An Asymptotically Exact Algorithm for the High-multiplicity Bin Packing Problem", Mathematical Programming (to appear).

M. Fischetti, A. Lodi, P. Toth, "Exact Methods for the Asymmetric Traveling Salesman Problem", in G. Gutin, A. Punnen, eds., The Traveling Salesman Problem and its Variations, Kluwer (2002) 169-206.

M. Fischetti, P. Toth, "A Polyhedral Approach to the Asymmetric Traveling Salesman Problem", Management Science 43 (1997) 1520-1536.

M. Fischetti, P. Toth, D. Vigo, "A Branch and Bound Algorithm for the Capacitated Vehicle Routing Problem on Directed Graphs", Operations Research 42 (1994) 846-859.

B. Fleischmann, M. Gietz and S. Gnutzmann, "Time-Varying Travel Times in Vehicle Routing", Transportation Science 38 (2004) 160–173.

G.N. Frederickson, J. Ja'Ja', "Approximation Algorithms for Several Graph Augmentation Problems", SIAM Journal on Computing 10 (1981) 270-283.

R. Fukasawa, J. Lysgaard, M. Poggi de Aragao, M. Reis, E. Uchoa, F. Wernek, "Robust Branch-and-cut-and-price for the Capacitated Vehicle Routing Problem", in G. Nemhauser, D. Bienstock eds., Integer Programming and Combinatorial Optimization 10, LNCS 3064, Springer Verlag (2004) 1-15.

M. Gendreau, A. Hertz, G. Laporte, "A Tabu Search Heuristic for the Vehicle Routing Problem", Management Science 40 (1994) 1276-1290.

G. Gutin, A. Punnen, eds., The Traveling Salesman Problem and its Variations, Kluwer (2002).

S. Ichoua, M. Gendreau, J.-Y. Potvin, "Vehicle Dispatching with Time-dependent Travel Times", EJOR 144 (2003) 379–396.

G. Laporte, "Vehicle Routing", in M. Dell'Amico, F. Maffioli, S. Martello, eds., Annotated Bibliographies in Combinatorial Optimization, Wiley (1997) 223-240.

E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys, eds., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley (1985).

F. Li, B.L. Golden, E.A. Wasil, "Very Large-scale Vehicle Routing: New Test Problems, Algorithms, and Results", Computers and OR (to appear).

A. Lodi, S. Martello, M. Monaci, "Two-Dimensional Packing Problems: a Survey", EJOR 141 (2002) 241-252.

A. Lodi, S. Martello, D. Vigo, "Heuristic and Metaheuristic Approaches for a Class of Two-dimensional Bin Packing Problems", INFORMS Journal on Computing 11 (1999) 345-357.

A. Lodi, S. Martello, D. Vigo, "Recent Advances on Two-Dimensional Bin Packing Problems", Discrete Applied Mathematics 123 (2002) 379-396.

J. Lysgaard, A.N. Letchford, R.W.Eglese, "A New Branch-and-Cut Algorithm for the Capacitated Vehicle Routing Problem", Mathematical Programming 100 (2004) 423-445.

O. Marcotte, "The Cutting Stock Problem and Integer Rounding", Mathematical Programming, 33 (1985) 82-92.

A. Mingozzi, R. Baldacci e S. Giorgi, "An Exact Method for the Vehicle Routing Problem with Backhauls", Transportation Science 33 (1999) 315-329.

D. Pretolani "A Directed Hypergraph Model for Random Time-Dependent Shortest Paths", EJOR 123 (2000) 315-324.

S.Martello, D.Pisinger, D.Vigo, "The Three-Dimensional Bin Packing Problem", Operations Research 48 (2000) 256-267.

S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley (1990).

S. Martello, D.Vigo, "Exact Solution of the Two-Dimensional Finite Bin Packing Problem", Management Science 44 (1998) 388-399.

P. Toth, D. Vigo, "An Exact Algorithm for the Vehicle Routing Problem with Backhauls", Transportation Science 31 (1997).

P. Toth, D. Vigo, "A Heuristic Algorithm for the Symmetric and Asymmetric Vehicle Routing Problems with Backhauls", EJOR 113 (1999).

P. Toth, D. Vigo, "Models, Relaxations and Exact Approaches for the Capacitated Vehicle Routing Problem", Discrete Applied Mathematics 123 (2002) 487-512.

P. Toth, D. Vigo, eds., The Vehicle Routing Problem, Monographs on Discrete Mathematics and its Applications, SIAM (2002).

P. Toth, D. Vigo, "An Overview of Vehicle Routing Problems", in P. Toth, D. Vigo, eds., The Vehicle Routing Problem, Monographs on Discrete Mathematics and Applications, SIAM (2002) 1-26.

P. Toth, D. Vigo, "Branch-and-bound Algorithms for the Capacitated VRP", in P. Toth, D. Vigo, eds., The Vehicle Routing Problem, Monographs on Discrete Mathematics and Applications, SIAM (2002) 29-51.

P. Toth, D. Vigo, "VRP with Backhauls", in P. Toth, D. Vigo, eds., The Vehicle Routing Problem, Monographs on Discrete Mathematics and Applications, SIAM, (2002) 195-224.
Parole Chiave
OTTIMIZZAZIONE COMBINATORIA; PROGRAMMAZIONE INTERA; ALGORITMI EURISTICI ED APPROSSIMATI; BRANCH-AND-BOUND; BRANCH-AND-CUT; INSTRADAMENTO DI VEICOLI; CARICAMENTO DI VEICOLI; LOGISTICA; TRASPORTO MERCI

Problemi di routing e packing nell'ottimizzazione dei sistemi di trasporto

Università degli Studi di Bologna
Abstract
Nell'ambito di questo programma ci si propone di studiare alcuni problemi di ottimizzazione di notevole rilevanza nel campo della logistica e dei trasporti. I problemi considerati rientrano in due categorie fondamentali, tra loro interconnesse:
1)l'instradamento di veicoli, ossia la definizione di percorsi ottimali (a minimo costo, o minima durata, o minima lunghezza) nel rispetto di vincoli legati alla tecnologia adottata e/o alla metodologia di distribuzione;
2) l'impaccamento, ossia il caricamento nei veicoli degli elementi da trasportare, fatto in modo da ottimizzare l'occupazione di spazio, ossia il numero di veicoli necessari per il trasporto, nel rispetto dei vincoli legati alle capacita', alla sequenza di caricamento e ad ulteriori vincoli tecnologici.

I membri delle Unità di Ricerca coinvolte hanno svolto negli ultimi anni ricerche su questi temi, raggiungendo una notevole visibilità internazionale per la qualità dei risultati, sia teorici che applicativi, conseguiti. Sia separatamente (nell'ambito delle rispettive unità), sia congiuntamente (mediante collaborazioni in atto da anni tra i membri delle diverse unità), essi hanno sviluppato nuovi modelli di programmazione matematica, tecniche per il calcolo di bound, algoritmi esatti ed approssimati per la soluzione di numerosi problemi negli ambiti precedentemente considerati. Sono stati inoltre realizzati i corrispondenti codici di calcolo.

Nonostante il fatto che i membri >>>

Coordinatore Scientifico del Programma di Ricerca
Paolo TOTH Università degli Studi di BOLOGNA
Obiettivo del Programma di Ricerca
Obiettivo del programma di ricerca e' lo sviluppo di metodologie matematiche ed algoritmiche, nonche' la realizzazione di programmi di calcolo efficienti, per la soluzione esatta e/o approssimata di una serie di problemi legati alla definizione di percorsi ottimi per veicoli ed al loro caricamento, problemi questi di notevole rilevanza, sia dal punto di vista scientifico-metodologico che dal punto di vista applicativo, nel campo della logistica e dei trasporti.

Nei problemi di instradamento di veicoli (Vehicle Routing) occorre definire i percorsi ottimali di una flotta di veicoli localizzati in uno o piu' depositi, secondo diversi possibili criteri (quali il minimo costo, la minima durata, la minima lunghezza) nel rispetto di svariati vincoli che sorgono nei diversi contesti applicativi. Oltre al classico problema del commesso viaggiatore in grafi orientati e non, che costituisce la base teorica ed algoritmica per la grande maggioranza dei problemi di questo settore, lo sforzo maggiore di ricerca verrà impiegato nello studio di algoritmi in grado di risolvere una serie di casi di notevole rilevanza pratica. Oltre agli ovvi vincoli legati al rispetto delle capacità dei veicoli utilizzati, eventualmente diversi, verranno infatti considerati:
- vincoli sulle finestre temporali all'interno delle quali occorre effettuare le visite ai clienti;
- casi in cui occorre gestire contemporaneamente, nell'ambito dello stesso viaggio, sequenze di prelievi e >>>

Durata
24 mesi
Base di partenza scientifica nazionale o internazionale
Scopo della ricerca e' la realizzazione di modelli ed algoritmi approssimati ed esatti per la soluzione di alcuni importanti problemi di ottimizzazione per l'instradamento ("routing") e il caricamento ("packing") dei veicoli che si incontrano nella pianificazione e nella gestione operativa di sistemi logistici e di trasporto merci. Tutti i problemi considerati appartengono alla classe dei problemi NP-difficili e sono di grande rilevanza dal punto di vista sia metodologico che applicativo.

I problemi di instradamento ("Vehicle Routing Problem", VRP) riguardano la pianificazione ottimale dei viaggi di una flotta di veicoli localizzati presso uno o piu' depositi in modo da servire un insieme di clienti minimizzando il costo globale di trasporto. I problemi reali di VRP sono caratterizzati da numerosi vincoli di natura complessa e richiedono frequentemente un coordinamento tra i gestori dei depositi ed i clienti. I principali metodi esatti ed euristici utilizzati in letteratura per il VRP sono illustrati nei recenti volumi [Gutin e Punnen, 2002, Toth e Vigo, 2002]. Problemi di instradamento di grande interesse che si intendono approfondire in questa ricerca sono il classico problema del commesso viaggiatore, il "Capacitated VRP", il VRP multi-deposito con vincoli di finestre temporali e vincoli di "pick-up" e "delivery", il VRP periodico, il "Car Pooling Problem".

Il problema del commesso viaggiatore ("Traveling Salesman Problem", TSP) e' uno dei >>>