Modélisation de Problèmes de Tournées de Véhicules Avec LocalSolver

EasyChair Preprint 2646

Abstract

LocalSolver est un solveur d’optimisation mathématique de type model & run. Son formalisme d’entrée lui permet d’accepter tout modèle utilisant les opérateurs mathématiques usuels (arithmétiques, logiques, relationnels, etc) avec des variables continues, entières ou ensemblistes. La recherche de solutions est faite par une approche heuristique basée sur des techniques de recherche locale dont l’objectif est de trouver rapidement des solutions de qualité. Des techniques d'optimisation globale sont utilisées en complément de la recherche locale pour accélérer la recherche de solutions, pour calculer des bornes et arrêter la recherche lorsque la solution optimale est trouvée.

Les variables de liste ont été introduites dans LocalSolver 5.5 pour modéliser de façon plus compacte des problèmes avec une notion d'ordre ou de séquence. Une liste est une variable de décision riche qui représente une sous-permutation de l'ensemble {0, 1, ..., n-1}. Le formalisme de modélisation de LocalSolver a ensuite été étendu pour ajouter des opérateurs variadiques permettant de manipuler plus facilement des listes. L'objectif de cet exposé est de donner des retours d'expérience sur la modélisation des problèmes de tournées de véhicules industriels.

Keyphrases: Routing, recherche locale, solveur, tournées

@booklet{EasyChair:2646,
  author    = {Tiphaine Rougerie},
  title     = {Best Practices to Model Routing Problems Using LocalSolver},
  howpublished = {EasyChair Preprint 2646},
  year      = {EasyChair, 2020}}