A priori policy evaluation and cyclic-order-based simulated annealing for the multi-compartment vehicle routing problem with stochastic demands

We develop methods to estimate and exactly calculate the expected cost of a priori policies for the multi-compartment vehicle routing problem with stochastic demands, an extension of the classical vehicle routing problem where customer demands are uncertain and products must be transported in separate partitions. We incorporate our estimation procedure into a cyclic-order-based simulated annealing algorithm, significantly improving the best-known solution values for a set of benchmark problems. We also extend the updating procedure for a cyclic order’s candidate route set to duration-constrained a priori policies.