两阶段混合优化算法求解模糊需求下多时间窗车辆路径问题

Two stage hybrid optimization algorithm for vehicle routing problem with multiple time windows under fuzzy demand

针对现实中广泛存在的一类模糊需求下多时间窗车辆路径问题(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的第1阶段设计改进灰狼优化算法(improved grey wolf optimizer, IGWO)求解车辆配送前客户需求模糊的VRPMTW,以获得VRPMTW_FD的预优化路径;然后,在TSHOA的第2阶段设计最优点重调度策略(optimal point rescheduling strategy, OPRS),对预优化路径进行动态调整,从而确定合适的返回点以降低因预优化路径故障产生的额外配送成本.通过不同规模问题上的仿真实验和算法比较,验证了TSHOA可有效求解VRPMTW_FD.

Aiming at a type of vehicle routing problems with multiple time windows under fuzzy demand(VRPMTW_FD)that exists widely in reality, which is that 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 the 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 the TSHOA designs an improved gray wolf optimizer(IGWO)to solve the VRPMTW with fuzzy customer demand before vehicle delivery, to obtain the pre-optimized path of the VRPMTW_FD. Then, in the second stage of the TSHOA, the optimal point rescheduling strategy(OPRS) is designed to dynamically adjust the pre-optimized path, so as to determine the appropriate return point to reduce the additional distribution cost due to the failure of the pre-optimized path. Through simulation experiments and algorithm comparisons on different scale problems, it is verified that the TSHOA can effectively solve the VRPMTW_FD.