Combinatorial optimization and vehicle fleet planning: Perspectives and prospects

Abstract

Abstract As a well‐structured and costly activity that pervades industries in both the public and private sector, vehicle fleet management would appear to be a splendid candidate for model‐based planning and optimization. And yet, until recently the combinatorial intricacies of vehicle routing and of vehicle scheduling have precluded the widespread use of optimization (exact) methods for this problem class. Our discussion in this paper identifies the extent and nature of these problem complexities and draws contrasts with other applications of combinatorial optimization. It also summarizes a number of successful uses of optimization for vehicle fleet planning and highlights potentially fruitful avenues for algorithmic development. In particular, we describe several alternative models and novel algorithms for the vehicle routing problem, show how various modeling approaches for this problem are intimately related, and illustrate the interplay between model formulations and the algorithms that they suggest. This discussion shows that prospects for applying exact methods, possibly in conjunction with heuristics, are far from fully realized and points to vehicle fleet planning as a tempting target of opportunity for further investigation.