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)在人道主义物流中出现的移动仓库的车辆路线问题，当无人机从移动直升机上派遣，以评估受灾地区不同区域的破坏程度时。从科学的角度来看，本研究的结果是方法论的，将适用于各种不同运输方式下的车辆路线问题，甚至适用于其他领域出现的某些问题。从商业角度来看，这些结果将有助于货运公司和人道主义物流供应商更好地管理其车辆的利用，因此将有助于提高加拿大公司的生产力并减少温室气体排放。最后，从学术角度来看，本研究将为三名博士，两名硕士和一名本科生提供资金支持和培训，这些学生在完成学业后将被加拿大优化软件开发公司所需要。