Last Mile Delivery With Stochastic Travel Times Considering Dual Services

Abstract

Nowadays there are two prevailing delivery modes in the last mile delivery; one is the home delivery (HD) that vehicles deliver parcels to customers' homes; and the other is the customers' pickup (CP) that vehicle deliver parcels to some kind of intelligent express boxes where customers can pick up their parcels with free time. This article studies a green vehicle routing problem considering dual services (HD and CP) with stochastic travel times (GVRP-DS-STT) to provide customers with sustainable and diversified delivery services. The GVRP-DS-STT problem is formulated as a two-stage stochastic optimization model with recourse strategy. The purpose of the model is to minimize the total operational cost under stochastic environment. In addition, a two-stage heuristic algorithm integrating with a sampling strategy is developed to solve approximately the problem, the first of which is the greedy-based initial feasible solution generation, and the second of which is an improvement heuristic with late acceptance to explore the solution space. The computational results show that there are increasing benefit in terms of total operational cost, number of the vehicles used and loading rate with the increase of percentage of CP customers. The time windows have great effect on the operational cost, but more CP customers can reduce their impact. The stochastic model outperforms the deterministic model in terms of total operational cost.

Keywords

• Green vehicle routing problem
• stochastic travel times
• dual services
• sample average approximation sampling
• hybrid heuristics