变动补偿的多模糊选址-路径机会约束模型及算法

针对同时具有模糊需求和模糊旅行时间,且有车辆容量、配送中心容量和时间窗约束的选址-路径问题,基于预优化和实时调整的两阶段策略,引入变动成本的概念,建立变动补偿的机会约束预优化模型.在实时调整阶段,考虑多模糊参数的联合影响,定义变动成本为因车辆剩余容量不足返回配送中心卸载的额外配送成本和因车辆实际到达时间超出客户时间窗的时间惩罚成本总和.鉴于多模糊参数影响的时间窗可信度计算复杂,且已将时间惩罚成本作为变动成本的一部分修正目标函数,去掉时间窗机会约束,设计一阶段模拟退火算法求解,贪婪聚类构建初始解,随机模拟法估算变动成本.测试算例验证了模型和算法的有效性.得出,该模型可弱化偏好值的影响,生成实时调整变动幅度小且整体最优的预优化方案,提高对不确定环境的风险抵抗力,且求解简单;该算法是求解此类问题的较好算法;研究成果为多模糊选址-路径问题提供新的求解思路.

Chance-constrained model and algorithm for LRP with multiple fuzzy variables under change-reward

This paper studies the capacitated location-routing problem with time window under fuzzy demand and fuzzy travel times (CLRPTWFD&FTT). Firstly, based on pre-optimization and real-time adjustment strategies, the concept of change cost is proposed, and a chance-constrained model with change-reward is presented in the pre-optimization phase. Secondly, considering the comprehensive impact of fuzzy variables in real-time adjustment phase, change cost is set as the sum of additional delivery cost and time penalty cost, which are caused by vehicle midway returning and arrival time beyond the time window respectively. Thirdly, owing to the complex calculations and modification for objective function, the time window chance constraint is removed. To solve the model, a one-phase simulated annealing algorithm is developed, greedy clustering is used to construct the initial solution, and stochastic simulation method is applied to estimate change cost. Finally, the validity of the model and algorithm are attested. The model can weaken the effects of preference index, obtain a pre-optimization solution with small real-time adjustment cost variance and overall optimum value, and improve risk resistance responding to uncertain environment. Moreover, it is easy to be solved. The algorithm has good performance. Research results provide new ideas for solving LRP with multiple fuzzy variables.