1 Introduction

Vehicle routing problems (VRPs) describe the logistic issues of many industries in a wide variety of application fields (Toth and Vigo 2002; Golden et al. 2008). Multiple VRP variants have been studied both using exact and approximate methods (Laporte 1992; Cordeau et al. 2005; Baldacci et al. 2010). The main goal of these problems is to efficiently distribute goods from factories or stores to wholesalers or final clients. Thus, the most common costs associated with the goods delivery are those related to driving distances, including: fuel consumption, driving times, maintenance/amortization of vehicles, or drivers’ salaries. Other indirect costs or externalities—such as congestion, safety-costs, CO2 emissions, etc.—are frequently considered too (Golden et al. 2008; Sbihi and Eglese 2010). Likewise, it is frequent to find in the vehicle routing literature many different constraints which naturally appear in real-life distribution processes (Drexl 2012).

This paper analyzes the two-dimensional loading vehicle routing problem with heterogeneous fleet (2L-HFVRP), and proposes a hybrid algorithm to solve it. Our work was originally motivated by a real-world case at Opein (www.opein.com), a medium-size enterprise which provides industrial equipment to its customers, mostly in the building-construction field. Opein has to periodically deliver a large variety of industrial equipment, including: aerial-work platforms, energy-generation sets, compressors, dumpers, forklifts, professional cleaning equipment, and so on. Similar issues arise in other enterprises which also deliver large-size items to their clients, e.g.: kitchen appliances, furniture, etc. Notice that these items, which are assumed to have a rectangular shape, must be efficiently packed over the truck surface in order to attain high levels of vehicle utilization. Therefore, the distribution of these equipments has to be done considering not only their weight but also their specific dimensions in width and length. Usually, these equipments cannot be piled up, and they cannot be overlapped either, thus constituting a two-dimensional loading routing problem (2L-CVRP) (Iori 2005; Fuellerer et al. 2009; Iori and Martello 2010). A packing and routing solution for a simple instance of the 2L-CVRP is depicted in Fig. 1.

Fig. 1
figure 1

Packing and routing solution for a simple instance of the 2L-CVRP

Full size image

In this paper we have also considered the existence of a heterogeneous fleet (2L-HFVRP), as well as the possibility of rotating the rectangular items by 90° (non-oriented case) during the loading stage. To the best of our knowledge, the 2L-HFVRP has only been analyzed in Leung et al. (2013), although these authors limited their study to the oriented case—i.e., without allowing rotation of items, which reduces the number of feasible solutions. Heterogeneous fleets of vehicles constitute a quite common scenario in practical applications. On the one hand, ‘large-size’ vehicles might have high fixed and/or variable costs, and they might not be able to access clients located in narrow streets or city centers with parking restrictions. On the other hand, only using ‘small-size’ vehicles might be an inefficient—or even infeasible—strategy due to the size of some industrial equipment. Moreover, the assumption of considering heterogeneous fleets is becoming more and more popular in the routing literature (Gendreau et al. 1999; Baldacci et al. 2008). Related to this is the challenging problem of determining the optimal composition of a fleet (Hoff et al. 2010). Regarding the possibility of rotating the items during the loading stage, we also consider that this is a perfectly valid assumption in a number of real-life cases, if not in most of them. In fact, not considering items rotation might represent an artificial constraint that generates suboptimal solutions—as it will be shown in the experimental section of this paper. Accordingly, we propose a hybrid algorithm for solving the 2L-HFVRP, both for the non-oriented as well as the oriented cases. Our model deals with the unrestricted versions of the 2L-HFVRP, according to the classification established in Fuellerer et al. (2009). In other words, the order in which items are loaded into the vehicle will not necessarily depend on the order in which the customers will be visited. In these circumstances, the goal is to minimize total costs, which in our case include not only the costs due to driving distances, but also fixed and variable costs for each type of vehicle employed. To do so, our algorithm combines biased-randomized versions of routing and packing heuristics. Biased-randomization of heuristics refers to the use of skewed probability distributions to induce ‘biased’ (non-symmetric) random behavior in a heuristic procedure. As described in Juan et al. (2013), this technique allows transforming a deterministic heuristic into a multi-start probabilistic algorithm. On the one hand, for the routing part we use a biased-randomized version of the saving heuristic (Clarke and Wright 1964). This version is also enriched with memory-based and splitting local search strategies, as described in Juan et al. (2011). On the other hand, for the packing part we use biased-randomized versions of the Best-Fit packing heuristic (Burke et al. 2004) and the Touching Perimeter algorithm (Lodi et al. 1999). The packing process is then integrated inside the constructive routing process.

This paper is structured as follows: Section 2 reviews several related works in the existing literature. Section 3 provides more details on the specific problem we are considering, including the assumptions of our model. Section 4 explains the basic ideas behind the hybrid algorithm we propose. In Sect. 5, a series of computational experiments, based on recently published benchmarks, are carried out in order to test our algorithm. Section 6 analyzes the results obtained in the previous section, highlighting how they improve the current state-of-the art. Finally, a conclusion section summarizes the main contributions of this paper.

2 Literature review

To the best of our knowledge, only Leung et al. (2013) have recently analyzed the 2L-HFVRP problem. In their work, these authors motivate and discuss the importance of considering the heterogeneous variant of the 2L-CVRP. They also propose an algorithm for solving this problem, as well as a set of benchmarks and results. In the experimental section of our paper, we use their set of benchmarks and results to test the efficiency of our approach. Since no other work on the 2L-HFVRP has been published so far, this section will focus on previous contributions related to the two combinatorial optimization problems which integrate the 2L-HFVRP: the heterogeneous fleet VRP (HVRP/FSM), and the two-dimensional loading constrained VRP. A review of the bibliographic sources associated with these problems allows us to say that: (i) the heterogeneous VRP has been extensively studied for several decades now, while the 2L-CVRP is referenced only a few times; and (ii) the heterogeneous VRP is a generic routing problem where the concept of heterogeneity needs to be explained in detail to understand its precise meaning, while the 2L-CVRP is a much more restricted family of routing problems—which are mainly concerned with the distribution of heavy machinery.

One of the first papers analyzing the heterogeneous VRP was authored by Golden et al. (1984). During the subsequent years, the existence of heterogeneous fleets was frequently considered in different VRPs. Case studies and applications can be found, among others, in Semet and Taillard (1993), Ruiz et al. (2004), and Privé et al. (2006). Different features of heterogeneous VRPs have been studied. Baldacci et al. (2008) propose a classification of these problems according to the number of available vehicles—either limited (HVRP) or unlimited (FSM)—and the considered costs per type of vehicle—fixed (F), variable (D), or both (FD). Osman and Salhi (1996) and Ochi (1998a, b), propose a Tabu Search algorithm and a scatter search approach, respectively, to solve the FSM-F problem. Tabu Search is also applied in Lee et al. (2006) and Gendreau et al. (1999) to solve both the FSM-F and the FSM-D problems. Regarding the FSM-FD, Lima et al. (2004) describe a Memetic Algorithm for solving it, while Liu et al. (2009) propose a Genetic Algorithm. Regarding the version with a limited number of vehicles, Gendreau et al. (1999) propose a Tabu Search algorithm, and Taillard (1999) a Column Generation algorithm. Also, Tarantilis and Kiranoudis (2002) introduce the backtracking adaptive threshold accepting (BATA) to solve the HVRP-D. Finally, in Tarantilis and Kiranoudis (2007) a two-phase algorithm called Generalized Route Construction Algorithm (GEROCA), which includes a flexible adaptive memory, is applied to solve the HVRP-FD.

Other variants for the VRPs with heterogeneous fleet have been also addressed in the literature. For example, there are heterogeneous VRPs with time windows (Liu and Shen 1999), multiple depots (Salhi and Sari 1997), uncertainty in customers’ demands (Couillard and Martel 1990), external carriers (Bolduc et al. 2007), multi-trip vehicles (Prins 2002), etc. In some works dealing with the heterogeneous VRP as well as other constraints, variable and fixed costs are ignored (Oppen et al. 2010; Rieck and Zimmermann 2010; Vallejo et al. 2012). However, there are also other studies that include advanced costs models. Thus, for example, Tavakkoli-Moghaddam et al. (2007) assume that the costs depend on the number of used vehicles as well as on the total unused capacity. Finally, two excellent surveys on heterogeneous VRPs can be found in Baldacci et al. (2008) and Hoff et al. (2010). Similarly, some real-life applications of heterogeneous VRPs are illustrated in Golden et al. (2002).

Regarding the 2L-CVRP, several variants have been analyzed, mainly due to the use of different vehicle routing and packing assumptions. From the point of view of the loading problem there are different constraints that could be considered. Depending on these constraints it is possible to distinguish among the following loading settings: (a) oriented loading (OL), in which rotation of items is not allowed; (b) non-oriented loading (RL), in which rotating items by 90° is allowed during the packing process; (c) sequential loading (SL), where items are always loaded in the reverse order in which the customers are visited—moreover, re-arrangements of items inside the vehicle are not allowed once the route has started–, and (d) unrestricted loading (UL), where items are allowed to be re-arranged during the distribution process. As far as we know, Fuellerer et al. (2009) are the first and only authors so far in dealing with the 2L-CVRP with non-oriented loading, which is also addressed in this paper for the heterogeneous variant.

As a generalization of the VRP, it is clear that the 2L-CVRP is NP-complete and also difficult to solve in practice. In fact, even when exact approaches based on Integer Linear Programming or Branch-and-Bound techniques are able to solve instances with up to 35 customers and 114 items (Iori et al. 2007), there are smaller instances which remain unsolved. For example, Iori and Martello (2010) refer to an instance with just 29 customers and 43 items that has yet to be solved optimally. Since these limits are not reasonable for real-life practice, several heuristics and metaheuristics have also been proposed for the 2L-CVRP, among others: Tabu Search (Gendreau et al. 2008), Guided Tabu Search (GTS) (Zachariadis et al. 2009), extended guided tabu search (EGTS) (Leung et al. 2010a), ant colony optimization (Fuellerer et al. 2009), Simulated Annealing (Leung et al. 2010), and GRASP (Duhamel et al. 2009, 2011). Finally, a nice survey on VRP with Loading Constraints can be found in Wang et al. (2009), and a systematic review on the 2L-CVRP is provided in Iori and Martello (2010).

3 Model assumptions

The 2L-HFVRP can be seen as a variant of the heterogeneous VRP where two-dimensional loading constraints have been incorporated to deal with ‘large-size’ items—which are usually assumed to be rectangular shaped. Therefore, the 2L-HFVRP is defined by a depot, where different types of vehicles are located, and a set of customers whose demand is composed by a set of rectangular items. Accordingly, customers’ demands associated with a 2L-CVRP instance must include not only the number of items but also their weight-load capacity, length, and width. In a similar way, information about vehicle types must include not only the capacity—in terms of maximum loading weight—but also the vehicle dimensions, i.e., width and length of the vehicle platform. Particularly, we consider a heterogeneous fleet where the number of vehicles of each type is unlimited and each vehicle type has a different capacity, width, length, fixed costs, and variable costs. Therefore, when solving the 2L-HFVRP some packing assumptions must be taken into account. These assumptions will be related to the feasible packing of the items inside the corresponding vehicle surface. As in previous works, in this paper it is assumed that each item must be loaded with its edges parallel to the edges of the selected vehicle (orthogonal packing). Also, the items need to be loaded without overlapping over the vehicle surface. Additionally, we consider two different scenarios depending on whether the items being loaded into the vehicles can be rotated (2L-UR) or not (2L-OR). We also assume unrestricted loading order. Accordingly, the aim of the 2L-HVRP problem considered in this paper is to minimize total costs, including driving distances plus fixed and variable costs associated with the vehicles employed. This solution has to fulfill the following constraints: (a) each customer is supplied just once and by a single vehicle of the heterogeneous fleet; (b) all used vehicles begin and end their route at the depot; (c) for each vehicle, its capacity is larger or equal than the sum of weights that it carries; (d) items cannot overlap when loaded inside the vehicle; (e) the length and width of the vehicle cannot be exceeded; and (f) items are allowed to be re-arranged during the distribution process—unrestricted loading case (UL).

4 Main ideas behind the MS-BR algorithm

Our approach for solving the 2L-HFVRP, the multi-start biased randomized (MS-BR) algorithm, combines the biased-randomized algorithm introduced in Juan et al. (2011) with biased-randomized versions of the Best-Fit packing heuristic (Burke et al. 2004) and the Touching Perimeter algorithms (Lodi et al. 1999). As explained in detail in Juan et al. (2013), biased randomization (BR) of heuristics refers to the use of skewed probability distributions in order to transform a heuristic into a multi-start probabilistic algorithm. Figure 2 shows a flowchart diagram of the MS-BR algorithm. It starts by computing a dummy solution, i.e., it assigns one round-trip route from the depot to each customer using the smallest possible type of vehicle. At this stage, the algorithm also computes the savings associated with each edge, as proposed in Clarke and Wright (1964). These savings values are used to generate and sort the ‘default’ list of edges—in which edges are sorted from the highest to the lowest savings value. Then, a multi-start (MS) process is initiated. In each iteration of the MS process, the list of edges is randomly re-sorted using a skewed probability distribution. A skewed distribution is used here in order to assign higher probabilities of being selected to edges with higher saving values. In effect, the higher the savings of an edge the greater its probability of being selected—put in other words, the more likely it is that the edge occupies the position at the top of the list. In our case, a Geometric distribution was employed to induce this biased-randomization behavior. One of the advantages offered by the Geometric distribution is that it only uses a single parameter, α, which can be easily tuned since it ranges from 0 to 1. By varying this parameter, different shapes of the distribution can be obtained. Thus, as α tends to 1 the random behavior will be almost inexistent, since the element at the top of the list will have almost all probabilities of being selected. On the other extreme, as α tends to 0 the random behavior will be almost uniform and any element in the list will have roughly the same probability of being selected. Values between these both extremes define different shapes of the probability distribution, thus obtaining intermediate and non-uniform random effects—thus assigning more probabilities of being selected to elements at the top of the list. After experimenting with several values of this parameter, we finally set α = 0.25. Then, until the randomly re-sorted list becomes empty, an iterative process begins in which the edge at the top of this list is extracted. This edge connects two different routes. Prior to checking the loading constraints, we verify whether a given type of vehicle reduces the costs when merging these two routes. If there is no improvement, the proposed merger of these two routes is discarded. Otherwise, the route is merged if all loading constraints are fulfilled, including those related to vehicle weight-load capacity and vehicle loading dimensions. In order to check feasibility of items packing for the selected vehicle type, i.e. capacity must be greater than or equal to the total demand of the two routes, the algorithm employs biased-randomized versions of two classical packing heuristics: the Best-Fit packing heuristic (Burke et al. 2004) and the Touching Perimeter algorithm (Lodi et al. 1999). Biased-randomization is used in both algorithms to provide a randomized list of items that fit in a specific position of the loading surface. Again, the probability distribution used in these processes is also a Geometric one. After some initial tests, the parameter, β, of these distributions—one for each algorithm—was set to β = 0.15. A new parameter, maxPackIter, controls the maximum number of times that both randomized heuristics will be run before assuming that the items cannot be fitted into a single vehicle of the currently selected type—i.e. before assuming that the merge is not possible, since the loading constraint would be transgressed. At this point, a new feasible solution is ready. Finally, if the new solution improves the best solution found so far, then the latter one is updated.

Fig. 2
figure 2

Flowchart diagram of the MS-BR algorithm

Full size image

Notice that while other 2L-CVRP approaches use a two-stage schema—one for solving the vehicle packing problem and then another for solving the VRP—our approach integrates the packing issue as part of the routing-construction process. That is, the proposed algorithm will generate routing solutions implicitly taking into account the loading constraints as well. Notice also that this multi-start process is particularly useful for two reasons: (a) it helps the algorithm to escape from local minima—by performing a biased randomization of the savings list, edges are selected in a different order at each iteration of the multi-start process while, at the same time, the logic behind the savings-based heuristic is maintained; and (b) the randomized algorithm is easily parallelizable. In fact, the algorithm can be parallelized by just running multiple instances of it, each one using a different seed for the pseudo-random number generator. These multiple instances can be executed over several threads, cores, or computers. This might help to obtain high-quality solutions in just a few seconds or even less, depending on the size of the instance and its intrinsic difficulty.

5 Computational experiments

The MS-BR algorithm described in the previous section was implemented as a Java application. A notebook with an Intel® Core™ i7-2670QM at 2.2 GHz and 4 GB RAM was used to perform all tests, which were run directly on the Netbeans platform installed over a Windows 7 operating system. In order to test our algorithm, we used the benchmarks described in Leung et al. (2013), which are a generalization of the classical 2L-CVRP benchmarks used in Iori et al. (2007) and Gendreau et al. (2008). Thus, we have considered five classes of instances [see Leung et al. (2013) (Table 4)], each corresponding to a different way used to generate the items associated with each customer. The first class corresponds to the original CVRP instance (obtained by assigning to each customer a single item having both sizes equal to 1). For each customer i, a set of mi items with uniform distribution on a certain range is created. For each class 2–5, the number of items generated for each customer is a uniformly random integer value in the interval (1, class number). For each of these items, a possible shape, namely Vertical (the relative heights are greater than the relative widths), Homogeneous (the relative heights and widths are generated in the same intervals) or Horizontal (the relative heights are smaller than the relative widths), is selected with equal probability, and the corresponding item sizes are randomly generated in the intervals given in Leung et al. (2013) (Table 4).

The aforementioned generalization of the classical 2L-CVRP benchmarks was made by adding information about capacity, loading surface, fixed and variable costs for each of the four types of vehicles considered. In particular, we selected the benchmarks associated with the non-sequential loading, which are composed of 5 classes of instances—differing in the number and size of their items—each class including 36 instances. The instances were run under two different scenarios, depending on whether or not the rotation of items was allowed. For each scenario, and for each instance-class combination, five replications of the algorithm were executed, each of them using a different randomization seed. Each replication was run for a maximum time of 1 min, i.e., a maximum time of 5 min was allowed for each scenario-instance-class combination. For the two-dimensional unrestricted oriented (without items rotation) loading scenario, 2|UO|L, we compare our results against the Simulated Annealing with Heuristic Local Search (SA_HLS) proposed in Leung et al. (2013). The SA_HLS was coded in C++ and it was run on a computer with a Core 2 Duo at 2.2 GHz and 2 GB RAM under Windows 7. As far as we know, for the two-dimensional unrestricted non-oriented (with items rotation) loading scenario, 2|UR|L, there are no previous results published. For that reason, we decided to compare the results we obtained for both scenarios as a way of estimating the reduction in costs derived from allowing rotation of items—whenever this might be a valid assumption.

Tables 1 and 2 contain the results obtained for the three aforementioned approaches: SA_HLS (oriented), MS-BR oriented, and MS-BR non-oriented (with rotation). The values associated with the SA_HLS were directly obtained from Leung et al. (2013). The values associated with our MS-BR methodology correspond to the best solution found after five runs. The seconds required to obtain the best solution in each case have been also included whenever they were available. With regard to Class 1, since all its items are square-shaped, results for this class are the same regardless items rotation is or is not allowed. Complete information about the solutions obtained is available at http://dpcs.uoc.edu/joomla/index.php/software.

Table 1 Comparison of results among SA_HLS (oriented), MS-BR oriented, and MS-BR non-oriented (with items rotation)—Classes 1–3
Full size table
Table 2 Comparison of results among SA_HLS (oriented), MS-BR oriented, and MS-BR non-oriented (with items rotation)—Classes 4 and 5 and averages for Classes 2–5
Full size table

6 Analysis of the results

An initial look at Tables 1 and 2 allows us to conclude the following: (i) for the non-oriented scenario, our MS-BR algorithm is able to improve most of the individual results—as well as the average results—provided by the SA_HLS algorithm, with individual average gaps ranging from −2.98 % (Class 2) to −9.71 % (Class 1), and a total average gap for Classes 2–5 of −4.17 %; (ii) results can be further enhanced, with respect to the oriented version of our algorithm, by allowing rotation of items in Classes 2–5; and (iii) computational times employed by our approach are far inferior to those employed by the SA_HLS algorithm using a similar CPU.

Figure 3 allows comparing, for each class, the total costs (including driving distance, fixed, and variable costs) associated with the best-found solution provided by each algorithm: SA-HLS, MS-BR OR (oriented), and MS-BR NOR (non-oriented). Notice that: (i) Class 1 is the one showing the lowest costs; (ii) inside each class, average costs generated with our MS-BR algorithm are always lower than the ones generated with the SA_HLS.

Fig. 3
figure 3

Boxplots of total costs by algorithm and class

Full size image

Figure 4 allows comparing gaps between results generated for the 36 instances by pairs of algorithms and classes. According to that Fig. 4, most of the obtained gaps are negative; therefore solutions obtained in this paper improve SA_HLS results. In particular, notice the following: (i) when comparing the gaps in SA_HLS versus MS-BR OR, classes 2, 3 and 4 present a similar behavior with their 50 % of the central data are around 0 and −6 % having the same values for median and mean. Moreover, the greater gaps are associated with classes 1 and 5, in particular those gaps in instances 28, 32 and 33 for class 1; (ii) similarly, when comparing the SA_HLS with the MS-BR NOR, the greater average gaps are those associated with classes 1, 3, and 5—of course, this comparison has to take into account that the SA_HLS does not consider rotation of items, so the values provided by the SA_HLS are only used as references;—and (iii) comparing both the oriented and non-oriented scenarios of the MS-BR algorithm for classes 2–5, it follows that additional costs reductions can be attained by allowing the rotation of items during the loading stage. Thus, considering classes 2 and 3, the 75 % greatest gaps of the tested instances are improved between 0 and −6 % being the best improvement around −12 %. Likewise, gaps in classes 4 and 5 are concentrated around 0 and −4 %, although some outlier gaps around −10 % are also found in class 5.

Fig. 4
figure 4

Boxplots of gaps by class

Full size image

Finally, Fig. 5 shows how gaps between the oriented and non-oriented scenarios vary for different class-instance configurations. Since both scenarios have been solved using our MS-BR algorithm, these (negative) gaps can be interpreted as estimates of the percentage improvement (reduction in total costs) that could be reached by shifting from an oriented scenario to a non-oriented scenario—i.e., by allowing rotation of items. Notice that for some class-instance configurations the improvements are relatively low (e.g., first five instances in all classes). However, for other class-instance combinations the improvements can exceed a 10 % percentage.

Fig. 5
figure 5

Gaps between the oriented and non-oriented scenarios by class and instance

Full size image

7 Conclusions and future work

This paper focuses on the two-dimensional VRP with heterogeneous fleet (2L-HFVRP). This problem represents an important challenge since it combines a heterogeneous VRP with vehicle packing problems. The combination of these two classical problems is found in practical applications of some real-world transportation activities. As far as we know, there is only one recent work in the existing literature dealing with this challenging problem (Leung et al. 2013). The paper presents a hybrid algorithm for solving the 2L-HFVRP. Our approach relies on the biased randomization of routing and packing heuristics, which are integrated inside a multi-start framework. Thus, our approach considers both routing and packing costs simultaneously to better support the decision-making process. In this paper, the possibility of rotating the items while they are loaded into the truck is also considered. This is quite a realistic assumption which has been seldom considered in the existing 2L-CVRP literature. In fact, to the best of our knowledge this is the first paper in providing computational results for the non-oriented 2L-HFVRP.

According to the experimental section, the algorithm presented here is able to provide good solutions to a difficult and yet quite unexplored problem. All in all, this paper contributes to improve the current state of the art in the 2L-HFVRP by providing new best-known solutions. As to future work, we plan to adapt our algorithm so that it can include other aspects frequently found in real-life scenarios, e.g.: pick-up and delivery actions, time windows, or stochastic demands/delivery times.