带软时间窗的随机需求车辆路径问题的算法研究

作     者：李国明 李军华 

作者机构：南昌航空大学江西省图像处理与模式识别重点实验室 

出 版 物：《计算机集成制造系统》 (Computer Integrated Manufacturing Systems)

年 卷 期：2021年

核心收录：

学科分类：02[经济学] 0202[经济学-应用经济学] 020205[经济学-产业经济学] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基　　金：国家自然科学基金资助项目(61440049，61866025，61866026) 江西省自然科学基金资助项目(20181BAB202025) 江西省优势科技创新团队计划资助项目(20181BCB24008) 

主　　题：随机需求 禁忌搜索 修正算法 车辆路径问题 

摘      要：带软时间窗的随机需求车辆路径问题(Vehicle Routing Problem with Stochastic Demand and Soft Time Window，VRPSD-STW)，旨在求解在客户需求未知下车辆准时到达指定地点，并且要求规划时间最短、修正成本最少、违背约束最小，是目前最具有挑战性的多约束组合优化问题之一。针对求解过程中大规模车辆规划复杂度较高、规划时间较长，客户需求未知等问题，提出一种改进两阶段算法。第一阶段将客户随机需求作确定化处理，使其等于期望值；然后，引入自适应禁忌长度，自适应惩罚系数及改进邻域结构以解决车辆偏离软时间问题，最后得到最初的规划方案，但该方案仍存在一定的误差。第二阶段采用SRTD算法(Select Return To Depot)对第一阶段所求解的误差进行修正。实验结果表明，改进后的两阶段算法具有较强的寻优能力、较高的鲁棒性，且能够快速地找到合理的解决方案。