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 条

[1] A note on computational aspects of the Steiner traveling salesman problem [J].

Alvarez-Miranda, Eduardo ;

Sinnl, Markus .

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2019, 26 (04) :1396-1401

[2]

Applegate D. L., 2006, The Traveling Salesman Problem:A Computational Study

[3] Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems [J].

Arora, S .

JOURNAL OF THE ACM, 1998, 45 (05) :753-782

[4]

Ball M.O., 1995, NETWORK ROUTING, V8

[5] Selected country circuity factors for road travel distance estimation [J].

Ballou, RH ;

Rahardja, H ;

Sakai, N .

TRANSPORTATION RESEARCH PART A-POLICY AND PRACTICE, 2002, 36 (09) :843-848

[6] ROUTE 1ST - CLUSTER 2ND METHODS FOR VEHICLE-ROUTING [J].

BEASLEY, JE .

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 1983, 11 (04) :403-408

[7] Vehicle routing problems with road-network information: State of the art [J].

Ben Ticha, Hamza ;

Absi, Nabil ;

Feillet, Dominique ;

Quilliot, Alain .

NETWORKS, 2018, 72 (03) :393-406

[8] THE SUITABILITY OF THE WEIGHTED LP-NORM IN ESTIMATING ACTUAL ROAD DISTANCES [J].

BERENS, W .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1988, 34 (01) :39-43

[9] ESTIMATING ROAD DISTANCES BY MATHEMATICAL FUNCTIONS [J].

BERENS, W ;

KORLING, FJ .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1985, 21 (01) :54-56

[10]

Bodin L.D., 1975, Computers Urban Society, V1, P11

← 1 2 3 4 →