Integrating machine learning in combinatorial dynamic optimization for urban transportation services

随机动态取货配送问题在城市物流中发挥着越来越重要的作用，本文结合混合整数线性规划（MILP）和强化学习（RL）的优势，为随机动态取货配送问题提供有效的决策支持。它们的特点是在城市中运送货物或乘客的时间往往很紧迫。常见的例子是当天交付，拼车和餐厅送餐。上述问题的共同之处在于，在每个决策步骤中必须解决一系列具有未来不确定性的决策问题，其中决策的全部价值仅在服务范围的后期才能揭示。在子问题的组合决策空间中寻找有效可行的图尔斯是求解MILP的一项复杂任务。这种复杂性现在被评估这种决策的有效性的挑战所倍增，因为它们具有未来的动态性和不确定性;这是RL的理想情况。这两者对于充分满足业务要求都至关重要。因此，需要将这两种方法直接结合起来。然而，由于各种原因，无缝集成尚未建立，这是本研究项目的目标。我们建议使用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.