Elsevier

Biosystems Engineering

Volume 124, August 2014, Pages 40-52
Biosystems Engineering

Research Paper
An application of the vehicle routing problem to biomass transportation

https://doi.org/10.1016/j.biosystemseng.2014.06.009Get rights and content

Highlights

  • The biomass collection problem is addressed as a vehicle routing problem.

  • A hybrid approach based on genetic algorithms maximises transportation efficiency.

  • Approaches from industrial engineering are translated to agricultural applications.

Pruning is a cultural operation linked to Mediterranean agricultural management and it offers through its wastes the chance to procure biofuels. Currently, these residues are disposed of by burning or shredding, not being exploited because of several technical difficulties in extraction, handling and transport as well as because of the lack of accurate data on the quantity and suitability of these residues. However, recent work has reported methods of supplying new biomass detection models and concentration locations. These make it possible to tackle reliable collection plans as a part of the decision support system in a biomass supply management information system. This paper addresses the biomass collection problem, as an application of the classical vehicle routing problem, where minimum cost routes have to be calculated for a fleet of several agricultural vehicles (chippers, trucks, tipper trailers and tractors). A hybrid approach based on genetic algorithms and local search methods is presented to solve a real case study. Results show a significant improvement in the operational efficiency obtained by applying such methods that come from the industrial engineering domain.

Introduction

Biomass is defined as any organic matter not fossilised and it can have multiple industrial applications in pharmacy, cosmetics, textiles, wood, paper and construction. Biomass can also be a source of energy since it can be converted into biofuels which are end-marketable energy products. Biomass feedstock production can be acquired from numerous sources such as agricultural crops (maize, sorghum, barley, etc), agricultural residues (maize stover, wheat straw, etc), energy crops (switch grass, energy cane, willow, etc), forest residues (logging residues, forest thinning, sawdust, etc) and wastes (manure, food processing waste, etc). Under EU Directive 2009/28/EC on the promotion of renewable energy, the European Union established, in every Member State, the goal of reaching a minimum 10% share of renewable energy in the transport sector by 2020. This directive also intends to ensure the expansion of the use of sustainable biofuels in the EU, in terms that their employment generates a clear and net greenhouse gas (GHG) saving and has no negative impact on biodiversity and land use. Markevičius, Katinas, Perednis, and Tamašauskienė (2010) recognised up to 35 different criteria to estimate biofuels sustainability. These include, inter alia, aspects related to environmental issues such as ecosystems protection, ecosystem connectivity, crop diversity and soil protection.

On the sustainable perspective of ecosystems protection and crop diversity, a large amount of biomass can be obtained from Mediterranean agricultural management, especially from pruning operations, renewal of plantations and crop residues. Up to now, this source of biomass has not been mobilised and used due to several technical difficulties in extraction, handling and transport as well as the lack of enough information on the quantity and suitability of these residues. Currently these wastes are piled up and disposed of by burning or shredding, not getting any direct benefit, but rather a cost and also taking a high risk of fire danger when fields are close to forest areas. In addition to the contribution to sustainable development, using this additional biomass as a source of energy would also provide benefits in relation to maintenance operations and potential extra income for producers, in addition to those obtained from the crop.

Pruning offers the possibility to obtain biofuels, such as chips, pellets or ethanol by means of acid hydrolysis and subsequent fermentation. Fruit tree production in Spain is smallholder-structured, which means that currently the exploitation of such wastes is mostly not viable for an individual small producer to sustain due to high harvesting and transport costs. Nevertheless, it has led to the creation of associated groups (cooperatives, agrarian transformation societies and marketing companies) which link together large areas in order to carry out harvesting operations and selling crops. Consequently, it would be possible for large-scale pruning also to be coordinated by these partnership structures, who could share resources and take advantage of economies of scale, as the equipment needed to accomplish the pruning and removal is expensive. On the other hand, the collection area of a medium-sized cooperative is usually characterised by considerable spatial dispersion as each partner typically has a rather large number of fields in several locations. This type of geographical distribution involves a great organisational effort for technicians responsible for machinery management to make possible cost-efficient pruning and collection operations.

Usually, procedures to plan the working sequences of a cooperative's equipment and vehicles are based on the extensive knowledge of the area, previous experience of past seasons and on negotiations with members. According to the peculiarity of the biomass collection process (small amounts of biomass volume at highly dispersed collection points) this kind of procedure is not good enough to achieve a cost-effective solution to ensure an optimised supply system for long term success of a biomass processing facility. Therefore, beyond the mere association of producers, the execution of biomass collection and transportation operations has to be efficiently planned in order to consider biomass from agricultural pruning as an agroforestry sustainable resource. Consequently, advanced techniques and logistics models need to be developed for determining the optimal collection points, managing the best transportation routes and deciding on the desirable location of the processing industries. Cost-effective planning requires the allocation and dispatch of each vehicle to land parcels, the computation of the in-parcel path for each vehicle, as well as the determination of their appropriates routes. Optimisation criteria taking into account issues such as minimising non-productive time, fuel consumption and distance travelled have to be applied in order to get significant economic and environmental benefits. Hence, it is necessary to describe such operations by mathematical models. Parameters regarding vehicles and machines (travelling speed, capacity, unloading and loading time, operating performance, etc.), parcels (geometry, presence of obstacles, biomass production volumes, etc.), depots (position, capacity, etc.) make such modelling difficult.

Previous work has already been reported by the authors supplying biomass detection models, harvesting techniques analysis and biomass concentration locations. This paper addresses the biomass harvesting and collection problem (BCP) within the context of a sustainable biomass supply chain management. The solution of BCP obtains optimised minimum cost routes for a fleet of agricultural vehicles (chippers, trucks, tipper trailers and tractors) describing the sequence in which biomass has to be harvested and collected from different production locations (orchards) and transported to a common storage location (biomass concentration node) for further distribution to a conversion facility. The biomass concentration node needs to have been determined in a previous planning step. Models already developed by the authors (Velázquez-Martí & Annevelink, 2009) integrate diverse sources as official cartographic and/or spatial bases with images of satellite in raster format or clouds of points from airborne light detection and ranging (LIDAR) to determine the location of the biomass concentration nodes.

The BCP belongs to a class of Operations Research problems known as vehicle routing problems (VRP). The VRP has been extensively discussed and has, for over fifty years, provided optimal solutions to fleet planning in many real applications involving planning of vehicle fleets. However, despite the fact that field tasks involve the collaborative use of vehicles, only recently have these concepts been transferred to the agricultural environment (Bochtis and Sørensen, 2009, Bochtis and Sørensen, 2010, Bochtis et al., 2013).

The VRP was first introduced by Dantzig, Fulkerson, and Johnson (1954) and it has been widely studied since. It is a complex combinatorial optimisation problem to define the efficient use of a fleet of vehicles that must make a number of stops to pick up and/or deliver products (Fisher, 1995). Each stop corresponds to a certain customer and has to be assigned to exactly one vehicle in a specific order.

According to the theory of computational complexity, most of these problems are non-deterministic polynomial time complete (NP-C) (Garey & Johnson, 1979). Therefore, procedures proposed usually focus on the use of algorithmic methods based on the application of meta-heuristics. These techniques have become recognised as one of the best approaches to solve many real complex combinatorial problems. During the last decade, nature-inspired intelligence has become popular through the development and use of intelligent paradigms in advanced information systems design. The use of meta-heuristics methods representing successful animal team behaviour has been extended, i.e., particle swarm optimisation inspired by flocks of birds or schools of fish (Kennedy, Kennedy, Eberhart, & Shi, 2001), artificial immune systems (Dasgupta, 1998, De Castro and Timmis, 2002), optimised performance of bees (Baykasoglu, Ozbakor, & Tapkan, 2007), or ant colony optimisation (Dorigo & Stützel, 2004). However, the most popular of these are genetic algorithms (GAs). Since their introduction in 1975 by Holland, a very large number of applications have been developed in the context of GAs and more generally in evolutionary computation (Goldberg & Chie, 1987).

A simple hybrid approach based on genetic algorithms (HGA) and local search methods is presented to solve a real case study. The paper is organised as follows. First, the problem of harvesting and collecting residual agricultural biomass is described and modelled in Section 2. Next, the proposed HGA approach to solve the problem is developed in Section 3 and an experimental study is carried out in Section 4.

Section snippets

Problem description and mathematical formulation

Pruning fruit trees is usually performed annually. It is usual to distinguish between traditional and hedge pruning techniques. Hedge pruning is performed by disk machines and consists of flat indiscriminate cuts in the row of fruit-trees. On the other hand, traditional pruning is done with hand tools and it discriminates the parts to cut from thick branches to small sideshoots. Today either technique can be found or the concurrence of both as they can complement each other. In the case of

Hybrid solution approach based on GAs

The VRP is NP-hard, and so is BCP, since the TSP is a special case of VRP. In practice, the VRP is significantly more difficult to solve than a TSP of the same size. The literature is rather extensive and research approaches extend from the use of pure optimisation methods for small size problems, to heuristics and meta-heuristics for medium and large-size problems with complex constraints (Cordeau et al., 2002, Toth and Vigo, 2002).

Experimental study

The proposed algorithm has been implemented in the commercial software MATLAB® release R2007b. The set of input parameters for the HGA were {Pop = 80, Iter = 6000, Elite = 0.125, Xover = 0.375, Mut = 0.5}. These settings are similar to those determined by Wang and Lu (2010), where the response surface methodology is employed to conduct systematic experiments with various crossover and mutation probabilities in order to determine the optimal combination of these parameters when solving the

Conclusions

An algorithmic approach based on genetic algorithms and local search heuristics to generate the collecting sequences of residual biomass has been developed. The resulting sequences are optimal in the sense that they minimise the total travelled distance in the field. The BCP was formulated and modelled in terms of mathematical programming.

The proposed translation of vehicle routing applications to the agricultural engineering domain enables a global perspective on sustainability of the biomass

References (39)

  • C. Perpiñá et al.

    Methodology based on geographic information systems for biomass logistics and transport optimisation

    Renewable Energy

    (2009)
  • B. Velázquez-Martí et al.

    Mathematical algorithms to locate factories to transform biomass in bioenergy focused on logistic network construction

    Renewable Energy

    (2010)
  • B. Velázquez-Martí et al.

    Quantification of the residual biomass obtained from pruning of trees in mediterranean almond groves

    Renewable Energy

    (2011)
  • D. Abbas et al.

    Cost analysis of forest biomass supply chain logistics

    Journal of Forestry

    (2013)
  • E. Alba et al.

    A hybrid cellular genetic algorithm for the capacitated vehicle routing problem

  • A. Baykasoglu et al.

    Artificial bee colony algorithm and its application to generalized assignment problem

  • J.J. Bentley

    Fast algorithms for geometric traveling salesman problems

    ORSA Journal on Computing

    (1992)
  • J. Berger et al.

    A hybrid genetic algorithm for the capacitated vehicle routing problem

  • R.M. Brady

    Optimization strategies gleaned from biological evolution

    Nature

    (1985)
  • Cited by (49)

    • Opportunities and challenges in industrial production of biofuels

      2022, Biofuels and Bioenergy: Opportunities and Challenges
    • A two-echelon location-routing problem for biomass logistics systems

      2021, Biosystems Engineering
      Citation Excerpt :

      To maximise profits and minimise risks, the best transportation route was established. Carlos et al. (2014) studied an application of the vehicle routing problem to biomass transportation. A hybrid approach based on genetic algorithms and local search methods was presented to solve a case study, thereby significantly improving operational efficiency.

    View all citing articles on Scopus
    View full text