关键词: 随机动态装卸, 车辆路径问题, 启发式策略, 排队论

Abstract: A mathematical model of the stochastic dynamic pick-up and delivery vehicle routing problem was established, with minimizing the expected waiting time of customers and that of vehicles simultaneously as the objective function. Two heuristics policies, the nearest neighbor policies and the stacker crane policies, were proposed to solve this problem. The upper bounds of the two policies were calculated. A simulation was carried out to analyze the performance of the two policies under different traffic intensity circumstances and to analyze the relationship between the objective function and parameters of each strategy. The simulation showed that the nearest neighbor strategy was superior to the stacker crane strategy when the traffic intensity was light and heavy, otherwise the stacker crane strategy was better; each strategy had its own optimal traffic intensity, and the optimal traffic intensity of nearest neighbor strategy was bigger than that of stacker crane strategy; stacker crane strategy had an optimal stack length, which was impacted by the traffic intensity and the average arrival rate of customers at the same time.

Key words: stochastic dynamic pick-up, delivery vehicle routing problem, heuristics policies, queuing theory, simulation