In this paper, we consider a practical open multi-depot vehicle routing problem that raises in an E-commerce company. In this problem, the E-commerce company accepts orders in multiple periods (such as, each period is associated with a day or a half-day) and delivers goods to orders’ destinations by a fleet of vehicles before or on orders’ deadlines. For the problem, we consider both the case (denoted as offline case) where each order information is known, i.e., order arrival time, order destination, and quantity of goods ordered by each order are known, and the case (denoted as online case) where no information about a future order’s arrival time, destination, and quantity of goods ordered by a future order is known until this order arrives. For the offline case, we propose a heuristic algorithm making one decision in the planning horizon. For the online case, we propose an online algorithm making decisions once every few periods. Computational results based on actual business data of an E-commerce company in China show that the heuristic algorithm and online algorithm can find near-optimal solutions.

CICTP