Constraint Programming Approaches to Integrated Scheduling and Transportation Problems

综合调度和运输问题的约束规划方法

• 批准号: RGPIN-2014-03968
• 负责人: Rousseau, LouisMartin
• 金额: $ 3.28万
• 依托单位: École Polytechnique de Montréal
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=610752
• 关键词: Constraint; Programming; Approaches; Integrated; Scheduling

It is common in the service industry for managers in different departments, using different tools, to solve planning problems in silos. Each of them concentrates on one piece of the puzzle, often ignoring the global picture. This behaviour is seen in large retail companies where human resources, inventory movement, and transportation are planned separately; healthcare organizations where the schedules for physicians, nurses, rooms, and patients are assembled by different people; and transportation networks where the opportunity for backhauling during operations is often lost because of myopic tactical planning. Moreover, new mobile technology is changing the business paradigm of many of these organizations. Multi-channel retailing is becoming increasingly important as more and more customers order online. Data collected in real time will soon allow many different organizations (such as public transit firms) to react instantly to changing trends and to adapt their offers accordingly. In healthcare, personalized medicine is knocking at the door. The challenges that lie ahead are thus numerous: i) Given the tremendous amounts of data that will be available, appropriate system performance measures will need to be developed and handled by optimization engines; ii) decision problems will need to be more integrated along the time line, e.g., strategic and tactical plans will need to take into account operational constraints and foresee real-time adjustments; iii) decision models will need to account for uncertainty because the available data can be incomplete or inaccurate. To tackle these challenges, the proposed research program will develop new methodology, built around rich combinatorial structures and their use within operations research methods, to solve large, integrated, and stochastic decision problems. I will target personnel scheduling, the planning and scheduling of transportation, and healthcare logistics. We have already developed methodology for complex and integrated personnel scheduling problems. These approaches will be extended by the development of new techniques that capture more complex contexts and thus allow us to integrate different decision problems. Finally, the rich internal structures will be able to capture the combined probability distribution of a series of events, and thus we will be able to use these techniques within a stochastic programming approach. We will base our methodological development on constraint programming, which we have found to be useful for many mixed integer nonlinear problems. I want to investigate this approach further to take advantage of its strong inference mechanism and to develop “learning during search” methods for difficult nonlinear problems, such as those where the objective function is obtained through data mining. The novelty of this proposal thus lies in the use of rich combinatorial structures in flexible constraint programming approaches. These new techniques will allow us to integrate different optimization problems that are part of the same global decision process, while taking into account uncertainty and real-time decision-making.

在服务行业中，不同部门的经理使用不同的工具来解决竖井中的计划问题是很常见的。他们中的每一个人都专注于拼图的一部分，往往忽视了全球图景。 这种行为见于大型零售公司，其中人力资源、库存移动和运输分别进行规划；医疗保健组织，医生、护士、房间和患者的时间表由不同的人组合；以及运输网络，在操作过程中，由于目光短浅的战术规划，经常失去回程的机会。此外，新的移动技术正在改变其中许多组织的业务模式。随着越来越多的客户在网上订购，多渠道零售正变得越来越重要。实时收集的数据将很快使许多不同的组织(如公共交通公司)能够立即对不断变化的趋势做出反应，并相应地调整他们的报价。在医疗保健领域，个性化医疗正在敲响大门。 因此，摆在面前的挑战是众多的：i)鉴于将会有大量的数据可用，适当的系统性能测量将需要由优化引擎来开发和处理；ii)决策问题将需要在时间线上更加综合，例如，战略和战术计划将需要考虑到业务限制并预见实时调整；iii)决策模型将需要考虑不确定性，因为可用数据可能不完整或不准确。为了应对这些挑战，拟议的研究计划将开发新的方法，围绕丰富的组合结构及其在运筹学方法中的使用，来解决大型、综合和随机决策问题。我的目标是人员调度、运输的规划和调度以及医疗保健物流。 我们已经为复杂和综合的人员调度问题开发了方法。这些方法将通过开发新的技术来扩展，这些技术捕获更复杂的背景，从而使我们能够整合不同的决策问题。最后，丰富的内部结构将能够捕获一系列事件的组合概率分布，因此我们将能够在随机编程方法中使用这些技术。 我们的方法论发展将建立在约束规划的基础上，我们已经发现约束规划对许多混合整数非线性问题很有用。我想进一步研究这种方法，以利用其强大的推理机制，并为困难的非线性问题(例如目标函数是通过数据挖掘获得的问题)开发“在搜索中学习”的方法。 因此，这一建议的新颖之处在于在灵活的约束规划方法中使用了丰富的组合结构。这些新技术将使我们能够整合不同的优化问题，这些问题是同一全球决策过程的一部分，同时考虑到不确定性和实时决策。