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

• Importance of considering multiple driving ranges in fleets including electric vehicles.
• Describes an integer programming formulation and a multi-round heuristic algorithm for solving the problem.
• The algorithm is used to analyze how distance-based costs are increased when considering ‘greener’ fleet configurations.
• The paper contributes to support the hypothesis that hybrid and electric vehicles can be used in routing problems without necessarily incurring significantly higher distance-based costs.

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.

Figure optionsDownload as PowerPoint slide