A hybrid meta-heuristic algorithm for vehicle routing and packing problem with cross-docking

Abstract

Cross-docking is a relatively new logistics strategy that has a great potential to eliminate storage cost and speed up the product flows. This paper considers the vehicle routing and packing problem with cross-docking and presents a mixed integer linear mathematical model. In the model, a set of trucks are used to transport products from suppliers to customers through cross-docking centers. Each supplier and customer node can be visited only once and directly shipping is not allowed from suppliers to customers. Moreover, truck capacities are identified with physical dimensional limits on the contrary of weight or amount of load. The objective of the study is to determine the vehicle routes that minimize the total distance. Due to the complexity of the mathematical model, a hybrid meta-heuristic algorithm (HMA), which integrates tabu search (TS) algorithm within simulated annealing (SA) algorithm, is proposed to solve the problem. Proposed HMA is tested on a well-known benchmark problem data set and compared with the SA and TS solutions. Results show that proposed HMA can produce effective solutions and outperforms the SA and TS especially for the large-sized problems.

Introduction

The efficiency of transportation is one of the most important factors for supply chain management. For this reason, many companies develop various strategies to boost customer satisfaction and bring down the total costs. Cross-docking which almost eliminates the storage costs and speeds up the product flows is one of these strategies. It can be described as the process of moving products from suppliers to customers through cross-docking centers without storing products for a long time in these centers (Ladier and Alpan 2014). At each center, incoming trucks loaded from different suppliers arrives to incoming doors and unloaded to incoming area quickly. These products are sorted and consolidated according to their destinations and then reloaded to outgoing trucks for distribution (Zarandi et al. 2014). This strategy provides different advantages compared with traditional distribution centers: the consolidation of shipments, a shorter delivery lead time, the reduction of costs, improved customer service, fewer overstocks, etc. (Van Belle et al. 2012). As a result of these advantages, cross-docking has become an interesting logistics strategy that can give companies important competitive benefits.

Until now, considerable researches on cross-docking have been studied in the literature and they categorized in many ways. Van Belle et al. (2012) present a comprehensive literature review about cross-docking and classified them based on the problem type: location of cross-docks, cross-docking layout design, cross-docking networks, vehicle routing, dock door assignment, truck scheduling, storage and other issues. Some of these problems are more concerned about long term decisions (strategic or tactical), while others deal with short-term decisions (operational).

The vehicle routing problem for cross-docking (VRPCD) involves the fulfilment of a set of customer orders which are picked up at various supplier locations and delivered to their destinations by a fleet of vehicle after consolidation at a cross-docking center. The objective is to find the best pickup and delivery routes to minimize total transportation cost. As in the extensive variants of the vehicle routing problem, the time windows constraint is widely considered in the literature so that all locations must be visited within their time windows and all pickup and delivery operations must be completed before the end of the planning horizon. Lee et al. (2006) consider the vehicle routing problem for cross-docking. The aim of their study is to find an optimal routing schedule for pickup and delivery operations that minimizes the total transportation cost and fixed costs of the vehicles. The split deliveries are not allowed in their study and it is assumed that all incoming trucks should arrive at the cross-dock simultaneously to prevent waiting for outgoing trucks. An integer mathematical model is presented for the problem and a tabu search (TS) algorithm is proposed as a solution approach. The same problem is taken into account by Liao et al. (2010). The authors propose a new TS algorithm which can achieve better results than the existing TS algorithm in short computational times. Wen et al. (2009) study the VRPCD, which differs from the existing studies by considering time windows. The authors formulate the proposed problem by using mixed integer model. A TS algorithm is used to solve the problem and tested on large scale realistic data set. Their results show that proposed algorithm finds close results to optimum solutions in less than five minutes. Tarantilis (2013) improves the TS proposed by Wen et al. (2009) with adaptive multi-restart strategy, in which the algorithm restarts the search from a new solution once a region has been extensively explored. Computational results demonstrate the efficiency of the algorithm with new improved upper bounds. Another study on VRPCD with time windows constraints is carried out by Vahdani et al. (2012). The authors introduce a hybrid algorithm which incorporates the elements of particle swarm optimization (PSO), simulated annealing (SA) and variable neighborhood search (VNS). The proposed algorithm is compared with TS presented by Lee et al. (2006) and results show that the hybrid algorithm capable to find better solution. Morais et al. (2014) develop a iterated local search heuristic for the VRPCD that includes a constructive heuristics and six local search procedures. This approach is tested on different data sets and compared with the TS proposed by Wen et al. (2009). Computational studies show that iterated local search method finds better solution than the best known solutions for many problems and outperforms the TS. Dondo et al. (2011) study the multi-echelon vehicle routing problem for cross-docking. In their paper, a hybrid strategy combining direct shipping, warehousing and cross-docking is allowed. A monolithic optimization framework based on a mixed integer linear mathematical model is presented for the problem. Dondo and Cerdá (2013, 2014) improve this approach by sweep-based heuristic which is incorporated into the model in order to derive more efficient formulation. Computational results show that sweep heuristic embedded model finds near optimal solution to large scale problems. Hasani-Goodarzi and Tavakkoli-Moghaddam (2012) consider the VRPCD for multi-product with split delivery and pickups. The authors also take into account the traveling times of the vehicles in order to complete all picking up operations in a specified time horizon. The problem is formulated as a mixed integer mathematical model which is tested on small-sized instances. Similarly, Hu et al. (2013) introduce a mathematical model that combines two sub models to optimize the overall travelling time, distance and waiting time at the cross-docking center. Vahdani and Sadigh (2014) investigate the multi-product VRPCD under uncertainty and present a hybrid solution methodologies by combining fuzzy probabilistic programming and stochastic programming. Another study that considers the split delivery condition is carried out by Moghadam et al. (2014). In order to solve the problem SA and a hybrid algorithm combining ant colony optimization (ACO) and SA are proposed. According to the computational studies on different data sets, hybrid algorithm exhibits better performance than SA. A different variant of the VRPCD is studied by Agustina et al. (2014). Their research focuses on the integration of the VRPCD with cross-docking scheduling problem which include product consolidation decisions at the cross-docking center. The authors propose a mixed integer linear program for the problem which obtains the solutions for the medium sized problems in a reasonable time.

Fig. 1

The concept of the vehicle routing problem for cross-docking center

Although the vehicle routing problem provides practical decisions on operational processes for distribution systems, logistics managers usually have to deal with routing and packing problems simultaneously because of the placement of freight, which cannot be stacked on each other, generally affects the route plans in real life applications (Wei et al. 2015). Therefore, there exist several works in literature, which consider the vehicle routing problem with 2-dimensional truck loading constraints and introduce different solution methodology in order to solve large scale problems, such as: Gendreau et al. (2006, 2008), Zachariadis et al. (2009), Leung et al. (2011) and Wei et al. (2011) propose TS based heuristic methods, Leung et al. (2013) propose a SA based heuristic method, Fuellerer et al. (2009) propose an ACO method, Khebbache-Hadji et al. (2013) propose memetic algorithm and recently Wei et al. (2015) propose a VNS algorithm. Motivated by the importance of the 2-dimensional packing operations on routing plans, this study considers the VRPCD with 2-dimensional truck loading constraints, which is called the vehicle routing problem for cross-docking with 2-dimensional truck loading (VRPCD-2D). The VRPCD-2D differs from the existing studies on VRPCD in that truck capacities are identified with the physical dimensional limits on the contrary of weight or amount of load which provides more practical and realistic plan for pickup and delivery operations. To the best of our knowledge, no work has been taken into account the 2-dimensional truck loading constraints for VRPCD though it is a practical problem in real-world transportation and logistics industries.

In this study, the VRPCD-2D is formulated as a mixed integer mathematical model and a hybrid meta-heuristic algorithm (HMA), which integrates TS within SA, is proposed in order to solve the problem. The hybridization of meta-heuristic algorithms are proposed by many researchers in order to solve various complex problems. Nearchou (2004) presents a HMA to solve flow-shop scheduling problem. Likewise, Dong and Wang (2012), Jolai et al. (2012), Azadeh et al. (2013) and Ramezani et al. (2015) consider the scheduling problems and solves their problems by using a HMA. Hamta et al. (2014) develop a hybrid framework of the VNS with TS to solve scheduling and line balancing problem. Poorzahedy and Rouhani (2007) compare the performance of different type hybrid algorithms for network design problem. Leno et al. (2015) propose an elitist strategy based hybrid genetic algorithm that uses SA as local search mechanism. Although, there exist numerous hybrid algorithm in literature, the hybrid structure of the SA and TS is one of the most popular HMA used to solve several problems: e.g. used by Osman and Christofides (1994) for capacitated clustering problems, by Lin and Ying (2009) for non-permutation flowshop scheduling problems, by Lin et al. (2012) for vehicle routing problem with time windows, by Katsigiannis et al. (2012) for optimal sizing of autonomous power systems with renewables, by Arıkan and Erol (2012) for part selection and machine loading problems in flexible manufacturing systems, by Kaviani et al. (2014) for quadratic assignment problem, etc. In this study, the proposed HMA of SA and TS is promoted with an efficient local search method and 2-dimensional packing heuristics in order to obtain efficient solutions. The performance of the HMA is tested on various benchmark instances derived from vehicle routing problem test problems and the results are compared with the solutions of the SA and TS. A remainder of this paper is organized as following sections: “Problem definition and model formulation”, “Proposed algorithm”, “Computational results” and “Conclusions”.

Problem definition and model formulation

In this paper, VRPCD-2D is defined as the problem of transporting products from suppliers to customer locations through cross-docking center in order to satisfy a set of customer demand. The considered problem is described in Fig. 1, where the products from the suppliers are picked up by incoming trucks, consolidated at the cross-docking center, and immediately delivered to customers by outgoing trucks. The incoming trucks start their tour from cross-docking center, serve to the suppliers in a specified time windows and return to the cross-docking center. After all incoming trucks complete their routes products are loaded to outgoing trucks and delivered to their destinations. As in the incoming operations, customer nodes are served in a specified time windows. Each product of suppliers is loaded into the incoming and outgoing trucks by regarding the 2-dimensional truck loading constraints. The demand of a customer is defined by a set of rectangular items with given width and length. All the products belonging to one customer/supplier must be assigned to the same pickup/delivery route. The objective of this study is to find the best route plan for incoming and outgoing trucks in order to minimize total transportation cost. VRPCD-2D is considered with the following assumptions:

• Each vehicle starts and terminates its route at the cross-docking center.

• Split deliveries are not allowed and each supplier and customer node must be visited by only one vehicle.

• Directly shipping from suppliers to customers is not allowed.

• Vehicles can serve more than one supplier or customer node and each route starts and ends at the cross-docking center.

• Each vehicle can be used for pickup or delivery operations.

• The pickup and delivery operations must be carried out in supplier’s and customer’s time window interval. Also, the whole process must be completed within the planning horizon.

• Vehicles are considered homogeneous and capacities are identified with physical dimensional limits on the contrary of weight or amount of load.

• Products are considered as rectangular shapes with different sizes.

• Products can be loaded into the incoming or outgoing trucks with unrestricted order.

As mentioned in the literature review, the VRPCD is considered by several studies with different assumptions. However, the VRPCD with 2-dimensional truck loading plans have not been taken into account by any research. Therefore, the mathematical model of the VRPCD-2D is newly formed on the basis of assumptions described above by adapting the 2-dimensional pallet packing constraints proposed by Chen et al. (1991). The proposed mathematical model is formulated as follows.

Parameters and notations

S:

Set of suppliers.

D:

Set of destinations.

N:

Set of all locations: $\{0\}\cup S\cup D$, where 0 denotes the cross-docking center.

PR:

Set of products.

K:

Set of vehicles.

$c_{ij}$:

Transportation cost from node i to node j; $\forall i,j\in N$.

$t_{ij}$:

Travelling time from node i to node $j; \forall i,j\in N$.

$e_i$:

Time window lower bound for node $i; \forall i\in N$.

$l_i$:

Time window upper bound for node $i; \forall i\in N$.

$s_i$:

Service processing time for node $i; \forall i\in N$.

W:

Width of the trucks.

L:

Length of the trucks.

$dem_m$:

Supplier label of product $m; \forall m\in PR$.

$dem_{m}^{\prime }$:

Destination label of product $m; \forall m\in PR$.

$q_m$:

Width of product m; $\forall m\in PR$.

$p_m$:

Length of product m; $\forall m\in PR$.

M:

Big number.

Decision variables

$z_{ijk}$:

1 if vehicle k travels from node i to node j, and 0 otherwise; $\forall i,j\in N, \forall k\in K$.

$w_{i}$:

Service start time at node $i; \forall i\in N$.

$w\_{c}$:

Distribution starting time for cross-docking center which denotes the end of the picking up procedures.

$x_{m}$:

x coordinate of product m in an incoming truck; $\forall m\in PR$.

$x_{m}^{\prime }$:

x coordinate of product m in an outgoing truck; $\forall m\in PR$.

$y_{m}$:

y coordinate of product m in an incoming truck; $\forall m\in PR$.

$y_{m}^{\prime }$:

y coordinate of product m in an outgoing truck; $\forall m\in PR$.

$\alpha _{mn}, \beta _{mn},$$\gamma _{mn}, \delta _{mn}$:

1 if product m is on the left, right, bottom and top side of product n in a same incoming truck, respectively, and 0 otherwise; $\forall m,n\in PR$.

$\alpha _{mn}^{\prime }, \beta _{mn}^{\prime },$$\gamma _{mn}^{\prime }, \delta _{mn}^{\prime }$:

1 if product m is on the left, right, bottom and top side of product n in a same outgoing truck, respectively, and 0 otherwise; $\forall m,n\in PR$.

Using the parameters, notations and decision variables described above, the VRPCD-2D is formulated as:

$$\begin{aligned}&\hbox {Min z}=\sum \limits _{i\in N} \sum \limits _{j\in N} \sum \limits _{k\in K} c_{ ij } z_{ijk} \end{aligned}$$

(1)

$$\begin{aligned}&\hbox {Subject to}\nonumber \\&{\mathop {\sum }\limits _{\begin{array}{c} j\in N\backslash D\\ i\ne j \end{array}}}\sum \limits _{k\in K} z_{ijk} =1 \quad \forall i\in S \end{aligned}$$

(2)

$$\begin{aligned}&{\mathop {\sum }\limits _{\begin{array}{c} i\in N\backslash D\\ i\ne j \end{array}}}\sum \limits _{k\in K} z_{ijk} =1 \quad \forall j\in S \end{aligned}$$

(3)

$$\begin{aligned}&{\mathop {\sum }\limits _{\begin{array}{c} j\in N\backslash S \\ i\ne j \end{array}}}\sum \limits _{k\in K} z_{ijk} =1 \quad \forall i\in D \end{aligned}$$

(4)

$$\begin{aligned}&{\mathop {\sum }\limits _{\begin{array}{c} i\in N\backslash S \\ i\ne j \end{array}}}\sum \limits _{k\in K} z_{ijk} =1 \quad \forall j\in D \end{aligned}$$

(5)

$$\begin{aligned}&\sum \limits _{j\in N\backslash \{0\}} z_{0jk} =1 \quad \forall k\in K\end{aligned}$$

(6)

$$\begin{aligned}&\sum \limits _{i\in N\backslash \{0\}} z_{i0k} =1\quad \forall k\in K \end{aligned}$$

(7)

$$\begin{aligned}&{\mathop {\sum }\limits _{\begin{array}{c} i\in N \\ i\ne j \end{array}}} z_{ijk} ={\mathop {\sum }\limits _{\begin{array}{c} i\in N \\ i\ne j \end{array}}} z_{jik} \quad \forall j\in N\backslash \{0\},\quad \forall k\in K \end{aligned}$$

(8)

$$\begin{aligned}&w_{i}+s_{i} +t_{ ij } \le w_{j}+M\left( 1-\sum \limits _{k\in K}z_{ijk}\right) \quad \nonumber \\&\quad \forall i\in N\backslash D, \quad \forall j\in S, \quad i\ne j \end{aligned}$$

(9)

$$\begin{aligned}&w_{i}+s_{i} +t_{i0} \le w\_c+M\left( 1-z_{i0k}\right) \nonumber \\&\quad \forall i\in S, \quad \forall k\in K \end{aligned}$$

(10)

$$\begin{aligned}&w\_c+s_0 +t_{0j}\le w_j +M(1-z_{0jk})\nonumber \\&\quad \forall j\in D, \quad \forall k\in K \end{aligned}$$

(11)

$$\begin{aligned}&w_{i}+s_i +t_{ ij } \le w_j +M\left( 1-\sum \limits _{k\in K}z_{ijk} \right) \nonumber \\&\quad \forall i,j\in D,\quad i\ne j \end{aligned}$$

(12)

$$\begin{aligned}&w_i +s_i +t_{i0} \le l_0 +M\left( 1-\sum \limits _{k\in K}z_{i0k}\right) \quad \forall i\in D \end{aligned}$$

(13)

$$\begin{aligned}&e_{i}\le w_i \le l_{i} \quad \forall i\in N\backslash \{0\} \end{aligned}$$

(14)

$$\begin{aligned}&x_{m}+q_m \le x_{n}+M(1-\alpha _{ mn })\nonumber \\&\quad \forall m,n\in PR , \quad m<n \end{aligned}$$

(15)

$$\begin{aligned}&x_{n} +q_{n} \le x_{m} +M(1-\beta _{ mn })\nonumber \\&\quad \forall m,n\in PR ,\quad m<n \end{aligned}$$

(16)

$$\begin{aligned}&y_{m} +p_{m} \le y_{n} +M(1-\gamma _{ mn })\nonumber \\&\quad \forall m,n\in PR ,\quad m<n \end{aligned}$$

(17)

$$\begin{aligned}&y_{n} +p_{n} \le y_{m} +M(1-\delta _{ mn })\nonumber \\&\quad \forall m,n\in PR ,\quad m<n \end{aligned}$$

(18)

$$\begin{aligned}&\alpha _{ mn } +\beta _{ mn } +\gamma _{ mn } +\delta _{ mn } +1\ge \sum \limits _{j\in N\backslash D} \left( z_{{ dem }_m jk}+z_{{ dem }_n jk} \right) \nonumber \\&\quad \forall k\in K,\quad \forall m,n\in PR ,\quad m<n \end{aligned}$$

(19)

$$\begin{aligned}&x_{m} +q_{m} \le W\quad \forall m\in PR \end{aligned}$$

(20)

$$\begin{aligned}&y_{m} +p_{m} \le L \quad \forall m\in PR \end{aligned}$$

(21)

$$\begin{aligned}&x_{m}^{\prime }+q_m \le x_{n}^{\prime }+M\left( 1-\alpha _{ mn }^{\prime }\right) \nonumber \\&\quad \forall m,n\in PR ,\quad m<n \end{aligned}$$

(22)

$$\begin{aligned}&x_n^{\prime }+q_n \le x_m^{\prime } +M\left( 1-\beta _{ mn }^{\prime }\right) \nonumber \\&\quad \forall m,n\in PR ,\quad m<n \end{aligned}$$

(23)

$$\begin{aligned}&y_m^{\prime }+p_m \le y_n^{\prime }+M\left( 1-\gamma _{ mn }^{\prime }\right) \nonumber \\&\quad \forall m,n\in PR ,\quad m<n \end{aligned}$$

(24)

$$\begin{aligned}&y_n^{\prime }+p_n \le y_m^{\prime }+M\left( 1-\delta _{ mn }^{\prime }\right) \nonumber \\&\quad \forall m,n\in PR ,\quad m<n \end{aligned}$$

(25)

$$\begin{aligned}&\alpha _{ mn }^{\prime }+\beta _{ mn }^{\prime }+\gamma _{ mn }^{\prime }+\delta _{ mn }^{\prime } +1\ge \sum \limits _{j\in N\backslash S} \left( z_{{ dem }_m^{\prime } jk} +z_{{ dem }_n^{\prime } jk}\right) \nonumber \\&\quad \forall k\in K, \quad \forall m,n\in PR ,\quad m<n \end{aligned}$$

(26)

$$\begin{aligned}&x_m^{\prime } +q_m \le W\quad \forall m\in PR \end{aligned}$$

(27)

$$\begin{aligned}&y_m^{\prime } +p_m \le L\quad \forall m\in PR \end{aligned}$$

(28)

The objective function (1) minimizes the total transportation costs of the incoming and outgoing trucks. Constraints (2) and (3) ensures that each supplier node can be serviced by only one vehicle and similarly constraints (4) and (5) provide this condition for customer nodes. Constraints (6) and (7) ensure that all routes leave from the cross-docking center and return to the cross-docking center at the end of the service. Constraint (8) guarantees that a vehicle leaves from the same node it has entered. Constraints (9)–(13) provide the feasibility of the schedule in accordance with the time considerations. Constraint (14) guarantees that each supplier and customer node is serviced within the time window. Constraints (15)–(18) and (22)–(25) assure that products do not overlap each other and these constraints are considered only if a pair of products is in the same incoming or outgoing truck. This is taken care of in constraint (19) for incoming trucks and constraint (26) for outgoing trucks. Constraints (20), (21), (27) and (28) provide that a product loaded in an incoming or outgoing truck, cannot exceed the truck’s physical dimensions.

Proposed algorithm

This section introduces main components of the proposed HMA for VRPCD-2D, which are two well-known meta-heuristics, SA and TS, and also introduces the packing heuristics used for the 2-dimensional loading procedures.

Simulated annealing algorithm

SA is a stochastic method for solving combinatorial problems proposed by Kirkpatrick et al. (1983). The SA methodology draws its inspiration from annealing process in metallurgy. It works by emulating the physical process so that a solid is heated to a high temperature and step by step cooled to low it to crystallize.

SA uses a stochastic approach to guide the search. In addition to accepting better solutions, SA allows the search to proceed to a neighboring state even if the move causes the value of the objective function to become worse. SA processes the local search in the following way. If a move to neighbor $\hbox {X}'$ in neighborhood ensures improvement in objective value, or leaves it unchanged, then the move is always accepted. More precisely, the solution $\hbox {X}'$ is accepted as the new solution if $\Delta \le 0$, where $\Delta =(\text {f}(\text {X}')-\text {f}(\text {X}))$ and $\hbox {f}(\hbox {X})$ is the value of objective function. Moves, which increase the objective function means that $\Delta >0$, are accepted according to a probability function $\hbox {e}^{(-\Delta /\mathrm{T})}>\theta$, where T is the parameter of temperature, and $\uptheta$ is a random number between [0, 1]. The value of T varies from a relatively large number to a small value close to zero, which is often controlled by linear equations for reducing temperature linearly. The stopping criterion of the SA is based on the probability that a move from a local minimum to a neighbor with the lowest score is accepted. If that probability is low compared to the selection probability the algorithm is stopped in that approach (Otten and Van Ginneken 1988). However, there have been various stopping criteria, which are developed on the basis of considered problem. The pseudo code of the SA algorithm is shown in Fig. 2.

Fig. 2

Pseudo code of the SA algorithm

Tabu search algorithm

TS was introduced by Fred Glover in 1986 as an iterative meta-heuristic algorithm that guides a local search procedure to explore the solution space beyond local optimality (Glover 1989, 1990). TS algorithm is different from the SA algorithm in that the tabu search includes a memory mechanism that prevents the search from cycling back to previously visited solutions. The memory mechanism which is called as tabu list maintains the search history by keeping either some of the moves or just their attributes, and prevents the reversing these moves for a given number of iterations. Data structure of the tabu list is necessary to ensure the proper management of the tabu restriction (Landrieu et al. 2001). On the other hand, this restriction can be ignored if the attempted move leads to find a new best solution for the algorithm. This procedure is defined as aspiration criterion, which allows for exception from tabu list, if any move leads to promising solution (Armentano and Yamashita 2000; Geyik and Cedimoglu 2004). The pseudo code of the TS algorithm is shown in Fig. 3.

Fig. 3

Pseudo code of the TS algorithm

Hybrid meta-heuristic algorithm

The proposed HMA for the VRPCD-2D is based on the integration of TS within the SA. The HMA takes the advantages of the SA and TS including the stochastic feature to escape local optima and tabu list to avoid cycling. The detail of the HMA is presented in the following subsections.

Presentation and initial solution

An integer string of length $(N+K)$, which provides an incentive to return to the original route information after decoding, is used to present a solution for the algorithm (Tan et al. 2001). An example for presentation of three routes is as follows, where the zeros represent the bounds of the routes:

String Code:

$0 \rightarrow 7 \rightarrow 3 \rightarrow 8 \rightarrow 10 \rightarrow 1 \rightarrow 0 \rightarrow 2 \rightarrow 9 \rightarrow 0 \rightarrow 5 \rightarrow 4 \rightarrow 6 \rightarrow 0$

Route No. 1:

$0 \rightarrow 7 \rightarrow 3 \rightarrow 8 \rightarrow 10 \rightarrow 1 \rightarrow 0$

Route No. 2:

$0 \rightarrow 2 \rightarrow 9 \rightarrow 0$

Route No. 3:

$0 \rightarrow 5 \rightarrow 4 \rightarrow 6 \rightarrow 0$

In order to obtain a feasible initial solution for the VRPCD-2D, an insertion based procedure, which primarily takes into account the free vehicle loading area, is applied for the HMA. At first |K| empty routes are generated and non-occupied surface area of the vehicles $F_{k}(k\in K)$ is set to the $W\times L$. Locations are sorted by the value of $A_{i} (\forall i\in S\cup D)$, where $A_{i}$ is the total area of products which have to pick up or drop off at location i. Then, each location i from the sorted sequence is inserted into the routes one by one by checking the 2-dimensional loading and time windows constraints. In this case, the location type is another factor to choose appropriate vehicle, such that a supplier location can be inserted into the route if the route is empty or the route contains another supplier location. Likewise, a customer location can be inserted into the route if the route is empty or the route contains another customer location. As a result of feasibility checking process, the initial solution procedure progress with respect to following three conditions:

• If the location i can be inserted feasibly into the only one route, then it is assigned to appropriate route.

• If location i can be inserted feasibly into the more than one route, then it is assigned to route that minimize $F_k -A_i$.

• If the location i cannot be inserted feasibly into the any route, then the sequence of locations is updated by exchanging two randomly selected locations and the construction procedure restarts with the new location sequence.

This above process is performed until all the locations that can be feasibly inserted into any route.

Neighborhood generation

In order to explore the search space, HMA employs the $\uplambda$-interchange local search, which was first introduced by Osman and Christofides (1994). This methods is based on the $\uplambda$ number, where the $\uplambda$ is the maximum number of locations that can be interchanged between routes, and includes both shift and exchange procedures. The locations that are interchanged can be selected randomly or systematically. For example, consider $\uplambda =2$, which means that up to two locations may be interchanged between routes with the following operators: (0, 1), (1, 0), (1, 1), (0, 2), (2, 0), (1, 2), (2, 1) and (2, 2).

In this study, $\uplambda$-interchange method is adapted with TS algorithm by using the tabu list property, in which the memory remembers the tabu moves for a certain number of iterations and does not allow using of any move until it leaves the tabu list. In addition to this prohibition, $\uplambda$-interchange method ignores the any move that leads to infeasible solution for a route, which avoids the redundant computations for the HMA. As a consequence, any move of a location j can be inserted between location i and location $i+1$ into the route k if the following conditions are met respectively;

• If the route is empty or both of the location i and location j are supplier or customer locations.

• $e_i +s_i +t_{ ij } \le l_{j}$.

• $e_j +s_j +t_{j(i+1)} \le l_{(i+1)}$.

• If the total area of products at location i is less than the non-occupied surface area of the vehicle k.

• If the all products of location i can be loaded into the vehicle k successfully.

The sequence of the checking list is arranged according to the computational complexity of the examination and a move is rejected when it failures for a condition. At the end of the checking feasibility, the fitness function value of a new route is determined by using the distance between the locations.

For the computational studies, the proposed $\uplambda$-interchange method is applied for $\uplambda =1$ and $\uplambda =2$ and best improvement strategy is implemented in selecting a new neighbor.

Packing heuristic

In order to determine whether all the products required by the locations can be feasibly loaded into the vehicles, five packing heuristics $Heur_{h}(h=1,\ldots , 5)$ developed by Zachariadis et al. (2009) are used in HMA. Each of the heuristics, which have different position selection criteria, loads a product into the vehicle from the feasible position list $( pos \_ list )$ as follows:

${\textit{Heur}}_{1}$:

Bottom Left Fill (W-axis) selects the position from the $pos \_ list$, which has the minimum W-axis coordinate, breaking ties by minimum L-axis coordinate.

${\textit{Heur}}_{2}$:

Bottom Left Fill (L-axis) selects the position from the $pos \_ list$, which has the minimum L-axis coordinate, breaking ties by minimum W-axis coordinate.

${\textit{Heur}}_{3}$:

Max Touching PerimeterHeuristic selects the position from the $pos \_ list$, which has the maximum touching perimeter value, which is evaluated as the sum of common edges of the inserted product with the edges of the already inserted products, and the edges of the loading surface of the vehicle.

${\textit{Heur}}_{4}$:

Max Touching Perimeter No WallsHeuristic selects the position from the $pos \_ list$, which has the maximum touching perimeter value, which is evaluated as the sum of common edges of the inserted product with the edges of the already inserted products. Distinctly from the Max Touching PerimeterHeuristic, the common edges of the inserted product with the loading surface are not taken into account for this heuristic.

${\textit{Heur}}_{5}$:

Min AreaHeuristic selects the position from the $pos \_ list$, which has the minimum rectangle surface corresponding to position.

As mentioned in the problem definition part, it is assumed that the products can be loaded into the vehicles in unrestricted order. Thus, the sequence of the locations in a route does not affect the loading feasibility. When the packing procedure is carried out for a route, first the products belongs to the locations are sorted by the area in decreasing order. Then the five packing heuristics are called in sequence. If a feasible loading plan is found by a heuristic method, the packing procedure stops and returns the result as success. On the other hand, if the current heuristic fails to find a feasible solution, then the next heuristic is called. At the end of the fifth heuristic if a feasible solution cannot be found then the packing procedure returns the result as failure.

Because of the packing procedure is very time consuming, a memory structure is used to speed up the loading check computations, which avoids duplicate examinations. This structure is employed to store the loading feasibility information of a route, and when a route is examined, this information can be easily obtained if the route has been generated previously. Otherwise, the packing procedure is applied for the route and the new information is recorded to memory in a string form. The string form of the route includes the locations excepting the cross-docking center and loading information which are split with the use of comma:e.g. the route 0–1–2–3–4–5–6–7–8–9–10–0 and its loading information is success is coded as “1, 2, 3, 4, 5, 6, 7, 8, 9, 10, success”. To reduce the searching process time for retrieving the stored information of a route, this memory structure is designed in the form of a three dimensional array. Each dimension of the array indicates a key factor of a route: the first location of the route, the number of locations in the route and the occupied area of the vehicle in integer form. Instead of a single array, the proposed key factors prevent the unnecessary searches. Figure 4 shows the pseudo-code of the memory-structure-adapted loading check procedure.

Fig. 4

Pseudo code of the loading check procedure

Table 1 Characteristics of the generated problems

Table 2 Details of the problems

Stopping criteria

The maximum iteration number is used as primary termination criteria for the proposed algorithm and the temperature is reduced progressively by the cooling parameter at each iteration. Additionally, the algorithm stops if there is no improvement in the objective function during the specified number of iterations. Based on the described statements above, the pseudo code of the proposed HMA is shown in Fig. 5.

Fig. 5

Pseudo code of the HMA

Computational results

The proposed HMA developed in the Visual Basic programming language, and numerical experiments are performed on 2.20-GHz Intel Core i7 processor with 8-GB memory. To evaluate the performance of the HMA, a well-known benchmark problem data set, which was developed by Solomon (1987) to test the vehicle routing problem with time windows, is used and adapted to VRPCD-2D. Solomon’s benchmark problems consist of totally 100 randomly located demand nodes and a depot node. Also, smaller problems are regarded by just considering the first 25 and 50 nodes. For the VRPCD-2D, the locations of the instances are divided into two groups: supplier locations and customer locations, in which the time windows of the customer locations are adjusted to further time period while the time windows of supplier locations remained as the same. Moreover, because of the customers should request the products from more than one supplier location and adapt the instances to the packing problem, the demand amount of the customers are regenerated randomly with 2-dimensional physical data. The problems formed for the VRPCD-2D are described with the supplier and customer locations: e.g. the problem “R101_2D_5_20” considers the first 25 demand node of the R101 problem of the Solomon’s data set where the first 5 demand nodes are represented as supplier locations while the other 20 demand nodes are customer locations.

The computational studies consist of two parts. First, HMA, SA and TS are performed on 24 different small-sized instances and the results of the algorithms are compared with the CPLEX. Then, each algorithm is practiced on more complex problems include 25, 50 and 100 locations, respectively. In this part, the performance of the HMA is demonstrated by comparing the results with SA and TS solutions. Table 1 represents the principle data of the problems used to generate instances with their intervals and Table 2 reports the some details of the problems used in the second part of the computational studies which identify the problem size. Table 2 also presents the best integer solution of the first 12 problems with their optimality gaps obtained by CPLEX 12.5 with 5 h time limitation. For the other problems which include 50 or 100 locations, the CPLEX could not reach any integer solution in specified time horizon. For each part of the computational studies for heuristic algorithms, the maximum iteration number is set to the 1000 iterations and each run is terminated if the algorithm does not provide a new best solution during the 100 iteration. Moreover, the algorithms are executed 10 times for each instance and the results are identified with best and average result of the runs.

For the first part of the computational studies, Table 3 shows the characteristics of the problems and the result of CPLEX solutions with best bound solution, best integer solution, number of vehicles, optimality gap of the solution and CPU time of the computations. On the other hand, the results of the HMA, SA and TS are presented in Table 4 with best solutions and average solution. Also, the table presents the gap between the result of heuristic methods and results of best integer CPLEX solution by using the following formulation;

$$\begin{aligned} \% \textit{Gap}_{C}=\frac{\textit{CPLEX }\;\textit{Solution}-\textit{Heuristic}\;\textit{Solution}}{\textit{CPLEX}\; \textit{Solution}}\times 100\,\% \end{aligned}$$

It can be seen from the Table 3 that, an optimal solution can be found for nine problems within the specified time limitation. For the other problems, CPLEX could find the results with the optimality gap range 0.03 and 24.20 %. When the best results of the heuristic methods are compared with the best integer solution of CPLEX, HMA finds 1.25 % and SA finds 1.24 % better solution on average. However, the average $\% {\textit{Gap}}_{C}$ of the TS for best results is less than zero. Similarly, the average solutions of the HMA and SA are better than the best integer solution of the CPLEX while the average $\% {\textit{Gap}}_{C}$ of the TS is less than zero for most of the instances.

Table 3 CPLEX solution for the small-sized instances

Table 4 Comparisons of the algorithms with CPLEX solutions

For the second part of the computational studies, Tables 5, 6 and 7, which are classified according to the number of locations, show the details of the results obtained by HMA, SA and TS. Each table compares the HMA solutions with SA and TS solutions with respect to best and average solution by using the following formulation;

$$\begin{aligned}&\% \textit{Gap}_{\textit{Heuristic}\;\textit{Method}}\\&\quad =\frac{\textit{Heuristic}\;\textit{Method}\;\textit{Solution}- \textit{HMA}\;\textit{Solution}}{\textit{Heuristic}\;\textit{Method}\;\textit{Solution}}\times 100\,\% \end{aligned}$$

where the positive variables pointed out with bold characters indicate that better solution is obtained by the HMA.

Table 5 Computational results for 25 locations

Table 6 Computational results for 50 locations

Table 7 Computational results for 100 locations

The results for 25 locations, which are reported in Table 5, show that proposed HMA could obtain the result with lower total distance for several problems with respect to best and average solutions. When the gaps are compared on the basis of best results, HMA provides 0.45 and 2.42 % better solution according to the SA and TS, respectively. Similarly, when the average solutions are considered the average gaps between the HMA and SA is 1.16 %, and between the HMA and TS is 3.17. In terms of the computational times, TS could reach the solutions in shorter times in general with respect to the HMA and SA.

For the 50 locations, the results are presented in Table 6. Regarding to the best solutions, HMA could obtain the best result for eight problems. For this case, there is only one problem that TS could obtain better result than the HMA. Considering the average results, HMA exhibits superior performance and finds better results for all problems except one problem. Additionally, when the results are compared according to the gaps of the best results, the average gap between the HMA and SA is 0.33 % and the average gap between the HMA and TS is 0.44 %. Moreover, the gaps rises up when the average solutions are considered, where the average gap between the HMA and SA is 1.00 % and the average gap between the HMA and TS is 1.45 %.

Finally, for the large sized problems, which consist of 100 locations, the results are shown in Table 7. The gaps between HMA and other two heuristics are significantly different, where the average gap between HMA and SA is 2.45 % and the average gap between HMA and TS is 3.24 %, insomuch that this value exceeds 5.00 % for some of the instances. Additionally, HMA could obtain best result for nine problems and obtain better average solution for all problems. On the other hand, SA exhibits better performance for 3 problems according to the best solution. On the basis of CPU times, each algorithm represents similar performance.

In addition to comparisons of the algorithms with respect to best and average solution, a statistical analysis for solutions are conducted by applying paired-t test at significance level $\alpha =0.05$ to reveal whether there exists significant differences between HMA and other two heuristics in terms of the solution quality. Therefore, the null hypothesis is formed as $H_0\,{:}\,\mu _{ HMA } -\mu _{ CHA }=0$ and two sided alternative hypothesis as $H_1\,{:}\,\mu _{ HMA }-\mu _{ CHA } \ne 0$, where the symbols $\mu _{ HMA }$ and $\mu _{ CMA }$ represent the population mean for HMA and the other compared meta-heuristic algorithm, respectively. Table 8 presents the result of the paired-t test for the algorithms which are separated according to the location number of the problems. It can be seen from table that proposed HMA is significantly different from the TS for each problem set and also it can be concluded that HMA is significantly different from the SA except one case which is formed for the problems consist of 25 locations.

Table 8 Results of the paired-t test

Conclusions

In this paper, the vehicle routing problem with the 2-dimensional truck loading constraints is studied for the cross-docking center in order to minimize total transportation cost. The problem is formulated as a mixed integer mathematical model and due to the complexity of the problem, a HMA is proposed as a solution approach for the problem. The HMA combine the SA and TS algorithm, which are the two well-known powerful meta-heuristic algorithms to solve combinatorial problems. The HMA takes the advantages of SA and TS including the stochastics feature to escape from local optima and tabu list to avoid cycling. Moreover, five packing heuristic methods are integrated with the algorithm to check 2-dimensional loading feasibility. The proposed algorithm is tested with several instances which are obtained from Solomon’s benchmark data sets and compared with the SA and TS methods. First, the algorithms are performed for small sized instances and compared based on the best integer solution of CPLEX. Then, the performance of the algorithms are analyzed on more complex problems. In addition to the comparisons of the algorithms with respect to best and average solution, a statistical analysis for solutions are conducted by applying paired-t test whether there exists significant differences between HMA and other two heuristics in terms of the solution quality. The computational results show that the proposed HMA exhibits superior performance and outperforms the SA and TS method with respect to the solution quality. On the other hand, the average computational times of the algorithms are significantly different. As a consequence, this study contributes to the literature by considering the 2-dimensional vehicle loading operations for VRPCD. Distinctly from the existing studies on VRPCD, the truck capacities are identified with the physical dimensional limits on the contrary of weight or amount of load in VRPCD-2D, which provides more practical and realistic plan for pickup and delivery operations. Also an efficient solution methodology is introduced to solve VPRCD-2D, which is expressly better than the SA and TS. For the future work on this study, the HMA can be improved by considering more than one cross-docking center, which allows splitting the customer request in network. Also, the HMA can be built up to solve VRPCD with 3-dimensional loading plans or VRPCD-2D with heterogeneous fleet. Another research can be done by extending the VRPCD-2D with truck-door assignment plans in cross-docking center, which directly affects the distribution starting time of the vehicles.