三阶段禁忌算法求解需求可拆分车辆路径问题
需积分: 25 178 浏览量
更新于2024-09-09
1
收藏 551KB PDF 举报
"这篇论文研究了需求可拆分车辆路径问题（SDVRP）并提出了一种三阶段禁忌算法的解决方案。SDVRP是车辆路径问题（VRP）的一个分支，其特点在于客户需求可以被分割成多个部分，由不同的车辆完成配送。与传统的不可拆分需求的VRP相比，SDVRP的求解策略更为复杂。
论文首先定义了目标函数，即大旅行商问题（TSP）路径成本加上切割增加的路径成本，构建了SDVRP的双层规划数学模型。双层规划模型考虑了车辆路径和客户需求分割的相互影响。接着，作者提出了一个三阶段的禁忌启发式算法来解决这个问题：
1. 第一阶段：求解包含车场和所有顾客的大TSP路径。这是基础路径，用于后续的切割和拆分操作。
2. 第二阶段：对大TSP路径进行切割和拆分。这一阶段的目标是根据客户需求的拆分情况，将大路径拆分成多个子路径，确保每个车辆能处理一部分需求。
3. 第三阶段：对生成的备选子路径进行优化，进一步降低总成本。这可能涉及到调整车辆路径，以减少行驶距离或满足其他约束条件。
通过实验仿真，该三阶段禁忌算法与其他已有的算法进行了对比，结果显示该算法在求解SDVRP时能有效找到优化解，证明了其在解决需求可拆分车辆路径问题上的有效性。论文的贡献在于为SDVRP提供了一个新颖且实用的求解策略，对于物流管理和运输优化等领域具有重要的理论与实践价值。"
35
5
Vol.35, No.5
2015
5
Systems Engineering — Theory & Practice May, 2015
: 1000-6788(2015)05-1230-06
: U492.3; TP311
:A
1,2
,
3
(1.
,
570228; 2.
,
410083;
3.
,
570228)
(SDVRP)
!
"#
,
$%&'
(#
VRP
)*#+,
.
-.
,
/
01
#%
——
2
3456
#789:;
'
.
,
<=>?
!"
@
#
*
TSP
A/B
$
CD
%
B
A/
,
EF1
SDVRP
#
345
!&
6
;
GH
,
IJ
345#
"
K1789: ;LM
'
'
:
NOPQ
(
RS#*
TSP
,
)
-*
TSP
T
*
CDQ
,
U
+
-V
,
&WT
*-
.
X
;
/
H
,
0
Y
12
Z
3
,
<
(
[#789:;
'
$
Æ
'T
*
\)
,
]^_`1
(
[#
'
4
\)
5
ab
#
.
X%
,
%c
#
5
&'
.
;
;
3456
;
:;
'
A three-phase tabu search heuristic for the split delivery vehicle
routing problem
XIONG Hao
1,2
, YAN Hui-li
3
(1. School of Economics and Management, Hainan University, Haikou 570228, China; 2. School of Traffic and Transportation
Engineering, Central South University, Changsha 410083, China; 3
Tourism College, Hainan University, Haikou 570228,
China)
Abstract The split delivery vehicle routing problem (SDVRP) is a kind of vehicle routing problem need
to be further studied. And its solving method is much different with the traditional VRP’s. This paper
provides a new heuristic to solve the SDVRP called three-phase tabu algorithm, which is based on the bi-
level programming model of SDVRP. First, the bi-level programming mathematical model of the SDVRP
is given, which set the cost of a big TSP path and the increased cost of cutting and split as the objective
function. Then, based on bi-level programming model, a three-phase tabu heuristic algorithm is designed.
First phase, a big TSP path including the distribution depot and all the customers is constructed. Second
phase, the big TSP is cut and split. And in the third phase, the sub-paths get from the second phase are
re-optimization. Finally, through the experimental simulation, the proposed three-stage tabu algorithm
compared with other algorithms. And the results showed that the proposed algorithm can really solve the
SDVRP effectively. And they also proved that the three-phase tabu algorithm is really a good method of
SDVRP.
Keywords vehicle routing problem; the split delivery; bi-level programming model; tabu algorithm
0
de
(VRP)
,
VRP
1
:
.
,
[1−4]
.
,
VRP
.
f
: 2013-09-25
ghi
:
(71461007, 71461006);
(2014M560653);
(126227)
jk
!"
:
(1981–),
,
,
,
,
,
:
,
, E-mail: xionghao@hainu.edu.cn;
#Æ
:
$
(1980–),
,
,
!
,
,
:
!
"
!
, E-mail: yhl yanhuili@126.com.
下载后可阅读完整内容，剩余5页未读，立即下载
452 浏览量
136 浏览量
194 浏览量
145 浏览量
216 浏览量
247 浏览量
119 浏览量
2022-05-12 上传
116 浏览量
weixin_38744270
- 粉丝: 329
- 资源: 2万+
我的内容管理
展开
