“ABARNET”

ABARNET Director

“Agent-Based Algorithms for Railway NETworks optimization” (ABARNET)

“Algoritmos Basados en Agentes Artificiales para Optimizar la Capacidad de Redes Ferroviarias” (ABARNET)

According to European Regulations, Raiway transport have to be liberalized. In this project, we research and develop new methodologies for slot allocation within the railway sector among the rail services companies. In particular, we will research the role of combinational auctions and agent based modelling.

The project main deliverable is a pilot model of combinational auction. We adapt the model to a subset of railway paths within the Spanish railway system. By means of simulation, we will design a set of recommendations about the auction market design.

KEYWORDS:

Yield management, agent based modelling, combinatory auctions, market design, transport.

“The study of combinatorial auctions has importance both practical and theoretical. In combinatorial auctions, our elegant models of resource allocation confront the true complexity of markets, where potential traders compete to buy or sell many different but related goods. Combinatorial auctions are the great frontier of auction theory today …”

ROGER MYERSON

Antecedentes y justificación del proyecto: la liberalización del sector ferroviario y el problema de asignación de capacidad a los operadores.

La Ley 39/2003 de 17 de noviembre del sector ferroviario español, modificada el 14 de octubre de 2014 reconoce el carácter estratégico del ferrocarril en España, y transpone varias Directivas Comunitarias que afectan a la liberalización del sector ferroviario en nuestro país, así como a la creación de un espacio ferroviario europeo. En concreto, y como paso previo, la ley separa en dos organizaciones las actividades de administración de la infraestructura -que gestionará ADIF-, de las del transporte –Renfe Operadora-. Además, en la misma ley se regula el acceso de nuevas compañías al mercado de transporte ferroviario, de forma que a partir del 1 de enero de 2005 se liberaliza el transporte de mercancías, y se aplaza para el año 2010 la liberalización del transporte de viajeros.

Sin embargo, el proceso de liberalización real del sector en España ha sufrido varios retrasos y no está exento de discusión en el ámbito político. El Informe de la Comisión Técnico-Científica para el Estudio de Mejoras en el Sector Ferroviario del 2014, aconseja la introducción de un periodo transitorio que permita una liberalización gradual: “Un proceso de liberalización totalmente abierto podría, dado el estrecho mercado existente, derivar en problemas económicos y de falta de rentabilidad que deteriorarían el servicio y la imagen del ferrocarril”

En cualquier caso, el “Pilar de Apertura de Mercado” descrito en el Cuarto Paquete Ferroviario de la UE, fija para 2019 la completa liberalización, para operadores europeos, del transporte interno de viajeros.

Más allá de los posibles intereses y reticencias de las distintas partes involucradas, una causa fundamental del retraso en la liberalización real estriba en la complejidad de la gestión de una red con múltiples actores, y en los procedimientos de asignación de trayectos y “ventanas” horarias de utilización (slot) así como en la fijación de los precios de uso de los mismos.

El proceso de asignación consiste en que la institución encargada de gestionar las infraestructuras ferroviarias otorga (“vende”) los derechos de circulación de un determinado número de trenes en un determinado tramo de la red viaria, en una franja horaria determinada. En otras palabras, el total de la red se divide en distintos tramos, y para cada tramo, se distinguen distintos intervalos temporales de utilización. El denominado “slot” se corresponde con los derechos de utilización de un tramo en un período temporal determinado.

Evidentemente, la falta de homogeneidad en la demanda de utilización por parte de los viajeros, tanto en tiempo como en destinos, hará que, en el caso genérico, varios operadores deseen operar sobre los mismos tramos y períodos temporales. Por ello, el gestor de infraestructuras debe establecer un procedimiento de asignación de los slots entre los posibles operadores (Stern and Turvey, 2003), de forma que se maximice alguna variable relacionada con la eficiencia del sistema o el servicio aportado a los ciudadanos.

Conceptualmente, la asignación es un proceso complejo debido a la gran variedad de factores que afectan (Bassanini et al. 2002): heterogeneidad en la demanda sobre distintos trayectos, que puede provocar congestiones en distintos tramos de la red; existencia de horas “punta” y horas de mínima utilización de determinados tramos de la red; se requieren mecanismos de coordinación entre los distintos tramos (no son independientes); y se debe garantizar “servicios mínimos” en áreas que, por su situación geográfica, puedan ser poco atractivas.

A lo anterior se añade que en una misma vía puedan convivir trenes “lentos” -que paran en todas las estaciones- con trenes rápidos que cubren grandes poblaciones. Además, el valor que tiene un determinado tramo para un operador depende del conjunto de tramos y franjas horarias sobre las que posee derechos (Gibson, 2003); por ejemplo, el valor de operar en el tramo Madrid-Zaragoza, depende de que se pueda operar también en el tramo Zaragoza-Barcelona. Y finalmente, un retraso en un tren en un determinado tramo afecta (en cascada) a retrasos en otros tramos de la red (network effect, Landex y Nielsen, 2012).

Por todo ello, aunque conceptualmente la asignación de slots sea un problema de asignación de capacidad, en la práctica, la dificultad y la complejidad es mucho mayor que la que se produce en otros problemas de asignación de capacidad, como en el caso de las frecuencias de radio y telefonía, los slots de aeropuertos, derechos de distribución de gas, etc.

Referencias:

Affuso, L. (2003). Auctions of rail capacity?. Utilities Policy 11, 43–46.

Arauzo, A., Pajares, J., López-Paredes (2010). Simulating the dynamic scheduling of project portfolios. Simulation Modelling Practice and Theory, 18 (10); pp. 1428-1441.

Bassanini, A., La Bella, A., Nastasi, A. (2002). Allocation of railroad capacity under competition: a game theoretic approach to track time pricing. En M. Gendreau and P. Marcotte (eds.). Transportation and Network Analysis: Current Trends, 1-17. Kluwer Academic Publishers

Borndörfer, R., Grötschel, M., Lukac, S., Mitusch, K., Schlechte, T., Schultz, S., Tanner, A., (2005). An auction approach to railway slot allocation. Competition Regul. Netw. Ind. 7 (2),
163–197.

Ferber, J. (1999). Multi-Agent Systems: An Introduction to Distributed Artificial Intelligence. Addison-Wesley Longman Publishing Co., Inc., Boston, MA

Gibsson, J. (2003). Allocation of capacity in the rail industry. Utilities Policy 11 (2003) 39–42.

Hernández, C., López-Paredes, A. (2000). Engineering market design and computational organization. Growing the market from the bottom-up. Proceedings of the Workshop on Complex Behaviour in Economics, CEFI, Aix-en-Provence, France

Hoffman. K.; D. Menon (2010). A practical combinatorial clock exchange for spectrum licenses. Decision Analysis, 7(1) 58–77.

Landex, A., Nielsen, O.A. (2012). Network effects in railways. In: Brabbia, C.A., Tomii, N., Mera, J.M., Ning, B., Tzieropoulos, P. (Eds.), Computers in Railways XIII: Computer System Design and Operation in the Railway and Other Transit Systems, pp. 391–401.

Le. L., Donohue, G., Chen, C.H. (2004). Le, Auction-Based Slot Allocation for Traffic Demand Management at Hartsfield Atlanta International Airport: A Case Study. Transportation Research Record: Journal of the Transportation Research Board, 1888, 50-58.

López-Paredes, A. (2001). Análisis e Ingeniería de las Instituciones Económicas. Una metodología Basada en Agentes. Servicio de Publicaciones de la Universidad del País Vasco. Bilbao. ISBN: 84-8373-347-1.

Nicolaisen, Petrov, J.,V.,Tesfatsion, L. (2001). Market power and efficiency in a computational electricity market with discriminatory double-auction pricing. IEEE Transactions on Evolutionary Computation, 5(5):504-523

Pajares, J., Lopez-Paredes, A., Hernandez, C. (2003). Industry as an organization of agents: Innovation and R&D management. Journal of Artificial Societies and Social Simulation,6,2,7.
Pekec, A., Rothkopf, M.H. (2003). Combinatorial auction design. Management. Science. 49 (11), 1485–1503.

Perennes, P. (2014). Use of combinatorial auctions in the railway industry: Can the ‘‘invisible hand’’ draw the railway timetable?. Transportation Research Part A, 67 (2014) 175–187.

Posada, M., Lopez-Paredes, A. (2008). ‘How to Choose the Bidding Strategy in Continuous Double Auctions: Imitation Versus Take-The-Best Heuristics’. Journal of Artificial Societies and Social Simulation 11(1)6

Ramírez, M., Villafáñez, F., Araúzo, A., López-Paredes, A. (2014). Agent-Based Pilot Model for Alternative Primary Airport Slot Allocation with Price-Setting Auctions. Proceedings of the 4th SESAR Innovation Days, Madrid, November 201

Sandholm, T. (2002). Algorithm for optimal winner determination in combinatorial auctions, Artificial Intelligence, Volume 135, Issues 1–2, pp:1-54

Stern, J., Turvey, R.(2003). Auctions of capacity in network industries. Utilities Policy 11,1–8.
Tonmukayakul, A., Weiss, M.H. (2009). A study of secondary spectrum use using agent-based computational economics. Netnomics, Vol. 9 Iss. 2, pp. 125-151.

Vries, S., & Vohra, R. V. (2003). Combinatorial auctions: A survey. INFORMS Journal on Computing, 15(3), 284-309.