Vehicle routing with compartments: applications, modelling and heuristics

被引：88

作者：

Derigs, Ulrich ^{[1
]}

Gottlieb, Jens ^{[2
]}

Kalkoff, Jochen ^{[3
]}

Piesche, Michael ^{[1
]}

Rothlauf, Franz ^{[4
]}

Vogel, Ulrich ^{[1
]}

机构：

[1] Univ Cologne, D-50969 Cologne, Germany

[2] SAP AG, D-69190 Walldorf, Germany

[3] SAP Deutschland AG & Co KG, D-69190 Walldorf, Germany

[4] Johannes Gutenberg Univ Mainz, D-55128 Mainz, Germany

来源：

OR SPECTRUM | 2011年 / 33卷 / 04期

关键词：

Transportation; Vehicle routing; Compartment; Heuristics; DELIVERY PROBLEM; TABU SEARCH; ALGORITHM; OPTIMIZATION; DISPATCH;

D O I：

10.1007/s00291-010-0194-3

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

Despite the vast amount of literature about vehicle routing problems, only very little attention has been paid to vehicles with compartments that allow transportation of inhomogeneous products on the same vehicle, but in different compartments. We motivate a general vehicle routing problem with compartments that is essential for several industries, like the distribution of food or petrol. We introduce a formal model, an integer program formulation and a benchmark suite of 200 instances. A solver suite of heuristic components is presented, which covers a broad range of alternative approaches for construction, local search, large neighbourhood search and meta-heuristics. The empirical results for the benchmark instances identify effective algorithmic setups as well as essential components for achieving high solution quality. In a comparison on 23 specific and combinatorially less complex instances taken from literature, our algorithm showed to be competitive.

引用

页码：885 / 914

页数：30

共 44 条

[31]

Michalewicz Z., 1996, Genetic Algorithms + Data Structures = Evolution Programs, V3rd

[32] Variable neighborhood search [J].