考虑随机旅行时间与二维装载约束的越库配送车辆路径优化

面向越库配送模式下二维装载和车辆路径联合优化,考虑现实配送过程的不确定性因素,提出考虑随机旅行时间和二维装载约束的越库配送车辆路径问题.基于蒙特卡洛模拟与场景分析方法,建立以运输成本、车辆固定成本以及时间窗期望惩罚成本之和最小化为目标的带修正随机规划模型.继而根据问题特征,设计改进的自适应禁忌搜索算法和基于禁忌搜索的多重排序最佳适应装箱算法进行求解.其中,改进的自适应禁忌搜索算法在禁忌搜索算法的基础上引入自适应机制,对不同邻域算子进行动态选择,并提出基于移除-修复策略的多样性机制以增强算法的寻优能力.数值实验表明,所提出的模型与方法能够有效求解考虑随机旅行时间和二维装载约束的越库配送车辆路径问题,自适应与多样性机制能一定程度上增强算法的全局搜索能力.

Optimization for two-dimensional loading constrained vehicle routing problem with cross-docking and stochastic travel time

Considering uncertainties in the real-life distribution applications, this paper studies the joint optimization of two-dimensional loading and vehicle routing with cross-docking, and for the first time presents a two-dimensional loading constrained vehicle routing problem with cross-docking and a stochastic travel time(2L-VRPCDSTT). Based on Monte Carlo simulations and a scenario analysis method, a stochastic programming model with recourse(SPR) for the 2L-VRPCDSTT is formulated, aiming to minimize the total transportation cost, fixed cost of vehicles and expected penalty cost of time window. According to the characteristics of the 2L-VRPCDSTT, an improved adaptive tabu search(IATS) algorithm incorporating a tabu-based multi-order best-fit(TSMOBF) packing heuristic is proposed to solve this problem. In the proposed algorithm, an adaptive mechanism is embedded to dynamically select different neighborhood operators, and a diversification mechanism based on the remove-reinsert strategy is proposed to enhance the exploitation capability of the algorithm. Experimental results show that the proposed SPR model and hybrid method can efficiently solve the 2L-VRPCDSTT, and that the adaptive mechanism and diversification mechanism are capable of enhancing the global search capability of the algorithm.