Algorítmica y complejidad computacional. Nuevo método para el problema del peaje.

1. Motivación.

He leído hoy en la prensa un artículo relacionado con las Radiales de Madrid, que son autopistas de peaje que se construyeron durante los  años de bonanza. Seguramente desde el punto de vista de la gestión de tráfico y urbanístico las radiales tienen todo el sentido pero finalmente no han ido bien como negocio.  Según nos informan en esta noticia de noviembre de 2013 todas estaban con problemas  económicos. Y en la noticia de hoy nos informan que varios de los socios de dos de ellas (R3 y R5) han acabado en arbitraje. ¡¡ Que difícil es redactar un contrato que permita una solución de los conflictos, que no deje pie a interpretaciones dispares, sin necesidad de recurrir a arbitrajes o juicios cuando la cosa acaba mal !! Y cuidado con el  arbitraje,  pese a lo que se suele pensar, no es gratuito: hay que provisionar unas fianzas o garantías iniciales, en ocasiones prohibitivas para alguna de las partes, que además se perderían en caso de laudo contrario. En este caso es una lucha de titanes y no entran estas consideraciones.

Por otra parte el otro día, cuando hablábamos sobre el índice de complejidad de una economía ya decíamos  que dejaban fuera los servicios, cuya complejidad puede ser tan elevada como la de algunos productos. Me quedé con ganas de aportar al lector ejemplos concretos.

Pues bien por casualidad de que el otro día dí con un artículo relacionado con ambos temas. Concretamente en él se presenta un nuevo método para la determinación de las tarifas óptimas de los peajes.  

[Nota la margen: Uno, que tiene una mentalidad más bien pragmática, está acostumbrado a encontrarse con algoritmos en contextos de una abstracción tal que cuando me he encontrado con este relacionado con un problema muy real  he sentido gran satisfacción, aunque  no tenga mucho que ver con la informática.  Por eso redacté el post el  otro día. Luego decidí no publicarlo. Al ver hoy esta noticia ya no he dudado]   

2. Sin más preliminares, presentamos el artículo:

Título. Elastic Multi-User Stochastic Equilibrium Toll Design with Direct Search Meta-Heuristics.

Extractos. 

The problem of optimum toll design involves the determination of the optimal toll levels at the links of  a road network, while accounting for the responses in the (route choice and/or trip-making decision) behavior of travelers. A large number of alternative modeling formulations has been hitherto proposed in the literature for solving the toll design problem.

The present bilevel programming problem seeks to maximize the volume of users entering the highway from various access points, taking into account the impact of toll level on the SUE conditions and travel demand of different user groups at the whole network. As typically any other type of bilevel (or MPEC) formulation, it is intrinsically nonconvex and complex in its nature, due to the nonlinear formulations of the functions involved in the upper and lower-level problems. The nonlinearity and nonconvexity portend the existence of local solutions, which imply that it might be difficult to solve for a global optimum (or adequately near-optimum) solution. In view of the difficulty in applying the standard algorithmic approaches for search of the global optimum, this study adopts a Direct Search meta-heuristic method, which is described in the following section

Enlace.

Reconozco que he leído el problema y su formulación no es fácil de comprender. Para introducirse un poco remito al lector a las consiguientes entradas  de wikipedia: 1 y 2.

Curiosamente, en el segundo enlace, que habla de programas no lineales ponen el siguiente ejemplo como de problema no convexo: A typical nonconvex problem is that of optimising transportation costs by selection from a set of transportion methods, one or more of which exhibit economies of scale, with various connectivities and capacity constraints. An example would be petroleum product transport given a selection or combination of pipeline, rail tanker, road tanker, river barge, or coastal tankship. Owing to economic batch size the cost functions may have discontinuities in addition to smooth changes. Hace poco nos preguntábamos sobre las redes multimodales de transporte del petróleo y veo que decidir sobre el flujo en estas redes no es sencillo.

3. Complejidad del problema. 

Volviendo al paper, en él comparan el nuevo método propuesto, basado en búsqueda directa o DS (son métodos que no utilizan derivación) con otros métodos basados en otras heurísticas como Algoritmos Genéticos o GA, pero en base a implementación y experimentación y no recurriendo a la teoría de complejidad computacional. 

El motivo debe de ser que siendo la complejidad computacional de estos problemas ya conocida lo más importante debe de ser el comportamiento experimental de los métodos. Como no domino este tema no voy a entrar en detalles. Solo recordar que un BPP (Bilevel Programming Problem) lineal ya es por lo visto NP-duro. En el problema del peaje hablan de no linealidad y no convexidad, tipo de problemas que siguen siendo NP-hard, (ver páginas 3 y 4): Without going into details we briefly outline that solving a general nonlinear optimization problem is an NP-hard problem….there are more subtle issues about complexity of non-linear programs.

¿ Cuales son estos sútiles matices ?. Demasiados y demasiado sútiles como para resumirlos. Si el lector quiere profundizar le aconsejo que lea este otro paper sobre programación no lineal entera.  Se aconseja ver la tabla de la página 51. Según la variante del problema, puede llegar a ser hasta indecidible.

El lector del problema tiene que tener en cuenta que cuando hablamos  de complejidad, nos referimos  a la computacional, que es un concepto técnico bien delimitado. No obstante creo que esto, y el  fracaso de las  radiales  en Madrid, demuestra que elservicio de gestión de una empresa de peajes no es tema sencillo.

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: