Abstract:
This paper considers the routing of vehicles with
limited capacity from a central depot to a set of geographically
dispersed customers where actual demand is revealed only
when the vehicle arrives at the customer. The solution to this
vehicle routing problem with stochastic demand (VRPSD)
involves the optimization of complete routing schedules with
minimum travel distance, driver remuneration, and number of
vehicles, subject to a number of constraints such as vehicle time
window and capacity. To solve such a multiobjective
combinatorial optimization problem, this paper presents a
multiobjective evolutionary algorithm that incorporates two
VRPSD-specific heuristics for local exploitation and a route
simulation method to evaluate the fitness of solutions. A novel
way of assessing the quality of solutions to the VRPSD on top of
comparing their expected costs is also proposed. It is shown
that the algorithm is capable of finding useful tradeoff solutions
which are robust to the stochastic nature of the problem.
