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

来源：计算机应用研究杂志2022年第7期北京时间：

作者：马俊,张纪会,郭乙运,

单位：1.青岛大学a.复杂性科学研究所;b.山东省工业控制技术重点实验室,山东青岛266071；2.青岛港国际股份有限公司,山东青岛266011；

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

关键词：车辆路径,客户分类,随机旅行及服务时间,机会约束,变邻域迭代局部搜索,

基金资助：国家自然科学基金资助项目(61673228,62072260)；青岛市科技计划资助项目(21-1-2-16-zhz)；；