Postman districting and bus driver scheduling

点击翻译按钮获取中文摘要

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.