摘要
研究顾客具有多种需求,分别需要由不同类型车辆提供服务,且同一顾客多种需求的服务时间具有固定先后顺序的车辆路径问题。在考虑各个顾客需求的服务时间窗,同一顾客不同需求的服务顺序、服务时间间隔,以及各种车型的车容量及最大行驶时间等约束的前提下,以满足顾客多种需求的车辆运行成本和等待成本之和极小化为目标,建立混合整数规划模型。进一步设计求解模型的联合优化遗传算法,并利用车辆路径问题的标准测试集构造具有两种需求的测试算例,分别利用所提出的联合优化遗传算法与文献中的两阶段遗传算法进行模拟计算与分析,验证所提出算法的有效性。将经典的单一需求车辆路径问题推广到多种需求的情形,建立带约束的多需求车辆路径问题的数学模型并设计求解模型的有效算法,为解决实际问题提供了决策依据。
A vehicle routing problem with multiple demands is investigated, where each type of demand needs a special type of vehicles to provide service and the service order of one customer’s multiple demands is fixed. Considering the constraints of time windows, the service order of multiple demands, the interval between different service, the capacity and total running time of each vehicle, a mix integer programming model is formulated to minimize the total costs of all vehicles. A joint optimal genetic algorithm is developed for solving the model. The effectiveness of the algorithm is verified by simulations on instances with two types of demands derived from the VRP benchmarks. This paper not only extends the classical single-demand vehicle routing problem to the multiple demands case, but also formulates a mathematical model of the multiple demands vehicle routing problem with constraints and designs an effective algorithm for solving the model, which provides a decision basis for solving practical problems.
作者
李珍萍
张煜炜
LI Zhen-ping;ZHANG Yu-wei(College of Information Science, Beijing Wuzi University, Beying 101149, China)
出处
《控制与决策》
EI
CSCD
北大核心
2019年第7期1565-1570,共6页
Control and Decision
基金
国家自然科学基金项目(71771028)
2018年北京市属高校高水平教师队伍建设支持计划-创新团队项目(IDHT20180510)
2018年北京市自然科学基金重点研究专题项目(Z18J0008)
关键词
多需求
时间窗
服务顺序约束
车辆路径问题
混合整数规划
联合优化遗传算法
multiple demands
time windows
service order constraint
vehicle routing problem
mixed integer programming
joint optimal genetic algorithm
