带左时间窗口的网络流问题及其应用

项目名称： 带左时间窗口的网络流问题及其应用

项目编号： No.11301469

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 数理科学和化学

项目作者： 张同全

作者单位： 云南民族大学

项目金额： 22万元

中文摘要： 本项目将以组合最优化理论、近似算法理论、图论以及代数结构为工具来研究带左时间窗口的网络上的网络流问题及其在现代物流企业管理中的应用。本项目主持人已经根据城市与城市之间的交通班车发车情况这一实际背景首次定义了左时间窗口，并讨论了带左时间窗口的最短路[30]、带左时间窗口的树划分等问题，得到了一些初步的研究结果。在本项目中，我们将根据更现实的应用背景继续考虑带左时间窗口的其他组合最优化问题―网络流问题，分析它们的结构性质，在此基础上为之建立模型并设计求解方案，尤其是带左时间窗口的调度、装箱问题的复杂性分析、带左时间窗口的最大流、最小费用最大流、带左时间窗口的区域划分等问题。通过对本项目的研究将得到一系列的理论以及相关的应用成果，并且丰富了组合最优化、近似算法理论在现实生活中的应用。本项目将通过解决上述问题并发表10-20篇高质量的研究论文结题。

中文关键词： 左时间窗口；组合最优化；排序问题；广义度-和公式；狄拉克猜想

英文摘要： This project would study the network flow problems and their applications in the modern logistics charging with left-side time windows by using the following tools theory of combinatorial optimization,theory of approximation algorithm,graph theory and algebra construction.The compere of this project has defined left-side time windows based on the real backgrounds that the transport buses leave the platform cases among some cities,discussed the shortest path [30] and tree partition problems with left-side time windows,etc,obtained some element results. In this project,we would hold on researching other combinatorial optimization problems with left-side time windows-the network flow problems with left-side time windows which based on the realler backgrounds,analysis their construction properties,construct their models and design algorithms for them,especially,analyze of the NP-completeness for the scheduling and binpacking problem with left-side time windows,studies of the maximum flows and the minimum cost maximum flows problems with left-side time windows,the study of the logistics distribution region partition problem with left-side time windows etc.We would obtain some results of both theory and application fields from the researching of this project,and enrich the applications in the real world for both theo

英文关键词： Left-side time window；Combinatorial optimization；scheduling problem；generalized degree-sum formula；Dirac conjecture