Vehicle routing problem for minimizing consumption of energy in three dimensional space

Hajar Ghahremani-Gol, Farzad Didehvar, Asadollah Razavi


The vehicle routing problem VRP is usually studied in two dimensional Euclideanspaces. In this paper a variant of VRP was proposed, when the points are lying in thethree dimensional space, as it is often the case in the real problem. The cost matrix ofthe consumed energy was not symmetric. The minimum cost of total consumed energywas determined by identical vehicles. A new method was presented to compute thedistance between every two points and the consumed energy.


Consumed energy in three dimensional space; metaheuristics; transportation; vehicle routing problem.

Full Text:



Ascheuer, N., Fischetti, M. & Grtِschel, M. (2001) Solving the asymmetric traveling salesman problem

with time windows by branch-and-cut. Mathematical Programming Series B, 90 (3):475-506.

Chen, H.K. & Wang, H. (2012) A two-stage algorithm for the extended linehaul-feeder vehicle routing

problem with time windows. International Journal of Shipping and Transport Logistics (IJSTL),


Clarke, G. & Wright, J.W. (1964) Scheduling of vehicles from a central depot to a number of delivery

points. Operations Research, 12:568-581.

Dantzig, G. & Ramser, J. (1959) The truck dispatching problem. Management Science, 6(1):81-91.

Desrosiers, J., Soumis, F. & Desrochers, M. (1984) Routing with time windows by column generation.

Networks, 14:545-565.

Do Carmo, M.P. (1976) Differential geometry of curves and surfaces. Prentice-Hall.

Dorigo, M. & Gambardella, L.M. (1997) Ant colony system: A cooperative learning approach to the

traveling salesman problem . IEEE Transactions on Evolutionary Computation, 1(1):53-66.

Fisher, M.L. & Jaikumar, R. (1978) A decomposition algorithm for large-scale Vehicle Routing. Working

Paper 78–11-05, Department of Decision Sciences, University of Pennsylvania.

Flood, M., 1956. The traveling-salesman problem. Operations Research, 4(1):61-75.

Geetha, S., Vanathi, P.T. & Poonthalir, G. (2012) Metaheuristic approach for the multy-depot vehicle

routing problem. Applied Artificial Intelligence, 26(9):878-901.

Ghahremani-Gol, H., Didehvar, F. & Razavi, A. (2012) On Distance Function among Finite Set of

Points. arXiv:1203.6177v1 [cs.DM].

Gillett, B.E. & Miller, L.R. (1974) A heuristic algorithm for the vehicle dispatch problem. Operations

Research, 22:340-349.

Golden, B., Raghavan, S. & Wasil, E. (2008) The vehicle routing problem : latest advances and new

challenges. NewYork: Springer.

Griffiths, D.F. & Higham, D.J. (2011) Numerical methods for ordinary differential equations, Springer.

Laporte G. (2009) Fifty years of vehicle routing. Transportation Science, 43:408-416.

Li, F., Golden, B. & Wasil, E. (2007) The open vehicle routing problem: algorithms, large scale test

problems, and computational results. Computers & Operations Research, 34(10):2918-2930.

Nazif, H. & Lee, L.S. (2012) Optimized crossover genetic algorithm for capacitated vehicle routing

problem. Applied Mathematical Modeling, 36:2110-2117.

O’Neill, B. (1966) Elementary differential geometry. Academic Press.

Osman, I. (1993) Metastrategy simulated annealing and tabu search algorithms for the vehicle routing

problem. Operations Research, 41:421-451.

Pillac, V., Gendreau, M., Guéret, Ch. & Medaglia, A.L. (2013) A review of dynamic vehicle routing

problems. European Journal of Operational Research, 225(1):1-11.

Roberti, R. & Toth. P. (2012) Models and algorithms for the Asymmetric Traveling Salesman Problem:

an experimental comparison, European Journal on Transportation and Logistics, 1(1-2):113-133.

Sedighpour, M., Ahmadi, V., Yousefikhoshbakht, M., Didehvar, F. & Rahmati, F. (2014) Solving the

open vehicle routing problem by a hybrid ant colony optimization. Kuwait Journal of Science &

Engineering, 41(3):139-162.

Taillard, E.D. (1993) Parallel Iterative search methods for vehicle routing problems. Networks, 23:661-

Tarantilis, C.D., Zachariadis, E.E. & Kiranoudis, C.T. (2009) A Hybrid metaheuristic algorithm

for the integrated vehicle routing and three-dimensional container-loading problem. intelligent

transportation systems, IEEE Transactions, 10(2):255-271.

Tas, D., Jabali, O. & Woensel, T.V. (2014) A Vehicle routing problem with flexible time windows.

Computers & Operations Research, 52:39-54.

Wisniewski, M., Ritt, M. & Buriol. L.S. (2011) A tabu search algorithm for the capacitated vehicle

routing problem with three-dimensional loading constraints. Anais do XLIII Simp sio Brasileiro

de Pesquisa Operacional. Ubatuba, Brazil, 1502-1511.

Yousefikhoshbakht, M., Didehvar, F. & Rahmati, F. (2014) An efficient solution for the vehicle routing

problem by using a hybrid elite ant colony optimization. International Journal of Computers,

Communications & Control, 9(3):156-162.

Zhang, X. & Tang, L. (2009) A new hybrid ant colony optimization algorithm for the vehicle routing

problem. Pattern Recognition Letters, 30(152):848-855.


  • There are currently no refbacks.