Heuristic Algorithms for Solving the Generalized Vehicle Routing Problem

Authors

  • 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

Keywords:

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

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

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

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

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

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

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.

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.

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.

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

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.

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

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.

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

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

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.

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.

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

Issue

Vol. 6 No. 1 (2011): International Journal of Computers Communications & Control (March)

Section

Articles

License

ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.

You are free to:

-Share: copy and redistribute the material in any medium or format;

-Adapt: remix, transform, and build upon the material.

The licensor cannot revoke these freedoms as long as you follow the license terms.

 

DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.