The bi-objective covering tour problem

被引：48

作者：

Jozefowiez, Nicolas ^{[1
]}

Semet, Frederic

Talbi, El-Ghazali

机构：

[1] Univ Sci & Technol Lille, Lab Informat Fondamentale, F-69655 Villeneuve Dascq, France

[2] Univ Valenciennes & Hainaut Cambresis, Lab Automat Mecan & Informat Ind & Humaines, F-59313 Valenciennes 9, France

来源：

COMPUTERS & OPERATIONS RESEARCH | 2007年 / 34卷 / 07期

关键词：

routing; multi-objective optimization; cooperative approach;

D O I：

10.1016/j.cor.2005.07.022

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The paper discusses the definition and solution of a bi-objective routing problem, namely the bi-objective covering tour problem. The bi-objective CTP is a generalization of the covering tour problem, which means that the covering distance and the associated constraints have been replaced by a new objective. We propose a two-phase cooperative strategy that combines a multi-objective evolutionary algorithm with a branch-and-cut algorithm initially designed to solve a single-objective covering tour problem. Experiments were conducted using both randomly generated instances and real data. Optimal Pareto sets were determined using a bi-objective exact method based on an epsilon-constraint approach with a branch-and-cut algorithm. (c) 2005 Elsevier Ltd. All rights reserved.

引用

页码：1929 / 1942

页数：14

共 13 条

[1] BALAS E, 1980, MATH PROGRAM STUD, V12, P37, DOI 10.1007/BFb0120886
[2] A genetic algorithm for the set covering problem
Beasley, JE
Chu, PC
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 94 (02) : 392 - 404
[3] Boffey B, 1995, TOP, V3, P167, DOI [10.1007/BF02568585, DOI 10.1007/BF02568585]
[4] Current J.R., 1981, Ph.D. thesis
[5] THE COVERING SALESMAN PROBLEM
CURRENT, JR
SCHILLING, DA
[J]. TRANSPORTATION SCIENCE, 1989, 23 (03) : 208 - 213
[6] THE MEDIAN TOUR AND MAXIMAL COVERING TOUR PROBLEMS - FORMULATIONS AND HEURISTICS
CURRENT, JR
SCHILLING, DA
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1994, 73 (01) : 114 - 126
[7] A fast and elitist multiobjective genetic algorithm: NSGA-II
Deb, K
Pratap, A
Agarwal, S
Meyarivan, T
[J]. IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2002, 6 (02) : 182 - 197
[8] NEW INSERTION AND POSTOPTIMIZATION PROCEDURES FOR THE TRAVELING SALESMAN PROBLEM
GENDREAU, M
HERTZ, A
LAPORTE, G
[J]. OPERATIONS RESEARCH, 1992, 40 (06) : 1086 - 1094
[9] The covering tour problem
Gendreau, M
Laporte, G
Semet, F
[J]. OPERATIONS RESEARCH, 1997, 45 (04) : 568 - 576
[10] A covering tour model for planning mobile health care facilities in Suhum District, Ghana
Hodgson, MJ
Laporte, G
Semet, F
[J]. JOURNAL OF REGIONAL SCIENCE, 1998, 38 (04) : 621 - 638

← 1 2 →