To the top

Page Manager: Webmaster
Last update: 9/11/2012 3:13 PM

Tell a friend about this page
Print version

Modeling and solving vehi… - University of Gothenburg, Sweden Till startsida
To content Read more about how we use cookies on

Modeling and solving vehicle routing problems with many available vehicle types

Conference paper
Authors Sandra Eriksson Barman
Peter Lindroth
Ann-Brith Strömberg
Published in Springer Proceedings in Mathematics & Statistics
ISBN 978-3-319-18566-8
ISSN 2194-1009
Publisher Springer International Publishing
Publication year 2015
Published at Department of Mathematical Sciences, Mathematical Statistics
Department of Mathematical Sciences, Mathematics
Language en
Keywords Vehicle routing problem, fleet size and mix, heterogeneous fleet, many vehicle types, set partitioning, Benders decomposition, projection of routes
Subject categories Optimization, systems theory


Vehicle routing problems (VRP) involving the selection of vehicles from a large set of vehicle types are hitherto not well-studied in the literature. Such problems arise at Volvo Group Trucks Technology, who faces an immense set of possible vehicle configurations, of which an optimal set needs to be chosen for each specific combination of transport missions. Another property of real-world VRP’s that is often neglected in the literature is that the fuel resources required to drive a vehicle along a route is highly dependent on the actual load of the vehicle.

We define the fleet size and mix VRP with many available vehicle types, called many-FSMVRP, and suggest an extended set-partitioning model of this computationally demanding combinatorial optimization problem. To solve the extended model, we have developed a method based on Benders’ decomposition, the subproblems of which are solved using column generation, and the column generation subproblems being solved using dynamic programming; the method is implemented with a so-called projection-of-routes procedure. The resulting method is compared with a column generation approach for the standard set-partitioning model. Our method for the extended model performs on par with column generation applied to the standard model for instances such that the two models are equivalent. In addition, the utility of the extended model for instances with very many available vehicle types is demonstrated. Our method is also shown to efficiently handle cases in which the costs are dependent on the load of the vehicle.

Computational tests on a set of extended standard test instances show that our method, based on Benders’ algorithm, is able to determine combinations of vehicles and routes that are optimal to a relaxation (w.r.t. the route decision variables) of the extended model. Our exact implementation of Benders’ algorithm appears, however, too slow when the number of customers grows. To improve its performance, we suggest that relaxed versions of the column generation subproblems are solved, and that the set-partitioning model is replaced by a set-covering model.

Page Manager: Webmaster|Last update: 9/11/2012

The University of Gothenburg uses cookies to provide you with the best possible user experience. By continuing on this website, you approve of our use of cookies.  What are cookies?