A heuristic algorithm for optimal fleet composition with vehicle routing considerations
MetadataShow full item record
This paper proposes a fast heuristic algorithm for solving a combined optimal fleet composition and multi-period vehicle routing problem. The aim of the problem is to determine an optimal fleet mix, together with the corresponding vehicle routes, to minimize total cost subject to various customer delivery requirements and vehicle capacity constraints. The total cost includes not only the fixed, variable, and transportation costs associated with operating the fleet, but also the hiring costs incurred whenever vehicle requirements exceed fleet capacity. Although the problem under consideration can be formulated as a mixed-integer linear program (MILP), the MILP formulation for realistic problem instances is too large to solve using standard commercial solvers such as the IBM ILOG CPLEX optimization tool. Our proposed heuristic decomposes the problem into two tractable stages: in the first (outer) stage, the vehicle routes are optimized using cross entropy; in the second (inner) stage, the optimal fleet mix corresponding to a fixed set of routes is determined using dynamic programming and golden section search. Numerical results show that this heuristic approach generates high-quality solutions and significantly outperforms CPLEX in terms of computational speed.
This is an Author's Original Manuscript of an article published by Taylor & Francis in Optimization Methods and Software on 10/07/2015 available online at <a href="http://www.tandfonline.com/10.1080/10556788.2015.1062890">http://www.tandfonline.com/10.1080/10556788.2015.1062890</a>
Showing items related by title, author, creator and subject.
Radiy, Mamon (2010)The vehicle routing problem (VRP) is to service a number of customers with a fleet of vehicles. The VRP is an important problem in the fields of transportation, distribution and logistics. Typically the VRP deals with the ...
Chong, Yen N. (2001)General routing problems deal with transporting some commodities and/or travelling along the axes of a given network in some optimal manner. In the modern world such problems arise in several contexts such as distribution ...
Grigoleit, Mark Ted (2008)The Constrained Shortest Path Problem (CSPP) consists of finding the shortest path in a graph or network that satisfies one or more resource constraints. Without these constraints, the shortest path problem can be solved ...