The development of iterative constraint satisfaction problem solving methods for combinational optimization problems

组合优化问题迭代约束满足问题求解方法的发展

• 批准号: 22700231
• 负责人: NAGATA Yuichi
• 金额: $ 2.41万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2010
• 资助国家: 日本
• 起止时间: 2010-04-01 至 2013-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22700231/
• 关键词: メタ戦略; 制約充足; 組合せ最適化; vehicle routing; timetabling; 制約充足問題; スケジューリング問題; 配送計画問題; タプ探索

In this research, I have developed a new local search-based search framework called guided ejection search (GES) and constructed a very powerful solution method for the job shop scheduling problem, which is one of the most studied scheduling problems in the OR community. The framework of GES is based on local search but has the following features; it efficiently enumerates bottlenecks of the current best solution in improving the quality and preferably resolves one that is not resolved recently. The basic idea of GES can be straightforwardly applied to other combinational optimization problems, and I have developed very powerful solution methods for the vehicle routing problem and timetabling problem.

在这项研究中，我开发了一种新的基于局部搜索的搜索框架，称为引导式喷射搜索(GES)，并构建了一种非常强大的求解作业车间调度问题的方法，该问题是运营界研究最多的调度问题之一。GES的框架基于局部搜索，但具有以下特点：它有效地列举了当前最佳解决方案在提高质量方面的瓶颈，并较好地解决了最近没有解决的瓶颈。遗传进化算法的基本思想可以直接应用于其他组合优化问题，针对车辆路径问题和排课问题，我提出了非常强大的求解方法。

项目成果

Guided ejection search の提案とジョブショップスケジューリング問題への適用

引导顶出搜索的提出及其在车间调度问题中的应用

• 发表时间: 2011
• 作者: Kenji Nagata;Sumio Watanabe and Masato Okada;永田裕一
• 通讯作者: 永田裕一

A Hybrid Genetic/Tabu Search Algorithm for the Job Shop Scheduling Problem

车间调度问题的混合遗传/禁忌搜索算法

• 发表时间: 2011
• 期刊: In Post conference Revised and Selected Volume Papers of 8th Metaheuristics International Conference, Springer
• 作者: Yuichi Nagata;Shigenobu Kobayashi
• 通讯作者: Shigenobu Kobayashi

The mixed capacitated general routing problem with turn penalties

• DOI: 10.1016/j.eswa.2011.04.092
• 发表时间: 2011-09-15
• 期刊: EXPERT SYSTEMS WITH APPLICATIONS
• 影响因子: 8.5
• 作者: Braysy, Olli;Martinez, Eulalia;Soler, David
• 通讯作者: Soler, David

Random Partial Neighborhood Search for University Course Timetabling Problem

大学课程时间表问题的随机部分邻域搜索

• 发表时间: 2014
• 作者: 小野渉;岡本卓;小圷成一;平田廣則;Katsumi Tateno,Yoshitaka Ohtubo;Y. D. Sato & Y. Kuriya;永田賢二,岡田真人;Y.Nagata and I.Ono
• 通讯作者: Y.Nagata and I.Ono

選択的なルート交換交叉法を用いたMemetic Algorithm のPickup and Delivery Problem with Time Windows への適用

选择性路由交换交叉法模因算法在时间窗取货和投递问题中的应用

• 发表时间: 2010
• 作者: Y. Nojima;S. Mihara;and H. Ishibuchi;永田裕一,小林重信
• 通讯作者: 永田裕一,小林重信