Présentation

La gestion autonome du parc automobile rassemble l'automatisation du véhicule, la logistique et la recherche opérationnelle pour déplacer les personnes et les biens de façon efficace.Le défi principal est de décider quels véhicules vont où, quand et avec quelle charge – décisions qui impliquent souvent des choix entiers distincts (nombre de véhicules, oui/non affectations, séquençage de la route). La programmation entière fournit un cadre mathématique rigoureux pour modéliser ces décisions et trouver des solutions optimales ou quasi-optimales.

Comprendre la programmation intégrale

La programmation intégrale (IP) est une branche d'optimisation mathématique où certaines ou toutes les variables de décision sont contraintes d'être des entiers. Lorsque toutes les variables sont des entiers, elle est appelée un programme entier pur; lorsqu'un sous-ensemble est des entiers, c'est un programme entier mixte (PIM). IP est essentiel pour la gestion du parc parce que de nombreuses décisions opérationnelles sont naturellement discrètes : vous ne pouvez pas affecter 2,7 véhicules à une route, ou envoyer un demi camion à un client.

Pourquoi les variables entières comptent-elles dans la gestion de la flotte

La programmation linéaire continue (LP) suppose que les variables peuvent prendre n'importe quelle valeur réelle. Cela fonctionne pour les problèmes de mélange, mais pour l'attribution, l'ordonnancement et l'acheminement, les solutions fractionnelles sont inutiles. Par exemple, une solution LP pourrait suggérer d'envoyer 1,3 véhicules du dépôt A et 0,7 véhicules du dépôt B. La programmation Integer force le modèle à choisir des nombres entiers, donnant des plans actionnables.

  • Diversité de la zone (0 ou 1):[ Utilisé pour des décisions oui/non telles que -does vehicle v visit location i?-- ou -- est-ce que la route r est sélectionnée?-
  • [Règle les nombres comme - Nombre de véhicules affectés à des postes de travail ou -Inventory détenus à l'entrepôt w.
  • Programmation en entier mixte (MIP): Combine des variables en entier et en continu; par exemple, une variable continue pour la consommation de carburant, ainsi que des variables en entier pour l'attribution du véhicule.

L'IP classique est difficile à utiliser dans de nombreux cas, ce qui signifie que les temps de solution les plus difficiles augmentent de façon exponentielle avec la taille du problème.

Composantes essentielles d'un modèle IP de gestion de flotte

Chaque modèle de programmation entier pour la gestion de flotte partage trois éléments : les variables de décision, une fonction objective et des contraintes. L'art est de choisir la bonne représentation pour le problème opérationnel.

Variables de décision

Les variables de décision traduisent les actions réelles en termes mathématiques. Pour la gestion autonome de la flotte, les variables typiques comprennent:

  • = 1 si le véhicule v se déplace de l'emplacement i à l'emplacement j, 0 autrement (binaire, pour l'itinéraire).
  • = 1 si le véhicule v est en service pendant l'intervalle de temps t, 0 autrement (binaire, pour l'horaire).
  • = nombre de véhicules affectés à la station de base k (entier, pour l'attribution des dépôts).

Le choix de l'indexation variable (par véhicule, temps, emplacement, tâche) affecte directement la taille du modèle et la solvabilité. Il est souvent bénéfique de la symétrie agrégée – par exemple, en utilisant des variables -route- plutôt que des variables -edge- pour réduire le nombre de décisions binaires.

Fonction objective

L'objectif consiste à quantifier ce que l'exploitant de la flotte s'intéresse à la question.

  • Minimiser la distance ou le temps de déplacement total : Réduit directement les coûts de carburant et d'énergie et améliore la réactivité.
  • Minimiser le coût total de fonctionnement:[ Comprend les dépenses d'usure, d'entretien et de conducteur (le cas échéant).
  • Nombre maximal de demandes signifiées :[ pertinentes dans les systèmes répondant à la demande où certaines demandes peuvent être rejetées.
  • Utilisation des capacités:[ Réduire au minimum les écarts dans l'utilisation des véhicules pour éviter les véhicules au ralenti et les goulets d'étranglement.

Des modèles multi-objectifs peuvent être créés en combinant plusieurs termes avec des poids, ou en traitant un objectif comme une contrainte (par exemple, servir toutes les demandes dans un délai maximum, puis minimiser la distance).

Contraintes

Les contraintes font respecter les règles opérationnelles et les limitations physiques du système. Les familles de contraintes clés pour les flottes autonomes sont:

  • Conservation des écoulements :[ Pour les problèmes de routage, chaque véhicule qui entre dans un emplacement doit le quitter (sauf dans les dépôts).
  • Contraintes de capacité:[ Les véhicules peuvent transporter un nombre limité de passagers ou de charges utiles.
  • Fenêtres horaires: Chaque ramassage ou livraison doit se faire dans un intervalle déterminé (p. ex. entre 14 h et 15 h).
  • Contraintes de batterie ou de portée:[ Les véhicules électriques autonomes ont une distance maximale avant de devoir se recharger.
  • Limites de taille de la flotte :[ Le nombre total de véhicules disponibles est fixe ou le nombre de véhicules déployés par quart est limité.
  • Exclusivité de l'attribution:[ Chaque tâche est attribuée à un seul véhicule (ou à zéro si la demande peut être rejetée).

La formulation de contraintes utilise souvent des techniques -big-M-- pour modéliser les conditions logiques, comme -if vehicle v sert location i, alors il doit aussi servir emplacement j dans son itinéraire.

Formuler des problèmes communs d'optimisation de la flotte

Plusieurs problèmes canoniques apparaissent à plusieurs reprises dans la gestion autonome de la flotte. La compréhension de leurs formulations IP aide les praticiens à construire des modèles pour leur contexte spécifique.

Problème d'acheminement des véhicules (VRP)

Le VRP est l'épine dorsale de nombreux systèmes d'optimisation de flotte. Un ensemble de clients doit être visité par un parc de véhicules commençant et se terminant dans les dépôts. La formulation classique utilise des variables binaires et comprend des contraintes pour le degré (chaque client visité exactement une fois), l'élimination du sous-tour (pour empêcher les cycles déconnectés) et la capacité du véhicule.

Une formulation simple à un seul dépôt de PRP (sans fenêtre temporelle) ressemble à :

min - v -(i,j) c ij · x ijv
subject to:
- v - j x ijv = 1 pour chaque client i (visiter chaque client une fois)
- i x i0v = 1 pour chaque véhicule v (dépôt de sortie)
- j x 0jv = 1 pour chaque véhicule v (retour au dépôt)
-conservation du débit, capacité, élimination du sous-tour.

Affectation et calendrier

La gestion du parc de véhicules comprend également l'affectation de véhicules à des postes de travail, à des tâches ou à des postes de recharge. Le problème d'affectation réduit le coût (p. ex., le déplacement jusqu'au point de départ) sous réserve que chaque véhicule reçoive au plus une tâche et que chaque tâche soit couverte par un seul véhicule.

Emplacement du dépôt et composition de la flotte

Les décisions stratégiques, comme le lieu où se trouvent les bornes de recharge ou le nombre de véhicules de chaque type à acheter, sont également des problèmes de programmation entiers. Par exemple, un modèle d'emplacement d'installation utilise des variables binaires pour les ouvertures de dépôts et des variables entiers pour le nombre de véhicules assignés de chaque dépôt.

Rééquilibrage en temps réel

Dans les systèmes autonomes de transport à roues, les véhicules au ralenti doivent être repositionnés dans des zones de demande prévue. Il s'agit d'un problème de transport dynamique qui peut être modélisé comme un débit minimum-coût avec des débits entiers, mis à jour toutes les quelques minutes à l'arrivée de nouvelles demandes.

Techniques de solution et logiciels

Les modèles de programmation entiers sont résolus en utilisant un mélange de méthodes exactes et approximatives. Le choix dépend de la taille du problème, du temps de calcul disponible et des exigences de qualité de la solution.

Méthodes exactes

  • Branche et liée: L'algorithme exact le plus commun pour MIP. Il divise récursivement la région possible en sous-problèmes (branchage) et calcule les limites aux branches suboptimales.
  • Plans de coupe: Des inégalités ajoutées à la relaxation LP pour resserrer la région possible et accélérer la recherche. Les résolveurs modernes combinent branche et lié avec des plans de coupe (branche et coupe).
  • Branche et prix: Utilisé lorsque le problème a un grand nombre de variables (comme toutes les routes possibles en VRP). Le solveur génère de nouvelles variables (colonnes) en vol à l'aide d'un sous-problème de tarification.

Parmi les principaux résolveurs commerciaux pour la PI, on compte IBM ILOG CPLEX[, Gurobi et FICO Xpress[. Des options open-source comme SCIP[ et Google OR-Tools sont largement utilisées dans la recherche et l'industrie.

Méthodes heuristiques et métaheuristiques

Lorsque les cas de problèmes sont trop importants pour des méthodes exactes (en milliers de véhicules et en millions de demandes), les approches heuristiques offrent de bonnes solutions rapidement.

  • Heuristique constructive:[ Construire une solution étape par étape (p. ex. insertion voisine la plus proche pour le PDV).
  • Recherche locale :[ Améliorer une solution existante par de petites modifications (2-opt, relocaliser, échanger).
  • Métaheuristique: Guidez la recherche locale pour échapper à l'optima local. Exemples comprennent le recuit simulé, algorithmes génétiques, recherche de tabu et recherche de quartier (LNS).

De nombreuses plateformes de gestion de flotte utilisent une approche hybride : exécuter un solveur IP pour un temps limité pour obtenir une solution de haute qualité, puis appliquer l'heuristique pour l'améliorer davantage.

Applications et études de cas dans le monde réel

Des modèles de programmation entiers sont déployés dans des parcs de véhicules autonomes dans plusieurs secteurs.

Autonome (Robotaxis)

Les entreprises comme Waymo et Cruise utilisent l'optimisation pour associer les véhicules aux passagers, gérer des milles vides et rééquilibrer les flottes. Un MIP typique pour l'expédition robotaxi comprend des contraintes d'affectation (un véhicule par trajet), des fenêtres de temps, une autonomie de batterie et une pénalité pour les voyages rejetés. L'objectif minimise le temps d'attente des passagers et la distance totale de voyage.

Véhicules de livraison autonomes

Nuro, Starship Technologies et Amazon Scout déploient des flottes de petits véhicules autonomes pour la livraison de dernier kilomètre. Integer planifie les itinéraires et les horaires pour des centaines de véhicules, souvent avec des fenêtres de livraison sensibles au temps et un stockage à bord limité.

Robots mobiles autonomes d'entrepôt (RAM)

Dans les centres d'exécution, les flottes de RMA déplacent des étagères ou des paquets entre les stations. La programmation entière coordonne le choix et le placement des tâches, l'évitement de la congestion et les calendriers de charge des batteries. Une étude 2020 dans Annals of Operations Research a décrit un PIM pour l'attribution des tâches de robot et le routage qui a réduit le temps de ralenti de 18 %.

Transport en commun et mobilité partagée

Les navettes autonomes dans des environnements contrôlés (aéroports, campus, communautés de retraite) nécessitent une planification et une planification des itinéraires qui s'adaptent à la demande.

Défis et considérations

Malgré la puissance de la programmation intégrale, l'appliquer aux flottes autonomes comporte plusieurs obstacles pratiques.

Échelle et temps de calcul

Un parc de 500 véhicules qui répond à 10 000 demandes par jour conduit à un PIM avec des dizaines de millions de variables et de contraintes. La résolution de l'optimalité peut prendre des heures ou des jours. Dans les systèmes en temps réel, les décisions doivent être prises en secondes. La solution est d'utiliser la décomposition (p. ex. horizon roulant basé sur le temps, regroupement géographique) ou heuristique rapide avec réoptimisation périodique.

Incertitude et stochastie

Les temps de voyage, la demande des clients et la disponibilité des véhicules ne sont pas parfaitement connus. Les modèles IP déterministes peuvent devenir sous-optimaux lorsque les prédictions sont erronées. La programmation stochastique et l'optimisation robuste prolongent l'IP pour gérer l'incertitude, mais ils augmentent la complexité du modèle.

Intégration avec les systèmes en temps réel

Un modèle IP n'est utile que s'il peut ingérer des données en direct à partir de véhicules, des API de trafic et des files d'attentes. Cela nécessite une architecture logicielle qui alimente le dernier état dans le solveur et map la solution optimale de retour aux commandes de flotte. La latence entre résolution et exécution doit être minimale.

Équité et contraintes réglementaires

Les flottes autonomes doivent respecter les lois sur la circulation, les restrictions d'accès et éventuellement les exigences d'équité (par exemple, les quartiers mal desservis), lesquelles peuvent être codées comme des contraintes (par exemple, le nombre minimum de véhicules affectés à une zone) ou comme des pénalités souples dans l'objectif.

Orientations futures

La programmation intégrale pour les flottes autonomes continue d'évoluer le long de plusieurs frontières.

Intégration avec le Machine Learning

Les modèles ML peuvent prédire les tendances de la demande, les temps de déplacement et les défaillances du véhicule, en alimentant ces prévisions en paramètres dans le modèle IP. L'apprentissage du renforcement peut également apprendre les politiques de rééquilibrage, tandis que l'IP gère les décisions d'attribution combinatoire.

Optimisation dynamique et distribuée

Les modèles de propriété intellectuelle centralisés deviennent un goulot d'étranglement pour les flottes de milliers de véhicules. Les schémas de décomposition permettent aux véhicules ou aux zones de résoudre des sous-problèmes plus petits qui se coordonnent par les prix (relaxation lagrangique) ou par consensus (ADMM).

Plateformes d'optimisation de bout en bout

Les nouvelles plateformes logicielles combinent des solutions IP, des simulations et des visualisations pour permettre aux opérateurs de flotte de construire, tester et déployer rapidement des modèles. Des environnements à faible code et open-source comme OR-Tools et COIN-OR Foundation réduisent la barrière à l'entrée.

Conclusion

En définissant avec soin les variables, les objectifs et les contraintes, les opérateurs peuvent résoudre les problèmes de routage, de programmation et d'assignation qui maximisent l'efficacité et la réactivité. Les solutions modernes et les méthodes heuristiques permettent de gérer les grands parcs de véhicules du monde réel. À mesure que la technologie autonome mûrit et que la demande de mobilité sur demande augmente, la programmation intégrale restera la pierre angulaire des opérations intelligentes de la flotte, permettant des systèmes non seulement autonomes mais également gérés de manière optimale.