Exact and heuristic solution methods for time-constrained vehicle routing

时间受限车辆路径的精确启发式求解方法

• 批准号: 157935-2012
• 负责人: Desaulniers, Guy
• 金额: $ 3.42万
• 依托单位: École Polytechnique de Montréal
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2012
• 资助国家: 加拿大
• 起止时间: 2012-01-01 至 2013-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=513848
• 关键词: Exact; heuristic; solution; methods; time

Time-constrained vehicle routing problems consist of determining least-cost vehicle routes to cover a set of tasks such that each task is executed within a predefined time window and vehicle capacity is respected for each route. Several problem variants exist, arising from different applications in freight transportation. In this proposal, we develop mathematical optimization models and methods to help the planners in determining the best possible vehicle routes. The optimization methods can be classified into two categories: an exact method seeks an optimal solution and can require substantial computational time; a heuristic method is much faster but provides a good-quality solution that may not be optimal. We explore three research directions for exact methods and one for heuristics. Furthermore, we develop optimization methods for two specific vehicle routing problems: the split delivery vehicle routing problem with time windows and synchronization constraints that allows multiple visits to each customer if they occur simultaneously; and the pickup and delivery vehicle routing problem with time windows and last-in, first-out constraints that consists of picking up merchandise at customers to deliver it at specific locations in the reverse order of the corresponding pickup operations. From a scientific point of view, the results of this research are rather methodological and will be applicable to a wide variety of vehicle routing problems in different mode of transportation and even to certain problems arising in other domains. From a commercial point of view, these results will help the freight companies to better manage the utilization of their vehicles and will therefore contribute to increase the productivity of Canadian companies. Finally, from an academic point of view, this research will provide financial support and training to three PhD students and two MSc students that will be in demand by the Canadian optimization software development companies after completing their studies.

时间约束的车辆路径问题包括确定最低成本的车辆路线，以覆盖一组任务，使每个任务在预定义的时间窗口内执行，并尊重车辆容量为每个路线。由于货物运输中的不同应用，存在几种不同的问题。在这个建议中，我们开发了数学优化模型和方法，以帮助规划人员确定最佳的车辆路线。优化方法可以分为两类：精确方法寻求最佳解决方案，可能需要大量的计算时间;启发式方法快得多，但提供了可能不是最佳的高质量解决方案。我们探索了精确方法的三个研究方向和启发式方法的一个研究方向。此外，我们开发了两个具体的车辆路径问题的优化方法：分裂交付车辆路径问题的时间窗口和同步约束，允许多个访问每个客户，如果他们同时发生;以及带时间窗和后进的配送车辆路径问题，先出约束，包括在客户处拾取商品，以按照相应拾取操作的相反顺序将其递送到特定位置。从科学的角度来看，本研究的结果是相当的方法，将适用于各种各样的车辆路径问题在不同的运输方式，甚至在其他领域出现的某些问题。从商业角度来看，这些结果将有助于货运公司更好地管理其车辆的使用，从而有助于提高加拿大公司的生产力。最后，从学术的角度来看，本研究将提供财政支持和培训，三个博士生和两个硕士生，将在加拿大的优化软件开发公司完成学业后的需求。