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.