A Hybrid Genetic Algorithm for the Traveling Salesman Problem with Pickup and Delivery

被引：7

作者：

FangGeng Zhao JiangSheng Sun SuJian Li WeiMin Liu Vehicle Management Institute Bengbu PRC Department of Logistics Engineering University of Science and Technology Beijing Beijing PRC Ordnance Technology Research Institute Shijiazhuang PRC ^{[1
,2
,3
,2
,2
,1
,233011
,2
,100083
,3
,50003
]}

机构：

来源：

International Journal of Automation & Computing | 2009年 / 6卷 / 01期

关键词：

Genetic algorithm (GA); pheromone-based crossover; local search; pickup and delivery; traveling salesman problem (TSP);

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

In this paper, a hybrid genetic algorithm (GA) is proposed for the traveling salesman problem (TSP) with pickup and delivery (TSPPD). In our algorithm, a novel pheromone-based crossover operator is advanced that utilizes both local and global information to construct offspring. In addition, a local search procedure is integrated into the GA to accelerate convergence. The proposed GA has been tested on benchmark instances, and the computational results show that it gives better convergence than existing heuristics.

引用

页码：97 / 102

页数：6

共 6 条

[1]

Ant Algorithms: Theory and Applications[J] . S. D. Shtovba.Programming and Computer Software . 2005 (4)

[2]

An improved hybrid genetic algorithm: new results for the quadratic assignment problem[J] . Alfonsas Misevicius.Knowledge-Based Systems . 2004 (2)

[3] A hybrid genetic algorithm for the job shop scheduling problems [J].

Park, BJ ;

Choi, HR ;

Kim, HS .

COMPUTERS & INDUSTRIAL ENGINEERING, 2003, 45 (04) :597-613

[4] An exact algorithm for the traveling salesman problem with deliveries and collections [J].

Baldacci, R ;

Hadjiconstantinou, E ;

Mingozzi, A .

NETWORKS, 2003, 42 (01) :26-41

[5]

MAX – MIN Ant System[J] . Thomas Stützle,Holger H. Hoos.Future Generation Computer Systems . 2000 (8)

[6] The traveling salesman problem with backhauls [J].

Gendreau, M ;

Hertz, A ;

Laporte, G .

COMPUTERS & OPERATIONS RESEARCH, 1996, 23 (05) :501-508

← 1 →