Iterative improvement approaches for collecting weighted items in directed bipartite graphs

作者：Karuno Yoshiyuki^*; Tanaka Seiya

来源：Journal of Advanced Mechanical Design Systems and Manufacturing, 2018, 12(2): 17-00588.

DOI：10.1299/jamdsm.2018jamdsm0051

• Engineering optimization
• 0-1 knapsack problems
• Directed bipartite graphs
• Arc reversing strategy
• Simulated annealing

In this paper, an iterative improvement heuristic based on the simulated annealing is designed for a weighted item collecting problem in directed bipartite graphs. The weighted item collecting problem is a generalization of an integrated circuit design problem, and it is also a variant of 0-1 knapsack problems in graphs. Recently, a greedy heuristic algorithm has been presented for the weighted item collecting problem. The greedy heuristic algorithm obtains an optimal solution of a known test instance of the original integrated circuit design problem in a short execution time, while for a randomly generated instance, there may be some room for improvement of the heuristic quality. In order to search for a better heuristic solution, some neighborhood structures for an incumbent solution are defined, and each of them is embedded in a framework of the simulated annealing. Numerical experiments are conducted to examine the iterative improvement performance, and the results are reported.

• 出版日期2018