In recent days, there has been good news from the 29th International Computing and Combinatorics Conference (COCOON 2023), where a paper titled “Improved Approximation Algorithms for Multidepot Capacitated Vehicle Routing” co-authored by Dr. Zhao Jingyang and Professor Xiao Mingyu from our Algorithms and Logic group has won the “Best Paper Award”. COCOON is an important international conference in the field of computer science theory and is ranked as Class B by the China Computer Federation (CCF). This year’s COCOON was held in Hawaii, USA from December 15th to 17th, 2023, receiving 146 submissions from over 20 countries worldwide. Among the accepted 60 papers, this paper stood out and won the Best Paper Award. In the congratulatory letter issued by the conference, the authors were praised with the following statement: “Your work has been commended for its originality, technical depth, and significant impact on the related field. The selection committee was particularly impressed with the innovative approach and the clarity of presentation in your paper.”

The vehicle routing problem is a very important class of problems in the field of combinatorial optimization and operations research. This problem requires us to design routes for transportation vehicles to meet customer demands while minimizing the total transportation cost. Despite the high prominence and widespread applications of this problem, progress in theoretical algorithmic research has been slow, especially in terms of approximation algorithms, with no substantial improvements in approximation ratios for many years. This paper focuses on the vehicle routing problem in a multi-depot setting and provides new approximation ratios for this important problem. The results improve upon the results by Li and Simchi-Levi in 1990 (INFORMS J. Comput. 1990) and Harks et al. in 2013 (Transp. Sci. 2013).

Jingyang Zhao is current a year-three Ph.D student in the Algorithms and Logic group under the supervision of Mingyu Xiao. He focuses on algorithms for vehicle routing problems. Over the course of three years, he has made theoretical breakthroughs in several vehicle routing problems, publishing over 10 papers in prestigious international journals and conferences such as IEEE Trans, AAAI, IJCAI, MFCS, and COCOON.

Additionally, at the same time, Ziliang Xiong, another student of the Algorithms and Logic group, along with his advisor, Professor Mingyu Xiao, received the Best Paper Award at the European Conference on Computer Science and Information Technology (ECCSIT 2023), held from December 15th to 17th, 2023.