Perspectives on integer programming for time-dependent models
Perspectives on integer programming for time-dependent models
复制标题
DOI：
10.1007/s11750-019-00514-4
复制
发表时间：
2019-05
期刊：
影响因子：
1.7
通讯作者：
N. Boland;M. Savelsbergh
中科院分区：
文献类型：
--
作者：
N. Boland;M. Savelsbergh
用于求解时间依赖模型的整数程序——必须对活动发生和/或资源被利用的时间做出决策的模型——在工业中普遍存在，但众所周知难以解决。在过去几年中，对离散化在解决这些问题的方法中的作用的兴趣已经加强。一个新的范例，动态离散化发现，已经出现了潜力，大大提高实际可追溯性的时间依赖模型使用整数规划技术。我们介绍了动态离散化发现，说明了它在带时间窗的旅行推销员问题上的应用，强调了它的核心原理，并指出了进一步研究的机会。还讨论了与处理时间依赖模型的其他方法的关系。
Integer programs for solving time-dependent models—models in which decisions have to be made about the times at which activities occur and/or resources are utilized—are pervasive in industry, but are notoriously difficult to solve. In the last few years, interest in the role of discretization in approaches to solve these problems has intensified. One novel paradigm, dynamic discretization discovery, has emerged with the potential to greatly enhance the practical tractability of time-dependent models using integer programming technology. We introduce dynamic discretization discovery, illustrate its use on the traveling salesman problem with time windows, highlight its core principles, and point to opportunities for further research. Relations to other approaches for tackling time-dependent models are also discussed.