Stochastic Travel-time Vehicle Routing Problem with Simultaneous Pick-up and Delivery Considering Soft Time Windows

Abstract:

According to the constraints of the total vehicle travel time， vehicle load， and the soft time windows， we studied the stochastic travel-time vehicle routing problem with simultaneous pick-up and delivery （STT-VRPSPD） considering soft time windows and established a chance-constrained programming model. Combining the tabu search algorithm with the scatter search algorithm， a hybrid scatter tabu search （HSTS） algorithm was constructed， and the C-W saving algorithm was used to generate initial solutions. Based on the classic Dethloff instances and Solomon time window generation method， 20 groups of instances including 50 customers and 20 groups of instances including 200 customers were generated respectively for numerical tests. The numerical results verify the effectiveness of the HSTS algorithm.