A two-pheromone trail ant colony system-tabu search approach for the heterogeneous vehicle routing problem with time windows and multiple products

被引：30

作者：

De la Cruz, Jair J. ^{[1
]}

Paternina-Arboleda, Carlos D. ^{[2
]}

Cantillo, Victor ^{[3
]}

Montoya-Torres, Jairo R. ^{[4
]}

机构：

[1] Univ Norte, Dept Ind Engn, Barranquilla, Colombia

[2] Univ Norte, Escuela Negocios, Barranquilla, Colombia

[3] Univ Norte, Dept Civil & Environm Engn, Barranquilla, Colombia

[4] Univ La Sabana, Escuela Ciencias Econ & Adm, Chia, Cundinamarca, Colombia

来源：

JOURNAL OF HEURISTICS | 2013年 / 19卷 / 02期

关键词：

Vehicle routing; Multiple products; Time windows; Ant colony; Tabu search; Sequential algorithm; DELIVERY PROBLEM; OPTIMIZATION; ALGORITHM; PICKUP;

D O I：

10.1007/s10732-011-9184-0

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

This paper considers a practical variant of the Vehicle Routing Problem (VRP) known as the Heterogeneous Vehicle Routing Problem with Time Windows and Multiple Products (HVRPTWMP). As the problem is NP-hard, the resolution approach proposed here is a sequential Ant Colony System (ACS)-Tabu Search algorithm. The approach introduces a two pheromone trail strategy to accelerate agents' (ants) learning process. Its convergence to good solutions is given in terms of fleet size and travel time while completing tours and service to all customers. The proposed procedure uses regency and frequency memories form Tabu Search to further improve the quality of solutions. Experiments are carried out using instances from literature and show the effectiveness of this procedure.

引用

页码：233 / 252

页数：20

共 43 条

[1] Travel time reliability in vehicle routing and scheduling with time windows [J].

Ando, Naoki ;

Taniguchi, Eiichi .

NETWORKS & SPATIAL ECONOMICS, 2006, 6 (3-4) :293-311

[2]

[Anonymous], 2002, The vehicle routing problem pp

[3] A tabu search algorithm for the vehicle routing problem [J].

Barbarosoglu, G ;

Ozgur, D .

COMPUTERS & OPERATIONS RESEARCH, 1999, 26 (03) :255-270

[4] Ant colony optimization techniques for the vehicle routing problem [J].

Bell, JE ;

McMullen, PR .

ADVANCED ENGINEERING INFORMATICS, 2004, 18 (01) :41-48

[5]

Bianchi L., 2006, Journal of Mathematical Modelling and Algorithms, V5, P91, DOI DOI 10.1007/S10852-005-9033-Y

[6] A LOCATION BASED HEURISTIC FOR GENERAL ROUTING-PROBLEMS [J].

BRAMEL, J ;

SIMCHILEVI, D .

OPERATIONS RESEARCH, 1995, 43 (04) :649-660

[7] Evolutionary algorithms for the vehicle routing problem with time windows [J].

Bräysy, O ;

Dullaert, W ;

Gendreau, M .

JOURNAL OF HEURISTICS, 2004, 10 (06) :587-611

[8] An improved ant system algorithm for the vehicle routing problem [J].

Bullnheimer, B ;

Hartl, RF ;

Strauss, C .

ANNALS OF OPERATIONS RESEARCH, 1999, 89 (0) :319-328

[9]

Bullnheimer B., 1997, P 2 INT C MET

[10] PARALLEL COOPERATIVE SAVINGS BASED ANT COLONY OPTIMIZATION - MULTIPLE SEARCH AND DECOMPOSITION APPROACHES [J].

Doerner, Karl F. ;

Hartl, Richard F. ;

Benkner, Siefried ;

Lucka, Maria .

PARALLEL PROCESSING LETTERS, 2006, 16 (03) :351-369

← 1 2 3 4 5 →