Evolutionary Computation for Combinatorial Optimisation (ECCO) Group

NEWS

Evolutionary Computation for Combinatorial Optimisation (ECCO) Group is a sub-group under the Evoultionary Computation Research Group in Victoria University of Wellington, New Zealand. The group has a wide range of research interests and projects in solving combinatorial optimisation problems using evolutionary computation, including evolutionary vehicle/arc routing, job shop scheduling, cloud resource allocation, Web service composition. Our detailed research interests and projects can be found here.

The group includes xx staff members and yy students. Here you can see a full list of group members.

Research

I. Hyper-heuristics for Dynamic/Uncertain Arc Routing

The Arc Routing Problem is a challenging problem that aims to find a set of routes through the arcs in a given graph with minimum cost under certain constraints. It has a variety of important applications in domains such as snow removal, waste collection, post delivery and cloud computing. It is NP-hard, and can hardly be solved by exact methods. Thus, we choose meta-heuristics (e.g. evolutionary computation, tabu search, etc) to solve this challenging problem. We particularly focus on dealing with constrained and combinatorial search space, large problem size, multiple conflicting objectives, dynamic environment...

We developed several completitive algorithms for solving this challenging problem. Typical representatives are an efficient tabu search and a competitive memetic algorithm. The tabu search is very fast without losing much of the solution quality. The memetic algorithm can achieve the state-of-the-art solution quality, although its computational effort is a bit higher than the tabu search. In addition, we proposed a flexible divide-and-conquer stragety that is particularly powerful in solving large scale instances. It can obtain much better solutions in a much shorter time than the other existing methods, and is independent of the topology of the road network.

For multiple conflicting objectives, we developed a very efficient multi-objective optimization algorithm to minimise the total cost and makespan (the longest route) simultaneously. We also developed a hierarchical optimization method to solve periodic arc routing problems (typically encountered in waste collection), so that we can minimise not only the total cost, but also the number of vehicles used over the week.

To tackle uncertain and dynamic environment, we did some preliminary work in defining the problem under uncertainty and creating the corresponding instances. We also provide the instance generator so you can generate your own instances.

Commonly used CARP instances can be downloaded from here.

II. Automatic Design of Job Shop Dispatching Rules

Job shop scheduling has a wide applications in manufacturing and cloud computing. It is to make a schedule for processing a set of jobs using a set of machines. In a dynamic environment, unexpected events may occur during the implementation of the schedule (e.g. new job arrivals and machine breakdowns). Dispatching rules have shown to be promising in dynamic job shop scheduling due to its low complexity, flexibility and scalability. However, it is strenuous to design effective dispatching rules manually. Therefore, we focus on automatically designing (evolving) dispatching rules with genetic programming.

Based on existing studies, we did some preliminary work on terminal selection to identify truly important terminals and remove redundant ones. We also investigated the possibility of evolving an ensemble of rules rather than a single rule, as well as evolving a set of tradeoff rules for many-objective job shop scheduling with many conflicting objectives.

III. Large Scale Optimisation with Inter-dependent Modules

In optimisation, it is common to have a large number of decision variables. To optimise all the decision variables simultaneously will lead to a huge search space. In this situation, a standard strategy is divide-and-conquer, which identifies smaller subcomponents in the whole problem, and solve them separately or collaboratively. A typical example is the supply chain management, which consists of many subproblems such as product manufacturing, storing and distribution. Each subproblem is complex by itself, and they interact with each other.

We investigated a benchmark problem called the travelling thief problem, compared a number of different algorithms on it, and proposed an efficient divide-and-conquer algorithm for solving the subproblems collaboratively. An improved work can be found here.

From theoretical point of view, we developed a very competitive decomposion algorithm for black-box large scale optimisation, called differential grouping. After further improvement, it can achieve perfect decomposition accuracy in most of the time.

IV. Warehouse Layout Optimisation

In industry, how to efficiently locate the products in a spacious warehouse remains a challenge to the warehouse manager. The basic idea is to put the more popular products in locations that are closer to the pickup/delivery point so as to minimise the total average picking distance. There are mainly three difficulties in this problem: (1) the problem size (number of products and possible locations) can be enormous; (2) there may be complex real-world constraints (e.g., the correlation between products) to cause a smaller feasible region; and (3) the problem structure may change over time due to the change of customer requirements. The optimization algorithm is not flexible enough to adapt to the change of problem structure.

To address the above issues, we used genetic programming to optimise an allocation program for the products in the warehouse. As a constructive rule/heuristic rather than a solution, the optimised program is more scalable and flexible. Then, we explored the possibility of evolving a meta-heuristic (tabu search in this case).

People

Staff members

  • Dr. Yi Mei (Evolutionary Combinatorial Optimisation, Hyper-heuristics, Genetic Programming)
  • Prof. Mengjie Zhang (Evolutionary Computation and Machine Learning, Genetic Programming, Image Processing, Feature Selection)
  • Dr. Aaron Chen (Reinforcement Learning, NeuroEvolution (NEAT), Evolutionary Computation for Games, Evolutionary Scheduling)
  • Dr. Hui Ma (Evolutionary Resource Allocation, Web Service Composition, Cloud Computing)
  • Dr. Su Nguyen (Australia) (Evolutionary Scheduling and Combinatorial Optimisation, Hyper-heuristics, Genetic Programming)

Students

Talks

  • 2017-09-26, Whole group, Discussion on "how to read a paper"
  • 2017-09-19, Yuxin Liu, EDA for capacitated arc routing problems
  • 2017-09-12, Atiya Masood, Reference point adaptation during many-objective optimisation (Part 1)

Contact

Room CO353, Cotton Building,
Kelburn Campus,
Victoria University of Wellington,
Wellington,
New Zealand
E-mail: yi.mei AT ecs.vuw.ac.nz
Phone: +64 4 463 5233 x 8016