Motivation

Imaginez que vous êtes propriétaire d'une compagnie aérienne. Votre compagnie aérienne doit affecter ses avions basés à New York pour couvrir tous les vols réguliers à venir.

Il y a 10 vols et 8 séquences de vols. Chaque séquence de vols se compose de plusieurs vols.

Par exemple, une séquence de vols peut comprendre des vols de New York à Buffalo, de Buffalo à Chicago et de Chicago à New York.

Chaque séquence de vol a un certain coût. Nous devons sélectionner un sous-ensemble de séquences de vol afin qu'il y ait au moins un avion pour chaque vol.

Il existe de nombreuses façons de sélectionner une combinaison de séquences de vol afin qu'il y ait un avion disponible pour chaque vol. Une combinaison possible est comme ceci :

Une autre combinaison possible est comme ceci :

Et beaucoup plus.

Quelle combinaison de séquences votre compagnie aérienne doit-elle choisir pour que la contrainte soit satisfaite et le coût minimisé ?

De nombreuses grandes compagnies aériennes sont confrontées à ce problème. American Airlines a estimé que son système basé sur la programmation mathématique permet d'économiser environ 20 millions de dollars par an.

Dans cet article, vous apprendrez à utiliser la programmation en nombres entiers et Python pour résoudre ce problème.

Qu'est-ce que la programmation en nombres entiers ?

La programmation en nombres entiers implique des problèmes avec des objectifs et des contraintes. Certaines ou toutes les variables sont limitées à des nombres entiers.

CVXPY est un outil Python qui fournit des interfaces à de nombreux solveurs de programmation en nombres entiers. Pour installer CXVPY, tapez :

pip install cvxpy

Obtenir des données

Commencez par télécharger les données depuis Google Drive :

Obtenez l'horaire, le coût et les heures de chaque séquence de vol.

Transformez tous les nombres positifs en 1 :

Paramètres d'entrée

Définissez les paramètres d'entrée :

Variables de décision

Définir les variables de décision en utilisant cp.Variable:

Contrainte

Il doit y avoir au moins un avion par vol. Par exemple, pour s'assurer qu'il y a au moins un avion pour le vol de New York → Buffalo, la séquence de vol 1, 4 ou 7 doit être choisie.

Pour s'assurer qu'il y a au moins un avion pour le vol New York → Cincinnati, la séquence de vol 2 ou 5 doit être choisie.

Ainsi pour le vol New York → Buffalo, on a la contrainte :

En généralisant cette contrainte pour les 10 vols, nous avons :

Objectif

Nous voulons choisir les séquences de vol qui minimisent le coût total.

Résoudre le problème

Maintenant que nous avons des contraintes et un objectif, résolvons le problème !

13.0

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

Cela signifie que l'avion doit voler :

• de New York → Buffalo → Chicago → New York
• de New York → Cincinnati → Pittsburgh → New York
• de New York → Chicago → Cincinnati → New York

Ajoutons cette contrainte à notre problème et voyons ce qui se passe.

Contrainte sur le nombre total d'heures

Nous devons d'abord obtenir le tableau représentant le nombre d'heures pour chaque séquence de vol :

Combinez la première contrainte avec la nouvelle contrainte :

Résoudre le problème:

20

C'est parce que différentes séquences de vols sont choisies.

Mais pourquoi les deuxième et troisième séquences de vols ne sont-elles pas choisies ? Si nous examinons de près le tableau représentant les heures, nous pouvons voir que le nombre total d'heures des 3 premiers vols dépasse 1700.

Cependant, le nombre total d'heures des première, cinquième et sixième séquences de vols est inférieur à 1700, ce qui satisfait la contrainte.

Et voici la représentation visuelle des nouvelles séquences de vol choisies.

Conclusion

Toutes nos félicitations! Vous venez d'apprendre à choisir des séquences de vols tout en minimisant le coût. J'espère que cet article vous motivera à résoudre des problèmes similaires en utilisant la programmation en nombres entiers et Python.

N'hésitez pas à forker et à jouer avec le code de cet article dans ce repo Github :

J'aime écrire sur les concepts de base de la science des données et jouer avec différents algorithmes et outils de science des données. Vous pouvez communiquer avec moi sur LinkedIn et Twitter .

Star ce repo si vous voulez vérifier les codes de tous les articles que j'ai écrits. Suivez-moi sur Medium pour rester informé de mes derniers articles sur la science des données comme ceux-ci :

Référence

Chen, D.-S., Batson, RG et Dang, Y. (2010). Programmation en nombres entiers appliquée : modélisation et solution . J. Wiley & Fils.