Performance evaluation of vehicle routing algorithms in a stochastic environment

The stochastic vehicle routing problem (VRP) is a problem of growing importance since it includes a reality that the deterministic VRP does not have. The stochastic VRP arises whenever some elements of the problem are random. Common examples are stochastic service quantities and stochastic travel times. The solution methodologies for the stochastic VRP are very intricate and regarded as computationally intractable. Even heuristics are hard to develop and implement. One possible way of solving it is to apply a solution for the deterministic VRP. This paper presents a performance evaluation of four simple heuristics for the deterministic VRP in a stochastic environment. The heuristics are modified to consider the time window constraints. The computational results show that some of them perform very well in different cases of the stochastic VRP.