Group Genetic Algorithm for Heterogeneous Vehicle Routing

Group Genetic Algorithm for Heterogeneous Vehicle Routing

Michael Mutingi (Namibia University of Science and Technology, Namibia)
Copyright: © 2014 |Pages: 20
DOI: 10.4018/978-1-4666-4785-5.ch009
OnDemand PDF Download:
List Price: $37.50


Cost-efficient transportation is a central concern in the transportation and logistics industry. In particular, the Heterogeneous Vehicle Routing Problem (HVRP) has become a major optimization problem in supply chains involved with delivery (collection) of goods to (from) customers. In this problem, there are limited vehicles of different types with respect to capacity, fixed cost, and variable cost. The solution to this problem involves assigning customers to existing vehicles and, in relation to each vehicle, defining the order of visiting each customer for the delivery or collection of goods. Hence, the objective is to minimize the total costs, while satisfying customer requirements and visiting each customer exactly once. In this chapter, an enhanced Group Genetic Algorithm (GGA) based on the group structure of the problem is developed and tested on several benchmark problems. Computational results show that the proposed GGA algorithm is able to produce high quality solutions within a reasonable computation time.
Chapter Preview


Cost efficient transportation is imperative in logistics and supply chain management. Logistics and transportation costs account for about 20% of the total cost of a product (Hoff et al., 2010). Moreover, increasing globalization, economic growth, and consumption continue to increase the need for efficient transportation. Global completion among logistics service providers lead to higher demand for cost efficiency, better customer services, responsiveness, and agility. Recently, the ever-growing environmental concerns and the ensuing legislation have become one of the major drivers of eco-efficient transportation. As such, logistics and transportation industry is often faced with the problem of fleet composition at almost all decision levels. Decision makers have to strike a balance between vehicle fleet ownership and fleet subcontracting, considering external market variables such as expected demand and transportation costs. This is further complicated by the fact that, in the real-world, vehicle fleets are inherently heterogeneous rather than homogeneous (Mutingi and Mbohwa, 2012). The goal of fleet composition is to determine the optimal fleet, considering all costs, revenues and other relevant constraints.

In an industrial set up, vehicle fleets are seldom homogeneous (Mutingi and Mbohwa, 2012). More often than not, vehicles are acquired over long planning horizons, such that the cumulative fleet will have different features due to technological changes (Hoff et al., 2010). Consequently, vehicle operating costs will vary across vehicles over their lifetimes. In addition, most managers would prefer to keep vehicles of different types as a way of improving their operations agility. Transportation demand features, in terms of volume, time and terrain, may also contribute to the overall need for keeping a heterogeneous fleet. Basically, vehicles differ in their capacity or physical dimensions and operating costs. These factors should be accounted for at all levels of decision making. Overall, fleet composition and routing occurs at strategic, tactical and operational levels.

In the long term, heterogeneous fleet composition and routing involves capacity adjustment (that is, fleet resizing, composition and allocation). This usually entails huge capital involvement, as the organization may wish to acquire capacity to cover a planning horizon of say 15 years. In such cases, uncertainty is high; it is difficult to anticipate transportation demand, costs and revenues in the long term. Consequently, careful risk management practices are crucial; risk can be reduced by establishing long term and short term contracts, which calls for effective usage of heterogeneous fleets.

Over a few years, heterogeneous fleet composition is concerned with capacity resizing, subject to the existing fleet. As such, uncertainty in transportation demand and operational costs will be much less than at the strategic level. Routing aspects are often included at a more detailed level. Decisions at this level involve contract negotiations, optimal vehicles to be acquired or to be chartered in or out, which vehicles should be sold, and vehicle route assignment (Hoff et al., 2010). At operational level, vehicle fleet composition usually consists of the integrative task of selecting the set of vehicles (selected from an existing fleet) to satisfy customer orders, and simultaneously determine the best routing patterns. Over a short term, certainty is relatively higher than in strategic and tactical transportation planning. Oftentimes, the fleet of vehicles to be used is usually fixed over the short term. As a result, flexibility in terms of fleet size adjustment is limited.

Complete Chapter List

Search this Book: