research-article

Routing vehicles to minimize fuel consumption

Authors:

Rishi Ranjan SinghAuthors Info & Claims

Operations Research Letters, Volume 41, Issue 6

Pages 576 - 580

https://doi.org/10.1016/j.orl.2013.07.007

Published: 01 November 2013 Publication History

Abstract

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.

References

[1]

K. Altinkemer, B. Gavish, Heuristics for unequal weight delivery problems with a fixed error guarantee, Oper. Res. Lett., 6 (1987) 149-158.

Digital Library

[2]

K. Altinkemer, B. Gavish, Technical note-heuristics for delivery problems with constant error guarantees, Transportation Science, 24 (1990) 294-297.

Digital Library

[3]

S. Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, J. ACM, 45 (1998) 753-778.

Digital Library

[4]

J.E. Beasley, Route first-cluster second methods for vehicle routing, Omega, 11 (1983) 403-408.

[5]

A. Blum, P. Chalasani, D. Coppersmith, W.R. Pulleyblank, P. Raghavan, M. Sudan, The minimum latency problem, in: STOC, 1994, pp. 163-171.

Digital Library

[6]

N. Christofides, Worst-case analysis of a new heuristic for the traveling salesman problem, Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA, 1976.

[7]

G.B. Dantzig, J.H. Ramser, The truck dispatching problem, Manage. Sci., 6 (1959) 80-91.

Digital Library

[8]

E. Demir, T. Bektaş, G. Laporte, A comparative analysis of several vehicle emission models for road freight transportation, Transportation Research Part D: Transport and Environment, 16 (2011) 347-357.

[9]

B.L. Golden, A.A. Assad, Vehicle Routing: Methods and Studies, North-Holland, 1988.

[10]

M. Haimovich, A.H.G. Rinnooy Kan, Bounds and heuristics for capacitated routing problems, Math. Oper. Res., 10 (1985) 527-542.

[11]

İ. Kara, B.Y. Kara, M.K. Yetiş, Cumulative vehicle routing problems, in: Vehicle Routing Problem, I-Tech Education and Publishing KG, Vienna, Austria, 2008, pp. 85-98.

[12]

İ. Kara, B.K. Yetiş, K. Yetiş, Energy minimizing vehicle routing problem, in: LNCS, vol. 4616, 2007, pp. 62-71.

Digital Library

[13]

P. Klein, A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights, SIAM J. Comput., 37 (2008) 1926-1952.

Digital Library

[14]

J.S.B. Mitchell, Guillotine subdivisions approximate polygonal subdivisions: a simple polynomial-time approximation scheme for geometric tsp, k -mst, and related problems, SIAM J. Comput., 28 (1999) 1298-1309.

Digital Library

[15]

R.H. Mole, D.G. Johnson, K. Wells, Combinatorial analysis for route first-cluster second vehicle routing, Omega, 11 (1983) 507-512.

[16]

P.W.G. Newman, B. Alimoradian, T.J. Lyons, Estimating fleet fuel consumption for vans and small trucks, Transportation Science, 23 (1989) 46-50.

Digital Library

[17]

B. Sahin, H. Yilmaz, Y. Ust, A.F. Guneri, B. Gulsun, An approach for analysing transportation costs and a case study, European J. Oper. Res., 193 (2009) 1-11.

[18]

P. Toth, D. Vigo, The Vehicle Routing Problem, SIAM, 2001.

Digital Library

[19]

Y. Xiao, Q. Zhao, I. Kaku, Y. Xu, Development of a fuel consumption optimization model for the capacitated vehicle routing problem, Comput. Oper. Res., 39 (2012) 1419-1431.

Digital Library

Cited By

Mulati MFukasawa RMiyazawa F(2022)The Arc-Item-Load and Related Formulations for the Cumulative Vehicle Routing ProblemDiscrete Optimization10.1016/j.disopt.2022.10071045:COnline publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1016/j.disopt.2022.100710
Gaur DSingh R(2017)A heuristic for cumulative vehicle routing using column generationDiscrete Applied Mathematics10.1016/j.dam.2016.05.030228:C(140-157)Online publication date: 10-Sep-2017
https://dl.acm.org/doi/10.1016/j.dam.2016.05.030
Fukasawa RHe QSong Y(2016)A Branch-Cut-and-Price Algorithm for the Energy Minimization Vehicle Routing ProblemTransportation Science10.1287/trsc.2015.059350:1(23-34)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1287/trsc.2015.0593
Show More Cited By

Routing vehicles to minimize fuel consumption
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis

Recommendations

Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem

The vehicle routing problem (VRP) has been addressed in many research papers. Only a few of them take time-dependent travel speeds into consideration. Moreover, most research related to the VRP aims to minimize total travel time or travel distance. In ...
Research on a Vehicle Routing Schedule to Reduce Fuel Consumption
ICMTMA '09: Proceedings of the 2009 International Conference on Measuring Technology and Mechatronics Automation - Volume 03

The Vehicle Routing Problem (VRP) is one of the most challenging combinatorial optimization task. This problem consists in designing the optimal set of routes for fleet of vehicles in order to serve a given set of customers. Almost all the research ...
Evaluation of ACC vehicles in mixed traffic: lane change effects and sensitivity analysis

Almost every automobile company is producing vehicles with adaptive cruise control (ACC) system onboard that enables a vehicle to do automatic vehicle following in the longitudinal direction. The ACC system is designed for driver's comfort and safety ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Operations Research Letters

Operations Research Letters Volume 41, Issue 6

November 2013

173 pages

ISSN:0167-6377

Issue’s Table of Contents

Copyright © Elsevier B.V.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 November 2013

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mulati MFukasawa RMiyazawa F(2022)The Arc-Item-Load and Related Formulations for the Cumulative Vehicle Routing ProblemDiscrete Optimization10.1016/j.disopt.2022.10071045:COnline publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1016/j.disopt.2022.100710
Gaur DSingh R(2017)A heuristic for cumulative vehicle routing using column generationDiscrete Applied Mathematics10.1016/j.dam.2016.05.030228:C(140-157)Online publication date: 10-Sep-2017
https://dl.acm.org/doi/10.1016/j.dam.2016.05.030
Fukasawa RHe QSong Y(2016)A Branch-Cut-and-Price Algorithm for the Energy Minimization Vehicle Routing ProblemTransportation Science10.1287/trsc.2015.059350:1(23-34)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1287/trsc.2015.0593
Cinar DGakis KPardalos P(2016)A 2-phase constructive algorithm for cumulative vehicle routing problems with limited durationExpert Systems with Applications: An International Journal10.1016/j.eswa.2016.02.04656:C(48-58)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1016/j.eswa.2016.02.046
Gaur DMudgal ASingh R(2016)Approximation Algorithms for Cumulative VRP with Stochastic DemandsProceedings of the Second International Conference on Algorithms and Discrete Applied Mathematics - Volume 960210.1007/978-3-319-29221-2_15(176-189)Online publication date: 18-Feb-2016
https://dl.acm.org/doi/10.1007/978-3-319-29221-2_15
Gitae Kim Yew-Soon Ong Chen Kim Heng Puay Siew Tan Zhang N(2015)City Vehicle Routing Problem (City VRP): A ReviewIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2015.239553616:4(1654-1666)Online publication date: 31-Jul-2015
https://dl.acm.org/doi/10.1109/TITS.2015.2395536
Xiao YKonak A(2015)A simulating annealing algorithm to solve the green vehicle routing & scheduling problem with hierarchical objectives and weighted tardinessApplied Soft Computing10.1016/j.asoc.2015.04.05434:C(372-388)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1016/j.asoc.2015.04.054

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents