| dc.description.abstract | Abstract
In this thesis, models have been formulated and mathematical optimization
methods developed for the heterogeneous vehicle routing problem
with a very large set of available vehicle types, called many-hVRP. This
is an extension of the standard heterogeneous vehicle routing problem
(hVRP), in which typically fairly small sets of vehicle types are considered.
Two mathematical models based on standard models for the hVRP
have been formulated for the many-hVRP. Column generation and dynamic
programming have been applied to both these models, following a
successful algorithm for the hVRP. Benders' decomposition algorithm has
also been applied to one of the models. In addition to the standard cost
structure, where the cost of a pair of a vehicle and a route is determined
by the length of the route and the vehicle type, we have studied costs that
depend also on the load of the vehicle along the route. These load dependent
costs were easily incorporated into the models, and other extensions
could be similarly incorporated.
By using a standard set of test instances (with between three and
six vehicle types in each instance) we have been able to compare our
implementation with published results for hVRP. For many-hVRP, we
have extended these instances to include larger sets of vehicle types (with
between 91 and 381 vehicle types in each instance). The results show that
the algorithms implemented for the two models nd optimal solutions in
a similar amount of time, but Benders' algorithm at times takes much
longer to verify optimality. However, some other properties of Benders'
algorithm suggests that it may constitute a good basis for a heuristic,
when instances with even larger sets of vehicle types are used. | sv |
