Ant colony optimization for the traveling purchaser problem

被引:54
作者
Bontoux, Boris [1 ]
Feillet, Dorninique [1 ]
机构
[1] Univ Avignon & Pays Vaucluse, Lab Informat Avignon, F-84911 Avignon 9, France
关键词
ant colony optimization; traveling purchaser problem;
D O I
10.1016/j.cor.2006.03.023
中图分类号
TP39 [计算机的应用];
学科分类号
081203 [计算机应用技术]; 0835 [软件工程];
摘要
The traveling purchaser problem (TPP) is a generalization of the traveling salesman problem where markets have to be visited to collect a set of commodities. Each market sells a number of commodities at a known price. The TPP consists in selecting a subset of markets purchasing every product, while minimizing the routing costs and the purchase costs. In this work, we address the solution of the TPP with an ant colony optimization procedure. We combine it with a local-search scheme exploring a new neighborhood structure. This procedure is evaluated on a set of benchmark instances from the literature and permits to improve most of the best-known solutions. (C) 2006 Elsevier Ltd. All rights reserved.
引用
收藏
页码:628 / 637
页数:10
相关论文
共 20 条
[1]
[Anonymous], 1991, 91016 DIP EL POL MIL
[2]
[Anonymous], 2004, Ant colony optimization
[3]
Ant colony optimization techniques for the vehicle routing problem [J].
Bell, JE ;
McMullen, PR .
ADVANCED ENGINEERING INFORMATICS, 2004, 18 (01) :41-48
[4]
Heuristics for the traveling purchaser problem [J].
Boctor, FF ;
Laporte, G ;
Renaud, J .
COMPUTERS & OPERATIONS RESEARCH, 2003, 30 (04) :491-504
[5]
Ants can colour graphs [J].
Costa, D ;
Hertz, A .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1997, 48 (03) :295-305
[6]
Ant system: Optimization by a colony of cooperating agents [J].
Dorigo, M ;
Maniezzo, V ;
Colorni, A .
IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS, 1996, 26 (01) :29-41
[7]
Traveling salesman problems with profits [J].
Feillet, D ;
Dejax, P ;
Gendreau, M .
TRANSPORTATION SCIENCE, 2005, 39 (02) :188-205
[8]
An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems [J].
Feillet, D ;
Dejax, P ;
Gendreau, M ;
Gueguen, C .
NETWORKS, 2004, 44 (03) :216-229
[9]
2 GENERALIZATIONS OF THE TRAVELING SALESMAN PROBLEM [J].
GOLDEN, B ;
LEVY, L ;
DAHL, R .
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 1981, 9 (04) :439-441
[10]
A branch-and-cut algorithm for the undirected traveling purchaser problem [J].
Laporte, G ;
Riera-Ledesma, J ;
Salazar-González, JJ .
OPERATIONS RESEARCH, 2003, 51 (06) :940-951