Collaborative Delivery Optimization for Multi-Store Retailers

The “Multi-Store Collaborative Delivery Optimization (MCDO)” problem can be described as follows: Consider there is a retailer with several physical stores in a region. Each store has order fulfillment ability and can collaborate to deliver orders. Each multi-item order can be split into sub-orders based on the storage of each store, as well as the distance between the store and the order. For each item in the order, it can be delivered directly from the store to the customer or transferred to another store for consolidation and deliver to customers with the other items. Use the following example to explain the MCDO problem.
Example 1. Tables 1 and 2 show the information of the order and store, including the arrival time, the delivery time window, and the demand item of the order, and Table 3 shows the distance between the order and the store. Fig 1 shows the location of each store and order, the straight-line distance on the graph represents the delivery time and delivery cost of an order. Denote store and order by m and r respectively, and use a^m and a^r to denote the items that the store owned and the order required, now there are four stores m₁, m₂, m₃, m₄, and two dynamically arriving online orders r₁, r₂. It is important to match real-time orders with stores, i.e., select stores that can complete the orders at a minimum cost, and design the order delivery routes for stores.
At time 0, order r₁ arrives, it can be delivered by {m₁, m₂} and {m₃} for two solutions, as shown in Fig 2. The cost of solutions is 4 and 5, and the delivery time of solutions is 3 and 5 respectively. Both solutions satisfy the time window of r₁, thus the optimal split plan of r₁ is, therefore {m₁, m₂}. And with the consolidation of m₁ and m₂, the joint delivery route S_v = {m₂, m₁, r₁}, where the cost and the delivery time are both 3, which is better than the individual delivery, it’s the optimal delivery solution of r₁ in the offline scenario.
At the moment 2 r₂ arrives, the optimal order-split plan of r₂ is {m₃, m₄}. In this situation, if r₁doesn’t deliver, with the consolidation of stores, the solution of r₁ can be change from {m₁, m₂} to {m₃}. In this way, the total cost of delivering {r₁, r₂} reduced from 9 to 8, and the delivery time of r₁ is 7, r₂ is 8, which both satisfy the time window, the final delivery plan of r₁ and r₂ can be seen in Fig 3. It can be imagined that as the scale of orders expands, the route repetition rate between different solutions will rise. Through the joint optimization of order-split and order-delivery, the route repetition rate can be effectively reduced, which is conducive to improving the efficiency of order fulfillment and reducing the order fulfillment cost of the enterprise.