Welcome to Yi Mei's homepage!

NEWS

  • IEEE CIS Webinar presentation: "Genetic Programming Hyper-Heuristics for Combinatorial Optimisation", Dec 2016, [Slides].

I am a Lecturer at the School of Engineering and Computer Science, Victoria University of Wellington, Wellington, New Zealand. My research interests include evolutionary algorithms, genetic programming, memetic algorithms and other meta-heuristics, hyper-heuristics, with various real-world applications in scheduling and routing, such as arc routing problems, vehicle routing problems, job shop scheduling, traveling salesman problems, warehouse layout optimization, and personalised tourist trip planning.

I received my B.Sc. degree in mathematics from the University of Science and Technology of China (USTC), Hefei, China. During my undergraduate study from 2001 to 2005, I was selected to be studying in the Special Class for the Gifted Young (introduction in Wikipedia), which is a special program of USTC that gives a special education for the gifted young undergraduate students from all parts of China, and only accept about 50 talented students no older than 15 in age from high school each year. From 2005 to 2010, I studied and worked at the Nature Inspired Computation and Applications Laboratory, School of Computer Science and Technology of USTC, and obtained my Ph.D. degree under the supervision of Professor Xin Yao and Professor Ke Tang.

During 2010-2012, I was a Provost's Research Associate at the Department of Computer Science and Engineering of the Chinese University of Hong Kong, Hong Kong, researching on portfolio optimization.

During 2012-2015, I worked as a ARC Discovery Research Fellow with A/Prof. Xiaodong Li at the School of Computer Science and Information Technology, RMIT University, Melbourne, Australia. My research topic was large-scale optimization with inter-dependent subcomponents.

Research

I. Evolutionary 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).

Publications

  • Note: Publications listed below are made on-line available for faster dissemination. The copyright of the papers is owned by their publisher.
  • All the codes are provided to help empirical comparison and understand the idea of the work. We guarantee them to be the original code from which the results in the papers were obtained (there is no trick). Please do NOT misuse them. We'd appreciate it if you cite the relevant paper when using the codes.

Journals

Conference Proceedings

Book Chapters

Professional Activities

Editorship

  • Editorial Board Member of International Journal of Bio-Inspired Computation
  • Guest Editor of Special Issue on Automated Design and Adaptation of Heuristics for Scheduling and Combinatorial Optimisation, Genetic Programming and Evolvable Machines, 2016

Membership

Session (Co-)Chairs

  • Co-chair of Special Session on Computational Intelligence for Scheduling and Combinatorial Optimization, 2016 Asia-Pacific Symposium on Intelligent and Evolutionary Systems
  • Co-chair of Special Session on Transfer Learning in Evolutionary Computation, 2016 IEEE World Congress on Computational Intelligence
  • Co-chair of Special Session on Evolutionary Scheduling and Combinatorial Optimization, 2016 IEEE World Congress on Computational Intelligence
  • Co-chair of IEEE Symposium on Computational Intelligence in Production and Logistics Systems, 2013 IEEE Symposium Series on Computational Intelligence

Conference PC Member

  • IEEE Congress on Evolutionary Computation (CEC) 2013, 2014, 2016
  • Australasian Conference on Artificial Life and Computational Intelligence (ACALCI) 2016, 2017
  • IEEE Symposium Series on Computational Intelligence (SSCI) 2016
  • Asia-Pacific Symposium on Intelligent and Evolutionary Systems (IES) 2016
  • International Conference on Swarm Intelligence (ANTS) 2016
  • International Conference on Hybrid Intelligent Systems (HIS) 2016
  • International Conference of Soft Computing and Pattern Recognition (SoCPaR) 2015, 2016
  • International Conference on Innovations in Bio-Inspired Computing and Applications (IBICA) 2015, 2016
  • International Conference on Intelligent Systems Design and Applications (ISDA) 2016
  • World Congress on Nature and Biologically Inspired Computing (NaBIC) 2016
  • BRICS Congress on Computational Intelligence (BRCIS-CCI) 2015
  • Australasian Joint Conference on Artificial Intelligence (Australasian AI) 2015
  • International Conference on Simulated Evolution And Learning (SEAL) 2014

Journal Reviewer

Grants and Awards

Supervisions

PhD Students

Current students

  • Boxiong Tan (Victoria University of Wellington, 2016): "Evolutionary Web Service Provisioning and Scheduling" (Second supervisor)
  • John Park (Victoria University of Wellington, 2015): "Evolving Robust Dispatching Rules for Dynamic Job Shop Scheduling" (Associate supervisor)
  • Alexandre Sawczuk Da Silva (Victoria University of Wellington, 2015): "Evolutionary QoS-based Web Service Composition" (Associate supervisor)
  • Atiya Masood (Victoria University of Wellington, 2015): "Many-Objective Job Shop Scheduling" (Associate supervisor)
  • Deepak Karunakaran (Victoria University of Wellington, 2015): "Island-based Model for Multi-Objective Job Shop Scheduling" (Associate supervisor)
  • Md. Jakirul Islam (RMIT University, Australia, 2014): "Structural Topological Optimization Using Evolutionary Techniques" (Second supervisor)
  • Jing Xie (RMIT University, Australia, 2013): "Hyper-heuristics for Warehouse Layout Optimization" (Associate supervisor)

Master Students

Graduated students

  • Boxiong Tan (Victoria University of Wellington, 2015-2016): "Evolutionary Computation for Service Location Allocation" (Associate supervisor)
  • Youhan Xia (University of Melbourne, Australia, 2015-2016): "Ant Colony System for Itinerary Planning with Restaurants" (Advice on algorithm design experimental studies)
  • Haobo Fu (University of Science and Technology of China, 2007-2010): "Meta-heuristics for Capacitated Arc Routing Problems" (Technical advice)

Resources

CARP datasets to download:

MOTDOP datasets to download:

The instances are used in the following paper:
Yi Mei, Flora Salim, Xiaodong Li, "Efficient Meta-heuristics for the Multi-Objective Time-Dependent Orienteering Problem," European Journal of Operational Research, vol. 254, no. 2, pp. 443-457, 2016.

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