题目：A genetic-algorithm-based approach to the two-echelon capacitated vehicle routing problem with stochastic demands in logistics service

作者：

Kangzhou Wang (兰州大学/Lanzhou University)

Shulin Lan (香港大学/The University of Hong Kong)

Yingxue Zhao (对外经济贸易大学/University of International Business and Economics)

期刊：Journal of the Operational Research Society (SSCI, SCI, IF: 1.225), 2017, 1-13.

英文摘要：

This paper addresses the two-echelon capacitated vehicle routing problem (2E-CVRP) with stochastic demands (2E-CVRPSD) in city logistics. A stochastic program with recourse is used to describe the problem. This program aims to minimize the sum of the travel cost and the expected cost of recourse actions resulting from potential route failures. In a two-echelon distribution system, split deliveries are allowed at the first level but not at the second level, thereby increasing the difficulty of calculating the expected failure cost. Three types of routes with or without split deliveries are identified. Different methods are devised or adapted from the literature to compute the failure cost. A genetic-algorithm-based (GA) approach is proposed to solve the 2E-CVRPSD. A simple encoding and decoding scheme, a modified route copy crossover operator, and a satellite-selection-based mutation operator are devised in this approach. The numerical results show that for all instances, the expected cost of the best 2E-CVRPSD solution found by the proposed approach is not greater than that of the best-known 2E-CVRP solution with an average relative gap of 2.57%. Therefore, the GA-based approach can find high-quality solutions for the 2E-CVRPSD.

中文摘要：

随着电子商务的兴起和快速发展，快递物流行业规模剧增，已成为人们日常生活的重要部分。例如，2015年双十一，中国电商巨头阿里巴巴单日产生的包裹达到3.08亿。这些包裹由物流公司从各个商家收集并发送到顾客手中。两级运输系统是收集包裹时物流公司采用的主要方式，首先，较小的车辆从离客户较近的市区中转点出发，访问一定数量的客户后，返回出发中转点;然后，较大的车辆再从离客户较远的郊区大仓库出发，访问所有中转点后返回仓库。但在制定车辆访问路线时，客户的实际需求只有车辆到达后才能确定，物流企业管理者事先并不知道。而当车辆收集的客户货物数量超过其最大能力时，车辆须满载返回出发点卸载货物后，再服务剩余客户。为了最小化运输成本，需合理设计第一级和第二级车辆访问路线。本文首先建立带补偿的随机规划模型来描述这一问题;然后结合第一级需求可拆分而第二级客户需求不可拆分的特点，设计逼近方法计算不同类型路径失效成本;在此基础上，设计遗传算法求解提出的问题。最后，基于顾客规模达到200的情形，测试提出的车辆路线规划方法的效果。大规模数据下实验结果表明，本文提出的方法比确定情况下最好方法的成本更低，两者平均相对间隙为2.57%，这一平均间隙定量地表明本文提出的方法的高效性，也间接地说明物流企业管理者在制定车辆运输路线时，需要提前考虑客户需求的不确定性，从而设计更为合理的包裹收集路线。

网址链接：

https://link.springer.com/article/10.1057/s41274-016-0170-7