A branch-and-regret heuristic for stochastic and dynamic vehicle routing problems

This paper describes a new Branch-and-Regret Heuristic for a class of dynamic and stochastic vehicle routing problems. This work is motivated by a real-life problem faced by a major transporter in Norway. The heuristic uses stochastic information during the solution process. The new method is shown to be superior to previous heuristics that are uniquely based on a pure dynamic approach. The proposed heuristic is well suited to problems containing stochastic customers, stochastic demands, or both. (c) 2007 Wiley Periodicals, Inc.