A Simple Metaheuristic for the FleetSize and Mix Problem with TimeWindows

被引：1

作者：

Braysy, Olli ^{[1
]}

Dullaert, Wout ^{[2
]}

Porkka, Pasi P. ^{[3
]}

机构：

[1] Univ Jyvaskyla, Dept Math Informat Technol, POB 35, FI-40014 Jyvaskyla, Finland

[2] Vrije Univ Amsterdam, Fac Econ & Business Adm, Boelelaan 1105, NL-1081 HV Amsterdam, Netherlands

[3] Justecon Oy, Fredrikinkatu 64 B 22, Helsinki 00100, Finland

来源：

COMPUTATIONAL METHODS AND MODELS FOR TRANSPORT: NEW CHALLENGES FOR THE GREENING OF TRANSPORT SYSTEMS | 2018年 / 45卷

关键词：

VEHICLE-ROUTING PROBLEM; VARIABLE NEIGHBORHOOD SEARCH; TIME WINDOWS; SCHEDULING PROBLEMS; SIZE;

D O I：

10.1007/978-3-319-54490-8_4

中图分类号：

X [环境科学、安全科学];

学科分类号：

08 ; 0830 ;

摘要：

This paper presents a powerful new single-parameter metaheuristic to solve the Fleet Size and Mix Vehicle Routing Problem with Time Windows. The key idea of the new metaheuristic is to perform a random number of random-sized jumps in random order through four well-known local search operators. Computational testing on the 600 large-scale benchmarks of Braysy et al. (Expert Syst Appl 36(4): 8460-8475, 2009) show that the new metaheuristic outperforms previous best approaches, finding 533 new best-known solutions. Despite the significant number of random components, it is demonstrated that the variance of the results is rather low. Moreover, the suggested metaheuristic is shown to scale almost linearly up to 1000 customers.

引用

页码：57 / 70

页数：14

共 13 条

[1]

Baldacci R, 2008, OPER RES COMPUT SCI, V43, P3, DOI 10.1007/978-0-387-77778-8_1

[2] A reactive variable neighborhood search for the vehicle-routing problem with time windows [J].

Bräysy, O .

INFORMS JOURNAL ON COMPUTING, 2003, 15 (04) :347-368

[3] An effective multirestart deterministic annealing metaheuristic for the fleet size and mix vehicle-routing problem with time windows [J].

Braysy, Olli ;

Dullaert, Wout ;

Hasle, Geir ;

Mester, David ;

Gendreau, Michel .

TRANSPORTATION SCIENCE, 2008, 42 (03) :371-386

[4] A well-scalable metaheuristic for the fleet size and mix vehicle routing problem with time windows [J].

Braysy, Olli ;

Porkka, Pasi P. ;

Dullaert, Wout ;

Repoussis, Panagiods P. ;

Tarantilis, Christos D. .

EXPERT SYSTEMS WITH APPLICATIONS, 2009, 36 (04) :8460-8475

[5] Efficient insertion heuristics for vehicle routing and scheduling problems [J].

Campbell, AM ;

Savelsbergh, M .

TRANSPORTATION SCIENCE, 2004, 38 (03) :369-378

[6] SCHEDULING OF VEHICLES FROM CENTRAL DEPOT TO NUMBER OF DELIVERY POINTS [J].

CLARKE, G ;

WRIGHT, JW .

OPERATIONS RESEARCH, 1964, 12 (04) :568-&

[7]

Gehring H, 1999, P EUROGEN99, V2

[8]

Gendreau M, 2008, OPER RES COMPUT SCI, V43, P143, DOI 10.1007/978-0-387-77778-8_7

[9] OPTIMIZATION BY SIMULATED ANNEALING [J].

KIRKPATRICK, S ;

GELATT, CD ;

VECCHI, MP .

SCIENCE, 1983, 220 (4598) :671-680

[10] An efficient variable neighborhood search heuristic for very large scale vehicle routing problems [J].

Kytojoki, Jari ;

Nuortio, Teemu ;

Braysy, Olli ;

Gendreau, Michel .

COMPUTERS & OPERATIONS RESEARCH, 2007, 34 (09) :2743-2757

← 1 2 →