Scalable Multi Swarm-Based Algorithms with Lagrangian Relaxation for Constrained Problems

摘要

Constrained optimisation problems for large real-world instances are usually difficult to solve and can require custom heuristics as well as other methods to solve them efficiently. They can also have large computational requirements that only large platforms can satisfy. The aim of this paper is to present a methodology where, by using a set of different techniques in parallel, we are able to find near optimal solutions for these problems in a reasonable time. This is important since many of these problems are critical in several different areas as, for example, logistics or scheduling. By being able to optimise these problems, we are able to solve complex scenarios with huge economic, environmental or human benefits, among others. Our approach tries to achieve an optimal usage of the available computational resources and is also easily extensible to allow further development of other parallel optimisation techniques. The effectiveness of this approach is demonstrated by applying it to a rail scheduling problem arising in the planning of train trips in the Hunter Valley Coal Chain.