A two-phase hybrid metaheuristic for the vehicle routing problem with time windows

被引：132

作者：

Homberger, J ^{[1
]}

Gehring, H ^{[1
]}

机构：

[1] Univ Hagen, D-58084 Hagen, Germany

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2005年 / 162卷 / 01期

关键词：

metaheuristics; tabu search; evolution strategy; hybridization; vehicle routing; time windows;

D O I：

10.1016/j.ejor.2004.01.027

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

The subject of this paper is a two-phase hybrid metaheuristic for the vehicle routing problem with time windows and a central depot (VRPTW). The objective function of the VRPTW considered here combines the minimization of the number of vehicles (primary criterion) and the total travel distance (secondary criterion). The aim of the first phase is the minimization of the number of vehicles by means of a (mulambda)-evolution strategy, whereas in the second phase the total distance is minimized using a tabu search algorithm. The two-phase hybrid metaheuristic was subjected to a comparative test on the basis of 356 problems from the literature with sizes varying from 100 to 1000 customers. The derived results show that the proposed two-phase approach is very competitive. (C) 2004 Elsevier B.V. All rights reserved.

引用

页码：220 / 238

页数：19

共 37 条

[11] HOFFMEISTER F, 1990, PARALLEL PROBLEM SOL, P447
[12] Homberger J, 1999, INFOR, V37, P297
[13] Kilby P., 1999, METAHEURISTICS ADV T, DOI [10.1007/978-1-4615-5775-3_32, DOI 10.1007/978-1-4615-5775-3_32]
[14] Kontoravdis G., 1995, ORSA Journal on Computing, V7, P10, DOI 10.1287/ijoc.7.1.10
[15] COMPLEXITY OF VEHICLE-ROUTING AND SCHEDULING PROBLEMS
LENSTRA, JK
KAN, AHGR
[J]. NETWORKS, 1981, 11 (02) : 221 - 227
[16] COMPUTER SOLUTIONS OF TRAVELING SALESMAN PROBLEM
LIN, S
[J]. BELL SYSTEM TECHNICAL JOURNAL, 1965, 44 (10): : 2245 - +
[17] A route-neighborhood-based metaheuristic for vehicle routing problem with time windows
Liu, FHF
Shen, SY
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1999, 118 (03) : 485 - 504
[18] NEITZEL W, 1977, TOURENPLANUNG PROBLE
[19] Or I., 1976, THESIS NW U EVANSTON
[20] Osman I. H., 1993, Annals of Operations Research, V41, P421, DOI 10.1007/BF02023004

← 1 2 3 4 →