Prof. Yi Mei

Prof. Yi Mei

Professor, Fellow of Engineering New Zealand, IEEE Senior Member

Evolutionary Computation for Combinatorial Optimisation

Many of society's logistics problems — collecting waste, gritting roads, delivering parcels, allocating cloud resources — are combinatorial optimisation problems: the number of possible solutions explodes with problem size. I design evolutionary and memetic algorithms that find near-optimal solutions quickly, and decomposition methods that let them scale to problems with thousands of decisions.

70+papers in this theme
1award-winning papers
8papers with 100+ citations (OpenAlex)
740+citations of differential grouping (OpenAlex)

Introduction

The problems

In the capacitated arc routing problem (CARP), a fleet of vehicles with limited capacity must serve a set of streets — for example to collect waste — at minimum total cost. Related problems include vehicle routing with electric vehicles or drones, team orienteering, job shop scheduling and service allocation. They are NP-hard, so exact methods quickly become impractical.

Capacitated arc routing exampleA depot and a road network; coloured streets must be served, and each colour is one vehicle's route.Depotroute of vehicle 1route of vehicle 2route of vehicle 3road (no service needed)
Figure 1. A small arc routing instance. Coloured streets require service; each colour is the route of one vehicle leaving and returning to the depot. Real instances have thousands of streets.

Why evolutionary computation?

Evolutionary algorithms search with a population of solutions, recombining good ones. Memetic algorithms add problem-specific local search, combining global exploration with powerful local refinement. They handle complex constraints and multiple objectives naturally and give good solutions within practical time.

Memetic algorithmEvolutionary search combined with problem-specific local search.Population ofcandidate solutionsCrossover(recombine routes)Local searche.g. Merge-Split operatorSelection &replacement
Figure 2. A memetic algorithm. Crossover explores new combinations of routes; local search, such as the large-step Merge-Split operator in MAENS, refines each offspring.

My Contributions

With my students and collaborators, I have made the following contributions. The papers shown are selected automatically: award-winning papers, papers with 100+ citations, and papers in top venues. Click a title to read the paper, or list entry to see it in my publication list.

1 Memetic algorithms for arc routing

We proposed MAENS, whose Merge-Split operator explores far beyond traditional local moves and became a widely used benchmark, and extended memetic search to multi-objective, periodic and uncertain arc routing.

2 Large-scale optimisation by decomposition

Very large problems are solved by splitting them into smaller interacting sub-problems. Our differential grouping detects variable interactions automatically, and route distance grouping and route clustering decompose large arc routing problems.

Cooperative co-evolution by decompositionVariables are grouped by interaction, each group is optimised separately, and results are combined.LARGE-SCALE PROBLEM: many interacting decision variablesx1x2x3x4x5x6x7x8x9x10x11x12① detect interactions (e.g. differential grouping) and group variablesoptimise group 1optimise group 2optimise group 3② combine via shared context solution
Figure 3. Cooperative co-evolution. Variables are grouped by their interactions; each group is optimised separately and the pieces are combined through a shared context solution.

3 Vehicle routing and emerging logistics

We design evolutionary algorithms for new logistics settings such as electric vehicles with charging, collaborative truck–drone delivery, multi-depot routing and orienteering.

4 Multi-objective and real-world optimisation

Real decisions involve trade-offs. We develop multi-objective evolutionary algorithms for web services and cloud, air traffic flow management, airport ground movement, project scheduling and water networks.

Research Output

Papers per yearStacked bars of journal and conference papers per year.0510152009: 2 journal2009: 1 conference32010: 0 journal2010: 1 conference120102011: 2 journal2011: 0 conference22012: 0 journal2012: 0 conference20122013: 1 journal2013: 1 conference22014: 2 journal2014: 2 conference420142015: 0 journal2015: 2 conference22016: 4 journal2016: 5 conference920162017: 2 journal2017: 1 conference32018: 2 journal2018: 2 conference420182019: 0 journal2019: 1 conference12020: 1 journal2020: 6 conference720202021: 3 journal2021: 2 conference52022: 7 journal2022: 4 conference1120222023: 3 journal2023: 1 conference42024: 3 journal2024: 0 conference320242025: 6 journal2025: 2 conference82026: 7 journal2026: 2 conference92026Journal articles & booksConference papers
Figure 4. My papers in this theme per year (78 in total), identified by title keywords in my publication lists; papers can belong to more than one theme. The 2026 count covers papers published so far this year.

Research Themes

Full publication list →   ← Back to home