带左时间窗口的组合最优化问题

针对带时间窗口的组合最优化结构在现实生活中的广泛用途以及已经引起了研究者的关注，并取得了一些研究成果，但是他们所讨论的时间窗口都有一个共同的特征：时间窗口的弹性不够强，即窗口一旦关闭，再也不会被打这一现状。该项目负责人在其博士学位论文中根据城市与城市之间的交通班车发车情况这一背景首次定义了左时间窗口，并讨论了带左时间窗口的最短路等问题，得到了一些初步的结果。在本项目中，我们将根据现实应用背景继续考虑带左时间窗口的其他组合最优化问题、为之建立模型并设计求解方案，尤其是带左时间窗口的中国邮递员问题的复杂性分析、带左时间窗口的最小费用最大流、带左时间窗口的加工排序等问题。对于此类问题，我们将首先分析它们的复杂性。若问题属于P类问题，我们将为它们设计计算复杂性较好的多项式时间算法；若问题属于NP-C问题类，我们将利用近似算法和计算复杂性理论这一工具为它们设计近似因子较好或时间复杂性较好的近似方案。