Routing electric cargo bikes: a hybrid solution approach

Abstract

Cities are getting more and more congested and environmental impact is becoming a larger point of interest for both customers and companies. Because of this more delivery companies are choosing to use cargo bikes instead of vans for the last-mile delivery of packages. This brings an interesting challenge as most vehicle routing problem solutions are created with vans in mind. We study the vehicle routing problem for electric cargo bikes. Cargo bicycles differ from vans since they have less power and lower weight. Because of this, the difference in travel speed caused by the weight of the load and also by the slope of the road is significant for cargo bicycles, whereas this is negligible for vans. Hence, load-dependent travel times have to be taken into account when we want to find a good routing solution. Specifically, we consider the vehicle routing problem with load-dependent travel times for cargo bicycles (or VRPLTT) as proposed in an earlier paper by Fontaine. This problem is a variant of the capacitated vehicle routing problem with time windows using a single depot. Our contribution is threefold. Firstly, we present a hybrid solution method based on combining column generation and local search. Such hybrid methods have previously been applied successfully on VRP models. We show that we can improve the solutions by applying this method. Secondly, we show how to introduce a constant wind in the VRPLTT model and present computational results showing different routing decisions are made when incorporating this wind. Lastly, in the original model, travel times are deterministic. This might not be a correct representation of the real world as travel times are not deterministic, especially in the city. Therefore, we show how to include stochastic travel times in our solution algorithm for VRPLTT and present computational results based on real-life instances.