没有合适的资源?快使用搜索试试~ 我知道了~
两阶段算法求解多车场车辆路径问题.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 96 浏览量
2022-11-04
16:44:56
上传
评论
收藏 575KB DOCX 举报
温馨提示
试读
14页
两阶段算法求解多车场车辆路径问题.docx
资源推荐
资源详情
资源评论
0 引言
传统的车辆路径问题(vehicle routing problem,VRP)由 Dantzig 和 Ramser 于 1959 年首次提出
[1]
.
该问题主要描述为:在满足车辆载重、容积、行使里程及客户服务要求等条件的同时,合理调度车辆出行
数量、行车路线、出行时间,使得运输总成本最优化.由于 VRP 为 NP-hard 问题,而多车场车辆路径问题
(multi-depot vehicle routing problem,MDVRP)可归约为 VRP,故 MDVRP 也属于 NP-hard 问题.已有研
究表明,对仅含 20 个客户的小规模 VRP,传统数学规划方法已需要很长时间求解
[2]
.因此,为在较短时间
内获得该问题不同客户规模的解,本文设计两阶段算法求解 MDVRP.
在已有的 MDVRP 研究中,由于问题的复杂性,因此对问题进行整体求解,所设计的编码解码方式
通常较为复杂;此外,相比单车场问题,多车场问题的解空间更加庞大,仅依靠智能算法自身进化机制难
以快速引导算法发现优质解区域.这两方面因素导致了算法的执行和搜索效率降低.针对这一问题,为降低
问题的求解复杂度的同时还能有效引导算法向优质解区域搜索,近年部分学者提出了一些分解策略,比如
最近邻算法(nearest neighbor algorithm,NNA)与 K 均值(K-means)算法,先把 MDVRP 分解为一系列子
问题(单个车场 VRP),然后提出相应算法求解该子问题.例如,Geetha 等
[3]
在所提混合遗传算法的初始化
过程中,采用 NNA 对客户划分,把距离某车场较近的客户归为由该车场服务,从而得到一系列单车场
VRP,然后再利用 PSO 对各单车场 VRP 进行求解. Geetha 等
[4]
采用改进的 K 均值算法先对客户进行聚
类,然后再利用结合遗传操作的 PSO 算法对聚类得到的各单车场 VRP 进行求解. Wang 等
[5]
在求解两阶
段多车场车辆配送问题(先求解选址问题,再进行路径规划)中,首先建立考虑最小化成本和最大化客户满
意度的双目标模型,然后在选址阶段利用改进的 K 均值算法对客户聚类并进行车场的选址,聚类过程中
考虑顾客的位置和购买行为并挖掘它们之间的相似特征,应用指数平滑法预测顾客的周期性需求,最后在
路径规划阶段提出了改进的非支配排序遗传算法(M-NSGA-II)求解.上述文献分别单独采用 NNA 或 K 均值
对 MDVRP 进行分解从而控制了问题的可行解空间规模同时降低了问题的复杂度,但仍存在一些不足:文
[3]采用 NNA 对 MDVRP 进行分解,虽可得到离车场较近的客户群,但忽略了客户的密度信息,容易导致
客户群中的客户分布较散,使得车辆在各客户之间的运输距离增加;文[4-5]采用基于 K 均值聚类分解的
方法对 MDVRP 进行分解,虽可获得较为密集的客户分布,但忽略了客户群和车场之间的距离因素,容易
导致客户群聚类重心位置距离车场较远,使得车辆从车场到各客户之间的运输距离增加.通过上述分析得
出,将二者有效且合理的结合是弥补以上两类分解算法不足的关键.
蚁群算法(ant colony optimization,ACO)是一种模拟蚂蚁寻找食物的群智能优化算法,最早由
Dorigo
[6]
提出.由于具有良好的全局搜索能力,ACO 已在多种 VRP 上得到应用.例如,Yu 等
[7]
提出了一种
带有蚂蚁重量策略和变异操作的并行蚁群算法,求解多车场绿色车辆路径问题. Yu 等
[8]
对文[7]的算法进行
改进,进而用其求解动态多车场车辆路径问题.陈希琼等
[9]
针对取送货车辆路径问题,建立了同时考虑车辆
容量和距离约束的双目标模型,并利用改进的蚁群算法进行求解.此外,为提高 ACO 的全局搜索能力,一
些学者设计自适应蚁群算法用于求解车辆调度问题.例如,王颖等
[10]
提出了一种自适应蚁群算法,在信息
素更新公式中加入信息素挥发系数调节策略,实验证明该算法的全局搜索性能与收敛速度均都有所提高.
Liu 等
[11]
采用了文[10]的信息素更新公式并用于求解 TSP,实验证明采用信息素浓度挥发调节策略的蚁群
算法具有良好的性能和收敛速度.从 ACO 在 VRP 系列问题上的研究现状来看,采用合理的信息素浓度计
算策略可控制全局搜索的方向,引入基于有效邻域操作的局部搜索能进一步提高算法性能,两者是设计有
效 ACO 的关键.同时,文[9, 11]虽然通过调节信息素浓度挥发系数使得信息素浓度可动态更新,但其更新
速率不可根据实际运行效果进行动态调节,故其信息素更新策略可进一步改进.
借鉴上述文献“先分解,再求解”的思想,本文提出两阶段算法(two-stage algorithm,TSA)用于求解
MDVRP. TSA 的结构如图 1 所示(以两车场为例),TSA 由问题分解阶段和子问题求解阶段组成. 1)在问题
分解阶段,为确保分解后的各子问题区域尽量覆盖解空间中的优质解区域,基于 NNA 与聚类分解算法各
自的特点,设计一种基于混合高斯聚类算法(Hybrid Gaussian Mixture model cluster with nearest
neighbor Algorithm,HGMA),用于为每个车场分配一定数量的客户,从而形成一系列单个车场 VRPs.
HGMA 同时考虑客户分布规律及车场与各客户间的距离关系,将 GMM 聚类后生成概率较小的客户利用
NAA 重新分配,并设计合理的车场分配规则,使得车场分配客户更加合理以获得更优质的子问题解空间.
2)在问题求解阶段,利用 EACO(enhanced hybrid ant colony optimization)对每个子问题(即 VRP)解区域
进行全局搜索,该算法引入信息素挥发系数控制因子以进一步调节信息素挥发系数取值,从而有效控制信
息素挥发进而避免算法过早收敛并引导算法全局搜索到达更多的不同区域;此外在全局搜索的基础上设计
两阶段局部搜索策略(two-stage variable neighborhood search,TVNS)以对子问题解区域进行细致且高效
的搜索,TVNS 基于不同车辆之间以及相同车辆内部间进行变邻域操作以扩大解区域的搜索范围从而提高
解的质量.最后,通过仿真实验和算法比较,验证了所提 TSA 的有效性.
图 1 TSA 结构 Fig.1 Framework of TSA
图选项
1 MDVRP 问题描述及数学模型
本节将对优化目标为最小化运输总成本的 MDVRP 进行介绍.
1.1 MDVRP 问题描述及相关假设
本文研究的车辆路径问题主要考虑了多车场因素,该问题在已知客户的位置坐标、多个车场的位置
坐标、客户货物需求量的情况下,规划出最满意的配送路线,从而使运输总成本达到最优.在配送过程中
应满足问题假设:
1) 车辆在一次任务分配中仅进行一次配送.
2) 车辆配送中负载不能超过车辆的最大装载限制.
3) 车辆从车场出发,完成服务后需回到原车场.
4) 每个客户都被服务,被服务的次数有且仅有一次.
1.2 MDVRP 数学模型建立
MDVRP 运输总成本由运输距离费用构成.该问题的数学模型为
(1)
(2)
(3)
(4)
(5)
(6)
决策变量:
(7)
其中,目标函数式(1)表示为最小化运输总成本;约束(2)表示从某车场出发的车辆数目和回到该车场
的车辆数目相等,且小于等于某车场的车辆总数;约束(3)和约束(4)共同表示任意一个客户都只能被一辆
配送车辆服务,有且仅有一次;约束(5)表示所有车辆从某车场出发且都必须回到该车场,若等于零,则
表示该车辆未被使用;车辆约束(6)表示车辆配送过程中不能超过其额定载重量;式(7)表示目标函数中的
决策变量,取值范围为 0 或 1.式(1)~式(7)的具体符号定义详见表 1.
表 1 符号及定义 Tab.1 Symbols and their definitions
符号
释义
i
第 i 个客户
j
第 j 个客户
P
s
全部车场集合{1,2,…,P
t
}
P
t
车场数量上限
剩余13页未读,继续阅读
资源评论
罗伯特之技术屋
- 粉丝: 3675
- 资源: 1万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 基于Java的医疗药房管理系统设计源码
- Magisk-v26.4
- 其他类别JS+Flash让网页元素发光的插件 glow! 0.1-glow.zip
- 其他类别Jsp考试系统-jspks.zip
- 其他类别JSP Explorer 文件浏览器 v1.0-fileexplorer.zip
- 其他类别JSP网页HTML编辑器 v1.0 beat-jsphtmleditor.zip
- 62341893098644701-源码.zip
- 解决windows11下无法安装.net framework 3.5(包括.net2.0和3.0)
- 其他类别jsp+servlet+javaBean实现MVC-jspmvc.zip
- 学生住宿管理系统JAVA.zip
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功