Capacitated vehicle routing with multiple constraints is an important and challenging problem with numerous real-world applications in smart logistics, including cargo distribution, waste collections, etc. Many efforts have been made by researchers in operations research and computer science to tackle it, although no satisfactory solution has been found so far.

Researchers from the Department of Computer Science and Engineering (CSE) at the Southern University of Science and Technology (SUSTech) have recently developed some innovative ideas in solving large-scale real-world instances and achieved state-of-the-art results. This research team included undergraduate students Wenxing Lan, Ziyuan Ye, and Peijun Ruan.

Their work, entitled “Region-focused Memetic Algorithms with Smart Initialisation for Real-world Large-scale Waste Collection Problems,” was published in IEEE Transactions on Evolutionary Computation, the flagship international journal in the evolutionary computation field. Their study introduced a two-stage optimization algorithm (Figure 1). The first stage uses a greedy algorithm to obtain initial solutions efficiently, and the memetic algorithm (MA) used in the second stage improves the initial solutions.

Figure 1. The framework of the two-stage optimization algorithm

The researchers’ extensive experimental results show that their method outperformed the state-of-the-art in terms of both time efficiency and solution quality. This is the first attempt at solving such a complex problem of this size.

Wenxing Lan, Ziyuan Ye, and Peijun Ruan, undergraduate students of the Department of CSE at SUSTech, are the co-first authors of this paper. Dr. Jialin Liu from the Department of CSE at SUSTech is the corresponding author.

This research was jointly supported by the National Natural Science Foundation of China (NSFC), the Guangdong Provincial Key Laboratory, the Program for Guangdong Introducing Innovative and Entrepreneurial Teams, the Guangdong Basic and Applied Basic Research Foundation, the Shenzhen Science and Technology Program, the Shenzhen Fundamental Research Program, and the Stable Support Plan Program of Shenzhen Natural Science Fund.

Undergraduates of the Department of Computer Science and Engineering (CSE) at SUSTech every year publish their research results in top international journals or conferences. There has been a heavy emphasis on problem-solving and computational thinking skills, rather than just book knowledge, in Computer Science undergraduate majors at SUSTech.

Related links:

Paper link (IEEE Transactions on Evolutionary Computation): https://ieeexplore.ieee.org/abstract/document/9594087/.

Department of Computer Science and Engineering at SUSTech: https://cse.sustech.edu.cn/.

To read all stories about SUSTech science, subscribe to the monthly SUSTech Newsletter.