带时间窗和服务顺序约束的多需求车辆路径问题

摘要

研究顾客具有多种需求,分别需要由不同类型车辆提供服务,且同一顾客多种需求的服务时间具有固定先后顺序的车辆路径问题。在考虑各个顾客需求的服务时间窗,同一顾客不同需求的服务顺序、服务时间间隔,以及各种车型的车容量及最大行驶时间等约束的前提下,以满足顾客多种需求的车辆运行成本和等待成本之和极小化为目标,建立混合整数规划模型。进一步设计求解模型的联合优化遗传算法,并利用车辆路径问题的标准测试集构造具有两种需求的测试算例,分别利用所提出的联合优化遗传算法与文献中的两阶段遗传算法进行模拟计算与分析,验证所提出算法的有效性。将经典的单一需求车辆路径问题推广到多种需求的情形,建立带约束的多需求车辆路径问题的数学模型并设计求解模型的有效算法,为解决实际问题提供了决策依据。