A grouping genetic algorithm for the pickup and delivery problem with time windows

被引：92

作者：

Pankratz, G ^{[1
]}

机构：

[1] Fernuniv, Univ Hagen, Dept Business Adm & Econ, D-58084 Hagen, Germany

来源：

OR SPECTRUM | 2005年 / 27卷 / 01期

关键词：

genetic algorithms; group-oriented encoding; pickup and delivery problem with time windows;

D O I：

10.1007/s00291-004-0173-7

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The Pickup and Delivery Problem with Time Windows (PDPTW) is a generalization of the well studied Vehicle Routing Problem with Time Windows (VRPTW). Since it models several typical planning situations in operational transportation logistics and public transit, the PDPTW has attracted growing interest in recent years. This paper proposes a Grouping Genetic Algorithm (GGA) for solving the PDPTW which features a group-oriented genetic encoding in which each gene represents a group of requests instead of a single request. The GGA is subject to a comparative test on the basis of two publicly available benchmark problem sets that comprise 9 and 56 PDPTW instances, respectively. The results show that the proposed GGA is competitive.

引用

页码：21 / 41

页数：21

共 42 条

[1]

[Anonymous], 2003, OP RES P 2002

[2]

[Anonymous], 1991, Handbook of genetic algorithms

[3]

Berger J., 1998, Advances in Artificial Intelligence. 12th Biennial Conference of the Canadian Society for Computational Studies of Intelligence, AI'98. Proceedings, P114

[4]

BLANTON JL, 1993, PROCEEDINGS OF THE FIFTH INTERNATIONAL CONFERENCE ON GENETIC ALGORITHMS, P452

[5]

BODIN LD, 1986, TIMS STUDIES MANAGEM, V26, P73

[6] A NEW OPTIMIZATION ALGORITHM FOR THE VEHICLE-ROUTING PROBLEM WITH TIME WINDOWS [J].

DESROCHERS, M ;

DESROSIERS, J ;

SOLOMON, M .

OPERATIONS RESEARCH, 1992, 40 (02) :342-354

[7]

Desrosiers J., 1988, Computer-Aided Transit Scheduling. Proceedings of the Fourth International Workshop on Computer-Aided Scheduling of Public Transport, P15

[8]

Desrosiers J., 1986, American Journal of Mathematical and Management Sciences, V6, P301

[9] THE PICKUP AND DELIVERY PROBLEM WITH TIME WINDOWS [J].

DUMAS, Y ;

DESROSIERS, J ;

SOUMIS, F .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1991, 54 (01) :7-22

[10]

Falkenauer E., 1998, GENETIC ALGORITHMS G

← 1 2 3 4 5 →