Grant: Engage Grants Program
Université Laval
$24,461.00
Planification des tournées de véhicules chez NSim Technologie
EF 2017-18
Résumé
NSim Technologie offre des outils informatiques de cartographie pouvant afficher sur une page web des cartessur lesquelles viennent se greffer des géo-données telles que le réseau routier, une partition du territoire enzones (villes, secteurs, quartiers ...), la localisation de points d'intérêt (stationnement, bornes-fontaines ...) demême que les adresses civiques. Dans la version actuelle de leur produit, NSim Technologie peut calculer leplus court chemin entre deux points sur le réseau routier. Toutefois, ils ont un besoin croissant de calculer leplus court chemin passant par plusieurs points. Ce problème classique est connu sous le nom du commisvoyageur. Les adresses ne pouvant généralement pas être toutes visitées en une seule journée, ils désirentpartitionner les adresses de sorte qu'elles soient visitées par des véhicules différents ou à des jours différents.Dans les deux cas, on doit partitionner les adresses de sorte que les parcours reliant les adresses de chaquepartition soient de longueurs semblables. Finalement, selon l'application, certaines contraintes viendronts'ajouter au problème. Dans un problème de collecte et de livraison de colis, on peut vouloir imposer que deuxadresses soient visitées par le même véhicule et dans un ordre préétabli. Dans le cadre de ce projet, nousdévelopperons un logiciel capable de résoudre ce problème avec pour fonction objectif de minimiser le pluslong parcours. Nous utiliserons la programmation par contraintes pour faciliter la modélisation des différentesvariantes du problème et exploiter l'efficacité du branch & bound.
Programme
Engage Grants Program
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
514090-2017
Name nom
Quimper, ClaudeGuy
Department département
Informatique et de génie logiciel
Organization id
51
Institution établissement
Université Laval
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2017
Competition year année de concours
2017
Award amount
24461
Program id
EGP
Program name en
Engage Grants Program
Program name fr
Programme de subventions d'engagement partenariat
Group en
Research partnerships programs
Group fr
Programmes de partenariat
Committee code
1552
Committee name en
Quebec Internal Decision Committee
Committee name fr
Comité de décision interne pour le Québec
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
2715
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Optimization
Research subject fr
Optimisation
Partie
1
Nb partie
1
Application title
Planification des tournées de véhicules chez NSim Technologie
Keyword
NSERC
Application summary
NSim Technologie offre des outils informatiques de cartographie pouvant afficher sur une page web des cartessur lesquelles viennent se greffer des géo-données telles que le réseau routier, une partition du territoire enzones (villes, secteurs, quartiers ...), la localisation de points d'intérêt (stationnement, bornes-fontaines ...) demême que les adresses civiques. Dans la version actuelle de leur produit, NSim Technologie peut calculer leplus court chemin entre deux points sur le réseau routier. Toutefois, ils ont un besoin croissant de calculer leplus court chemin passant par plusieurs points. Ce problème classique est connu sous le nom du commisvoyageur. Les adresses ne pouvant généralement pas être toutes visitées en une seule journée, ils désirentpartitionner les adresses de sorte qu'elles soient visitées par des véhicules différents ou à des jours différents.Dans les deux cas, on doit partitionner les adresses de sorte que les parcours reliant les adresses de chaquepartition soient de longueurs semblables. Finalement, selon l'application, certaines contraintes viendronts'ajouter au problème. Dans un problème de collecte et de livraison de colis, on peut vouloir imposer que deuxadresses soient visitées par le même véhicule et dans un ordre préétabli. Dans le cadre de ce projet, nousdévelopperons un logiciel capable de résoudre ce problème avec pour fonction objectif de minimiser le pluslong parcours. Nous utiliserons la programmation par contraintes pour faciliter la modélisation des différentesvariantes du problème et exploiter l'efficacité du branch & bound.