Grant: Collaborative Research and Development Grants
École Polytechnique de Montréal
$42,000.00
Postman districting and bus driver scheduling
EF 2016-17
Résumé
Giro Inc. is a world leader in the development and commercialization of optimization-based softwares for planning the operations of postal agencies and public transport companies. This research project aims at developing new algorithms for Giro's GeoRoute and Hastus softwares dedicated to postal and public transport companies, respectively. In postal companies around the world, we observe an increase in the number of parcels to deliver with the advent of e-commerce. Because building postman territories (a process called districting) for parcel delivery differs significantly from the case for mail delivery, new algorithms are required to deal with parcel delivery districting. This planning problem is complex because of the stochastic presence of the customers, the average workload must be balanced between the territories, and compact territories must be build. For GeoRoute, our main objective consists of developing new algorithms to efficiently compute from scratch postman territories for parcel delivery, and also to update them when needed. In public transport companies, operations planning has traditionally been performed by solving a sequence of interrelated problems, including timetabling, bus scheduling, duty scheduling, and rostering. In this project, we integrate some of these steps to improve the quality of the overall computed solutions. In particular, we develop state-of-the-art solution algorithms for two problems: 1- Integrated bus and duty scheduling problem with trip shifting that allows to slightly change the schedule of certain bus trips; and 2- Integrated duty scheduling and rostering. This research will yield several benefits to Canada. First, a canadian-owned private company, Giro, will enhance two of its softwares that are commercialized worldwide. Second, Canada Post and several canadian public transport companies that plan their operations with either GeoRoute or Hastus will have access to improved algorithms that will help them realized savings. Finally, four graduate students whose specialization is often sought in optimization-based companies in Montreal and elsewhere in Canada will be trained.
Programme
Collaborative Research and Development Grants
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
463433-2014
Name nom
Desaulniers, Guy
Department département
Mathématiques et génie industriel
Organization id
64
Institution établissement
École Polytechnique de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2014
Award amount
42000
Program id
CRDPJ
Program name en
Collaborative Research and Development Grants
Program name fr
Subventions de recherche et développement coopérative
Group en
Research partnerships programs
Group fr
Programmes de partenariat
Committee code
96
Committee name en
RPP Internal Decision Cttee
Committee name fr
Cté de décision interne - PPR
Area of application code
700
Area of application group en
Transportation systems and services
Area of application group fr
Services et systèmes de transport
Area of application en
Transportation systems and services
Area of application fr
Services et systèmes de transport
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
3
Nb partie
3
Application title
Postman districting and bus driver scheduling
Keyword
NSERC
Application summary
Giro Inc. is a world leader in the development and commercialization of optimization-based softwares for planning the operations of postal agencies and public transport companies. This research project aims at developing new algorithms for Giro's GeoRoute and Hastus softwares dedicated to postal and public transport companies, respectively. In postal companies around the world, we observe an increase in the number of parcels to deliver with the advent of e-commerce. Because building postman territories (a process called districting) for parcel delivery differs significantly from the case for mail delivery, new algorithms are required to deal with parcel delivery districting. This planning problem is complex because of the stochastic presence of the customers, the average workload must be balanced between the territories, and compact territories must be build. For GeoRoute, our main objective consists of developing new algorithms to efficiently compute from scratch postman territories for parcel delivery, and also to update them when needed. In public transport companies, operations planning has traditionally been performed by solving a sequence of interrelated problems, including timetabling, bus scheduling, duty scheduling, and rostering. In this project, we integrate some of these steps to improve the quality of the overall computed solutions. In particular, we develop state-of-the-art solution algorithms for two problems: 1- Integrated bus and duty scheduling problem with trip shifting that allows to slightly change the schedule of certain bus trips; and 2- Integrated duty scheduling and rostering. This research will yield several benefits to Canada. First, a canadian-owned private company, Giro, will enhance two of its softwares that are commercialized worldwide. Second, Canada Post and several canadian public transport companies that plan their operations with either GeoRoute or Hastus will have access to improved algorithms that will help them realized savings. Finally, four graduate students whose specialization is often sought in optimization-based companies in Montreal and elsewhere in Canada will be trained.