OR-Tools est un logiciel Open Source d'optimisation combinée, qui cherche à trouver la meilleure solution à un problème parmi un très grand nombre de solutions. Voici quelques exemples de problèmes résolus avec OR-Tools:
- Routage des véhicules: trouvez des itinéraires optimaux pour les parcs de véhicules qui récupèrent et livrent des colis en fonction de contraintes (par exemple, "ce camion ne peut pas supporter plus de 9 000 kg" ou "toutes les livraisons doivent être réalisées dans un délai de deux heures."
- Planification: trouvez le planning optimal pour un ensemble complexe de tâches, dont certaines doivent être exécutées avant d'autres, sur un ensemble fixe de machines ou d'autres ressources.
- Emballage dans des bacs: placez autant d'objets de différentes tailles que possible dans un nombre fixe de bacs avec des capacités maximales.
Dans la plupart des cas, de tels problèmes présentent un grand nombre de solutions possibles. Trop souvent pour qu'un ordinateur les recherche toutes. Pour contourner ce problème, OR-Tools utilise des algorithmes de pointe pour affiner l'ensemble de recherche et trouver une solution optimale (ou presque).
OR-Tools inclut les résolveurs pour:
- Programmation avec contrainte
- Ensemble de techniques permettant de trouver des solutions réalisables à un problème exprimé par des contraintes (par exemple, une salle ne peut pas être utilisée pour deux événements en même temps, ou la distance à parcourir les cultures doit être inférieure à la longueur du tuyau, ou pas plus de cinq émissions télévisées peuvent être enregistrées en même temps).
- Programmation linéaire et mixte à nombres entiers
- L'optimiseur linéaire Glop trouve la valeur optimale d'une fonction d'objectif linéaire, compte tenu d'un ensemble d'inégalités linéaires en tant que contraintes (par exemple, affecter des personnes à des tâches ou trouver la meilleure allocation d'un ensemble de ressources tout en minimisant les coûts). Glop et le logiciel de programmation à nombres entiers SCIP sont également disponibles via le service d'optimisation de Google Apps Script.
- Acheminement des véhicules
- Bibliothèque spécialisée permettant d'identifier les meilleurs itinéraires selon les contraintes.
- Algorithmes de graphes
- Code permettant de trouver les chemins les plus courts dans les graphiques, les flux de coût minimal, les flux max. et les attributions de somme linéaire.
La section suivante vous explique comment utiliser rapidement OR-Tools.