FILM-COPY DELIVERER PROBLEM USING GENETIC ALGORITHMS

被引：10

作者：

CHENG, RW ^{[1
]}

GEN, M ^{[1
]}

SASAKI, M ^{[1
]}

机构：

[1] ASHIKAGA INST TECHNOL,DEPT IND & SYST ENGN,ASHIKAGA 326,JAPAN

来源：

COMPUTERS & INDUSTRIAL ENGINEERING | 1995年 / 29卷

关键词：

GENETIC ALGORITHMS; TRAVELING SALESMAN PROBLEM; FILM-COPY DELIVERER PROBLEM; NEIGHBORHOOD SEARCH AND COMBINATORIAL OPTIMIZATION;

D O I：

10.1016/0360-8352(95)00132-K

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 [计算机应用技术]; 0835 [软件工程];

摘要：

Film-copy Deliverer problem (short for the FDP) can be regarded as a new extension of traveling salesman problem. It has bn proven that FDP is a NP hard problem and several heuristic algorithms have been reported. In this paper, we develop an implementation of genetic algorithms to solve this problem. A deliverer tour can bw resented as a walk on a graph, which is a natural coding scheme. A subtour preservation crossover is proposed in order to maintain building blocks in the offspring in much the same manner as Holland described. Mutation is designed with local search techniques intending to generate the improved offspring. The proposed procedure is tested on randomly generated problems and the results show that genetic algorithms can be a promising way for this problem.

引用

页码：549 / 553

页数：5

共 6 条

[1]

CHARTRAND G, 1979, GRAPHS DIGRAPHS

[2]

CHENG R, 1993, 2ND P INT C SYS SCIE, P542

[3]

HOLLAND JH, 1975, ADAPTATION NATURAL A

[4]

THE TRAVELING SALESMAN PROBLEM - AN OVERVIEW OF EXACT AND APPROXIMATE ALGORITHMS [J].

LAPORTE, G .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1992, 59 (02) :231-247

[5]

MICHALEWICZ Z, 1994, GENETIC ALGORITHM PL

[6]

ZHANG L, 1994, 1994 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN, AND CYBERNETICS - HUMANS, INFORMATION AND TECHNOLOGY, VOLS 1-3, P543, DOI 10.1109/ICSMC.1994.399895

← 1 →