The Stochastic Multi-Path Vehicle Routing Problem and Its Algorithm
To better fit the realistic urban distribution operation environment,this article conducts a new extended study on the classic vehicle routing problem,considering the situation where there are multiple paths with uncertain travel costs between any two logistics nodes.A stochastic multi-path vehicle routing problem(SMP-VRP)model is established,and a two-stage algorithm with high solution efficiency is designed for the studied problem.In the first stage of the algorithm,a constrained K-means algorithm is used to group customers and convert the SMP-VRP problem to a stochastic multi-path traveling salesman problem(SMP-TSP).In the second stage of the algorithm,the SMP-TSP problem is firstly converted into an equivalent scenario planning problem,and then approximated into a deterministic planning problem;the solution of the SMP-TSP problem is used to obtain the solution of the SMP-VRP problem.Case studies show that compared with the delivery organization method using a greedy strategy,the two-stage algorithm proposed in this article can reduce the average delivery cost by around 7%and exhibits good stability.This algorithm provides a new research approach to the vehicle routing optimization in logistics delivery and has strong practical value.
万方数据
维普
