The vehicle routing problem with simultaneous pickup-delivery and soft time windows (VRPSPDSTW) is typical of NP-hard combination problem. Aimed at the problems that convergence speed is slow and easy to fall into local optimum value at the later stage for standard cuckoo search algorithm (CS), this paper puts an improved strategy based on the mixture of saving algorithm and stochastic probability in initialization, and adopts the dynamic discovery probability and variation mechanism of pheromone orientation. The performance of the modified cuckoo search algorithm (MCS) is proved by quantitative test. And then the modified algorithm is applied to solve the vehicle routing problem with simultaneous pickupdelivery and soft time windows, compared with the existing algorithm, and the superiority of the modified cuckoo algorithm in practical engineering is verified.