Integrating machine learning in combinatorial dynamic optimization for urban transportation services

该项目的目标是通过结合混合整数线性规划（MILP）和强化学习（RL）的优势，为随机动态拾取和交付问题提供有效的决策支持。随机动态取货问题在城市物流中发挥着越来越重要的作用。它们的特点是在城市中运送货物或乘客的时间往往很紧迫。常见的例子是当日送达、拼车和餐厅送餐。上述问题的共同点是，必须在每个决策步骤中解决具有未来不确定性的一系列决策问题，其中决策的全部价值仅在稍后的服务范围中显示。在子问题的组合决策空间中寻找有效可行的行程是求解一个复杂的MILP问题。鉴于未来的活力和不确定性，评估这种决定的有效性的挑战使这种复杂性成倍增加；一个理想的RL案例。两者对于完全满足操作要求都是至关重要的。因此，需要两种方法的直接结合。然而，由于各种原因，没有建立无缝集成，这是本研究项目的目的。我们建议使用强化学习来操纵MILP本身，以得出不仅高效而且有效的决策。这种操作可能会改变目标函数或约束。可以在目标函数中加入激励或惩罚条款，以强制或禁止某些决策的选择。或者，可以调整约束以保留舰队资源。挑战在于决定操纵发生的地点和方式。sdpdp在路由、车辆容量或时间窗口方面有限制。有些约束可能与舰队的灵活性无关，而另一些约束可能具有约束力。研究项目的第一部分侧重于通过（无）监督学习识别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.