Integrating machine learning in combinatorial dynamic optimization for urban transportation services

该项目的目标是结合混合整数线性规划(MILP)和强化学习(RL)的优点，为随机动态收发问题提供有效的决策支持。随机动态收发问题在城市物流中发挥着越来越重要的作用。它们的特点是城市中的货物或乘客的运输往往是时间紧迫的。常见的例子是当天送货、拼车和餐馆送餐。上述问题的共同点是，必须在每个决策步骤中解决一系列具有未来不确定性的决策问题，其中决策的全部价值在服务范围内稍后才会显现。搜索子问题的组合决策空间以寻找有效可行的路径是求解MILP问题的一项复杂任务。鉴于未来的活力和不确定性，这种复杂性现在被评估这种决定的有效性的挑战所放大；这是RL的理想情况。两者都是完全满足业务要求的关键。因此，需要将这两种方法直接结合起来。然而，由于种种原因，无缝集成并没有建立起来，这也是本研究项目的目的所在。我们建议使用RL来操纵MILP本身，以不仅得出有效的决策，而且还得出有效的决策。这种操作可以改变目标函数或约束条件。可以在目标函数中添加激励或惩罚条款，以强制或禁止选择某些决策。或者，这些限制可能会被调整以储备舰队资源。挑战是决定操纵发生在哪里以及如何发生。SDPPS在路线、车辆能力或时间窗口方面有限制。一些限制可能与船队的灵活性无关，而其他限制可能具有约束力。研究项目的第一部分集中于通过(无)监督学习来识别MILP中的“有趣”部分。一旦确定了“有趣的”部分，第二个挑战就是找到正确的参数化。在这里，我们将应用RL方法来学习MILP组件的状态相关操作。

The goal of this project is to provide effective decision support for stochastic dynamic pickup and delivery problems by combining the strengths of mixed-integer linear programming (MILP) and reinforcement learning (RL).Stochastic dynamic pickup-and-delivery problems play an increasingly important role in urban logistics. They are characterized by the often time-critical transport of wares or passengers in the city. Common examples are same-day delivery, ridesharing, and restaurant meal delivery. The mentioned problems have in common that a sequence of decision problems with future uncertainty must be solved in every decision step where the full value of a decision reveals only later in the service horizon. Searching the combinatorial decision space of the subproblems for efficient and feasible tours is a complex task of solving a MILP. This complexity is now multiplied by the challenge of evaluating such decision with respect to their effectiveness given future dynamism and uncertainty; an ideal case for RL. Both are crucial to fully meet operational requirements. Therefore, a direct combination of both methods is needed. Yet, a seamless integration has not been established due to different reasons and is the aim of this research project. We suggest using RL to manipulate the MILP itself to derive not only efficient but also effective decisions. This manipulation may change the objective function or the constraints. Incentive or penalty terms can be added to the objective function to enforce or prohibit the selection of certain decisions. Alternatively, the constraints may be adapted to reserve fleet-resources.The challenge is to decide where and how the manipulation takes place. SDPDPs have constraints with respect to routing, vehicle capacities, or time windows. Some constraints may be irrelevant for the fleet’s flexibility while others might be binding. The first part of the research project focuses on identifying the “interesting” parts of the MILP via (un-)supervised learning. Once the “interesting” parts are identified, the second challenge is to find the right parametrization. Here, we will apply RL methods to learn the state-dependent manipulation of the MILP components.