Exact and heuristic algorithms for vehicle routing

用于车辆路线的精确启发式算法

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

Vehicle routing problems consist of determining least-cost vehicle routes to perform a set of tasks while respecting operational constraints, such as vehicle capacity and service time windows at the customers. Several problem variants exist, arising from different applications in, e.g., freight transportation and humanitarian logistics. In this proposal, we develop mathematical optimization models and methods, called branch-price-and-cut methods, to help the planners determine 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 four research directions for exact methods and one for heuristics. In particular, we aim at integrating machine learning algorithms developed in artificial intelligence into branch-price-and-cut algorithms that are widely used for vehicle routing. Furthermore, we develop optimization methods for two specific vehicle routing problems: 1) the simultaneous pickup and delivery problem with time windows and a load fragility constraint that forbids stacking heavy items over light ones and 2) the vehicle routing problem with a moving depot that arises in humanitarian logistics when drones are dispatched from a moving helicopter to assess the extent of damage in different zones of a devastated area. From a scientific point of view, the results of this research are methodological and will be applicable to a wide variety of vehicle routing problems in different modes of transportation and even to certain problems arising in other domains. From a commercial point of view, these results will help the freight companies and the humanitarian logistic providers to better manage the utilization of their vehicles and will therefore contribute to increase the productivity of Canadian companies and reduce greenhouse gas emissions. Finally, from an academic point of view, this research will provide financial support and training to three PhD, two MSc and one undergraduate students that will be in demand by the Canadian optimization software development companies after completing their studies.

车辆路径问题包括确定执行一组任务的成本最低的车辆路线，同时考虑运营约束，如车辆容量和客户的服务时间窗口。由于在货运和人道主义物流等领域的不同应用，存在若干问题变体。在这个方案中，我们开发了数学优化模型和方法，称为分支定价和切割法，以帮助规划者确定可能的最佳车辆路线。优化方法可以分为两类：精确方法寻求最优解，可能需要大量的计算时间；启发式方法速度快得多，但提供的解质量好，可能不是最优解。我们探索了精确方法的四个研究方向和启发式方法的一个研究方向。特别是，我们的目标是将人工智能中开发的机器学习算法整合到广泛用于车辆路径的分支定价和切割算法中。此外，我们还开发了两个具体的车辆路径问题的优化方法：1)带时间窗的同时取货和配送问题，以及禁止堆放重物而不是轻物的负载脆弱性约束问题；2)人道主义物流中出现的具有移动仓库的车辆路径问题，当从移动的直升机上派遣无人机来评估受灾地区不同区域的破坏程度时。从科学的角度来看，本研究的结果是方法论的，将适用于不同运输方式下的各种车辆路径问题，甚至适用于其他领域中出现的某些问题。从商业角度来看，这些成果将有助于货运公司和人道主义物流供应商更好地管理其车辆的使用，因此将有助于提高加拿大公司的生产率和减少温室气体排放。最后，从学术角度来看，本研究将为加拿大优化软件开发公司在完成学业后需要的三名博士、两名硕士和一名本科生提供资金支持和培训。