Heuristic approaches for the solution of high-dimensional stochastic routing and scheduling problems

运筹学中的许多问题都可以在网络流或路径优化的基础上得到分析和很好的解决。然而，随机因素在网络问题中占有很大的比重，而目前的研究往往没有考虑这些因素。实际上，在解决有限资源必须以最优方式分配的实际问题时，需要充分考虑整个过程的不确定性，特别是根据最新可用信息在不同点及时做出一系列决策。换句话说，它可以被定义为可以用马尔可夫决策过程（MDP）表示的动态问题，但状态空间可能是高维的，我们可能需要彻底考虑近似动态规划（DP）或强化学习等方法。总之，我们的目标是为这些问题设计有效的算法，并证明它们比可能考虑的替代方案表现得更好。

Many problems can be analysed and well solved on the basis of optimising flows or routes in networks involved in operations research (OR). However, stochastic factors largely take a major part in network problems, which are not always considered in nowadays research. Actually, when solving practical problems in which limited resources must be distributed in an optimal way, uncertainty across the whole process and making a series of decisions at different points timely according to the latest available information in particular need to be fully taken into consideration. In other words, it can be defined as dynamic problems that can be formulated as a Markov decision process (MDP), but the state space may be high-dimensional and we likely need to consider approaches such as approximate dynamic programming (DP) or reinforcement learning thoroughly. In conclusion, we aim to devise efficient heuristics for these kinds of problems and demonstrate that they perform better than alternatives that might be considered.