A hybrid algorithm for the Heterogeneous Fleet Vehicle Routing Problem

被引：115

作者：

Subramanian, Anand ^{[1
,2
]}

Vaz Penna, Puca Huachi ^{[4
]}

Uchoa, Eduardo ^{[3
]}

Ochi, Luiz Satoru ^{[2
]}

机构：

[1] Univ Fed Paraiba, Dept Prod Engn, Ctr Tecnol, BR-58051970 Joao Pessoa, Paraiba, Brazil

[2] Univ Fed Fluminense, Inst Comp, BR-24210240 Niteroi, RJ, Brazil

[3] Univ Fed Fluminense, Dept Prod Engn, BR-24210240 Niteroi, RJ, Brazil

[4] Univ Fed Fluminense, Inst Noroeste Fluminense Educ Super, BR-28470000 Santo Antonio De Padua, RJ, Brazil

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2012年 / 221卷 / 02期

关键词：

Routing; Heterogeneous fleet; Matheuristics; Iterated Local Search; Set Partitioning; TABU SEARCH; SIZE;

D O I：

10.1016/j.ejor.2012.03.016

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

This paper deals with the Heterogeneous Fleet Vehicle Routing Problem (HFVRP). The HFVRP generalizes the classical Capacitated Vehicle Routing Problem by considering the existence of different vehicle types, with distinct capacities and costs. The objective is to determine the best fleet composition as well as the set of routes that minimize the total costs. The proposed hybrid algorithm is composed by an Iterated Local Search (ILS) based heuristic and a Set Partitioning (SP) formulation. The SP model is solved by means of a Mixed Integer Programming solver that interactively calls the ILS heuristic during its execution. The developed algorithm was tested in benchmark instances with up to 360 customers. The results obtained are quite competitive with those found in the literature and new improved solutions are reported. (C) 2012 Elsevier B.V. All rights reserved.

引用

页码：285 / 295

页数：11

共 30 条

[1] An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts [J].

Baldacci, Roberto ;

Christofides, Nicos ;

Mingozzi, Aristide .

MATHEMATICAL PROGRAMMING, 2008, 115 (02) :351-385

[2] A unified exact method for solving different classes of vehicle routing problems [J].

Baldacci, Roberto ;

Mingozzi, Aristide .

MATHEMATICAL PROGRAMMING, 2009, 120 (02) :347-380

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

Brandao, Jose .

COMPUTERS & OPERATIONS RESEARCH, 2011, 38 (01) :140-151

[4] A deterministic tabu search algorithm for the fleet size and mix vehicle routing problem [J].

Brandao, Jose .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 195 (03) :716-728

[5] A column generation approach to the heterogeneous fleet vehicle routing problem [J].

Choi, Eunjeong ;

Tcha, Dong-Wan .

COMPUTERS & OPERATIONS RESEARCH, 2007, 34 (07) :2080-2095

[6]

Dongarra J.J., 2010, CS8985 U TENN COMP S

[7] A tabu search heuristic for the heterogeneous fleet vehicle routing problem [J].

Gendreau, M ;

Laporte, G ;

Musaraganyi, C ;

Taillard, ÉD .

COMPUTERS & OPERATIONS RESEARCH, 1999, 26 (12) :1153-1173

[8] THE FLEET SIZE AND MIX VEHICLE-ROUTING PROBLEM [J].

GOLDEN, B ;

ASSAD, A ;

LEVY, L ;

GHEYSENS, F .

COMPUTERS & OPERATIONS RESEARCH, 1984, 11 (01) :49-66

[9] Industrial aspects and literature survey: Fleet composition and routing [J].

Hoff, Arild ;

Andersson, Henrik ;

Christiansen, Marieile ;

Hasle, Geir ;

Lokketangen, Arne .

COMPUTERS & OPERATIONS RESEARCH, 2010, 37 (12) :2041-2061

[10] A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem [J].

Imran, Arif ;

Salhi, Said ;

Wassan, Niaz A. .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 197 (02) :509-518

← 1 2 3 →