Metaheuristics for vehicle routing problems with three-dimensional loading constraints

Abstract

This paper addresses an important combination of three-dimensional loading and vehicle routing, known as the Three-Dimensional Loading Capacitated Vehicle Routing Problem. The problem calls for the combined optimization of the loading of freight into vehicles and the routing of vehicles along a road network, with the aim of serving customers with minimum traveling cost. Despite its clear practical relevance in freight distribution, the literature on this problem is very limited. This is because of its high combinatorial complexity.

We solve the problem by means of an Ant Colony Optimization algorithm, which makes use of fast packing heuristics for the loading. The algorithm combines two different heuristic information measures, one for routing and one for packing. In numerical tests all publicly available test instances are solved, and for almost all instances new best solutions are found.

Introduction

The Three-Dimensional Loading Capacitated Vehicle Routing Problem (3L-CVRP) is a highly complex problem combining three-dimensional loading and vehicle routing. The problem was introduced in Gendreau et al. [20] and calls for the determination of the routes travelled by a vehicle fleet for delivering items to customers, while minimizing the total travel cost. Items consist of rectangular boxes of given size and weight, and must be feasibly loaded within the vehicles before they are shipped.

The problem is of practical interest in freight distribution, because of its many real-world transportation applications. It is particularly relevant for those cases where shippers have to deal with large items and loading is not trivial. Examples are the distributions of household appliances, kitchen components, mechanical components and others. The first paper on the 3L-CVRP was indeed motivated by a furniture distribution problem [20].

The problem is also of theoretical interest because it generalizes two of the most well known problems in combinatorial optimization: the Capacitated Vehicle Routing Problem (CVRP), and the Three-dimensional Bin Packing Problem (3BPP).

The CVRP calls for the determination of the set of routes of minimal cost, to be travelled by a set of vehicles so as to deliver a given quantity of freight to each customer. The loading is not taken explicitly into account, except checking that, for each vehicle, the total weight of the loaded freight does not exceed the given vehicle weight capacity. The literature on the problem is very wide. For recent surveys we refer the reader to Toth and Vigo [31] and Cordeau et al. [10]. Other contributions especially focused on heuristics and metaheuristics are Cordeau and Laporte [9] and Cordeau et al. [7].

The 3BPP calls for packing a given set of three-dimensional rectangular items into the minimum number of three-dimensional rectangular boxes (bins), while ensuring that items do not overlap and are completely contained by the bins. The 3BPP is particularly difficult and, despite some decades of research, several instances with less than 50 items cannot be solved to optimality (see Martello et al. [25], [26]). For recent and very effective metaheuristics on the 3BPP we refer the reader to Faroe et al. [16] and Crainic et al. [11], [12]. All these approaches solve the most common version of the 3BPP, in which orthogonal packing is required (items must be packed with their edges parallel to the edges of the bin).

Concerning the practical relevance of the 3L-CVRP, the seminal paper [20] was motivated by a particularly difficult loading problem, with items of high cost, high risk of being damaged during transportation and very different shapes (e.g., chests of drawers, night tables, beds, wardrobes and accessories). Other loading and routing problems have been addressed very recently. Doerner et al. [14] studied the delivery of timber chipboards. The chipboards had to be placed on three different piles contained in particular vehicles, where the opening for the loading/unloading operations was placed on one side. The problem was solved by an Ant Colony Optimization (ACO) algorithm and by Tabu Search (TS), both using fast approximation algorithms for the loading. A work in progress related to the 3L-CVRP is presented by Pisinger (http://www.diku.dk/~pisinger/), who addresses the problem of loading and delivering sofas. In this problem the packing may result in complicated structures due to the sofas having non-convex shapes.

The 3L-CVRP generalizes another loading and routing problem known as the Two-Dimensional Loading Capacitated Vehicle Routing Problem (2L-CVRP). In the 2L-CVRP items have a two-dimensional rectangular shape, and vehicle have a two-dimensional rectangular space for loading items. The problem is of interest for optimizing the distribution of those items that may not be stacked one over the other (e.g., refrigerators, pallets as high as the vehicle, big and heavy boxes). The problem was introduced by Iori et al. [22], who solved it in an exact way by means of a branch and cut algorithm, making use of a nested branch and bound algorithm for the loading subproblem. It was then addressed with metaheuristics by Gendreau et al. [21] and Zachariadis et al. [32], through TS, and by Fuellerer et al. [18], through ACO. This paper generalizes the results obtained in [18] for the 2L-CVRP to the case of 3L-CVRP, where loading is much more complex and challenging, and real-world constraints have to be carefully handled.

Some first papers combining loading with routing or pickup and delivery have been presented very recently. In the Traveling Salesman Problem with Pickup and Delivery and LIFO Loading (TSPPDL) a single vehicle has to first pickup and deliver freight to customers, by ensuring that a Last-In-Fist-Out (LIFO) policy is respected in loading and unloading of cargo. This implies that the vehicle may be seen as a single stack, being rear-loaded and rear-unloaded. The TSPPDL was addressed by using variable neighborhood search by Carrabs et al. [4] and by means of a branch and cut algorithm by Cordeau et al. [8]. A more complex problem has been presented by Pettersen [27] and defined as the double TSP with multiple stacks. In this case the vehicle is formed by three stacks and again a LIFO policy must be fulfilled on each of the stacks. In [27] a mathematical model and two metaheuristics, based on TS and simulated annealing paradigms, are described.

The problem of loading a three-dimensional container is, from a practical point of view, more complex than the standard 3BPP. Additional constraints may arise from the nature of the items, from the cargo stability and from practical considerations in transportation (see, e.g., Bortfeldt and Gehring [2] and Pisinger [28] for a discussion on container loading problems). In the 3L-CVRP the total weight of the items must not exceed the vehicle weight capacity and all items required by a customer must be placed on the same vehicle (no split deliveries). In addition to the orthogonal loading, items have a fixed top, while 90° rotations are allowed on the horizontal plane. Some of the items may be fragile, and in this case it is requested that no non-fragile item is placed over a fragile one. When an item is placed on top of other items, its base area must be supported totally or partially by the other items. Finally, the loading of each vehicle should allow an easy unloading, i.e., it should be possible to unload the items of a customer without shifting in the cargo items requested by other customers.

A simple example of a 3L-CVRP instance is given in Fig. 1, in which eight customers demand for a total of 15 weighted items, and must be served through vehicles based at a central depot. In the example, fragile items are depicted in gray color. The sum of the weights of the items demanded by each customer (indicated by $d_i$ for a given customer i) should not exceed the maximum weight vehicle capacity $D=100$. A possible solution formed by three routes is also depicted. In Fig. 2 the feasible loadings associated to each route of Fig. 1 are shown. No non-fragile item is placed over a fragile item, and each item basis is supported, partially or totally, by other items or by the vehicle surface. It is also easy to check how unloading operations may be performed for each customer along the l axis.

In this paper we propose an ACO algorithm for the 3L-CVRP. This is motivated by the excellent results that this metaheuristic paradigm obtained on both classical routing problems (see, e.g., Reimann et al. [29], [30]) and loading and routing problems (see Doerner et al. [14] and Fuellerer et al. [18]). Our aim is to provide high quality solutions with reasonable computational effort, hence developing an algorithm capable of dealing with large-size instances, and being possibly useful for real world distribution. We do this by carefully merging and tailoring to the problem techniques from the literature. The contribution of this paper is twofold. First, we provide very good results on all publicly available test instances improving previous approaches on average by more than 6%, and in some cases even by more than 17%. Second, we show that these results can be obtained using very simple but fast packing heuristics. It seems to be better to consider some simple packing information in the construction of the solutions than using highly complicated packing heuristics. This is in contrast to our results in the two-dimensional case [18], where apart from the heuristics also a truncated branch and bound algorithm is used.

The paper is organized as follows. A more formal description of the 3L-CVRP and of its loading constraints is given in Section 2. The ACO algorithm is described in Section 3 and is computationally evaluated in Section 4. Some conclusions are finally drawn in Section 6.