Two-phase variable neighborhood scatter search for the capacitated vehicle routing problem with stochastic demand
LI Yang
FAN Hou-ming
ZHANG Xiao-nan
YANG Xiang
Abstract：The capacitated vehicle routing problem with stochastic demand(CVRPSD)is an extension of capacitated vehicle routing problem(CVRP)which is a well-known NP-hard problem.Due to the stochastic characteristic of customer's demand,the solution process is evidently different from deterministic CVRP and it is rather complicated to be solved.Based on the principles of pre-optimization and re-dispatch,a two-stage variable neighborhood scatter search algorithm(VNSS) is proposed.In first stage,the stochastic chance constrained optimization model is constructed and the stochastic constrain of customer's demand is transformed to a certain constrain.On base of the equivalent formation,the optimal solutions of pre-optimization scheme are generated by VNSS and it could be participated in the re-dispatch optimization.In second stage,the paper proposes a new re-dispatch policy to deal with the so-called failure point in pre-optimization scheme.The failure point and the customers afterwards are re-optimized to avoid unnecessary vehicle routings which may cause extra costs and more vehicles.Numerical results show that the two-stage VNSS and re-dispatch policy is rather effective.
Keywords：vehicle routing problemstochastic demandre-dispatch policyscatter search algorithmvariable neigh-borhood search algorithm
Publication Date：2017-01-01
Online Publishing Date：2025-08-15(First online date of this platform, not the publication date of the document)
Pages：11( 1594-1604 )