Solution of time-dependent logistic optimization problems via time-free relaxations

物流中的优化问题通常包含一个时间依赖的组件。在最简单的情况下，这是运输货物或车辆的最早和最晚到达时间。更复杂的应用程序涉及两个或多个进程的时间同步或遵守优先关系（“首先...在那之后... ").目标是最小化或最大化某个目标函数，服从这些条件。这样的优化问题通常可以表述为混合整数规划。作为计算数值解的一种可能的方法，可以开发出在短时间内生成可行解的算法。然而，它们并没有带来全局最优性的证明。为了显示这些解决方案的最优性，人们可以求助于分支定界切割方法，该方法基本上基于混合整数公式的线性规划松弛。虽然这种方法在许多问题上都很有效--最突出的可能是旅行推销员问题--但在许多情况下，当时间方面与离散决策必须耦合时，它在某种程度上受到限制。流行的建模技术使用Big-M公式，其中连续时间变量通过线性不等式与二元决策变量相关联。另一种类似的流行技术使用时间扩展图，其中时间被离散化，从而嵌入到底层图的组合结构中。这两种技术都有各自的问题：大M公式可能导致弱松弛，其中整数最优解的目标函数值和连续松弛相距甚远。使用时间扩展图可能会导致非常大的问题实例（就变量和约束的数量而言），这些问题不再是当前计算机技术所能管理的。新的方法，我们的目标是开发和测试在这个研究项目中，是从一个时间相关的模型的逻辑优化问题，并将其转换成一个无时间的松弛模型的时间相关的部分被忽略的投影模型到一个低维子空间。这种松弛仍然是一个混合整数问题，更容易解决数值。然而，一般而言，这一解决方案在时间方面不一定可行。因此，只有在发生时间冲突的那些部分，问题的时间条件才必须逐步重新纳入提法。我们为此开发了各种基于切割平面和分支策略的技术。我们还开发了具体的算法，试图将不可行的时间无关的解决方案，在可行的时间相关的解决方案。这两种策略，精确和启发式，将被集成到一个整体解决方案，并使用选定的物流问题类进行测试。

Optimization problems in logistics often contain a time-dependent component. In the simplest case this are earliest and latest arrival times of transported goods or vehicles. More complex applications involve the temporal synchronization of two or more processes or a compliance with precedence relationships ("at first... after that..."). The goal is to minimize or maximize a certain objective function, subject to such conditions. Such optimization problems can often be formulated as mixed-integer programs. As one possible method for the calculation of numerical solutions, heuristics can be developed that generate feasible solutions in short time. However, no certificate of global optimality comes with them. In order to show the optimality of these solutions, one can resort to branch-and-bound-and-cut methods, which are based essentially on linear programming relaxations of the mixed-integer formulation. Although this approach worked well for a number of problems - most prominently perhaps for the traveling salesman problem - it is somehow limited in many cases when temporal aspects with discrete decisions must be coupled. The popular modeling techniques use either a Big-M formulation, where a continuous time variable is linked to a binary decision variable by linear inequalities. Another similarly popular technique uses time-expanded graphs, in which the time is discretized and thus embedded in the combinatorial structure of the underlying graph. Both techniques have their individual problems: the Big-M formulation can lead to weak relaxations, in which the objective function value of the integer optimal solution and the continuous relaxation are far apart. Using time-expanded graphs can lead to very large problem instances (in terms of number of variables and constraints) that are no longer manageable with the current computer technology. The new approach, which we aim to develop and test in this research project, is to starting with a time-dependent model of a logistic optimization problem, and transform it into a time-free relaxation by which the time-dependent parts of the models are neglected by projection of the model into a lower-dimensional subspace. This relaxation is still a mixed-integer problem that is much easier solved numerically. In general, this solution is, however, not necessarily feasible with respect to the temporal aspects. Hence the temporal conditions of the problem must be gradually reintegrated in the formulation only at those parts where temporal conflicts occur. We develop various techniques for this purpose which are based on cutting planes and branching strategies. We also develop specific heuristics that attempt to transform infeasible time-free solutions in feasible time-dependent solutions. Both strategies, the exact and the heuristic, will be integrated into an overall solver and tested using selected classes of logistic problems.