Optimizacija ruta u tretiranju poljoprivrednog zemljišta

Abstract

Predmet istraţivanja doktorske disertacije je tretiranje poljoprivrednog zemljišta, odnosno kreiranje i izbor efikasnih ruta. Pregledom literature uoĉeno je da su u oblasti poljoprivrede rešavani razliĉiti lokacijski problemi, problemi alokacije i rutiranja. Znaĉajnu ulogu u odgovornom planiranju korišćenja poljoprivrednih resursa ima i prepoznavanje i rešavanje raznih optimizacionih problema koji se javljaju u procesu eksploatacije, o ĉemu svedoĉi i veliki broj istraţivanja koja se bave primenom metoda operacionih istraţivanja u ovoj oblasti. Problem koji se rešava se sastoji od izvršenja jedne vrste operacije na isparcelisanom poljoprivrednom zemljištu koje je potrebno tretirati korišćenjem avijacije. Karakteristike problema su: zemljište je isparcelisano i takve je površine da ga je nemoguće obraditi jednim preletom aviona; postoji nehomogena flota aviona i više potencijalnih letelišta koja se mogu koristiti za uzletanje i sletanje aviona; jednim preletom je moguće obraditi više parcela u zavisnosti od kapaciteta aviona. Prouĉavani problem se sastoji u odreĊivanju optimalnih ruta za dati broj aviona koji se koriste za tretiranje isparcelisanog poljoprivrednog zemljišta hemikalijama. Ovaj NP (Nondeterministic Polynomial) teţak problem je prikazan na grafu i predstavlja specijalnu varijantu roblema rutiranja vozila (The Vehicle Routing Problem - VRP) sa više depoa gde se generiše transportni plan za homogeni proizvod (hemikalije korišćene za tretiranje zemljišta) sa razliĉitih lokacija ponude (letelišta) do razliĉitih lokacija potraţnje (parcele) uz minimalne troškove. Da bi se jedno zemljište, podeljeno na parcele, efikasno tretiralo uz pomoć avijacije, potrebno je: izabrati letelišta koja će se koristiti za uzletanje i sletanje i odrediti alokaciju parcela letelištima, odrediti naĉin preleta svake parcele (obrada parcele, tj. izvršenje operacije nad parcelom) i redosled tretiranja parcela. Deo rešenja problema je i odreĊivanje broja potrebnih aviona, kao i struktura same flote. Kompleksnost problema i primeri većih dimenzija uslovili su formulisanje specijalne heuristike za rešavanje opisanog problema. Heuristikom su rešeni primeri većih dimenzija. Primenom razvijene specijalne heuristike dobijaju se planovi obrade - odnosno skup ruta kojima će poljoprivredni avion obraditi sve parcele na jednom poljoprivrednom zemljištu. Metoda obavijanja podataka (Data Envelopment Analysis – DEA) primenjena je za poreĊenje više planova obrade istog problema (dobijenih primenom heuristike) i odreĊivanje relativno efikasnih planova, a u okviru jednog efikasnog plana obrade primenom DEA metode su odreĊene relativno efikasne rute. U oba sluĉaja primenjen je CCR DEA izlazno orijentisani model. Predloţeni pristupi su testirani na primerima razliĉitih dimenzija i pokazalo se da se primenom DEA metode moţe oceniti efikasnost i izabrati planovi obrade i rute koje će se koristiti za tretiranje poljoprivrednog zemljišta.

The subject of this research is the agricultural land treatment, i.e. determination and selection of efficient routes in the treatment of agricultural land. The review of available literature proved that in the field of agriculture, different location problems, problems of allocation and routing are being solved. Identification and solving various optimization problems that arise in the treatment of the agricultural land have an important role in responsible planning of agricultural resources and its usage, which is confirmed in large number of studies that deal with the application of operational research methods in this field. The problem that is solved consists of performing one type of operation on a parceled agricultural land using agricultural aviation. The characteristics of the problem are: the land is divided into parcels; the surface of the whole land can not be processed by a single plane overflight; a non-homogeneous fleet of aircraft is used; there exists several potential airfields that can be used as landing sites; processing of several parcels can be done with one overflight (depending on the capacity of the aircraft). The studied problem consists of determining the optimal routes for a given set of aircraft used for chemical treatment of arable agricultural land divided into parcels. This NP (Nondeterministic Polynomial) problem is represented on a graph and represents a specific variant of the multidepot vehicle routing problem (VRP) where a min-cost plan for the transportation of a homogeneous product (chemicals used for land treatment) from different supply locations (airfields) to different demand locations (agricultural parcels) should be generated. In order to effectively treat an agricultural land divided into parcels using agricultural aviation, it is necessary to: choose the airfields for take-offs and to determine the parcel allocation to the airfields, determine the treatment way for each parcel and sequence of parcel treatment. Part of the solution of the problem is to determine the number of required aircrafts, as well as the structure of the fleet itself. The complexity of the problem and large dimensions of the problem examples have led to the formulation of a special heuristics. These examples of larger dimensions are solved using formulated heuristics. The application of the special heuristics results in processing plans - that is, a set of routes the agricultural aircraft will take and process all the parcels on one agricultural land. DEA (Data Envelopment Analysis) method is applied to compare multiple processing plans (obtained using heuristics) and to determine relatively efficient plans. Relatively efficient routes are determined within one efficient processing plan, also by using DEA method. In both cases, an output-oriented DEA model is applied. The proposed approaches are tested on examples of different dimensions and it is shown that, by applying the DEA method, the efficiency and selection of cultivation plans and routes that will be used for the treatment of agricultural land can be evaluated.