A hybrid genetic algorithm for route optimization in the bale collecting problem

C. Gracia, B. Diezma-Iglesias, P. Barreiro

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.

Keywords


precision agriculture; logistics; wheat harvest

Full Text:

PDF

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




DOI: 10.5424/sjar/2013113-3635