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

通过无时间松弛解决依赖时间的逻辑优化问题

• 批准号: 289354542
• 负责人: Professor Dr.-Ing. Uwe Clausen
• 金额: --
• 依托单位: Institut für Transportlogistik (ITL)
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2016
• 资助国家: 德国
• 起止时间: 2015-12-31 至 2021-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/289354542?language=en
• 关键词: Solution; time; dependent; logistic; optimization

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.

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