یک روش تجزیه دقیق برای صرفه جویی در پیکاپ تعاونی و تحویل بر اساس گردش برنامه ریزی شده و توزیع سود An exact decomposition method to save trips in cooperative pickup and delivery based on scheduled trips and profit distribution

1. Introduction Cooperation is a powerful way to reduce operational cost of pickup and delivery service. Before participants agree to join in a cooperation scheme, an estimation of the profit brought by cooperation must be available. The problems in the transportation have been studied (Caputo and Mininno, 1996; Frisk et al., 2010; Audy et al., 2011; Lozano et al., 2013). These studies calculated cost saving brought by cooperation by integrating the original data of all participants. However, sometimes participants do not like to publish the customer’s detailed information in order to maintain business sensitive information, but it is acceptable to open the scheduled results because the scheduled results do not show sensitive customer’s information. As a consequence, a method should be developed to estimate the profit brought by cooperation based on scheduled results. This paper is originally motivated by the cost reduction brought by a real cooperative pickup and delivery service, i.e., “picking up and delivering customers to airport service” (PDCA). In real PDCA, a case of customer’s detailed information is shown in Table 1. The customer’s detailed information was provided by the companies performing PDCA, such as Zhongshan, Shuntian, and Jiantong Inc. in Shenyang in China (Tang et al., 2008, 2014; Yu et al., 2014, 2016). Location means the vertical and horizontal coordinates of customer’s preferred location to pick up the customer. Customer’s detailed information can reveal company’s business sensitive information. For example of Table 1, we can know location (50, 70) is the important customer point. Thus, other companies can lure customers in thus important customer points. However, a company may publish the scheduled result when joining in cooperation. A scheduled result of Table 1 can be shown in Table 2. As shown in Table 2, the scheduled result can conceal some sensitive business information, such as location of picking up and the number of customers in location. Thus, it is acceptable for a company to open the scheduled trips to participate cooperation. Before participating cooperation, each company wonders the exact profit distributed by cooperation. Therefore, the first objective of the study is to estimate the exact profit brought by cooperation based on trip scheduled results. The second objective is to obtain the fair profit distribution based on exact Shapley value to stabilize coalition. The remainder of this research is organized as following. The literature review on cooperative cases in the transportation, profit distribution, and picking up and delivering customers to airport service (PDCA) is given in the second section. The third section constructs the mathematical model minimizing trips of cooperation. We define cooperative trip set and prove that if no cooperative trip set exists the trips cannot be saved by cooperation. For a two-trip cooperative trip set, we obtain the exact solution by enumerating all feasible cooperative cases. For a cooperative trip set with K trips, we propose a novel decomposition method to obtain the exact solution by decomposing it to at most K-1 two-trip cooperative trip sets. Section four develops a based-on-decomposition algorithm to accurately calculate saved trips by cooperation. The computational complexity of the exact algorithm is O(N), where N is the total number of used trips in non-cooperative companies. The fifth section demonstrates the profit distribution based on Shapley value. The Shapley value can be easily obtained by the exact algorithm. Section six gives the extensive computational cases from PDCA and states how to compute exactly Shapley value based on the decomposition algorithm. In the last section conclusions and future research are given. The results of extensive experiments are given in Appendices A–C.