Transportation problems

Public transportation analysis and planning - Models and algorithms are studied to analyze the public transportation passenger demand in urban and suburban areas. The aim of the research is to study mathematical properties of the models and to verify their fitness on real transit networks. More specifically, the following models have been proposed:
  • models generalizing the well known equilibrium models, which take into account hyperpaths in urban transit networks [NP86, NP87, NP88, NP89];
  • stochastic models for the urban case, based on hyperpaths in the transit network [NPG98, PP97].
  • models devoted to the suburban case [CMP95, CMP96, NPM98];
  • models for flexible transit systems [MNP97, MNP99];
  • demand estimation models, with emphasis on the interrelation between demand and assignment problems [NMP88, NPI96].

    Resource management - Another topic in public transportation addresses resource management. Particular vehicle scheduling problems (with time windows and maintenance constraints) are currently approached both in airline and urban transportation; most of the problems are solved by using NonDifferentiable optimization. Among the others:

  • problems regarding the determination of uniform travelling time shifts [CMS94];
  • crew and vehicle scheduling problems in the mass transit setting, with emphasis on algorithm design and implementation [CGN95, N98];
  • routing and scheduling problems arising in freight transportation [EGMW97], for which a heuristic method which combines simulated annealing and tabu search techniques has been proposed [EM93].

    Evaluation of transportation systems - A new research line, recently opened, is the use of multicriteria and data envelopment analysis techniques for the evaluation of transportation systems [F98, FGS99].

    Shortest path problems - An activity is going on aimed at the analysis and design of fast shortest path algorithms for static and dynamic networks [GP84, PS98].

    General - Some reviews on transportation problems have been produced [MP97, PS99].

    [A01] D. Ambrosino "Progetto di reti distributive: alcuni modelli ed un approccio di ricerca locale basato su tecniche multiscambio", Ph.D. Dissertation in "Matematica per le Decisioni Economiche", Università di di Pisa, 2001

    [ACGP92] A. Albano, P. Carraresi, L. Girardi and S. Pallottino "Un sistema informatico per la valutazione ed il controllo delle prestazioni di una azienda di trasporto pubblico", Dipartimento di Informatica, Università di Pisa, 1992

    [AOPS01a] R.K. Ahuja, J.B. Orlin, S. Pallottino and M.G. Scutellà "Minimum time and minimum cost path problems in street networks with traffic lights" Transportation Science, to appear, 2001 (previously appeared as TR 99-13, Dipartimento di Informatica, Università di Pisa, 1999, revised May 2001)

    [AOPS01b] R.K. Ahuja, J.B. Orlin, S. Pallottino and M. G. Scutellà Dynamic shortest paths minimizing travel times and costsTR 01-23, Dipartimento di Informatica, Università di Pisa, 2001 (submitted to Networks)

    [AS01] D. Ambrosino, M.G. Scutellà "Distribution network design: new problems and related models" TR 01-5, Dipartimento di Informatica, Università di Pisa, 2001

    [CFG01] T.G. Crainic, A. Frangioni and B. Gendron "Bundle-based Relaxation Methods for Multicommodity Capacitated Fixed Charge Network Design Problems" Discrete Applied Mathematics, to appear, 2001 (previously appeared as Publication CRT-98-45, Centre de Recherche sur les Transports, Université de Montreal, 1998)

    [CG01] P. Cappanera and G. Gallo "On the Airline Crew Rostering Problem" TR 01-08 , Dipartimento di Informatica, Università di Pisa, 2001 (submitted to Operations Research)

    [CGN95] P. Carraresi, L. Girardi and M. Nonato "Network models, lagrangean relaxation and subgradient bundle approach in crew scheduling problems", (J.R. Daduna, I. Branco and J.M. Paixao, eds.) Computer-aided Transit Scheduling, Lecture Notes on Economics and Mathematical Systems 430, Springer-Verlag, 188-212, 1995.

    [CGPS01] I. Chabini, A. Glenn, S. Pallottino and M. G. Scutellà; Reoptimization algorithms for minimum-time path problems in dynamic networks, accepted in Proceedings of Transportation Research Board Annual Meeting 2002

    [CGR93] P. Carraresi, G. Gallo and G. Rago "A hypergraph model for constraint logic programming and applications to bus drivers' scheduling" Annals on Mathematics and Artificial Intelligence 8, 247-270, 1993

    [CMP95] P. Carraresi, F. Malucelli and S. Pallottino "On the regional mass transit assignment problem" (A. Sciomachen, ed.) Optimization in Industry 3, Wiley, 19-33, 1995.

    [CMP96] P. Carraresi, F. Malucelli and S. Pallottino "Regional mass transit assignment with resource constraints", Transportation Research B 30, 81-98, 1996.

    [CMP99] D. Caputi, P. Mentrasti and S. Pallottino "Un metodo di supporto alle decisioni nei trasporti intermodali" Proceedings of INPUT'99, University of Venice, June 1999, 371-384

    [CMS94] P. Carraresi, F. Malucelli and C. Sandi "Partitioning the service period of a bus line into uniform travelling time shifts via network flow algorithms", Dipartimento di Informatica, Univ. di Pisa, TR 21/94, 1994.

    [CP91] S. Catoni, S. Pallottino; "Traffic equilibrium paradoxes" Transportation Science 25, 240-244, 1991

    [CP92] P. Carraresi, S. Pallottino "Integrazione fra strumenti di pianificazione e gestione delle risorse per la valutazione ed il controllo delle prestazioni in una azienda di trasporto pubblico", Giornata di studio, Brescia, 5 Giugno 1992

    [EGMW97] L. Equi, G. Gallo, S. Marziale and A. Weintraub "A combined transportation and scheduling problem", European Journal of Operational Research 97, 94-104, 1997.

    [F98] F. Farinaccio "Data Envelopment Analysis come strumento di Analisi Multicriteria", Ph.D. Thesis in Mathematics for Economic Decisions, University of Florence, 1998.

    [FGS99] F. Farinaccio, G. Gallo and C. Sandi "Valutazioni di produttività e misure di efficienza con applicazioni al settore del trasporto pubblico", (S. Pallottino and A. Sciomachen, eds.) Scienze delle Decisioni per i Trasporti" F. Angeli, Milano, 1999, 783-808.

    [FP99] P. Ferrari, S. Pallottino "Il trasporto individuale urbano" Scienze delle Decisioni per i Trasporti, S. Pallottino and A. Sciomachen eds., F. Angeli, Milano, 1999, 509-537

    [GD01] G.Gallo, F. Di Miele "Dispatching Buses in Parking Depots" Transportation Science 35 (3), 322-330, 2001

    [GLNP89] G. Gallo, G. Longo, S. Nguyen and S. Pallottino "Gli ipergrafi orientati: un nuovo approccio per la formulazione e risoluzione di problemi combinatori" Atti delle Giornate AIRO'89, 217-236, 1989

    [GLNP93] G. Gallo, G. Longo, S. Nguyen and S. Pallottino "Directed hypergraphs and applications" Discrete Applied Mathematics 42, 177-201, 1993

    [GP84] G. Gallo and S. Pallottino "Shortest path methods in transportation models", (M. Florian, ed.) Transportation Planning Models, North-Holland, 227-256, 1984.

    [GP88] G. Gallo, S. Pallottino "Shortest path algorithms" Annals of Operations Research 13, 3-79, 1988

    [MNP97] F. Malucelli, M. Nonato and S. Pallottino "Modelli di trasporto collettivo in condizioni di domanda debole", Proceedings of III Convegno del Progetto Finalizzato Trasporti 2, Taormina, 1997.

    [MNP99] F. Malucelli, M. Nonato and S. Pallottino "Demand Adaptive Systems: some proposals on flexible transit" (T.A. Ciriani, S. Gliozzi, E.L. Johnson and R. Tadei, eds.) Operations Research in Industry, McMillan Press, London, 1999, 157-182.

    [MP97] F. Malucelli and S. Pallottino "Metodologie matematiche per l'analisi dell'efficienza del trasporto collettivo urbano ed interurbano", (C.S. Bertuglia and F. Vaio, eds.) La Città e le sue Scienze, Vol. IV - Le Metodologie delle Scienze della Città, Franco Angeli, Milano, 249-283, 1997.

    [N98] M. Nonato "An integrated approach to extra-urban crew and vehicle scheduling" (M. Labbé, G. Laporte, K. Tanczos and P. Toint, eds.) O.R. and Decision Aid Methodologies in Traffic and Transportation Management, Nato-Asi F.166, 319-335, 1998.

    [NMP88] S. Nguyen, E. Morello and S. Pallottino "Discrete time dynamic estimation model for passenger origin/destination matrices on transit networks" Transportation Research 22B, 251-260, 1988.

    [NP86] S. Nguyen and S. Pallottino "Assegnamento dei passeggeri ad un sistema di linee urbane: determinazione degli ipercammini minimi" Ricerca Operativa 38, 29-74, 1986.

    [NP87] S. Nguyen and S. Pallottino "Traffic assignment for large scale transit networks, (A.R. Odoni, L. Bianco e G. Szegö, eds.) Flow Control of Congested Networks, Computers and Systems Sciences, NATO ASI 38, Springer-Verlag, Berlin, 25-34, 1987.

    [NP88] S. Nguyen and S. Pallottino "Equilibrium traffic assignment for large scale transit networks" European Journal of Operational Research 37, 176-186, 1988.

    [NP89] S. Nguyen and S. Pallottino "Hyperpaths and shortest hyperpaths" (B. Simeone, ed.) Combinatorial Optimization, Lecture Notes in Mathematics 1403, Springer-Verlag, Berlin, 258-271, 1989.

    [NP91] S. Nguyen, S. Pallottino "Ipercammini attivi in reti di trasporto" Ricerca Operativa 57, 91-115, 1991

    [NPG98] S. Nguyen, S. Pallottino and M. Gendreau "Implicit enumeration of hyperpaths in logit models for transit networks", Transportation Science 32, 54-64, 1998.

    [NPI96] S. Nguyen, S. Pallottino and D. Inaudi "Postoptimizing equilibrium flows on large scale networks" European Journal of Operational Research 91, 507-516, 1996.

    [NPM01] S. Nguyen, S. Pallottino and F. Malucelli "A modeling framework for the passenger assignment on a transport network with time-tables", Transportation Science 35(3), 238-249, 2001.

    [NPS01] S. Nguyen, S. Pallottino and M.G. Scutellà "A new dual algorithm for shortest path reoptimization" Transportation and Nework Analysis - Current Trends, M. Gendreau e P. Marcotte eds., Kluwer, to appear, 2001 (previously appeared as TR 99-14, Dipartimento di Informatica, Università di Pisa, 1999, revised July 2000)

    [PP97] P. Paiano and S. Pallottino "Motivazioni comportamentali e insiemi attrattivi nei modelli stocastici per il trasporto collettivo", Sistemi di Trasporto 20, 25-48, 1997.

    [PS96] S. Pallottino, A. Schettino "Assegnazione dei passeggeri a una rete pubblica interurbana mediante l'enumerazione dei cammini attivi" TR 96-9, Dipartimento di Informatica, Università di Pisa, 1996

    [PS98] S. Pallottino and M.G. Scutellà "Shortest path algorithms in transportation models: classical and innovative aspects" (P. Marcotte and S. Nguyen, eds.) Equilibrium and Advanced Transportation Modelling, Kluwer, 245-281, 1998.

    [PS99a] S. Pallottino, A. Schettino "Il trasporto collettivo urbano" Scienze delle Decisioni per i Trasporti, S. Pallottino and A. Sciomachen eds., F. Angeli, Milano, 1999, 619-655

    [PS99b] S. Pallottino, A. Sciomachen "Trasporto urbano e parcheggio", Scienze delle Decisioni per i Trasporti, S. Pallottino and A. Sciomachen eds., F. Angeli, Milano, 1999, 585-605

    [PS99c] S. Pallottino, A. Sciomachen (Editors) Scienze delle Decisioni per i Trasporti, Collana Trasporti 1797.14, F. Angeli, Milano, 1999

    [PS01] S. Pallottino, M.G. Scutellà "A new algorithm for reoptimizing shortest paths when the arc costs change", TR 01-11, Dipartimento di Informatica, Università di Pisa, 2001 (submitted to Operations Research Letters)

    [S91] A. Schettino "Sulla determinazione degli ipercammini minimi per modelli di trasporto pubblico urbano" Ricerca Operativa 59, 53-87, 1991

    [S01] M.P. Scaparra "Multi-exchange algorithms for some capacitated facility location problems", Ph.D. Dissertation in "Matematica per le Decisioni Economiche", Università di Pisa, in progress

    [SS01] M.P.Scaparra, M.G. Scutellà "Facilities, Locations, Customers: Building blocks of location models. A survey" TR 01-18, Dipartimento di Informatica, Università di Pisa, 2001