Postman districting and bus driver scheduling

邮递员分区和公交车司机调度

• 批准号: 463433-2014
• 负责人: Desaulniers, Guy
• 金额: $ 3.06万
• 依托单位: École Polytechnique de Montréal
• 依托单位国家: 加拿大
• 项目类别: Collaborative Research and Development Grants
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=577065
• 关键词: Postman; districting; 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.

Giro Inc.是开发和商业化用于规划邮政机构和公共交通公司运营的基于优化的软件的世界领先者。这项研究项目旨在为Giro的GeoRoute和Hastus软件开发新的算法，这些软件分别专用于邮政和公共交通公司。 在世界各地的邮政公司中，我们观察到随着电子商务的到来，要递送的包裹数量有所增加。由于为包裹递送建立邮递员区域(称为分区的过程)与邮件递送的情况有很大不同，因此需要新的算法来处理包裹递送分区。这个规划问题是复杂的，因为客户的随机存在，平均工作量必须在区域之间平衡，并且必须建立紧凑的区域。对于GeoRoute，我们的主要目标是开发新的算法，以便从零开始高效地计算包裹递送的邮递员地区，并在需要时进行更新。在公共交通公司，运营计划传统上是通过解决一系列相互关联的问题来执行的，包括时刻表、公交车调度、值班和排班。在这个项目中，我们集成了其中的一些步骤来提高整体计算解决方案的质量。特别是，我们为两个问题开发了最先进的解决算法：1-集成公交车和班次调度问题，允许轻微改变某些公交车出行的调度；2-集成值班调度和排班。 这项研究将给加拿大带来几个好处。首先，加拿大拥有的私人公司Giro将对其在全球范围内商业化的两款软件进行升级。其次，加拿大邮政和几家计划使用GeoRoute或Hastus运营的加拿大公共交通公司将获得改进的算法，这将帮助他们实现节省。最后，四名研究生将接受培训，他们的专业经常在蒙特利尔和加拿大其他地方的优化公司寻求。