A genetic-algorithm-based approach to the two-echelon capacitated vehicle routing problem with stochastic demands in logistics service
针对城市物流中随机需求下的两级容量受限车辆路径问题，提出基于遗传算法的求解方法，通过改进编码、交叉和变异算子，在测试实例中平均比已知最优解成本低2.57%。
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.