1 Introduction

Transportation and product distribution costs often make up for a great portion of the total operating and logistics costs of a company either upstream or downstream in the supply chain. For this reason, it is important to focus on the design of distribution networks aiming to optimize product flows in pursuit of cost savings. In this context, cross-docking systems have been widely used in real-life distribution networks. Cross-docks can be seen as intermediate transshipment facilities that regulate the flow of products from origin to destination locations. The main role is to collect products coming from multiple sources, to sort and consolidate the products, and to arrange their shipping to the next echelon or to the final destinations. The main difference between modern cross-docking systems and traditional single or multi-echelon distribution network structures is that inbound products arrive at the cross-dock and are directly loaded to outbound vehicles. Therefore, the cross-docking system is lean and maintains little or no inventory. This paper presents a new problem, the so-called many-to-many vehicle routing problem with cross-docking, which according to our knowledge generalizes previous problem settings that appear in the literature. Key feature is that each customer requests products from multiple suppliers, while there is the restriction to visit each customer and supplier only once during the planning horizon.

The problem introduced in this paper has numerous practical applications. It is common for retailers located in urban areas to replenish their stock by receiving goods from multiple production warehouses located around the city limits. This situation emerges when a retailer receives different types of products from the same logistics provider, and not all of them are available at a single supplier location. This creates cargo consolidation opportunities, which can be exploited by the proposed problem setting with major cost savings. Furthermore, the single visit requirement at the supplier and customer nodes is essential in practice to minimize the administrative, handling, and various types of setup costs and times (Tarantilis et al. 2011). Finally, recent pro-environmental city logistics initiatives are aligned with the use of cargo consolidation operations outside urban areas, in pursuit of dispatching lighter, greener, or even electric vehicles in the city to minimize the impact on the urban environment (Zachariadis et al. 2015). Interested readers may also refer to the recent survey paper of Guastaroba et al. (2016) for vehicle routing problems with intermediate facilities.

Cross-docking has several advantages compared to other product distribution strategies both from the economic and environmental viewpoints. As it is discussed in Ma et al. (2011), logistics carriers often offer discount prices for truck-load orders; however, in practice it is common to have customers that raise less-than-truckload orders. In these situations, cross-docking offers a straightforward cargo consolidation opportunity, which enables products originated from various suppliers to be combined in truckload shipments and, thus, to be shipped with the discounted carrier rates. Moreover, this direct consolidation process avoids holding cargo in the intermediate nodes until sufficient products for forming a truckload shipment has arrived at the expense of inventory costs. In addition, the use of an intermediate node for consolidating products has been seen to reduce the total distance travelled and, thus, the transportation costs incurred compared to the direct shipping alternative, especially when the origin and destination points are located in different geographic regions and the intermediate node is located between these regions (Nikolopoulou et al. 2017). Another aspect that makes the cross-docking strategy an attractive transportation logistics practice is that it promotes short cycle times, rarely exceeding a single day. As a result, the service quality of the overall distribution system increases. In fact, cross-docking is considered to follow the Just-In-Time principle. Another favorable feature of the cross-docking strategy is that it enables the use of different vehicle fleets for handling the inbound and outbound transportation operations. This is of major importance when product flows are originated from areas outside the city center and the destination points are located in urban areas. In these cases, it is desirable to use large capacity heavy-duty vehicles for moving products from the suppliers to the cross-dock. On the contrary, it is often essential to use more compact vehicles for travelling within the core city road network. This will allow traversing narrow streets and avoiding traffic congestion, providing delivery service in confined customer spaces, and minimizing the environmental impact in urban areas.

Cross-docking practice has received research attention, especially regarding the operational aspects of the cross-dock. Focus is given on maximizing throughput by examining the layout of the cross-docks (Bartholdi and Gue 2004), the positioning of consolidated products inside the cross-dock (Vis and Roodbergen 2008), and the assignment of vehicles to dock doors (Tsui and Chang 1992; Cohen and Keren 2009). Another important research stream is devoted to location problems for the cross-dock facilities (Musa et al. 2010; Sung and Song 2003). In terms of the inbound/outbound distribution operations, there is a group of papers that call for the joint minimization of the total transportation and inventory costs incurred by cross-docking logistics systems. The common characteristic of these works is that vehicle trips are modeled as direct links between origin (suppliers) and destination (customers) nodes, or direct links between the cross-dock and the origin and destination locations. Under this setting, a vehicle cannot serve more than one supplier (or customer) order. These models aim to identify the optimal balance between the product flows directly shipped from suppliers to customers and the flows passing through intermediate consolidation facilities (Ma et al. 2011).

The routing component of cross-docking distribution networks has been initially examined by Lee et al. (2006). In this work the authors assume that vehicles may visit more than one service locations along their trips, subject to capacity constraints. The model introduced calls for the minimization of the routing costs involved for transferring products between suppliers and customers. It also assumes that all products collected from the suppliers are moved to the cross-dock, where they are consolidated and loaded to outbound vehicles for the shipment of these products to the customers. As far as the synchronization is concerned between the inbound and outbound trips, the authors assume that all pickup routes arrive at the cross-dock simultaneously. To solve the problem, Lee et al. (2006) propose a Tabu Search algorithm that is tested on instances with up to 50 nodes. Later, Liao et al. (2010) propose for the same problem an improved Tabu Search algorithm.

More recently, Wen et al. (2009) introduce a vehicle routing variant denoted as Vehicle Routing Problem with Cross-Dock (VRPCD) that extends the model of Lee et al. (2006). More specifically, time window constraints are imposed on both suppliers and customers, while the simultaneous vehicle arrival restriction at the cross-dock is dropped. Instead, more elaborate synchronization constraints are introduced to bridge the timing of inbound and outbound vehicle routes. Another important feature of the VRPCD model is that each transportation request is associated with a specific origin and destination location, where every pickup (supplier) node is paired with a single delivery (customer) node. Wen et al. (2009) propose an Adaptive Memory Procedure applied on problem instances involving up to 200 transportation orders. Later, Tarantilis (2013) studies the same problem and also proposes extensions with respect to the route structure and the consolidation activities at the cross-dock. In particular, an alternative scenario is examined where different vehicles are used for the pickup and delivery routes. This scenario implies that all products are unloaded to the cross-dock and reloaded onto the delivery leg vehicles for being transported to the customer locations. In addition, Tarantilis (2013) differentiates between closed and open route configurations for both inbound and outbound routes. A multi-restart Tabu Search algorithm is proposed for solving all aforementioned problem versions. Another work on the basic VRPCD is that of Morais et al. (2014). In this work an iterative local search algorithm is proposed for solving VRPCD instances of up to 500 customers. Another paper on the transportation costs incurred when products must be transferred between origin and destination points, is due to Nikolopoulou et al. (2017). In this work two alternative transportation strategies are compared, namely direct shipping and cross-docking. Several computational experiments are performed to gain insight on the role of temporal and operational parameters on the relative effectiveness of each strategy. Lastly, Santos et al. (2013) study a VRPCD variant with a hybrid network structure. Instead of requiring all products to pass through the cross-dock, the authors allow direct shipping between suppliers and customers. To solve the problem, denoted as the Pickup and Delivery Problem with Cross-docking (PDPCD), a branch and price algorithm is proposed and applied to instances with up to 30 transportation requests.

A real-life vehicle routing with cross-docking application is presented by Petersen and Ropke (2011). They assume that vehicles depart from the cross-dock and may visit both suppliers and customers before returning back to the cross-dock facility. Each vehicle may visit the cross-dock several times for unloading/loading operations and the cross-dock can serve as a short-term inventory holding point for the products. More specifically, the products of a given request may be pickedup along a morning route and shipped to the cross-dock, where they are held until shipped to the destination point by means of an evening vehicle trip. Dondo et al. (2011) develop an MILP formulation for scheduling the operations taking place in a single cross-dock facility. Their model aims to maximize the cross-dock productivity by jointly designing the inbound/outbound vehicle trips and assigning vehicles to cross-dock doors. The authors also consider cases where the number of cross-dock doors is lower than the vehicles used, and thus, there is not always a free door for every vehicle during the time horizon. Enderer (2014) introduces the combined Dock-Door Assignment and Vehicle Routing Problem (DAVRP). This model aims to make decisions for the three distinct levels of a cross-dock system: (a) assignment of suppliers to inbound doors; (b) internal cross-dock routing plans and assignment of inbound products to outbound doors; and (c) vehicle routing plans for transporting the requested products to the customers using the outbound doors. Overall, the goal of the DAVRP is to minimize the total product handling and transportation costs. Finally, Grangier (2016) in his dissertation presents a matheuristic algorithm for the Vehicle Routing Problem with Dock Resource Constraints (VRPCD-DR).

The contribution of this paper is three-fold. First, a new generalized vehicle routing problem with a cross-dock is introduced. Most papers discussed above assume that every supplier is connected with only one customer (one-to-one VRPCD), while in most cases a common homogeneous fleet of vehicles is used for both inbound and outbound routes. Contrary, in the examined problem a many-to-many relationship between the suppliers and customers is considered, while different vehicle fleets are used to perform the pick and delivery routes. Second, an Adaptive Memory Programming method has been developed. Key characteristic is the mechanism for identifying and selecting elite components from the reference solutions. Particularly, the proposed mechanism assigns scores to all possible subroutes with varying length and gradually selects those with the highest score in terms of solution cost or diversity. A Tabu Search algorithm coupled with new long term memory structures is applied as the main optimization block for improving the quality of the new provisional solutions generated throughout the search process. Third, various computational experiments have been performed. Using well-known benchmark data sets for the one-to-one VRPCD, the proposed method proved to be efficient and effective compared to the current state-of-the-art. Furthermore, new best solutions have been found, while it seems that the method scales well with the problem size. On the other hand, the proposed method has been also tested on new data sets with diverse features regarding the geographic distribution of the network nodes as well as the density of supplier-customer links. This set of results provides several new insights regarding the effect of split options.

The remainder of the present paper is organized as follows: Sect. 2 describes the examined problem. Section 3 introduces the mathematical formulation for the problem. The proposed adaptive memory programming algorithm is presented in Sect. 4 and all its components are discussed. Next, Sect. 5 presents our computational study and findings on various benchmark data sets. Finally, Sect. 6 concludes the paper.

2 Problem description

Let G = (V, A) be a graph, where V is the node set and A is the arc set. V is composed of the cross-dock (node 0) and two node subsets S′ and D′, representing the supplier (pickup) and customer (delivery) locations, respectively. The arc set A is considered to link every pair of nodes that belongs either to the set \(S^{\prime\prime} = S^{\prime} \cup \left\{ 0 \right\}\) (pickup arcs), or to the set \(D^{\prime\prime} = D^{\prime} \cup \left\{ 0 \right\}\) (delivery arcs).

Consider a set of transportation requests O. Each request o ∈ O is associated with a supplier io ∈ S′, a customer jo ∈ D′ and a demand do. It calls for the transportation of do units of products from supplier io to customer jo. There is also the demand matrix dij (i ∈ S′, j ∈ D′) that represents the quantity of goods customer j requires from supplier i. Each non-zero dij (i ∈ S′, j ∈ D′) actually refers to a transportation request contained in O. Note that the demand matrix may have multiple non-zero entries in each row, meaning that each supplier may send products to more than one customer. For each supplier i (i ∈ S′), let \(p_{i}\) be the total amount of products supplied by i. In addition, each column may also have multiple non-zero values, and this corresponds to cases where a customer receives products from more than one suppliers. There is also a demand \(d_{c}\) associated with each customer c (c ∈ D′).

The set of transportation requests are to be fulfilled by two distinct fleets of vehicles, denoted as KS and KD. The vehicles from the set KS are considered to travel the S″ arcs, whereas vehicles from the KC set traverse only D″ arcs. The capacity of each vehicle k ∈ KS is equal to QS, whereas the capacity of each vehicle l ∈ KD is equal to QD. All pickup (or delivery) vehicles start and end their pickup (or delivery) routes at the cross-dock. In addition, the delivery routes should return to the cross-dock within a time limit T. Lastly, note that each supplier or customer must be visited only once.

The problem examined considers that vehicles of KS, based at the cross-dock, are dispatched to the suppliers S′, in order to collect all products associated with the transportation orders in O. These vehicles return to the cross-dock where the products are unloaded, and appropriately consolidated to be loaded onto outbound vehicles. For this purpose, vehicles from the KD set are used. As soon as the products for each delivery route reach the cross-dock, the delivery trip is performed and the products are transported to the customer locations. All vehicles performing delivery trips return to the cross-dock.

The objective is to design the set of pickup and delivery routes that minimize the total travelled distance. The produced set of routes is subject to the following constraints:

  1. (a)

    All inbound and outbound routes originate from the cross-dock and terminate at the cross-dock.

  2. (b)

    Each supplier i ∈ S′ must be visited once by exactly one pickup route and, thus, all products from the corresponding transportation requests associated with i must be assigned to the same vehicle.

  3. (c)

    The total amount of products assigned to a pickup route should not exceed vehicle capacity QS, and similarly the total amount of products assigned to a delivery route should not exceed vehicle capacity QD.

  4. (d)

    Each customer i ∈ D′ must be visited once by exactly one vehicle and, thus, all products from all transportation requests associated with i must be assigned to the same vehicle.

  5. (e)

    There is a maximum route duration T which refers to the total time required for completing all pickup and delivery operations. More specifically, every delivery route must terminate at the cross-dock no later than time T. Note that we do not apply any duration length restrictions on individual pickup or delivery routes, we only apply a maximum time limit T that all delivery vehicles should be back at the cross-dock.

  6. (f)

    A delivery vehicle cannot leave the cross-dock, until all products from the connected pickup routes arrive at the cross-dock.

Let a set RS to denote all pickup routes. Each pickup route r (r ∈ RS) visits a subset of suppliers Sr and it is assumed to leave the cross-dock at time zero. The time \(RT_{r}\) that the vehicle performing the pickup route r is “released” (i.e., has finished its pickup route and has unloaded all products) at the cross-dock, is equal to the total traveling time plus the service time (sps) spent at the location of each supplier s ∈ Sr plus the time spent for unloading operations (u) at the cross-dock. At the customer level, let RD be the set of delivery routes. Each r ∈ RD visits a subset of customers Dr. For every delivery route r, the total traveling time plus the service time (sdc) spent at each customer location c ∈ Dr is represented by \(t_{r}\). In addition, let \(DT_{r}\) denote the departing time from the cross-dock of a delivery route r. On this basis, the duration constraint (e) for every delivery route r can be expressed as \(DT_{r} + t_{r} \le T\). Constraint (f) is associated with the temporal characteristics of the examined problem, and dictates the synchronization between the pickup and delivery routes. Necessary condition for the departure of a delivery route is that all products requested by each of the customers (c ∈ Dr) of the route must be available at the cross-dock in order to be sorted and loaded onto the delivery vehicle. Therefore, for every route r ∈ RD, \(DT_{r} = a_{r} + l\), where \(a_{r}\) is equal to the maximum release time at the cross dock of all the relevant pickup routes that contain the products requested by the Dr customers. This is explained in detail in the example that follows (illustrated in Fig. 1). Finally, parameter \(l\) denotes the time for unloading operations that take place at the cross-dock.

Fig. 1
figure 1

Problem instance with four suppliers and six customers

Full size image

Figure 1 illustrates a problem instance with four suppliers and six customers. The link between a supplier and a customer node indicates that there is a transportation request for moving products between this node pair. Figure 1 also provides the demand matrix for the corresponding product flows. Supplier A sends products to customers 1 and 2, Supplier B send products to customers 1 and 6, and so on.

An example solution to the problem instance of Fig. 1 is shown in Fig. 2. Observe that there are two routes at the supplier level, and three vehicle routes at the customer level. The suppliers and customers are served by different vehicle types (k1, k2 ∈ KS and k3, k4, k5 ∈ KD). The pickup route assigned to vehicle k1 visits suppliers A and B and collects the products requested by customers 1, 2, and 6, whereas the pickup route performed by k2 visits suppliers C and D to pickup the products destined to customers 2, 3, 4, and 5. The capacity constraints for the inbound routes k1 and k2 ensure that dA1 + dA2 + dB1 + dB6 ≤ QS and dC2 + dC3 + dC4 + dD2 + dD3 + dD4 + dD5 ≤ QS, respectively. For the outbound routes k3, k4, and k5, the capacity constraints are dA1 + dB1 + dB6 ≤ QD, dA2 + dC2 + dD2 + dC3 + dD4 ≤ QD, and dC4 + dD4 + dD5 ≤ QD, respectively. Regarding the synchronization constraints discussed earlier, the release time for the products of delivery route k3 is \(a_{k3} = RT_{k1} + l\). This is because k3 serves customers 1 and 6 who receive products from suppliers A and B, both of them visited by k1. Similarly, the release times for routes k4 and k5 are \(a_{k4} = \hbox{max} \left\{ {RT_{k1} ,RT_{k2} } \right\} + l\) and \(a_{k5} = RT_{k2} + l\), respectively.

Fig. 2
figure 2

Example solution for the problem instance of Fig. 1

Full size image

The problem described above is closely related to the so-called Vehicle Routing Problem with Cross-Docking (VRPCD). As mentioned in the introduction section, the VRPCD has been introduced by Wen et al. (2009) and it assumes one-to-one relationships between suppliers and customers (i.e., each supplier is connected with only one customer and vice versa). Instead, in this paper a more generalized distribution network structure is considered with many-to-many relationships between the suppliers and the customers. Notably, many-to-many relationships can also be captured within a one-to-one VRPCD setting if we assume that collocated node copies are generated for every endpoint of the various transportation links. For example, consider the problem instance presented in Fig. 1. The many-to-many association between customers and suppliers can be translated into multiple one-to-one relations by generating a supplier-customer pair for each non-zero element in the demand matrix. As such, the resulting problem will contain 11 suppliers and 11 customer nodes. Besides the fact that the dimension of the problem increases, this setting would permit multiple visits per node (i.e., copies of the original supplier or customer nodes can be assigned to different vehicle routes). In practice, this is often undesirable given that the resulting service times from the multiple visits are typically higher due to the multiple setup times (e.g. for security procedures or for exchange of paperwork). On the contrary, in our model each supplier and customer node is served only once by exactly one vehicle.

3 Mathematical formulation

In this section we present and describe in detail the mathematical model for the many-to-many Vehicle Routing Problem with Cross-docking (many-to-many VRPCD) as described above. In addition to the notation introduced in Sect. 2, let us denote the set of pickup nodes by S = {0, 1,…, n + 1} and the set of delivery nodes by D = {0, 1,…, n′+1}. The cross-dock is represented by the nodes 0, n + 1 and n′+1, where the nodes 0 and n + 1 in S represent the starting and ending points for the pickup routes, while the nodes 0 and n′+1 in D represent the starting and ending points for the delivery routes, respectively. Note that these four nodes are associated with a zero amount of supply/demand and with zero service time. The set E denotes all the feasible arcs for the pickup operations. It consists of the arcs {(i, j): i, j ∈ S, i ≠ j}. The set E′ denotes all the feasible arcs for the delivery operations and consists of the arcs {(h, f): h, f ∈ D, h ≠ f}. Each arc (i, j) ∈ E is associated with a known non-negative distance csij, that represents the travel distance from pickup node i to pickup node j. Similarly, each arc (h, f) ∈ E′ is associated with a known non-negative distance cchf, that represents the travel distance from delivery node h to delivery node f. In addition, M is an arbitrarily large constant.

Indices and sets

i, j:

Index for pickup nodes (suppliers)

h, f:

Index for delivery nodes (customers)

k :

Index for pickup vehicles

l :

Index for delivery vehicles

Parameters

K S :

Number of available pickup vehicles

K D :

Number of available delivery vehicles

Q S :

Capacity of the pickup vehicles

Q D :

Capacity of the delivery vehicles

cs ij :

Travel distance between pickup node i and pickup node j ((i, j): i, j ∈ S, i ≠ j})

cc hf :

Travel distance between delivery node h and delivery node f ((h, f): h, f ∈ D, h ≠ f})

CV ih :

1, if pickup node i (i ∈ S ∩ {0, n + 1}) supplies (is connected to) delivery node h (h ∈ D ∩ {0, n′+1}); 0, otherwise

p i :

Amount supplied by pickup node i (i ∈ S)

d h :

Amount delivered to delivery node h (h ∈ D)

sp i :

Service time spent at pickup node i (i ∈ S)

sd h :

Service time spent at delivery node h, (h ∈ D)

u :

Time for unloading operations at the cross-dock

l :

Time for loading operations at the cross-dock

T :

Maximum route duration

Binary variables

x k ij :

1, if vehicle k (k ∈ KS) travels from pickup node i to pickup node j (i, j ∈ S); 0, otherwise

z l hf :

1, if vehicle l (l ∈ KD) travels from delivery node h to delivery node f (h, f ∈ D); 0, otherwise

y k i :

1, if pickup node i (i ∈ S) is serviced by vehicle k (k ∈ KS); 0, otherwise

v l h :

1, if delivery node h (h ∈ D) is serviced by vehicle l (l ∈ KD); 0, otherwise

Continuous non-negative variables

tp k i :

Time at which vehicle k leaves pickup node i (i ∈ S, k ∈ KS)

td l h :

Time at which vehicle l leaves delivery node h (h ∈ D, l ∈ KD)

RT k :

Release time of pickup vehicle k at the cross-dock (k ∈ KS)

DT l :

Starting time of delivery vehicle l at the cross dock (l ∈ KD)

Below we present the mathematical formulation of the many-to-many VRPCD as a mixed-integer linear programming model. The objective is to minimize total transportation costs.

$${\text{Minimize}}\mathop \sum \limits_{{\left( {i,j} \right) \in E}} \mathop \sum \limits_{{k \in K_{S} }} cs_{ij} \,\cdot\,x_{ij}^{k} + \mathop \sum \limits_{{\left( {h,f} \right) \in E'}} \mathop \sum \limits_{{l \in K_{D} }} cc_{hf} \,\cdot\,z_{hf}^{l}$$
(3.1)
$$\begin{aligned} & {\text{Subject to}} \\ & \mathop \sum \limits_{j \in S: i \ne j } x_{ij}^{k} = y_{i}^{k} \quad \forall i \in S \cap \left\{ {0,n + 1} \right\},k \in K_{S} \\ \end{aligned}$$
(3.2)
$$\mathop \sum \limits_{f \in D: h \ne f } z_{hf}^{l} = v_{h}^{l} \quad \forall h \in D \cap \{ 0,n^{\prime} + 1\} ,l \in K_{D}$$
(3.3)
$$\mathop \sum \limits_{{k \in K_{S} }} y_{i}^{k} = \, 1\quad \forall i \in S \cap \left\{ {0,n + 1} \right\}$$
(3.4)
$$\mathop \sum \limits_{{l \in K_{D} }} v_{h}^{l} = \, 1\quad \forall h \in D \cap \{ 0,n^{\prime} + 1\}$$
(3.5)
$$\mathop \sum \limits_{{j \in S \cap \left\{ 0 \right\}}} x_{0j}^{k} = \, 1\quad \forall k \in K_{S}$$
(3.6)
$$\mathop \sum \limits_{{f \in D \cap \left\{ 0 \right\}}} z_{0f}^{l} = \, 1\quad \forall l \in K_{D}$$
(3.7)
$$\mathop \sum \limits_{{i \in S \cap \left\{ {n + 1} \right\}}} x_{i,n + 1}^{k} = \, 1\quad \forall k \in K_{S}$$
(3.8)
$$\mathop \sum \limits_{{h \in D \cap \left\{ {n^{\prime} + 1} \right\}}} z_{h, n^{\prime} + 1}^{l} = \, 1\quad \forall l \in K_{D}$$
(3.9)
$$\mathop \sum \limits_{i \in S} x_{i0}^{k} = \, 0\quad \forall k \in K_{S}$$
(3.10)
$$\mathop \sum \limits_{h \in D} z_{h0}^{l} = \, 0\quad \forall l \in K_{D}$$
(3.11)
$$\mathop \sum \limits_{j \in S } x_{n + 1, j}^{k} = \, 0\quad \forall k \in K_{S}$$
(3.12)
$$\mathop \sum \limits_{f \in D } z_{n + 1,f}^{l} = \, 0\quad \forall l \in K_{D}$$
(3.13)
$$\mathop \sum \limits_{j \in S: i \ne j } x_{ij}^{k} = \mathop \sum \limits_{j \in S: i \ne j } x_{ji}^{k} \quad \forall i \in S \cap \left\{ {0,n + 1} \right\},k \in K_{S}$$
(3.14)
$$\mathop \sum \limits_{f \in D: h \ne f } z_{hf}^{l} = \mathop \sum \limits_{f \in D: h \ne f } z_{fh}^{l} \quad \forall h \in D \cap \{ 0,n^{\prime} + 1\} ,l \in K_{D}$$
(3.15)
$$\mathop \sum \limits_{i \in S} p_{i} \,\cdot\,y_{i}^{k} \le Q_{S} \quad \forall k \in K_{S}$$
(3.16)
$$\mathop \sum \limits_{h \in D} d_{h} \,\cdot\,v_{h}^{l} \le Q_{D} \quad \forall l \in K_{D}$$
(3.17)
$$tp_{\text{i}}^{\text{k}} + cs_{ij} + sp_{j} - tp_{\text{j}}^{\text{k}} {-}M\left( {1 \, - x_{ij}^{k} } \right) \le \, 0\quad \forall i \in S,j \in S \cap \, \left\{ {0,n + 1} \right\},k \in K_{S}$$
(3.18)
$$tp_{\text{i}}^{\text{k}} + cs_{i,n + 1} + u - RT_{k} {-}M\left( {1 - x_{i,n + 1}^{k} } \right) \le \, 0\quad \forall i \in S \cap \, \left\{ {n + 1} \right\},k \in K_{S}$$
(3.19)
$$RT_{k} \le CV_{ih} DT_{l} + M\left( { - y_{i}^{k} - CV_{\text{ih}} v_{h}^{l} + 2} \right)\quad \forall i \in S,k \in K_{S} ,h \in D,l \in K_{D}$$
(3.20)
$$DT_{l} + l + cc_{0f} + sd_{f} - td_{f}^{l} {-}M\left( {1 - z_{0f}^{\text{l}} } \right) \le 0\quad \forall f \in D \cap \, \left\{ 0 , n^{\prime}+1 \right\},l \in K_{D}$$
(3.21)
$$td_{h}^{l} + cc_{hf} + sd_{f} - td_{f}^{l} - M\left( {1 - z_{hf}^{l} } \right) \le 0\quad \forall \left( {h,f} \right) \in D \cap \, \{ 0,n^{\prime} + 1\} ,l \in K_{D}$$
(3.22)
$$td_{h}^{l} + cc_{h,n^{\prime} + 1} - td_{{\left( {n^{\prime} + 1} \right)}}^{l} {-}M\left( {1 - z_{h,n^{\prime} + 1}^{l} } \right) \le 0\quad \forall h \in D \cap \{ 0\} ,l \in K_{D}$$
(3.23)
$$td_{{\left( {n^{\prime} + 1} \right)}}^{l} \le T\quad \forall l \in K_{D}$$
(3.24)
$$tp_{i}^{k} \le My_{i}^{k} \quad \forall i \in S,k \in K_{S}$$
(3.25)
$$td_{h}^{l} \le Mv_{h}^{l} \quad \forall h \in D,l \in K_{D}$$
(3.26)
$$RT_{k} {-}M\left( {1 - x_{{0\left( {n + 1} \right)}}^{k} } \right) \le 0\quad \forall k \in K_{S}$$
(3.27)
$$DT_{l} {-}M\left( {1 - z_{{0\left( {n^{\prime} + 1} \right)}}^{l} } \right) \le 0\quad \forall l \in K_{D}$$
(3.28)
$$\mathop \sum \limits_{{k \in K_{\text{S}} }} y_{0}^{k} = 0$$
(3.29)
$$\mathop \sum \limits_{{k \in K_{\text{S}} }} y_{n + 1}^{k} = 0$$
(3.30)
$$\mathop \sum \limits_{{l \in K_{\text{D}} }} v_{0}^{l} = 0$$
(3.31)
$$\mathop \sum \limits_{{l \in K_{\text{D}} }} v_{n + 1}^{l} = 0$$
(3.32)

The objective (3.1) is to minimize the total distance traveled. Constraints (3.2) and (3.3) ensure that each node is visited once by one vehicle. Constraints (3.4) and (3.5) guarantee that each request is pickedup or delivered in only one pickup or delivery route, respectively. Constraints (3.6)–(3.10) guarantee that every route leaves the corresponding starting point and returns to the ending point. There are also constraints to guarantee that routes do not return to the starting points nor leave the ending points (3.11)–(3.13). Constraints (3.14) and (3.15) are flow conservation constraints. Constraints (3.16) and (3.17) ensure that for each vehicle, the load on the pickup route and the delivery route does not exceed the vehicle capacity. Constraint (3.18) computes the time a pickup vehicle k arrives at pickup node j after visiting pickup node i. Constraint (3.19) computes the time at which vehicle k arrives at the cross-dock from pickup route for unloading. Constraint (3.20) is the connectivity constraint among pickup and delivery routes. This constraint states that the delivery route l of an order h cannot start until the corresponding request has been picked up, arrived at the cross-dock and been unloaded from pickup vehicle k. Next (3.21)–(3.24) are time constraints for the delivery routes. In particular, constraint (3.21) computes the arrival time at the first delivery node visited on route l. Constraint (3.22) computes the arrival time at delivery node j which is visited after node i on route l. Constraint (3.23) computes the arrival time of vehicle l at the cross-dock and it is ensured that this time is within the maximum route duration limit T (3.24). We have also added constraints (3.25) and (3.26) to keep the starting time of pickup/delivery nodes not visited on a pickup/delivery route at 0. Similarly, constraints (3.27) and (3.28) keep the finishing/starting time of a not-driven pickup/delivery route at 0. Constraints (3.29)–(3.32) ensure that the starting and ending points (cross-dock) are not serviced by any pickup or delivery vehicle.

The above MILP model was solved using IBM ILOG CPLEX 12.5. Computational experiments for small scale problem instances and implementation details are reported in Sect. 5.3.

4 Solution method

An Adaptive Memory Programming (AMP) metaheuristic algorithm has been developed for solving the many-to-many VRPCD. AMP is a general-purpose solution framework that focuses on the exploitation of strategic memory structures (Glover 1997). The adaptive memory rationale was introduced by Taillard et al. (2001). The main goal is to identify solution characteristics frequently found in the search history and use this information to produce high-quality solutions. AMP frameworks have also been developed to efficiently solve vehicle routing problems (Repoussis and Tarantilis 2010; Tarantilis 2005). Gounaris et al. (2014) presents an AMP framework to address the robust capacitated vehicle routing problem. Cardona-Valdés et al. (2014) have developed an AMP framework to address the design of a two-echelon production distribution network. Lastly, Paraskevopoulos et al. (2016) are among the first to present an AMP framework for the Resource-Constrained Project Scheduling Problem (RCPSP).

Following the earlier works of Taillard et al. (2001), Tarantilis (2005) and Gounaris et al. (2014), the proposed framework consists of two phases. During the initialization phase, the goal is to generate a reference set of high quality solutions. Subsequently, the exploitation phase is triggered, that incorporates adaptive memory mechanisms for identifying elite solution components that are used to generate new provisional solutions. In both phases, a Tabu Search algorithm is employed as a local search method applied for further improvement and for reaching high quality local optimal solutions.

The pseudocode of the proposed AMP algorithm is depicted in Algorithm 1. Starting from an empty reference set P, μ high quality solutions are generated during the initialization phase (Lines 2–10). Α generalized savings heuristic (Line 4) is employed to generate random initial solutions. This is achieved via a greedy randomized mechanism controlled via parameter λ (see Sect. 4.1). All initial solutions are locally improved via a Tabu Search metaheuristic algorithm (Line 5) that is controlled through parameters ξ and ζ, described in Sect. 4.4. Subsequently, the exploitation phase is triggered (Lines 11–19). During this phase, elite solution components from the reference set P are extracted according to a deterministic set of criteria that make use of the parameter θ. Given these components, an intermediate solution \(x^{elite}\) is generated (Line 12) based on which the final provisional solution \(x^{\prime}\) is constructed via the saving construction heuristic (Line 13). The criteria of extracting solution components and generating the provisional solution \(x^{\prime}\) are described in Sect. 4.3. Next, the provisional solution \(x^{\prime}\) is further improved by the Tabu Search metaheuristic algorithm (Line 14), and after this local search process is completed the improved solution \(x^{\prime\prime}\) is used to update the reference set P (Line 18). The improvement phase terminates whenever a pre-specified time limit tlm is reached (Line 11), and the best feasible solution xB encountered throughout the AMP framework (Line 20) is returned.

4.1 Greedy randomized savings construction heuristic algorithm

A generalized savings heuristic algorithm similar to that proposed in Gounaris et al. (2014) is adopted in this paper. The construction framework starts from an initial intermediate feasible solution (x0). During the initialization phase, this is a solution where one pickup or delivery vehicle is assigned to each pickup or delivery node, respectively. On the other hand, during the exploitation phase, this is a solution where one pickup or delivery vehicle is assigned to an elite component/subset of connected pickup or delivery nodes, respectively. In any case, all pickup and delivery routes originate and terminate at the cross-dock, while all nodes are assigned to vehicle routes. Furthermore, only feasible combinations of pickup and delivery routes are considered with respect to the maximum route duration and synchronization constraints. Lastly, note that no limit is imposed on the total number of pickup or delivery routes.

Given the initial intermediate solution, at each iteration two pickup (or delivery) routes are selected and merged according to the following generalized savings scheme. Let two routes \(r = \left\{ {0, \ldots ,i,j, \ldots ,0} \right\}\) and \(r^{\prime} = \left\{ {0,i^{\prime}, \ldots ,j^{\prime},0} \right\}\). The savings function evaluates to \(c_{ij} + c_{{0i^{\prime}}} + c_{{j^{\prime}0}} - c_{{ii^{\prime}}} - c_{{jj^{\prime}}}\), where \(c_{ij}\) is the travel distance for traversing arc (i, j). The merging of route pairs is repeated either until all merging combinations in all possible positions produce negative savings or no feasible merging combination can be found with respect to the capacity, duration and synchronization constraints. Note that both pickup and delivery routes are consider during the construction process.

In an effort to diversify the reference set P, a probabilistic mechanism is added during the solution construction process similar to that proposed by Tarantilis et al. (2013). Particularly, a restricted candidate list of feasible merging combinations between pickup or delivery routes with positive saving is maintained at each iteration, which contains the route pairs with the highest saving. To that end, one route pair from the list is selected at random, and the corresponding vehicle routes are merged. In our implementation, the restricted savings list is fixed to a predefined size λ.

4.2 Reference set update method

In both initialization and exploitation phases the reference set P contains a maximum number of solutions μ. It is well documented in the literature that one essential element for the performance of population-based approaches is to maintain the diversity of the population during the search. This need intensifies for methods with relatively small populations, such as scatter search, path relinking and AMP approaches. In the proposed solution method, the reference set P is updated with solutions that are not only attractive in terms of the total transportation costs, but also in terms of diversity (measured in terms of total number of different arcs with respect to the best encountered solution). From the implementation viewpoint, an elitist strategy is adopted. Let x denote the candidate solution for insertion into P, xr any reference solution of P, and xB and xW the best and the worst solutions of P, respectively. If x performs better than xB in terms of cost, f(x) < f(xB), then x replaces xW; otherwise, if f(x) < f(xr), then x replaces xr only if d(x, xB) > d(xr, xB), where d(x, xB) represents the total number of different arcs between solutions x and xB.

4.3 Generation of provisional solutions

The goal of the exploitation phase is to generate new provisional solutions by combining elite components encountered in the reference solutions. An elite component refers to a subroute, i.e., an ordered subset of nodes (either pickup or delivery nodes) that appears frequently in the reference solutions. The first step is to select and isolate these subroutes considering both pickup and delivery routes. Let lz denote the length, i.e., the number of nodes (either suppliers or customers), of a subroute z. A component z may be as large as a complete route and as short as an individual arc connecting two nodes, therefore lz ≥ 2 (i.e., singleton nodes do not qualify as components).

During the scoring and selection process, the final set of extracted components should consist of non-overlapping node sets in order to be suitable for recombination in a new solution. Furthermore, we always make sure that it is feasible to send one vehicle to serve all selected pickup and delivery subroutes with respect to the capacity, route duration and synchronization constraints. For scoring the subroutes, the metric introduced by Gounaris et al. (2014) is adopted and each elite component z is assigned a score \(H_{z}\) as follows: \(H_{z} = \frac{{\left( {\mathop \sum \nolimits_{x \in P} w_{x} I_{x,z} } \right)}}{{\left( {1 - \vartheta } \right)^{{l_{z} - 2}} }}\), where \(w_{x}\) is the solution score and \(I_{x,z}\) is a binary indicator taking the value of 1, if the subroute appears in the solution x, and 0 otherwise. The term \(\left( {1 - \vartheta } \right)^{{l_{{z^{ - 2} }} }}\) quantifies the adoption of longer subroutes at the expense of their shorter subsets, where θ ∈ (0, 1). Two strategies are followed to calculate the weight factor wx that are used interchangeably with equal selection probability. The first strategy takes into account the dissimilarity \(ds\left( {x,x^{\prime}} \right)\), i.e., number of different arcs, between two solutions \(x\) and \(x'\) and is calculated as follows [see also Tarantilis et al. (2013): \(ds\left( {x,x^{\prime}} \right) = \mathop \sum \nolimits_{{\left( {i,j} \right) \in A}} h_{ij}\), where \(h_{ij}\) is a binary indicator taking the value of 1, if (i, j) is an edge of either solution x or \(x^{\prime}\) (but not both), and 0 otherwise]. In this strategy, the weight factor is calculated as \(w_{x} = ds\left( {x,x^{B} } \right)/max_{{x^{r} \in P}} d\left( {x^{r} ,x^{B} } \right)\), where xB is the current best reference solution. Contrary, the second strategy takes into account only the cost. In this case, the weight factor wx is calculated as: \(w_{x} = \left( {max_{{x^{r} \in P}} f\left( {x^{r} } \right) - f\left( x \right)} \right)/(max_{{x^{r } \in P}} f\left( {x^{r} } \right) - min_{{x^{r } \in P}} f\left( {x^{r} } \right))\).

Having scored each possible delivery and pickup subroute extracted from all reference solutions, the subroutes are sorted according to their score with decreasing order. Once a subroute is selected from the list as elite component, all remaining subroutes that share at least one supplier or customer with the selected subroute are removed from the sorted subroute list. The selection is repeated until either the list is empty or there is no way with the remaining subroute to generate a feasible solution. Α feasible intermediate solution (\(x^{elite}\)) is then generated by assigning a vehicle to each of the selected elite components as well as to any singleton supplier or customer that does not participate in any of the selected elite components. At this point, the greedy randomized savings construction heuristic algorithm described in Sect. 4.1 is employed to obtain the new improved provisional solution. Notably, the provisional solution will often provide different combinations of the elite components since it goes through the route merging procedure.

4.4 Tabu search

All generated solutions are subject to local search via a Tabu Search metaheuristic algorithm. The latter explores the solution space by performing search trajectories based on edge-exchange moves from a current solution to the best admissible neighboring solution. The overall procedure iterates for a number of iterations and the best solution is returned. Below, each major component is described.

4.4.1 Neighborhood structures

The edge-exchange neighborhood structures considered are 0–1 node relocation, 1–1 node exchanges and 2-Opt exchanges (Zachariadis and Kiranoudis 2010). A lexicographic neighborhood evaluation scheme is adopted, while only feasible solutions are considered. The size of 0–1 Relocation and 2-Opt is \(O\left( {n^{2} } \right)\), while the size of 1–1 Exchange is \(O\left( {n^{4} } \right)\). All of them involve a constant number of edge exchanges.

The 0–1 node relocation removes any supplier (or customer) node from its current position, and reinserts this node into any other available position. Note that both intra- and inter-route node relocation moves are considered. The 1–1 exchanges any two supplier (or customer) nodes served by two different pickup (or delivery) routes. More specifically, the first supplier (or customer) node can be pushed in any available insertion position in the route originally serving the second supplier (or customer) node. Similarly, the second supplier (or customer) node can be inserted in any available insertion position combination of the route originally serving the first supplier (or customer) node. Note that both intra- and inter-route exchange can be performed. Obviously, the two nodes involved in the exchange must be of the same type (pickup or delivery). Lastly, the 2-Opt exchange removes a pair of edges and replaces them by a new pair in the solution. 2-Opt can be applied on the same route (the visiting sequence of a subroute is reversed) and between a pair of routes (subroute segments each including the cross-dock are swapped).

4.4.2 Short-term memory, aspiration conditions and diversification mechanism

Our Tabu Search framework operates according to the best admissible local move scheme. Specifically, all neighborhood structures of the current incumbent solution are exhaustively explored, and the highest quality feasible neighboring solution is selected at each iteration. To avoid an over-intensified search, a diversification mechanism is introduced similar to the Attribute Hill Climber presented by Whittley and Smith (2004). Each arc (i, j) ∈ A is associated with a threshold tag ta. Every time a move m is applied to a solution x with objective value f(x), the threshold tags of the eliminated arcs (Em) are set equal to f(x), i.e., ta = f(x), ∀ a ∈ Em. Any move m that forms a solution x’ is considered admissible only if the cost tags of the generated arcs (Cm) exceed the objective value of the modified solution x′, i.e., ta > f(x′), ∀ a ∈ Cm. Note that the threshold tags are re-initialized to a large value after a number of iterations ξ, while a maximum number of iterations ζ is imposed as termination condition.

5 Computational experiments

5.1 Experimental settings and parameter values

Various computational experiments have been performed to examine the inherent characteristics of the many-to-many VRPCD, as well as to access the performance of the proposed AMP solution method. At first, focus is given on the one-to-one VRPCD; the benchmark data set of Wen et al. (2009) and Morais et al. (2014) are used to compare our method with respect to the current state-of-the-art approaches of the literature. The results of the comparative performance analysis are reported in Sect. 5.2. Next, attention is given on the new generalized problem setting, and new benchmark data sets are generated with up to 200 nodes considering different geographical distributions and varying supplier-to-customer connection densities. The data generation method of the new benchmark data sets as well as the discussion of the computational results are reported in Sects. 5.3 and 5.4.

Regarding the experimental setup, the proposed AMP method was implemented in C# and the MILP was solved using the CPLEX 12.5 callable library. All experiments for each problem instance were executed on a single core of a computer system equipped with an Intel Xeon CPU E5-2650 v2 (2.60 GHz) and 16 GB of RAM under Windows Server 2012. A CPU time limit of 6 h was imposed for the execution of CPLEX. During the branch and cut process nodes were selected according to the best-bound criterion and all CPLEX heuristics were disabled. Note also that the best found solution from the AMP metaheuristic algorithm was used as the initial MIP start solution (upper bound) for CPLEX. On the other hand, for the AMP all computational times reported are in seconds. Unless otherwise stated, 10 simulation runs are performed for each problem instance, and the best out of the 10 runs is reported in the tables. All best solutions obtained for the new benchmark data sets are reported in “Appendix”.

Regarding the AMP parameter settings, a single set has been used for all experiments. Although better results could be in principle obtained by varying the parameters for each individual problem instance, we selected to adopt after minor tuning the parameter set that seemed to perform well for the majority of problems. In particular, we set λ = 12, μ = 12, θ = 0.4, ξ = 2*(total number of requests) and ζ = 600. Unless otherwise stated, the maximum time limit tlim for each run is set to 3600 s.

5.2 Assessment of the method and discussion of results for the one-to-one VRPCD

At first, the proposed AMP method is applied for the one-to-one VRPCD using the benchmark data set of Wen et al. (2009) with up to 200 requests as well as the data set of Morais et al. (2014) involving up to 500 requests. Previous algorithms solve these instances considering variable times for the unloading and loading operations taking place at the cross-dock as well as time windows for both suppliers and customers. In order to ensure a common and fair basis for comparison, we have modified our AMP algorithm accordingly to take into account all necessary operational realities, and in particular, we followed the so-called CS1 consolidation scenario for the cross-dock operations as described by Tarantilis (2013). This scenario assumes that the same vehicle fleet is utilized for both pickups and deliveries. In this case, only the pickup products that will be delivered to their corresponding customers by another vehicle will be unloaded from the pickup vehicles at the cross-dock, and subsequently they must be sorted and reloaded to the corresponding delivery vehicles. In addition, this scenario assumes that both suppliers and customers have to be serviced within predefined time windows.

The computational results obtained for the Wen et al. (2009) and Morais et al. (2014) instances are summarized in Tables 1 and 2, respectively. Our algorithm exhibits a reliable performance. In particular, for the Wen et al. (2009) instances, it managed to find one new best solution (50b instance). For the rest of the instances, the algorithm is close to the best known solutions (BKS)—which are highlighted in bold font- and it has a worst case performance of 1.00%, with an average deviation from the BKS of 0.24%. No significant variations with respect to the solution cost are observed over the 10 runs for each instance. Finally, it is worth noticing that the proposed method scales-up well in terms of solution quality and computational times with respect to the problem size. Better are the figures for the larger data set of Morais et al. (2014). The proposed AMP in this data set consistently improves the best solutions for 15 out of 16 instances. The average improvement on the best known solutions is −0.12%, ranging from +0.30 to −0.31%.

Table 1 Comparative results on the VRPCD problem instances
Full size table
Table 2 Comparative results on the Morais set of instances
Full size table

5.3 Small-scale many-to-many VRPCD instances

For the initial assessment of the proposed AMP algorithm we have generated 8 instances derived from the well-known data sets of Li and Lim (2001) originally introduced for the Pickup-and-Delivery Problem (PDP). The instances generated are from the Random class set of instances (lr100) involving cases where the suppliers and customers are randomly distributed. All of the instances involve 5 suppliers and 15 customers whose locations were randomly selected from the lr100 data set of Li and Lim (2001). Furthermore, in the first four instances (lr2_) customers request products from up to 2 suppliers, while in the last four instances (lr3_) customers request products from up to 3 suppliers. Note that for all instances we consider a common fixed service time for each supplier and customer location (as obtained from the original instances) as well as fixed times for the unloading and loading operations at the cross-dock. Table 3 reports the computational results produced by the AMP metaheuristic algorithm compared to the optimal solutions or lower bounds obtained from CPLEX.

Table 3 Computational experiments on small-scale many-to-many VRPCD problem instances
Full size table

The AMP algorithm exhibited a very stable performance. For all 8 problems, all ten runs obtained the same final solution (bst). In terms of the computational time, the average time required by the AMP for reaching the final solution of each of the ten runs ranged from 5.5 up to 8.75 CPU seconds for the lr2_ and lr_3 instance series, respectively. Concerning the MILP CPLEX runs, the smaller problems appeared to be easier to solve: for all 4 instances of the lr2_ instance series, CPLEX managed to close the gap and find the best solution obtained initially by the AMP (optimality tolerance was set equal to 0.01%), whereas for the lr_3 instance series, CPLEX found the best solution obtained initially by the AMP for 2 out of 4 instances.

5.4 Medium- and large-scale many-to-many VRPCD instances

5.4.1 Data set generation method

A new data set of benchmark problem instances has been generated. Similarly to the set of instances described in Sect. 5.3, these problem instances are also derived from the data sets of Li and Lim (2001). Three main classes of instances are developed, namely Random, Random-Clustered and Clustered referring to the geographic distribution of supplier and customer nodes. The Random class involves cases where the suppliers and customers are randomly located in the same geographic region, whereas the Clustered class involves cases where suppliers and customers are located in different areas (clusters). In the Random-Clustered case only some suppliers and customers are located in the same area. The Random and Random-Clustered instances are produced by modifying the following sets: lr100; lrc100; LR1_2, and LRC1_2, respectively. The Clustered instances are produced by modifying the following sets: lc100 and LC1_2. Initially, collocated nodes are removed from the graphs. The cross-dock is set to be the original depot node. Then, the sets of suppliers and customers are generated from the nodes of the original instance. Let norg be the number of pickup and delivery nodes of the original nodes after the collocated points have been removed. Obviously, |S′| + |D′| = norg. Three ratios of supplier participation σ = |S′|/norg are considered: 10, 30 and 40%. For the Random and Random-Clustered instances, the number of suppliers |S′| is randomly picked out of the norg vertices. On the contrary, for the Clustered instances, the number of suppliers |S′| is manually picked to be concentrated into different regions compared to the rest of the node population. The remaining norg − |S′| nodes are included in the set of customers.

To quantify the distribution of the node locations for the generated sets, the Nearest Neighbor Index (NNI) is used (Clark and Evans 1954). The NNI is defined as the ratio \(V_{obs} / V_{ran}\), where the observed distance \(V_{obs}\) represents the average over all distances between each point and its nearest neighbor, and the random distance \(V_{ran}\) is the expected average distance that would occur, if the distribution was random. The former is given by \(V_{obs} = (\sum\nolimits_{i \in S \cup D} {min_{j \in S \cup D, i \ne j} (d_{ij} ))/n_{org} }\). The latter can obtained as \(V_{ran} = 0.5 \sqrt {Y/n_{org} }\), where Y is the area of the grid. NNI values <1, indicate some degree of clustering. In Table 4, we provide the NNI values for the three geographic distribution classes.

Table 4 Nearest neighbor index (NNI) for the three geographic distribution classes
Full size table

After separating the set of nodes into customers and suppliers, the transportation request flows are identified. At first, the demand of each customer c is set equal to dc, where dc is the absolute value of the original demand of node c (note that in the original data set a node could be either a delivery or a pickup node). Next, we define the maximum number of suppliers serving each customer node c. For this purpose, we have used four different “supplier-customer connection density” classes ε with 1, 2, 3, and 4 number of connections, respectively. To that end, the total dc quantity is randomly allocated to the ε supplier nodes. Special care is given so that each supplier is associated with at least one customer node. From the demand matrix perspective presented in Sect. 2, note that \(\mathop \sum \nolimits_{i \in S} d_{ij} = d_{c} , \forall j \in D\) and \(\mathop \sum \nolimits_{j \in D} d_{ij} > 0, \forall i \in S\).

In terms of the capacities of the inbound and outbound vehicles, we used \(Q_{S} = 5\mathop \sum \nolimits_{c \in D} d_{c} /\left| D \right|\) and \(Q_{D} = 0.5Q_{S}\) rounded down to the nearest ten. If these values cannot guarantee feasibility, they are set to the minimum capacity levels adequate for serving every supplier or customer node. Regarding the time characteristics of the problem, for all pickup/delivery nodes the service time st is common and is equal to the original value used by Li and Lim (2001). In terms of the loading and unloading operations taking place at the cross-dock, we set u = l = 2st. For each problem instance and σ-class combination, all four ε-class instances are associated with a common maximum route duration (T) value. This T value is heuristically obtained so as to ensure both a challenging interplay with the capacity constraints as well as the feasibility of the instances. In total, 708 instances are generated (59 original PDP problem instances x 3 σ classes x 4 ε classes).

5.4.2 Assessment of the proposed method on the new benchmark instances

Table 5 summarizes the average results obtained for the many-to-many VRPCD on the new benchmark data sets (detailed solutions for all problem instances can be found in “Appendix”). The problem instances are initially divided in two sections referring to instances with 100 and 200 nodes. Furthermore, the problem instances are grouped according to their characteristics. In particular, each result represents the average solution costs for all problem instances of the same geographic distribution (R, RC, C) class, supplier-customer density (ε) class and supplier participation ratio (σ).

Table 5 Average solution costs obtained for the new benchmark data sets
Full size table

One main observation is that the transportation costs increase for all cases as the supplier participation ratio increases from 10 to 40%. This is not surprising as the problem instances with higher supplier participation ratio, involve vehicles with low capacities, and therefore, more pickup and delivery routes are required to serve all requests. Table 5 also reveals reduced costs for the clustered distribution class (C) for all instances with 100 and 200 nodes, compared to the random classes (R and RC). We observe that the average costs decrease as the geographic distribution of the nodes becomes more clustered, for the cases where the supplier participation ratio is 10 and 30%. This indicates that the cross-docking operations might be more beneficial when the customers are clustered. However, this is not the case for instances where the supplier participation is high (40%). This is possibly due to the fact that the original Li and Lim (2001) instances of the C class have larger T values, and larger cross-dock preparation times compared to the instances of the R and RC classes. Therefore, when the supplier participation increases, vehicles perform routes to more isolated/distant nodes, and the loading and unloading operations taking place at the cross-dock are more time-consuming.

Considering the implications on transportation costs with respect to the supplier-customer density class, a rather unexpected result occurs. We observe reduced transportation costs when customers are associated with more than one suppliers, compared to cases where there is a one-to-one relationship between suppliers and customers. More specifically, for all the groups of problems where the supplier participation ratio is low (10%), transportation costs decrease for the more dense groups (ε = 4), compared to the problem groups with ε = 1. The same finding is also observed for the R and RC classes of all instances with 30% supplier participation ratio. This shows that cost savings can be achieved when customers are able to receive the total delivery quantity by multiple suppliers, not just one. Similar are the findings for the average solutions obtained for problem instances with 200 nodes among the R, RC and C classes.

5.4.3 Computational experiments with collocated nodes and split options

In this section, the benefit of splitting requests by alleviating the restriction that each node should be visited only once is examined. For this purpose, we transform the many-to-many data sets presented in Sect. 5.4.1 so as to consider a one-to-one mapping between suppliers and customers (as such different requests may involve collocated suppliers and customers).

To make this transformation, we generate for each supplier node i that is connected with more than one customers, collocated supplier nodes that are copies of the original i node. Obviously, the total number of collocated suppliers generated for supplier i is equal to the total number of non-zero entries in row i of the demand matrix. Similarly, the total number of collocated customers generated for customer j of the original problem instance, is equal to the total number of non-zero entries in column j of the demand matrix. To generate the service times for each node of the modified instance, we divide the original service time value st by the number of node copies generated. In what follows, we denote as Data Set I the transformed data set with originally 100 nodes and as Data Set II the transformed data set with originally 200 nodes.

Table 6 summarizes the average results obtained for all groups of problems on the transformed data set. Detailed solutions for all problem instances can be found in “Appendix”. Similar to Table 5, the problem instances are initially divided into two sections with respect to the problem size, i.e., 100 and 200 nodes. Note that for all problem instances of the same geographic distribution (R, RC or C) class, supplier-customer density (ε) class and supplier participation ratio (σ), Table 6 presents the average solution costs for each group of problems as well as the average number of split requests #s, including both pickups and deliveries. Let ki be the total number of vehicle routes serving the node copies of supplier i. Then, the number of split pickup requests for supplier i is defined as \(s_{i} = (\sum\nolimits_{i \in S} {k_{i} } ) - 1\). Similarly, let kj be the total number of vehicle routes serving the node copies of customer j. Then, the number of split delivery requests for customer j is defined as \(s_{j} = (\sum\nolimits_{j \in D} {k_{j} } ) - 1\).

Table 6 Average solution costs obtained for the transformed data set (data set I and II) with collocated nodes and split options
Full size table

Compared to Table 5, we can clearly observe that better on average costs can be obtained when splitting of the transportation requests is allowed. This is not surprising, as splitting yields more opportunities for cost improvement through combined pickup and/or delivery routes. Another observation from Table 6 is that for the cases where the supplier participation ratio is low (10%), splitting requests does not improve the overall costs. However, this is not the case for the clustered instances (C class). As shown in Table 6, allowing requests that belong to C class to be split, results in reduced average transportation costs for all classes of the supplier participation ratio. Lastly, Table 6 reveals that the average number of split requests is higher for the random (R) distribution class, and in particular for the larger supplier-customer connection density instance (ε) classes. Allowing requests to be split in this case, may yield substantial savings. Note that the total service time of each pickup (or delivery) node in the transformed data set is divided by the number of customers (or suppliers) connected to this node so that the comparison between the two data sets is fair. However, in practice we often need to add extra setup time the service at each node, and this is the trade-off we need to consider.

6 Conclusions

This paper examined a new vehicle routing problem with pickups, deliveries and a cross-dock facility. Key feature of the examined problem was that each customer might request products from multiple suppliers, while there is the restriction to visit each customer and supplier node only once by exactly one vehicle. To our knowledge this many-to-many relationship for the VRPCD appears for the first time in the literature, and it can be seen as a generalization of one-to-one settings with and without collocated nodes. A mathematical formulation was introduced that captures all the critical characteristics of the problem considered. For solving the problem, an Adaptive Memory Programming method was proposed. Key methodological component was the procedure followed for identifying and selecting elite subroutes of varying length from the reference solutions.

Various computational experiments were conducted to assess the performance of the proposed method and to examine the characteristics of the new problem. On existing benchmark data sets for the one-to-one VRPCD, the AMP performed very well compared to the current state-of-the-art approaches of the literature. On the other hand, computational results on new data sets provided new useful insights. For example, the solution costs increased as the supplier participation ratio increased. The solution costs decreased as the geographic distribution became more clustered for all cases with supplier participation ratio <30%. Significant savings may also be observed if splitting is allowed for the R and RC classes combined with cases where the supplier participation ratio is >30%. Finally, more splits are observed for the cases where supplier and customers are randomly distributed in a geographic region with large supplier-customer connection density.