School of Information Engineering and Automation, Kunming University of Science and Technology
The National Natural Science Foundation of China (General Program, Key Program, Major Research Plan)
针对现实中广泛存在的一类模糊需求下多时间窗车辆路径问题(Vehicle routing problem with multiple time windows under fuzzy demand, VRPMTW_FD), 即车辆配送前客户需求模糊但车辆到达客户后其需求变为确定的多时间窗车辆路径问题(Vehicle routing problem with multiple time windows, VRPMTW), 以最小化总成本为优化目标, 构建基于模糊可信性理论的模糊机会约束规划模型, 并提出一种两阶段混合优化算法(Two-stage hybrid optimization algorithm, TSHOA)进行求解. 首先, TSHOA的第一阶段设计改进灰狼优化算法(Improved grey wolf optimization algorithm, IGWO)求解车辆配送前客户需求模糊的VRPMTW, 以获得VRPMTW_FD的预优化路径. 然后, TSHOA的第二阶段设计最优点重调度策略(Optimal point rescheduling strategy, OPRS)对预优化路径进行动态调整, 从而确定合适的返回点降低因预优化路径故障产生的额外配送成本. 通过不同规模问题上的仿真实验和算法比较, 验证了TSHOA可有效求解VRPMTW_FD.
Aiming at a type of vehicle routing problem with multiple time windows under fuzzy demand (VRPMTW_FD) that exists widely in reality, that is the customer demand is fuzzy before the vehicle is delivered, but the customer demand becomes definite after the vehicle reaches the customer, a fuzzy chance constrained programming model based on fuzzy credibility theory is constructed to minimize the total cost, and a two-stage hybrid optimization algorithm (TSHOA) is proposed to solve it. Firstly, the first stage of TSHOA designs an improved gray wolf optimization algorithm (IGWO) to solve the VRPMTW with fuzzy customer demand before vehicle delivery, to obtain the pre-optimized path of VRPMTW_FD. Then, in the second stage of TSHOA, the optimal point rescheduling strategy (OPRS) is proposed to dynamically adjust the pre optimized path, so as to determine the appropriate return point and reduce the additional cost caused by the failure of the pre optimized path due to the fuzzy customer demand. Through simulation experiments and algorithm comparisons on different scale problems, it is verified that TSHOA can effectively solve VRPMTW_FD.