Problème de livraisons à séquence fixée

Colloque avec actes et comité de lecture. internationale.International audienceCet article présente plusieurs méthodes de découpage d'une séquence préfixée de clients à livrer par un unique véhicule. Lorsque l'ordre de livraison des clients pour un véhicule donné est imposé, le calcul des tournées de ce véhicule revient à déterminer le nombre de retours au dépôt et les dates correspondantes. Ce problème se complique rapidement dès que l'on prend en compte des contraintes telles que des dates de disponibilité des produits ou des dates de livraisons souhaitées. Les méthodes de résolution proposées varient suivant la nature du critère à optimiser (date de retour de la dernière tournée, nombre de livraisons en retard, ...). Les algorithmes présentés sont polynomiaux, inspirés de méthodes de programmation dynamique et destinés à être intégrés dans des méta-heuristiques afin de résoudre des problèmes plus complexes. Cette étude généralise également certains travaux de la littérature