A meta-heuristic algorithm for heterogeneous fleet vehicle routing problems with two-dimensional loading constraints

Abstract

The two-dimensional loading heterogeneous fleet vehicle routing problem (2L-HFVRP) is a variant of the classical vehicle routing problem in which customers are served by a heterogeneous fleet of vehicles. These vehicles have different capacities, fixed and variable operating costs, length and width in dimension, and two-dimensional loading constraints. The objective of this problem is to minimize transportation cost of designed routes, according to which vehicles are used, to satisfy the customer demand. In this study, we proposed a simulated annealing with heuristic local search (SA_HLS) to solve the problem and the search was then extended with a collection of packing heuristics to solve the loading constraints in 2L-HFVRP. To speed up the search process, a data structure was used to record the information related to loading feasibility. The effectiveness of SA_HLS was tested on benchmark instances derived from the two-dimensional loading vehicle routing problem (2L-CVRP). In addition, the performance of SA_HLS was also compared with three other 2L-CVRP models and four HFVRP methods found in the literature.

Introduction

The vehicle routing problem (VRP) was firstly addressed by Dantzig and Ramser (1959), proposing the most cost-effective way to distribute items between customers and depots by a fleet of vehicles. Taking into account of the attribute of the fleet, the traditional VRP has evolved to different variants. Amongst them include CVRP (homogenous VRP) that only considers a constraint of vehicles having the same limited capacity (Rochat and Taillard, 1995), HVRP (heterogeneous VRP) that serves customers with different types of vehicles (Golden et al., 1984, Gendreau et al., 1999, Lima et al., 2004, Prins, 2009, Brandao, 2011), VRPTW (VRP with time windows) that requires the service of each customer to start within the time window subject to time windows constraints (Kolen et al., 1987); and SDVRP (split deliver VRP) that allows more than one vehicle serving a customer (Chen et al., 2007). Readers are to refer to Crainic and Laporte, 1998, Toth and Vigo, 2002 for a detailed description of VRP and its variants. To solve the VPR variants above effectively, a number of metaheuristics have been applied, such as simulated annealing (Osman, 1993), Tabu search (Brandao, 2011, Gendreau et al., 1999), genetic algorithms (Lima et al., 2004), variable neighborhood search (Imran et al., 2009), and ant colony optimization (Rochat and Taillard, 1995, Li et al., 2009).

In the real world, logistics managers have to deal with routing and packing problems simultaneously. This results in another domain of VRP to be investigated. In the literature, there are a number of frameworks proposed to address these two problems simultaneously. Iori et al. (2007) addressed the VRP with two-dimensional packing constraints (2L-CVRP) with an algorithm based on branch-and-cut technique. Gendreau et al. (2008) proposed a Tabu search heuristic algorithm to solve large instances with up to 255 customers and more than 700 items in the 2L-CVRP. Zachariadis et al. (2009) developed a new meta-methodology guided Tabu search (GTS) which can obtain better results. In this work, a collection of packing heuristics was proposed to check the loading feasibility. Fuellerer et al. (2009) presented a new ant colony optimization algorithm deriving from saving-based ant colony optimization method and demonstrated its performance to successfully solve the 2L-CVRP. More recently, Leung et al. (2011) developed a new efficient method that consists of a series of algorithms for two-dimensional packing problems. The method has proven its capability to improve the results of most instances used by Zachariadis et al. (2009). Duhamel et al. (2011) proposed a GRASP × ELS algorithm for 2L-CVRP, whereby the loading constraints were transformed into resource constrained project scheduling problem (RCPSP) constraints before a packing problem can be solved. However, only basic CVRP and Unrestricted version of 2L-CVRP were solved with their algorithm. Some researchers have extended their heuristics to three-dimensional problems. Gendreau et al. (2006) proposed a multi-layer Tabu search algorithm that iteratively invokes an inner Tabu search procedure to search the optimal solutions of a three-dimensional loading sub-problem. Tarantilis et al. (2009) used a guided Tabu search (GTS) approach with a combination of six packing heuristics to solve 3L-CVRP. In their work, a manual unloading problem was also tested. Furthermore, Fuellerer et al. (2010) also proposed their methods to deal with three-dimensional loading constraints. In addition, Iori and Martello (2010) provided a review in regard to vehicle routing problems with two and three-dimensional loading constraints.

Since most enterprises own a heterogeneous fleet of vehicles or hire different types of vehicles to serve their customers, it is therefore crucial to study VRP with a fleet of heterogeneous vehicles. The heterogeneous fleet VRP (HFVRP) addresses the VRP with a heterogeneous fleet of vehicles which have various capacities, fixed costs and variable costs (Choi and Tcha, 2007, Imran et al., 2009). In the literature, three versions of HFVRP have been studied. Golden et al. (1984) considered the variable costs to be uniformly spread across all vehicle types and the availability of each type of vehicle to be unlimited. Gendreau et al. (1999) considered the different variable costs for different types of vehicle. The third HFVRP was introduced by Taillard, 1999, Tarantilis et al., 2004, in which the number of available vehicles of each type is limited. Recently, Penna et al. (2011) introduced an Iterated Local Search, combined with a Variable Neighborhood Decent procedure and a random neighborhood ordering (ILS-RVND), to solve all variants of HFVRP.

In this paper, we combined the HFVRP with two-dimensional loading constraints, called the heterogeneous fleet vehicle routing problems with two-dimensional loading constraints (2L-HFVRP). However, to the best of our knowledge, no work has been conducted to address such VRP although it is a practical problem in real-world transportation and logistics industries. In 2L-HFVRP, there are different types of vehicles with different capacity, fixed cost, variable cost, length and width in vehicle dimension, and two-dimensional loading constraints. The demand of a customer is defined by a set of rectangular items with given width, length and weight. All the items belonging to one customer must be assigned to the same route. The objective is to describe the minimum transportation costs with a function of the distance travelled, fixed and variable costs associated with the vehicles.

This paper presents a simulated annealing (SA) algorithm for 2L-HFVRP. In the literature SA has been proven to be an effective method to solve combinatorial optimization problems and it has been successfully applied to 2L-CVRP (Leung et al., 2010). In this paper, a heuristic local search is used to further improve the solution of SA. In addition, six promising packing algorithms, whereby five were developed by Zachariadis et al. (2009) and one by Leung et al. (2010), are also used to solve the loading constraints in 2L-HFVRP. These algorithms are extensively tested on benchmark instances derived from the 2L-CVRP test problems with vehicles of different capacity, fixed and variable costs, length, and width. The comparison with several effective methods of the 2L-CVRP and pure HFVRP is also given.