Motivación

Imagínese que es propietario de una aerolínea. Su aerolínea debe asignar sus aviones con base en Nueva York para cubrir todos los próximos vuelos programados.

Hay 10 vuelos y 8 secuencias de vuelos. Cada secuencia de vuelos consta de varios vuelos.

Por ejemplo, una secuencia de vuelos puede constar de vuelos de Nueva York a Buffalo, de Buffalo a Chicago y de Chicago a Nueva York.

Cada secuencia de vuelo tiene un costo determinado. Necesitamos seleccionar un subconjunto de secuencias de vuelo para que haya al menos un avión para cada vuelo.

Hay muchas formas posibles de seleccionar una combinación de secuencias de vuelo para que haya un avión disponible para cada vuelo. Una posible combinación es la siguiente:

Otra posible combinación es la siguiente:

Y muchos más.

¿Qué combinación de secuencias debería elegir su aerolínea para que se satisfaga la restricción y se minimice el costo?

Muchas aerolíneas importantes se enfrentan a este problema. American Airlines estimó que su sistema basado en programación matemática ahorra alrededor de $ 20 millones por año.

En este artículo, aprenderá a utilizar la programación de enteros y Python para resolver este problema.

¿Qué es la programación de enteros?

La programación de enteros implica problemas con los objetivos y las limitaciones. Algunas o todas las variables están restringidas a números enteros.

CVXPY es una herramienta de Python que proporciona interfaces a muchos solucionadores de programación de enteros. Para instalar CXVPY, escriba:

pip install cvxpy

Obtener datos

Empiece por descargar los datos de Google Drive:

Obtenga el horario, el costo y las horas de cada secuencia de vuelo.

Convierte todos los números positivos en 1:

Parámetros de entrada

Definir parámetros de entrada:

Variables de decisión

Defina las variables de decisión usando cp.Variable:

Restricción

Debe haber al menos un avión por vuelo. Por ejemplo, para asegurarse de que haya al menos un avión para el vuelo de Nueva York → Buffalo, se debe elegir la secuencia de vuelo 1, 4 o 7.

Para asegurarse de que haya al menos un avión para el vuelo de Nueva York → Cincinnati, se debe elegir la secuencia de vuelo 2 o 5.

Por lo tanto, para el vuelo de Nueva York → Buffalo, tenemos la restricción:

Generalice esta restricción para los 10 vuelos, tenemos:

Objetivo

Queremos elegir las secuencias de vuelo que minimicen el coste total.

Resolver el problema

Ahora que tenemos limitaciones y un objetivo, ¡resolvamos el problema!

13.0

[1. 1. 1. 0. 0. 0. 0. 0.]

Eso significa que el avión debería volar:

• de Nueva York → Búfalo → Chicago → Nueva York
• desde Nueva York → Cincinnati → Pittsburgh → Nueva York
• desde Nueva York → Chicago → Cincinnati → Nueva York

Agreguemos esa restricción a nuestro problema y veamos qué sucede.

Restricción del número total de horas

Primero necesitamos obtener la matriz que representa la cantidad de horas para cada secuencia de vuelo:

Combine la primera restricción con la nueva restricción:

Resolver el problema:

20

Es porque se eligen diferentes secuencias de vuelos.

Pero, ¿por qué no se eligen la segunda y tercera secuencia de vuelos? Si observamos de cerca la matriz que representa las horas, podemos ver que las horas totales de los primeros 3 vuelos superan las 1700.

Sin embargo, el total de horas de la primera, quinta y sexta secuencia de vuelos es menor que 1700, lo que satisface la restricción.

Y aquí está la representación visual de las nuevas secuencias de vuelo elegidas.

Conclusión

¡Felicidades! Acaba de aprender a elegir secuencias de vuelos minimizando el costo. Espero que este artículo lo motive a resolver problemas similares utilizando programación de enteros y Python.

Siéntase libre de bifurcar y jugar con el código de este artículo en este repositorio de Github:

Me gusta escribir sobre conceptos básicos de ciencia de datos y jugar con diferentes algoritmos y herramientas de ciencia de datos. Podrías conectarte conmigo en LinkedIn y Twitter .

Protagonizar esta repo si quieres echa un vistazo a los códigos para todos los artículos que he escrito. Sígueme en Medium para mantenerte informado con mis últimos artículos sobre ciencia de datos como estos:

Referencia

Chen, D.-S., Batson, RG y Dang, Y. (2010). Programación de enteros aplicada: modelado y solución . J. Wiley & Sons.