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

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

作　　者：李阳[1] 范厚明[1] 张晓楠[2] 杨翔[1] 

机构地区：[1]大连海事大学交通工程学院,战略管理与系统规划研究所,大连116026 [2]陕西科技大学机电工程学院,西安710021

出　　处：《系统工程理论与实践》2018年第2期522-531,共10页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(61473053);辽宁省社会科学规划基金重点项目(L16AGL004);辽宁省教育厅科学技术研究一般项目(L2014046);大连市科学技术计划项目(2015D12ZC181)~~

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

关 键 词：车辆路径问题 模糊需求 点重调度策略 禁忌搜索算法 变邻域搜索算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]