Abstract: This paper studied the vehicle routing problem with release dates and time windows of e-commerce terminal distribution, taking into consideration order release dates, customers time windows, and customer dispersion, in order to minimize the total travel distance. Besides, it not only constructed a flow-based model, but also proposed a novel linear model considering problem characteristic. Moreover, it developed an improved branch-and-cut algorithm based on two valid inequalities. Furthermore, it compared the two models and analyzed the influence of two valid inequalities on the algorithm. The effectiveness of the proposed exact method was verified by comparing it with the CPLEX default branch-and-cut algorithm. The results show that proposed method can get the optimal solution in a short time for small size instances. For large size instances, the related intelligent algorithm can be evaluated by the optimal solutions obtained by the improved branch-and-cut algorithm.

Key words: release dates, time windows, improved branch-and-cut, e-commerce terminal distribution

摘要： 针对考虑订单可得时间和客户时间窗的电商末端配送路径问题，考虑配送特点（订单可得时间）、客户的时间需求（时间窗）和客户分布分散等特点，以最小化配送总里程为目标，构建了基础数学模型，并通过分析问题特征对模型改进，从而构建了改进数学模型。在此基础上，提出两种有效不等式，并设计了基于分离两种有效不等式的改进分支切割精确算法对模型进行求解。最后，通过测试多组算例，不仅对两种数学模型进行了比较，而且分析了不等式对算法性能的影响；通过与CPLEX默认的分支切割算法对比，验证了改进的分支切割算法的优越性。结果表明：对小规模的实际算例，采用改进的分支切割算法可以在极短的时间内得到最优解，具有很好的实用效果；对规模较大的算例，采用改进的分支切割算法得到的最优解可以对智能算法性能进行评价。

关键词: 订单可得时间, 客户时间窗, 改进分支切割算法, 电商末端配送