How to efficiently and economically deliver takeout orders? What's the optimal delivery path? People found the answer by simulating the behavior of ants seeking a path between their colony and a source of food.
In the natural world, ants wander randomly, and upon finding food return to their colony while laying down pheromone trails. If we assume that each ant has the same amount of pheromone, the short paths would have higher pheromone density, thus attracting more ants. By simulating the behavior of ants seeking a path, we can obtain the shortest path with iterative calculation.
This algorithm, i.e., the ant colony algorithm, is the state-of-the-art algorithm for last-mile delivery. It was first proposed by Italian scientist Dr. M. Dorigo in 1991. In 2010, Dr. G. Fuellerer in Austria used it to optimize vehicle routing. This theory is widely applied in package delivery, to help save cost for the last mile delivery.
Recently, a team from Huazhong University of Science and Technology in "The Last Mile Rush" Tianchi competition made a breakthrough. They formulate the last mile delivery as a "sharing point of interest" problem. They find a better solution by decreasing the times of passing points of interest and loading/unloading more packages at each point of interest. Compared to the ant colony algorithm, the proposed algorithm can effectively avoid solutions that are locally optimal, thus obtaining better global results.
In international package delivery, it is a common practice to use algorithms for vehicle scheduling and cost savings. For a large platform of takeout orders, using these algorithms can also increase the rate of timely delivery.
If the proposed algorithm is applied to production, it is estimated to be capable of handling 500 orders within 6 seconds and decreasing the delivery cost by around 25 percent, which is 5 percent higher than the algorithm currently used in Alibaba.
"We are now in the age of sharing economy." Dr. Ming Chu in Ali-Yun artificial intelligence says. "When an enterprise/organization is faced with a problem or challenge, the solution should not be limited by its own capability. It can show the problem to all the people through the internet and use crowd intelligence to seek for solution."
"As educators and researchers, we hope to strengthen the connection to the industry and enhance education with different kinds of competitions." Professor Fangming Liu at Huazhong University of Science and Technology says. "The School of Computer Science and Technology in HUST has three advantages in education and research. The first one lies in scientific innovation. Our undergraduate students continuously win prizes in such famous competitions as ACM International Collegiate Programming Contest, the Imagine Cup Worldwide finals, and International Supercomputing Conference. The second is the emphasis on practice application. We fully utilize all kinds of research platforms to attract students to participate in research projects, publish top-level papers, or develop real-world systems. We also cooperate with leading enterprises in the industry, like Alibaba, to build the connection between education and practical application. The third advantage is the support for startups. We fostered a group of young elite entrepreneurs who successfully started up their own IT companies such as PPTV and Taomi. With the support from the university, we are also planning to build up a research center for big data-related research."
By now, Tianchi competitions have been held worldwide more than 20 times, continuously sharing computing resources in Ali-yun. It is also officially announced that the historical problems and data in the past two years will become publically accessible, welcoming competitors around the world to break the records.
