基于超启发式算法的选址-路径问题研究1
需积分: 0 196 浏览量
2022-08-03
15:17:16
上传
评论
收藏 1.16MB PDF 举报
第
４７
卷第
６
期
２０１９
年
１２
月
浙 江 工 业 大 学 学 报
JOURNALOFZHEJIANG UNIVERSITYOFTECHNOLOGY
Vol．４７No．６
Dec．２０１９
收稿日期
:
２０１８Ｇ０６Ｇ０６
基金项目
:
国家自然科学基金资助项目
(
６１５７２４３８
)
作者简介
:
王万良
(
１９５７
—),
男
,
江苏高邮人
,
教授
,
博士
,
博士生导师
,
研究 方向为 计 算机控 制 与智能 自 动化
、
智能 调 度等
,
EＧmail
:
z
j
utwwl
＠z
j
ut．edu．cn
.
基于超启发式算法的选址
Ｇ
路径问题研究
王万良
,
徐
昶
,
赵燕伟
,
朱文成
(
浙江工业大学 计算机科学与技术学院
,
浙江 杭州
３１００２３
)
摘要
:
为了降低物流配送过程中车辆的碳排放
,
采用具有良好通用性的超启发式算法对低碳选址路
径问题进行求解
.
将蛙跳算法作为超启发式算法的高层选择策略
,
并在蛙 跳算法中 提出了基 于最
长公共子序列的相似度计算方式代替原有的相似度计算
,
而采用动态 规划的方 法对个体 间的最长
公共子序列进行计算
.
实验结果表明
:
提出的相似度计算方式能更直观地反映个体之间的相似性
,
具有良好的通用性
,
并且在低碳选址
Ｇ
路径问题上获得更优秀的解
.
关键词
:
超启发式算法
;
选择策略
;
蛙跳选择
;
最长公共子序列
中图分类号
:
TP１８３
文献标志码
:
A
文章编号
:
１００６Ｇ４３０３
(
２０１９
)
０６Ｇ０６０４Ｇ０７
ResearchonlocationＧroutin
gp
roblembasedonh
yp
erＧheuristical
g
orithm
WANG Wanlian
g
,
XUChan
g
,
ZHAOYanwei
,
ZHU Wenchen
g
(
Colle
g
eofCom
p
uterScienceandTechnolo
gy
,
Zhe
j
ian
g
Universit
y
ofTechnolo
gy
,
Han
g
zhou３１００２３
,
China
)
Abstract
:
Inordertoreducethecarbonemissionofvehicles
,
theh
yp
erＧheuristical
g
orithm with
g
ooduniversalit
y
isusedtosolvethelowＧcarbonlocationＧroutin
gp
roblem．This
p
a
p
eruses
lea
p
fro
g
al
g
orithm astheto
p
choicestrate
gy
ofh
yp
erＧheuristical
g
orithms
,
and
p
ro
p
osesthe
similarit
y
calculation method based onlon
g
estcommon subse
q
uenceinstead ofthe ori
g
inal
similarit
y
calculationinlea
p
fro
g
al
g
orithm
,
andusesthed
y
namic
p
ro
g
rammin
g
tocalculatethe
lon
g
estcommonsubse
q
uencebetweenindividuals．Theex
p
erimentalresultsshowthatthenew
similarit
y
calculationmethodcanmoreintuitivel
y
reflectthesimilaritiesbetweenindividuals
,
and
itmakesh
yp
erＧheuristical
g
orithm
g
etbettersolutionsinlocationＧroutin
gp
roblem．
Ke
y
words
:
h
yp
erＧheuristical
g
orithm
;
selectionstrate
gy
;
lea
p
fro
g
al
g
orithm
;
lon
g
estcommonsubse
q
uence
选 址
Ｇ
路 径 问 题
(
LocationＧroutin
g p
roblem
,
LRP
)
将 选 址 分 配 问 题
(
Locationallocation
p
robＧ
lem
,
LAP
)
与 经 典 车 辆 路 径 问 题
(
Vehicleroutin
g
p
roblem
,
VRP
)
进 行 组 合 研 究
,
属 于 经 典 的
NP
难
问题
.
随着全球气 候 变 暖
,
低碳问题得到了越来越
多人的重视
,
而物流业是碳排放的主要来源之一
,
因
此对于低碳物 流 模 型 的 研 究 日 趋 增 多
.
在模型上
,
曹剑东等
[
１Ｇ２
]
以总 成 本 最 小 化 为 优 化 目 标 研 究 了 考
虑碳 排 放 因 素 的 车 辆 路 径 问 题
(
Vehicleroutin
g
p
roblem
,
VRP
).
在求 解 算 法 上
,
基本以遗传算法
、
禁忌搜索等启发式 算 法 居 多
,
但这些算法不具有良
好的通用性
,
无法适用于新研究出来的模型
.
超启发 式 算 法
[
３
]
(
H
yp
erＧheuristical
g
orithms
)
是近年才发展起来 的 一 种 新 型 的 启 发 式 算 法
,
可以
简单阐述为
“
寻找启发 式 算 法 的 启 发 式 算 法
”,
该算
法具有良好的通用性
,
可用于求解排课问题
[
４
]
、
流水
车间调度问题
[
５
]
和装箱问题
[
６
]
等约束较少的组合优
化问题
.
超 启 发 式 算 法 的 研 究 主 要 集 中 在 选 择 策
晕过前方
- 粉丝: 113
- 资源: 328
最新资源
- Screenshot_20240430_144340_com.ss.android.ugc.live.jpg
- 回到山沟沟.mp3
- 基于matlab实现自适应波束形成RLS及LMS算法仿真源程序1.rar
- 基于matlab实现自己编写的基于卡尔曼滤波的利用加速度传感器的计步器，测试数据是传感器放在腰部和手臂 .rar
- 基于matlab实现阵列信号处理，波束形成.rar
- 111111111111111111
- 基于matlab实现计步器编程；对当前的计步器装置的数值算法模拟 .rar
- Mdb学习查看PW；access;mdb;pw;password;patch
- 基于matlab实现关于语音信号声源定位DOA估计所用的一些传统算法.rar
- 基于ultralytics-yolov8, 将其检测/分类/分割/姿态等任务移植到rk3588上
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论0