The development of centralization-diversity method for NP-hard combinatorial optimization problems

我们为组合优化问题开发了元启发式算法，并用所研究的数据结构实现了这些元启发式算法。主要研究车辆路径问题和机器调度问题。我们在许多国际会议上展示了我们的研究成果。在研究过程中开发的算法(最大团、图划分和通道分配)在算法数据库中以演示程序的形式开放，这是该项目的主要成果之一；针对车辆路径问题，我们开发了在具有软时间窗的车辆路径问题的元启发式算法中出现的邻居搜索的快速算法，这在商业实践和研究兴趣中都是非常重要的。在库存路径中，配送成本和库存成本同时优化。利用动态规划和交叉优化的思想，提出了一种有效的库存路径优化算法。我们还报道了计算实验。实验表明，库存路径降低了约40%的总成本。我们还处理了调度问题。在作业车间调度问题的算法中，区间一致性检验对缩小搜索区域是有效的。这些测试对于资源受限的项目调度问题自然是广泛的，并且在调度中非常有用。针对区间一致性检验中的输入或输出检验问题，提出了一种快速算法。通过使用平衡二叉树和堆结构，我们将输入或输出测试的时间复杂度从O(n^4)降低到O(n^2log^2n)。

We developed meta-heuristics for combinatorial optimization problems and implemented these meta-heuristics with those investigated data structures. We mainly deal with the vehicle routing and the machine scheduling. We presented our research results in many international conferences. The algorithms developed in our research process are open as demo programs (maximum clique, graph partition and channel assignment) in the Algorithm Database that is one of the main results of the research project.In relation to the vehicle routing, we developed fast algorithm of neighbor search appeared in the meta-heuristics for the vehicle routing with soft time windows that is very important in business practice and in research interest.We deal with the inventory routing. In the inventory routing, delivery costs and inventory cost are simultaneously optimized. We developed effective algorithm for the inventory routing by using dynamic programming and cross-opt improvement. We also reported computational experiments. The experiments show that the inventory routing reduces total cost about 40%.We also deal with the scheduling problem. In algorithms for the job-shop scheduling problem, interval consistency tests are known to be effective to narrowing search areas. The tests are naturally extensive to the resource constraint project-scheduling problem and very useful in scheduling. We developed a fast algorithm for the input-or-output test that is one of the interval consistency tests. We reduced the time complexity from O(n^4) to O(n^2log^2n) of the input-or-output test by using the balanced binary tree and heap structures.