文章编号
带 收 益 的 车 辆 路 径 问 题 研 究 综 述
李琳
刘涛
沈阳航空航天大学 理学院 辽宁 沈阳 东北大学 材料与冶金学院 辽宁 沈阳
摘要车辆路径问题是企业实现物流配送的关键环节对带收益的车辆路径问题的研究进行了
综述 根据目前该问题的研究进展对相关的研究进行了分类分析了该类问题的特点探讨了
相应的 整数规划模型及集划分模型总结了求解该问题的精确算法与启发式算法 介绍了
该问题在实际中的应用展望了其研究前景为相关研究指出了方向
关键词带收益的车辆路径问题 数学模型 精确算法 启发式算法
中图分类号TP
doi jissn
文献标识码A
车辆路径问题是物流配送过程中的关键环
节选取适当的车辆路径可以加快对顾客需求的
响应速度提高企业的服务质量增加客户对物流
环节的满意度对降低企业的运作成本提高企业
形象及其竞争力具有十分重要的意义
车辆路径问题是由 Dantzig
首次提出的其
一般定义为对一系列发货点和收货点组织适当的
行车路线使车辆有序地通过它们在满足指定的
约束条件下 如货物需求量发送量交发货时
间车辆的容量限制行驶里程限制行驶时间限
制等实现一定的目标行驶路程最短总运费最
少总行驶时间最少总使用车辆数最少等 该
问题的特点是每个顾客点都被访问到一次且只能
由一辆车访问 实际问题中存在这样一类问题
车辆数目一定由于车辆最长服务时间或最大容
量等方面的限制车辆在相关约束条件下只能访
问部分顾客点而每辆车在访问某一顾客点时会
得到相应的收益每个顾客点只能由一辆车访问
因此需要讨论在满足车辆相应约束的条件下收
益最大的车辆路径问题即带收益的车辆路径问
题
Vehicle Routing Problem with Profits VR
PP 该问题也常称作可选择的车辆路径问题
Selective Vehicle Routing Problem SVRP或多环
游路径最大收集问题
multiple tour maximum
collection problem
收稿日期
基金项目国家自然科学基金资助项目项目编号
作者简介李琳 女吉 林 吉林人讲师主 要 研 究 方向
系统建模算法优化E mailLLcom
带收益的车辆路径问题分类及数
学模型
VRPP 的分类
根据问题的目标函数及其约束情况可将该
问题分为以下 类
多目标带收益的车辆路径问题 目标函
数为最小化总的车辆行驶费用最大化总的利润
收益等 多目标问题也可以通过加权使其转化为
单目标问题 当仅有一辆车时该类问题又称为
带收益的环游问题
profitable tour problem
若将车辆行驶费用作为约束条件在行
驶费用不超过现有费用 C
max
的条件下使总收益
最大 当车辆数为 时该问题又称为定向越野
竞赛问题
orienteering problem
若将收益作为约束条件在收益不小于
价值 R
min
的条件下使总的行驶费用最小 当车
辆数为 时该问题又成为奖金收集旅行商问
题
prize collecting TSP
VRPP 的数学模型
整数规划模型
设一完全图 GN AN n为
节点集合其中节点 为车场共有 n 个顾客点
弧集合 A ij ijN
第一类问题的模型如下
MaxZ
k
iN
p
i
y
k
i
iN
jN
i j
d
ij
x
k
ij
年月
第 卷第期
沈阳航空工业学院学报
Journal of Shenyang Institute of Aeronautical Engineering
Oct
VolNo