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

点击翻译按钮获取中文摘要

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.