Use of GVRP as a Model of Two Specific Real World Problems and Its Bioinspired Solution

Introduction

This chapter is interested in biologically inspired computing, a branch of natural computing (de Castro 2006) where algorithms inspired from nature are developed to solve highly complex problems, in particular problems that cannot be addressed in a satisfactory way with traditional approaches. Under this paradigm, algorithmic models of processes observed in nature are developed and implemented on computers to explore solution spaces.

In the scientific literature, there is a growing interest in the exchange of ideas between natural systems and computational systems. Bio-inspired algorithms are representative of this trend and have been applied to a large variety of problems, including optimization problems. Among them, Vehicle Routing Problems (VRP) have generated a lot of attention, because they are inherently complex and hold a central place in real-world distribution activities.

Dantzig and Ramser (1959) proposed VRP for the first time with the objective to design optimum routing of a fleet of gasoline delivery trucks between a depot and a large number of service stations. VRP is a generic name given to a whole class of problems in which a set of routes for a fleet of vehicles based at one or several depots must be determined for a number of geographically dispersed customers (Laporte et al., 1989, 2002; Calvete et al., 2004; Baldacci et al., 2010). A depot, a set of geographically dispersed customers with demands, and a set of vehicles define it with capacity. In addition, customers must be visited exactly once and the total customer demand of a route must not exceed the vehicle capacity (Clarke & Wright, 1964; Laporte et al., 2002; Novoa et al., 2006). Its objective is to find a collection of K simple ways each corresponding to a vehicle route with minimum cost, distance or time.

To achieve this objective, high numbered of research has been conducted on VRP to design and develop different models and optimization methods. VRP models are differed by inclusion or exclusion of different restrictions. The commonly used restrictions on capacity of vehicle, total time, windows time, precedence relations between pairs of destinations, the number of depots (Laporte, 1992; Madsen et al., 1995; Paolo & Daniele, 2002; Chenghua & Xiaofeng, 2011) and others.

It is common to find the well-known travelling salesman problem (TSP), a canonical combinatorial optimization problem, widely studied in the scientific literature mentioned above. Given a graph with a number of vertices and a cost associated with each arc, the TSP looks for a least cost tour that visits each vertex exactly once (where the cost of a tour is the sum of its arc costs) (Lawler et al., 1985). In vehicle routing problems, side constraints are introduced to limit the number of vertices that can be visited with a single tour, thus leading to solutions that cover all vertices with different routes that start from and end at a particular vertex, called the depot. These problems are used to model various real-world applications. In the manufacturing sector, for example, they model transportation activities within the supply chain, that is, the movement of goods from suppliers to factories and then to customers. In the service sector, they include activities such as mail delivery, garbage collection, and public transportation, in another. (Potvin, 2009).

The chapter is organized as follows. Section 2 introduces a brief overview of the general Vehicle Routing Problem (VRP). Then, Sections 3 to 6 introduce the selected four bio-inspired algorithms, namely Ant Colony Optimization (ACO) and Firefly (FF, in this order, and describe their application to two real world logistic problems treated as VRPs. Section 7 results obtained from the 4 algorithms application to real world problems are discussed. Concluding remarks follow in Section 8.