A simheuristic approach for the two-dimensional vehicle routing problem with stochastic travel times

The two-dimensional vehicle routing problem (2L-VRP) is a realistic extension of the classical vehicle routing problem in which customers’ demands are composed by sets of non-stackable items. Examples can be found in real-life applications such as the transportation of furniture or industrial machinery. Often, it is necessary to consider stochastic travel times due to traffic conditions or customers availability. However, there is a lack of works discussing stochastic versions of the 2L-VRP. This paper offers a model of the 2L-VRP with stochastic travel times that also includes penalty costs generated by overtime. To solve this stochastic and non-smooth version of the 2L-VRP, a hybrid simheuristic algorithm is proposed. Our approach combines Monte Carlo simulation, an iterated local search framework, and biased-randomised routing and packing heuristics. Our algorithm is tested on an extensive benchmark, which extends the deterministic one for the 2L-VRP with unrestricted and non-oriented loading.