Routing fleets with multiple driving ranges: Is it possible to use greener fleet configurations?

This paper discusses the vehicle routing problem with multiple driving ranges (VRPMDR), an extension of the classical routing problem where the total distance each vehicle can travel is limited and is not necessarily the same for all vehicles - heterogeneous fleet with respect to maximum route lengths. The VRPMDR finds applications in routing electric and hybrid-electric vehicles, which can only cover limited distances depending on the running time of their batteries. Also, these vehicles require from long charging times, which in practice makes it difficult to consider en route recharging. The paper formally introduces the problem, describes an integer programming formulation and a multi-round heuristic algorithm that iteratively constructs a solution for the problem. Using a set of benchmarks adapted from the literature, the algorithm is then employed to analyze how distance-based costs are increased when considering 'greener' fleet configurations - i.e., when using electric vehicles with different degrees of autonomy. (C) 2014 Elsevier B.V. All rights reserved.