考虑客户分类的随机时间车辆路径优化模型与算法

针对一类考虑客户分类、随机旅行时间、随机服务时间及时间窗约束的车辆路径问题构建了机会约束规划模型，该模型考虑两类客户（普通客户与优质客户）并通过添加机会约束条件确保优质客户获得准时服务的概率。同时，设计了变邻域迭代局部搜索算法，并给出了一种基于最小等待时间的初始解生成启发式规则。基于Solomon算例进行了多组仿真实验。仿真实验结果表明，所设计生成初始解的启发式规则是有效的；所给算法能够在短时间内找到确定问题和随机问题的近似最优解；客户比与车辆使用数目呈正相关关系。研究结果对解决资源有限条件下克服随机不确定性因素带来的不利影响、保证客户服务水平等问题有一定的参考意义。

Optimization model and algorithm for vehicle routing problem with stochastic time and customer classification

For the vehicle routing problem with time window, stochastic travel and service time, and customer classification, this paper constructed a chance constrained programming model, which considered two class customers(ordinary customers and priority customers) and adopted the chance constraint to guarantee the punctual service possibility of priority customers. Meanwhile, this paper designed a variable neighborhood iterated local search algorithm to solve the model, and proposed a minimum waiting time heuristic rule to generate initial solution. Based on Solomon benchmarks, it conducted series of simulation experiments. The results show that the initial solution generation method is valid, the given algorithm can get approximate optimal solutions for both of the deterministic and stochastic problems in a short time, and the customer ratio is positively relative to the number of vehicle usage. The results have a certain reference significance to solve the problem of low customer service level caused by the limited resources and uncertain factors.