Heuristic Algorithms for Solving the Generalized Vehicle Routing Problem

  • Petrică Claudiu Pop North University of Baia Mare, Department of Mathematics and Informatics Romania, V. Babeş , 430083, Baia Mare
  • Ioana Zelina North University of Baia Mare, Department of Mathematics and Informatics Romania, V. Babeş , 430083, Baia Mare
  • Vasile Lupşe North University of Baia Mare, Department of Mathematics and Informatics Romania, V. Babeş , 430083, Baia Mare
  • Corina Pop Sitar North University of Baia Mare, Department of Economics Romania, V. Babeş , 430083, Baia Mare E-mail:
  • Camelia Chira “Babes-Bolyai” University of Cluj-Napoca Romania, M. Kogalniceanu, 400084, Cluj-Napoca

Abstract

The vehicle routing problem (VRP) is one of the most famous combinatorial optimization problems and has been intensively studied due to the many practical applications in the field of distribution, collection, logistics, etc. We study a generalization of the VRP called the generalized vehicle routing problem (GVRP) where given a partition of the nodes of the graph into node sets we want to find the optimal routes from the given depot to the number of predefined clusters which include exactly one node from each cluster. The purpose of this paper is to present heuristic algorithms to solve this problem approximately. We present constructive algorithms and local search algorithms for solving the generalized vehicle routing problem.

References

[1] R. Baldacci, E. Bartolini and G. Laporte, Some applications of the Generalized Vehicle Routing Problem, Le Cahiers du GERAD, G-2008-82, 2008.

[2] G. Clarke and J.W. Wright, Scheduling of Vehicles From a Central Depot to a Number of Delivery Points, Operations Research, Vol. 12, pp. 568-581, 1964.
http://dx.doi.org/10.1287/opre.12.4.568

[3] M. Fischetti, J.J. Salazar and P. Toth, A branch-and-cut algorithm for the symmetric generalized traveling salesman problem, Operations Research, 45:378-394, 1997.
http://dx.doi.org/10.1287/opre.45.3.378

[4] G. Ghiani, G. Improta, An efficient transformation of the generalized vehicle routing problem, European Journal of Operational Research, Vol. 122, pp. 11-17, 2000.
http://dx.doi.org/10.1016/S0377-2217(99)00073-9

[5] I. Kara and T. Bektas, Integer linear programming formulation of the generalized vehicle routing problem, in Proc. of the 5-th EURO/INFORMS Joint International Meeting, 2003.

[6] I. Kara and P.C. Pop, New Mathematical Models of the Generalized Vehicle Routing Problem and Extensions, in Proc. of the International Conference on Applied Mathematical Programming and Modelling, Bratislava, Slovakia, May 27-30, 2008.

[7] G. Laporte, Location-routing problems, in B.L. Golden and A.A. Assad (eds.), Vehicle Routing: Methods and Studies, North-Holland, Amsterdam, pp. 163-197, 1988.

[8] G. Laporte, S. Chapleau, P.E. Landry and H. Mercure, An algorithm for the design of mail box collection routes in urban areas, Transportation Research B, Vol. 23, pp. 271-280, 1989.
http://dx.doi.org/10.1016/0191-2615(89)90029-5

[9] G. Laporte, M. Gendreau, J-Y. Potvin and F. Semet, Classical and modern heuristics for the vehicle routing problem, International Transactions in Operational Research, Volume 7, Issue 4-5, pp. 285 - 300, 2006.

[10] G. Nagy and S. Salhi, Location-routing issues: Models and methods, European Journal of Operational Research, Vol. 177, pp. 649-672, 2007.
http://dx.doi.org/10.1016/j.ejor.2006.04.004

[11] C.M. Pintea, D. Dumitrescu and P.C. Pop, Combining heuristics and modifying local information to guide ant-based search, Carpathian Journal of Mathematics, Vol. 24, No. 1, pp. 94-103, 2008.

[12] P.C. Pop, C. Pop Sitar, I. Zelina and I. Tascu, Exact algorithms for generalized combinatorial optimization problems, Lecture Notes in Computer Science, Vol. 4616, pp. 154-162, 2007.
http://dx.doi.org/10.1007/978-3-540-73556-4_18

[13] P.C. Pop, C.M. Pintea, I. Zelina and D. Dumitrescu, Solving the Generalized Vehicle Routing Problem with an ACS-based Algorithm, American Institute of Physics (AIP), Conference Proceedings: BICS 2008, Vol.1117, No.1, 157–162, 2009.
http://dx.doi.org/10.1063/1.3130618

[14] P.C. Pop, Efficient Transformations of the Generalized Combinatorial Optimization Problems into Classical Variants, Proceedings of the 9-th Balkan Conference on Operational Research, Constanta, Romania, 2-6 September 2009.

[15] P.C. Pop, A survey of different integer programming formulations of the generalized minimum spanning tree problem, Carpathian Journal of Mathematics, Vol. 25, No. 1, pp. 104-118, 2009.

[16] A. van Breedam, An analysis of the behavior of the heuristics of the vehicle routing problem for a selection of problems, with vehicle-related, customer-related and time-related constraints, Ph.D. Dissertation, University of Antwerp, Belgium, 1994.
Published
2011-03-01
How to Cite
POP, Petrică Claudiu et al. Heuristic Algorithms for Solving the Generalized Vehicle Routing Problem. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 6, n. 1, p. 158-165, mar. 2011. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/2210>. Date accessed: 16 july 2020. doi: https://doi.org/10.15837/ijccc.2011.1.2210.

Keywords

network design, combinatorial optimization, generalized vehicle routing problem, heuristic algorithms