Collaborative vehicle routing problem with rough location using extended ant colony optimization algorithm

3.1.1 Notations

(1) Sets:

(2) Input variables:

(3) Decision variables:

3.1.2 Rough location

In traditional studies of the CVRP, the customer’s detailed location is visible to all LSPs, which will compromise the security of customer information. In the proposed CVRPRL, LSPs will offer RLs to their partners to protect sensitive information. Figure 1 shows illustrative examples of a non-cooperative routing plan, traditional cooperative routing plan, and cooperative routing plan with an RL. From Fig. 1(a) and 1(b), we can see that both LSP A and LSP B can optimize their respective routes through cooperation, but they have to reveal their respective customer’s detailed location to each other. As shown in Fig. 1(c), both LSP A and LSP B can only obtain the RL of the other’s customer but can still optimize the collaborative routing plan. If a customer order is outsourced to another LSP, the travel cost depends on the distance between the RLs and their areas. It is noted that the area of an RL will affect the entire logistics activity. The larger the area of the RL, the more uncertain the collaborative route is. Thus, if the area of the RL is too large, it will increase the overall operational cost. If the area of the RL is too small, the security of customer information cannot be guaranteed. In this study, if a LSP’s customer is served by other LSPs, the LSP will incur an extra penalty cost that is determined by the area and girth of the RL. The configuration of an RL depends on the LSP’s strategy.

OPEN IN VIEWER

Fig.1

Illustrative examples of different routing plans.

In traditional studies on CVRPs, all the shared resources of LSPs are controlled by a horizontal logistics coalition. In the proposed CVRPRL, LSPs can adjust their respective shared resources according to the CLSD from three aspects: freight capacity sharing degree (FCSD), warehouse inventory sharing degree (WISD), and customer order sharing degree (COSD). First, an LSP usually does not share all freight capacity in the horizontal logistics coalition so that it can use its remaining freight capacity in its own future expected plans. In this study, the shared freight capacity can be expressed as the transportation cost from the other LSPs’ customers and Equation (1) shows the FCSD of LSP l. Second, an LSP usually does not share all warehouse inventory in the horizontal logistics coalition so that it can use the remaining inventory for its own future customer orders. In this study, the shared warehouse inventory can be expressed as the total capacity of products that is used to meet the other LSPs’customers and Equation (2) shows the WISD of LSP l. Third, an LSP usually does not share all customer orders in the horizontal logistics coalition so that it can fulfil the remaining customer orders itself. In this study, the shared customer order can be expressed as the number of outsourced customer orders and Equation (3) shows the COSD of LSP l. Equation (4) shows that the CLSD of LSP l consists of FCSD, WISD, and COSD. FCSD l = ∑ i ∈ N ∑ j ∈ C 1 - C ∑ k ∈ K ( a ij + g j c j e s j / ( 1 + c j ) ) x ijkl | F max l |(1) WISD l = ∑ i ∈ N ∑ j ∈ C 1 - C ∑ k ∈ K x ijkl w j | W max l |(2) COSD l = | C l | - ∑ i ∈ N ∑ j ∈ C 1 - C ∑ k ∈ K x ijkl | C max l |(3) CLSD l = ω 1 FCSD l + ω 2 WISD l + ω 3 COSD l(4)

In addition, the larger the RL area of the outsourced customer, the more unreliable the overall routing is. In Equation (1), besides the consideration of explicit transportation costs a ij , g j c j e s j / ( 1 + c j ) is set to a penalty cost to limit both the area size of RL and excessive freight capacity shared by LSPs. ω₁,  ω₂, and ω₃ denote the weights of the preferred LSPs in view of their vehicle capacities, warehouse inventory, and customer order, which will add up to one. CLSD _l will be within the range [0, 1].

The objective function is to minimize the overall operational cost, consisting of two parts. The first part is composed of the transportation costs to arrive at RL and the delivery cost in RL, which involves a penalty mechanism to limit the area size of RL. The second part is the delivery cost of customerservedby its own LSP. Thus, the objective function of the CVRPRL model is defined as follows:

f = min [ ∑ i ∈ N ∑ l ∈ L ∑ k ∈ K ∑ j ∈ C l ( a ij + g j c j e s j / ( 1 + c j ) ) x ijkl + ∑ i ∈ N ∑ l ∈ L ∑ k ∈ K ∑ j ∈ C l h ij x ijkl ](5)

Subject to the following constraints: ∑ i ∈ N ∑ k ∈ K ∑ l ∈ L x ijkl = 1 , ∀ j ∈ C(6) ∑ i ∈ N x i j k l = ∑ i ∈ N x i j k l , ∀ j ∈ N , ∀ k ∈ K , ∀ l ∈ L(7) CLSD l ⩽ MCLSD l , ∀ l ∈ L(8) ℓ j x ijkl = ξ ij x ijkl , ∀ i ∈ D , ∀ j ∈ C , ∀ k ∈ K , ∀ l ∈ L(9) ℓ j x ijkl = ( ℓ i + ξ ij ) x ijkl , ∀ i ∈ C , ∀ j ∈ N , ∀ k ∈ K , ∀ l ∈ L(10) ∑ i ∈ N ∑ j ∈ C ∑ l ∈ L w j x ijkl ⩽ w 0 , ∀ k ∈ K(11)

Equation (6) shows that each customer is visited exactly once. Equation (7) represents that the amount of outgoing vehicles is equal to the amount of incoming vehicles at each node. Equation (8) shows that the CLSD of LSP l is no more than its MCLSD, which avoids the LSP l from sharing excessive resource. Equation (9) represents the fuzzy arrival time at customer j from depot i. Equation (10) represents the fuzzy arrival time at node j from customer i. Equation (11) shows that each vehicle is not overloaded.

In this model, the arrival time is presented by trapezoidal fuzzy number ℓ = (ℓ ₁, ℓ ₂, ℓ ₃, ℓ ₄). In order to rank them, we employ credibility measure [20] in CVRPRL model. According to the nature of this problem, coalition should provide a confidence level ∂ where the decision must meet the constraints at the defined confidence level. According to the credibility theory, we can derive the credibility with which the vehicle arrives at the customer before due time. Cr { ℓ ⩽ t } = { 1 , ℓ 4 ⩽ t , t + ℓ 4 - 2 ℓ 3 2 ( ℓ 4 - ℓ 3 ) , ℓ 3 ⩽ t ⩽ ℓ 4 , 1 2 , ℓ 2 ⩽ t ⩽ ℓ 3 , t - ℓ 1 2 ( ℓ 2 - ℓ 1 ) , ℓ 1 ⩽ t ⩽ ℓ 2 , 0 , else .(12) Cr { ℓ i ⩽ T i } ⩾ ∂ , ∀ i ∈ C(13)

Equation (13) shows that the credibility with which the vehicle arrives at the node within the due time equals or exceeds the confident level.

It can be found that the cost of optimal solution from CVRPRL will be possibly higher than that from the traditional CVRP model. There are two main reasons. On the one hand, there exist more uncertain factors in the proposed model due to RL. On the other hand, the resource distribution and management encounters more constraints from LSP. These issues need be addressed in the future work so that the logistics network based on CVRPRL becomes more stable and brings more potential benefits.

The time complexity of calculating the CVRPRL model can be divided into three parts. First, the CLSD of all LSPs are obtained by enumerating each customer, which requires O (|C|) time. Second, the fuzzy arrival time of all customers is obtained by enumerating each route, which requires O (|C| + |D| * |K|) time. Third, the overall travelling cost is obtained by adding up the costs of all routes, which requires O (|C| + |D| * |K|) time. |D| * |K| is equal to the total number of vehicles, which is much lower than the number of customers in a real-world situation. Thus, the time complexity of calculating the CVRPRL model is O (3 * |C| + 2 * |D| * |K|), which is approximately equal to O (3 * |C|). Therefore, similar to the time complexity of calculating the traditional CVRP model, the time complexity of calculating the CVRPRL model will increase linearly with the number of customers.

3.2.1 Shapley value

Allocation strategy is critical in cooperative logistics [21]. The Shapley value is proposed by Shapley [29] for profit or cost allocation. Let us define the set N of LSPs, the power set of P (N), and the payoff function v. Each subset of N is called a coalition, excluding null set. The following two conditions should be satisfied: v ( ∅ ) = 0(14) v ( S ∪ T ) ⩽ v ( S ) + v ( T ) , S ∩ T = ∅ , S , T ∈ N(15)

Equation (14) shows that void coalition has no cost value. Equation (15) shows that the cost value of two mutually cooperative coalitions is less than or equal to that of two independent coalitions; two mutually cooperative coalitions can incur less cost. In the coalition S, the marginal cost φ of LSP i is calculated by Equation (16). φ ( S , i ) = v ( S ) - v ( S - { i } ) .(16)

ζ (S, v) represents the Shapley value of coalition S, and is calculated by Equation (17). ζ ( S , v ) = ∑ T ⊂ S ; i ∈ T ( | S | - 1 ) ! ( | T | - | S | ) ! | T | ! φ ( S , i )(17)

The allocation cost of a LSP is the weighted sum of marginal costs in the coalition. However, in the process of cooperation, emergency issues such as vehicle damage or cargo loss may impact the actual cost. The risk of logistics coalition should also be considered in the allocating strategy. Next, we will extend Shapley value by including the risk of logistics to solve this problem.

In this study, the overall cost consists of fixed cost and risk cost. Based on the extra cost of risk and the amount of resource sharing of each LSP, we propose an extended Shapley value. By comparing with the fixed cost, the allocation scheme for risk cost will be adjusted. The payoff function v is composed of fixed payoff p _f and risk payoff p _r . p _f  (S) represents the minimum fixed fuel cost of coalition S, which is given by the CVRPRL model. p _r  (S) represents the additional cost of coalition S based on risk assessment. The payoff function v and modified marginal cost φ _e are calculated as follows: v ( S ) = p f ( S ) + p r ( S ) ,(18) φ e ( S , i ) = p f ( S ) - p f ( S - { i } ) + | S | κ i S ∑ j ∈ S κ j S p r ( S ) - p r ( S - { i } )(19) where κ i S represents the weight of LSP in coalition S and estimated by experts according to the ability of coping with risk and the degree of resource sharing, satisfying ∑ i ∈ S κ i S = 1 . In Equation (19), modified marginal risk cost will be adjusted, because different LSPs will take risks with different extents. ζ _e  (S, v) represents the extended Shapley value of coalition S, and is calculated by Equation (20). ζ e ( S , v ) = ∑ T ⊂ S ; i ∈ T ( | S | - 1 ) ! ( | T | - | S | ) ! | T | ! φ e ( S , i ) = ∑ T ⊂ S ; i ∈ T ( | S | - 1 ) ! ( | T | - | S | ) ! | T | ! [ p f ( S ) - p f ( S - { i } ) + | S | κ i S ∑ j ∈ S κ j S p r ( S ) - p r ( S - { i } ) ] .(20)

In the ACO phase, the ants will construct solutions according to heuristic information. It can be considered as an optimized heuristic clustering process and a better solution can be found. In traditional studies of ACO, the solution construction process largely depends on the pheromone, which tends to lead to stagnation. Therefore, we improve the construction mechanism in the current study by employing three rules randomly to avoid stagnation. A new route between node i and node j can be built based on Equation (25). y = { Y 1 : P ( i , j ) = [ τ ij ] α · [ η ij ] β ∑ t ∈ I k ∑ s ∈ J t k [ τ ts ] α · [ η ts ] β , r ⩽ r 1 , Y 2 = arg max i ∈ I k , j ∈ J t k ( [ τ ij ] α · [ η ij ] β ) , r 1 < r ⩽ r 2 , Y 3 = arg max j ∈ J t k ( [ τ ij ] α · [ η ij ] β ) , r 2 < r ⩽ 1 , i is randomly selected from I k ,(25) where I ^k is the set of vehicle locations of ant k. J i k is the set of customers that have not yet been visited by ant k and can be arrived at when the vehicle is at node i. r is a random number belonging to [0, 1]. r₁ and r₂ are user parameters. Y¹, Y² and Y³ represent three different ways to construct a new route. If r ⩽ r₁, a new route is built randomly and the probability of building a feasible route between node i and node j is calculated by Y¹. If r₁ < r ⩽ r₂, the ant will apply Y² to select next node y. Otherwise, Y³ is applied. After all the customers are passed, a new initial solution is obtained.

After the construction phase, we use the local search to optimize the current best solution and the global best solution. The LNS algorithm applies removal operation and re-insertion operation to the initial feasible solutions to improve the solution. Ropke and Pisinger [27] proposed the worst removal heuristic to replace Shaw removal heuristic [30]. In the worst removal heuristic, the higher the transportation cost a customer incurs, the likelier it is that the customer is removed. However, some customers may be removed by mistake if they are too far away from other customers. Figure 3 shows an illustrative example by using conventional worst removal heuristic to remove customer, in which, two customers A and B, who are far away from other customers, will be removed by mistake with high probability.

OPEN IN VIEWER

Fig.3

Using conventional worst removal heuristic to remove customers.

In this work, a modified worst removal heuristic is proposed, according to which, a customer that incurs abnormally high transportation cost should have higher probability of removal. In Fig. 3, two customers A and B, who are very likely to be removed by conventional worst removal heuristic, are served with normal transportation cost and are less likely to be removed by our modified worst removal heuristic. Four customers C, D, E and F, who are less likely to be removed by conventional worst removal heuristic, are served with abnormally high transportation cost due to reverse route and can be very likely to be removed by our modified worst removal heuristic. The abnormal cost (AC) and the corresponding probability are calculated by Equations (26) and (27) respectively.

AC x = f ( s ) - f - x ( s ) c min x(26) π x = AC x max i ∈ C AC i(27) where f (s) and f_-x (s) represent the transportation costs of solution s with and without customer x, respectively; c min x is the minimum cost from other nodes to customer x. According to the probability π _x , a few customers should be removed. The number of customers removed depends on the parameter Δ. Subsequently, these removed customers will be reinserted according to the greedy strategy, which will prefer the minimum cost in the current state. The pseudo code is shown in Algorithm 1.

Although a basic ACO can be used to find a solution for a VRP, the basic ACO tends to be the stagnation after a certain time of iteration. The drawback can be avoided by combining other approaches. In some studies [19, 34], the local search strategy is often applied to further improve the performance of ACO. In the current study, we also apply the local search strategy to further improve the optimization performance of EACO, which consists of a 2-opt algorithm [7] and an Or-opt algorithm [25]. The 2-opt algorithm is an effective local search technique that reverses a segment of a route to obtain a better solution, unless the solution cannot be improved further. As an illustrative example, Fig. 4(a) shows that the segment of the route from node B to node D is reversed. Similarly, the Or-opt algorithm is used to reverse a segment of a route, and then change the position of the segment in the route to obtain a better solution, unless the solution cannot be improved further. As another illustrative example, Fig. 4(b) shows that the segment of the route from node A to node B is reversed first, and is then inserted between node D and node E.

OPEN IN VIEWER

Fig.4

The operations of 2-opt and Or-opt.

The local search strategy offsets the mistakes made by the greedy re-insertion operation, which sometimes inserts a costly route. The pseudo code of the 2-opt and Or-opt algorithms are shown in Algorithm 2 and Algorithm 3, respectively.