针对带软时间窗的随机需求车辆路径问题求解过程中存在的大规模车辆规划复杂度较高、规划时间较长、客户需求未知等问题,提出一种改进两阶段算法.第一阶段将客户随机需求作确定化处理,使其等于期望值,然后引入自适应禁忌长度、自适应惩罚系数和改进邻域结构,以解决车辆偏离时间窗问题,最后得到最初的规划方案,但该方案仍存在一定误差;第二阶段采用选择回配送中心算法修正第一阶段所求解的误差.实验结果表明,改进后的两阶段算法具有较强的寻优能力和较高的鲁棒性,能够快速找到合理的解决方案.