Routing vehicles to minimize fuel consumption

被引：48

作者：

Gaur, Daya Ram ^{[1
]}

Mudgal, Apurva ^{[2
]}

Singh, Rishi Ranjan ^{[2
]}

机构：

[1] Univ Lethbridge, Dept Math & Comp Sci, Lethbridge, AB T1K 3M4, Canada

[2] Indian Inst Technol Ropar, Dept Comp Sci & Engn, Rupnagar 140001, Punjab, India

来源：

OPERATIONS RESEARCH LETTERS | 2013年 / 41卷 / 06期

关键词：

Approximation algorithms; Fuel consumption; Cumulative vehicle routing problem; DELIVERY PROBLEMS; HEURISTICS; TRANSPORTATION; 1ST;

D O I：

10.1016/j.orl.2013.07.007

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider a generalization of the capacitated vehicle routing problem known as the cumulative vehicle routing problem in the literature. Cumulative VRPs are known to be a simple model for fuel consumption in VRPs. We examine four variants of the problem, and give constant factor approximation algorithms. Our results are based on a well-known heuristic of partitioning the traveling salesman tours and the use of the averaging argument. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：576 / 580

页数：5

共 19 条

[1] HEURISTICS FOR UNEQUAL WEIGHT DELIVERY PROBLEMS WITH A FIXED ERROR GUARANTEE [J].

ALTINKEMER, K ;

GAVISH, B .

OPERATIONS RESEARCH LETTERS, 1987, 6 (04) :149-158

[2] HEURISTICS FOR DELIVERY PROBLEMS WITH CONSTANT ERROR GUARANTEES [J].

ALTINKEMER, K ;

GAVISH, B .

TRANSPORTATION SCIENCE, 1990, 24 (04) :294-297

[3]

[Anonymous], 2001, TION ENGRG

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

Arora, S .

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

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

BEASLEY, JE .

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

[6]

BLUM A, 1994, STOC, P163

[7]

Christofides N, 1976, 388 CARNEGIE MELLON 388 CARNEGIE MELLON

[8] THE TRUCK DISPATCHING PROBLEM [J].

DANTZIG, GB ;

RAMSER, JH .

MANAGEMENT SCIENCE, 1959, 6 (01) :80-91

[9] A comparative analysis of several vehicle emission models for road freight transportation [J].

Demir, Emrah ;

Bektas, Tolga ;

Laporte, Gilbert .

TRANSPORTATION RESEARCH PART D-TRANSPORT AND ENVIRONMENT, 2011, 16 (05) :347-357

[10]

Golden B.L., 1988, VEHICLE ROUTING METH

← 1 2 →