Exact and heuristic algorithms for vehicle routing

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

基本信息

  • 批准号:
    RGPIN-2017-05683
  • 负责人:
  • 金额:
    $ 3.72万
  • 依托单位:
  • 依托单位国家:
    加拿大
  • 项目类别:
    Discovery Grants Program - Individual
  • 财政年份:
    2022
  • 资助国家:
    加拿大
  • 起止时间:
    2022-01-01 至 2023-12-31
  • 项目状态:
    已结题

项目摘要

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

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Desaulniers, Guy其他文献

Employee scheduling with short demand perturbations and extensible shifts
A two-stage solution approach for personalized multi-department multi-day shift scheduling
  • DOI:
    10.1016/j.ejor.2019.07.068
  • 发表时间:
    2020-02-01
  • 期刊:
  • 影响因子:
    6.4
  • 作者:
    Dahmen, Sana;Rekik, Monia;Desaulniers, Guy
  • 通讯作者:
    Desaulniers, Guy
Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows
  • DOI:
    10.1287/opre.2016.1535
  • 发表时间:
    2016-11-01
  • 期刊:
  • 影响因子:
    2.7
  • 作者:
    Desaulniers, Guy;Errico, Fausto;Schneider, Michael
  • 通讯作者:
    Schneider, Michael
A two-phase mathematical-programming heuristic for flexible assignment of activities and tasks to work shifts
  • DOI:
    10.1007/s10951-013-0324-2
  • 发表时间:
    2013-10-01
  • 期刊:
  • 影响因子:
    2
  • 作者:
    Elahipanah, Mahsa;Desaulniers, Guy;Lacasse-Guay, Eve
  • 通讯作者:
    Lacasse-Guay, Eve
Branch-price-and-cut algorithms for the pickup and delivery problem with time windows and multiple stacks
  • DOI:
    10.1016/j.ejor.2015.10.046
  • 发表时间:
    2016-05-01
  • 期刊:
  • 影响因子:
    6.4
  • 作者:
    Cherkesly, Marilene;Desaulniers, Guy;Laporte, Gilbert
  • 通讯作者:
    Laporte, Gilbert

Desaulniers, Guy的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Desaulniers, Guy', 18)}}的其他基金

Exact and heuristic algorithms for vehicle routing
用于车辆路线的精确启发式算法
  • 批准号:
    RGPIN-2017-05683
  • 财政年份:
    2021
  • 资助金额:
    $ 3.72万
  • 项目类别:
    Discovery Grants Program - Individual
Exact and heuristic algorithms for vehicle routing
用于车辆路线的精确启发式算法
  • 批准号:
    RGPIN-2017-05683
  • 财政年份:
    2020
  • 资助金额:
    $ 3.72万
  • 项目类别:
    Discovery Grants Program - Individual
Advanced data-driven optimization tools for public transit scheduling and parcel delivery
用于公共交通调度和包裹递送的先进数据驱动优化工具
  • 批准号:
    520349-2017
  • 财政年份:
    2019
  • 资助金额:
    $ 3.72万
  • 项目类别:
    Collaborative Research and Development Grants
Exact and heuristic algorithms for vehicle routing
用于车辆路线的精确启发式算法
  • 批准号:
    RGPIN-2017-05683
  • 财政年份:
    2019
  • 资助金额:
    $ 3.72万
  • 项目类别:
    Discovery Grants Program - Individual
Fast optimization algorithms for complex personnel scheduling problems
复杂人员调度问题的快速优化算法
  • 批准号:
    530544-2018
  • 财政年份:
    2019
  • 资助金额:
    $ 3.72万
  • 项目类别:
    Collaborative Research and Development Grants
Exact and heuristic algorithms for vehicle routing
用于车辆路线的精确启发式算法
  • 批准号:
    RGPIN-2017-05683
  • 财政年份:
    2018
  • 资助金额:
    $ 3.72万
  • 项目类别:
    Discovery Grants Program - Individual
Exact and heuristic algorithms for vehicle routing
用于车辆路线的精确启发式算法
  • 批准号:
    RGPIN-2017-05683
  • 财政年份:
    2017
  • 资助金额:
    $ 3.72万
  • 项目类别:
    Discovery Grants Program - Individual
Optimization methods for complex personnel shift scheduling problems
复杂人员排班问题的优化方法
  • 批准号:
    468716-2014
  • 财政年份:
    2016
  • 资助金额:
    $ 3.72万
  • 项目类别:
    Collaborative Research and Development Grants
Exact and heuristic solution methods for time-constrained vehicle routing
时间受限车辆路径的精确启发式求解方法
  • 批准号:
    157935-2012
  • 财政年份:
    2016
  • 资助金额:
    $ 3.72万
  • 项目类别:
    Discovery Grants Program - Individual
Postman districting and bus driver scheduling
邮递员分区和公交车司机调度
  • 批准号:
    463433-2014
  • 财政年份:
    2015
  • 资助金额:
    $ 3.72万
  • 项目类别:
    Collaborative Research and Development Grants

相似国自然基金

基于Hyper-heuristic的纳米芯片设计关键算法研究
  • 批准号:
    61071024
  • 批准年份:
    2010
  • 资助金额:
    36.0 万元
  • 项目类别:
    面上项目
基于DDM的第四方物流风险管理决策机制的研究
  • 批准号:
    71071028
  • 批准年份:
    2010
  • 资助金额:
    28.0 万元
  • 项目类别:
    面上项目
密码学中概率与组合方法
  • 批准号:
    10601032
  • 批准年份:
    2006
  • 资助金额:
    16.0 万元
  • 项目类别:
    青年科学基金项目

相似海外基金

Exact and heuristic algorithms for vehicle routing
用于车辆路线的精确启发式算法
  • 批准号:
    RGPIN-2017-05683
  • 财政年份:
    2021
  • 资助金额:
    $ 3.72万
  • 项目类别:
    Discovery Grants Program - Individual
Exact and heuristic algorithms for vehicle routing
用于车辆路线的精确启发式算法
  • 批准号:
    RGPIN-2017-05683
  • 财政年份:
    2020
  • 资助金额:
    $ 3.72万
  • 项目类别:
    Discovery Grants Program - Individual
Performance Analysis of Heuristic Optimization Algorithms for Multi-Sensor Resource Management
多传感器资源管理启发式优化算法的性能分析
  • 批准号:
    552566-2020
  • 财政年份:
    2020
  • 资助金额:
    $ 3.72万
  • 项目类别:
    University Undergraduate Student Research Awards
Exact and heuristic algorithms for vehicle routing
用于车辆路线的精确启发式算法
  • 批准号:
    RGPIN-2017-05683
  • 财政年份:
    2019
  • 资助金额:
    $ 3.72万
  • 项目类别:
    Discovery Grants Program - Individual
Exact and heuristic algorithms for vehicle routing
用于车辆路线的精确启发式算法
  • 批准号:
    RGPIN-2017-05683
  • 财政年份:
    2018
  • 资助金额:
    $ 3.72万
  • 项目类别:
    Discovery Grants Program - Individual
Parallel Search Algorithms for Heterogeneous Computing Environments
异构计算环境的并行搜索算法
  • 批准号:
    17K00296
  • 财政年份:
    2017
  • 资助金额:
    $ 3.72万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Exact and heuristic algorithms for vehicle routing
用于车辆路线的精确启发式算法
  • 批准号:
    RGPIN-2017-05683
  • 财政年份:
    2017
  • 资助金额:
    $ 3.72万
  • 项目类别:
    Discovery Grants Program - Individual
RI: Small: Heuristic Search Algorithms for Probabilistic Graphical Models
RI:小:概率图形模型的启发式搜索算法
  • 批准号:
    1526842
  • 财政年份:
    2015
  • 资助金额:
    $ 3.72万
  • 项目类别:
    Standard Grant
Computing width parameters of graphs: theory of commitments and development of practical algorithms
计算图的宽度参数:承诺理论和实用算法的开发
  • 批准号:
    26330021
  • 财政年份:
    2014
  • 资助金额:
    $ 3.72万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Parabola Research - Research and Development of Heuristic Algorithms for High Efficiency Video Coding
Parabola Research - 高效率视频编码启发式算法的研究与开发
  • 批准号:
    710330
  • 财政年份:
    2013
  • 资助金额:
    $ 3.72万
  • 项目类别:
    GRD Proof of Concept
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了