Collaborative Research: Robust Optimization of Rich Vehicle Routing Problems Under Uncertainty

协作研究：不确定性下丰富车辆路径问题的鲁棒优化

• 批准号: 1434682
• 负责人: Chrysanthos Gounaris
• 金额: $ 27.17万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2018-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1434682&HistoricalAwards=false
• 关键词: Collaborative; Research; Robust; Optimization; Rich

This project considers the utilization of a fleet of vehicles during freight and service delivery operations, and aims to enhance the ability to optimize such processes in view of operational uncertainty, such as uncertainty related to the transportation network (e.g., traffic conditions, road closings or vehicle break-downs), or uncertainty related to the delivery targets themselves (e.g., customer demands, time availabilities, or geographic locations). From a practical perspective, failure to take into account uncertainty when making operational decisions in this context may have significant economic and reputational repercussions for operators, as slight changes in operational conditions may lead even a carefully planned and "optimized" operation to become highly suboptimal or outright infeasible. Furthermore, efficient optimization and risk-management frameworks for vehicle routing operations, such as the one developed in this project, can benefit the environment by reducing unwanted side-effects of delivery systems such as traffic congestion and pollution emissions. In addressing this important issue, this project applies and advances the theoretical field of Robust Optimization (RO), which has emerged in the scientific literature as a promising framework to optimize mathematical models subject to parameter uncertainty. The project seeks to systematize the application of RO in the context of mathematical models used for the optimization of vehicle routing operations and to streamline the adoption of its theoretical and methodological innovations by practitioners. The project further impacts Education by providing training to graduate and undergraduate students on issues of freight and service delivery operations, optimization methods and algorithms, uncertainty quantification and analysis, and scientific computation, as well as enabling STEM outreach to K-12 students.This project aims to develop an optimization framework for the systematic treatment of uncertainty in rich Vehicle Routing Problems (VRPs). VRPs consider a fleet of vehicles and their optimal utilization in freight and service delivery operations. Rich VRP settings particularly account for complicated operational realities that are answered in practice. From a practical perspective, it is of interest to design freight and service delivery systems that take into account operational uncertainties, since failure to do so may lead to solutions that are infeasible or highly suboptimal. The project applies the Robust Optimization (RO) framework, which has not been considered much in the context of VRPs. The framework seeks to optimize the problem in view of a "worst-case" scenario, as dictated by an uncertainty set that is suitably selected to reflect the decision maker's tolerance for risk and ambiguity. An RO-based approach can be advantageous from a tractability viewpoint and does not require precise distributional knowledge. The expected methodological contributions include the development of (a) robust formulations, cutting planes, and efficient exact solution approaches, (b) robust feasibility checks and efficient metaheuristic solution approaches, and (c) associated uncertainty sets that are tractable, practically relevant, and easily tuned according to risk tolerance. Furthermore, we plan to compile comprehensive collections of new benchmark instances and computational performance profiles, which will help to stimulate research efforts in the area. Efficient rich-VRP optimization and risk-management frameworks, such as the one developed in this project, can have an important impact in the competitiveness, service quality and sustainability of companies that adopt them. Furthermore, they benefit the environment by reducing unwanted side-effects of delivery systems, such as traffic congestion and pollution emissions. The project will further impact Education via providing training to graduate and undergraduate students on issues of freight and service delivery operations, optimization methods and algorithms, uncertainty quantification and analysis, and scientific computation, as well as enabling STEM outreach to K-12 students.

该项目考虑在货运和服务交付业务中使用车队的问题，旨在提高在业务不确定性的情况下优化这些流程的能力，例如与运输网络有关的不确定性（例如，交通状况、道路封闭或车辆故障），或与递送目标本身相关的不确定性（例如，客户需求、时间可用性或地理位置）。从实践的角度来看，在这方面作出业务决定时不考虑不确定性可能会对运营商产生重大的经济和声誉影响，因为业务条件的微小变化可能导致即使是精心规划和“优化”的业务也变得非常不理想或完全不可行。 此外，有效的优化和风险管理框架的车辆路线操作，如本项目中开发的，可以通过减少不必要的副作用，如交通拥堵和污染排放的交付系统，有利于环境。 在解决这一重要问题时，该项目应用并推进了鲁棒优化（RO）的理论领域，该理论领域已在科学文献中作为一个有前途的框架出现，以优化参数不确定性的数学模型。该项目旨在系统化RO在用于优化车辆路线操作的数学模型中的应用，并简化从业者对其理论和方法创新的采用。该项目通过为研究生和本科生提供货运和服务交付操作、优化方法和算法、不确定性量化和分析以及科学计算等问题的培训，进一步影响教育，并使STEM推广到K-12学生。该项目旨在开发一个优化框架，用于系统处理丰富的车辆路径问题（VRP）中的不确定性。VRP考虑车队及其在货运和服务交付业务中的最佳利用。丰富的VRP设置特别考虑了在实践中回答的复杂操作现实。 从实际角度来看，设计考虑到业务不确定性的货运和服务提供系统是有意义的，因为不这样做可能导致不可行或非常不理想的解决方案。该项目应用了鲁棒优化（RO）框架，这在VRP的背景下没有得到太多的考虑。该框架旨在优化问题的“最坏情况”的情况下，所规定的不确定性集，适当选择，以反映决策者的风险和模糊性的容忍度。从易处理性的观点来看，基于RO的方法可以是有利的，并且不需要精确的分布知识。预期的方法学贡献包括：（a）制定稳健的公式、切割平面和有效的精确解方法;（B）制定稳健的可行性检查和有效的元启发式解方法;（c）制定易于处理、实际相关和易于根据风险承受能力调整的相关不确定性集。此外，我们计划编制新的基准实例和计算性能配置文件的全面集合，这将有助于刺激该领域的研究工作。高效的富VRP优化和风险管理框架，如本项目中开发的框架，可以对采用它们的公司的竞争力，服务质量和可持续性产生重要影响。此外，它们通过减少运输系统的有害副作用，如交通堵塞和污染排放，对环境有益。该项目将通过为研究生和本科生提供有关货运和服务交付运营、优化方法和算法、不确定性量化和分析以及科学计算等问题的培训，进一步影响教育，并使STEM能够推广到K-12学生。