Análisis del problema de asignación de flotas flexible con ventanas de tiempo discretas, duración variable, preferencias de salida y relaciones de precedencia. Optimización por colonias de hormigas

Resumen

Una correcta gestión de ?otas incide directamente en la cuenta de resultados de una empresa de transporte de viajeros. Existen variantes del problema de asignación de ?otas en cuanto al objetivo que se busca, en cuanto a la forma de modelar el problema y en cuanto a la técnica de resolución. En este trabajo presentamos nuevas restricciones que lo acercan mucho a su aplicación de problemas de empresas reales, para resolverlo a continuación utilizando la optimización mediante colonias de hormigas. Finalmente los resultados obtenidos son comparados con los que se obtendrían operando con la programación lineal, que es el método más utilizado en la resolución de este tipo de problemas. 2. Introducción Sherali y otros (2005) re?ejan la gran importancia en el bene?cio que tiene para una compañía aérea la toma de decisiones sobre su ?ota, y por tanto su correcta gestión constituye un componente esencial para la empresa. Bélanger y otros (2005) de?nen el problema de asignación de ?otas (FAP, Fleet Assignmet Problem) como la asignación del tipo de avión a cada vuelo que ofrezca mayor bene?cio global. La mayoría de los trabajos publicados sobre optimización de ?otas están referidos al sector n del transporte aéreo; nosotros planteamos un modelo ?exible que se pueda aplicar a los sectores aéreo, marítimo y terrestre. Una variable muy considerada en el sector marítimo es la velocidad desarrollada durante el trayecto, ya que el consumo es función de la velocidad, y un pequeño porcentaje de ahorro en el consumo signi?ca mucho dinero de ahorro al ?nal del año. En este artículo introducimos como variable la duración del trayecto (y por tanto la velocidad), llevando a optimizaciones con una reducción total de los costes de plani?cación e, incluso con una reducción del número de vehículos. Hablaremos de trayecto en general como producto que venden las compa compañías de transporte de viajeros para independizarlo del sector. También hablaremos de estaciones como término general de aeropuerto, estación de autobuses o puerto. Las ventanas de tiempo en la salida de un trayecto fueron una de las primeras opciones de optimización introducidas, ya que ajustando las horas de salida de los trayectos se puede reducir n el número de vehículos necesarios, Bélanger (2004). Esta ?exibilidad en la hora de salida aumenta el número de posibles conexiones entre trayectos y ofrece posibilidades de mejorar mero la calidad de la solución en términos de bene?cio o de reducción del número de vehículos. Pero esta ?exibilidad debe ser controlada para que no se produzcan situaciones no deseables. En este sentido, introducimos el concepto de relaciones de precedencia entre trayectos, como mecanismo de carácter general que permite modelar restricciones de diversa naturaleza que aparecen en los problemas de la vida real, y que sirven para evitar esas situaciones no deseables que puede provocar la apertura de la hora de salida a una ventana de tiempo. Estas relaciones de 1326 Quantitative Methods precedencia se establecen ligando las variables de comienzo y ?n de varios trayectos. Las ventanas de tiempo en la salida ofrecen mucha ?exibilidad, pero a menudo no ofrecen la su?ciente como para plasmar los requerimientos que se plantean en situaciones de la vida real. Una de estas situaciones son los trayectos que se realizan una o varias veces a la semana. Por ejemplo, el requerimiento puede ser que el trayecto salga el lunes o el martes por la noche, entre las 20:00 y las 23:00. Este requerimiento no se puede expresar mediante una ventana de tiempo en la salida. Nosotros introducimos el concepto de ventana de tiempo discreta en la salida, como un conjunto de ventanas de tiempo que de?nen la posible salida del trayecto, de forma que la salida del trayecto que ?jará el sistema de optimización estará dentro de una sola de las ventanas de tiempo de?nidas en la salida. Al igual que las relaciones de precedencia, las ventanas de tiempo discretas se presentan como un mecanismo de carácter general que permite modelar muchas situaciones de diferente naturaleza que se presentan en la vida real. La ?exibilidad de las ventanas de tiempo en la salida también puede ser medida en términos de bene?cio: podemos dar la ?exibilidad a la hora de salida de un trayecto para que se mueva entre las 09:00 y las 11:00, pero sabemos que habría algo más de demanda a las 10:00 que a las 09:00 o las 11:00. Si se conocieran con exactitud las variaciones de demanda en función de la hora de salida del trayecto, se podría introducir ese bene?cio variable en la función objetivo del problema. Pero no suele ser fácil medir esa función y además, la demanda suele ser muy f estocástica, por lo que en muchas ocasiones puede ser más práctico aprovechar la experiencia del comercial, y plasmarla en el concepto de hora preferida de salida dentro de la ventana de tiempo de salida del trayecto, que en el ejemplo propuesto al principio de esta párrafo sería las