论文研究-需求可拆分车辆路径问题的三阶段禁忌算法.pdf
需积分: 14 138 浏览量
2019-09-20
19:15:18
上传
评论 1
收藏 551KB PDF 举报
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.
资源评论
