Research On Prize Collecting Vehicle Routing Problem

With the implementation of the national "One Belt,One Road" policy and the promotion of the Internet,E-commerce has developed rapidly,making the logistics industry develop rapidly on a global scale.In the environment of E-commerce,order types have the characteristics of small batches,multiple batches,and diversity,which makes logistics and distribution problems more and more complicated,and the difficulty of distribution is increasing.At present,there are more than 1,000 domestic express companies carrying out related businesses,and the competition is particularly fierce.Therefore,more and more companies are beginning to pay attention to how to control costs for companies through reasonable planning of distribution routes.The determination of the distribution route is generally attributed to the Vehicle Routing Problem（VRP）.This paper considered the restrictions of delivery conditions in real life,the vehicle routing problem in the E-commerce environment has reduced to the prize collecting vehicle routing problem（PCVRP）,and the PC VRP has discussed from the following two aspects:（1）Static PCVRP problem:On the basis of the existing PCVRP problem model,this paper added the soft time window constraint,and the demand for pickup is increased on the basis of the delivery demand,and established the static model of prize collecting vehicle routing problem with time windows and simultaneous pickup and delivery.In the algorithm for solving the model,the simulated annealing algorithm and the large neighborhood search algorithm were mixed,and an adaptive mechanism was introduced in the search process.A heuristic algorithm based on adaptive large neighborhood search algorithm was proposed.Three sets of simulation experiments verified the effectiveness of the algorithm.（2）Dynamic PCVRP problem:Based on the static PCVRP problem model,this paper established PCVRP model of dynamic demand and dynamic travelling time.The dynamic PCVRP problem model has solved in two stages:the stage dynamic problem was to transform into a static PCVRP problem firstly,which was solved by an adaptive large neighborhood search algorithm;the second stage proposed local search algorithm and 2-opt algorithm to solve the problem.Experimental results showed that both algorithms are effective.