An iterated beam search algorithm for the green vehicle routing problem

Green, or, alternative‐fuel vehicles provide opportunities to improve fleet operators’ financial and environmental bottom lines. They also present challenges due to limited driving ranges, limited refueling infrastructure, and lengthy refueling times. This paper addresses a green vehicle routing problem of homogeneous service fleets with stated challenges, and develops an Iterated Beam Search algorithm for its solution. The developed algorithm can employ different lower and upper bounding strategies, and can work as an exact or a heuristics algorithm. A dominance strategy is also developed to improve efficiency of the algorithm. Computational experiments on various‐size test instances show that the algorithm's performance is comparable to existing approaches.