A robust approach to multiple vehicle location-routing problems with time windows for optimization of cross-docking under uncertainty

3.1 Determining cross-docks location (phase one)

The first phase of the proposed model aims to minimize three types of costs. The first type of costs is fixed costs regarding operations of open cross-docks. The second type is costs to transport units of multiple products from the suppliers (i.e., pickup nodes) to cross-docks and from cross-docks to the retailers (i.e., delivery nodes). The third type is the cost of holding inventories at cross-docks. Limitations of the first phase are as follows. Pickup and delivery are provided and fulfilled by respecting related time windows. All demands are met by the sufficient inventory of each product. In addition, there are limitations on the number of potential cross-docks and capacity restrictions for multiple cross-docks in the pickup and delivery processes. It is pointed out that cost per unit of distance is assumed to be equal to one in the presented model.

3.2 Vehicle route scheduling with multiple cross-docks (phase two)

The objective of the second phase is to obtain the best route and the arrival time of each vehicle to minimize transportation costs associated with moving multiple products in the pickup and delivery processes separately. Limitations of the second phase are as follows. Each supplier or retailer can only be picked up or delivered once. The total quantity of pickup should equal the quantity to be delivered. The load on the pickup route and on the delivery route for each vehicle cannot exceed the capacity of the vehicle. Maximum working time of each vehicle is also considered in pickup and delivery processes. The considered problem in the second phase is depicted in Fig. 1, where it is assumed that all the vehicles are located in the multiple cross-docks and split deliveries are not allowed. The pickup vehicles start from the multiple cross-docks and arrive at the same cross-dock concurrently. The delivery vehicles move to the retailers and then return to the same cross-dock after completing their tours.

In light of the presented two-phase model, to provide the most suitable decision via strategic and executional viewpoints, all contributing issues consisting of the location of multiple cross-docks as well as vehicle routing scheduling with the cross-docking are integrated concurrently in the proposed mathematical model under uncertainty. In addition, the parameters values of the phase two are employed by these values determined in the phase one because of close connections between two phases of the proposed model. This study introduces a new two-phase MILP model for the cross-docking distribution network in logistics systems that can support both important decisions in strategic and executional point of views. The proposed model is able to provide the location of multiple products multiple cross-docks under uncertainty, unlike the previous studies with deterministic models, and to determine vehicle routing scheduling with multiple cross-docking under uncertainty, unlike the previous studies with a single cross-dock based on deterministic approach. In addition, the robust counterpart of the proposed MILP model is developed to cope with the uncertainty in the design parameters, such as holding and transportation costs, the capacity of each vehicle and time of each vehicle (route) in the pickup and delivery processes.

4.1 Multiple cross-docks location model (phase one)

In terms of the above notations, cross-docks location problem in the first phase of the proposed model via strategic viewpoint can be formulated as follows: Min Z 1 = ∑ k = 1 c F k x k + ∑ k = 1 c ∑ p = 1 q ∑ t = T min T max HC k , p S p , k , t + ∑ p = 1 q ∑ i ′ = 1 m ∑ k = 1 c ∑ t = T min T max X p , k , t i ′ Dist i ′ , k C i ′ k + ∑ p = 1 q ∑ i = 1 n ∑ k = 1 c ∑ t = T min T max X p , k , t i Dist i , k C ik(1) S . t . : ∑ k = 1 c ∑ t = T min T S d - 1 X p , k , t i ′ = 0 ∀ i ′ , p(2) ∑ k = 1 c ∑ t = TS d TE d X p , k , t i ′ ≤ 1 ∀ i ′ , p(3) ∑ k = 1 c ∑ TE d + 1 T max X p , k , t i ′ = 0 ∀ i ′ , p(4) ∑ k = 1 c ∑ t = T min TS p - 1 X p , k , t i = 0 ∀ i , p(5) ∑ k = 1 c ∑ t = TS p TE p X p , k , t i = 1 ∀ i , p , and Q i , p = 1(6) ∑ k = 1 c ∑ t = TE p + 1 T max X p , k , t i = 0 ∀ p , i(7) S p , k , t ≥ 0 ∀ p , k , and T min ≤ t ≤ T max(8) ∑ p = 1 q S p , k , t ≤ cap k ∀ k , and T min ≤ t ≤ T max(9) s p , k , T min - 1 = 0 ∀ p , k(10) s p , k , t = s p , k , t - 1 + ∑ i ′ = 1 m X p , k , t i ′ Q i ′ , p Am i ′ , p - ∑ i = 1 n X p , k , t i Q i , p Am i , p ∀ p , k , and T min ≤ t ≤ T max(11) ∑ k = 1 C ∑ i ′ = 1 m X p , k , t i ′ Q i ′ , p Am i ′ , p - ∑ k = 1 C ∑ i = 1 n X p , k , t i Q i , p Am i , p ≥ 0 ∀ p , and T min ≤ t ≤ T max(12) X p , k , t i ≤ x k ∀ i , p , k , and T min ≤ t ≤ T max(13) X p , k , t i ′ ≤ x k ∀ i ′ , p , k , and T min ≤ t ≤ T max(14) ∑ k = 1 c x k ≤ R(15) ∑ k = 1 c F k x k ≤ TC(16) X p , k , t i ′ , X p , k , t i , x k ∈ { 0 , 1 }(17)

Objective function (1) regards the total costs by minimizing costs of holding inventories at cross-docks and costs of transportation, namely costs of transportation from suppliers to cross-docks and then from cross-docks to customers. Constraints (2), (3) and (4) ensure that each delivery, if necessary, is fulfilled within its specified time window and beyond that range, it takes the value of zero. Constraints (5), (6) and (7) guarantee the time window restriction for pickups. Constraint (8) guarantees that the flow of product p at each cross-dock is constantly non-negative. Constraint (9) describes the potential capacity of cross-docks. Constraint (10) sets a zero initial inventory for each product at each cross-docking center. Changes and modifications in the inventory level of cross-docking center at each time are indicated by constraint (11). Constraint (12) ensures the sufficient inventory of each product to meet all demands. Constraints (13) and (14) ensure that transporting product from suppliers to cross-dock and from cross-dock to retailers in the pickup and delivery processes can be taken and conducted only when the related cross-dock is open. Constraint (15) limits the number of cross-docks that can be located. Constraint (16) is related to capacity constraint on total costs which could pay for opening cross-docks. Constraint (17) enforces the binary and non-negativity restrictions on the decision variables.

In terms of the above notations, vehicle route scheduling problem with multiple cross-docks in the second phase of the proposed model via executional viewpoint can be formulated as follows: Min Z 2 = ∑ i ∈ P ∪ K ∑ j ∈ P ∪ K ∑ v ∈ V c ij x ijv + ∑ i ′ ∈ D ∪ K ∑ j ′ ∈ D ∪ K ∑ v ′ ∈ V ′ c i ′ j ′ x i ′ j ′ v ′(18) S . t . : ∑ i ∈ P ∪ K ∑ v ∈ V x ijv = 1 ∀ j ∈ P(19) ∑ i ′ ∈ D ∪ K ∑ v ′ ∈ V ′ x i ′ j ′ v ′ = 1 ∀ j ′ ∈ D(20) u iv - u jv + nx ijv ≤ n - 1 ∀ i , j ∈ P , and ∀ v ∈ V(21) u i ′ v ′ - u j ′ v ′ + mx i ′ j ′ v ′ ≤ m - 1 ∀ i ′ , j ′ ∈ D , and ∀ v ′ ∈ V ′(22) ∑ j ∈ P ∪ K x ijv = ∑ j ∈ P ∪ K x jiv ∀ i ∈ P ∪ K , and ∀ v ∈ V(23) ∑ j ′ ∈ D ∪ K x i ′ j ′ v ′ = ∑ j ′ ∈ D ∪ K x i ′ j ′ v ′ ∀ i ′ ∈ D ∪ K , and ∀ v ′ ∈ V ′(24) ∑ i ∈ K ∑ j ∈ P x ijv ≤ 1 ∀ v ∈ V(25) ∑ i ′ ∈ K ∑ j ′ ∈ D x i ′ j ′ v ′ ≤ 1 ∀ v ′ ∈ V ′(26) - Z kj + ∑ l ∈ P ∪ K ( x ilv + x ljv ) ≤ 1 ∀ i ∈ K , ∀ j ∈ P , and ∀ v ∈ V(27) - Z kj ′ + ∑ l ′ ∈ D ∪ K ( x i ′ j ′ v ′ + x l ′ j ′ v ′ ) ≤ 1 ∀ i ′ ∈ K , ∀ j ′ ∈ D , and ∀ v ′ ∈ V ′(28) w iv + ∑ p = 1 q f p p ip - w jv ≤ ( 1 - x ijv ) CA v(29) ∀ i ∈ P ∪ K , ∀ j ∈ P , and ∀ v ∈ V(30) w i ′ v ′ - ∑ p = 1 q f p d i ′ p - w j ′ v ′ ≥ ( 1 - x i ′ j ′ v ′ ) CA v ′ D ∪ K , ∀ j ′ ∈ D , and ∀ v ′ ∈ V ′(31) at i v ≥ t ij v ∀ v ∈ V , i ∈ K , and j ∈ P(32) a t i ′ v ′ ≥ t i ′ j ′ v ′ ∀ v ′ ∈ V ′ , ∀ i ' ∈ K , and ∀ j ′ ∈ D(33) a t i ′ v ′ + t i ′ j ′ v ′ − a t j ′ v ′ ≤ ( 1 − x i ′ j ′ v ′ ) T v ′ ∀ i ′ , j ′ ∈ D , and ∀ v ′ ∈ V ′(34) x ijv , x i ′ j ′ v ′ , Z kj , Z kj ′ ∈ { 0 , 1 }(35) w i v , w i ′ v ′ , a t i v , a t i ′ v ′ ≥ 0(36)

The objective function (18) minimizes total transportation costs associated with moving multiple products in the processes of pickup and delivery. Constraints (19) and (20) indicate that one vehicle has to arrive at and leave one node in the pickup process, delivery process and cross-dock. Moreover, these constraints specify that every supplier or retailer belongs to one and only one route. Constraints (21) and (22) make sub-tours impossible. Constraints (23) and (24) express the consecutive movement of vehicles. Whether or not a vehicle arrives at and leaves a cross-dock is shown in Equations (25) and (26). Constraints (27) and (28) specify that a retailer or supplier can be assigned to a cross-dock only if there is a route from that cross-dock going through that retailer or supplier. Constraints (29) and (30) express that the values of loaded and unloaded goods or products for each vehicle cannot exceed the maximum capacity of the vehicle in pickup and delivery processes. Constraints (31) to (34) ensure that all time windows are respected. Constraints (35) and (36) take the binary and non-negativity limitations on the decision variables.

5.1 Robust optimization model

The robust optimization theory was first introduced by Soyster [35]. Ben-Tal and Nemirovski [27, 28] and El-Ghaoui et al. [36] made attempts to present models for uncertain linear problems with ellipsoidal uncertainties. To apply the robust optimization model, holding costs, fixed opening costs, maximum total costs which could pay for opening cross-docks, and distances of pickup and delivery nodes are treated as uncertain parameters for the first phase of the proposed MILP model. Also, in the second phase, transportation costs and volume capacity of vehicles (route) in pickup and delivery processes, time for the vehicle to move between nodes and maximum working time of each vehicle in pickup and delivery processes are treated as uncertain parameters. For further details of robust optimization, readers are referred to [28, 29].

According to the above descriptions, the robust optimization model for multiple cross-docks location problem in two phases of the proposed model can be presented, respectively, as follows: Min Z 1 S . t . : ∑ k = 1 c ( F ¯ k x k + η k F ) + ∑ k = 1 c ∑ p = 1 q ∑ t = T min T max ( HC ¯ k , p S p , k , t + η k , p HC ) + ∑ p = 1 q ∑ i ′ = 1 m ∑ k = 1 c ∑ t = T min T max ( C i ′ k . Dist ¯ i ′ , k X p , k , t i ′ + η i ′ , k Dist ) + ∑ p = 1 q ∑ i ′ = 1 n ∑ k = 1 c ∑ t = T min T max ( C ik . Dist ¯ i , k X p , k , t i + η i , k Dist ) ≤ Z 1 ρ F G k F x k ≤ η k F ∀ k ρ F G k F x k ≥ - η k F ∀ k ρ HC G k , p HC S p , k , t ≤ η k , p HC ∀ p , k , and T min ≤ t ≤ T max ρ HC G k , p HC S p , k , t ≥ - η k , p HC ∀ p , k , and T min ≤ t ≤ T max ρ Dist G i ′ , k Dist X p , k , t i ′ ≤ η i ′ , k Dist ∀ i ′ , p , k , and T min ≤ t ≤ T max ρ Dist G i ′ , k Dist X p , k , t i ′ ≥ - η i ′ , k Dist ∀ i ′ , p , k , and T min ≤ t ≤ T max ρ Dist G i ′ , k Dist X p , k , t i ≤ η i , k Dist ∀ p , i , k , and T min ≤ t ≤ T max ρ Dist G i , k Dist X p , k , t i ≥ - η i , k Dist ∀ p , i , k , and T min ≤ t ≤ T max ∑ k = 1 c ∑ t = T min Ts d - 1 X p , k , t i ′ = 0 ∀ i ′ , p ∑ k = 1 c ∑ t = TS d TE d X p , k , t i ′ ≤ 1 ∀ i ′ , p ∑ k = 1 c ∑ TE d + 1 T max X p , k , t i ′ = 0 ∀ i ′ , p ∑ k = 1 c ∑ t = T min TS p - 1 X p , k , t i = 0 ∀ i , p ∑ k = 1 c ∑ t = TS p TE p X p , k , t i = 1 ∀ p , i , and Q i , p = 1 ∑ k = 1 c ∑ t = TE p + 1 T max X p , k , t i = 0 ∀ p , i ∑ p = 1 q S p , k , t ≤ cap ¯ k - ρ cap G cap ∀ k , and T min ≤ t ≤ T max s p , k , T min - 1 = 0 ∀ p , k s p , k , t = s p , k , t - 1 + ∑ i ′ = 1 m X p , k , t i ′ Q i ′ , p Am i ′ , p - ∑ i = 1 n X p , k , t i Q i , p Am i , p ∀ p , k , and T min ≤ t ≤ T max ∑ k = 1 C ∑ i ′ = 1 m X p , k , t i ′ Q i ′ , p Am i ′ , p - ∑ k = 1 C ∑ i = 1 n X p , k , t i Q i , p Am i , p ≥ 0 ∀ p and T min ≤ t ≤ T max X p , k , t i ≤ x k ∀ i , p , k , and T min ≤ t ≤ T max X p , k , t i ′ ≤ x k ∀ i , p , k , and T min ≤ t ≤ T max ∑ k = 1 c x k ≤ R ∑ k = 1 c F ¯ k ( 1 + ρ F ) x k ≤ TC ¯ - ρ TC G TC X p , k , t i X p , k , t i ′ , x k ∈ { 0 , 1 } s p , k , t , η k F , η k , p HC , η i ′ , k Dist , η i , k Dist ≥ 0 Min Z 2 S . t . : ∑ i ∈ P ∪ K ∑ j ∈ P ∪ K ∑ v ∈ V ( c ¯ ij x ijv + η ij c ) + ∑ i ′ ∈ D ∪ K ∑ j ′ ∈ D ∪ K ∑ v ′ ∈ V ′ ( c ¯ i ′ j ′ x i ′ j ′ v ′ + η i ′ j ′ c ) ≤ Z 2 ρ c G ij c x ijv ≤ η ij c ∀ i , j ρ c G ij c x ijv ≥ - η ij c ∀ i , j ρ c G i ′ j ′ c x i ′ j ′ v ′ ≤ η i ′ j ′ c ∀ i ′ , j ′ ρ c G i ′ j ′ c x i ′ j ′ v ′ ≥ - η i ′ j ′ c ∀ i ′ , j ′ ∑ i ∈ P ∪ K ∑ v ∈ V x ijv = 1 ∀ j ∈ P ∑ i ′ ∈ D ∪ K ∑ v ′ ∈ V ′ x i ′ j ′ v ′ = 1 ∀ j ′ ∈ D u iv - u jv + nx ijv ≤ n - 1 ∀ i , j ∈ P , and ∀ v ∈ V u i ′ v ′ - u j ′ v ′ + mx i ′ j ′ v ′ ≤ m - 1 ∀ i ′ , j ′ ∈ D , and ∀ v ′ ∈ V ′ ∑ j ∈ P ∪ K x ijv = ∑ j ∈ P ∪ K x ijv ∀ i ∈ P ∪ K , and ∀ v ∈ V ∑ j ′ ∈ D ∪ K x i ′ j ′ v ′ = ∑ j ′ ∈ D ∪ K x i ′ j ′ v ′ ∀ i ′ ∈ D ∪ K , and ∀ v ′ ∈ V ′ ∑ i ∈ K ∑ j ∈ P x ijv ≤ 1 ∀ v ∈ V ∑ i ′ ∈ K ∑ j ′ ∈ D x i ′ j ′ v ′ ≤ 1 ∀ v ′ ∈ V ′ - Z kj + ∑ l ∈ P ∪ K ( x ilv + x ljv ) ≤ 1 ∀ i ∈ K , ∀ j ∈ P , and ∀ v ∈ V - Z kj ′ + ∑ l ′ ∈ D ∪ K ( x i ′ l ′ v ′ + x l ′ j ′ v ′ ) ≤ 1 ∀ i ′ ∈ K , ∀ j ′ ∈ D , and ∀ v ′ ∈ V ′ ∑ i ∈ K ∑ j ∈ P x ijv ≤ 1 ∀ v ∈ V ∑ i ′ ∈ K ∑ j ′ ∈ D x i ′ j ′ v ′ ≤ 1 ∀ v ′ ∈ V ′ - Z kj + ∑ l ∈ P ∪ K ( x ilv + x ljv ) ≤ 1 ∀ i ∈ K , ∀ j ∈ P , and ∀ v ∈ V - Z kj ′ + ∑ l ′ ∈ D ∪ K ( x i ′ l ′ v ′ + x l ′ j ′ v ′ ) ≤ 1 ∀ i ′ ∈ K , ∀ j ′ ∈ D , and ∀ v ′ ∈ V ′ w iv + ∑ p = 1 q f p p ip - w jv ≤ ( 1 - x ijv ) CA ¯ v ( 1 - ρ CA ) ∀ i ∈ P ∪ K , ∀ j ∈ P , and ∀ v ∈ V w i ′ v ′ - ∑ p = 1 q f p d i ′ p - w j ′ v ′ ≥ ( 1 - x l ′ j ′ v ′ ) CA ¯ v ′ ( 1 + ρ CA ) ∀ i ′ ∈ D ∪ K , ∀ j ′ ∈ D , and ∀ v ′ ∈ V ′ at i v ≥ t ¯ ij v ( 1 + ρ t ) ∀ v ∈ V , ∀ i ∈ K , and ∀ j ∈ P at i ′ v ′ ≥ t ¯ i ′ j ′ v ′ ( 1 + ρ t ) ∀ v ′ ∈ V ′ , ∀ i ′ ∈ K , and ∀ j ′ ∈ D at i v + t ¯ ij v ( 1 + ρ t ) - at j v ≤ ( 1 - x ijv ) T ¯ v ( 1 - ρ T ) ∀ i , j ∈ P , and ∀ v ∈ V at i ′ v ′ + t ¯ i ′ j ′ v ′ ( 1 + ρ t ) - at j ′ v ′ ≤ ( 1 - x i ′ j ′ v ′ ) T ¯ v ′ ( 1 - ρ T ) ∀ i ′ , j ′ ∈ D , and ∀ v ′ ∈ V ′ x ijv , x i ′ j ′ v ′ , Z kj , Z kj ′ ∈ { 0 , 1 } 0 ≤ u iv ≤ n , 0 ≤ u i ′ v ′ ≤ m , w iv , w i ′ v ′ , at i v , at i ′ v ′ ≥ 0

5.2 Meta-heuristic algorithm

This study applies a new version of imperialist competitive algorithm, namely self-adaptive ICA (SAICA), to present near optimal solution by regarding pure ICA and simulated annealing [31, 37–40]. Pseudo codes of the two phases of the proposed SAICA are separately shown as Figs. 2 and 3.