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

Abstract

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.

Keywords:

• city logistics
• genetic algorithm
• stochastic demands
• stochastic programming
• two-echelon capacitated vehicle routing

Electronic supplementary material

The online version of this article (doi:10.1057/s41274-016-0170-7) contains supplementary material, which is available to authorized users.

Electronic supplementary material

The online version of this article (doi:10.1057/s41274-016-0170-7) contains supplementary material, which is available to authorized users.

Acknowledgements

The authors thank the editors as well as two anonymous referees for their valuable comments and suggestions. This work is supported by the research grant from the National Natural Science Foundation of China (71602081) and the Fundamental Research Funds for the Central Universities (16LZUJBWZY005).