Exact and heuristic algorithms for vehicle routing

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

• 批准号: RGPIN-2017-05683
• 负责人: Desaulniers, Guy
• 金额: $ 3.72万
• 依托单位: École Polytechnique de Montréal
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=759408
• 关键词: 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）当无人机从移动的直升机上派遣以评估受灾地区不同区域的损坏程度时，在人道主义物流中出现的移动仓库的车辆路线问题。从科学的角度来看，本研究的结果是方法，将适用于各种各样的车辆路径问题在不同的运输方式，甚至在其他领域出现的某些问题。从商业角度来看，这些结果将有助于货运公司和人道主义后勤供应商更好地管理其车辆的使用，从而有助于提高加拿大公司的生产力，减少温室气体排放。最后，从学术的角度来看，本研究将提供财政支持和培训，三个博士，两个硕士和一个本科生，将在加拿大的优化软件开发公司完成学业后的需求。