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