1 Introduction

Transportation logistics activities make up for a significant part of the overall running costs of an organization. For this reason, great interest has been dedicated both to develop effective logistics models and to design powerful optimization frameworks for generating cost-effective transportation solutions. Undoubtedly, the most important optimization problem in the areas of transportation logistics and fleet management is the vehicle routing problem which has attracted great research interest for over five decades (Laporte 2009). Advances in computational resources and optimization methodologies allow researchers and practitioners to deal with complex vehicle routing extensions which in the past were considered too difficult to tackle. In this context, an emerging class of complex vehicle routing variants are the vehicle routing problems integrated with loading constraints. These problems are aimed at optimizing vehicle routes and at the same time they take into account the physical dimensions of transported items in pursuit of identifying feasible loading patterns.

In the present paper, we study logistics activities with the following key characteristics: vehicles based at a central depot must be dispatched to exhaustively serve a set of customer requests. These requests involve shipping products from the depot to the customer locations and at the same time collecting products from customers to be moved back to the depot. In other words, the examined operational setting corresponds to the vehicle routing problem with simultaneous pick-up and delivery service. The products to be transported consist of two-dimensional items which are considered non-stackable. Thus, feasible two-dimensional loading arrangements of the transported items into the vehicles must be identified. The examined operational setting arises in reverse logistics systems: Supermarket and grocery store chains use different types of non-stackable items such as pallets, roll cages and plastic baskets due to specific store limitations and requirements. Their activities require both shipping products from the warehouse to the various store locations, and at the same time moving product returns, outdated goods and empty bottles, as well as stacks of empty pallets, roll cages and baskets from the stores to the warehouse. In addition, the increasingly popular haul-away service offered by furniture and electric appliance stores is a direct application of the transportation scenario examined in the present article. Under this service, vehicles are dispatched to deliver purchased items to customers and at the same time, they are responsible for collecting items that customers want to dispose of. Another case where the studied operational setting is met involves the delivery and return of voluminous objects like furniture. Such transportation requirements emerge in store chains where product returns must be made, in order to redistribute stock among branches.

The purpose of the present paper is to optimize and compare the routing costs of three alternative strategies for satisfying the above-described transportation requests: the vehicle routing problem with two-dimensional loading constraints and simultaneous pick-up and deliveries (2L-SPD), the vehicle routing problem with backhauls and two-dimensional loading constraints (2L-VRPB) and the bi-directional vehicle routing problem with two-dimensional loading constraints (2L-BiVRP). Briefly, the 2L-SPD model considers that vehicles simultaneously serve both the delivery and pick-up requests of customers by performing one visit per customer location (Zachariadis et al. 2015). The 2L-VRPB model assumes that each vehicle route consists of two legs: the first one is responsible for delivering customer orders, followed by the pick-up leg where the pick-up requirements of customers are satisfied. The 2L-BiVRP operational setting decomposes the overall problem in two distinct levels: the first one is responsible for serving customer delivery orders, whereas the second one is aimed at generating the collection vehicle routes. To draw comparative conclusions on the relative cost effectiveness of the aforementioned operational alternatives, we employ a powerful solution framework which consists of two main algorithmic components: one for optimizing the routing characteristics and the other for identifying feasible two-dimensional loading patterns for the items onboard. Obviously, the structure of the overall solution approach depends on the examined model. However, the individual routing and packing components employed are the same for all examined alternatives. Thus, a fair evaluation of the three compared strategies is performed. From a different perspective, the paper gives insight on the value of integrating given routing and packing methodologies into appropriate solution frameworks for dealing with different operational settings. To perform a complete comparison of the examined routing-loading models, we have constructed and solved a large collection of benchmark instances with diverse characteristics regarding the geographic distribution of customers, the shape of transported items, the number of items per vehicle and the ratio between the volume of the delivery and pick-up product quantities.

Regarding a brief outline of the literature on routing problems integrated with multi-dimensional loading constraints, Iori et al. (2007) have introduced the vehicle routing problem with two-dimensional loading constraints (2L-CVRP). The 2L-CVRP model is aimed at optimizing route plans, while feasible two-dimensional packing arrangements must be identified for the transported item sets. Methodologically, the authors propose a branch-and-cut algorithm for solving small-scale problem instances. For tackling large-scale 2L-CVRP instances, several metaheuristic algorithms have been proposed (Gendreau et al. 2008; Fuellerer et al. 2009; Leung et al. 2011; Zachariadis et al. 2013). A recent article dealing with the two-dimensional loading problem of 2L-CVRP is due to Côté et al. (2014). Their work presents an exact two-dimensional packing methodology for identifying feasible loading patterns when the LIFO requirement is imposed to facilitate easy unloading operations. Zachariadis et al. (2015) have introduced the 2L-CVRP extension which assumes that customers simultaneously require both delivery and pick-up service. The vehicle routing problem integrated with three-dimensional loading constraints is introduced in the work of Gendreau et al. (2006) where a tabu search method is proposed for solving the examined model. Other 3L-CVRP methodological developments are due to Tarantilis et al. (2009), Fuellerer et al. (2010), Zhu et al. (2012), Bortfeldt (2012) and Tao and Wang (2015). An additional problem on routing optimization subject to three-dimensional palletization constraints is introduced by Zachariadis et al. (2012). More details on vehicle routing problems integrated with loading constraints may be found in the review papers of Iori and Martello (2010, 2013) and Perboli et al. (2014).

The remainder of the present article is organized as follows: Sect. 2 describes in detail the compared transportation strategies. Then, Sect. 3 presents the employed solution approach. A brief description of the routing and packing components is provided, whereas emphasis is given on the methodological particularities for tackling the special requirements of each routing model. Section 4 summarizes the results of extensive computational experiments. In addition, several comparative remarks are drawn and discussed. Finally, Sect. 5 concludes the paper.

2 Problem definition

In the following, we describe the three compared routing-loading problem models studied in the present paper. We start from the vehicle routing problem with simultaneous pick-ups and deliveries and two-dimensional loading constraints (2L-SPD), then we define the vehicle routing problem with backhauls and two-dimensional loading constraints (2L-VRPB) and finally the bi-directional vehicle routing problem with two-dimensional loading constraints (2L-BiVRP) is presented. Note that the basic notation is introduced for 2L-SPD and it is used both for the 2L-VRPB and 2L-BiVRP.

2.1 The vehicle routing problem with simultaneous pick-ups and deliveries and two-dimensional loading constraints

The problem is defined on a complete graph G = (V, A), where V is the vertex set and A is the arc set. Vertex set V is made up by the depot (vertex 0) and a set of customers N (V = {0} ∪ {1, …, n}). With each arc (i, j) ∈ A is associated a known travel cost c ij. Each customer i ∈ N is associated with two transportation requirements: the first one corresponds to a set of rectangular items D i which must be shipped from the depot to the location of i. The second requirement corresponds to a set of rectangular items P i which must be picked-up from customer i and moved to the depot. The length and width of an item j ∈ D i  ∪ P i is denoted by l j and w j , respectively. The transportation requests are to be served by a set of homogeneous vehicles K based at the depot. Each vehicle i ∈ K has a rectangular loading space of length and width dimensions equal to L and W, respectively.

The goal of the 2L-SPD model is to design the set of routes that minimize the total travel cost. This route set is subject to the following constraints:

2L-SPD.1 :

The total number of routes does not exceed |K| (at most one route per vehicle).

2L-SPD.2 :

Each route starts from the depot and terminates at the depot.

2L-SPD.3 :

The transportation requests of customers are exhaustively satisfied.

2L-SPD.4 :

Each customer is visited once by exactly one vehicle route.

2L-SPD.5 :

For every arc travelled by the generated routes, there exists a feasible loading pattern of the associated items (i.e. the pick-up items of the customers already visited and the delivery items of the customers to be visited later on the route).

Requirement 2L-SPD.5 corresponds to the loading constraints of the 2L-SPD model. They can be expanded as follows:

2L-SPD.5.a :

All items are orthogonally placed in the loading space of the vehicle.

2L-SPD.5.b :

No item exceeds the boundaries of the vehicle loading space.

2L-SPD.5.c :

No item overlaps with any other item.

Here, we distinguish two model configurations as per Fuellerer et al. (2009): the first configuration (oriented) requires items to be loaded into the vehicle with fixed orientation, i.e. the length and width dimensions of items are parallel to the length and width dimensions of the loading space, respectively. The second configuration (rotations) assumes that items can be rotated by 90° before being loaded onto the vehicle space. The oriented and rotations configurations of 2L-SPD are denoted as 2|O|SPD and 2|R|SPD, respectively. Note that in the present paper, we consider only the basic version of the 2L-SPD model which allows items to be repositioned through the vehicle trips. This is because we aim to explore the routing cost savings achieved by the pure 2L-SPD model which promotes high loading area utilization throughout the routes by permitting item reshuffling at the various service locations.

2.2 The vehicle routing problem with backhauls and two-dimensional loading constraints

The basic assumption of the 2L-VRPB model is that a customer may require either delivery or pick-up service. Thus, the customer set N is composed by two customer types: the linehaul customers N D which require only delivery service (∀i ∈ N D , D i  ≠ Ø, P i  = Ø) and the backhaul customers N P which require only pick-up service (∀i ∈ N P , P i  ≠ Ø, D i  = Ø). All other problem characteristics are exactly as presented in Sect. 2.1 for the 2L-SPD model.

The 2L-VRPB is aimed at identifying the minimum cost set of routes such that:

2L-VRPB.1 :

The total number of routes does not exceed |K| (at most one route per vehicle).

2L-VRPB.2 :

Each route starts from the depot and terminates at the depot.

2L-VRPB.3 :

The transportation requests of customers are exhaustively satisfied.

2L-VRPB.4 :

Each customer is visited once by exactly one vehicle route.

2L-VRPB.5 :

Within any route, linehaul customers are visited before backhaul ones (precedence constraint).

2L-VRPB.6 :

There exists a feasible loading pattern for both the delivery and pick-up items assigned to a route.

Rule 2L-VRPB.6 corresponds to the loading constraints of the 2L-VRPB model. These are identical to constraints 2L-SPD.5.a–2L-SPD.5.c described for the 2L-SPD model.

In the following, we comment on the loading requirements of the 2L-VRPB model: each route consists of two legs. Along the first leg, linehaul orders are served. This implies that the vehicle leaves the depot fully loaded and delivers items to the customer locations. When the last linehaul of the route has been served, the vehicle space is empty and the vehicle proceeds to the second route leg along which backhaul customers are visited. This means that the loading constraints must be checked for the two depot-adjacent arcs: for the depot leaving arc, a feasible loading pattern must be identified for all delivery items assigned to the vehicle, while for the depot returning arc, a feasible loading pattern must be identified for all pick-up items shipped to the depot. In other words, independently of the number of customers assigned to a route, two loading sub-problems must be solved. This is contrary to the loading requirement of 2L-SPD, where a packing sub-problem must be solved for every route arc (for a 2L-SPD route of ρ customers, ρ + 1 packing sub-problems are defined).

Two 2L-VRPB configurations are examined according to whether item rotations are allowed. Under the oriented configuration, items must be loaded with fixed orientation, whereas under the rotations configuration, items may be rotated by 90°. Except for the orientation aspect, two additional problem configurations are examined depending on whether LIFO constraints are taken into consideration. These constraints make sure that loading and unloading operations are performed via direct moves without being necessary to rearrange other items on board: for the linehaul leg of a 2L-VRPB route, LIFO constraints make sure that items are loaded in such a way that no item j to be delivered later than i lies between item i and the door of the vehicle. Similarly, to ensure direct loading operations along the backhaul leg of a route, the LIFO policy guarantees that no item j picked up earlier than i may be positioned between item i and the door of the vehicle. The LIFO constraint for the 2L-VRPB is depicted in Fig. 1.

Fig. 1
figure 1

The LIFO constraints for the linehaul and backhaul route legs

Full size image

In total, four 2L-VRPB model versions are examined:

  • 2|OU|VRPB: Fixed orientation—no LIFO constraint.

  • 2|RU|VRPB: Rotations—no LIFO constraint.

  • 2|OS|VRPB: Fixed orientation—LIFO constraint.

  • 2|RS|VRPB: Rotations—LIFO constraint.

2.3 The bi-directional vehicle routing problem with two-dimensional loading constraints

The Bi-Directional Vehicle Routing Problem with Two-Dimensional Loading Constraints considers that a customer either requires delivery or pick-up service (just as in the case of 2L-VRPB). Thus, the customer set N is formed by the union of the linehaul customers N D and backhaul customers N P . The basic assumption of the model is that delivery and pick-up customers are served by different routes, namely linehaul and backhaul routes, respectively.

The 2L-BiVRP is aimed at identifying the minimum cost set of routes such that:

2L-BiVRP.1 :

The total number of linehaul routes does not exceed |K| (at most one linehaul route per vehicle).

2L-BiVRP.2 :

The total number of backhaul routes does not exceed |K| (at most one backhaul route per vehicle).

2L-BiVRP.3 :

The transportation requests of customers are exhaustively satisfied.

2L-BiVRP.4 :

Each linehaul customer is visited once by exactly one linehaul route.

2L-BiVRP.5 :

Each backhaul customer is visited once by exactly one backhaul route.

2L-BiVRP.6 :

There exists a feasible two-dimensional loading pattern for the transported items of each route (linehaul or backhaul).

Rule 2L-BiVRP.6 corresponds to the loading constraints of the 2L-BiVRP model which match constraints 2L-SPD.5.a–2L-SPD.5.c introduced for the 2L-SPD model. Note that 2L-BiVRP directly reduces to the standard 2L-CVRP model, if either the delivery or the pick-up customer set is empty.

As discussed for the 2L-VRPB model, we define two problem configurations depending on whether items can be rotated by 90°. In addition, two model configurations are examined according to the consideration of LIFO constraints. The LIFO constraints for the 2L-BiVRP model ensure that unloading (loading) operations are directly performed for the linehaul (backhaul) routes. Thus, the LIFO constraints for the linehaul routes match those described for the linehaul route legs of 2L-VRPB. Analogously, the LIFO constraints for the backhaul routes match those presented for the backhaul route legs of 2L-VRPB. In total, four 2L-VRPB model versions are examined:

  • 2|OU|BiVRP: Fixed orientation—no LIFO constraint.

  • 2|RU|BiVRP: Rotations—no LIFO constraint.

  • 2|OS|BiVRP: Fixed orientation—LIFO constraint.

  • 2|RS|BiVRP: Rotations—LIFO constraint.

2.4 Discussion on the three compared transportation models

The three vehicle routing models described in the previous paragraphs are very closely related. In fact, all three problem models consider exactly identical product flows. However, they are differentiated according to the employed operational scenario. More specifically, a 2L-SPD instance can be directly translated to a 2L-VRPB or a 2L-BiVRP instance by generating two co-located nodes for every original 2L-SPD customer node: the first such node is responsible for the delivery order, whereas the second node corresponds to the pick-up order of the original customer. This is depicted in Fig. 2, where a 2L-SPD instance of three customers is given. Regarding the delivery item sets, customer 1 requires two items (1-1 and 1-2), customer 3 requires one item (3-1) and customer 2 requires two items (2-1 and 2-2). As far as the pick-up products are concerned, customer 1 sends one item to the depot (1-3), while customer 3 requests the shipment of two items to the depot (3-2 and 3-3). This instance is translated to a 2L-VRPB and a 2L-BiVRP one by simply generating a pair of collocated nodes for the delivery and pick-up requests of each 2L-SPD customer node. This is shown in Fig. 2: customer 1 requests the delivery items 1-1 and 1-2, while the pick-up item 1′-1 (denoted as 1-3 for the 2L-SPD instance) is assigned to the co-located customer 1′. In addition, the 2L-SPD node 3 is replaced by node 3 requesting the delivery item 3-1 and node 3′ associated with the pick-up items 3′-1 and 3′-2. Note that for customer 2 requiring only delivery items, no extra node is created.

Fig. 2
figure 2

Translating a 2L-SPD instance to a 2L-VRPB and 2L-BiVRP instance

Full size image

Figure 3 provides example solutions under each of the three examined transportation models for the case depicted in Fig. 2. Note that the solutions provided assume that only one vehicle is available. More specifically, the 2L-SPD solution consists of a route with the following node sequence [0, 1, 3, 2, 0]. As previously explained, the simultaneous pick-up and delivery service drastically modifies the item set carried along the route, so that one packing pattern must be identified for each arc traversed. This is seen in Fig. 3a, where four feasible item loadings are depicted. The routing plan provided for 2L-VRPB is different: the node sequence is [0, 1, 3, 2, 3′, 1′, 0], where [0, 1, 3, 2] is the linehaul leg and [3′, 1′, 0] is the backhaul leg. As shown in Fig. 3b, only two feasible loading patterns must be determined for the route: The first one is associated with the first travelled arc and involves all items to be delivered along the route (1-1, 1-2, 2-1, 2-2, and 3-1). The second loading is associated with the items picked-up along the backhaul leg of the route (1′-1, 3′-1, 3′-2). Since items carried in intermediate route positions are subsets of the aforementioned item sets, it follows that they can be feasibly loaded into the vehicle. Finally, Fig. 3c depicts an example solution for the 2L-BiVRP model. Two routes are assigned to the single vehicle available. The delivery route (solid line) visits the [0, 1, 3, 2, 0] node sequence, while the pick-up route [0, 1′, 3′, 0] is responsible for collecting the pick-up requests (dashed line). Exactly as in the case of the 2L-VRPB, two feasible loadings must be identified (one loading per route in this case). The first one is associated with the delivery route and involves the delivery items of customers 1, 2, and 3. The second loading involves the items collected from customers 1′ and 3′.

Fig. 3
figure 3

Example solutions for the three compared models. a 2L-SPD solution, b 2L-VRPB solution, c 2L-BiVRP solution

Full size image

One important aspect regarding the three examined transportation strategies is the consideration of LIFO constraints. As stated in the model description, LIFO constraints are not imposed under the basic 2L-SPD version. This is because along a 2L-SPD route, items are delivered and other items are collected, so that the item set on board is drastically modified. As a result, repositioning of items in the vehicle space is required for taking full advantage of the vehicle loading area throughout the vehicle trips. This limitation makes the 2L-SPD applicable for light and medium-duty transportation systems, because it would be impractical to reposition the 20 or 30 pallets carried by heavy-duty trucks, every time a service stop is visited. On the contrary, the LIFO constraints are more compatible with the operational setting of 2L-VRPB and 2L-BiVRP and thus they are integrated into these models.

3 Solution methodology

Each of the three examined problems can be regarded as a bundle of two NP-hard combinatorial optimization problems: the first one consists of determining the minimum cost set of routes, generalizing the classical VRP model (Laporte 2009) which is known to be NP-hard. The second problem is related to the loading constraints and calls for the determination of feasible two-dimensional orthogonal patterns. This problem is known as the two-dimensional orthogonal packing problem (Fekete et al. 2007) which is also NP-hard. To solve instances of practical importance within reasonable computational time, we employ the solution methodology originally presented for the 2L-SPD (Zachariadis et al. 2015). The proposed algorithm uses two components: one for the routing and one for the packing aspects. Extensive experiments that have been applied to the well examined 2L-CVRP instances generated solutions of fine quality, proving the effectiveness of both methodological components (Zachariadis et al. 2015).

In the following, a description of the employed solution approach is provided. Firstly, the routing component is presented. It consists of two phases: a constructive procedure for generating an initial solution and a local-search framework which is the core of the optimization method and produces the final solution. This master routing algorithm invokes a loading feasibility method, which is responsible for generating feasible loading patterns. The general structure of the employed methodology is common for all three examined models. Obviously, some algorithmic differences are necessary for dealing with the different constraints of the examined models. We provide a brief description of the employed algorithm emphasizing on the necessary modifications for solving each of the examined models. An analytic presentation of the employed optimization methodology is given in the work of Zachariadis et al. (2015).

3.1 The master routing component

The routing algorithm is employed in two steps. In the first step, an initial solution is generated. This solution may be partial or complete. The routes involved in this solution respect all constraints imposed by the examined problem model. In the second phase, the initial solution is improved by a local-search method.

3.1.1 Generating an initial solution

The procedure is initiated by opening |K| empty routes. Then, a randomly chosen radius starting from the depot is defined. Customers are sequentially inserted in increasing order of the angle formed by the random radius and their locations. The service position of each customer is the one minimizing the additional routing cost and at the same time respects all of the constraints imposed by the examined problem. Note that the loading constraints of every trial insertion are examined with the use of the procedure presented in Sect. 3.2.

3.1.2 The employed local-search framework

The initial solution is improved by a local-search framework which employs three operators, namely the 1-0 and 1-1 exchange, and the 2-opt move type. To move between candidate solutions, the best acceptable move criterion is employed. In other words, the search transits to the candidate solution neighbor which minimizes the cost objective and respects the examined model constraints. To avoid being trapped around locally optimal solutions, the algorithm employs a diversification strategy based on the regional aspiration criteria of tabu-search and the attribute based hill climber (Whittley and Smith 2004). To drastically accelerate the search, we use the static move descriptors (SMD) entities which can statically store obtained objective and feasibility information for the candidate local search moves. In this way, the SMD strategy is capable of drastically accelerating the search process, because it manages to eliminate duplicate tentative move cost and feasibility evaluations (Zachariadis and Kiranoudis 2010).

For the sake of self-completeness, we provide a pseudocode of the employed method (Algorithm 1), supported by a brief verbal description. The interested reader is referred to (Zachariadis et al. 2015) for additional implementation details. The provided pseudocode makes use of the following notation:

z(S):

The objective of solution S.

m(S):

The solution obtained by applying local-search move m to solution S.

z(m):

The objective change incurred by applying local-search move m to solution S (=z(m(S)) − z(S)).

R(m):

The route set to be created by the application of local search move m.

C m :

The set of arcs to be created by the application of local search move m.

E m :

The set of arcs to be eliminated by the application of local search move m.

The method is fed with the initial solution S 0 constructed by the method of Sect. 3.1.1 and the set of non-served customers U. A series of initialization steps are performed in lines 1–5 of Algorithm 1. Then, the iterative core of our algorithm is performed. Every iteration firstly identifies the local search move m to be applied to the candidate solution S. To do so, the best moves for each of the three employed local search operators m j (j = 1, 2, 3) are found. Each of these moves must jointly satisfy the following requirements: (a) the objective change incurred is minimized, (b) the routes to be created by the move satisfy the examined model constraints, (c) the cost of the modified solution is lower than the objective threshold associated with each of the created arcs. If any of these moves improves the current solution, the best of them (incurring the best objective improvement) is selected to be applied. On the contrary, if none of these moves improves the current solution objective, one of them is randomly selected to be applied. The objective threshold of the arcs to be eliminated is appropriately set. Then, move m is performed and the cost of the affected tentative moves is re-evaluated. This is achieved by identifying the affected SMD instances and updating their objective labels according to the modified solution state (Zachariadis and Kiranoudis 2010). Afterwards, the procedure tries to feasibly insert any yet unserved customer in the modified solution. Any insertion point is examined. The overall procedure is terminated after μ main iterations have been executed by returning the lowest objective complete solution encountered.

figure a

3.2 Evaluating the loading feasibility

The master optimization framework of Sect. 3.1 repeatedly needs to evaluate the loading feasibility of tentative local-search moves. More specifically, each time the feasibility status of a move m is examined, the loading feasibility of the set of routes R(m) must be determined. Note that |R(m)| = 1 for intra-route moves, whereas |R(m)| = 2 for inter-route moves. To do so, the master algorithm invokes a loading feasibility procedure which is described in the following.

The proposed loading feasibility procedure makes use of hashtable structures for recording and retrieving obtained loading feasibility information. More specifically, the following two hashtables are employed for storing the loading feasibility of routes:

\(H_{r}^{s}\) :

Hashtable which stores route loading feasibility information obtained by the strong mode of the employed packing heuristic (strong packing heuristic mode is defined in Sect. 3.3).

\(H_{r}^{w}\) :

Hashtable which stores route loading feasibility information obtained by the weak mode of the employed packing heuristic (weak packing heuristic mode is defined in Sect. 3.3).

The key of each H s r and H w r entry contains the string representation of the route involved. The value of each hashtable entry is a binary flag indicating if this route has been found feasible or not. A straightforward mapping of routes to strings is employed, using the customer IDs separated with a standard character (*). For the 2L-SPD route presented in Fig. 3a, the hashtable entry is (“1*3*2”, true). Analogously for the 2L-VRPB route of Fig. 3b, this entry is (“1*3*2*3′*1′”, true), while for the two 2L-BiVRP routes of Fig. 3c, the hashtable entries are (“1*3*2”, true) and (“1′*3′”, true). Note that for the 2L-SPD and the LIFO versions of 2L-VRPB and 2L-BiVRP, the string representations are prepared exactly as described, taking into account the positioning of the customers within the routes. On the contrary, if no LIFO constraints are imposed, there is no need to keep track of the visit order of customers. Thus, to reduce the total number of hashtable entries, customers are sorted in a standard way (e.g. increasing order of their IDs) before preparing the route string representation. For example, the route representation for the linehaul route of Fig. 3c is (“1*2*3”).

In addition, the following two hashtables are used for storing obtained feasibility information for specific item sets associated with the arcs travelled by the examined routes:

\(H_{p}^{w}\) :

Hashtable which stores the loading feasibility of item sets obtained by the weak mode of the employed packing heuristic.

\(H_{p}^{s}\) :

Hashtable which stores the loading feasibility of item sets obtained by the strong mode of the employed packing heuristic.

The key of each H s p and H w p entry contains the string representation of a given item set, whereas the value of each entry is a binary flag indicating the corresponding loading feasibility status. The item sets are implicitly defined via the corresponding customer subsets. To prepare the string representation for the item set associated with each arc, we use a straightforward scheme: the corresponding customer IDs are separated by a standard character (*). The string consists of two parts. The first one corresponds to the customer delivery items, while the second one is associated with the pick-up items. These two parts are divided by another separator character (‘#’). If no LIFO constraints are imposed, the customer IDs are sorted within the two substrings. For the 2L-SPD route (no LIFO constraints) of Fig. 3a, four hashtable entries exist, equal in number with the travelled arcs: (“1*2*3#”, true), (“2*3#1”, true), (“2#1*3”, true), and (“#1*3”, true). Accordingly, the 2L-VRPB route of Fig. 3b is associated with two entries (one for the linehaul and one for the backhaul route leg). If LIFO constraints are imposed, these entries are (“1*3*2#”, true) and (“#3′*1′”, true). For the non-LIFO case, these entries are (“1*2*3#”, true) and (“#1′*3′”, true). Regarding the 2L-BiVRP model, there is only one item set associated with each route. This implies that the relevant loading feasibility information is already contained in the route hashtables, so that the item set hashtables are not employed (see Sect. 3.2.3).

Note that the terms strong and weak packing heuristic modes describe the behavior of the two-dimensional, packing heuristic. This will be clarified when the packing heuristic is presented (Sect. 3.3).

As earlier stated, the method uses three memory levels for storing and retrieving loading feasibility information obtained along the search process: the first level is responsible for storing obtained information in the SMD instances which encode the local-search moves. The second memory level stores the loading feasibility of complete routes, while the third level is associated with the loading feasibility of travelled arcs, or in other words specific item sets.

In terms of the first memorization level, each SMD instance contains a binary flag corresponding to the loading feasibility status of the encoded local search move. In addition, it contains the master iteration when this feasibility status was last obtained. When move m needs to be examined, the method applies the following steps: if routes R(m) have remained unaffected since the move feasibility was last examined, the feasibility status is directly retrieved by the feasibility flag of the corresponding SMD instance. Otherwise, the method moves on to the second feasibility examination level.

In the second level, the method checks if the loading constraints for the R(m) routes have been previously examined. This is done by generating the route string representations and accessing the appropriate route hashtables. If move m is objective-improving (z(m) < 0), H s r is accessed. On the contrary, if z(m) ≥ 0, the H w r hashtable is accessed. If any route is found to be infeasible, move m is declared infeasible and the corresponding SMD instance feasibility flag is set to false. On the other hand, if a route is found to be feasible, it is excluded from set R(m). When the R(m) routes have been checked, two cases may hold: if R(m) set is empty (all routes have been found to be feasible by accessing the route hashtables), move m is declared feasible and the flag of the corresponding SMD instance is appropriately set. Otherwise, the method moves on to the third feasibility examination level which depends on the model under examination. In the next three paragraphs, we present the third feasibility level separately for the 2L-SPD, 2L-VRPB and 2L-BiVRP models.

3.2.1 The third level of loading feasibility examination for the 2L-SPD model

For each route r ∊ R(m), the set of the arcs traversed by this route and denoted by A r is generated. The method examines whether the item sets associated with each arc have been already tested. This is done by preparing the string representation of each arc and accessing the H s p hashtable, if z(m) < 0, or the H w p , otherwise. If any arc is found to be infeasible, route r and move m are directly declared infeasible. The negative feasibility status is recorded in the appropriate route hashtable and SMD instance. On the other hand, if any arc is found to be feasible, this arc is excluded from A r . Afterwards, the A r arcs are sorted in decreasing order of the associated item set area. They are selected sequentially and the method examines if the associated items sets can be feasibly inserted into the vehicle loading space. This is done by applying the two-dimensional packing heuristic method of Sect. 3.3. If any arc is found to be infeasible, route r and move m are declared infeasible. The corresponding information is stored in the appropriate arc and route hashtables, as well as in the SMD instance encoding move m. On the other hand, if all arcs are found to be feasible, route r is declared feasible. Obviously, if all R(m) routes are declared feasible, then move m is declared feasible. The obtained feasibility information is recorded in the corresponding SMD instance, as well as in the appropriate route and item set hashtables.

3.2.2 The third level of loading feasibility examination for the 2L-VRPB model

For each route r ∊ R(m), a set of two arcs A r is created. These arcs correspond to the depot-adjacent arcs, or in other words, the first and the last arc travelled by route r. This is because under 2L-VRPB, the loading feasibility must be checked when: (a) the vehicle departs the depot loaded with the delivery items and (b) the vehicle returns to the depot loaded with the pick-up items. The procedure checks if the item sets associated with the A r arcs have been already investigated. To do so, the string representation of each arc is prepared and the H s p or H w p hashtable is accessed, according to whether z(m) < 0, or z(m) ≥ 0. If any arc is found to be infeasible, route r and move m are declared infeasible. This information is stored in the appropriate route hashtable and the SMD instance encoding m. On the other hand, if any arc is found to be feasible, this arc is removed from A r. Then, the A r arcs are sorted in decreasing order of the associated item set total area. They are selected sequentially and the method examines if the corresponding items can be feasibly loaded onto the loading surface via the packing heuristic method of Sect. 3.3. If any arc is found to be infeasible, route r and move m are declared infeasible. The obtained loading information is stored in the appropriate arc and route hashtables, as well as in the corresponding SMD instance. On the other hand, if the A r arcs are found to be feasible, route r is declared feasible. Obviously, if all R(m) routes are declared feasible, then move m is also declared feasible and the corresponding SMD flag, route and item set hashtable entries are appropriately set.

3.2.3 The third level of loading feasibility examination for the 2L-BiVRP model

Under the 2L-BiVRP model, the feasibility of just one arc has to be examined: the first arc for the linehaul routes, or the last arc for the backhaul ones. Thus, the method directly employs the packing heuristic for the item sets associated with the routes of R(m). If any R(m) route is found to be infeasible, move m is deemed infeasible. On the contrary, if all R(m) routes are found to be feasible, move m is also declared feasible. In both cases, the corresponding information is stored in the appropriate route hashtable and SMD instance.

3.3 The employed procedure for obtaining feasible packing structures

To determine whether an item set can be feasibly loaded within the loading area of a vehicle, a two-dimensional packing heuristic is employed. This heuristic is described in detail in (Zachariadis et al. 2015). In the following, we provide a brief description of the basic methodological features.

The loading heuristic performs a series of packing attempts for feasibly packing the examined items in the loading area. Each packing attempt starts from an empty loading space and sequentially inserts items onto the vehicle. When an item placement is performed, new loading positions become available for subsequent items. The rationale for managing the available loading positions is based on the extreme-point method of Crainic et al. (2008) and the envelope procedure of Martello et al. (2000). Regarding item-to-position assignments, we employ the maximum touching perimeter criterion (Lodi et al. 1999). To promote the development of diverse packing structures and subsequently increase the probability to obtain a feasible packing arrangement, the employed packing attempts are inter-connected with the use of a memory component responsible for keeping track of the frequency of encountered packing structures. This memory component is used to systematically guide the method towards less explored packing arrangements.

For a given item set, the proposed heuristic employs a series of θ packing attempts. Under the weak mode of the packing heuristic θ = 1, whereas under the strong heuristic mode θ = 2500. As described in Sect. 3.2, the strong and weak modes are applied for cost improving and non cost improving local-search moves, respectively. Apparently, if all θ packing attempts fail to produce a complete feasible packing arrangement, the examined item set is declared infeasible regarding the loading constraints. On the contrary, if any attempt manages to produce a complete feasible packing structure, the heuristic terminates by declaring the examined item set feasible.

4 Computational results

To draw conclusions on the relative effectiveness of the three compared models, we have used the proposed algorithm as a policy evaluation tool. For all three examined strategies, this algorithm employs the same routing and packing optimization components. Thus, a fair model comparison is achieved. Regarding the effectiveness of the routing and packing components, it is proved by the high quality solutions obtained on well examined 2L-CVRP test cases (Zachariadis et al. 2015). Our computational results involve a set of newly constructed 2L-SPD instances. The proposed algorithm was coded in C# and executed on a single core of an Intel Xeon E5-2650 v2 (2.6 GHz) processor. All benchmark instances and obtained analytic solutions are available at http://users.ntua.gr/ezach/.

4.1 The benchmark test cases

To compare the three examined transportation strategies, a collection of new benchmark cases was constructed. In terms of the customer set, we have considered six graph sizes involving from 50 to 150 customers. For each size, two graphs were generated: a random and a clustered one. Thus in total, 12 problem graphs were obtained. For both random and clustered graphs, the depot is located at (x, y) = (50, 50). For the random graphs, the customer x and y coordinates take random integer values from the [0, 100] range. The clustered graphs also involve a [0, 100]2 grid. Ten-customer mutually exclusive geographic clusters are considered. These clusters correspond to squares of 10 distance units and are randomly placed within the grid. Customer coordinates take random integer values from the range defined by their cluster. The cost matrix is obtained by calculating the Euclidean distance between the node pairs of the graph. The L and W dimensions of the loading area are set to 288 and 102 inches, respectively, corresponding to light to medium-duty trucks. Then, for each customer i ∈ N, a set of items I i is constructed until the total area of this item set exceeds A i . The value of A i is uniformly distributed within [0.1 L·W, 0.3 L·W]. To set the item dimensions, we have used three item classes. For the first class, each item is randomly assigned to one of the pallet types used in the North American region. For the second and third classes, the length and width dimensions of each item is randomly set within [a·L, b·L] and [a·W, b·W], respectively. For the second class (a, b) = (0.2, 0.4), whereas for the third class (a, b) = (0.1, 0.8). Each of the generated items must be assigned to the delivery, or the pick-up item set of the associated customer. To do so, each item is declared either a pick-up item with probability u, or a delivery item with probability (1 − u). To examine different ratios of delivery to pick-up items, we consider three u values: 12.5, 25 and 50 %. Overall, 108 benchmark instances are introduced (6 graph sizes × 2 graph types × 3 item classes × 3 classes of delivery/pick-up assignments). They are presented in Table 1. The number of available vehicles was set after preliminary algorithmic executions, to ensure instance feasibility.

Table 1 The characteristics of the newly constructed test cases
Full size table

4.2 Computational results for the 2L-SPD model

The proposed solution approach was applied ten times on each of the 108 benchmark instances presented in Sect. 4.1, for the 2|O|SPD (fixed item orientation) and 2|R|SPD (item rotations) configurations. The results obtained are summarized in Tables A.1 and A.2, respectively. We observe that the proposed solution method has a rather stable performance. The gap between the best and average solution values obtained for each instance over the ten runs averages at 0.47 and 0.58 % varying within [0.00, 2.25 %] and [0.00, 2.67 %], for 2|O|SPD and 2|R|SPD, respectively. Regarding the average computational times required for obtaining the best solutions over the ten runs, they ranged between [0.4, 237.6] and [0.2, 227.7] averaging at 32.7 and 27.7 CPU min for the 2|O|SPD and 2|R|SPD versions, respectively.

4.3 Computational results for the 2L-VRPB model

The proposed solution approach was applied ten times on each of the 108 benchmark instances presented in Sect. 4.1, after applying the benchmark modification procedure described in Sect. 2.4 (the pick-up and delivery requests of a single customer are represented by two co-located customers raising a pick-up and a delivery request, respectively), under the 2L-VRPB model. Depending on the item orientation and LIFO constraints, four model versions were examined: 2|OU|VRPB, 2|OS|VRPB, 2|RU|VRPB and 2|RS|VRPB. The results for these model configurations are summarized in Tables A.3, A.4, A.5 and A.6, respectively. Again, a stable algorithmic performance is seen, as the average gap between the best and average solution scores over the ten runs is limited into satisfactory levels (2|OU|VRPB: 0.60 %, 2|OS|VRPB: 0.63 %, 2|RU|VRPB: 0.57, and 2|RS|VRPB: 0.61 %). The average CPU times required for obtaining the best solutions over the best runs ranged within [0.5, 147.8] and [0.2, 178.1] averaging at 28.2 and 30.5 CPU min for the non-LIFO VRPB versions, 2|OU|VRPB and 2|RU|VRPB, respectively. When LIFO constraints are imposed, the times involved are significantly higher. In specific, the ranges are [0.2, 147.1], [0.4, 189.4], averaging at 34.6 and 50.0 CPU min, for the 2|OS|VRPB and 2|RS|VRPB versions, respectively.

4.4 Computational results for the 2L-BiVRP model

The proposed solution approach was applied ten times on the benchmark instances presented in Sect. 4.1, after applying the benchmark modification procedure described in Sect. 2.4, under the 2L-BiVRPB model. Note that in total 216 instances are solved, since each of the original 108 2L-SPD problems is decomposed into two sub-problems. Four model configurations were examined: 2|OU|BiVRP, 2|OS|BiVRP, 2|RU|BiVRP, and 2|RS|BiVRP. The results for these model configurations are summarized in Tables A.7, A.8, A.9 and A.10, respectively. The gap between the best and average solution scores over the ten runs ranges within [0.00, 3.41 %], [0.00, 2.82 %], [0.00, 2.54 %], and [0.00, 2.67 %], averaging at 0.26, 0.28, 0.30, and 0.27 %, for the 2|OU|VRPB, 2|OS|VRPB, 2|RU|VRPB, and 2|RS|VRPB model configurations, respectively. When LIFO constraints are not taken into account, the average CPU times required for obtaining the best solutions over the best runs range within [0.2, 226.2] and [0.1, 353.6] averaging at 35.3 and 43.3 CPU min for 2|OU|BiVRP and 2|RU|BiVRP, respectively. When LIFO constraints are imposed on the model, the times involved are almost doubled. In specific, the ranges are [0.3, 371.4], [0.2, 482.0], averaging at 74.2 and 81.6 CPU min, for the 2|OS|BiVRP and 2|RS|BiVRP model versions, respectively.

4.5 Comparison of the routing costs incurred by the three models

The compared routing strategies have a number of counterbalancing characteristics: the 2L-VRPB and 2L-BiVRP models relax the 2L-SPD assumption of jointly serving the pick-up and delivery requirements of the customer set, as they allow vehicles to offer split service for the pick-up and delivery requests. On the contrary, they impose harder constraints in terms of the visiting sequence: for the 2L-VRPB, there is the precedence constraint which forces delivery visits to precede pick-up visits within routes, whereas for the 2L-BiVRP, we force delivery and pick-up requests to be served by different vehicle routes. To gain insight on the relative performance of the three models, we compare the best solution scores obtained. For each of the 108 test cases, we introduce two important parameters: β = (n D  + n P  + K)/(n + K) can be regarded as the increase on the number of arcs that may be travelled by the 2L-VRPB and 2L-BiVRP strategies in respect to the 2L-SPD one and ε = n P /(n P  + n D ) is the ratio of the pick-up requests over the total number of delivery and pick-up requests (n P and n D are introduced in Table 1). In addition, let λ A/B denote the percent increase of the routing costs incurred by strategy A in respect to the costs incurred by strategy B (λ A/B = 100 × (z A − z B)/z B). Table 2 presents the average λ values for the various model configurations tested.

Table 2 The relative effectiveness of the examined routing strategies
Full size table

From Table 2, it is clear that the simultaneous service of pick-up and delivery requests is capable of bringing substantial routing savings compared to the 2L-VRPB and 2L-BiVRP strategies. It is also obvious that the higher the PD class (the stronger the participation of the pick-up items in the mix of the transported items), the higher the cost savings achieved by the 2L-SPD model. In particular, for the fixed item orientation, the 2L-VRPB model increases the routing costs of the 2L-SPD one by 1.36, 3.87 and 7.55 % for the PD classes 0, 1 and 2, respectively. When LIFO constraints are incorporated into the 2L-VRPB model, these increase rates are higher (PD0: 2.22 %, PD1: 5.04 %, PD2: 8.65 %). When item rotations are allowed, a similar relative performance of the two models is seen: without LIFO constraints, the routing costs of the 2L-VRPB augment the 2L-SPD costs by 1.44, 4.18 and 7.96 % for the PD classes 0, 1 and 2, respectively, whereas when LIFO constraints are imposed on the 2L-VRPB model, the cost increase goes up to 2.70, 5.59, and 9.52 %. The performance of the 2L-BiVRP model is much poorer, because extra routes are opened and thus additional arcs must be traversed for moving to and from the depot. When no LIFO constraints are imposed and rotations are not allowed, the 2L-BiVRP model increases the 2L-SPD costs by 21.85, 46.23, and 78.78 % for PD classes 0, 1 and 2, respectively. When LIFO requirements are imposed on the 2L-BiVRP model, these percentages go even higher to 22.65, 47.45, and 80.10 %. When item rotations are permitted, the basic 2L-BiVRP model increases the 2L-SPD costs by 22.09, 46.54, and 78.65 %, for PD0, PD1, and PD2, respectively. Finally, when both rotations and LIFO constraints are taken into account, this cost increase ranges up to 23.45, 48.41, and 81.01 %.

Figure 4 provides 3-D scatter plots with individual λ values for the 2L-SPD and 2L-VRPB strategies against the β and ε parameters for the 108 instances tested. We observe that the increase of the routing costs of the 2L-VRPB strategy in respect to the 2L-SPD model has a strong positive correlation to the ε and β values. In particular, when no LIFO constraints are imposed and items are placed with fixed orientation, the 2L-VRPB strategy marginally improves the routing costs for only two out of the 108 test cases (0.46 % for 90-C-2-PD2 and 0.63 % for 90-R-2-PD2), while the λ 2|OU|VRPB/2|O|SPD range is [−0.63, 20.52]. For all other three configurations, the 2L-VRPB strategy consistently increases the routing costs of 2L-SPD. The λ 2|OS|VRPB/2|Ο|SPD , λ 2|RU|VRPB/2|R|SPD , λ 2|RS|VRPB/2|R|SPD value ranges are: [0.32, 20.80], [0.04, 21.82], and [0.16, 22.13], respectively.

Fig. 4
figure 4

The percent savings of 2L-SPD over 2L-VRPB. a 2|OU|VRPB versus 2|O|SPD, b 2|OS|VRPB versus 2|O|SPD, c 2|RU|VRPB versus 2|R|SPD, d 2|RS|VRPB versus 2|R|SPD

Full size image

Figure 5 indicates that serving delivery and pick-up requests with separate vehicle routes increases the 2L-SPD routing costs, even more strongly. For all four examined 2L-BiVRP configurations, all 108 best solutions scores are consistently worse than the corresponding 2L-SPD ones. Again, the cost increase exhibits a significant positive correlation to the ε and β values. The λ 2|OU|BiVRP/2|Ο|SPD λ 2|OS|BiVRP/2|Ο|SPD , λ 2|RU|BiVRP/2|R|SPD , λ 2|RS|BiVRP/2|R|SPD ranges are [11.29, 94.65], [12.74, 94.65], [11.48, 92.82], and [12.42, 93.76], respectively.

Fig. 5
figure 5

The percent savings of 2L-SPD over 2L-BiVRP. a 2|OU|BiVRP versus 2|O|SPD, b 2|OS|BiVRP versus 2|O|SPD, c 2|RU|BiVRP versus 2|R|SPD, d 2|RS|BiVRP vs 2|R|SPD

Full size image

4.6 Computational efficiency for the three compared models

One interesting observation is related to the computational time required for solving the three compared transportation models. The time spent for solving the 2L-SPD model seems to be comparable to the time required for the 2L-VRPB model. On the other hand, it is significantly lower than the time consumed for generating the 2L-BiVRP solutions. This is contrary to what we had expected: although the number of customers in the translated 2L-BiVRP instances is greater, the packing feasibility of just one arc is required for each route under the 2L-BiVRP model, whereas the 2L-SPD model requires that the loading aspects of all arcs travelled by each route have to be examined. To shed light on this rather unexpected finding, we have applied the proposed method for all examined model configurations and we have used various counters that record the number of times that some important steps of the algorithm feasibility methods have been executed:

  • F m : the number of loading feasibility checks of local-search moves.

  • F smd : the number of times that the loading feasibility of these moves was retrieved from the SMD instances.

  • F r : the number of loading feasibility checks for routes.

  • F rh : the number of times that the loading feasibility of routes was retrieved from the route hashtables.

  • F a : the number of loading feasibility examinations for travelled arcs.

  • F ah : the number of times that the feasibility of arcs was retrieved from the arc hashtables.

  • F p : the number of times that the packing heuristic was called.

  • F ps : the number of times that the packing heuristic obtained a feasible packing.

We note that for the 2L-VRPB model, up to two arcs per route are examined. In addition, for the 2L-BiVRP model, no individual arcs are examined, thus the arc hashtables are inapplicable. The results are summarized in Table 3. Each row provides average values over all 108 instances. Several interesting remarks are extracted: Firstly, the basic feature of the 2L-SPD model which calls for a feasible packing for each arc is efficiently tackled by the arc hashtable retrievals: 64 and 66 % of the arc feasibility checks are avoided by accessing the arc hashtables which limits the necessary packing heuristic calls to levels almost double compared to those required for the non-LIFO versions of 2L-VRPB. This aspect together with the higher rate of successful packing heuristic calls (which reduces the time-consuming unproductive packing efforts employed by each packing heuristic call) for the 2L-SPD model causes the CPU times elapsed when the best solutions of these two models are obtained to be comparable (2|O|SPD: 32.7 CPU min, 2|R|SPD: 27.7 CPU min, 2|OU|VRPB: 28.2 CPU min, 2|RU|VRPB: 30.5 CPU min). When LIFO constraints are imposed on the 2L-VRPB model, both the necessary feasibility evaluations of moves and routes are significantly higher. In addition, recording specific node permutations (not combinations) into the route hashtables brings fewer route feasibility retrievals from the hashtable structures. As a result, more packing heuristic calls are made and the CPU times for reaching the final solutions are higher (2|OS|VRPB: 34.6 CPU min, 2|RS|VRPB: 50.0 CPU min). Regarding the 2L-BiVRP model, we observe the following: since more nodes are involved in the instances (compared to the 2L-SPD model) and no precedence constraints are involved in the instance (in contrary to the 2L-VRPB model), the total number of move loading feasibility evaluations for the two sub-problems (delivery and pick-up sub-problems), are more in number. This causes the number of necessary loading checks for the candidate routes to be increased. As a result, the number of necessary calls to the packing heuristic is considerably higher compared to the 2L-SPD and 2L-VRPB models, particularly for the LIFO versions of the 2L-BiVRP. Thus, contrary to what was expected, the necessary CPU time for obtaining the 2L-BiVRP solutions—especially for the 2|OS|BiVRP and 2|RS|BiVRP configurations—is very high (2|OS|BiVRP: 74.2 CPU min, 2|RS|BiVRP: 81.6 CPU min).

Table 3 The role of the feasibility memory components for the examined transportation models
Full size table

5 Conclusions

In the present paper, we have compared three alternative transportation strategies for serving customer pick-up and delivery requests. These requests involve bi-directional item movements from a central depot to customer locations and vice versa. Feasible two-dimensional loading arrangements must be determined for the transported items. The reference model used for conducting the comparisons assumes that vehicle routes offer simultaneous pick-up and delivery service, so that items are delivered to and collected from customers by a single customer visit. The alternative transportation strategies are modeled by the vehicle routing problem with backhauls and two-dimensional loading constraints which considers that vehicles firstly deliver items to customers and then offer collection services before returning back to the depot, and the bi-directional vehicle routing problem with two-dimensional loading constraints which considers that pick-up and delivery requests are served using distinct vehicle routes. Towards a fair comparison, all three models are solved using a common optimization framework consisting of a local search method for the routing aspects and a two-dimensional packing heuristic for determining feasible loading arrangements of the transported items. The relative performance of the alternative strategies is tested on an extended set of newly constructed benchmark instances. These instances involve diverse features in terms of the number of customers, the size and number of transported items and the participation of pick-up items in the mix of total items to be transported. Numerical results indicate that offering simultaneous pick-up and delivery service and rearranging items onboard can bring substantial transportation cost savings. Comments are provided regarding the algorithm behavior on the three examined models.

In terms of future research, the integrated vehicle and packing models constitute an interesting field with several real-life applications which have not yet been sufficiently investigated. Composite routing-knapsack problems can be examined for cases where vehicles cannot exhaustively transport all items, so decisions must be made regarding which items must be selected to be distributed. In addition, strategies allowing split deliveries and collections should be investigated in the context of routing problems with loading constraints.