Vehicle routing on road networks: How good is Euclidean approximation?

被引：18

作者：

Boyaci, Burak ^{[1
]}

Thu Huong Dang ^{[2
]}

Letchford, Adam N. ^{[1
]}

机构：

[1] Univ Lancaster, Dept Management Sci, Lancaster LA1 4YX, England

[2] Univ Lancaster, STOR i Ctr Doctoral Training, Lancaster LA1 4YR, England

来源：

COMPUTERS & OPERATIONS RESEARCH | 2021年 / 129卷

基金：

英国工程与自然科学研究理事会;

关键词：

Vehicle routing problems; Traveling salesman problem; Road networks; Combinatorial optimisation;

D O I：

10.1016/j.cor.2020.105197

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

Suppose that one is given a Vehicle Routing Problem (VRP) on a road network, but does not have access to detailed information about that network. One could obtain a heuristic solution by solving a modified version of the problem, in which true road distances are replaced with planar Euclidean distances. We test this heuristic, on two different types of VRP, using real road network data for twelve cities across the world. We also give guidelines on the kind of VRP for which this heuristic can be expected to give good results. (C) 2021 Elsevier Ltd. All rights reserved.

引用

页数：13

共 40 条

[21] INTEGER PROGRAMMING APPROACH TO VEHICLE SCHEDULING PROBLEM [J].

FOSTER, BA ;

RYAN, DM .

OPERATIONAL RESEARCH QUARTERLY, 1976, 27 (02) :367-384

[22] Vehicle routing problems with alternative paths: An application to on-demand transportation [J].

Garaix, Thierry ;

Artigues, Christian ;

Feillet, Dominique ;

Josselin, Didier .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 204 (01) :62-75

[23]

Garey M.R., 1976, PROC 8 ANN ACM S THE, P10

[24] HEURISTIC ALGORITHM FOR VEHICLE-DISPATCH PROBLEM [J].

GILLETT, BE ;

MILLER, LR .

OPERATIONS RESEARCH, 1974, 22 (02) :340-349

[25]

Golden B.L., 1988, VEHICLE ROUTING METH

[26]

Golden B, 2008, OPER RES COMPUT SCI, V43, pV

[27] A DYNAMIC PROGRAMMING APPROACH TO SEQUENCING PROBLEMS [J].

HELD, M ;

KARP, RM .

JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS, 1962, 10 (01) :196-210

[28] Pricing routines for vehicle routing with time windows on road networks [J].

Letchford, Adam N. ;

Nasiri, Saeideh D. ;

Oukil, Amar .

COMPUTERS & OPERATIONS RESEARCH, 2014, 51 :331-337

[29] Compact formulations of the Steiner Traveling Salesman Problem and related problems [J].

Letchford, Adam N. ;

Nasiri, Saeideh D. ;

Theis, Dirk Oliver .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2013, 228 (01) :83-92

[30] MATHEMATICAL-MODELS OF ROAD TRAVEL DISTANCES [J].

LOVE, RF ;

MORRIS, JG .

MANAGEMENT SCIENCE, 1979, 25 (02) :130-139

← 1 2 3 4 →