Alibaba VRP Algorithms Have Enabled Its On-time Hour-level Delivery

Alibaba-promoimage

In recent years, Alibaba has pioneered an integrated online and offline retailer where customers can place online orders of e-commerce and grocery products at its participating stores or restaurants and have them delivered in as short as 30 minutes or 2-4 hours. Depending on the customer segments and geographical locations, these services are provided through various businesses of Alibaba ecosystem, such as Freshippo, Taoxianda, Cainiao Network, Lazada, etc. 

The delivery services enable their customers to order nearly everything, including fresh foods, raw or cooked, and OTC drugs on their mobile phones.

These service commitments indicate that as soon as orders are placed, decisions have to be made to 1) batch these orders and schedule picking routes of orders for pickers at warehouses or stores, and 2) optimize routes for motor drivers. There are varieties of routing problems to be solved in the whole process or order fulfillment process. The stringent service commitment, coupled with urban transportation uncertainty and complicated picking operations in space-tight warehouses, have created significant challenges in developing solutions to these problems.

To solve these problems, the operations research community of Alibaba has developed its own vehicle routing problem (VRP) system. In addition to the reduced time and the resulting cost-saving benefits, the algorithm has brought several other intangible benefits.

It significantly frees up the time of algorithm developers, speeds up the business development, and becomes one of the key drivers behind the success of several business subsidiaries inside Alibaba — providing on-time and fast delivery service in a cost-efficient way is critical to stay competitive in the market, and by shortening the vehicles’ traveling route, the carbon dioxide emissions are reduced, another effort highlighting our commitment to environment protection. 

The system is built upon two approaches: an Adaptive Large Neighborhood Search (ALNS) Framework and a Learning-based Framework.

The former is based on the latest metaheuristics in the solution of VRPs, contains a rich pool of neighborhood search operators, supports almost all variants of VRPs, and allows the inclusion of additional objectives and constraints for expansion, and has consistently ranked the best among several VRP test cases.

The latter is the development of a deep-learning-based approach that trains neural network models offline to make almost instant online predictions of optimal solutions. 

The algorithms have achieved near the vicinity of the best solutions for some VRP cases with a tiny fraction of the time and thus are used for practical online decision making. 

To increase the transportability of the system, several efforts were made: First, a framework that allows extension through neighborhood operators is developed. An extendable domain-specific language is designed to implement user-defined constraints and objectives. 

Second, a data-driven approach that allows self-learning VRP solutions based on real data is provided. It also incorporates optimization to generate offline training to derive models that could be used for online real-time decision making. Such an approach has been applied to develop the solution to address a variety of routing problems in milliseconds in real life.