Grants and Contributions:

Grant or Award spanning more than one fiscal year (2017-2018 to 2018-2019).

NSim Technologie offre des outils informatiques de cartographie pouvant afficher sur une page web des cartesx000D
sur lesquelles viennent se greffer des géo-données telles que le réseau routier, une partition du territoire enx000D
zones (villes, secteurs, quartiers ...), la localisation de points d'intérêt (stationnement, bornes-fontaines ...) dex000D
même que les adresses civiques. Dans la version actuelle de leur produit, NSim Technologie peut calculer lex000D
plus court chemin entre deux points sur le réseau routier. Toutefois, ils ont un besoin croissant de calculer lex000D
plus court chemin passant par plusieurs points. Ce problème classique est connu sous le nom du commisx000D
voyageur. Les adresses ne pouvant généralement pas être toutes visitées en une seule journée, ils désirentx000D
partitionner les adresses de sorte qu'elles soient visitées par des véhicules différents ou à des jours différents.x000D
Dans les deux cas, on doit partitionner les adresses de sorte que les parcours reliant les adresses de chaquex000D
partition soient de longueurs semblables. Finalement, selon l'application, certaines contraintes viendrontx000D
s'ajouter au problème. Dans un problème de collecte et de livraison de colis, on peut vouloir imposer que deuxx000D
adresses soient visitées par le même véhicule et dans un ordre préétabli. Dans le cadre de ce projet, nousx000D
développerons un logiciel capable de résoudre ce problème avec pour fonction objectif de minimiser le plusx000D
long parcours. Nous utiliserons la programmation par contraintes pour faciliter la modélisation des différentesx000D
variantes du problème et exploiter l'efficacité du branch & bound.