Next Article in Journal
Local Energy Communities and Distributed Generation: Contrasting Perspectives, and Inevitable Policy Trade-Offs, beyond the Apparent Global Consensus
Previous Article in Journal
Leadership and Organizational Culture in the Sustainability of Subsistence Small Businesses: An Intellectual Capital Based View
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Collaborative Mechanism for Pickup and Delivery Problems with Heterogeneous Vehicles under Time Windows

1
School of Economics and Management, Chongqing Jiaotong University, Chongqing 400074, China
2
School of Management and Economics, University of Electronic Science and Technology, Chengdu 610054, China
3
Department of Civil and Environmental Engineering, University of Washington, Seattle, WA 98195, USA
4
School of Civil and Construction Engineering, Oregon State University, Corvallis, OR 97330, USA
*
Authors to whom correspondence should be addressed.
Sustainability 2019, 11(12), 3492; https://0-doi-org.brum.beds.ac.uk/10.3390/su11123492
Submission received: 25 May 2019 / Revised: 15 June 2019 / Accepted: 24 June 2019 / Published: 25 June 2019
(This article belongs to the Section Sustainable Transportation)

Abstract

:
The sustainability and complexity of logistics networks come from the temporally and spatially uneven distributions of freight demand and supply. Operation strategies without considering the sustainability and complexity could dramatically increase the economic and environmental costs of logistics operations. This paper explores how the unevenly distributed demand and supply can be optimally matched through collaborations, and formulates and solves a Collaborative Pickup and Delivery Problem under Time Windows (CPDPTW) to optimize the structures of logistics networks and improve city sustainability and liverability. The CPDPTW is a three-stage framework. First, a multi-objective linear optimization model that minimizes the number of vehicles and the total cost of logistics operation is developed. Second, a composite algorithm consisting of improved k-means clustering, Demand-and-Time-based Dijkstra Algorithm (DTDA) and Improved Non-dominated Sorting Genetic Algorithm-II (INSGA-II) is devised to solve the optimization model. The clustering algorithm helps to identify the feasible initial solution to INSGA-II. Third, a method based on improved Shapley value model is proposed to obtain the collaborative alliance strategy that achieves the optimal profit allocation strategy. The proposed composite algorithm outperforms existing algorithms in minimizing terms of the total cost and number of electro-tricycles. An empirical case of Chongqing is employed to demonstrate the efficiency of the proposed mechanism for achieving optimality for logistics networks and realizing a win-win situation between suppliers and consumers.

1. Introduction

The Collaborative Pickup and Delivery Problem under Time Windows (CPDPTW) seeks to identify a collaborative mechanism for logistics network and synergize pickups and deliveries by coordinating Logistics Providers (LPs). CPDPTW need to be studied so that the efficiency of the logistics network can be improved and commodity can be collected and distributed timely. The development of e-commerce has led to a surge in consumer demand, for example, China’s fresh e-commerce transactions totaled about 140 billion yuan in 2017, with a year-to-year increase of 59.7%, whereas the loss rate of fresh food in the distribution process has reached 30% [1]. The huge order sizes and strict timeliness requirement increase the complexity of the pickup and delivery logistics network.
Solving this CPDPTW problem can improve network transport efficiency and security. It can also improve the timeliness of service provided by LPs and boost the stability of the network, which will help enterprises reduce operation costs. Therefore, the design of pickup and delivery logistics networks is of particular interest to researchers and LPs alike [2,3]. CPDPTW is different from the conventional Multi-Depot Vehicle Routing Problem with Pickups and Deliveries (MDVRPPD), which assumes that pickups and deliveries are independent. CPDPTW connects the product collecting process and distribution process in collaborative network. A growing emphasis is provided on the coordination among commodity suppliers, LPs and customers in CPDPTW, which commonly exists in Logistics Network with Pickups and Deliveries (LNPD). Effective and low-cost LNPD needs to be designed to ensure the quality of products and meet customers’ timeliness requirements. LNPD, which is usually composed of suppliers, LPs and customers, is an important part of a multi-echelon logistics system [4,5]. Cooperation among logistics providers can improve the performance of the entire logistics network by reducing transportation or operation costs and generating additional profit ensuring customer service quality. Therefore, identifying the means to configure the network in case of on-demand delivery and to achieve the synergy of resources are crucial. Among the three components of LNPD, LP is the key to ensuring a well-connected and stable pickup and delivery logistics network.
Existing works have covered vehicle routing problem (VRP) optimization and the profit distribution strategy [6,7]. These studies, however, mostly overlooked the coordination and cooperation process among commodity suppliers, logistics providers and customers. Research on CPDPTW needs to be strengthened. To fill the research gap, the current work presents a collaboration mechanism to coordinate the components of LNPD. Establishing the collaboration mechanism can greatly improve logistics efficiency. In the proposed collaboration mechanism, each supplier and customer are reasonably assigned to an adjacent logistics provider to optimize LNPD. The optimization problem aims to find the near-optimal vehicle routes through a composite algorithm. We investigate customer clustering, and employ dynamic programming and heuristic algorithms to reduce the complexity of this computation and further find the optimal solution of CPDPTW. Finally, a profit distribution strategy based on cooperative game theory is proposed to fairly distribute the profits and study the alliance sequences, the orders in which logistics providers join an alliance.
The remaining sections of this paper are organized as follows. Relevant literature is reviewed in Section 2. In Section 3, the problem of CPDPTW is set up with the definitions of related concepts and quantities and the assumptions in the CPDPTW model. In Section 4, a multi-objective optimization model is established to redesign the vehicle routes and minimize the total cost in the collaborative logistics network, and a composite algorithm including DTDA, clustering and a hybrid algorithm named INSGA-II is presented to obtain the optimal routes A profit strategy for profit distribution is presented in Section 5. In Section 6, a real-world case study is performed to verify the applicability of the proposed model and methodology. In Section 7, the conclusion and summary results are presented, and the possible future research directions are pointed out.

2. Literature Review

The collaborative mechanism based on CPDPTW becomes increasingly valuable [8,9]. LPs play an important part in the logistics supply chain. The synergy among them can reduce logistics costs and generate profits for enterprises. In addition, vehicle, customer service and resource sharing have been integrated into the collaborative logistics network, which could improve the sustainability of such a network. Because of its practical importance, many researchers have attempted to achieve resource synergy and study the dynamic quality game among participants in logistics network design [10,11]. To improve the ability of commodity distribution in supply chain network, Govindan et al. [12] proposed a two-echelon location routing problem under time window for designing a sustainable supply chain network, which aims to cut the cost of the whole network. Based on the duration of logistics operations, Bal and Satoglu [13] proposed a multi-product and multi-period goal programming model to study sustainable logistics operations planning and an application. By making the best choice for commodity packaging containers, Bortolini et al. [14] focused on the cost of the entire distribution network, and then designed a supply chain network to reduce costs while controlling quality. Other researchers have also studied the two-echelon collaborative logistics network. Lozano et al. [15] merged the transportation demands from multiple companies to achieve the horizontal collaboration among shippers, which can effectively reduce the operation cost. Feng et al. [16] designed multiple collaboration and decision-making mechanisms for efficient logistics transportation planning. Wang et al. [17] optimized two-echelon pickup and delivery networks to reduce their total operation costs by establishing collaborative alliances.
The above research on supply chain networks provides a reference for the study of pickup and delivery logistics networks. A single logistics provider processing a large amount of commodity typically exists in a commodity distribution network with pickups and deliveries. This phenomenon enables the application of precise method for studying the collaborative logistics networks with pickups and deliveries. Researchers have studied numerous precise methods [18,19]. Sedeño-Noda and Raith [20] proposed a Dijkstra-like method to determine all extreme supported non-dominated solutions to the shortest path problem. Horváth and Kis [21] presented a branch and bound method to study the constrained shortest path problem. Zhang et al. [22] studied a stochastic network based on lagrangian relaxation method to find a reliable shortest path. Liu et al. [18] presented a branch-and-cut algorithm to study the two-echelon capacitated vehicle routing problem. Andrade and Saraiva [23] used shortest path method to solve an inter-linear programming model, which aims to find the shortest path between two vertices. A branch-and-cut algorithm was used to study the unit-demand capacitated vehicle routing problem [24]. Consequently, the precise method used to optimize the vehicle routing problem with pickups and deliveries can improve the reliability of logistics network, and contribute to achieve sustainable transportation goals.
Following commodity pickup, vehicles must be assigned to distribute the collected commodity after simple classification and sorting. The underlying delivery network is different from the pickup network. The clustering methods of customer demands are particularly important for sustainable large-scale distribution networks. Clustering algorithm can be seen as a necessary element in solving multi-depot vehicle routing problem with time windows (MDVRPTW) [25,26]. Many researchers have studied various clustering methods to solve complex network problems. Narasimha et al. [27] used a clustering algorithm to simplify the computation process in the min‒max multi-depot vehicle routing problem. Wang et al. [28] proposed a fuzzy clustering algorithm to divide the large number of customers into multiple cluster units, which accelerates convergence in optimizing the logistics network. A clustering method named demand clustering was implemented in freight logistics networks, and has proved to be an important strategic decision tool for carriers [29]. Dragomir et al. [30] studied the computational complexity of multi-depot pickup and delivery problems, which can be simplified by customer clustering. Wang et al. [31] presented a clustering algorithm to study the complex logistics network optimization problem with pickups and deliveries. Wang et al. [32] considered customers’ locations and purchase behaviors and discovered similar characteristics among them through clustering algorithm to solve the two-echelon location-routing optimization with time windows. An improved density peaks clustering algorithm based on fast calculation of cluster centers was proposed to simplify the computational complexity of large-scale data [33,34]. In summary, customer clustering algorithm can be considered as an important input step during the MDVRPTW optimization procedure.
MDVRPTW is an important part of the CPDPTW. Heuristic or intelligent algorithms and the simulation-based approach can be used to study CPDPTW [19,35,36]. Integrated transportation services into logistics providers should be considered in the CPDPTW. Soysal and Çimen [37] combined a heuristic approach with simulation-based dynamic programming method to solve the green time dependent vehicle routing problem in a large sized logistics network. Liu et al. [38] proposed a simulation-based optimization approach combined with a tabu search algorithm to study the two-echelon vehicle routing problem consisting of freight transportation through intermediate satellites. Belgin et al. [39] presented a hybrid heuristic algorithm with variable neighborhood descent and local search to solve the two-echelon vehicle routing problem with simultaneous pickup and delivery. Chami et al. [40] proposed a hybrid metaheuristic to solve a multi-period pickup and delivery problem with time windows and paired demands, which aimed to minimize the total traveled distance needed. Nedjati et al. [41] proposed a heuristic solution procedure named NSGAII multi-objective algorithm with two distinct improvements, which was utilized to solve the location routing problem. Given that delivery should meet the time window, Afshar-Nadjafi [42] established a mixed integer-programming model and proposed a constructive heuristic algorithm to solve the MDVRPTW model, which aimed to minimize the total cost of heterogeneous fleets. Li et al. [43] formulated an integer programming model and proposed a hybrid genetic algorithm with adaptive local search to study the multi-depot vehicle routing problem with time windows. Naccache et al. [44] established a model based on multi-pickup and delivery problem under time window constraints, and developed a hybrid adaptive large neighborhood search to solve this problem. Meng et al. [45] proposed a Tabu Search (TS) algorithm with designed batch combination and item creation operation to solve the vehicle routing problem in a pickup and delivery network. The above proposed models and solution approaches can provide decision-making reference for the study of CPDPTW, and further demonstrate that the future work is required.
CPDPTW optimization usually includes vehicle routing optimization and collaborative strategy design [12,46]. Collaboration among logistics providers will often be considered in a multi-level logistics distribution network optimization process on the basis of a sustainable perspective, which will generate the net profits and exist profit distribution problems [15,47,48]. The distribution of profits is handled in many ways, and some researchers have proposed various profit allocation methods to study the collaboration alliance mechanism. Frisk et al. [49] proposed a new allocation method, which aimed to ensure the relative profits to participants are as equal as possible. Cruijssen et al. [47] proposed a so-called Shapley monotonic path method to allocate cost reduction to the participating shippers in a fair and sustainable way. To improve vehicle utilization and reduce carriage return in collaborative logistics network, Dai and Chen [50] proposed three profit distribution mechanisms based on the Shapley value, the concept of proportional allocation and the contribution of each operator to solve the resulting profit distribution problem. Lozano et al. [15] tackled the problem of allocating the joint cost savings from cooperation based on cooperative game theory. Kumoi and Matsubayashi [51] formulated a cooperative game to analyze the stable and fair profit allocations under the grand alliance, which means all participants, joined an alliance according to an effective cooperation strategy. In the field of video on-demand services, Kamiyama et al. [52] suggested that network service providers cooperate to deal with the problem of wide-ranging on-demand volume, and proposed to use the Shapley value method to distribute the profits from the alliance reasonably. Wang et al. [53] proposed an improved Shapley value method to solve the problem of revenue redistribution due to the alliance and achieved good results. Wu et al. [54] compared four benefit allocation schemes including Shapely, the Nucleolus, Degree of Polymerization (DP) equivalent method, and Nash-Harsanyi based on cooperative game theory, which aims to deal with the benefit assignment among the building clusters in the distributed building heating network. However, collaborative strategy design among multiple logistics facilities should be further investigated and studied in collaboration-based MDVRPTW.
The above studies suffer from the following issues: (1) Conventional MDVRPTW rarely considers the optimization of vehicle routes and profit allocation collectively, especially when goods are transported between logistics providers in a sustainable collaborative logistics network. (2) Collaborative logistics network design is rarely considered including resource sharing, vehicle sharing and customer service sharing among LPs on the basis of the sustainability view in LNPD. (3) Conventional multi-objective model and heuristic algorithm cannot be directly employed to account for the resource sharing and the alliance mechanism among multiple logistics providers. (4) Most studies tend to consider pickup and delivery independently, but ignore the construction of collaborative coalition sequence and the sustainability of long-term collaboration, and little research has also been done on the problem of collect-to-distribute process in the CPDPTW.
In summary, the main contributions of the current work are as follows: (1) Proposing a sustainable collaborative logistics network with both pickups and deliveries, which accounts for collaborations horizontally and vertically: horizontally, logistics providers cooperate with each other to form alliance(s) and vertically, logistics providers synchronize their operations with suppliers and customers. (2) Establishing a multi-objective optimization model based on the minimum number of vehicles and the minimum total cost with consideration of resource sharing, vehicle sharing and customer service sharing among LPs for the sustainable collaborative logistics network. (3) Designing a three-stage composite algorithm that comprises DTDA, improved K-means clustering and improved NSGA-II algorithm to effectively solve the multi-objective optimization model, and then a strictly monotonic path (SMP) selection strategy is utilized to study the collaborative coalition sequences and evaluating alliance stability(sustainability) given a profit distribution scheme. (4) Implementing a real-world case study to assess the applicability and sustainability of the proposed approach to two alliance mechanisms, and conducting a series of comparisons and analysis to demonstrate the superiority of the composite algorithm. In addition, this study solves a special case problem of the logistics network optimization, which can be further extended to solve the problem of collaborative multi-echelon logistics network optimization in a sustainable intelligent transportation system.

3. Problem Statement

Solving the CPDPTW can increase the stability of the logistics network through sharing of customer service, vehicles and resources. Figure 1 shows the changes in logistics network structure before and after optimization. This logistics network consists of two parts, the pickup and the delivery network. After a customer places the order with an expected time of delivery, LPs should serve the customers within their expected time windows, due to the timeliness nature of commodities. Suppliers also hope that LPs can pick up the goods within their expected time windows because they need to prepare the commodity after receiving orders. Thus, LPs need to arrive within suppliers’ expected time windows. In terms of the means of transportation, trucks transport commodities collected from LPs to suppliers while electro-tricycles are used to deliver goods to customers.
As shown in Figure 1a complex logistics network combines pickups and deliveries. Figure 1a shows the logistics network structure in the non-optimal LNPD. On the one hand, every supplier is doing business with every LP. Therefore, LPs need to pick up the commodity from each supplier and then distribute the collected commodity to customers. Thus, long-distance transportation cannot be avoided during pickup and delivery. Moreover, LPs will wait until the orders have accumulated to a certain number before starting pickup to save transportation costs. The two factors of long-distance transportation and the desired number of orders to start pickup together make meeting the time requirements of suppliers and customers difficult. On the other hand, the transportation network shown in Figure 1a is over-complicated, with many cross-transport loops during pickup and delivery. In Figure 1b, logistics provider intends to cooperate with one another in the LNPD. As a result, each LP only needs to serve the suppliers and customers assigned by the optimization results. In other words, we should first divide customers into different clusters according to customers’ order demands, and each cluster must be paired with an LP who is responsible for delivering commodity to its paired cluster of customers. The commodity ordered by a cluster of customers should then be collected to the corresponding LP and then transported among the LPs. The comparison of cost and number of vehicles between before and after optimization is given in Table 1. Assuming that customers visited beyond time windows are compensated $50 in addition to the pickup and transportation costs of $20 per unit time and delivery cost of $10 per unit time, significant reduction in cost and number of vehicles can be achieved through collaborative transportation and distribution optimization.
In the collaborative LNPD, LPs coordinate on pickup and delivery together, and the CPDPTW can fulfill customers’ requirements for delivery time and achieve the minimum waiting time minimum during pickup and delivery. Therefore, the proposed CPDPTW solution through collaboration could facilitate a systematic optimization and effective resource management in the pickup and delivery network.

4. Model Formulation and Solution Methodology

4.1. Model Formulation

4.1.1. Related Assumptions and Definitions

Our proposed network includes multiple LPs, several suppliers and numerous customers. To make our proposed network structure realistic, we propose the following assumptions.
  • Assumption 1: There exist multiple working periods in one year, and the customer demand is stable within each working period.
  • Assumption 2: LPs operate independently in a non-optimized network.
  • Assumption 3: Each LP pursues profit maximization and fair profit distribution strategy.
  • Assumption 4: The collection of goods and the transportation between the LPs are all based on trucks. The goods are delivered via electric tricycles.
  • Assumption 5: The alliance among suppliers is not considered. Only the alliance between logistics providers is considered.
  • Assumption 6: The service time of each customer is considered to be 0.
In order to formulate the proposed problem into a mathematical model for analytical solutions, some related variables are defined as follows:
S = { s | s = 1 , 2 , 3 , , m } denotes the set of suppliers, and m is the total number of suppliers;
C = { c | c = 1 , 2 , 3 , , a } denotes the set of customers, and a is the total number of customers;
I = { i | i = 1 , 2 , 3 , , b } denotes the set of logistics providers, and b is the total number of logistics providers;
K = { k | k = 1 , 2 , 3 , , m } denotes the set of electro-tricycles, and m is the total number of electro-tricycles;
V = { v | v = 1 , 2 , 3 , , g } denotes the set of trucks from the suppliers to LPs, and g is the total number of trucks;
V ¯ = { v ¯ | v ¯ = 1 , 2 , 3 , , g ¯ } denotes the set of trucks between LPs, and g ¯ is the total number of trucks, V ¯ V ;
x i s v is the decision variable which equals to 1 if truck v traveled from i to s ( i I S , s S ), otherwise set x i s v = 0 , v V ;
x i c k is the decision variable which equals to 1 if electro-tricycle k traveled from i to c ( i I C , c C ), otherwise set x i c k = 0 , k K ;
d i s denotes the Manhattan distance between LP i and supplier s or supplier i and supplier s, ( i I S , s S );
d i c denotes the Manhattan distance between LP i and customer c or customer i and customer c, ( i I C , c C );
d i j denotes the distance from LP i to LP j;
f k denotes electric power consumption per kilometer of electro-tricycle k;
[ e s , u s ] denotes the time window of supplier s;
[ e c , u c ] denotes the time window of customer c;
a s denotes the time of arriving at supplier s;
a c denotes the time of arriving at customer c;
φ 1 denotes the penalty coefficient of arriving early;
φ 2 denotes the penalty coefficient of arriving late;
c v , c v ¯ denotes the transport expense of trucks per kilometer;
c e denotes the expense of one kilowatt per hour(kwh);
| N N k | expresses the number of customers served by electro-tricycle k in one delivery route;
| N N v | expresses the number of suppliers served by truck v in one pickup route;
V k is the decision variable which equal to 1 if vehicle k is chosen to serve customers, 0 otherwise;
λ i expresses the variable transport cost coefficient of the LP i;
q i j denotes the transport quantity from LP i to LP j within a working period;
z i s j denotes the change in service from LP i to j, if supplier s changes its LP from LP i to LP j, and set z i s j = 1 , otherwise set z i s j = 0 , i , j I , s S ;
z i c j denotes the change in service from LP i to j, if customer c changes its LP from LP i to LP j, and set z i c j = 1 , otherwise set z i c j = 0 , i , j I , c C ;
L v denotes the loading capacity of truck v and v ¯ , respectively;
L k denotes the loading capacity of electro-tricycle k;
d max denotes the maximum driving distance with full power;
θ denotes the conversion rate (fuel efficiency) of battery;
q s denotes the pickup quantity from supplier s;
q c denotes the delivery quantity to customer c;
M v denotes the maintenance cost of the truck v and v ¯ , respectively within one year;
M k denotes the maintenance cost of electro-tricycle k within one year;
N i denotes the number of trucks for collecting commodity from suppliers to LP i;
E i denotes the number of electro-tricycles for serving customers in LP i;
N k denotes the number of delivery trips for electro-tricycle k within a working period;
N v denotes the number of pickup trips for truck v within a working period;
N v ¯ denotes the number of shipments for truck v ¯ among LPs within a working period;
T denotes the number of working periods a year;
t i s v denotes the travel time of truck v from LP i to supplier s or from supplier i to s, i I S , s S ;
t i c k denotes the travel time of electro-tricycle k from LP i to customer c or from customer i to customer c, i I C , c C ;
T 1 denotes the maximum en-route time allowed for the truck;
T 2 denotes the maximum en-route time allowed for the electro-tricycle;
d e p i v denotes the departure time of truck v leaving from LP i;
d e p i k denotes the departure time of electro-tricycle k leaving from LP i;
a t v s denotes the time of truck v arriving at supplier s;
a t k c denotes the time of electro-tricycle k arriving at customer c;
z i s is the decision variable which equals to 1 if supplier s is served by LP i, otherwise set z i s = 0 ;
z i c is the decision variable which equals to 1 if customer c is served by LP i, otherwise set z i c = 0 ;
R i expresses the cooperative decision variable, if LP i agrees to cooperate in CFFPDTW, then set R i = 0 , otherwise set R i = 1 ;
G i expresses the government incentive provided to the LP i in the case of cooperation within a working period.

4.1.2. CPDPTW Optimization Framework

CPDPTW optimization procedures of integrating with a collaborative mechanism are shown in Figure 2. At the first stage, a multi-objective linear optimization model is established based on CPDPTW. Then, a composite algorithm consisting of DTDA, an improved K-means clustering algorithm and INSGA-II is presented at the second stage. At the third stage, a cooperative alliance strategy based on improved Shapley value model is proposed and the monotonic path selection strategy is derived to verify the mathematical model and determine the sequence and stability of alliances. LPs play an important role in the procedures. They address the increased diversity in customer demand by cooperating with each other and forming alliances in order to reduce high transportation costs from long-distance transportation. Based on the above considerations, we devise the following model to evaluate the applicability of the cooperative alliance as shown at stage 1 in Figure 2.

4.1.3. Optimization Model Formulation

To achieve the optimization of the pickup and delivery problems with heterogeneous vehicles under time windows, a bi-objective optimization model simultaneously considering the minimum total cost F1 and the number of electro-tricycles F1 is established as follows.
min   F 1 = T C 1 + T C 2 + T C 3 + T C 4 + T C 5
min F 2 = k K | V k | i I c C x i c k
TC1 expresses the total transportation cost that trucks pick up commodity from the suppliers to LPs, while TC2 represents the total transportation costs that electro-tricycles deliver commodity from LPs to the customers.
T C 1 = v V i I S s I S ( d i s × c v × x i s v × N v )
T C 2 = i I C c C I k K [ ( d i c × f k × c e × θ ) × x i c k × N k ]
TC3 expresses the penalty cost for the earliness or delay of the trucks picking up commodity in the suppliers and electro-tricycles delivering commodity to the customers.
T C 3 = i I S s S v V [ max ( e s a s ,   0 ) ] × φ 1 × x i s v + i I C c C k K [ max ( e c a c ,   0 ) ] × φ 1 × x i c k + i I S s S v V [ max ( a s u s ,   0 ) ] × φ 2 × x i s v + i I C c C k K [ max ( a c u c ,   0 ) ] × φ 2 × x i c k
TC4 expresses the transportation cost as the summation of fuel cost and variable transport cost among logistics providers.
T C 4 = i , j I , i j v ¯ V ¯ ( d i j × c v ¯ × θ × N v ¯ ) + i , j I , i j ( q i j × λ i )
TC5 evaluates the maintenance cost of trucks and electro-tricycles with consideration of the discount from government incentives.
T C 5 = i I ( N i × M v T ) + i I ( E i × M k T ) + i , j I , i j ( q i j L v ¯ × M v ¯ T ) i I ( 1 R i ) × G i
Subject to:
i I v V x i s v = 1 , s S
i I k K x i c k = 1 , c C
i I S s I S ( d i s × x i s v ) d max , v V
i C I c C I ( d i c × x i c k ) d max , k K
s I S x i s v s I S x s i v = 0 , v V , i I S
i I C x l c k i I C x c l k = 0 , c I C , k K
i , s I S x i s v | N N v | - 1 , v V
i , c C I x i c k | N N k | - 1 , k K
s S ( q s i I S x i s v ) L v , v V
c C ( q c i I C x i c v ) L k , k K
i I S s S t i s v T 1 , v V
i I C c C t i c k T 2 , k K
d e p t i v + t i s v a t v s , i I S , s S , v V
d e p t i k + t i c k a t k c , i I C , c C , k K
q i j = s S z i s j q s , i , j I , s S
q i j = c C z i c j q c , i , j I , c C
r I S ( x i r v + x r s v ) z i s 1 , i I , s S , v V
w I C ( x i w k + x w c k ) z i c 1 , i I , c C , k K
Constraint (8) specifies that each supplier can be served by only one logistics provider and one truck. Constraint (9) ensures that each customer is served by only one logistics provider. Constraints (10)–(11) ensure that each vehicle travels no more than its maximum distance that can be covered without refueling. Constraints (12)–(13) ensure that flow conservation is achieved at the pickup and delivery processes, respectively. Constraints (14)–(15) specify that the sub-tours can be eliminated on every pickup/delivery route. Constraint (16) guarantees that the sum of supplier goods collected by the truck should be less than the capacity of that truck. Constraint (17) ensures that the electro-tricycles’ capacity meets the total demand of customers on a delivery route. Constraint (18) guarantees that the total travel time during pickup process does not exceed the maximum route time allowed. Constraint (19) guarantees that the total travel time during delivery process does not exceed the maximum route time allowed. Constraints (20)–(21) ensure the arrival of vehicles to suppliers and customers. Constraint (22) specifies the transport quantity from LP i to j, which is equal to the total quantities that are picked up by LP j but previously by LP i. Constraint (23) specifies the transport quantity from LP i to j, which is equal to the total quantities that are delivered by LP j but previously by LP i. Constraints (24)–(25) ensure the routes of LPs (i.e., which suppliers/customers each LP serves) in the pickup process and delivery process, respectively.

4.2. Solution Methodology

4.2.1. Relevant Definitions and Solution Procedure

Our proposed mathematical model reflects the complexity of the problem, and can enhance the necessity of designing a robust and reliable optimization method. For the clarity of the optimization framework, relevant parameters are defined as follows.
P s i z e : Chromosome population size
g max : Maximum number of iterations
C r o s p : Crossover probability
M u t p : Mutation probability
Q : Vehicle capacity
T S : Travel speed
α : Penalty coefficient of early arrival
β : Penalty coefficient of late arrival
G 1 : Periodic incentive for LP1
G 2 : Periodic incentive for LP2
G 3 : Periodic incentive for LP3
G 4 : Periodic incentive for LP4
S 0 : Start point
B : Set of suppliers that have been visited
S / B : Set of suppliers have not been visited
d r : Distance from S 0 to point r, r B
d s ds: Distance from S 0 to point s, s B / S
X : The tabu set used to distinguish commodities with different attributes cannot be delivered together
C : Total cost savings provided if all the facilities form the grand alliance
In addition, we need to introduce the methodology applied to effectively optimize the vehicle routing optimization problem in the proposed pickup and delivery logistics network. In real life, logistics enterprises often aim at minimizing costs and maximizing profits, along with maintaining customer satisfaction. These goals are somehow interrelated to the extent that operating on the minimum possible cost could generate more profit, and making more profit would provide sufficient means to achieve customer satisfaction. In the pickup and delivery logistics network, customer satisfaction is critical, and is defined by their perception of the service and product’s quality. In view of the problems which could emerge in the delivery process, we propose a three-step composite method to solve the CPDPTW. At the first step, an improved K-means clustering algorithm is devised to assign customers to appropriate LPs. The second step employs the DTDA to calculate the shortest routes from LPs to suppliers based on the results from first step, and returns supplier information to the first step. Finally, the INSGA-II algorithm is utilized to optimize the distribution routes, and then returns the customer information to the first step. Figure 3 illustrates the optimization process, and Figure 4 shows the algorithm flowchart. It is worth noting that in this proposed methodology, the three steps iterate until g max , where the optimal solution is found.

4.2.2. Improved K-Means Clustering Algorithm

Cost reduction and profit generation are strong incentives for any entity to cooperate with each other, in modern logistics operations. In the current supply chain structure, transportation costs constitute one major portion of logistics facilities operation costs. Transportation costs are mainly affected by factors like the distance, speed, road quality, etc. [29]. Therefore, the operation cost of the pickup and delivery logistics network can be lowered by reducing the travelled distance. Customer clustering is a procedure where groups of customers in a logistics network are formed based of similar features [27,28]. This paper adopts the proximity degree of customers to each LP as a clustering criterion.
We propose an improved K-means algorithm for clustering [55,56], considering its wide application, simplicity and fast convergence. For the distance function in the improved K-means algorithm, squared Manhattan distance is used in this paper following the convention. As shown in Figure 5, the customers are distributed in a three-dimensional network including geographic coordinates and time axis. The customers can be clustered based on the customer locations and time windows. For further explanation, customers can be first clustered at time range [t1, t2], and then the space range can be considered to determine if the above customers can be clustered.
Our goal in using clustering is to find the initial routes for LPs to reach corresponding customers in a cluster. Therefore, the clustering algorithm is executed only when there are at least two members in the alliance. Parameter o refers to the number of LPs in the alliance. The improved K-means clustering algorithm is shown in Figure 6. It is noticing that a tabu set X consist of locations and time windows can be established at the beginning, and a customer can be considered to join a cluster based on the tabu set X. For example, the customers whose time window [8:30, 9:30] cannot be grouped in the same cluster with customers whose time window is [14:30, 15:30].

4.2.3. Demand and Time-Based Dijkstra Algorithm

In our proposed pickup and delivery logistics network, a pickup operation is executed based on customers clustering. Considering that the number of suppliers is far less than the number of customers, we use the Demand and Time-based Dijkstra Algorithm (DTDA) to address the route optimization problem. The DTDA can be seen as an exact algorithm based on Dijkstra algorithm for solving the pickup process from suppliers [20]. The proposed DTDA needs to cluster the suppliers into several clusters, which accounts for the demands and time windows of customers and ensures that a truck can accommodate the demands in a cluster. Detailed steps are shown in Figure 7.

4.2.4. Improved NSGA-II Algorithm

Owing to the complexity of the CPDPTW, commercial solvers are ineffective in incorporating all the practical factors considered in the problem formulation. Compared with commercial solvers, a heuristic algorithm can offer a series of feasible solutions for practical analysis [57]. The Improved NSGA-II algorithm (INSGA-II) is developed from NSGA and is proposed by Deb et al. [58] in order to complement NSGA’s lack of elitism and speed [41,59,60]. First, NSGA-II employs a fast-non-dominated sorting algorithm, and the computational complexity is much lower than that of NSGA. Second, it introduces an elite strategy to ensure that certain elite individuals are not abandoned during evolution. Finally, it uses comparison operators among individuals in the population, so that individuals in the quasi-pareto domain are representative of the population in the entire Pareto domain, ensuring generalizability of solutions in the quasi-pareto domains.
In this paper, we use NSGA-II in combination with TS to solve our proposed CPDPTW. We have retained the main framework of the NSGA-II algorithm and made some modifications to it. We introduce the initialization part of TS to NSGA-II. TS has a flexible “memory” technology, which can record and select the optimization process already carried out, thereby guiding the next search. We generate the tabu list based on the real problem and then select an initial solution that is more conducive to get the optimal solution. In addition, the sweep algorithm is utilized to enforce the binding of constraints (14)–(15) and increased the quality of solutions in INSGA-II. The detailed steps of the algorithm are shown in Figure 8.
For further explanation, assume that LP1 serves ten customers with a fleet of electric tricycles whose initial arrangement for delivery is shown in Figure 9. According to this figure, the route generation is related to the loading capacity of the electro-tricycle and the time windows of the customers. If the customers’ demands exceed the load capacity of an electric tricycle, or the time windows are unsuitable for accepting service from this electric tricycle, this electric tricycle stops routing to the remaining customers who will be served by the next vehicle. In addition, in our proposed INSGA-II algorithm, we use Partial Mapped Crossover in the genetic operation. We select two chromosomes from the initial population and one point on each chromosome. The two selected points are then exchanged to generate the new offspring chromosomes. Considering the total cost after exchanged, two better chromosomes are selected from the four (parent and children chromosomes) to regenerate the next generation. The procedure of Partial Mapped Crossover is illustrated in Figure 10. For example, after the position of 4 becomes 2, the solution of the route for the new chromosome should be reacquired considering the demands and time windows of 4 and 2.

5. Profit Distribution Strategy

5.1. Improved Shapley Value Model

Many previous studies have demonstrated the Shapley model’s efficiency of profit distribution in multi-participant games [47,51]. In the CPDPTW optimization problem, both suppliers and customers are served by the nearest LP to save costs and increase benefits. Whether a member (an LP) joins the alliance or not depends on the fairness of the profit distribution mechanism. The parameters associated with the profit distribution mechanism in this study are defined as follows:
N: The set of members in the alliance. The number of N’s subset is 2N−1, excluding the null set. All subsets of N are denoted as S, where S N . N is also called the grand alliance.
σ Synergy requirement
V ( S ) : The profits of forming alliance S
C 0 ( i ) : Costs of i without coalition, i I
C ( S ) : The total cost of alliance S
π ( i ) : Rank of i in sequence π , i I
η ( i , π , u ) : The cost reduction percentage to participator i on step u along sequence π
Participants tend to hope that their contribution to the alliance will be reasonably rewarded. Therefore, to ensure the stability of the alliance, participants need a reasonable and effective profit distribution mechanism. Improved Shapley value model presents an effective profit distribution mechanism based on the contribution of participants under cooperative game theory. Equation (26) means to allocate the benefits or cost savings obtained by the alliance to the participants who agree to cooperate.
φ i ( N , V ) = S N , i S [ ( | S | 1 ) ! ( | N | | S | ) ! | N | ! ] × [ V ( S ) V ( S { i } ) ]
In Equation (26), N represents the set of all members in the alliance. S is a subset of N. The term V ( S ) V ( S { i } ) indicates the marginal contribution of participant i when i joins the alliance. The improved Shapley value model has four properties: efficiency, symmetry, dummy and additivity. These properties guarantee the rationality of benefit distribution and the stability of the alliance. In fact, the purpose of an alliance in the improved Shapley value model is to gain more profit, which is expressed by the synergy requirement σ . The larger the value of σ , the greater the benefits that the alliance organizer receives. Correspondingly, a larger value of σ will decrease the benefits to other members of the alliance and consequently destabilize the alliance. The value of V ( S ) can be calculated by formula (27).
V ( S ) = ( 1 σ ) max { i S C 0 ( i ) C ( S ) , 0 }
Equation (27) states that an alliance is beneficial only if the participation of a member would decrease the total cost compared to this member not participating. Otherwise, V ( S ) will be set to 0.

5.2. Strictly Monotonic Path Principles

Strictly monotonic path (SMP) selection strategy is a method for evaluating alliance stability given a profit distribution scheme. Different alliance sequences show different levels of stability. The cost reduction percentage η ( i , π , u ) can be calculated by Equation (28).
η ( i , π , u ) = ϕ i ( π ( μ ) μ , v ) C 0 ( i ) , π ( i ) μ
SMP can be described as: when a new participant joins the alliance, the cost reduction percentages of the original members in the alliance will increase. When there are multiple eligible alliance sequences, we will choose the optimal alliances based on the SMP selection strategy. The specific process is presented as in Figure 11.

6. Case Study

6.1. Algorithms Optimization Comparison

To assess the applicability of the proposed algorithm to LNPD optimization, we run and test our INSGA-II algorithm, the MOPSO algorithm [60] and the NSGAII-CW algorithm [51]. We use 20 different datasets, which are illustrated in Table 2. To evaluate their effectiveness, we compare the optimal total cost of delivery, the optimal number of vehicles and computation time across these three algorithms. We calibrated some parameters of INSGA-II to improve its performance. p s i z e = 150 is the population size, g max = 1000 represents the maximum number of iterations; c r o s p = 0.9 and m u t p = 0.1 represent the parameters of crossover and mutation, respectively. The vehicle capacity Q = 180 , travel speed T S = 40 , M v = 100 , α = 0.05 , and β = 0.1 . The optimal solutions from the three algorithms with randomly generated datasets are shown in Table 3.
Table 3 lists the optimal solution and the computation time returned by each algorithm for each data instance. For cost minimization, INSGA-II performs better than NSGAII-CW and MOPSO in most cases. For vehicle number, the results indicate that the INSGA-II, NSGAII-CW and MOPSO have the same optimization effectiveness. However, in terms of computation time, NSGAII-CW tends to need more time to converge than the other two algorithms. INSGA-II has slightly higher computation time than MOPSO but outperforms the latter in cost minimization. The t-test results and p-values for comparing the minimum costs in NSGAII-CW and MOPSO to the minimum cost in INSGA-II are shown at the bottom of Table 3, which shows that INSGA-II reaches significantly lower total cost than the other two algorithms.

6.2. Data Description

To evaluate the applicability of the proposed optimization model in the real world, a case study with regard to the proposed logistics network optimization mechanism is conducted in Chongqing, China. In the actual pickup and delivery logistics network of the city, we selected 4 logistics providers, 10 suppliers and 180 customers, whose geographical distributions are highly mixed (instead of clustered) with one another, to illustrate the customer allocation problem. The layout of logistics network before optimization is shown in Figure 12. Triangles refer to suppliers. Diamonds refer to LP1 and the customers it serves. Crosses, squares and stars are used to symbolize LP2, LP3 and LP4, a well as the customers they each serve, respectively. Table 4 shows the characteristics of all logistics facilities. Logistics service overlap pickup and delivery can be found in the original logistics network. Therefore, further study on logistics network optimization based on the collaborative mechanism is necessary. In addition, Table 8 shows the characteristics of all logistics facilities.

6.3. Optimization Results

In this section, we present the optimization setup in the case study by setting the initial values for the parameters. The parameters in the objective function are: L v = 1500 , L k = 180 , f k = 0.04997 , c e = 0.04297 , c v = 1.2 , M v = 150 M k = 100 , T = 52 , N t = 5 . To encourage logistics facilities to cooperate, we assume that the government provide LPs who join the alliance with incentives every working period: G 1 = 2145 , G 2 = 2370 , G 3 = 1849 , and G 4 = 2291 . The total cost savings provided all the facilities form the grand alliance is C = 8656 .
In this study, a working period consists of five working days. INSGA-II algorithm is used to reassign customers to the LPs and calculate the total cost of a working period. Cost savings need to be distributed to each participant in the alliance via the improved Shapley value model. Table 5 shows the optimization results including the initial cost, optimized cost, demand and cost savings for each possible alliance scenario. Table 6 shows the customers served by each supplier. The initial supplier and customer assignments to LPs and the routes for pickup from suppliers and delivery to corresponding customers are listed in Table 7. Table 8 shows the optimal suppliers and Customers’ assignment in the grand alliance.
In comparison with the initial customer allocation, the cooperative network in Table 12 shows that the number of customers served by per LP has changed. In the non-optimal network, each LP has to serve each supplier, while the number of suppliers served by each LP obviously decreased after optimization. For example, before optimization, LP1 served 15 suppliers (S1-S15), whereas LP1 served only four suppliers (S1, S12, S13 and S9) after optimization. This condition greatly reduces the cost. The routes for pickup and delivery are also optimized in the grand alliance scenario. The logistics network will be simplified as the unnecessary routing is minimized, which will also greatly reduce travel distances and thus transportation costs.

6.4. Improved Shapley Model Application and Coalition Sequence Selection

To ensure long-term cooperation and the stability of the alliance in the CPDPTW, the benefits and cost savings should be reasonably allocated to each LP [61]. In this study, the synergy requirement value σ = 0 which means the alliance organizers take no profit generated by the alliance. Thus, all the profits are shared by the logistics providers. All non-empty alliances from the combinations of LPs are shown in Table 9.
Table 9 shows the cost savings for each alliance and how the savings are distributed among the LPs in the alliance, evaluated based on the improved Shapley value model. The same LP may benefit differently from various alliances. For example, the cost saving of LP1 operating alone is $15446, after sharing vehicles and resources with LP2, the saved cost for LP1 becomes $32503. By contrast, a situation exists where the benefits of existing members will decrease if new members join. For example, after LP2, LP3, and LP4 form an alliance, the addition of LP1 changes the cost saving for LP4 from $35,018 to $34,295. Therefore, comprehensive decision-making requires that the profits to other members must be guaranteed with the addition of new members. In other words, the stability of the alliance depends on the changes in members’ profits before and after new members join. Figure 13. shows the percentage of saved costs in the process of forming a grand alliance and a feasible alliance sequence that maintains the alliance stability is illustrated in Figure 14.
The examination of alliance sequences is critical to the profit distribution strategy and to participants’ willingness to become member. In other words, the order in which members are added to the alliance affects the distribution of profits and the satisfaction of SMP principles. Nevertheless, following the examination of every possible combination, the SMP-based alliance sequence is π 1 = { L P 1 , L P 3 , L P 4 , L P 2 } . All possible alliance sequences satisfying SMP principles are calculated based on Equation (28) and shown in Table 10.
From Table 11, in the design of the coalition, we have considered that LP1 joined the alliance first followed by LP3. The percentages of operation cost reduced for LP1 and LP3 are 66.6% and 71.5%, respectively. LP4 is the third member joining the coalition, raising the cost reduction percentage for LP1, LP3 and LP4 to 74.9%, 77.5% and 69.9% respectively. The final sequence for the grand alliance {LP1, LP3, LP4, LP2} yields a cost reduction percentage of {80.7%, 85.0%, 75.5%, 79.0%}, respectively.
Figure 15 shows the cost change for every LP before and after resource sharing in a collaborative logistics network. The cost for every logistics provider substantially decreased when LPs cooperate and join the alliance. For instance, the cost for LP1 before choosing to cooperate is $42,905, while the cost after cooperation is $34,623. The reduction is caused by collaborations including resource sharing, vehicle sharing and customer service sharing among LPs. The result suggests that the proposed cooperation strategy is effective.

6.5. Alliance Stability

In this section, we examine the accuracy of the improved Shapley value model to identify an optimal profit distribution mechanism. Four different profit distribution methods are chosen to calculate the profit to each LP: the improved Shapley value model, the Minimum Cost Remaining Savings model (MCRS), the Cost Gap Allocation (CGA) model and the Equal Profit Method (EPM) model. To determine the performance of each method, the result of each profit distribution mechanism is compared to the core center [50]. According to the snowball theory [48, 50, 16], the strategy closest to the core is the best. Equation (29) is used to calculate the position of the core center where v ( N ) is the total cost savings from the grand alliance, β represents an alliance member, and α is a parameter for controlling the scope of the core. Table 12 shows the profit distribution results for each LP under these distribution mechanisms. Figure 16 illustrates the core position and corresponding distances.
v ( N ) v ( N { β } ) v ( N ) × α + k Z k i y k = v ( N { β } )
In Figure 13, the numbers in parentheses are the distribution of profit for LP1, LP2, LP3 and LP4 in order. However, the use of the improved Shapley value model for LP3 is the lowest, but the improved Shapley value model is the closest distance to the core center. Therefore, the improved Shapley value is the closest to the core center and thus the most appropriate profit distribution strategy. This result implies that individual benefits are not supposed to be the most important consideration in a cooperative logistics network. Decision makers should be aware of the overall impacts of the cooperative network.

6.6. Analysis of Two Coalition’s Network

In multi-echelon logistics network optimization, collaboration is a common strategy to reduce cross-transportation and the complexity of logistics networks. Studies on cooperation in logistics network optimization mostly consider the formation of a single alliance. However, in real life, multiple alliances may also be formed in a logistics network. Therefore, this paper considers a case of two alliances. The SMP-based alliance sequences are shown in Table 13.
As shown in Table 13, the order in which members join the alliance has an impact on the benefits of the alliance. For LP2 and LP4, the situation where LP4 joins the alliance after LP2 can save more cost than where LP4 joins the alliance before LP2. Similarly, for LP1 and LP3, the situation where LP3 joins the alliance first can save much more cost than where LP1 joins the alliance first. Therefore, two alliances π 1 = { L P 2 , L P 4 } and π 3 = { L P 1 , L P 3 } will be formed in the end.
Figure 17 shows the percentages of cost reductions during the formation of the two alliances. After the new members join, the percentage of cost reduction increases dramatically in both alliances, proving that the solution follows the SMP rules. In the final two alliances, the cost reduction percentage reaches 75.5%, 74.2%, 71.5% and 66.6% for LP4, LP2, LP3 and LP1, respectively, after LP4 teamed with LP2 and LP3 teamed with LP1. This is a notable increase in the cost reduction percentages for LP2 and LP1, up from 36.0% (for LP2 and LP1) before forming the alliances.

6.7. Discussion

To select the optimal alliance strategy and enhance the long-term stability of the cooperative logistics network, we compare the benefits of each participant in the two-alliance scenario and single-alliance scenario, respectively. Table 14 presents the allocated profits to the four logistics providers considered in our case study.
As shown in Table 14, the two-alliance strategy generates a total profit of $124,829. By contrast, the grand-alliance strategy produces more benefits with a total profit of $138,724 than the two-alliance strategy. For individual LPs, joining a sub-alliance vs. joining the grand alliance also presents different benefits. For example, LP1 gains more benefits ($35,182) by joining a sub-alliance with LP3 than joining a grand alliance with a profit of ($34,665). For LP3, however, the situation is the opposite, with a grand alliance being more profitable than a sub-alliance with LP1. This situation will prompt LP3 to give up the opportunity to form a sub-alliance with LP1 and choose to join the grand alliance, thereby leaving LP1 with no choice but to join the grand alliance as well. Therefore, the logistics network will ultimately be stable when the grand alliance is formed.
In recent years, collaboration between logistics facilities has played an important role in optimizing of enterprise logistics supply chain. Further sharing of transportation resources can save additional costs. In addition, local government incentives for cooperation indicate that the governments are willing to achieve sustainable development in their administrative regions. Transportation activities are among of the main factors contributing to regional economic development as well as environmental issues. Hence, they should be organized efficiently. Therefore, encouraging the formation of alliances benefits logistics enterprises and many members of society. However, forming a grand alliance may present some management challenges. For example, the alliance may meet the strict monotonous path principle in the short term. However, due to the dynamic nature of modern logistics services and the changes in operation costs over time, participants may face serious challenges in internal financial and operational crises. Therefore, the distribution of benefits will be affected and the stability of the grand alliance will be threatened. As a precautionary measure, different situations must be assessed before starting negotiations. The grand alliance should be divided into groups, and the potential risks associated with individual facilities in the network before making a final decision.

7. Conclusions

This paper studies the impact of cooperation among logistics providers on logistics networks with pickup and delivery activities under time windows. One- and two-alliance strategies are studied to assess each participant’s willingness to minimize costs and maximize profits. A three-stage cooperation strategy is proposed to describe the problem and optimize the cost of non-empty alliances. At the first stage, this study establishes a multi-objective programming model to minimize the number of vehicles and the total cost for the collaborative logistics network. A composite algorithm, which consists of improved k-means clustering algorithm, DTDA and INSGA-II, Dijkstra algorithm is used to calculate the travel cost of trucks. To simplify the calculation, the improved clustering algorithm is utilized to assist LPs to find the initial routes. INSGA-II is presented to optimize the routes of electro-tricycles in the delivery process. At the third stage, a cooperative alliance strategy based on improved Shapley value model is proposed and the optimal profit allocation strategy is obtained in the logistics network. Because different alliance sequences have various cost reduction percentages, the SMP theory is used for optimal sequence selection.
To test the collaboration mechanism and CPDPTW implementation in real life, an empirical analysis is conducted on a pickup and delivery logistics network in Chongqing, China. The total cost change from before to after implementing collaboration mechanism is $138724. A comparison among the INSGA-II, NSGAII-CW and MOPSO algorithms reveals that INSGA-II performs outstandingly among the three in terms of solution quality. In selecting the best profit distribution scheme, we find that the improved Shapley value method returns the profit distribution scheme closer to the core center than MCRS, CGA and EPM. In addition, we share profits to each member based on the assumption that the synergistic demand is zero. Through the analysis of two alliance strategies including one grand alliance and two sub alliances respectively and the formation of the grand alliance is the most desirable for LPs.
From a practical point of view, the optimization of the CPDPTW provides a strategic collaboration mechanism for supplier and LPs for the improvement of logistics transportation network. On the one hand, the formation of a collaboration mechanism achieves the additional profits among the cooperative members in the entire transportation system. On the other hand, for suppliers and customers, a coordinated logistics network with cooperation can provide more timely services to meet the timeliness requirements of suppliers and customers. Considering the collaboration mechanism and optimization strategy proposed in this paper, the reductions of cost and vehicle number not only generate great economic benefits in reducing resource consumption, but also produce great positive externalities to the environment, thus providing favorable theoretical support for profit seekers. The discussion about the influence of different profit allocation methods on the stability of the alliance will provide the best profit allocation strategy for the cooperative members, and thus guarantee the sustainability of the cooperation. In addition, reasonable logistics network resource configuration through cooperation will propel the sustainable development of an intelligent transportation system and further promote the establishment of a resource-friendly society. Therefore, a reasonable collaboration mechanism can serve as a reference for logistics companies and local governments to further cooperate and establish better cooperation strategies.
This work aims to study the CPDPTW, a special case of LNPD, which has so far been insufficiently investigated by existing research. Future work can be conducted in the following directions: (1) Considering a multi-echelon pickup and delivery logistics network and studying how to achieve coordination between multi-level facilities. (2) Considering the cooperation among suppliers based on the study of cooperation among logistics providers. (3) Considering vehicle sharing during pickup and delivery processes, which can make full use of vehicle resources. (4) Introducing state-space-time networks into a pickup and delivery logistics network and considering their impacts on logistics cost.

Author Contributions

Y.W. and X.G. conceived and designed the experiments; Y.Y. performed the experiments; Y.W. and Y.Y. analyzed the data; H.W., Y.L. and M.X. contributed reagents/materials/analysis tools; Y.W. and Y.Y. wrote the paper. All the authors approved the final manuscript.

Funding

This research was funded by National Natural Science Foundation of China, grant number [71871035], [71402011] and [71471024], and Humanity and Social Science Youth Foundation of Ministry of Education of China, grant number [18YJC630189].

Acknowledgments

The authors would like to express our appreciation for the valuable comments made by two anonymous reviewers and the academic editor, which helped us to improve the quality of this paper. This research is supported by National Natural Science Foundation of China (Project No. 71871035, 71402011, 71471024), Humanity and Social Science Youth Foundation of Ministry of Education of China (18YJC630189), China Postdoctoral Science Foundation (Project No. 2017T100692 and 2016M600735), Chongqing Municipal Education Commission Science and Technology Research Project (KJQN201800723). 2017 Postdoctoral Science Foundation of Sichuan Province, and this research is also supported by 2018 Chongqing Liuchuang Plan Innovation Project (cx2018111), and Program for the Philosophy and Social Science Research of Higher Learning Institutions of Shanxi (201803066).

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Winshang.com. Fresh Retail Market Status Survey. 2018. Available online: http://news.winshang.com/html/063/7022.html (accessed on 12 April 2018).
  2. Hsiao, Y.H.; Chen, M.C.; Chin, C.L. Distribution planning for perishable foods in cold chains with quality concerns: Formulation and solution procedure. Trends Food. Sci. Technol. 2017, 61, 80–93. [Google Scholar] [CrossRef]
  3. Cai, X.Q.; Chen, J.; Xiao, Y.B.; Xu, X.L. Optimization and coordination of fresh product supply chains with freshness-keeping effort. Prod. Oper. Manag. 2010, 19, 261–278. [Google Scholar] [CrossRef]
  4. Li, H.Q.; Liu, Y.Y.; Jian, X.R.; Lu, Y.R. The two-echelon distribution system considering the real-time transshipment capacity varying. Transp. Res. Part B Methodol. 2018, 110, 239–260. [Google Scholar] [CrossRef]
  5. Akyol, D.E.; Koster, R.B.M. Determining time windows in urban freight transport: A city cooperative approach. Transp. Res. E-Logist. 2018, 118, 34–50. [Google Scholar] [CrossRef]
  6. Sawik, B.; Faulin, J.; Pérez-Bernabeu, E. A Multicriteria Analysis for the Green VRP: A Case Discussion for the Distribution Problem of a Spanish Retailer. Transp. Res. Procedia 2017, 22, 305–313. [Google Scholar] [CrossRef]
  7. Gutierrez, A.; Dieulle, L.; Labadie, N.; Velasco, N. A multi-population algorithm to solve the VRP with stochastic service and travel times. Comput. Ind. Eng. 2018, 125, 144–156. [Google Scholar] [CrossRef]
  8. Khayyat, M.; Awasthi, A. An intelligent multi-agent based model for collaborative logistics systems. Transp. Res. Procedia 2016, 12, 325–338. [Google Scholar] [CrossRef]
  9. Deng, Y.R.; Zheng, Y.; Li, J.P. Route optimization model in collaborative logistics network for mixed transportation problem considered cost discount based on GATS. J. Amb. Intell. Humaniz. Comput. 2019, 10, 409–416. [Google Scholar] [CrossRef]
  10. Wang, Z. Delivering meals for multiple suppliers: Exclusive or sharing logistics service. Transp. Res. E-Logist. 2018, 118, 496–512. [Google Scholar] [CrossRef]
  11. Hafezalkotob, A.; Makui, A. Cooperative maximum-flow problem under uncertainty in logistic networks. Appl. Math. Comput. 2015, 250, 593–604. [Google Scholar] [CrossRef]
  12. Govindan, K.; Jafarian, A.; Khodaverdi, R.; Devika, K. Two-echelon multiple-vehicle location–routing problem with time windows for optimization of sustainable supply chain network of perishable food. Int. J. Prod. Econ. 2014, 152, 9–28. [Google Scholar] [CrossRef]
  13. Bal, A.; Satoglu, S.I. A goal programming model for sustainable reverse logistics operations planning and an application. J. Clean Prod. 2018, 201, 1081–1091. [Google Scholar] [CrossRef]
  14. Bortolini, M.; Galizia, F.G.; Mora, C.; Botti, L.; Rosano, M. Bi-objective design of fresh food supply chain networks with reusable and disposable packaging containers. J. Clean. Prod. 2018, 184, 375–388. [Google Scholar] [CrossRef]
  15. Lozano, S.; Moreno, P.; Adenso-Díaz, B.; Algaba, E. Cooperative game theory approach to allocating benefits of horizontal cooperation. Eur. J. Oper. Res. 2013, 229, 444–452. [Google Scholar] [CrossRef]
  16. Feng, F.; Pang, Y.S.; Lodewijks, G.; Li, W.F. Collaborative framework of an intelligent agent system for efficient logistics transport planning. Comput. Ind. Eng. 2017, 112, 551–567. [Google Scholar] [CrossRef]
  17. Wang, Y.; Ma, X.L.; Liu, M.W.; Gong, K.; Liu, Y.; Xu, M.Z.; Wang, Y.H. Cooperation and profit allocation in two-echelon logistics joint distribution network optimization. Appl. Soft Comput. 2017, 56, 143–157. [Google Scholar] [CrossRef]
  18. Liu, T.; Luo, Z.X.; Qin, H.; Lim, A. A branch-and-cut algorithm for the two-echelon capacitated vehicle routing problem with grouping constraints. Eur. J. Oper. Res. 2018, 266, 487–497. [Google Scholar] [CrossRef]
  19. Ebrahimi, H.; Tadic, M. Optimization of dangerous goods transport in urban zone. Decis. Mak. Appl. Manag. Eng. 2018, 1, 131–152. [Google Scholar] [CrossRef]
  20. Sedeño-Noda, A.; Raith, A. A Dijkstra-like method computing all extreme supported non-dominated solutions of the biobjective shortest path problem. Comput. Oper. Res. 2015, 57, 83–94. [Google Scholar] [CrossRef]
  21. Horváth, M.; Kis, T. Solving resource constrained shortest path problems with LP-based methods. Comput. Oper. Res. 2016, 73, 150–164. [Google Scholar] [CrossRef] [Green Version]
  22. Zhang, Y.L.; Shen, Z.J.M.; Song, S.J. Lagrangian relaxation for the reliable shortest path problem with correlated link travel times. Transp. Res. Part B Methodol. 2017, 104, 501–521. [Google Scholar] [CrossRef]
  23. Andrade, R.C.; Saraiva, R.D. An integer linear programming model for the constrained shortest path tour problem. Electron. Notes Discret. Math. 2018, 69, 141–148. [Google Scholar] [CrossRef]
  24. Bektaş, T.; Gouveia, L.; Martínez-Sykora, A.; Salazar-González, J. Balanced vehicle routing: Polyhedral analysis and branch-and-cut algorithm. Eur. J. Oper Res. 2019, 273, 452–463. [Google Scholar] [CrossRef]
  25. Tu, W.; Fang, Z.; Li, Q.; Shaw, S.L.; Chen, B.Y. A bi-level voronoi diagram-based metaheuristic for a large-scale multi-depot vehicle routing problem. Transp. Res. E-Logist. 2014, 61, 84–97. [Google Scholar] [CrossRef]
  26. Wang, Z.; Lin, W.H. Incorporating travel time uncertainty into the design of service regions for delivery/pickup problems with time windows. Expert Syst. Appl. 2016, 72, 207–220. [Google Scholar] [CrossRef]
  27. Narasimha, K.V.; Kivelevitch, E.; Sharma, B.; Kumar, M. An ant colony optimization technique for solving min–max multi-depot vehicle routing problem. Swarm Evol. Comput. 2013, 3, 63–73. [Google Scholar] [CrossRef]
  28. Wang, Y.; Ma, X.L.; Lao, Y.T.; Wang, Y.H. A fuzzy-based customer clustering approach with hierarchical structure for logistics network optimization. Expert Syst. Appl. 2014, 41, 521–534. [Google Scholar] [CrossRef]
  29. Mesa-Arango, R.; Ukkusuri, S.V. Demand clustering in freight logistics networks. Transp. Res. E-Logist. 2015, 81, 36–51. [Google Scholar] [CrossRef]
  30. Dragomir, A.G.; Nicola, D.; Soriano, A.; Gansterer, M. Multi-depot pickup and delivery problems in multiple regions: A typology and integrated model. J. Adv. Transp. 2017, 25, 569–597. [Google Scholar]
  31. Wang, Y.; Zhang, J.; Assogba, K.; Liu, Y.; Wang, Y.H. Collaboration and transportation resource sharing in multiple centers vehicle routing optimization with delivery and pickup. Knowl. Based Syst. 2018, 160, 296–310. [Google Scholar] [CrossRef]
  32. Wang, Y.; Assogba, K.; Liu, Y.; Ma, X.; Xu, M.; Wang, Y. Two-echelon location-routing optimization with time windows based on customer clustering. Expert Syst. Appl. 2018, 104, 244–260. [Google Scholar] [CrossRef]
  33. Xu, X.; Ding, S.; Shi, Z. An improved density peaks clustering algorithm with fast finding cluster centers. Knowl. Based Syst. 2018, 158, 65–74. [Google Scholar] [CrossRef]
  34. Musolino, G.; Polimeni, A.; Vitetta, A. Freight vehicle routing with reliable link travel times: A method based on network fundamental diagram. Transp. Lett. 2018, 10, 159–171. [Google Scholar] [CrossRef]
  35. Hemmelmayr, V.C.; Cordeau, J.F.; Crainic, T.G. An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics. Comput. Oper. Res. 2012, 39, 3215–3228. [Google Scholar] [CrossRef] [PubMed]
  36. Breunig, U.; Schmid, V.; Hartl, R.F.; Vidal, T. A large neighbourhood based heuristic for two-echelon routing problems. Comput. Oper. Res. 2016, 76, 208–225. [Google Scholar] [CrossRef] [Green Version]
  37. Soysal, M.; Çimen, M. A simulation based restricted dynamic programming approach for the green time dependent vehicle routing problem. Comput. Oper. Res. 2017, 88, 297–305. [Google Scholar] [CrossRef]
  38. Liu, R.; Tao, Y.Y.; Hu, Q.Y.; Xie, X.L. Simulation-based optimisation approach for the stochastic two-echelon logistics problem. Int. J. Prod. Res. 2016, 55, 187–201. [Google Scholar] [CrossRef]
  39. Belgin, O.; Karaoglan, I.; Altiparmak, F. Two-echelon vehicle routing problem with simultaneous pickup and delivery: Mathematical model and heuristic approach. Comput. Ind. Eng. 2018, 115, 1–16. [Google Scholar] [CrossRef]
  40. Chami, Z.A.; Manier, H.; Manier, M.A.; Chebib, E. An advanced GRASP-HGA combination to solve a multi-period pickup and delivery problem. Expert. Syst. Appl. 2018, 105, 262–272. [Google Scholar] [CrossRef]
  41. Nedjati, A.; Izbirak, G.; Arkat, J. Bi-objective covering tour location routing problem with replenishment at intermediate depots: Formulation and meta-heuristics. Comput. Ind. Eng. 2017, 110, 191–206. [Google Scholar] [CrossRef]
  42. Afshar-Nadjafi, B.; Afshar-Nadjafi, A. A constructive heuristic for time-dependent multi-depot vehicle routing problem with time-windows and heterogeneous fleet. J. King Saud Univ. Eng. Sci. 2017, 29, 29–34. [Google Scholar] [CrossRef] [Green Version]
  43. Li, J.; Li, Y.; Pardalos, P.M. Multi-depot vehicle routing problem with time windows under shared depot resources. J. Comb. Optim. 2016, 31, 515–532. [Google Scholar] [CrossRef]
  44. Naccache, S.; Côté, J.F.; Coelho, L. The multi-pickup and delivery problem with time windows. Eur. J. Oper. Res. 2018, 269, 353–362. [Google Scholar] [CrossRef]
  45. Meng, Q.; Zhuo, F.; Eglese, R.; Qiong, T. A Tabu Search algorithm for the vehicle routing problem with discrete split deliveries and pickups. Comput. Oper. Res. 2018, 100, 102–116. [Google Scholar] [Green Version]
  46. Allahyari, S.; Salari, M.; Vigo, D. A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem. Eur. J. Oper. Res. 2015, 242, 756–768. [Google Scholar] [CrossRef]
  47. Cruijssen, F. Supplier-initiated outsourcing: A methodology to exploit synergy in transportation. Eur. J. Oper. Res. 2010, 207, 763–774. [Google Scholar] [CrossRef]
  48. Comi, A.; Schiraldi, M.M.; Buttarazzi, B. Smart urban freight transport: Tools for planning and optimising delivery operations. Simul. Model Pract. Theory 2018, 88, 48–61. [Google Scholar] [CrossRef]
  49. Frisk, M.; Göthe-Lundgren, M.; Jörnsten, K.; Rönnqvistab, M. Cost allocation in collaborative forest transportation. Eur. J. Oper. Res. 2010, 205, 448–458. [Google Scholar] [CrossRef] [Green Version]
  50. Dai, B.; Chen, H.X. Profit allocation mechanisms for carrier collaboration in pickup and delivery service. Comput. Ind. Eng. 2012, 62, 633–643. [Google Scholar] [CrossRef]
  51. Kumoi, Y.; Matsubayashi, N. Vertical integration with endogenous contract leadership: Stability and fair profit allocation. Eur. J. Oper. Res. 2014, 238, 221–232. [Google Scholar] [CrossRef]
  52. Kamiyama, N.; Kawahara, R.; Hasegawa, H. Optimum profit allocation in coalitional VoD service. Comput. Netw. 2013, 57, 3081–3097. [Google Scholar] [CrossRef]
  53. Wang, Y.; Ma, X.L.; Li, Z.B.; Liu, Y.; Xu, M.Z.; Wang, Y.H. Profit Distribution in Collaborative Multiple Centers Vehicle Routing Problem. J. Clean. Prod. 2017, 144, 203–219. [Google Scholar] [CrossRef]
  54. Wu, Q.; Ren, H.; Gao, W.; Ren, J. Benefit allocation for distributed energy network participants applying game theory based solutions. Energy 2017, 119, 384–391. [Google Scholar] [CrossRef]
  55. Markova, I.; Varone, S.; Bierlaire, M. Integrating a heterogeneous fixed fleet and a flexible assignment of destination depots in the waste collection VRP with intermediate facilities. Transp. Res. Part B Methodol. 2016, 84, 256–273. [Google Scholar] [CrossRef] [Green Version]
  56. Coelhoa, V.N.; Grasas, A.; Ramalhinho, H.; Coelho, I.M.; Souza, M.J.F.; Cruz, R.C. An ILS-based algorithm to solve a large-scale real heterogeneous fleet VRP with multi-trips and docking constraints. Eur. J. Oper. Res. 2016, 250, 367–376. [Google Scholar] [CrossRef] [Green Version]
  57. Leng, L.L.; Zhao, Y.W.; Wang, Z.; Zhang, J.L.; Wang, W.L.; Zhang, C.M. A Novel Hyper-Heuristic for the Biobjective Regional Low-Carbon Location-Routing Problem with Multiple Constraints. Sustainability 2019, 11, 1596. [Google Scholar] [CrossRef]
  58. Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T. A fast and elitist multi objective genetic algorithm: NSGA-II. IEEE Trans. Evolut. Comput. 2002, 6, 182–197. [Google Scholar] [CrossRef]
  59. Su, C.; Shi, Y.M.; Dou, J.P. Multi-objective optimization of buffer allocation for remanufacturing system based on TS-NSGAII hybrid algorithm. J. Clean. Prod. 2017, 166, 756–770. [Google Scholar] [CrossRef]
  60. Lin, Y.H.; Huang, L.C.; Chen, S.Y.; Yu, C.M. The optimal route planning for inspection task of autonomous underwater vehicle composed of MOPSO-based dynamic routing algorithm in currents. Appl. Ocean Res. 2018, 75, 178–192. [Google Scholar] [CrossRef]
  61. Wang, Y.; Peng, S.G.; Assogba, K.; Liu, Y.; Wang, H.Z.; Xu, M.Z.; Wang, Y.H. Implementation of Cooperation for Recycling Vehicle Routing Optimization in Two-Echelon Reverse Logistics Networks. Sustainability 2018, 10, 1358. [Google Scholar] [CrossRef]
Figure 1. Illustration of the CPDPTW optimization through collaboration.
Figure 1. Illustration of the CPDPTW optimization through collaboration.
Sustainability 11 03492 g001
Figure 2. Schematic of the CPDPTW optimization framework.
Figure 2. Schematic of the CPDPTW optimization framework.
Sustainability 11 03492 g002
Figure 3. Illustration of the optimization process.
Figure 3. Illustration of the optimization process.
Sustainability 11 03492 g003
Figure 4. Algorithm flowchart for CPDPTW.
Figure 4. Algorithm flowchart for CPDPTW.
Sustainability 11 03492 g004
Figure 5. Illustration for K-means clustering algorithm in a three-dimensional network.
Figure 5. Illustration for K-means clustering algorithm in a three-dimensional network.
Sustainability 11 03492 g005
Figure 6. Improved K-means clustering algorithm process.
Figure 6. Improved K-means clustering algorithm process.
Sustainability 11 03492 g006
Figure 7. Demand and time-based Dijkstra algorithm process.
Figure 7. Demand and time-based Dijkstra algorithm process.
Sustainability 11 03492 g007
Figure 8. INSGA-II algorithm process.
Figure 8. INSGA-II algorithm process.
Sustainability 11 03492 g008
Figure 9. Chromosome encoding and route decoding illustration.
Figure 9. Chromosome encoding and route decoding illustration.
Sustainability 11 03492 g009
Figure 10. Process of Partial-Mapped Crossover.
Figure 10. Process of Partial-Mapped Crossover.
Sustainability 11 03492 g010
Figure 11. SMP algorithm process.
Figure 11. SMP algorithm process.
Sustainability 11 03492 g011
Figure 12. Suppliers and Logistics providers and customers’ locations.
Figure 12. Suppliers and Logistics providers and customers’ locations.
Sustainability 11 03492 g012
Figure 13. Cost reduction percentage.
Figure 13. Cost reduction percentage.
Sustainability 11 03492 g013
Figure 14. Cost reduction percentage diagram for the grand coalition.
Figure 14. Cost reduction percentage diagram for the grand coalition.
Sustainability 11 03492 g014
Figure 15. Cost change before and after sharing.
Figure 15. Cost change before and after sharing.
Sustainability 11 03492 g015
Figure 16. Core center and distance comparison diagram.
Figure 16. Core center and distance comparison diagram.
Sustainability 11 03492 g016
Figure 17. Cost reduction percentage diagram for two alliances. (a) Sub-alliance for LP4 and LP2; (b) Sub-alliance for LP3 and LP 1.
Figure 17. Cost reduction percentage diagram for two alliances. (a) Sub-alliance for LP4 and LP2; (b) Sub-alliance for LP3 and LP 1.
Sustainability 11 03492 g017
Table 1. Comparison before and after optimization.
Table 1. Comparison before and after optimization.
Cost ($)Transportation, Pickup and Delivery Costs ($)Cooperation ($)Penalty ($)Total ($)The Number of Vehicles ($)
Non-collaboration1970--70026709
collaboration540260508507
Table 2. Description of instances.
Table 2. Description of instances.
InstanceNumber of CustomersNumber of Logistics Providers
1–4908,6,4,2
5–81108,6,4,2
9–1213010,8,6,4
13–1615010,8,6,4
17–2020012,10,8,6
Table 3. Algorithms optimization results comparison.
Table 3. Algorithms optimization results comparison.
InstanceINSGA-IINSGAII-CWMOPSO
Cost ($)No. of VehiclesTime (s)Cost ($)No. of VehiclesTime (s)Cost ($)No. of VehiclesTime (s)
1375715207.3461515208.4665015223.7
2475216173.4462516176.2520116167.2
3695214134.3649714130.4766314145.2
440,7001389.341,8001387.142,0311384.2
5571718211.4753418213.3862618214.3
6705815178.6679315180.2798216159.7
7961115153.212,81815155.314,60515140.3
852,1281497.259,9961496.454,3921591.9
9744420284.2789220288.5807721271.5
10744820249.2808820253.6914020240.8
1112,15618206.515,25518205.314,12018179.8
1218,48716143.220,74416142.721,24517138.1
13800622272.4887722273.5956022242.7
1410,27120234.610,60520236.311,39320221.3
1517,82119197.320,55219196.421,94819181.2
1624,94918153.529,11018156.232,10118139.7
1718,24727374.519,38827371.720,95727357.8
1816,84525306.817,35425308.218,40925321.7
1917,39825285.118,81424284.617,95724274.5
2021,04925252.322,53625253.423,31625246.3
Average15,54019210.217,19519210.817,76919202.1
t-test −3.86 −5.98
p-value 1.04 × 10−3 9.27 × 10−6
Table 4. Characteristics of logistics facilities.
Table 4. Characteristics of logistics facilities.
FacilitiesNumber of Allocated Customer UnitsSymbol
S1–S15\ Sustainability 11 03492 i001
LP150 Sustainability 11 03492 i002
LP237 Sustainability 11 03492 i003
LP338 Sustainability 11 03492 i004
LP455 Sustainability 11 03492 i005
Table 5. Comparison between initial and optimized network over one working period.
Table 5. Comparison between initial and optimized network over one working period.
AlliancesInitialOptimizedV(t)
Cost ($)Demand(kg)Cost ($)Demand(kg)
{LP1}42,905447,20027,459483,60015,446
{LP2}47,406410,80030,340353,60017,066
{LP3}36,992374,40023,675182,40013,317
{LP4}45,820426,40029,325525,20016,495
{LP1LP2}90,311858,00025,169837,20065,141
{LP1LP3}79,897821,60024,861666,00055,036
{LP1LP4}88,725873,60030,1601,008,80058,565
{LP2LP3}84,398785,20025,611536,00058,787
{LP2LP4}93,226837,20023,433878,80069,793
{LP3LP4}82,812800,80029,135707,60053,676
{LP1LP2LP3}127,3031,232,40023,6581,019,600103,645
{LP1LP2LP4}136,1311,284,40026,8441,362,400109,287
{LP1LP3LP4}125,7171,248,00032,8801,191,20092,837
{LP2LP3LP4}130,2181,211,60029,4171,061,200100,801
{LP1LP2LP3LP4}173,1231,658,80034,3991,658,800138,724
Table 6. Distribution of customers’ orders from each supplier.
Table 6. Distribution of customers’ orders from each supplier.
SupplierCustomer Unit Allocation
S1C7 C10 C19 C21 C30 C31 C73 C96 C143 C145 C163
S2C4 C45 C51 C58 C80 C91 C92 C94 C97 C146 C149 C151 C178
S3C34 C42 C44 C59 C63 C66 C68 C95 C103 C117 C122 C127 C154 C155 C177
S4C11 C16 C17 C41 C82 C85 C93 C100 C123 C126 C173 C176 C77 C113
S5C8 C29 C35 C52 C62 C65 C98 C102 C162 C175
S6C5 C12 C25 C60 C61 C101 C106 C112 C140 C141 C144 C153 C161
S7C27 C43 C56 C83 C86 C105 C118 C125 C135 C137 C150 C156 C165
S8C24 C55 C75 C76 C78 C90 C107 C131 C134 C136 C139 C164
S9C13 C18 C39 C79 C89 C104 C120 C129 C138 C166
S10C1 C2 C14 C20 C28 C33 C46 C49 C99 C110 C121 C147 C15 C32
S11C40 C54 C70 C71 C72 C124 C130 C142 C148 C158 C170 C179 C180 C169
S12C3 C36 C38 C47 C81 C88 C128 C171 C172 C174
S13C22 C37 C48 C84 C87 C115 C119 C133 C152 C167 C109
S14C26 C64 C69 C74 C111 C114 C157 C23 C159
S15C6 C9 C50 C53 C57 C67 C108 C132 C160 C168 C116
Table 7. Initial suppliers and Customers’ assignment.
Table 7. Initial suppliers and Customers’ assignment.
Logistics ProviderSuppliers and Customers AllocationSymbol
LP1S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12 S13 S14 S15 Sustainability 11 03492 i001
C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C13 C14 C15 C16 C17 C18 C19 C20 C21 C22 C23 C24 C25 C26 C27 C28 C29 C30 C31 C32 C33 C34 C35 C36 C37 C38 C39 C40 C41 C42 C43 C44 C45 C46 C47 Sustainability 11 03492 i002
LP2S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12 S13 S14 S15 Sustainability 11 03492 i001
C48 C49 C50 C51 C52 C53 C54 C55 C56 C57 C58 C59 C60 C61 C62 C63 C64 C65 C66 C67 C68 C69 C70 C71 C72 C73 C74 C75 C76 C77 C78 C79 C80 C81 C82 C83 C84 C85 C86 C87 C88 C89 C90 Sustainability 11 03492 i003
LP3S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12 S13 S14 S15 Sustainability 11 03492 i001
C91 C92 C93 C94 C95 C96 C97 C98 C99 C100 C101 C102 C103 C104 C105 C106 C107 C108 C109 C110 C111 C112 C113 C114 C115 C116 C117 C118 C119 C120 C121 C122 C123 C124 C125 C126 C127 C128 C129 C130 C131 C132 C133 Sustainability 11 03492 i004
LP4S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12 S13 S14 S15 Sustainability 11 03492 i001
C134 C135 C136 C137 C138 C139 C140 C141 C142 C143 C144 C145 C146 C147 C148 C149 C150 C151 C152 C153 C154 C155 C156 C157 C158 C159 C160 C161 C162 C163 C164 C165 C166 C167 C168 C169 C170 C171 C172 C173 C174 C175 C176 C177 C178 C179 C180 Sustainability 11 03492 i005
Table 8. Suppliers and Customers’ assignment in the grand coalition.
Table 8. Suppliers and Customers’ assignment in the grand coalition.
Logistics ProviderSuppliers and Customers Allocation
LP1S1 S12 S13 S9
C1 C2 C3 C7 C10 C13 C17 C18 C19 C20 C27 C29 C30 C31 C32 C33 C34 C35 C36 C37 C38 C39 C40 C46 C47 C48 C51 C52 C63 C81 C84 C85 C97 C100 C108 C109 C110 C112 C113 C114 C115 C128 C155 C160 C161 C162 C165 C166 C167 C176
LP2S15 S14 S11 S5 S10
C6 C8 C9 C14 C15 C21 C22 C23 C26 C28 C49 C50 C53 C54 C57 C58 C62 C64 C65 C66 C67 C68 C69 C86 C87 C88 C89 C101 C111 C126 C127 C156 C163 C164 C172 C177 C180
LP3S4 S2
C4 C11 C16 C41 C44 C45 C59 C60 C61 C77 C79 C80 C82 C83 C91 C92 C93 C94 C95 C96 C98 C99 C102 C103 C105 C107 C129 C130 C131 C132 C141 C151 C154 C157 C169 C170 C175 C178
LP4S7 S8 S3 S6
C5 C12 C24 C25 C42 C43 C55 C56 C70 C71 C72 C73 C74 C75 C76 C78 C90 C104 C106 C116 C117 C118 C119 C120 C121 C122 C123 C124 C125 C133 C134 C135 C136 C137 C138 C139 C140 C142 C143 C144 C145 C146 C147 C148 C149 C150 C152 C153 C158 C159 C168 C171 C173 C174 C179
Table 9. Profit distribution in Two-echelon logistics distribution network (unit: USD).
Table 9. Profit distribution in Two-echelon logistics distribution network (unit: USD).
AlliancesV(t) φ ( s , v )
{LP1}15446(15446,0,0,0)
{LP2}17066(0,17066,0,0)
{LP3}13317(0,0,13317,0)
{LP4}16495(0,0,0,16495)
{LP1LP2}65141(32503,32638,0)
{LP1LP3}55036(27607,0,27429,0)
{LP1LP4}58565(29239,0,0,29326)
{LP2LP3}58787(0,31268,27519,0)
{LP2LP4}69793(0,35182,0,34611)
{LP3LP4}53676(0,0, 25249,28427)
{LP1LP2LP3}103645(34989,36932,31723,0)
{LP1LP2LP4}109287(33745,39427,0,36115)
{LP1LP3LP4}92837(32002,0,29469,31366)
{LP2LP3LP4}100801(0,37858,27925,35018)
{LP1LP2LP3LP4}138724(34623,40315,29212,34574)
Table 10. Feasible cooperation sequence based on SMP principle.
Table 10. Feasible cooperation sequence based on SMP principle.
π 1 = { L P 1 , L P 3 , L P 4 , L P 2 }
Player i LP1LP3LP4LP2
η ( i , π , 1 ) 36.0%
η ( i , π , 2 ) 66.6%71.5%
η ( i , π , 3 ) 74.9%77.5%69.9%
η ( i , π , 4 ) 80.7%85.0%75.5%79.0%
π 2 = { L P 3 , L P 1 , L P 4 , L P 2 }
Player i LP3LP1LP4LP2
η ( i , π , 1 ) 36.0%
η ( i , π , 2 ) 71.5%66.6%
η ( i , π , 3 ) 77.5%74.9%69.9%
η ( i , π , 4 ) 85.0%80.7%75.5%79.0%
π 3 = { L P 1 , L P 4 , L P 3 , L P 2 }
Player i LP1LP4LP3LP2
η ( i , π , 1 ) 36.0%
η ( i , π , 2 ) 67.0%57.7%
η ( i , π , 3 ) 74.9%69.9%77.5%
η ( i , π , 4 ) 80.7%75.5%79.0%85.0%
π 4 = { L P 4 , L P 1 , L P 3 , L P 2 }
Player i LP4LP1LP3LP2
η ( i , π , 1 ) 36.0%
η ( i , π , 2 ) 57.7%67.0%
η ( i , π , 3 ) 69.9%74.9%77.5%
η ( i , π , 4 ) 75.5%80.7%79.0%85.0%
Table 11. Optimal cooperation sequence based on SMP principle.
Table 11. Optimal cooperation sequence based on SMP principle.
π 1 = { L P 1 , L P 3 , L P 4 , L P 2 }
Player i LP1LP3LP4LP2
η ( i , π , 1 ) 36.0%
η ( i , π , 2 ) 66.6%71.5%
η ( i , π , 3 ) 74.9%77.5%69.9%
η ( i , π , 4 ) 80.7%85.0%75.5%79.0%
Table 12. Profit distributions according to MCRS, Shapley, CGA and EPM.
Table 12. Profit distributions according to MCRS, Shapley, CGA and EPM.
MCRSImproved Shapley Value ModelCGAEPM
LP134,11934,62333,49335,255
LP237,80140,31541,06138,952
LP329,57229,21130,16629,437
LP437,23034,57434,00335,080
Table 13. Two sub-coalition sequences based on SMP.
Table 13. Two sub-coalition sequences based on SMP.
π 1 = { L P 2 , L P 4 } π 2 = { L P 1 , L P 3 }
Player i LP2LP4LP1LP3
η ( i , π , 1 ) 36.0% 36.0%
η ( i , π , 2 ) 74.2%75.5%66.6%71.5%
π 3 = { L P 4 , L P 2 } π 4 = { L P 3 , L P 1 }
Player i LP4LP2LP3LP1
η ( i , π , 1 ) 36.0% 36.0%
η ( i , π , 2 ) 75.5%74.2%71.5%66.6%
Table 14. Comparison of different network scenarios.
Table 14. Comparison of different network scenarios.
Player i Two Sub-AlliancesGrand Alliance
LP135,18234,665
LP234,61139,861
LP327,60729,903
LP427,42934,295
Total124,829138,724

Share and Cite

MDPI and ACS Style

Wang, Y.; Yuan, Y.; Guan, X.; Wang, H.; Liu, Y.; Xu, M. Collaborative Mechanism for Pickup and Delivery Problems with Heterogeneous Vehicles under Time Windows. Sustainability 2019, 11, 3492. https://0-doi-org.brum.beds.ac.uk/10.3390/su11123492

AMA Style

Wang Y, Yuan Y, Guan X, Wang H, Liu Y, Xu M. Collaborative Mechanism for Pickup and Delivery Problems with Heterogeneous Vehicles under Time Windows. Sustainability. 2019; 11(12):3492. https://0-doi-org.brum.beds.ac.uk/10.3390/su11123492

Chicago/Turabian Style

Wang, Yong, Yingying Yuan, Xiangyang Guan, Haizhong Wang, Yong Liu, and Maozeng Xu. 2019. "Collaborative Mechanism for Pickup and Delivery Problems with Heterogeneous Vehicles under Time Windows" Sustainability 11, no. 12: 3492. https://0-doi-org.brum.beds.ac.uk/10.3390/su11123492

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop