权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

NP难组合优化问题的集中-多样性方法的发展

基本信息

批准号：
10205206
负责人：
KUBO Mikio
金额：
$ 3.65万
依托单位：
Tokyo university of mercantile marine
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas (B)
财政年份：
1998
资助国家：
日本
起止时间：
1998 至 2000
项目状态：
已结题

项目摘要

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.

我们开发了元算法的组合优化问题，并实现这些元算法与这些调查的数据结构。主要研究车辆路径问题和机器调度问题。我们在许多国际会议上展示了我们的研究成果。在我们的研究过程中开发的算法是开放的演示程序（最大团、图划分和通道分配）在算法数据库中的应用，这是本研究项目的主要成果之一。我们开发了快速的邻域搜索算法出现在Meta，软时间窗车辆路径问题是一个重要的研究课题，本文研究了软时间窗车辆路径问题。在库存路径选择中，同时优化配送成本和库存成本。利用动态规划和交叉选择改进算法，提出了一种有效的库存路径优化算法。我们还报告了计算实验。实验结果表明，库存路径优化使总成本降低了40%左右。在作业车间调度问题的算法中，区间一致性检验被认为是缩小搜索范围的有效方法。测试自然是广泛的资源约束项目调度问题，非常有用的调度。我们开发了一个快速算法的输入或输出测试，这是一个区间一致性测试。通过使用平衡二叉树和堆结构，将输入输出测试的时间复杂度从O（n^4）降低到O（n^2log^2n）。