Source: http://docplayer.es/1261099-Gestion-y-gerencia-vol-8-no-2-mayo-agosto-2014.html
Timestamp: 2017-09-23 04:04:32+00:00

Document:
Gestión y Gerencia Vol. 8 No. 2 Mayo - Agosto PDF
Gestión y Gerencia Vol. 8 No. 2 Mayo - Agosto 2014
Download "Gestión y Gerencia Vol. 8 No. 2 Mayo - Agosto 2014"
Purificación Montero Farías
1 Gesión y Gerencia Vol. 8 No. 2 Mayo - Agoso 2014 MODELADO Y RESOLUCIÓN DEL PROBLEMA DE ASIGNACIÓN DE HORARIOS PARA EL TRANSPORTE FERROVIARIO UTILIZANDO TÉCNICAS DE SATISFACCIÓN DE RESTRICCIONES Marlene Arangú* - Miguel A. Salido** *Docor en Informáica. Profesor Asociado del Decanao de Adminisración y Conaduría de la Universidad Cenroccidenal Lisandro Alvarado, Venezuela. Docene PEII. Trabajo produco del proyeco subvencionado 001-AC **Docor en Informáica. Profesor Tiular del Deparameno de Sisemas Informáicos y Compuación de la Universidad Poliécnica de Valencia, España. I N V E S T I G A C I Ó N RESUMEN El ranspore ferroviario iene un rol imporane y creciene en muchos países, lo cual crea la necesidad de opimizar el uso de la infraesrucura ferroviaria y los méodos y herramienas para su adminisración. La consrucción de horarios ferroviarios es una area difícil que consume mucho iempo, paricularmene en el caso de redes ferroviarias reales. El objeivo del rabajo que se presena, es realizar un modelado del problema de asignación de horarios para el raspore ferroviario que permia aplicar las diferenes écnicas de resolución de programación de resricciones exisenes en la lieraura y evaluar su efecividad. El rabajo es de ipo descripivo-documenal bajo la modalidad de invesigación básica. La meodología uilizada es del área de Ineligencia Arificial. Consise en desarrollar una herramiena auómaa que permia modelar insancias reales del problema como un Problema de Saisfacción de Resricciones (CSP); aplicar écnicas de solución y poseriormene evaluar los resulados. Se propone un modelado binario de CSP no-normalizado que conempla reglas de ráfico, requerimienos del usuario y reglas opológicas de una infraesrucura real. Los resulados de las pruebas indican que en la búsqueda el algorimo BLS uvo un desempeño superior al 80% que los algorimos MAC3, FC y BT, en diferenes insancias evaluadas. Palabras clave: Problemas de saisfacción de resricciones, scheduling, ranspore ferroviario. JEL: C6 Recibido: 02/10/ Acepado: 07/03/
2 Gesión y Gerencia Vol. 8 No. 2 Mayo - Agoso 2014 MODELING AND PROBLEM SOLVING ASSIGNMENT SCHEDULES FOR RAILWAY TRANSPORT USING CONSTRAINT SATISFACTION TECHNIQUES Marlene Arangú* - Miguel A. Salido** *PhD in Informaics. Professor a he Faculy of Managemen and Accounancy of he Universidad Cenroccidenal Lisandro Alvarado. Barquisimeo, Venezuela. **PhD in Informaics. Professor a Deparmen of Informaion Sysems and Compuaion of he Universidad Poliécnica de Valencia, España. ABSTRACT Rail ransporaion has an imporan and growing role in many counries, which creaes he need o opimize he use of railway infrasrucure and he mehods and ools for is adminisraion. Railway imeables consrucion is a difficul and ime consuming ask, paricularly in he case of real railway neworks. The aim of his work is o model he railway scheduling problem; ha allows applying he differen echniques in consrain programming resoluion in he lieraure and evaluaing is effeciveness. The work is descripive and documenary in he form of basic research. The mehodology is from Arificial inelligence area, i consiss in developing an auomaed ool which allow modeling PLC real insances of he problem as a Consrain Saisfacion Problem (CSP) applied soluion echniques and hen evaluae he resuls. We propose a binary CSP modeling non normalized (he same variables can share more han one consrain) ha provides raffic rules, user requiremens and opology rules from a real infrasrucure. The es resuls indicae ha in finding he BLS algorihm ouperformed he 80% ha he algorihms MAC3, FC and BT, in differen insances evaluaed. Key words: Consrain saisfacion problem, railway, scheduling. R E S E A R C H JEL: C6 46
3 Modelado y Resolución del Problema de Asignación de Horarios para el Transpore Ferroviario uilizando Técnicas de Saisfacción de Resricciones MODELAGEM E RESOLUÇÃO DE PROBLEMA DE ATRIBUIÇÃO DE HORÁRIOS PARA TRANSPORTE FERROVIÁRIO USANDO TÉCNICAS DE SATISFAÇÃO DE RESTRIÇÕES Marlene Arangú* - Miguel A. Salido** *Douor em Compuação. Professor da Faculdade de Adminisração e Conabilidade da Universidad Cenroccidenal Lisandro Alvarado. Barquisimeo, Venezuela. **Douor em Compuação. Professor do Deparameno de Sisemas de Informação e Compuação da Universidad Poliécnica de Valencia, Espanha. P E S Q U I S A RESUMO O ranspore ferroviário em um papel imporane e crescene em muios países, o que cria a necessidade de oimizar o uso da infra-esruura ferroviária e os méodos e ferramenas para a adminisração. A consrução de horários ferroviários é uma arefa difícil e demorada, especialmene no caso das redes ferroviárias reais. O objeivo do rabalho apresenado é a realização de um problema de aribuição de modelagem para os horários de ranspore ferroviário que permiam a aplicação de diferenes écnicas para resolver as resrições de agendameno que exisem na lieraura e avaliar a sua eficácia. O rabalho é descriivo e documenal, na forma de pesquisa básica. A meodologia uilizada é da área da Ineligência Arificial. PLC consise em desenvolver uma ferramena para modelar casos reais do problema como um problema Saisfação de Resrições (CSP), aplicar écnicas de resolução e poseriormene avaliar os resulados. Propõe-se uma modelagem binária de CSP não normalizada que inclui as regras de rânsio, requerimeno do usuário e as regras de opológicas de uma infra-esruura real. Os resulados do ese indicam que o algorimo de busca BLS eve um desempenho 80 % superior aos algorimos MAC3, FC e BT, em diferenes siuações avaliadas. Palavras chave: Agendameno, problema saisfação de resrições, ranspore ferroviário. JEL: C6 47
4 Gesión y Gerencia Vol. 8 No. 2 Mayo - Agoso 2014 Inroducción En los úlimos años, el ranspore ferroviario ha enido un rol imporane en muchos países. El ráfico y la infraesrucura ferroviaria se han incremenado considerablemene (Eurosa, 2011; INE, 2011 y IFE, 2013), lo cual crea la necesidad de opimizar el uso de la infraesrucura ferroviaria y los méodos y herramienas para su adminisración. En ese senido, uno de los objeivos en Europa para el 2020, es lograr un incremeno del 20% en el ranspore de pasajeros y del 70% en mercancías y, para Venezuela en el 2026 se prevé su alcance alrededor de los km en rieles, uniendo los cuaro punos cardinales del país, por medio de diez sisemas ferroviarios organizados en 21 ramos (Venezuela en Daos, 2007). Un horario de renes flexible debe especificar los iempos de salida y llegada a cada esación del rayeco, eniendo en cuena la capacidad de la línea y oras resricciones operacionales. La consrucción de horarios ferroviarios es una area difícil que consume mucho iempo, paricularmene en el caso de redes ferroviarias reales, donde el número de resricciones y la complejidad de las mismas crece drásicamene. Moivado por lo aneriormene planeado, se han desarrollado numerosas aproximaciones y herramienas para planificar los horarios ferroviarios. A ese ipo de problemas se les conoce como el problema de asignación de horarios ferroviarios (Barber e al., 2007). El escenario del problema de asignación de horarios ferroviarios consise en un conjuno ordenado de dependencias (esaciones, apeaderos, cargaderos, bifurcaciones, ec.), un conjuno de renes en cada senido (ida, vuela) y un recorrido (es el orden en el que el ren visia cada dependencia) para cada ren. El problema raa de asignar los insanes de enrada/salida de los k renes en las i dependencias minimizando el iempo promedio de recorrido y saisfaciendo las resricciones del usuario (hora de salida inicial, frecuencia de salida, paradas comerciales, ec.), las resricciones de ráfico (cruce, iempo de recepción, iempo de expedición, precedencia, ec.) y las resricciones opológicas (número de vías enre las dependencias, capacidad de cada esación, iempos de cierre de las esaciones, ec.). El problema de asignación de horarios ferroviarios se caraceriza por poseer un gran número de variables y resricciones, lo cual lo hace favorable para ser 48
5 Modelado y Resolución del Problema de Asignación de Horarios para el Transpore Ferroviario uilizando Técnicas de Saisfacción de Resricciones resuelo uilizando Técnicas de Saisfacción de Resricciones, o CSP (por sus siglas en inglés Consrain Saisfacion Problem), ya que esas écnicas rabajan con problemas combinaorios donde exisen un número finio de variables, dominios y resricciones. Un CSP consise en un conjuno finio de variables, cada una de las cuales posee un dominio de valores y exisen un conjuno de resricciones que acoan la combinación de valores que las variables pueden omar. El rabajo esá organizado de la siguiene forma, un Marco Teórico, donde se explican en dealle los Problemas de Saisfacción de Resricciones, el Problema de Asignación de Horarios Ferroviarios y la noación uilizada para dicho problema. Poseriormene se explica la meodología uilizada y los resulados obenidos en las pruebas. Finalmene son presenadas las conclusiones. Marco Referencial Problemas de Saisfacción de Resricciones Los Problemas de Saisfacción de Resricciones (CSPs) son unas esrucuras úiles para la resolución de diversos ipos de problemas y son ampliamene uilizados en el área de Ineligencia Arificial (IA) (Barák, 1999; Palma y Marín, 2008; Barák, Salido y Rossi, 2010). Formalmene, un CSP esá formado por la erna P = (X, D, R) donde X es el conjuno finio de variables {X 1,X 2,, X n}; D es el conjuno de dominios {D 1,D 2,, D n} al que, para cada variable Xi X, exise un conjuno finio de valores Di D que la variable Xi puede omar; y R es el conjuno finio de resricciones {R 1,R 2,, Rm}, el cual resringe los valores que las variables pueden simuláneamene omar. Una solución para un CSP es una asignación de un valor del dominio de cada variable de forma que saisfaga odas las resricciones del problema. Un CSP es binario si y sólo si odas sus resricciones en R involucran dos variables X y X, con i j. Modelar un problema como un CSP confiere venajas imporanes (Russell y Norvig, 2010), como lo son las siguienes: (a) la represenación de los esados se ajusa a un modelo esándar (compueso por variables, dominios y resricciones, donde se pueden asignar valores a las variables); (b) pueden desarrollarse heurísicas genéricas eficaces que no requieran ninguna información dependiene del problema y (c) la esrucura del grafo de resricciones puede ser uilizada para simplificar el proceso de solución en i j 49
6 Gesión y Gerencia Vol. 8 No. 2 Mayo - Agoso 2014 problemas binarios (en un grafo de resricciones los nodos corresponden a las variables y las arisas corresponden a las resricciones). Así por ejemplo, un CSP con 10 variables, y cada variable con 10 posibles valores en su dominio, endría un oal de diez mil millones de posibilidades diferenes. Dado que por lo general los CSP son problemas NP-compleos, diversas écnicas han sido diseñadas para conseguir solución a ese ipo de problemas, las cuales son agrupadas como se muesra a coninuación: écnicas de búsqueda, écnicas de inferencia y écnicas híbridas. Las écnicas de búsqueda consisen en explorar el espacio de esados hasa enconrar una solución, y pueden ser sisemáicas (ejemplos: genera y prueba, backracking cronológico) o locales (ejemplos: abú search, algorimos genéicos). Las écnicas de inferencia consisen en deducir un CSP* equivalene que sea más fácil de resolver. Esas écnicas pueden ser compleas -si se logra exraer la solución del CSP* en forma direca- o incompleas -si se requiere complemenarla con un proceso de búsqueda poserior, para enconrar la solución-. Ejemplo de inferencia incomplea son las écnicas de consisencia (ejemplos: AC3, AC4, AC6, 2-C3; 2-C3OPL, ec.). Las écnicas híbridas consisen en combinar las dos écnicas aneriores. La Figura 1 proporciona un esquema global de las écnicas anes mencionadas. Figura 1. Técnicas de Solución para los CSPs Fuene: Elaboración propia. 50
7 Modelado y Resolución del Problema de Asignación de Horarios para el Transpore Ferroviario uilizando Técnicas de Saisfacción de Resricciones Adicionalmene, para mejorar el desempeño de los algorimos de solución en los CSP, se han agregado heurísicas como por ejemplo: heurísicas de ordenación de variables, de ordenación de valores y de ordenación de resricciones, lo cual ha generado algorimos más eficienes para resolver los problemas. Los algorimos de búsqueda compleos o sisemáicos buscan a ravés del árbol de búsqueda las posibles asignaciones de valores a las variables, garanizando enconrar una solución, si es que exise, o demosrando que el problema no iene solución, en caso conrario. A coninuación se presenan brevemene los algorimos de búsqueda uilizados en ese manuscrio: Backracking, BT (Biner y Reingold, 1975) es la base fundamenal de los algorimos de búsqueda sisemáica para la resolución de CSPs. Se asume que: (a) el CSP es binario; y (b) la exisencia de un orden esáico enre las variables y enre los valores de los dominios de dichas variables. BT realiza el rabajo de búsqueda uilizando dos procesos: hacia adelane y hacia arás. En el proceso hacia adelane, el algorimo selecciona la siguiene variable de acuerdo al orden de las mismas y le asigna su próximo valor. Esa asignación de la variable se verifica en odas las resricciones formadas por la variable acual y alguna de las variables aneriores. Si odas las resricciones formadas por variables ya asignadas se han saisfecho, el algorimo selecciona la siguiene variable y raa de enconrar un valor para ella de la misma manera. Si alguna resricción en la que paricipa esa variable no se saisface, enonces se aciva el proceso hacia arás: la asignación acual se deshace y se prueba con el próximo valor de la variable acual. Si no se encuenra ningún valor consisene, enonces enemos una siuación sin salida ( dead-end) y el algorimo rerocede a la variable aneriormene asignada y prueba la asignación de un nuevo valor. Si se asume que se esá buscando una sola solución, BT finaliza cuando a odas las variables se les ha asignado un valor, en cuyo caso devuelve una solución, o cuando odas las combinaciones de variable-valor se han probado sin éxio, en cuyo caso no exise solución (Biner y Reingold, 1975). Forward Checking, FC (Haralick y Ellio, 1980) es uno de los algorimos lookahead más comunes. En cada eapa de la búsqueda, FC chequea hacia adelane la asignación acual, con odos los valores de las fuuras variables, 51
8 Gesión y Gerencia Vol. 8 No. 2 Mayo - Agoso 2014 que esán resringidas con la variable acual. Los valores de las fuuras variables, que son inconsisenes con la asignación acual, son emporalmene eliminados de sus dominios. Si el dominio de una variable fuura se queda vacío, la insanciación de la variable acual se deshace y se prueba con un nuevo valor. Si ningún valor es consisene, enonces se lleva a cabo el backrack. FC garaniza que en cada eapa la solución parcial acual sea consisene con cada valor de cada variable fuura. Así, cuando se asigna un valor a una variable, chequea la consisencia con las variables fuuras con las que esá involucrada. Así, mediane el chequeo hacia adelane, FC puede idenificar anes las siuaciones sin salida y podar el espacio de búsqueda. FC puede ser viso como la aplicación de un simple paso de arco-consisencia sobre cada resricción, que implica a la variable acual con una variable próxima, después de cada asignación de variables (Haralick y Ellio, 1980). Manenimieno de la Arco-Consisencia, MAC. Los algorimos de búsqueda MAC combinan un algorimo de búsqueda con una écnica de inferencia incomplea: arco-consisencia (Bessiere y Regin, 1996). Esos algorimos son acualmene los más uilizados en los resoluores de CSP (Ver CPAI08, 2010). Cuando se inena la asignación de una variable, MAC aplica arco-consisencia al sub-problema formado por odas las fuuras variables. Eso significa que además del rabajo que FC realiza, MAC chequea la consisencia ambién las variables pasadas. Si el dominio de alguna variable fuura se queda vacío, la insanciación realizada a la variable acual se deshace, el valor probado se elimina del dominio de la variable acual y se prueba la arco-consisencia de nuevo. Después se prueba con un nuevo valor de la variable acual. Si ya no quedan valores en el dominio de la variable acual, enonces, al igual que en FC, se lleva a cabo el backracking. El rabajo exra que MAC realiza al aplicar arco-consisencia puede eliminar más valores de las fuuras variables y como consecuencia logra podar más el árbol de búsqueda que FC. Dependiendo el algorimo de consisencia que se uilice denro del algorimo MAC se generan diferenes versiones. Así, MAC3 maniene la arco-consisencia uilizando Ac3. Look Back-Las Search BLS, (Arangú y Agüero, 2012) es una écnica de búsqueda heurísica independiene del dominio, que combina las esrucuras del almacenamieno de sopores (mariz Las) del algorimo de consisencia 2- C3OPL (Arangú, Salido y Barber, 2010), con la écnica de búsqueda con enfoque look-back. BLS uiliza las resricciones para decidir el orden de 52
9 Modelado y Resolución del Problema de Asignación de Horarios para el Transpore Ferroviario uilizando Técnicas de Saisfacción de Resricciones asignación de las variables y crear dependencias enre ellas. BLS uiliza las esrucuras generadas por 2-C3OPL para guiar el proceso de búsqueda, ahorrando iempo de cómpuo y rerocesos ( backracks). Problema de Asignación de Horarios para el Transpore Ferroviario El objeivo principal del problema de asignación de horarios ferroviarios es minimizar el iempo de recorrido de un conjuno de renes. Una red ferroviaria básicamene esá compuesa por dependencias y vías únicas o dobles. Los ipos de dependencias que se consideraron son las siguienes: - Esación: es un lugar donde los renes pueden esacionarse, deenerse o circular. En las esaciones hay dos o más vías donde pueden realizarse cruces y adelanamienos. - Apeadero: es un lugar donde los renes pueden deenerse o circular pero no pueden esacionarse, ni gesionar cruces o adelanamienos. - Bifurcación: es un lugar donde una única vía se divide en dos, o viceversa. No esá permiida la parada en la bifurcación. En una red ferroviaria, el operador necesia programar los rayecos de n renes que van en un senido (ida) y de m renes que van en dirección opuesa (vuela). Los renes pueden ser de diferenes ipos (cercanías, mercancías, regionales, larga disancia, ec.) y cada uno de ellos puede requerir una frecuencia de salida paricular. El ipo de ren deermina el iempo necesario para recorrer dos dependencias del rayeco. El rayeco seleccionado por el operador para el recorrido del ren, deermina por cuáles esaciones se ha de pasar y los iempos de parada requeridos en cada esación para propósios comerciales. Para poder realizar cruces en una sección de vía única, uno de los renes debe esperar en una esación previa. A esa espera se le denomina parada écnica, donde uno de los renes es desviado de la vía principal de forma que el oro ren pueda deenerse o coninuar. Los planificadores uilizan los mapas de recorridos (ver Figura 2) como herramienas gráficas que les ayudan en el proceso de planificación. Un mapa de recorridos coniene información concerniene a la opología ferroviaria 53
10 Gesión y Gerencia Vol. 8 No. 2 Mayo - Agoso 2014 (dependencias, vías, disancia enre dependencias, caracerísicas de conrol de ráfico, ec.) y los horarios de los renes que uilizan la opología ferroviaria (iempos de llegada y salida de los renes en cada dependencia, frecuencias, paradas, cruces, adelanamienos, ec.). Figura 2. Mapa de Recorridos Fuene: Arangú, Salido y Barber(2010). La Figura 2 muesra un mapa de recorridos donde los nombres de las dependencias son presenados a la izquierda, las líneas vericales represenan el número de vías enre dependencias (vía única o vía doble), las líneas puneadas horizonales represenan apeaderos o bifurcaciones y las líneas sólidas horizonales represenan las esaciones. El objeivo es obener un mapa de recorridos válido (que ambién puede ser opimizado) que enga en cuena lo siguiene: (i) las reglas de ráfico, (ii) los requerimienos del usuario y 54
11 Modelado y Resolución del Problema de Asignación de Horarios para el Transpore Ferroviario uilizando Técnicas de Saisfacción de Resricciones (iii) la opología de la infraesrucura ferroviaria. Así el problema de asignación de horarios ferroviarios ha sido modelado como un caso especial del problema de asignación de areas (job-shop scheduling problem) (Ingoloi, 2007; Walker, Snowdon y Ryan, 2005; Silva, 2001), donde los recorridos del ren se consideran los rabajos programados y las vías se consideran los recursos. También ha sido modelado uilizando écnicas disribuidas de Sisemas Muli-Agenes (MAS) (Abril, 2007) y uilizando procedimienos analíicos (Bürker y Seybold, 2012). Así mismo, la asignación de horarios para los nuevos renes se puede hacer de dos formas: sobre una red 'vacía' (donde no hay renes previamene planificados) (Walker e al, 2005 y Silva, 2001), o eniendo en cuena que la línea de ferrocarril puede esar ocupada por oros renes en circulación, cuyos horarios no se pueden modificar (Ingoloi, 2007). Noación La noación uilizada para describir el problema de asignación de horarios ferroviarios, esá basada en la propuesa por Ingoloi (2007) y Tormos, Lova, Barber, Ingoloi, Abril y Salido (2008), se dealla a coninuación: - T: conjuno finio de renes considerados en el problema. TD: conjuno de renes viajando en senido ida. TU: conjuno de renes viajando en senido vuela. De esa forma, T U T = T y T T = ɸ. D U D U - L = {l 0, l 1,...,l m} : línea ferroviaria compuesa por un conjuno ordenado de dependencias (esaciones, apeaderos y bifurcaciones) que pueden ser visiadas por los renes. Las dependencias coniguas li y li+1 esán enlazadas por una sección de vía única o doble. - J: recorrido del ren. El recorrido se describe como una secuencia ordenada de dependencias a ser visias por el ren de forma al T, J : J L. El recorrido J muesra el orden uilizado por el ren para visiar un conjuno de dependencias. De esa forma y represenan, respecivamene, la primera y úlima dependencia visiada por el ren. - : iempo mínimo requerido por el ren para operaciones comerciales (como son embarque y desembarque de pasajeros) en la esación i (parada comercial). - : iempo recorrido por el ren desde la dependencia a la 55
12 Gesión y Gerencia Vol. 8 No. 2 Mayo - Agoso F: frecuencia de los renes considerados en el problema. FD: frecuencia de los renes que salen (viajan en senido ida). FU : frecuencia de los renes que regresan (viajan en senido vuela). - λ: iempo de reraso permiido para el ren con una frecuencia F. Meodología La nauraleza del rabajo es de carácer descripivo documenal por ser un esudio de problemas de ipo eórico-prácico con el propósio de ampliar y profundizar el conocimieno de su nauraleza (Beníez, Sanabria, Areaga y Nieo, 1991). Hernández, Fernández y Bapisa (2006) señalan lo siguiene: En un esudio descripivo se selecciona una serie de cuesiones y se mide o recoleca información sobre cada una de ellas, para así describir lo que se invesiga... preenden medir o recoger información de manera independiene o conjuna sobre los concepos o las variables a los que se refieren (p. 71). Es un rabajo enfocado bajo la modalidad de invesigación básica, ya que involucra problemas eóricos cuya finalidad radica en formular nuevas eorías o modificar las exisenes, en incremenar los conocimienos cieníficos o filosóficos (Zorrilla, 2004). Se uilizaron écnicas perenecienes al área de Ineligencia Arificial, específicamene los CSPs para abordar y solucionar el Problema de Asignación de Horarios para el Transpore Ferroviario. La resolución de un CSP consa de dos fases diferenes (Barák e al, 2010). Esas se describen a coninuación: - Fase de modelado: consise en expresar el problema en érminos de la sinaxis de los CSP: variables, dominios y resricciones. - Fase de solución: consise en aplicar écnicas de saisfacción de resricciones para resolver el CSP, las cuales pueden clasificarse en: écnicas compleas, écnicas incompleas (o de inferencia) y écnicas híbridas. Para la resolución del problema (ver Figura 3) se consruyó una herramiena auómaa que permie converir en un CSP la formulación del modelo de maemáico del problema, la daa y resricciones proporcionadas por la Adminisración de Infraesrucura Española Ferroviaria Española, ADIF. Esa herramiena auómaa iene incorporada écnicas de resolución compleas e incompleas, lo cual permie generar una solución al problema. Así mismo, 56
13 Modelado y Resolución del Problema de Asignación de Horarios para el Transpore Ferroviario uilizando Técnicas de Saisfacción de Resricciones iene la capacidad de generar el modelado para ser resuelo por oro resoluor. Figura 3: Esquema de la Meodología de Resolución del Problema de Asignación de Horarios Ferroviarios. Fuene: Elaboración propia. El modelaje propueso se comparó empíricamene los algorimos genéricos: BT, FC MAC3 y BLS en la búsqueda de una solución al problema de asignación de horarios ferroviarios. La búsqueda con MAC3 se realizó uilizando el resoluor CON'FLEX (2010). Todos los algorimos realizaron consisencia en eapa de pre-proceso (previo a realizar la búsqueda). Así, MAC3 y FC se ejecuaron con AC3 (Mackworh, 1977) mienras que BLS y BT se ejecuaron uilizando 2-C3OPL (Arangú e al, 2010). La medida de eficiencia para odos los algorimos fue el iempo de cómpuo. Se uilizó la gráfica como medio de presenación de los resulados. Todos los algorimos evaluados fueron escrios en C. Los experimenos fueron realizados en un ordenador con procesador Inel Core 2 Quad (de 2.83 GHz velocidad del procesador y 3 GB RAM). El número de variables y de resricciones en la formulación CSP presenada esuvo deerminado por el número de renes T y el número de dependencias L. Si L o T se incremenan, enonces ano el número de variables como el de resricciones se incremenarán ambién. El número de resricciones no cambia cuando se modifican los valores de frecuencia F D, FU o el valor de reraso λ, sin embargo esas variaciones influyen en la resringibilidad de las resricciones. Las combinaciones de renes T y frecuencias F uilizadas en la evaluación se muesran en las Tabla 1 (a) y (b), respecivamene. 57
14 Gesión y Gerencia Vol. 8 No. 2 Mayo - Agoso 2014 Tabla 1. Problema de Transpore Ferroviario. (a) Combinaciones de Trenes uilizada. (b) Combinaciones de Frecuencia y reraso uilizadas Fuene: Elaboración propia. La evaluación se llevó a cabo en una infraesrucura ferroviaria real que une a las ciudades españolas de Zaragoza y Caseas, a parir de daos faciliados por operadores de ADIF. El recorrido Zaragoza-Caseas consise en 7 dependencias. En odos esos casos de prueba se fija el número de dependencias (5 esaciones y 2 apeaderos). Sin embargo el número de renes, la frecuencia y el reraso, se cambian para cada caso de prueba. Resulados Como se indicó aneriormene, la resolución de un CSP consa de dos fases: Modelado y Solución. Así, los resulados de ese rabajo se presenan de igual forma. Fase de Modelado: Formulación CSP para el problema de asignación de horarios ferroviarios Se propone un modelado binario, no-normalizado con resricciones expresas en forma exensional, el cual, como un CSP coniene: Variables. Cada ren cuando pasa por una dependencia generará dos variables diferenes (iempo de llegada y iempo de salida): - iempo de salida del ren 58 T de la dependencia i, donde i J { }.
15 Modelado y Resolución del Problema de Asignación de Horarios para el Transpore Ferroviario uilizando Técnicas de Saisfacción de Resricciones iempo de llegada del ren T de la dependencia i, donde i J { }. Dominios. El dominio de cada variable es un inervalo [min V,max V], donde donde minv 0 y max V > min V. Ese inérvalo es obenido del operador ferroviario, y puede ener una funcionalidad de segundos o decasegundos. Resricciones. La asignación de horarios ferroviarios debe saisfacer un conjuno de reglas/requerimienos para que sea facible. Dichas reglas/requerimienos se clasificaron en res grupos, dependiendo si son: (1) reglas de ráfico, (2) requerimienos del usuario y (3) reglas opológicas. Esas reglas se modelaron con las siguienes resricciones: (1) Reglas de Tráfico. Las resricciones omadas en cuena son: - Resricción de cruce. Dos renes que viajen en direcciones opuesas no deben uilizar al mismo iempo la misma sección de vía única: dep > arr > Vdep > arr i+1 i+1 i i - Resricción de iempo de expedición. Exise un iempo dado para colocar un ren desviado de vuela a la vía principal para que salga de la esación. Así, depl - arrl E, donde E es el iempo de expedición especificado para el ren. - Resricción de iempo de recepción. Exise un iempo dado para desviar un ren desde la vía principal de forma al que puedan realizarse cruces y/o adelanamienos: arr 1 l arrl arr 1 l - arrl Recep, donde Recep es el iempo de recepción especificado para que el ren llegue al primero. - Resricción de iempo de rayeco. arr i+1 = dep i + Δi (i+1). Para cada ren y cada sección de vías, el iempo de rayeco esá dado por Δi (i+1), lo cual represena el iempo que el ren debe emplear en ir desde la dependencia l hasa dependencia l. i i (2) Requerimienos del usuario. Las principales resricciones son: - Número de renes viajando en cada senido n (ida) y m (vuela). T = TD T U, donde: T ( l : 0 i < n, l { L \ {l } } : l = l l = l ) D i j m i j i+1 j+1 T ( l : 0 i < n, l { L \ {l } } : l = l l = l ) U i j 0 i j i+1 j+1 - Recorrido: dependencias por las que visiar y iempo de parada para propósios comerciales en cada senido para cada ren T: j = {l, l,..., l }. 0 1 n 59
16 Gesión y Gerencia Vol. 8 No. 2 Mayo - Agoso Horario de Frecuencias: Los requerimienos de frecuencia F de la salida de +1 renes en ambas direcciones: depi - dep i = F + λi. Esa resricción es muy resriciva debido a que cuando son realizados los cruces, los renes deben esperar en las esaciones un ciero inervalo de iempo. Ese inervalo debe ser propagado a odos los renes que van en el mismo senido para manener el horario de frecuencia esablecido. El usuario puede requerir una frecuencia fija, una frecuencia enre un inervalo mínimo y máximo, o múliples frecuencias. Una frecuencia enre un inervalo mínimo y máximo fue la seleccionada en esa invesigación, lo que conviere al problema en nonormalizado: Para T : dep + F < dep dep + F + λ > dep D i D i i D i i Para T : dep + F < dep dep + F + λ > dep U i U i U i (3) Topología de la infraesrucura ferroviaria. resricciones son: Algunas de esas - Número de vías en las esaciones y el número de vías enre dos dependencias (vía única o vía doble). No esá permiido ni los cruces ni los adelanamienos en los ramos de vía única. - Resricciones de iempo adicional en la esación con propósios comerciales y/o écnicos. Cada ren T esá obligado a permanecer en una esación li por lo menos Comi unidades de iempo (parada comercial). El reso del iempo que el ren permanezca en la esación se considerará parada écnica (necesaria para gesionar cruces o adelanamienos): dep arr + Com i i i. De conformidad con los requerimienos de ADIF, el sisema debe obener una solución para que odas las resricciones anes mencionadas (ráfico, necesidades de los usuarios y opológicas) se cumplan. La fuene de las dificulades subyacene en la asignación de horarios ferroviarios son las siguienes: (a) cada dependencia genera dos variables cuyas allas de dominio son grandes (un problema combinaorio); (b) El aumeno de los renes aumena las resricciones disyunivas (que genera las ramas del árbol de búsqueda); (c) El aumeno de la frecuencia de los renes, hace que el problema sea más resricivo (a menudo no hay solución); (d) Enconrar una solución mediane un algorimo de búsqueda esándar como FC 60
17 Modelado y Resolución del Problema de Asignación de Horarios para el Transpore Ferroviario uilizando Técnicas de Saisfacción de Resricciones para las insancias propuesas en esa invesigación puede ardar más de doce horas. Fase de solución El modelado propueso se le aplican las siguienes écnicas de búsqueda exisenes en la lieraura: BT, FC, MAC3 y BLS. El CSP generado para cada problema de asignación de horarios ferroviarios coniene odas las variables y resricciones aneriormene mencionadas. Las resricciones de cruce fueron generadas resringiendo el número de cruces con la heurísica 1.0 propuesa por Salido (2008) para generar problemas con solución. Todas las resricciones esán presenadas en forma inencional y cada problema posee resricciones no-normalizadas. La Figura 4 muesra los resulados de la búsqueda en el ramo Zaragoza- Caseas uilizando los algorimos BT, FC, MAC3 y BLS. El número de renes T se incremenó de 2 a 16 uilizando las combinaciones de la Tabla 1 (a). Para odas las insancias el número de dependencias se fijó a 7; la alla del dominio se fijó a d=2500; las frecuencias de salida y llegada se fijaron a F D=100 y F U=120, respecivamene; el reraso se fijó a 5 y el iempo máximo de finalización se fijó en segundos. Cada problema genera diferenes insancias de CSP. Así por ejemplo, con la combinación de renes T1, el CSP generado es <58, 2500, 77, 2> y con la combinación de renes T10, el CSP generado es <226, 2500, 434, 2>. Figura 4. Tiempo de cómpuo (seg.) empleado por los algorimos de búsqueda BT, FC, MAC3 y BLS para el problema de asignación de horarios ferroviarios en el recorrido Zaragoza-Caseas, fijando L = 7 y F = F2 e incremenando T. Fuene: Elaboración propia. 61
18 Gesión y Gerencia Vol. 8 No. 2 Mayo - Agoso 2014 Como puede observarse en la Figura 4, en la búsqueda de una solución el algorimo BLS uvo mejor desempeño, en odas las insancias, que los algorimos MAC3, FC y BT. Ello se debe a que BLS uiliza la información almacenada en el úlimo sopore enconrado para guiar la búsqueda y no requiere rehacer el proceso de consisencia que si es hecho por FC y MAC3 (en dominios grandes, rehacer la consisencia varias veces es muy cososo en lo que se refiere a iempo de cómpuo). También, en insancias superiores a 4 renes, los algorimos FC y BT alcanzaron el iempo máximo de finalización sin generar la solución. Conclusiones El problema de asignación de horarios ferroviarios es un problema real que puede ser modelado como un CSP. En ese rabajo se ha presenado una herramiena auómaa que permie el modelaje binario no-normalizado de dicho problema y su resolución uilizando écnicas de solución exisenes en la lieraura, lo que permie opimizar el uso de la infraesrucura ferroviaria y faciliar el rabajo que realizan los planificadores encargados de realizar los mapas de recorridos. La formulación CSP genera problemas grandes y de amplios dominios en los que las écnicas de consisencia son imporanes para reducir el espacio de búsqueda y mejorar el proceso de búsqueda de soluciones. En la búsqueda el algorimo BLS uvo mejor desempeño que los algorimos MAC3, FC y BT, en varias insancias del problema de asignación de horarios ferroviarios, donde el iempo de cómpuo fue reducido en un 80% con respeco a MAC3 y fue reducido en un 99% con respeco a FC y BT en insancias con solución. Referencias bibliográficas Abril Monserra (2007). Paricionamieno y resolución disribuida mulivariable de problemas de saisfacción de resricciones. Tesis de docorado no publicada, Universidad Poliécnica de Valencia, España. Arangú Marlene, Salido Miguel and Barber Federico (2010). A filering echnique for he railway scheduling problem. In COPLAS 2010: ICAPS 2010 Workshop on Consrain Saisfacion Techniques for Planning and Scheduling Problems pages , 62
19 Modelado y Resolución del Problema de Asignación de Horarios para el Transpore Ferroviario uilizando Técnicas de Saisfacción de Resricciones Arangú Marlene y Jorge Agüero (2012). Algorimo de Resolución del problema de asignación de horarios para el ranspore. En 1er Congreso Venezolano de Ciencia, Tecnología e Innovación en el marco de la LOCTI y del PEII. Tomo 2. p Barber, Federico; Abril, Monserra; Salido, Miguel Ángel; Ingoloi, Laura; Tormos, Pilar and Lova, Anonio (2007). Survey of auomaed sysems for railway managemen. Technical Repor, DSIC-II/01/07. UPV. Barák, Roman (1999). Consrain programming: In pursui of he holy grail. In MaFyzPress, edior, Proceedings of he Week of Docoral Sudens (WDS99), Par IV, pages Barák, Roman; Salido, Miguel and Rossi Francesca (2010). New rends in consrain saisfacion, planning, and scheduling: a survey. The Knowledge Engineering Review, 25 (Special Issue 03): Beníez, José; Sanabria, Alicia; Areaga, Lis y Nieo, Corina (1991). Normas para la Realización de Trabajos de Ascenso del Personal Docene y de Invesigación de la UCLA. Bessiere, Chrisian y Régin, Jean-Charles (1996). MAC and combined heurisics: Two reasons o forsake fc (and cbj?) on hard problems. In Proceedings of he Second Inernaional Conference on Principles and Pracice of Consrain Programming, pages Biner, James R. and Reingold, Edward M. (1975). Backrack programming echniques. Commun. ACM, 18(11), Buker, T. and Seybold, B. (2012). Sochasic modelling of delay propagaion in large neworks. Journal of Rail Transpor Planning & Managemen, 2(12), CPAI08 (2010). [Página web]. Disponible en hp://www.cril.univarois.fr/cpai08/compeiion-08.pdf. [Consula: 2010, Marzo 03]. Eurosa: Esadísicas Europeas. (2011). [Página web]. Disponible en hp://epp.eurosa.ec.europa.eu. [Consula: 2011, Enero 15]. Haralick, R. and Ellio, G (1980). Increasing ree efficiency for consrain saisfacion problems. Arificial Inelligence, 14, Hernandez R.; Fernandez C. y Bapisa P (2006). Invesigación. 4a Edic. Ediorial McGrawHill. México. Meodología de la IFE: Insiuo de Ferrocarriles del Esado, Venezuela (2013). [Página web]. Disponible en hp://www.ife.gob.ve/. [Consula: 2013, Abril 2]. 63
20 Modelado y Resolución del Problema de Asignación de Horarios para el Transpore Ferroviario uilizando Técnicas de Saisfacción de Resricciones INE: Insiuo Nacional de Esadísica de España (2011). [Página web]. Disponible en hp://www.ine.es. [Consula: 2011, Enero 15]. Ingoloi, Laura (2007). Modelos y méodos para la opimización y eficiencia de la programación de horarios ferroviarios. Tesis de docorado no publicada, Universidad Poliécnica de Valencia. España. Mackworh, Alan K. (1977). Consisency in neworks of relaions. Arificial Inelligence, 8: Palma Méndez, José Tomás and Marín Morales, Roque (2008). Ineligencia Arificial: Méodos, écnicas y aplicaciones Ediorial McGraw-Hill. España. Salido, Miguel A. (2008). A non-binary consrain ordering heurisic for consrain saisfacion problems. Applied Mahemaics and Compuaion, 198(1), Silva de Oliveira, Elias (2001). Solving Single-Track Railway Scheduling Problem Using Consrain Programming. Tesis docoral no publicada, Universidad de Leeds, School of Compuing. Yorkshire, Inglaerra. Suar, Russell y Peer, Norvig (2010). Arificial Inelligence: A Modern Approach 3rd Ediion. Ediorial Prenice Hall. New Jersey, USA. Tormos, Pilar; Lova, Anonio; Barber, Federico; Ingoloi, Laura; Abril, Monserra and Salido, Miguel Ángel (2008). A geneic algorihm for railway scheduling problems. Meaheurisics for Scheduling In Indusrial and Manufacuring Applicaions, ISBN: pages Venezuela en Daos (2007). Transpore. Ediorial El Nacional Caracas Walker, Cameron; Snowdon, Jody y Ryan, David (2005). Simulaneous disrupion recovery of a rain imeable and crew roser in real ime. Compu. Oper. Res pages , Zorrilla Arena, Saniago (2004). Inroducción a la Meodología de la Invesigación. Ediorial Aguilar León. México..,. 64
Un algoritmo para la Planificación de Producción en un Sistema en Red de Fabricación basada en Sistemas Multiagente 1
X Congreso de Ingeniería de Organización Valencia, 7 y 8 de sepiembre de 2006 Un algorimo para la Planificación de Producción en un Sisema en Red de Fabricación basada en Sisemas Muliagene 1 Julio J. García-Sabaer
LÍNEAS DE MONTAJE CON TIEMPOS DEPENDIENTES DEL TIPO DE OPERARIO
27 Congreso Nacional de Esadísica e Invesigación Operaiva Lleida, 8-11 de abril de 2003 LÍNEAS DE MONTAJE CON TIEMPOS DEPENDIENTES DEL TIPO DE OPERARIO A. Corominas 1, R. Pasor 1, J. Plans 2 1 Insiuo de
Optimización del Despacho de Unidades Generadoras en una Central Hidroeléctrica Utilizando Algoritmos Evolutivos Multiobjetivo
Opimización del Despacho de Unidades Generadoras en una Cenral Hidroelécrica Uilizando Algorimos Evoluivos Muliobjeivo Carolina Villasani Universidad Caólica Nuesra Señora de la Asunción Faculad de Ciencias
Representación gráfica de curvas en forma paramétrica x a(t sent) 1.- Representar la curva dada por
Represenación gráfica de curvas en forma paramérica x a( sen) 1.- Represenar la curva dada por, siendo a > 0. y a(1 cos).- Emparejar cada curva con su gráfica ì ì x = a) ï x = í b) ï ì í ï c) ï x = - sen
Meodología del Índice de Nivel de Acividad Regisrada (INA R) Dirección responsable de la información esadísica y conenidos: DIRECCIÓN DE ESTADÍSTICAS ECONÓMICAS Realizadores: Ligia ordillo Pasquel Corrección
ECONOMÍA. Teoría del control óptimo: Una guía para principiantes! David Bardey y Hélène Bonnet ISSN 0124 4396
ISSN 0124 4396 ECONOMÍA BORRADORES DE INVESTTI I IGACIÓN No. 87. Enero 2006 Teoría del conrol ópimo: Una guía para principianes! David Bardey y Hélène Bonne UNIVERSIDAD DEL ROSARIO Colegio Mayor de Nuesra
Navegación Autónoma de un Robot Móvil usando Técnicas Probabilísticas de Localización y Mapeo basadas en Métodos Monte Carlo Secuenciales
Navegación Auónoma de un Robo Móvil usando Técnicas Probabilísicas de Localización y Mapeo basadas en Méodos Mone Carlo Secuenciales Iván A. Calle Flores Universidad Nacional de Ingeniería icallef@uni.pe
Enfoques de Programación Matemática para la Previsión de la Demanda mediante descomposición de series temporales
IX Congreso de Ingeniería de Organización Gijón, 8 y 9 de sepiembre de 2005 Enfoques de Programación Maemáica para la Previsión de la Demanda mediane descomposición de series emporales Josefa Mula Bru,
Criterios de evaluación y selección de los proyectos de inversión en Cuba
Crierios de evaluación y selección de los proyecos de inversión en Cuba Auor: Msc. Eliover Leiva Padrón E-Mail: eleyva@ucfinfo.ucf.edu.cu Insiución: Universidad de Cienfuegos Carlos Rafael Rodríguez Carreera
Sus experiencias con el cáncer
Número de OMB: 0935-0118 Fecha de vencimieno de la aprobación: 01/31/2013 Sus experiencias con el cáncer l Esa encuesa es acerca de las secuelas o efecos secundarios del cáncer y de los raamienos para
MODELO PARA EL CÁLCULO DE TARIFAS DE EMPRESAS ELÉCTRICAS DE DISTRIBUCIÓN CONSIDERANDO ASPECTOS ECONÓMICO-FINANCIEROS
MODELO PARA EL CÁLCULO DE TARIFAS DE EMPRESAS ELÉCTRICAS DE DISTRIBUCIÓN CONSIDERANDO ASPECTOS ECONÓMICO-FINANCIEROS Marcos Facchini (*), Albero Andreoni (*), Andrés Koleda (**), Ángel Garay (**), María
Master en Economía Macroeconomía II. 1 Problema de Ahorro-Consumo en Horizonte Finito
Maser en Economía Macroeconomía II Profesor: Danilo Trupkin Se de Problemas 1 - Soluciones 1 Problema de Ahorro-Consumo en Horizone Finio Considere un problema de ahorro-consumo sobre un horizone finio
Documento de Trabajo. Restricciones al crecimiento:
Documeno de Trabajo Resricciones al crecimieno: Algunas consideraciones sobre el capial humano CODIGO 7123 CODIGO 7123 Resumen Siguiendo el enfoque denominado Diagnósico del crecimieno, en una primera
DERECHOS BÁSICOS DE APRENDIZAJE matemáticas - grado 9
4 Reconoce el significado de los eponenes racionales posiivos negaivos uiliza las lees de los eponenes. Por ejemplo: 7 7 7 + 7 4 7 7 7 7 40 ( 7 / ) / 7 / / 7 /0 0 7,... Uiliza la noación cienífica para
COMPARACION DE PLANES DE PENSIONES DESDE LA PERSPECTIVA DEL INVERSOR
COMPARACION DE PLANES DE PENSIONES DESDE LA PERSPECTIVA DEL INVERSOR Monserra Guillén 1, Jens Perch Nielsen 2 y Ana M. Pérez-Marín 3 RESUMEN En ese rabajo se comparan res producos básicos de ahorro exisenes
Tesis de Maestría en Informática
PEDECIBA Informáica Insiuo de Compuación Faculad de Ingeniería Universidad de la República Monevideo Uruguay Tesis de Maesría en Informáica Redes de Conenido: Taxonomía y Modelos de evaluación y diseño
ALGORITMOS GENÉTICOS VERSUS FILTRO DE KALMAN EN LA PREDICCIÓN DE ACCIONES NORTEAMERICANAS: GE, GM, IBM, UTX Y VZ
UNIVERSIDAD DE CHILE FACULTAD DE ECONOMÍA Y NEGOCIOS ALGORITMOS GENÉTICOS VERSUS FILTRO DE KALMAN EN LA PREDICCIÓN DE ACCIONES NORTEAMERICANAS: GE, GM, IBM, UTX Y VZ Seminario para opar al íulo de Ingeniero
LÍNEAS DE FASES. Fig. 1. dx (1) dt se llama Ecuación Diferencial Ordinaria (E.D.O.) de Primer Orden definida en Ω.
LÍNEAS DE FASES E. SÁEZ Sea el dominio Ω R R y la función F : Ω R. F R Ω Una epresión de la forma Fig. 1 d (1) = F(,), o bien, ẋ = F(,) se llama Ecuación Diferencial Ordinaria (E.D.O.) de Primer Orden
Los datos fueron obtenidos de una publicación del Golden Gate Bridge.
Pronósicos Resumen El procedimieno Pronósicos esa diseñado para pronosicar valores fuuros de daos de series de iempo. Una serie de iempo consise de un conjuno secuencial de daos numéricos omados en inervalos
Comparación de Relajaciones de Términos Bi-Lineales: Aplicación al Problema de Programación de Mezclado Multi-Período
Comparación de Relajaciones de Términos Bi-Lineales: Aplicación al Problema de Programación de Mezclado Muli-Período Danilo A. Figueroa P., Rafael R. A. Vargas, Aldo R. Vecchiei y José Espinosa INGAR,
Departamento de Teorías Psicológicas y Psicología Clínica
168 Faculad de psicología deparameno de eorías psicológicas y psicología clínica Deparameno de Teorías Psicológicas y Psicología Clínica Adapación de la prueba de evaluación del funcionamieno familiar
Plantas mini hidroeléctricas con bombas centrífugas y motores de inducción
Planas mini hidroelécricas con bombas cenrífugas y moores de inducción Dr. Armando Llamas Terrés (Senior Member) Cenro de esudios de energía - ITESM, Campus Monerrey allamas@iesm.mx Ing. Juan José Flores

References: RESOLUCIÓN 
 resolución 
 Resolución 
 Resolución 
 resolución 
 Resolución 
 resolución 
 Resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 Resolución 
 resolución 
 Resolución 
 Resolución 
 resolución 
 resolución 
 Resolución 
 Resolución 
 Resolución