ES2359124T3

ES2359124T3 - Procedimiento para la creación de horarios de circulación para sistemas de transporte teniendo en cuenta límites de tiempo.

Info

Publication number: ES2359124T3
Application number: ES08804653T
Authority: ES
Inventors: Karl-Heinz Erhard
Original assignee: Siemens AG; Siemens Corp
Current assignee: Siemens AG; Siemens Corp
Priority date: 2007-09-27
Filing date: 2008-09-24
Publication date: 2011-05-18
Anticipated expiration: 2028-09-24
Also published as: EP2200884A1; US20100305996A1; PT2200884E; DE502008002511D1; CA2700993A1; ATE496814T1; DK2200884T3; EP2200884B1; AU2008307181B2; AU2008307181A1; WO2009043770A1; DE102007047474A1

Abstract

Procedimiento para la creación de horarios de circulación para sistemas de transporte teniendo en cuenta límites de tiempo, caracterizado por las siguientes etapas del procedimiento: - los trayectos a planificar son clasificados según la prioridad y entonces son programados individualmente, - para la planificación de un trayecto individual se representan las líneas de ferrocarril que están todavía libres intervalos de tiempo entre salidas para secciones de rutas- por medio de un gráfico de intervalos y se aplica un algoritmo de la distancia más corta a dicho gráfico para calcular una ruta óptima, donde no sólo se tienen en cuenta totalmente las alternativas topológicas, sino también las alternativas de tiempo, en particular los adelantamientos y los encuentros, - como valor funcional objetivo que debe reducirse al mínimo se considera un retraso total ponderado de todos los vehículos, siendo el factor de ponderación tanto mayor cuando mayor sea la prioridad del vehículo, - la utilización de una línea de ferrocarril libre se permite en general y se penaliza con un valor adecuado, como resultado de lo cual cada vehículo ya planificado puede ser desplazado, en principio, por vehículos planificados posteriormente, - el valor de penalización se suma al valor funcional objetivo para la solución en consideración.

Description

La invención se refiere a una creación automática asistida por ordenador de horarios de circulación para sistemas de transporte. El procedimiento se puede emplear tanto fuera de línea para la creación de horarios de circulación – en el marco de herramientas de planificación – como también en línea para la disposición de los horarios de circulación –como componente de sistemas de mando-. La invención amplía el procedimiento descrito en la solicitud de patente DE Nº 19533127 para la creación de horarios de circulación. Con el procedimiento reivindicación se tienen en cuenta especialmente límites de tiempo superiores como condiciones marginales operativas.

Los procedimientos automáticos existentes para la creación de horarios de circulación se pueden clasificar en dos clases:

-Los procedimientos incrementales parte del horario de circulación actual fuera de línea o en línea y solamente llevan a cabo modificaciones locales en este horario de circulación. La decisión sobre qué adaptación del horario de circulación debe realizarse, se lleva a cabo, por ejemplo, con la ayuda de una bases de datos [H. Shaefer y col. An Expert System for Real-Time Train Dispatching, Railway Operations, Computers in Railways 4, Volumen 2, COMPRAIL 94, T. Murthy y col, (editores), Computational Mechanics Publications, Southampton, ISBN 1-85312-3595, páginas 27 a 34, 1994] o a través de procedimientos de optimización, por ejemplo Branch-and-Bound-Algorithmus según [R. Sauder, Computer Aided Train Dispatching: Decision Support through Optimization, INTERFACES 13,45.24 a 37, 1993).

- Los procedimientos constructivos calculan un horario de circulación totalmente nuevo partiendo de las condiciones marginales operativas, por ejemplo, paradas planificadas de los pasajeros, prioridades de los vehículos y, dado el caso, los lugares reales de emplazamiento de los vehículos. En [K.-H. Erhard, U. Lauther: Verfahren zur Regelung von Verkehrsmitteln, solicitud de patente DE 19533127] se emplean aquí heurísticas rápidas sobre la base de modelos y algoritmos gráficos.

Los procedimientos conocidos tienen cuenta ciertos límites inferiores de tiempo, por ejemplo el vehículo en una parada de pasajeros no puede salir antes del tiempo de partida planificado. Los límites superiores de tiempo no son tenidos en cuenta actualmente. Un ejemplo típico de la consideración de límites superiores de tiempo es el tiempo de servicio limitado del personal conductor, que no debe excederse, a ser posible. En otro caso, se generan costes de producción considerables y retrasos adicionales en virtud del cambio de personal requerido en los puestos de relevo del personal fuera de la planificación.

La invención tiene el cometido de ampliar el procedimiento para la creación de horarios de circulación con la posibilidad de considerar límites superiores de tiempo.

De acuerdo con la invención, a tal fin se utiliza un modelo de costes punibles no lineal, es decir, un modelo de penalización.

El procedimiento en el que se basa la invención es constructivo y genera paso a paso el nuevo horario de circulación, clasificando los recorridos a planificar en primer lugar según la prioridad y planificándolos entonces individualmente. Para la planificación de un recorrido individual se representan las líneas de ferrocarril que están todavía libres –intervalos de tiempo entre salidas para secciones de rutas-por medio de un gráfico de intervalos y se aplica un algoritmo de la distancia más corta a dicho gráfico para calcular una ruta óptima. En este caso, no sólo se tienen en cuenta totalmente las alternativas topológicas, sino también las alternativas de tiempo, en particular los adelantamientos y los encuentros. Como valor funcional objetivo que debe reducirse al mínimo se considera un retraso total ponderado de todos los vehículos. El factor de ponderación tanto mayor cuando mayor sea la prioridad del vehículo.

En el procedimiento de base conocido es un inconveniente la propiedad de que los trayectos ya planificados no se pueden modificar ya. Una línea de ferrocarril todavía libre solamente se puede utilizar, por lo tanto, para un recorrido posterior cuando su intervalo de tiempo es suficientemente grande para la absorción del tiempo de circulación y del tiempo de espera dado el caso planificado. Esto puede conducir a que los límites superiores de tiempo para trenes planificados posteriormente son violados.

Para eliminar este inconveniente, se permite, en general, en el procedimiento de acuerdo con la invención, según una primera ampliación del modelo, la utilización de una línea de ferrocarril y penalizarla con un valor adecuado. El valor de penalización se añade la valor funcional objetivo de la solución considerada. De esta manera, cada vehículo ya planificado puede ser desplazado, en principio, por vehículos planificados posteriormente. Durante el cálculo de las penalizaciones se distinguen los siguientes casos:

1.: El recorrido planificado a través de la línea de ferrocarril es posible sin penalización: en este caso, el valor de penalización es 0.

2.: Para la realización del recorrido sobre la línea de ferrocarril seleccionada deben desplazarse otros vehículos, es decir, deben retrasarse: aquí se calcula el retraso adicional de los otros vehículos y se añade al valor funcional objetivo. Para tener en cuenta las diferentes prioridades del vehículo, se multiplica el suplemento de retraso por el factor de ponderación respectivo para los trayectos desplazados.

Una segunda ampliación del modelo consiste ahora en que para las líneas de ferrocarril está previsto un valor de penalización adicional, en particular grande –valor bigM- para las líneas de ferrocarril más allá de los límites superiores de tiempo. Este valor es mayor que el valor máximo de las soluciones posibles sin tener en consideración el valor bigM. Sin la utilización de este valor podría suceder que se genere una solución con violación del límite, aunque existiera una solución admisible.

Partiendo de estas ampliaciones del modelo, se proponen las siguientes etapas prácticas del procedimiento para la planificación de un recorrido nuevo:

a) Cálculo de la ruta más corta sobre el gráfico de intervalos teniendo en cuenta los valores de penalización individuales de las líneas de ferrocarril individuales todavía libres,

b) Verificación del valor funcional objetivo de la solución obtenida.

b1) Cuando el valor es menor que bigM, entonces se puede violar el límite superior de tiempo. En este caso, la solución obtenida es fiable. Cuando en la solución seleccionada deben demorarse algunos vehículos, se actualizan de manera correspondiente sus recorridos. Cuando después de esta actualización se ha violado un límite superior del tiempo para un vehículo demorado, entonces se procede como en la etapa b2.

b2) Cuando el valor es mayor o igual que bigM, la solución no es admisible en virtud de la violación de límites de tiempo. En este caso, se determina una solución alternativa adecuada. En el caso concreto de un exceso del tiempo de servicio del personal de transporte, se coloca en lugar de relevo en la dirección del lugar de emplazamiento actual del vehículo.

El modelo de costes punibles propuesto se puede utilizar de manera similar teniendo en cuenta límites inferiores de tiempo. Cuando, por ejemplo, un vehículo no debe llegar a un lugar determinado antes de un tiempo determinado, entonces se impulsan las líneas de ferrocarril, que se encuentran temporalmente antes de este instante, con el valor bigM.

La invención se explica en detalle en un ejemplo de realización con la ayuda del diagrama de recorrido – tiempo representado en el dibujo.

En el diagrama de recorrido – tiempo representado, se representa sobre el eje-x el tiempo entre las 8 y las 12 horas, sobre el eje-y el recorrido con indicación de las estaciones.

Un recorrido está constituido por una secuencia de intervalos de tiempo. Cada intervalo de tiempo describe la ocupación de una sección determinada del trayecto –por ejemplo, carretera- por un vehículo determinado. Los campos en blanco entre estos intervalos son las líneas todavía libres, que se pueden utilizar para la planificación del recorrido siguiente.

Ahora se supone que en la parte inferior izquierda –en la estación de Belen- se inicia un recorrido que de nueva planificación a las 7:50 horas y debe tener lugar un relevo del personal lo más tarde a las 10 horas en la parte superior central –en la estación de Clovis-. Para la consideración de este límite superior de tiempo se establece el siguiente modelo de costes punibles:

-: Las líneas de ferrocarril libres, que se encuentran en la parte izquierda, a saber, antes de las 10 horas, son impulsadas con una penalización positiva inferior a bigM, cuando su intervalo de tiempo es tan pequeño que la utilización de la línea de ferrocarril para el trayecto a planificar implicaría un desplazamiento, es decir, un retraso, de trayectos ya planificados. Cuando no es necesario ningún desplazamiento, no se realiza ninguna penalización.

-: Las líneas de ferrocarril libres en la parte derecha, a saber, después de las 10 horas, son impulsadas con una penalización especialmente grande bigM.

Este modelo conduce a que el algoritmo de trayectos más cortos determina, según las posibilidades, una ruta a través de las vías de ferrocarril libre, en la que el vehículo llega lo más tarde a las 10 horas a Clovis. Cuando el vehículo se ha retrasado ya hasta el punto de que incluso el desplazamiento de todos los recorridos existentes provoca un exceso del tiempo de servicio máximo admisible, entonces la solución obtenida utilizaría una línea de ferrocarril a la derecha de las 10 horas y, por lo tanto, resultaría un valor funcional objetivo mayor que bigM. En este caso, el procedimiento propondría el desplazamiento del lugar de relevo en la dirección de la estación de partida.

A través de la introducción del modelo de costes punibles de acuerdo con la invención para la consideración de límites de tiempo para la creación de horarios de circulación resultan las siguientes ventajas.

- La calidad de la solución obtenida en el sentido del valor funcional objetivo se mejora adicionalmente frente al procedimiento conocido, puesto que a través del desplazamiento potencial de recorridos ya planificados de incrementa claramente el espacio de solución considerado.

- El cálculo de una solución admisible se realiza de manera muy eficiente dentro de un solo proceso de cálculo, es 5 decir, que no es necesario un seguimiento.

-: La utilización de límites superiores de tiempo sirve, por ejemplo, para prevenir que se excedan tiempos de servicio. De ello resultan ahorros de costes considerables para el cliente.

-: Los límites inferiores de tiempo se pueden utilizar, por ejemplo, para evitar sobrellenar lugares de emplazamiento con capacidad limitada de vehículos, por ejemplo depósitos.

10 - La combinación de límites de tiempo inferiores y superiores se puede utilizar para la planificación Just-In-Time, por ejemplo para un almacenamiento óptimo de los productos transportados.

Puesto que se amplía un procedimiento constructivo existente para la creación de horarios de circulación, se asumen sus ventajas:

- El principio constructivo permite una optimización lo más global posible de los horarios de circulación.

15 - El procedimiento se puede emplear para redes generales de tráfico, no sólo para líneas de tráfico.

-El cálculo de horarios de tráfico admisibles y optimizados se realiza de manera especialmente eficiente a través de la utilización de heurísticas rápidas, lo que posibilita el empleo del procedimiento no sólo para aplicaciones fuera de línea sino también para aplicaciones en línea.

Claims

REIVINDICACIONES

1. Procedimiento para la creación de horarios de circulación para sistemas de transporte teniendo en cuenta límites de tiempo, caracterizado por las siguientes etapas del procedimiento:

-

los trayectos a planificar son clasificados según la prioridad y entonces son programados individualmente,

-

para la planificación de un trayecto individual se representan las líneas de ferrocarril que están todavía libres –

5 intervalos de tiempo entre salidas para secciones de rutas- por medio de un gráfico de intervalos y se aplica un algoritmo de la distancia más corta a dicho gráfico para calcular una ruta óptima, donde no sólo se tienen en cuenta totalmente las alternativas topológicas, sino también las alternativas de tiempo, en particular los adelantamientos y los encuentros,

- como valor funcional objetivo que debe reducirse al mínimo se considera un retraso total ponderado de todos los 10 vehículos, siendo el factor de ponderación tanto mayor cuando mayor sea la prioridad del vehículo,

-

la utilización de una línea de ferrocarril libre se permite en general y se penaliza con un valor adecuado, como resultado de lo cual cada vehículo ya planificado puede ser desplazado, en principio, por vehículos planificados posteriormente,

-

el valor de penalización se suma al valor funcional objetivo para la solución en consideración.

15 2. Procedimiento de acuerdo con la reivindicación 1, caracterizado porque en el caso de que el trayecto planificado por la línea de ferrocarril sea posible sin desplazamiento, el valor de penalización es igual a 0.
3. Procedimiento de acuerdo con la reivindicación 1, caracterizado porque en el caso de que para la realización del recorrido sobre la vía ferroviaria seleccionada deban desplazarse, es decir, retrasarse otros vehículos, se calcula el retardo adicional de los otros vehículos y se suma al valor funcional objetivo, de manera que, en función de la

20 prioridad del vehículo, se multiplica el suplemento de retraso por el factor de ponderación respectivo para los trayectos desplazados.
4. Procedimiento de acuerdo con la reivindicación 1, caracterizado porque sobre la base de una ampliación del modelo para las líneas de ferrocarril, está previsto un valor de penalización adicional, en particular grande –valor bigM- para las líneas de ferrocarril más allá de los límites superiores de tiempo, de manera que este valor es mayor

25 que el valor máximo de las soluciones posibles sin tener en consideración el valor bigM.