Algorithm for Distance Constrained Aerial Vehicle Routing Problem: based on minimum spanning tree and genetic computation

被引：1

作者：

Song, Zhihua ^{[1
]}

Zhang, Han ^{[2
]}

Che, Wanfang ^{[3
]}

Hui, Xiaobin ^{[1
]}

机构：

[1] Air Force Engn Univ, Equipment Management & Safety Engn Coll, Xian, Peoples R China

[2] Air Force Engn Univ, Coll Sci, Xian, Peoples R China

[3] Equipment Acad Air Force, Key Lab Complex Aviat Syst Simulat, Beijing, Peoples R China

来源：

2015 11TH INTERNATIONAL CONFERENCE ON COMPUTATIONAL INTELLIGENCE AND SECURITY (CIS) | 2015年

关键词：

vehicle routing problem; minimum spanning tree; heuristic; genetic algorithm; NP-complete; OPTIMIZATION; SYSTEM;

D O I：

10.1109/CIS.2015.10

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

The main goal of this research is to find a solution of distance constrained aerial vehicle routing problem using genetic algorithm based on the minimum spanning tree heuristic. As the lower bound of vehicle routing problem, the minimum spanning tree provides a natural heuristic for the searching of routes. It is used in generating the initial population and designing of the reorganization crossover operator. The proposed algorithm performs well with respect to accuracy, consistency, speed, and simplicity in all tests in the paper.

引用

页码：5 / 9

页数：5

共 13 条

[1]

[Anonymous], COMPUT OPER RES

[2] A genetic algorithm for the vehicle routing problem [J].

Baker, BM ;

Ayechew, MA .

COMPUTERS & OPERATIONS RESEARCH, 2003, 30 (05) :787-800

[3] A novel hybrid column generation-metaheuristic approach for the vehicle routing problem with general soft time window [J].

Beheshti, Ali Kourank ;

Hejazi, Seyed Reza .

INFORMATION SCIENCES, 2015, 316 :598-615

[4] An improved ant system algorithm for the vehicle routing problem [J].

Bullnheimer, B ;

Hartl, RF ;

Strauss, C .

ANNALS OF OPERATIONS RESEARCH, 1999, 89 (0) :319-328

[5] SCHEDULING OF VEHICLES FROM CENTRAL DEPOT TO NUMBER OF DELIVERY POINTS [J].

CLARKE, G ;

WRIGHT, JW .

OPERATIONS RESEARCH, 1964, 12 (04) :568-&

[6] A guide to vehicle routing heuristics [J].

Cordeau, JF ;

Gendreau, M ;

Laporte, G ;

Potvin, JY ;

Semet, F .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2002, 53 (05) :512-522

[7] THE TRUCK DISPATCHING PROBLEM [J].

DANTZIG, GB ;

RAMSER, JH .

MANAGEMENT SCIENCE, 1959, 6 (01) :80-91

[8] A GENERALIZED ASSIGNMENT HEURISTIC FOR VEHICLE-ROUTING [J].

FISHER, ML ;

JAIKUMAR, R .

NETWORKS, 1981, 11 (02) :109-124

[9] A TABU SEARCH HEURISTIC FOR THE VEHICLE-ROUTING PROBLEM [J].

GENDREAU, M ;

HERTZ, A ;

LAPORTE, G .

MANAGEMENT SCIENCE, 1994, 40 (10) :1276-1290

[10] HEURISTIC ALGORITHM FOR VEHICLE-DISPATCH PROBLEM [J].

GILLETT, BE ;

MILLER, LR .

OPERATIONS RESEARCH, 1974, 22 (02) :340-349

← 1 2 →