Welcome to Yi Mei's homepage

For what will it profit a man if he gains the whole world and forfeits his soul? -- Matthew 16:26

Arc Routing Problems

Briefly speaking, given a graph and a set of vehicles, arc routing is to design the best (e.g., shortest, fastest or most reliable) routes for the vehicles to serve a prespecified subset of the arcs (directed edges). Although this problem is practically significant and has a wide range of real-world applications, it is highly challenging especially when the real road map have a huge number of streets and customers. Efficient algorithms are needed to give better routing solutions within a shorter time for a larger network.

Applications

Winter Gritting

In winter, there is usually a thin coating of glazed ice on the surface of roads due to the low temperature, causing a high risk of traffic accident. Such black ice hazard is a common issue in many countries. For example, according to the data in 2006, there are about 3000 routes, 120,000 km or 30% of the entire road network to be gritted each year in the UK, inducing a cost of millions of Pounds. In this problem, the goal is to spread salt onto all the high-risk (low-temperature) streets with the least cost (e.g., petrol consumption, number of trucks and labour force).

We have designed 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.

We have also seriously taken into account the important issues that are often encountered in the real world. Specifically, we have considered multiple conflicting objectives and large problem size. We have designed a very efficient multi-objective optimization algorithm to minimize the total cost and makespan (the longest route) simultaneously. 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.

Waste Collection

In waste collection, not all the garbage bins need to dumped every day. In general, The ones in the urban areas need to be dumped more frequently than those in the rural regions. In this scenario, making a weekly plan is more realistic than a daily plan, which can be abstracted to the so-called Periodic Capacitated Arc Routing Problem. In this problem, the objective is not only to schedule the best routes for each day, but also to properly decide which streets are to be collected in which day of the week.

We have designed a hierarchical optimization method to solve this problem, so that we can minimize not only the total cost, but also the number of vehicles used over the week.

Freight Delivery

In Freight Delivery, there may be new orders coming in while the vehicles are on their way to serve the existing customers. It is desirable to prepare for responding these potential new orders in advance and update the routes of the existing vehicles in the real time rather than sending new vehicles from the depot. In this case, ones needs to consider the robustness (ability of dynamic change without losing much quality) of the routing plan as well as its static quality.

We have done 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 based on your preference.

Benchmark Datasets

Below is a list of the commonly used benchmark instances to test your algorithms for arc routing:

gdb set (small sized)
val set (median sized)
egl set (median to large sized)
Beullens set (small to large sized)
EGL-G set (large sized)

Publications

Below are my publications relevant to arc routing problems.

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

Yi Mei, Xiaodong Li, and Xin Yao, "Cooperative Co-evolution with Route Distance Grouping for Large-Scale Capacitated Arc Routing Problems," IEEE Transactions on Evolutionary Computation, vol. 18, no. 3, pp. 435-449, 2014.
The C language source code of can be downloaded here.
Yi Mei, Ke Tang, and Xin Yao, "A Memetic Algorithm for Periodic Capacitated Arc Routing Problem," IEEE Transactions on Systems, Man, and Cybernetics: Part B, Vol. 41, no. 6, pp. 1654-1667, 2011.
The experimental results can be downloaded here.
Yi Mei, Ke Tang, and Xin Yao, "Decomposition-based Memetic Algorithm for Multi-Objective Capacitated Arc Routing Problems," IEEE Transactions on Evolutionary Computation, vol. 15, no. 2, pp. 151-165, April, 2011.
The C language source code can be downloaded here.
Ke Tang, Yi Mei, and Xin Yao, "Memetic Algorithm with Extended Neighborhood Search for Capacitated Arc Routing Problems," IEEE Transactions on Evolutionary Computation, vol. 13, no. 5, pp. 1151-1166, October, 2009.
The C language source code can be downloaded here.
Yi Mei, Ke Tang and Xin Yao, "A Global Repair Operator for Capacitated Arc Routing Problem," IEEE Transactions on Systems, Man, and Cybernetics: Part B, vol. 39, no. 3, pp. 723-734, June, 2009.
The C language source code can be downloaded here.

Conference Proceedings

Yi Mei, Xiaodong Li and Xin Yao, "Variable Neighborhood Decomposition for Large Scale Capacitated Arc Routing Problem," Proceedings of the 2014 IEEE Congress on Evolutionary Computation (CEC2014), pp. 1313--1320, Beijing, China, 6-11 July 2014.
The C language source code of can be downloaded here.
Yi Mei, Xiaodong Li and Xin Yao, "Decomposing Large-Scale Capacitated Arc Routing Problems using a Random Route Grouping Method," Proceedings of the 2013 IEEE Congress on Evolutionary Computation (CEC2013), Cancun, Mexico, 20-23 June 2013, IEEE Press.
The C language source code of can be downloaded here.
Yi Mei, Ke Tang and Xin Yao, "Capacitated Arc Routing Problem in Uncertain Environments," Proceedings of the 2010 IEEE Congress on Evolutionary Computation (CEC2010), Barcelona, Spain, 18-23 July 2010, IEEE Press.
The C language source code of the uncertain CARP benchmark instance generator can be downloaded here, and the generated uncertain CARP benchmark sets can be downloaded here.
Haobo Fu, Yi Mei, Ke Tang and Yanbo Zhu, "Memetic Algorithm with Heuristic Candidate List Strategy for Capacitated Arc Routing Problem," Proceedings of the 2010 IEEE Congress on Evolutionary Computation (CEC2010), Barcelona, Spain, 18-23 July 2010, IEEE Press.
Yi Mei, Ke Tang and Xin Yao, "Improved Memetic Algorithm for Capacitated Arc Routing Problem," Proceedings of the 2009 IEEE Congress on Evolutionary Computation (CEC2009), Trondheim, Norway, 18-21 May 2009, IEEE Press.

Book Chapters

Yi Mei, Ke Tang and Xin Yao, "Evolutionary Computation for Dynamic Capacitated Arc Routing Problem," Evolutionary Computation for Dynamic Optimization Problems, Shengxiang Yang and Xin Yao (Eds.), Studies in Computational Intelligence Volume 490, pp. 377-401, 2013.