A hybrid genetic algorithm for route optimization in the bale collecting problem
Abstract
The bale collecting problem (BCP) appears after harvest operations in grain and other crops. Its solution defines the sequence of collecting bales which lie scattered over the field. Current technology on navigation-aid systems or auto-steering for agricultural vehicles and machines, is able to provide accurate data to make a reliable bale collecting planning. This paper presents a hybrid genetic algorithm (HGA) approach to address the BCP pursuing resource optimization such as minimizing non-productive time, fuel consumption, or distance travelled. The algorithmic route generation provides the basis for a navigation tool dedicated to loaders and bale wagons. The approach is experimentally tested on a set of instances similar to those found in real situations. In particular, comparative results show an average improving of a 16% from those obtained by previous heuristics.Downloads
References
Amiama C, Bueno J, Alvarez CJ, Pereira JM, 2008. Design and field test of an automatic data acquisition system in a self-propelled forage harvester. Comput Electron Agric 61: 192-200. http://dx.doi.org/10.1016/j.compag.2007.11.006
Baker BM, Ayechew MA, 2003. A genetic algorithm for the vehicle routing problem. Comput Oper Res 30: 787-800. http://dx.doi.org/10.1016/S0305-0548(02)00051-5
Baykasoglu A, Ozbakor L, Tapka P, 2007. Artificial bee colony algorithm and its application to generalized assignment problem. In: Swarm intelligence, focus on ant and particle swarm optimization (Chan FT, ed.). I-Tech Education and Publishing, Vienna (Austria), pp: 113-144. http://dx.doi.org/10.5772/5101
Bentley JJ, 1992. Fast algorithms for geometric traveling salesman problems. ORSA J Comput 4: 387-411. http://dx.doi.org/10.1287/ijoc.4.4.387
Bochtis DD, Sorensen CG, 2009. The vehicle routing problem in field logistics part I. Biosystems Eng 104: 447-457. http://dx.doi.org/10.1016/j.biosystemseng.2009.09.003
Bochtis DD, Sorensen CG, 2010. The vehicle routing problem in field logistics: Part II. Biosystems Eng 105: 180-188. http://dx.doi.org/10.1016/j.biosystemseng.2009.10.006
Bochtis DD, Dogoulis P, Busato P, Sorensen CG, Berruto R, Gemtos T, 2013. A flow-shop problem formulation of biomass handling operations scheduling. Comput Electron Agric 91: 49-56. http://dx.doi.org/10.1016/j.compag.2012.11.015
Botey M, 2009. La concentración parcelaria en Castilla y León. Caracterización de la parcelación a través del análisis multivariante. Doctoral thesis. Univ. Politécnica, Madrid, Spain. [In Spanish].
Brady RM, 1985. Optimization strategies gleaned from biological evolution. Nature 317: 804-806. http://dx.doi.org/10.1038/317804a0
Chen J, Pan JC, Lin C, 2008. A hybrid genetic algorithm for the re-entrant flow-shop scheduling problem. Expert Syst Appl 34: 570-577. http://dx.doi.org/10.1016/j.eswa.2006.09.021
Cook SE, Bramley RG, 1998. Precision agriculture - Opportunities, benefits and pitfalls. Aust J Exp Agric 38: 753-763. http://dx.doi.org/10.1071/EA97156
Cordeau JF, Gendreau M, Laporte G, Potvin JV, Semet F, 2002. A guide to vehicle routing heuristics. J Oper Res Soc 53: 512-522. http://dx.doi.org/10.1057/palgrave.jors.2601319
Dantzig G, Fulkerson R, Johnson DS, 1954. Solution of a large-scale travelling salesman problem. Oper Res 2: 393-410. http://dx.doi.org/10.1287/opre.2.4.393
Dasgupta D (ed.), 1999. Artificial immune systems and their applications, Springer-Verlag Inc, Berlin, Germany. http://dx.doi.org/10.1007/978-3-642-59901-9
Davis L, 1985. Job shop scheduling with genetic algorithms. Proc of the First Int Conf on Genetic Algorithms and their Applications, Pittsburg, PA (USA). July 24-26. pp: 136-140.
De Castro LN, Timmis J, 2002. Artificial immune systems: a new computational approach. Springer-Verlag Inc, London, UK.
Dorigo M, Stützle T, 2004. Ant colony optimization. MIT Press, Cambridge, MA, USA. http://dx.doi.org/10.1007/b99492
Eksioglu B, Vural AV, Reisman A, 2009. The vehicle routing problem: A taxonomic review. Comput Ind Eng 57: 1472-1483. http://dx.doi.org/10.1016/j.cie.2009.05.009
Garey MR, Johnson DS, 1979. Computers and intractability: a guide to the theory of NP-completeness. WH Freeman & Company, NY. PMCid:PMC1619045
Gendreau M, Laporte G, Potvin JY, 1998. Metaheuristics for the vehicle routing problem. Technical Report G-98-52, Les Cahiers du GERAD, Montréal, Quebec, Canada.
Gillet BE, Miller LR, 1974. A heuristic algorithm for the vehicle-dispatch problem. Oper Res 22: 340-349. http://dx.doi.org/10.1287/opre.22.2.340
Goldberg DE, 1989. Genetic algorithms in search, optimization and machine learning. Kluwer Acad Publ, Boston, MA, USA.
Gracia C, Andrés C, Gracia L, 2013. A hybrid approach based on genetic algorithms to solve the problem of cutting structural beams in a metalwork company. J Heuristics 19(2): 253-273. http://dx.doi.org/10.1007/s10732-011-9187-x
Grisso RD, Cundiff JS, Vaughan DH, 2007. Investigating machinery management parameters with computers tools, ASABE Conf, Paper 071030.
Hameed IA, Bochtis DD, Sorensen CG, Vougioukas S, 2012. An object-oriented model for simulating agricultural i-field machinery activities. Comput Electron Agric 81: 24-32. http://dx.doi.org/10.1016/j.compag.2011.11.003
Holland JH, 1975. Adaptation in natural and artificial systems (Holland JH, ed.). Ann Arbor MI Univ of Michigan Press, MI, USA.
Jünger M, Reinelt G, Rinaldi G, 1995. The traveling salesman problem. In: Network models. Handbooks on Operations Research and Management Science 7 (Ball MO, Magnanti TL, Monma CL, Nemhauser GL, eds.). Elsevier, Amsterdam, pp: 225-330.
Kennedy JF, Kennedy J, Eberhart R, Shi Y, 2001. Swarm intelligence. Academic Press Inc, London.
Laporte G, Gendreau M, Potvin JY, 2000. Classical and modern heuristics for the vehicle routing problem. Int Trans Oper Res 7: 285-300. http://dx.doi.org/10.1111/j.1475-3995.2000.tb00200.x
Martin O, Otto SW, Felten EW, 1991. Large-step markov chains for the travelling salesman problem. Complex Syst 5(3): 299-326.
Nikkilä R, Seilonen I, Koskinen K, 2010. Software architecture for farm management information systems in precision agriculture. Comput Electron Agric 70: 328-336. http://dx.doi.org/10.1016/j.compag.2009.08.013
Sorensen CG, Pesonen L, Bochtis DD, Vougioukas SG, Suomi P, 2011. Functional requirements for a future farm management information system. Comput Electron Agric 76: 266-276. http://dx.doi.org/10.1016/j.compag.2011.02.005
Toth P, Vigo D, 2002. Branch-and-bound algorithms for the capacitated vehicle routing problem. In: The vehicle routing problem (Toth P, Vigo D, eds.). SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, PA (USA), pp: 29-51. http://dx.doi.org/10.1137/1.9780898718515.ch2
Wang C, Lu J, 2010. An effective evolutionary algorithm for the practical capacitated vehicle routing problems. J Intell Manuf 2: 363-375. http://dx.doi.org/10.1007/s10845-008-0185-2
Zhang N, Wang M, Wang N, 2002. Precision agriculture—A worldwide overview, Comput Electron Agric 36(2-3): 113-132. http://dx.doi.org/10.1016/S0168-1699(02)00096-0
© CSIC. Manuscripts published in both the print and online versions of this journal are the property of the Consejo Superior de Investigaciones Científicas, and quoting this source is a requirement for any partial or full reproduction.
All contents of this electronic edition, except where otherwise noted, are distributed under a Creative Commons Attribution 4.0 International (CC BY 4.0) licence. You may read the basic information and the legal text of the licence. The indication of the CC BY 4.0 licence must be expressly stated in this way when necessary.
Self-archiving in repositories, personal webpages or similar, of any version other than the final version of the work produced by the publisher, is not allowed.
