In the age of globalization, great emphasis has been placed on integration throughout the supply chain and consequently, building alliances appears to be a successful way to improve logistics e ciency. In this paper, we consider a distribution system where a set of retailers order a single product from a unique supplier. In such an environment, we identify the cooperative game theory approach as a feasible toolbox to deal with the pro t allocation problem. In order to provide a guide for collaboration companies, we design e ective and e cient cost allocation methods to ensure the continuity of the collaboration. We propose a method and subsequently this core allocation is compared to well-known methods. We discuss the main advantages and drawbacks of the proposed solution. We observe that our proposed method is computationally e cient and can be implemented to solve real-life sized problems. A numerical example is presented to show the usefulness of this approach.
In today's marketplace, logistics collaboration is increasingly emerging as a new opportunity for cost saving through internal chain coordination. Logistics collaborations are categorized as vertical, horizontal, or lateral [Simatupang and Sridharan, 2002]. This research paper focuses on one form of coordination in logistics, namely horizontal logistics collaboration, which is considered to be an e ective way of reducing logistics costs [Lozano et al., 2013]. Horizontal cooperation is de ned as \bundling the transport requirements of companies operating at the same level of the supply chain, which have similar or complementary transportation needs" [Vanovermeire et al., 2014]. [Cruijssen et al., 2007] expressed a more explicit de nition as \an active collaboration between two or more rms that operate at the same level of the supply chain and perform a comparable logistics function on the landside".
A major problem of collaboration is to decide how to share costs, pro ts or resources [Guajardo and Ronnqvist, 2016]. Cooperative game theories are widely used in logistics as a sharing mechanism, this includes the problems of transportation planning [Frisk et al., 2010], traveling salesmen [Sun et al., 2015], vehicle routing [Krajewska et al., 2008], joint distribution [Dai and Chen, 2012] and inventory [O zener et al., 2013]. In an attempt to nd a solution to these problems, game theory is presented in this paper as a feasible tool to deal with pro t allocation.
A Joint Replenishment Problem (JRP) is de ned as the coordination of multiple items that are jointly ordered and shipped by using a single truck [Goyal, 1974]. Since it became signi cant in practice, the JRP has grown in importance over the past decade and is of interest to researchers [Arkin et al., 1989, Porras and Dekker, 2008, Qu et al., 2015].
This paper examines the subject of cooperation in a JRP for one-supplier multi-retailer systems under the same cost structure. JRP is a model of the supply chain formed by one supplier and n retailers to deal with optimizing the shipment of goods through shared warehouses. In this situation, the strategic decision is how to allocate the pro ts (costs) among partners is an important factor in the design of the coalition. The cost allocation problem may be modelled naturally as a cooperative game. Hence, in this research, we used game theory solution concepts to divide the cost among the members of the coalition. More speci cally, to examine the question of cost distribution, rst we focus on some of the most central solution concepts in cooperative game theory e.g. equal allocation, Shapley value. Furthermore, by integrating cooperative game theory with the joint replenishment problem we propose a new method of cost allocation. The method is based on di erent distribution keys e.g. volume, capacity. The proposed method is accurate, fair and realistic as compared with conventional methods.
The rest of the paper is organized as follows. Section 2 presents the standard de nitions from cooperative game theory, that are applied in the proposed approach for cost allocation in JRP. Section 3 presents the solution methodology. Section 4 illustrates numerical examples and also presents the comparisons between solution methods. Finally, Section 5 concludes this paper and proposes perspectives for further research. 2
A cooperative game is a pair G = (N; ), characterized by a given set of players N = f1; 2; :::; jN jg and the characteristic function . N is called the grand coalition. The characteristic function : 2N ! R assigns to every nonempty coalition S N a value (S), with (;) = 0: The characteristic function may be interpreted as pro ts or costs. When coalition S cooperates, the total cost C(S) is generated (S) =
X C(i) i2S
C(S); for all S
N:
Some important properties of cooperative games are listed below in order to derive insights concerning the application of solution concepts.
De nition 1. A coalition S is pro table if and only if (S) 0: De nition 2. The game G = (N; ) is superadditive if the value satis es the following equation (S [ T ) (S) + (T ) for all coalitions
S; T
N and
S \ T = ;: (1)
Equation (1) indicates whether two players have an incentive to cooperate and is focused in most applications of cooperative game theory on logistics collaborations e.g. [Krajewska et al., 2008, Frisk et al., 2010, Lozano et al., 2013].
i is the cost(pro ts) allocated to player i; i 2 N: This vector = ( 1; 2; :::; jNj) is an element of the jN j dimensional linear space RN :. In a budget balanced cost allocation, the total cost allocated to the players is equal to the total cost incurred by the grand coalition (X i( ) = (N )). In a stable cost allocation, the total cost i2N allocated to a subset of players should be less than or equal to the total cost incurred by that subset (S): The set of cost allocations that are budget balanced and stable is called the core of a collaborative game. De nition 3. The core of coalitional game G = (N; ) is de ned as
Core(N; ) = nx : X i( ) = (N ) ^ X i( ) (S); for all S
N o: i2N
i2S
The core is the most attractive solution concept in cooperative game theory. It is a set of valid, e cient allocations that cannot be improved upon by a coalition. For a collaborative game, the core may be empty, that is, a balanced budget with stable cost allocations may not be achievable.
The major problem in cooperative game theory is how to allocate the costs of the grand coalition among the players. The allocation vector satis es a variety of properties, some of them are listed below. Coalitional game G = (N; ) is e cient if Pi2N i( ) = (N ), this property ensures that the total value of the grand coalition is distributed among the players, individual rationality if 8i2N i( ) would get individually,
(fig), it guarantees that each player should at least get what the player collective rationality if 8i2S i( ) (S); ; S N: If this property is not satis ed, then the players have an incentive to drop out of the grand coalition in order to gain a higher payo allocation.
The payo s that secures e ciency and individual rationality are called the imputation. No partner would accept an allocation that has no imputation, therefore most of the solution concepts are a set of imputations. Now we present the de nition of di erent fairness properties represented by well-known allocation rules such as equal allocation, the Shapley value [Shapley, 1953], the Nucleolus [Schmeidler, 1969] and the Gately point [Gately, 1974]. 2.1
Firstly, we introduce the equal allocation rule which awards an equal portion to each player and is de ned by the equation (N ) i( ) = : n In general the proportional method is easy to implement due to the fact that it does not take into account the e ect of synergies among the players. 2.2
One of the earliest and most important solution concepts in coalitional game theory is the Shapley value [Shapley, 1953], that is de ned based on marginal contribution.
De nition 4. The marginal contribution of player i to a coalition S is (S [ fig) (S): De nition 5. The Shapley value is de ned by the formula i( ) =
X S Nnfig jSj!(n jSj n! 1)! ( (S [ fig) (S)); for all i 2 S:
The Shapley value can be explained as the average marginal contribution in which each individual would make it to the grand coalition if it were to form an individual a time. Shapley value allocations may not lie in the core of the game, in cases where the core is non-empty. 2.3
In addition to the Shapley value another solution concept that is studied in cooperative game theory is the Nucleolus [Schmeidler, 1969]. When we compute the Nucleolus of a game, we lexicographically maximize the minimal gain, the di erence between the stand alone cost of a subset and the total cost allocated to that subset, over all the subsets of the collaboration.
Consider x 2 G(N; ). For each such x and for each S 2 2N n fN; ;g, de ne the excess of coalition S at x as that measures the \degree of happiness" of each coalition S. De ne the vector e(x) = (e(x))S2sN nfN;;g: This is the vector of all excesses of the di erent coalitions at x.
eS (x) = x(S)
(S); De nition 6. Let r(x) be a vector arranged in order of decreasing magnitude. Then, for any pair of payo vectors x and y, for the rst entry z in which they di er, x is smaller than y in the lexicographical order. Let the lexicographical order be denoted by lxm : De nition 7. The Nucleolus of the game (N; ) is nc(N; ) = fx 2 X(N; ) : there does not exists y 2 X(N; )); e(y) lxm e(x)g:
The Nucleolus is the imputation that maximizes the minimal excess and determines such an allocation that the smallest satisfaction is maximized. And hence, it is ensured that the least satis ed coalition is as satis ed as possible. 2.4
In addition to the Shapley value and the Nucleolus, an interesting solution concept for coalitional games is the Gately point [Gately, 1974].
De nition 8. The Gately point is de ned by the formula
Gi( ) = P
(N ) j2N ( (N ) (N n fig) (N n fjg)) (N ):
This concept attempts to ensure that the most valuable coalition members retain the most importance. 3
Let us consider the example of a group of retailers who decide to cooperate by ordering jointly via a single large order. The mathematical model is developed based on the following assumptions the group of retailers can only make orders for full truckload delivery, the demand of each retailer is deterministic, and there is no shortage, the transportation cost is not relevant to the transportation quantity.
The notions and parameters of the model are summarized in Table 1.
N = f1; 2; :::ng Disti
i Hi Di A Vi Qi set of retailers travel distance cost per kilometer holding cost demand of retailer i
xed ordering cost volume of i retailer' product order size of i retailer
In the optimal replenishment strategy under full truckload (FTL) shipments (Vi Qi = CAPi), the
carriers have a similar cost structure. Various cost functions in FTL have been proposed in the literature
CO(S) = A
X Fi; i2S
CH(S) = PPii22SS HFii FS = X Di Vi =
Capi i2S
X Fi; i2S ;
S
N; i 2 f1; 2; :::; ng; ;
S However, from the retailers point of view, the function used in the above scheme does not provide player satisfaction in terms of all of the costs incurred. As a result a more advanced cost function is needed in order to evaluate the impact of transportation costs, de ned by (2), with the collaboration mechanism CT (S) = X iDisti; ;
S
Consequently, the total average cost of the coalition ; and transportation cost, as follows
C(S) = A o|rderi{nzg cost }
P Xi2S Fi + Pi2S Fi h|olding cos}t {z i2S Hi +
X iDisti i2S tra|nspor{taztion c}ost Lemma 1. The cost savings function C(S) is a pro table supperadditive function. Proof. The cost saving function is pro table if for every S Let S 6= ; then from (3) we have the following
Pi2S C(i): = CO(S) + CH(S) + CT (S); i 2 f1; 2; :::; ng: (3) Let S and T be two disjointed and non-empty coalitions, then C(S) + C(T ) =
C(S) =
A Pi2S Fi + PPi2S Hi + Pi2S iDisti = APPi2 Si2CS (Fi)i:+ Pii22SSFHFiii + Pi2S iDisti = =
C(S [ T ):
P A Pi2S[T Fi + P A(Pi2S Fi + Pi2T Fi) + PPPii22SS HFii + PP
i2S Hi + P i2T Fi A(Pi2S Fi + Pi2T Fi) + Pi2S Fi + Pii22TT FHii + P i2S[T Hi + P
i2T Hi + P i2S[T iDisti i2S[T Fi i2S iDisti + Pi2T iDisti i2S iDisti + Pi2T iDisti
Pi2S C(i) then (S)
0: This implies that every coalition S is pro table.
The idea is de ned, based on the cost de ned by (3), a pro t allocation, namely the Ordering Holding Transportation solution (OHT-solution). The total holding and transportation cost is reduced for each retailer i when they order jointly.
De nition 9. The OHT-solution i( ), that assigns to each retailer i in coalition S; ; savings allocation is de ned by the formula S
N; their cost Hi Fi
Hi Pj2S Fj
; = Pi2N ( i(1 )Disti + HFii FHNi ) == (1(N ); ) Pfoir2Nall iiD2isNti: + Pi2N HFii
Hi Fi
Hi
FN In this section, an illustrative example of four retailers (label A; B; C; D) supplied by the same manufacturer is presented and analyzed. The travel distance, holding and ordering cost, product volume, vehicle capacity, demand of each retailer, and ordering frequency are shown in Table 2. Notice that retailer D o ers the lowest total cost. In addition, it has the lowest transportation cost. However, retailer D also o ers one of the highest ordering costs. This prevents the existence of a dominant position in the process of grand coalition formation. The total cost for each possible coalition S and their savings ratio are shown in Table 3. The grand coalition fA; B; C; Dg is stable, which means that no sub-coalition has an incentive to leave the grand coalition. In addition, for the CS function the monotonicity and superadditivity properties hold.
In section 3 a new method of allocating of pro ts was introduced, the so-called ordering-holding-transportation solution (OHT-solution). This solution belongs to the core of the game, which implies that the solution is stable in the sense that no player is motivated to break o and form their own coalition. Table 4 indicates the comparison of costs allocated to each of the retailers A; B; C; D based on each method. The results in this study were obtained from equal allocation, Shapley value, Nucleolus, Gately point and OHT-solution. For each allocation concept, the Cost Saving is calculated according to the de nition and formula presented in section 2. Net Cost equals the Stand-alone Cost minus Cost Savings. The total cost saving is 885. The Savings Ratio equals the Cost Savings divided by the Net Cost.
These results show clearly that it is worthwhile cooperating in a single-supplier multi-retailer problem with full truckload shipments in order to save costs. The cost savings range from 22% to 38:2%: We can see that individual C gets the maximum pro t according to the OHT-solution while retailer C has also makes the largest contribution to the grand coalition (equal 2 433:32). Hence, it is easy to conclude that retailer C should prefer the OHT-solution. In contrast, an equal allocation would probably cause the coalition to be disbanded since retailer C gains smaller savings than retailer D but it still contributes to the grand coalition. The Shapley value and Nucleolus, which is less practical and may be more costly, may be rejected by any of them. However, it must be stressed that all of the concepts (except for equal allocation) are fair in the sense that the retailers who contribute more are paid more. 5
This paper examines a set of cost allocation methods which depends on the situation whereby there are multiple decision makers who obtain bene ts by full truckload shipments cooperation. Motivated by this problem, the primary focus of the paper is to make use of well-known game theoretical concepts and introduce new allocation rules that arise from the practical situation (OHT - solution). In this paper the equal allocation, Shapley value, Nucleolus, and Gately point have been used to investigate their e ectiveness in a fair cost sharing between companies. We nd that under the methods proposed, companies have an incentive to collaborate since this results in reduced costs. In addition, we also explored the issues concerning the detailed comparison of the proposed allocation methods. The results indicated that the methods proposed can lead to a fair cost allocation, since a method such as OHT-solution may establish an adequate incentive for collaboration. Further, the OHTsolution is a suitable allocation since it is designed especially for this kind of cooperation.
Further research may take a number of di erent directions. First of all, it is worth to discuss the applicability of the proposed approach to dynamic distribution systems. Second direction is to consider multiple suppliers. Another possible direction is to extend the model by considering multiple objectives, such as the supply chain risk. Finally, an assumption of the approach discussed in the paper is that all the trips are full-truck-load. The long-term goal is to elaborate the paper to consider less-than-truck load scenarios. However, this approach may increase the model's computational complexity.