求解模糊需求车辆路径问题的两阶段变邻域禁忌搜索算法

模糊需求车辆路径问题(CVRPFD)是对带容量约束车辆路径问题(CVRP)的扩展,属于经典的NP难题,其求解与需求确定CVRP区别较大,较为复杂,具有很强的理论和现实意义.基于先预优化后重调度的思想,提出一种新的两阶段变邻域禁忌搜索算法(VNTS)对其求解:在预优化阶段,基于可信性理论构建模糊机会约束优化模型处理客户点模糊需求,设计VNTS求解预优化方案;在重调度阶段,设计随机模拟算法模拟客户点实际需求,提出一种新的点重调度策略对预优化方案进行调整.算例实验表明两阶段变邻域禁忌搜索算法是一种求解CVRPFD的有力工具,点重调度策略调整效果较佳.

Two-phase variable neighborhood tabu search for the capacitated vehicle routing problem with fuzzy demand

The capacitated vehicle routing problem with fuzzy demand (CVRPFD) is an extension of capacitated vehicle routing problem (CVRP) which is a well-known NP-hard problem. Due to the fuzzy characteristic of customer's demand the solution process is evidently different from definitive CVRP that it is very complicated to be solved. Based on the principles of pre-optimization and re-dispatch, a two-stage variable neighborhood tabu search algorithm (VNTS) was proposed. In first stage, the fuzzy chance constrained optimization model was constructed on the basis of fuzzy credibility theory. The model insures that fuzzy demand of customers can participate in optimization so CVRPFD can be connected with conventional optimization methods. On base of the fuzzy chance constrained optimization model, pre-optimization schemes were generated by VNTS. In second stage, demand in customers was recognized and due to its fuzzy property, the confirmed demand may be beyond the capability of vehicle. The paper proposed a new failure point re-dispatch policy to deal with the so called failure point in pre-optimization schemes. The failure point and the customers after it intra-line were re-optimized to avoid unnecessary vehicle routings which may cause extra staff and more vehicles. Numerical results show that the two-stage VNTS and re-dispatch policy is rather effective.