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

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 theory of combinatorial optimization and theory of approximation algorithm.This project would be concluded by solving the above problems and publishing 10-20 high quality papers.

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

本项目以组合最优化理论、近似算法理论、图论、代数结构以及组合几何为工具来研究带左时间窗口的网络上的优化问题及其在现代企业管理中的应用。根据更现实的应用背景考虑了带左时间窗口的其他组合最优化问题―排序问题，分析它们的结构性质，在此基础上为之建立模型并设计求解方案，尤其是带时间窗口的单机同工件排序问题、带时间窗口的单机工件排序问题、带时间窗口的平行机工件排序问题、几何网络优化问题。通过本项目的研究得到了一系列的理论以及相关的应用成果，并且丰富了组合最优化、近似算法理论在现实生活中的应用。到目前为止，本项目在解决上述问题的过程中已经完成发表了多篇研究论文。该项目最重要的研究成果为：将图的度这一基本概念推广成了h-度，推广了图论中众所周知的结果，证明了广义度-和公式，并证明了图的广义度以及度序列矩阵是图的不变量；对于狄拉克猜想，我们证明了对平面上的每一非共线n点集P，包含一个点与由P所确定的 (2n+3)^1/2 -1 条线相关联，当n很小时这给出了一个最优下界，并猜测对平面上的每一度为t(P)的非共线点集P，至多包含3(t(P)-1)个点，该猜测最近得到了证明并被接收。