Research in the field of vehicle routing problem started in 1959. For more then 50 years a lot of versions of this problem have been considered and many solution methods have been developed. Unfortunately new management concepts continuously put out the challenge to vehicle routing researchers. Presented paper is divided into two parts. In the first part the classical vehiclerouting formulations and their solution methods were presented. In the second part the three main directions of advance are identified and briefly described. The new solution approaches to finding solution to the new variants of vehicle routing problem are proposed and tested. Firstly we conduct new solution methods to inventory routing problem. Then the common case of the vehicle routing problem in different distribution tariff environment is analyzed. Lastly the vehicle routing problem in multiechelon distribution networks is considered.