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 Softwares开发新算法，分别致力于邮政和公共交通公司。 在世界各地的邮政公司中，我们观察到随着电子商务出现的出现，可以增加包裹的数量。由于建筑邮递员领土（称为区域的过程）与邮件交付的案例有很大不同，因此需要新的算法来处理包裹交付区域。由于客户的随机存在，该计划问题很复杂，因此必须在领土之间平衡平均工作量，并且必须建立紧凑的领土。对于Georoute，我们的主要目标包括开发新算法，以有效地计算从头开始的邮递员领土以进行包裹的交付，并在需要时进行更新。在公共交通公司中，传统上通过解决一系列相互关联的问题（包括时间表，公共汽车调度，占空比计划和名册）来执行运营计划。在这个项目中，我们集成了其中的一些步骤，以提高整体计算解决方案的质量。特别是，我们为两个问题开发了最先进的解决方案算法：1-综合总线和旅行转移的责任调度问题，可以稍微更改某些公交旅行的时间表；和2-综合义务计划和名册。 这项研究将为加拿大带来一些好处。首先，一家加拿大拥有的私人公司Giro将增强其在全球范围内商业化的两种软件。其次，加拿大邮政和几家加拿大公共交通公司与Georoute或Hastus计划运营的加拿大公共交通公司将有能力获得改进的算法，这将帮助他们实现储蓄。最后，将在蒙特利尔和加拿大其他地区的优化公司中寻求专业化的四名研究生。