Scatter search for the stochastic travel-time vehicle routing problem with simultaneous pick-ups and deliveries

In parallel with the growth of both domestic and international economies, there have been substantial efforts in making manufacturing and service industries more environmental friendly (i.e., promotion of environmental protection). Today manufacturers have become much more concerned with coordinating the operations of manufacturing (for new products) and recycling (for reuse of resources) together with scheduling the forward/reverse flows of goods over a supply chain network. The stochastic travel-time vehicle routing problem with simultaneous pick-ups and deliveries (STT-VRPSPD) is one of the major operations problems in bi-directional supply chain research. The STT-VRPSPD is a very challenging and difficult combinatorial optimization problem due to many reasons such as a non-monotonic increase or decrease of vehicle capacity and the stochasticity of travel times. In this paper, we develop a new scatter search (SS) approach for the STT-VRPSPD by incorporating a new chance-constrained programming method. A generic genetic algorithm (GA) approach for STT-VRPSPD is also developed and used as a reference for performance comparison. The Dethloff data will be used to evaluate the performance characteristics of both SS and GA approaches. The computational results suggest that the SS solutions are superior to the GA solutions.

► We propose the stochastic travel-time vehicle routing problem with simultaneous pick-ups and deliveries (STT-VRPSPD), and construct a chance-constrained programming model to transform the dynamic problem to a static problem.
► We develop a new scatter search (SS) approach for the STT-VRPSPD by incorporating a new chance-constrained programming method.
► Our SS framework includes constructing new solution improvement and combination strategies as well as improving the C–W algorithm to more effectively construct initial good solutions. These efforts make our SS framework suitable for the STT-VRPSPD as it can effectively deal with the stochasticity of travel times and the fluctuating capacity loads.