Incitements for transportation collaboration by cost allocation

Abstract

In this paper, we focus on how cost allocation can be used as a means to create incentives for collaboration among companies, with the aim of reducing the total transportation cost. The collaboration is assumed to be preceded by a simultaneous invitation of the companies to collaborate. We make use of concepts from cooperative game theory, including the Shapley value, the Nucleolus and the EPM, and develop specific cost allocation mechanisms aiming to achieve large collaborations among many companies. The cost allocation mechanisms are tested on a case study that involves transportation planning activities. Although the case study is from a specific transportation sector, the findings in this paper can be adapted to collaborations in other types of transportation planning activities. Two of the cost allocation mechanisms ensure that any sequence of companies joining the collaboration represents a complete monotonic path, that is, any sequence of collaborating companies is such that the sequences of allocated costs are non-increasing for all companies.

1 Introduction

Collaboration in transportation has become the subject of a growing area of research, resulting in the development of new transportation planning models. Some areas where collaborative transportation solutions are desirable or necessary are countryside freight transportation, supply chain operations, and sector-specific collaborations. In such applications, the objective is mainly to increase vehicle load factors and to reduce the total transportation cost. Another area of growing interest, in which collaboration in transportation may occur, is city logistics (Thompson and Taniguchi 1999; Taniguchi 2014), alternatively urban freight transportation, where the main objectives, besides efficiency of the transportation system, are to reduce externalities such as congestion, pollution and noise. Other externalities of urban freight transportation are visual intrusion, vibrations and accidents.

In this paper we study collaborative transportation planning in a specific sector, the forest industry, where shipments and companies are considered as components of an integrated logistics system, which is to be optimized. Examples of such logistics systems are, e.g., collaboration between forest companies (Frisk et al. 2010) and alliances of cargo carriers (Houghtalen 2007). When the integrated logistics system is optimized, the total transportation cost normally decreases compared to the sum of the costs of the non-collaborative transportation plans. Thus, the question arises of how the overall costs and gains should be allocated among the companies. This is the cost allocation problem. This is a rather crucial question because it implies incentives for the companies to take part in the collaboration. This question has been treated in different ways in the literature. In Frisk et al. (2010), a cost allocation method, the Equal Profit Method (EPM), is proposed, such that relative cost savings are as equal as possible for all participating companies, see Sect. 2.3. In Houghtalen (2007), models for capacity exchange prices as incentives for collaboration are proposed. In Agarwal and Ergun (2010), cost allocation with side payments is studied in the context of maritime transport, namely liner shipping. In Dai and Chen (2012), three profit allocation mechanisms based on the Shapley value are proposed. The profit allocation mechanisms ensure stable profit allocations and are tested on a carrier collaboration problem with pick and delivery requests and time window constraints. In Vanovermeire and Sörensen (2014), it is argued that companies with large flexibilities should be rewarded; however, considering two-partner coalitions, flexibility is not usually rewarded. Thus, they propose an alternative approach. More examples can be found in the survey by Guajardo and Rönnqvist (2016).

The size of a collaboration may be crucial, but larger collaborations are generally more difficult to manage. In Guajardo and Rönnqvist (2015), the total cost allocated among collaborating companies is minimized with respect to an upper bound on the size of a collaboration. A second situation of how coalitions are formed is considered in Frisk et al. (2010). Here it is assumed that the collaboration of the companies is decided upon a priori, although it is possible that one company or a coalition of companies can do better, in terms of savings, on their own. In the considered application, however, it is shown that it is possible to allocate costs in such a way that no company, or coalition of companies, can do better on their own. In Cruijssen et al. (2005), a third situation is studied, where the a priori decision is replaced by a negotiation, where each company is invited to the collaboration by means of a cost saving offer. A logistics service provider proactively selects a group of shippers with large synergy potential. It is crucial to decide in what sequence the companies are to be invited because different sequences allow for different cost saving offers to the companies.

In this paper we consider a fourth situation in which companies simultaneously are invited to collaborate, and it is not possible to predetermine which of them will accept or in which order they will join. To our knowledge, the application of the cost allocation problem for this situation is new. The hypothetical scenario is a platform or internet application on which transportation companies may announce their transportation activities in hopes of finding collaborations in order to reduce their total transportation cost. This is plausible considering the trend of digitalization. In this paper we focus on the problem of allocating the total transportation cost among the stakeholders. That is, we do not discuss how such a system might work or how it might be administrated. We simply assume it exists and is working as intended.

The main focus of this paper is on the system design, in which the overall aim is to achieve system optimal solutions by reducing the total transportation cost. This is usually the case when many companies collaborate, that is, large collaborations exist. The aim of this paper is to provide as good conditions as possible to achieve large collaborations. This is done by choosing a suitable cost allocation mechanism, see Sect. 4.2, for providing cost saving offers to the companies. The cost saving offers should incentivize collaboration. We study which effects different cost allocation mechanisms, based on concepts from cooperative game theory, have on the cost saving offers and, thereby, on the incentive to collaborate.

Collaborative planning in logistics operations is studied in Audy et al. (2012), and their case study is based on the same data as the case study of this paper. Companies are joining a collaboration sequentially. They study how the leading coalition affects the full collaboration’s final profit allocation. Four business models are tested. Two of the business models allocate costs and two business models allocate savings. One of the business models is reallocating the costs each time a new company is joining, and the other three business models are allocating costs or savings based on previous allocations. A result from not reallocating costs or savings is a diversion in the final cost or saving allocation, that is, the sum of all costs or savings allocated to each company, is strongly dependent on the leading coalition. In our paper, the total transportation cost is reallocated. In spite of the approaches being different, it is interesting to highlight the similarities and differences in the results of the two studies, see Sect. 6.3.

With the aim of providing as good conditions as possible to achieve large collaborations, we study the number of complete monotonic paths (MPs), as defined in Cruijssen et al. (2005), generated by the use of different cost allocation mechanisms. A complete MP represents a sequence of companies that all agree to collaborate. A more formal definition of an MP is presented in Sect. 4.1. In order to provide a cost saving offer to each company, the cost allocation problem is solved each time a new company considers joining. We assume that the new company accepts, and is accepted by, the other already committed companies if no company is allocated a higher cost compared to the previous cost allocation.

The contribution of this paper is a number of cost allocation mechanisms for providing cost saving offers to companies joining a collaboration sequentially, with the aim to achieve large collaborations. Two of the cost allocation mechanisms ensure that any sequence of companies joining the collaboration represent a complete MP, that is, any sequence of collaborating companies is such that the sequences of allocated costs are non-increasing for all companies.

The outline of this paper is the following. In Sect. 2 we describe some basics from cooperative game theory. In Sect. 3 we elaborate on different ways to achieve collaboration. In Sect. 4 we describe MPs, a mathematical definition is presented, and the cost allocation mechanisms are studied. Section 5 consists of a description of a case study and, for this paper, relevant data from that study. In Sect. 6 we present the results based on full path enumeration for different proposed cost allocation mechanisms. The number of complete MPs is presented as well as details on the number of complete MPs, starting with certain companies. We also report on to what extent the inclusion of certain companies results in an incomplete monotonic path (IMP). In Sect. 7 we summarize the computational results and draw some conclusions.

2 Cost allocation

When allocating a total transportation cost among the companies, we make use of cost allocation methods from cooperative game theory. In this context, each company is considered as a player of a cooperative cost game, (N, c), where N is the set of players, known as the grand coalition, and c is the characteristic cost function of the cooperative cost game. The value c(S) expresses the total cost of a collaboration of the players in coalition$S\subseteq N$. For simplicity we define $c(j):=c(\{j\})$ and we call this the individual cost of player j.

Each cost allocation method that provides us with a cost allocation can fulfill a number of properties, or fairness criteria. Below we list some of the basic properties. There is, however, no cost allocation method that fulfills all properties listed in the literature. It is assumed that all players have the opportunity to form and collaborate in coalitions.

2.1 Properties of cost allocation methods

A cost allocation method fulfills efficiency if it allocates the total cost, c(N), among the players $j\in N$, that is $\sum \nolimits _{j\in N}y_j=c(N)$ where $y_j$ is the cost allocated to player j.

A cost allocation method fulfills individual rationality if no player is allocated more than its individual cost, that is $y_j\leqslant c(j),\forall j\in N$.

A cost allocation method fulfills group rationality if no coalition is allocated more than its characteristic function cost, $\sum \nolimits _{j\in S}y_j\leqslant c(S),\forall S\subseteq N$.

A cost allocation is stable if it satisfy the constraints of efficiency and group rationality.

For each coalition, S, and a given cost allocation, y, we can compute the excess value, $e(S,y)=c(S)-\sum \nolimits _{j\in S}y_j$ which express the difference between the total cost of a coalition and the sum of the costs allocated to its players. Observe that the excess value, $e(\{j\},y)$, and cost saving, $\bar{c}_j$, of player j is the same, that is, $\bar{c}_j=c(j)-y_j=e(\{j\},y)$. The relative cost saving is defined as $\frac{\bar{c}_j}{c(j)}$.

A cooperative cost game is said to be proper if $c(S)+c(T)\geqslant c(S\cup T),S\cap T=\emptyset ,S,T\subseteq N$, that is, the cost function is sub-additive. In such a cooperative cost game, it is always profitable (or at least not unprofitable) to form larger coalitions.

2.2 Shapley value

The Shapley value (Shapley 1953) provides us with a cost allocation that is unique; however, there is no general guarantee that it is stable. It allocates to player j the value

$y_j=\sum \limits _{S\subseteq N,S\ne \emptyset }\frac{(|S|-1)!(|N|-|S|)!}{N!}[c(S)-c(S\backslash \{j\}]$.

2.3 Equal Profit Method

The EPM (Frisk et al. 2010) provides us with a stable cost allocation, such that the maximum difference in pairwise relative cost savings, $|\frac{c(i)-y_i}{c(i)}- \frac{c(j)-y_j}{c(j)}|(=|\frac{y_i}{c(i)}- \frac{y_j}{c(j)}|)$, is minimized. To find such a cost allocation, we need to solve the linear optimization problem

$$\begin{aligned}&[P_{EPM}]&\min f_0,&\end{aligned}$$

(1a)

$$\begin{aligned}&s.t.&\frac{y_i}{c(i)}-\frac{y_j}{c(j)}&\leqslant f_0,&\forall (i,j)\in N\times N, \end{aligned}$$

(1b)

$$\begin{aligned}&\sum \limits _{i\in S}y_i&\leqslant c(S),&\forall S\subset N, \end{aligned}$$

(1c)

$$\begin{aligned}&\sum \limits _{i\in N}y_i&=c(N).&\end{aligned}$$

(1d)

The variable $f_0$ is used in the objective function (1a) in order to minimize the largest difference of the first constraint set, (1b), which measures the pairwise difference between all players’ relative cost savings. The two other constraint sets, (1c) and (1d), define all stable cost allocations.

2.4 Nucleolus

To define the Nucleolus (Schmeidler 1969) we need the following. Let x and z denote two arbitrary vectors in $\mathbb {R}^n$ and let $\hat{x}$ and $\hat{z}$ denote sorted lists of each vector, respectively. If $\exists k\in N$ such that $\hat{x}_i=\hat{z}_i, \forall i<k$ and $\hat{x}_k>\hat{z}_k$, then we say that $\hat{x}$ is lexicographically greater than $\hat{z}$.

Let the associated excess vector of the cost allocation, y, be a non-decreasing list of excess values. The Nucleolus is the cost allocation y that has the lexicographically greatest associated excess vector and is such that individual rationality holds.

Procedures to calculate the Nucleolus are presented in Kopelowitz (1967) and Dragan (1981). Common mistakes to avoid are pointed out in Guajardo and Jörnsten (2015). The procedure ($P_{NUC}$) we use solves a sequence of optimization problems. In each iteration, some inequalities are changed to equality constraints based on the values of the dual variables corresponding to the constraints in an optimal solution. The k:th optimization problem in the sequence is formulated as $P_{NUC}^k$:

$$\begin{aligned}&[P_{NUC}^k]&\max w_k&\end{aligned}$$

(2a)

$$\begin{aligned}&s.t.&y_i&\leqslant c(i),&\forall i\in N \end{aligned}$$

(2b)

$$\begin{aligned}&w_k+\sum \limits _{i\in S}y_i&\leqslant c(S)&\forall S\in \mathcal {P}(N)\backslash \Pi _k \end{aligned}$$

(2c)

$$\begin{aligned}&w_{\kappa (S)-1}^*+\sum \limits _{i\in S}y_i&=c(S)&\forall S\in \Pi _k \end{aligned}$$

(2d)

$$\begin{aligned}&\sum \limits _{i\in N}y_i&=c(N)&\end{aligned}$$

(2e)

where $\mathcal {P}(N)=\{S\subseteq N|S\ne \emptyset \}$, $\Pi _0=\emptyset$, $\Pi _\lambda =\Pi _{\lambda -1}\cup \{S\in \mathcal {P}(N)\backslash \Pi _{\lambda -1}|\pi _{\lambda -1}^*(S)>0\}$, $\forall \lambda >0$, and $\kappa (S)=\min \nolimits _{S\in \Pi _k}k$. Further, $\pi _\lambda ^*(S)$ is an optimal value of the dual variable corresponding to the constraint in (2c) related to S, and $w_\lambda ^*$ is the optimal objective function value of problem $P_{NUC}^\lambda$. The problems $P_{NUC}^k$ is solved for $k:=k+1$ until a unique solution is found.

3 Collaboration

There are several ways to form collaborations for transportation activities. Shippers may outsource their transportation activities to a Logistics Service Provider (LSP) of their choice. In Cruijssen et al. (2005), a reverse process, insinking, is suggested, where the LSP invites the shippers instead. In this way the LSP can be more efficient by proactively selecting shippers with large synergy potential, e.g. that have similar distribution networks. It is further suggested that the selection of shippers is a sequential process where the next shipper is selected and receives a cost saving offer based on the current collaboration and game theoretical concepts, in such a way all previous cost saving offers remain or improve, that is, the path is a complete MP.

In this paper, we use the concepts of insinking and MPs, but instead of a sequential invitation we study a simultaneous invitation. The idea is that companies are invited to register for the collaboration, and when they do, they receive a cost saving offer that may be further improved each time a new company joins the collaboration. Observe that this implies that the simultaneous invitation leads to a sequential order of joining companies, that is, they do not register all at once. We call a sequence of these companies that receive a cost saving offer a path in the network of possible collaborations, see Fig. 1. The only information known by the companies is their cost saving offers and the final cost allocation, that is, the cost allocation when no more companies will join.

Fig. 1

A network of possible collaborations of four companies, $\{A,B,C,D\}$, of which one path, B, C, A, D, is dashed

The invitation may be initiated by a leading coalition, thereby inviting the other companies to join. In the network of possible collaborations, such a scenario is illustrated by a path starting in the node corresponding to the leading coalition, and passing nodes only in the succeeding sub-network. A path that starts in the node corresponding to the empty set ($\{\}$) is a path in which any, not pre-defined, single company (leading company) is initiating the invitation.

When collaboration in transportation planning is achieved by simultaneous invitation, an aim is to achieve collaborations that are, from a system perspective, good. Such collaborations are usually large. If all companies eventually accept, we denote this as a full collaboration. We refer to a cost allocation based on an a priori decided full collaboration as a baseline cost allocation, one for each cost allocation method.

4 Monotonic paths and cost allocation mechanisms

In this section we introduce the following concepts: monotonic paths, cost allocation mechanisms, semi monotonic paths, side-constrained cost allocation and the Lexicographic Equal Profit Method (EPML).

4.1 Monotonic paths

A step in the path is represented by an arc in the network of possible collaborations. At each step, k, a new company, i, receives a cost saving offer. Let $N_k$ denote the set of committed companies, who have accepted their cost saving offer, including company i. In order to provide a cost saving offer, a cost allocation problem, modelled as the cooperative cost game $(c,N_k)$, is solved. Company i accepts to participate if the cost saving offer has a non-negative value, and company i is accepted by the committed companies if their new allocated cost is less than or equal to their prior allocated cost, that is, no company may have negative profit nor end up with a higher cost allocation than its individual cost.

Let $y_{i,k}$ denote the cost allocated to company i in step k and let step 0 represent an initial state, where $N_0=\emptyset$ and $y_{i,0}:=c(i),\forall i\in N$.

A path is said to be an MP if $y_{i,k-1}\geqslant y_{i,k},\forall i\in N,k\in \{1,2,\ldots ,n\}$ where $y_{i,k-1}$ is the cost allocated to company i in the previous step and $y_{i,k}:=y_{i,k-1}, \forall i\in N\backslash N_k$. The path is complete if $n=|N|$, and the path is an IMP if at least one of the inequalities is violated.

We define the length of a path as the number of steps that the path is an MP. If a path becomes an IMP at step k, then the length is $k-1$.

4.2 Cost allocation mechanisms

In order to increase the likelihood for large collaborations, e.g. to increase the number of complete MPs, we have added two modifications to the straightforward implementation of the enumeration of MPs.

The first modification is a relaxation of the monotonicity of an MP, and instead of requiring a constant improvement of cost savings, we allow regression to some extent, however not further than to the cost saving offer of each company. We call the relaxed version of an MP, a semi monotonic path (SMP), see Sect. 4.2.1.

The second modification prevents cost allocations that would result in an IMP. This is done for those cost allocation methods that are solved as an optimization problem. We prevent undesirable cost allocations by adding (side) constraints, see Sect. 4.2.2. However, it may occur that all cost allocations are excluded. In that case the path is an IMP.

Further, when the cost allocation problem is solved by the EPM, we face the problem of non-uniqueness of the solution. We resolve this problem by using lexicography, and we call this the EPML, see Sect. 4.2.3.

4.2.1 Semi monotonic paths

When simultaneous invitation is applied, it could be sufficient to inform companies about their cost savings twice; once when they consider to join the collaboration and once when the full collaboration is achieved. Therefore, we consider SMPs, in which all companies must have an improved (or at least equal) cost saving at each step compared to the cost saving offer obtained when they initially joined the collaboration instead of requiring a continuous (or at least equal) improvement. Let $k^i$ denote the step in which company i receives a cost saving offer and accepts to join the collaboration. A path is said to be an SMP if $y_{i,k^i}\geqslant y_{i,k},\forall i\in N,k\in \{k^i+1,\ldots ,n\}$.

4.2.2 Side-constrained cost allocation

For the Nucleolus and for the EPML, the cost allocation problem can be formulated and solved as optimization problems. Then it is possible to avoid some IMPs by modifying the cost allocation method by adding side constraints to the optimization problem. The side constraints are identical to the mathematical definition of an MP and an SMP, that is $y_{i,k-1}\geqslant y_{i,k},\forall i\in N$ and $y_{i,k^i}\geqslant y_{i,k},\forall i\in N$, respectively. The key difference between adding side constraints and not adding them is when to check if any inequality is violated. Without added side constraints, the check is done after the cost allocations are computed. With added side constraints, the check is done during the computations.

The consequence of adding side constraints is illustrated in the following example, including five players. The values of the characteristic function for all coalitions are given in Table 1. We consider a specific path where the players join the collaboration in the order 3, 2, 5, 1 and 4. In Table 2, we show the computed cost allocations according to the Nucleolus as the players successively join. Each column in Table 2 corresponds to a player, and each row corresponds to a step. The individual costs for the players are given below the players’ numbers. The values of Table 2 are the allocated costs to the players in each step. A blank value indicates that the player is not currently participating in the collaboration.

Table 1 The characteristic function values of the small example

As seen in Table 2, when cost allocations are computed according to the Nucleolus, the path becomes an IMP at step 5 because player 3 is allocated a higher cost compared to the previous step (bold in Table 2). If instead side constraints are added to the Nucleolus computations, the last step results in a cost allocation $y=(156, 587, 118, 179, 1080)$. That is, one of the added side constraints in step 5 is stating that $y_3\leqslant 118$. This results in slightly higher allocated costs for player 2 and 4 compared to the allocated costs in Table 2, but the path is a complete MP.

Table 2 The cost allocations, for each step in the path, according to the Nucleolus for the small example

Observe that there is a risk that the baseline cost allocation is excluded in the process. In the example above, the baseline cost allocation $y=(156,583,126,175,1080)$ is excluded. In that case, the cost allocation deviates from the (baseline) cost allocations provided by the EPM and the Nucleolus. Therefore, we have performed analyses for the different cost allocation mechanisms concerning how often such exclusions occur and the magnitude of deviation from the baseline cost allocations. We refer to Sects. 6.2 and 6.3 for further reports on the computational results. Note that, complete MPs may still be found even though the baseline cost allocation is excluded.

Proposition 1

Given a proper cooperative cost game (N, c), applying the cost allocation mechanisms based on the Nucleolus and adding side constraints for either MPs or SMPs results in all paths to be complete MPs and complete SMPs, respectively.

Proof

Let $P_{NUC+}$ denote the procedure $P_{NUC}$ but with the added side constraints. Assume that player k considers to join the collaboration in step k. There exists a feasible solution to $P_{NUC+}$ for $N_1$; $y_{1,1}=c(1)$. Assume there exists a feasible solution to $P_{NUC+}$ for $N_k$, thus, $\sum \nolimits _{i\in N_k}y_{i,k}=c(N_k)$ holds. In step $k+1$ the side constraints are $y_{i,k}\geqslant y_{i,k+1},\forall i\in N_k$ and $c(k+1)\geqslant y_{k+1,k+1}$. Let us set $y_{i,k}:=y_{i,k+1},\forall i\in N_k$.

$c(k+1)\geqslant [{\text {proper cooperative cost game}}]\geqslant c(N_{k+1})-c(N_k)=c(N_{k+1})-\sum \nolimits _{i\in N_k}y_{i,k+1}=[{\text {efficiency}}]=y_{k+1,k+1}$. That is, we have found a feasible solution satisfying all side constraints, efficiency and individual rationality. $\square$

4.2.3 The EPML

If there is more than one solution to $P_{EPM}$, at least two players have non-unique feasible cost allocations. Because the objective of the EPM is to reduce the difference in relative cost savings, it is arguably fair in that sense to further reduce the difference in relative cost savings between these players.

Consider $P_{EPM}$ and a sorted list, $\bar{s}$, of the differences in relative cost savings from the constraint set (1b) in non-increasing order. Then the cost allocation according to the EPML is the solution to $P_{EPM}$ with the lexicographically smallest $\bar{s}$.

In Dahlberg et al. (2017) and Dahlberg (2015), the EPML is presented and discussed in more detail.

5 A case study

In this paper we apply the proposed cost allocation mechanisms to a transportation planning case study from the forest industry, as presented in Frisk et al. (2010), where shipments and companies of the forest industry are considered as components of an integrated logistics system.

We consider eight companies that have the opportunity to collaborate in order to minimize their total transportation cost. Their operations are modeled as a tactical problem, which often ranges from one to several weeks and deals with transportation of different types of wood from many harvest areas (supply points) to a few industries (demand points) such as paper mills, pulp mills, saw mills and heating plants. This case study is based on data taken from transports carried out during one month. A collaboration may reduce the total transportation cost due to synergy effects when the wood is bartered and by efficiently using return flows, thus reducing the travel distance.

The location of a company is the minimum convex geographic region covering the harvest areas and industries of the company. Companies have a small geographical overlap if the intersection of the locations of the companies are small, relative to the union of the locations, that is, the coverage of the companies. The whole geographic area is the union of the eight companies locations. In Frisk et al. (2010), examples of maps of the location of the companies are presented.

In this paper, the collaboration costs, c(S), are those used in Frisk et al. (2010), computed with the FlowOpt software (Forsberg et al. 2005) developed at Skogforsk.

5.1 Baseline cost allocations

There is a relatively large difference in size, indicated by individual costs, between the eight companies. In the second column of Table 3, we present the individual costs (without a collaboration). In the subsequent columns we show cost allocations according to the Shapley value, the EPM and the Nucleolus, as presented in Frisk et al. (2010), together with relative cost savings. Full collaboration provides an overall saving of $8.6\%$.

Table 3 Individual cost [Million SEK] and (baseline) cost allocations according to the Shapley value, the EPM and the Nucleolus and the relative cost savings (labelled Savings) [$\%$], see Frisk et al. (2010)

These three cost allocations represent the baseline cost allocations of the three cost allocation methods. We have verified that all three cost allocations are stable.

6 Computational study

Recall that the aim of this paper is to provide as good conditions as possible to achieve large collaborations. In this section we present computational results given by the enumeration of all paths and the cost allocation mechanisms presented in Sect. 4. By doing so, we obtain an indication of how successful each cost allocation mechanism is in regards to the aim.

We apply three types of cost allocation methods [EPML (Sect. 2.3), Nucleolus (Sect. 2.4), Shapley value (Sect. 2.2)] and two types of monotonicity [MP (Sect. 4.1), SMP (Sect. 4.2.1)], and for all cost allocation methods but for the Shapley value we have two cases, one in which side constraints are added (Sect. 4.2.2) and one in which they are not. This means that we have ten different cost allocation mechanisms. When referring to these cost allocation mechanisms, we first specify the cost allocation method, then if SMPs or MPs are considered. We indicate if side constraints are added with “+”, e.g. Nucleolus SMP+ indicates that the Nucleolus with added side constraints is used and that SMPs are considered.

Python (Van Rossum and Drake 1995) scripts were mainly used for the enumerations of all paths and for all cost allocation mechanisms, as well as for calculating the Shapley value and to save the results. For all optimization problems, the optimization solver Gurobi (Gurobi Optimization 2015) was used, which has a Python API. The optimization problems ($P_{EPM}$ (Model 1) $P_{NUC}$ (Model 2), as well as the models with added side constraints) are linear (LP) and contain at most 262 variables and at most 326 constraints. As mentioned in Sect. 5, the characteristic function values, c(S), are those in Frisk et al. (2010), who reports that the optimization problem for calculating c(N) has 240,000 variables and 5000 constraints and takes a few seconds to solve.

6.1 Path length

The length of a path is determined by the first time a company declines its cost saving offer or is rejected by any of the other committed companies, and path length indicates the success of achieving large collaborations. With an aim to achieve large collaborations, it is relevant to see how well the different cost allocation mechanisms perform in this regard.

In Table 4, we show the number of paths with certain lengths for each cost allocation mechanism. For eight companies, there are a total of 40320 possible paths. All complete paths in the case study in this paper have a lentgh of 8. The values in columns $3-5$ are the number of paths, and column 6 is the average length of all paths. Since no two-partner coalitions are more costly than the sum of the two singleton coalitions, no paths are of length 1. The two-partner coalition may, in a worst case scenario, act equivalent to the two singleton coalitions.

Table 4 Number of paths of certain lengths and the average length for each cost allocation mechanism

When SMPs are considered, the number of complete paths is naturally at least as large as the number of complete paths when MPs are considered, because an SMP is a relaxation of an MP. In the case study of this paper the number of complete SMPs is quite a bit larger than the number of complete MPs, see Table 4. If the EPML is considered, then roughly $30\%$ of the paths are complete MPs and roughly $80\%$ of the paths are complete SMPs.

There is a slight increase of complete paths for EPML SMP+ and EPML MP+ compared to EPML SMP and EPML MP, respectively. However, for Nucleolus MP+ and Nucleolus SMP+, the amount of complete paths are 100$\%$ compared to 0$\%$ and 10$\%$ for Nucleolus MP and Nucleolus SMP, respectively. That is, we can ensure that all paths are complete MPs or complete SMPs, which according to the proposition in Sect. 4.2.2 holds for any proper cooperative cost game.

With the aim to achieve large collaborations, Nucleolus MP+ and Nucleolus SMP+ seem promising. But, as mentioned in Sect. 4.2.2, these two cost allocation mechanisms do not always converge to the Nucleolus baseline cost allocation.

6.2 Deviation from baseline cost allocations

The deviation from the baseline cost allocation (see Sect. 5.1) due to added side constraints creates an uncertainty regarding fairness from a cooperative game theory point of view. But the concern may be reduced if the deviation is relatively small and the overall consequences of adding side constraints are positive relative to the aim. In the results of our case, we conclude that the cost allocations of EPML MP+ and EPML SMP+ converge to the EPML baseline cost allocation and it is therefore moot to include these cost allocation mechanisms in this section. Therefore, we study the magnitude of the deviation from the Nucleolus baseline cost allocation when side constraints are added.

In Table 5, for each company and for both SMPs and MPs we show the smallest and largest cost (in percentages) relative to the cost associated with the Nucleolus baseline cost allocation. In addition to the results presented in Table 5, we also note that for Nucleolus MP+, no paths converge to the Nucleolus baseline cost allocation, but for Nucleolus SMP+, 8813 paths ($22\%$ of all) do converge. The 40320 (final) cost allocations according to Nucleolus MP+ and Nucleolus SMP+ respectively are all stable.

Table 5 Comparing the difference between the Nucleolus baseline cost allocation and thcost allocation according to the Nucleolus with added side constraints

Out of the eight companies, company B is the only company that never receives an allocated cost that is less than the baseline cost allocation for any path. This might be explained by the fact that company B is the largest company and thus has greater synergy potential with the other companies. Those coalitions including company B gain quite large reduced costs in terms of absolute values, the excess values of these coalitions are therefore relatively large. These excess values are at the end of the associated excess vector and are therefore seldom at risk of being cut by the side constraints. A similar (but opposite) situation can be argued for the small companies. It is also evident that medium-sized companies have reduced costs for some paths and increased costs for other paths with one exception, company E. A possible explanation for this is that the relative cost saving of company E, according to the Nucleolus baseline cost allocation, is small. It is likely that the cost allocated to company E, according to the Nucleolus, in certain coalitions is less than the Nucleolus baseline cost allocation.

A common denominator between the companies with no higher cost than the Nucleolus baseline cost allocation (the maximum cost percentage is $< 0.05\%$) is that they are geographically located in peripheral areas.

For the case study of this paper, the deviations from the Nucleolus baseline cost allocation are small. In the worst case scenario, one company (company B) receives an allocated cost that is a 1.0$\%$ increase compared to the Nucleolus baseline cost allocation, but because the Nucleolus baseline cost allocation of company B is 11.1$\%$ less than its individual cost, company B still saves 10.3$\%$ compared to its individual cost. The largest deviations are cost reductions in the favor of company G and company H. In the best case scenario for company H, the relative cost saving is 7.5% which is significantly larger than the relative cost saving of 4.6% for the Nucleolus baseline cost allocation.

The average cost expresses the expected deviation based on a random path, and it is more representative of the common situation than the minimum or the maximum cost. The two largest deviations of the average cost, in terms of absolute values, occur for company G and company H, and the values are closer to the baseline cost allocation than to the minimum cost. The deviations of the average cost of the two largest companies, company B and company C, are both positive. However, they are close to zero, that is, they are almost negligible. It is evident that the deviations are relatively small, especially the deviations of the average cost.

According to our observations, the deviations of the cost allocations of Nucleolus MP+ and Nucleolus SMP+ from the Nucleolus baseline cost allocation are small. If one can accept such deviations, these two mechanisms are to be preferred instead of the other mechanisms presented in this paper, since Nucleolus MP+ and Nucleolus SMP+ guarantee full collaboration. However, if such deviations are unacceptable, cost allocation mechanisms with added side constraints must be excluded and one has to choose among the other mechanisms.

6.3 Leading coalition

In Table 6 we show more details about the complete paths for seven cost allocation mechanisms when the leading coalition is a single company (leading company), e.g. for EPML MP, 816 paths (the top left entry), or 7%, out of 11,064 complete paths start with company A. Because no paths for Nucleolus MP are complete and 100$\%$ of the paths for Nucleolus MP+ and Nucleolus SMP+ are complete, these numbers of complete paths do not add anything to Table 6 and are therefore not included.

Table 6 Number of complete paths starting with company i for seven cost allocation mechanisms

When comparing percentages, company A is the best leading company for EPML SMP+ and EPML SMP and the worst leading company for EPML MP+ and EPML MP. When the cost allocation mechanism is based on the EPML, company B is only a little bit worse as a leading company (around 10$\%$) compared to the other companies, but for Nucleolus SMP and Shapley value MP, no paths starting with company B are complete and only a few are complete for Shapley value SMP. A general observation is that if the leading company is located in the peripheral areas, it is better to use either the Nucleolus or the Shapley value than the EPML.

In Audy et al. (2012), the same transportation planning case study is considered as the one used in this paper, and four leading coalitions: $\{B\}$, $\{A,E\}$, $\{C,F\}$ and $\{A,D,G,H\}$ are studied in the same context as this paper, that is, the same case study. The choice of leading coalitions is based on the sizes of the companies and their geographic locations. In Table 7 we present the average path length depending on the same leading coalitions suggested by Audy et al. (2012). The results presented in Table 4 correspond to the case when there is no leading company, that is, the leading coalition is the empty set, $\{\}$, and the first company to join the collaboration is any of the companies, see Fig. 1. The average lengths from Table 4 are included in Table 7 for comparative purposes. Figure 2 is a graph visualizing the values in Table 7.

Table 7 The average length for each cost allocation mechanism based on different leading coalitions

Fig. 2

A graphic representation of the data in Table 7. The cost allocation mechanisms are sorted based on their average path length

In Audy et al. (2012), it is observed that company B gains the largest profit by being the leading company when using the business models presented in their paper. However, as seen in Table 7, the conditions to form the grand coalition are worse if company B is the leading company instead of the empty set, which is also indicated by Table 6, in which all percentages related to company B are below the average. The observation made by Audy et al. (2012) can explain the observations made in this paper. If company B is the leading company and strives to gain the largest profit, then less profit will be gained by the other companies. Thus, the likelihood that some company will terminate the path is increased if company B is the leading company.

Compared to the case when the empty set is the leading coalition, the coalition $\{C,F\}$ worsens the conditions to form the grand coalition if the cost allocation mechanism is based on either the Nucleolus or the EPML and improves the conditions if the cost allocation mechanism is based on the Shapley value. The overall best leading coalition among the four is $\{A,D,G,H\}$. The companies in $\{A,D,G,H\}$ have a small geographical overlap and at the same time cover a large part of the whole geographic area.

It is evident that the choice of cost allocation mechanism is crucial for the final cost allocation as well as for the conditions to form the grand coalition, as seen by the examples of leading coalitions $\{B\}$ and $\{C,F\}$.

6.4 Terminators

It is arguably interesting to study both constructive characteristics and destructive characteristics of collaborating companies. This has been done in Guajardo et al. (2016) where the dual game of a cooperative cost game reflects the destructive characteristics and the cooperative cost game reflects the constructive characteristics. In this paper, we study the destructive characteristics differently. As a complement to the study of the leading coalition, we present how often each company declines their cost saving offer or is rejected by any of the committed companies, both leading to a termination of the process, that is, the path is an IMP.

In Table 8 we show the number of paths becoming IMPs when company i receives a cost saving offer. Observe that because Nucleolus SMP+ and Nucleolus MP+ have 100$\%$ complete paths, there are no terminators for these two cost allocation mechanisms. Thus they are not included in Table 8.

Table 8 Number of paths becoming IMPs when company i receives a cost saving offer

When the cost allocation mechanism is based on the EPML, company A and company F terminate relatively few paths compared to other companies, except company B, and when the cost allocation mechanism is based on the Nucleolus or the Shapley value company A and company F terminate relatively many paths. Company E has the opposite characteristics.

Company C terminates almost six times as many paths for EPML MP and EPML MP+ than for EPML SMP and EPML SMP+ compared to other companies who terminates approximately four times as many.

It is notable that company B terminates the least number of paths. This can be explained by the fact that there will be large cost reductions, regardless of coalition, when company B joins. All other companies benefit by including company B. A conclusion of this is that companies that generate large cost reductions should join the collaboration in the later steps. This fact is supported by our results presented in Sect. 6.3 as well as by the observations made by Audy et al. (2012).

Overall, it is evident that the choice of a cost allocation mechanism affects the allocated cost for individual companies. Different companies are favoured by different cost allocation mechanisms, and this might lead to disputes between the companies.

6.5 Counter collaborators

In this section, we present a pairwise comparisons between companies for three of the cost allocation mechanisms, namely EPML MP, Nucleolus MP and Shapley value MP. The values in Tables 9, 10 and 11 represent the number of paths in which company i is allocated a higher cost than in the previous step when company j receives a cost saving offer resulting in an IMP. It can be interpreted as they are in some sense counter collaborators. We have not included the cost allocation mechanisms where SMPs are considered because the results are very similar to when MPs are considered. We have also excluded the cost allocation mechanisms with added side constraints, because in that case, if a path is IMP, we are not obtaining any cost allocation since the optimization model solved is simply infeasible.

Table 9 Number of paths for Nucleolus MP in which company i is allocated a cost resulting in the path becoming an IMP when company j receives a cost saving offer

Table 10 Number of paths for Shapley value MP in which company i is allocated a cost resulting in the path becoming an IMP when company j receives a cost saving offer

There is a symmetry in the results for Nucleolus MP and Shapley value MP. The numbers of paths are of roughly the same magnitude for each pair of companies, that is, company i causes a higher allocated cost for company j roughly as much as company j causes for company i. For each pair of non-zero valued counter collaborators, there is a small or no geographical overlap. Counter collaborators do not have much synergy potential with one another.

There are two companies, company A and company E, that do not follow this type of symmetry for EPML MP. If these two companies were to be removed from Table 11, then the resulting table would follow the same symmetry as for the Nucleolus MP and Shapley value MP.

Table 11 Number of paths for EPML MP in which company i is allocated a cost resulting in the path becoming an IMP when company j receives a cost saving offer

The largest exception from the symmetry occurs for company A and EPML MP. In Table 11, it is shown that company A is allocated a higher cost in many more paths than it is causing other companies to be allocated a higher cost. An explanation for this might be that company A has more synergy potential with some companies than with others, that is, due to geographic location or type of wood being transported. If company A is one of the committed companies, including a new company might result in a coalition with less synergy potential than if company A were to be excluded from the coalition. This might result in a higher allocated cost for company A. On the other hand, if company A is the company joining the collaboration, the consequences of having a coalition with more synergy potential only results in a small (yet positive) cost saving for company A. This characteristic is also notable for the EPML baseline cost allocation, in which company A is the only company with a lower relative cost saving compared to the other companies.

The reason for why this characteristic of company A appears only for the EPML might be explained by the fact that the cost allocations according to the Nucleolus and the Shapley value are based on absolute cost differences between coalitions, while the cost allocation according to the EPML is based on relative difference between the allocated cost and individual cost. Compared to the other companies, there are many coalitions in which the cost reduction for including company A is small relative to the individual cost of company A. If the EPML is considered, then company A will have a larger relative cost saving compared to if the Nucleolus or the Shapley value is considered. Therefore, the negative impact on the path made by company A is larger if the cost allocation is based on relative differences instead of absolute differences.

7 Conclusions and future research

In this paper we examine and analyze how collaboration can be achieved in a situation where companies of the forest industry, see Frisk et al. (2010), are invited to register to join a collaboration. The collaboration is achieved by companies being simultaneously invited and are joining sequentially, and the sequence is represented by a path in a network of possible collaborations. We study which effects different cost allocation mechanisms, based on concepts from game theory, have on the cost saving offers and, thereby, on the incentive to collaborate. The aim of this paper is to provide as good conditions as possible to achieve large collaborations.

The length of a path is an indication of the success in achieving large collaborations, and a full collaboration is equivalent to a complete path. We study monotonic paths (MPs) and semi monotonic paths (SMPs), defined by if the allocated costs along the path are required to be non-increasing or not. It is obvious that the number of complete SMPs is larger than (or equal to) the number of complete MPs. The computational results show indeed that this difference is very large. If the cost allocation mechanism is based on the EPML, roughly $30\%$ of the paths are complete MPs and roughly $80\%$ of the paths are complete SMPs. This implies that, when simultaneous invitation is applied based on SMPs, there are good possibilities for obtaining large collaborations. Further, when side constraints are added to the EPML there is a slight increase in the number of complete MPs and SMPs. For the Nucleolus without added side constraints, all paths (with a few exceptions for SMPs) are IMPs; however, by adding side constraints all paths are complete. The fact that the Nucleolus with added side constraints results in all paths being complete is not exclusive to the case study of this paper. A proof that it holds for a general case is provided, see Sect. 4.2.2. However, it might happen that for Nucleolus MP+ and Nucleolus SMP+ the cost allocation does not converge to the Nucleolus baseline cost allocation. The deviations between those cost allocations and the Nucleolus baseline cost allocation are small, at most $1.0\%$ for the case study of this paper, compared to an overall saving of $8.6\%$ for the grand coalition.

The geographic locations and the sizes of the companies do affect the results. If the Nucleolus with added side constraints are considered, that is, Nucleolus MP+ or Nucleolus SMP+, then the deviation from the Nucleolus baseline cost allocation is likely to be a cost reduction for the small companies and companies located in peripheral areas. In the best case scenario for company H, that is by far the smallest company, the amount of relative cost savings is 7.5%. It’s about 40% better than the relative cost savings of 4.6% for the Nucleolus baseline cost allocation. The deviation from the Nucleolus baseline cost allocation is likely to be a cost increase for company B, that is the largest company.

With the aim to achieve large collaborations, the coalition $\{A,D,G,H\}$ is a good leading coalition and $\{B\}$ is not. There is a small geographical overlap between the companies in $\{A,D,G,H\}$ and the coalition cover a large part of the considered geographic area. That is, small companies, whose location are spread out, should join first. The likelihood of achieving full collaboration is increased (compared to the expected probability of a random path) if the magnitudes of cost reductions are smaller in the beginning of a path compared to the cost reductions in the end of a path. In the beginning of such a path, small companies with a small geographical overlap are joining the collaboration and in the end large companies are joining.

Some additional observations are; 1) The Shapley value and the Nucleolus are better than the EPML if the leading company is a company located in the peripheral area.; 2) Counter collaborators have a small or no geographical overlap.; 3) The choice of cost allocation mechanism is crucial for the final cost allocation.

The contribution of this paper is the cost allocation mechanisms presented, with the aim to achieve large collaborations. The cost allocation mechanisms Nucleolus SMP+ and Nucleolus MP+ provide the best conditions to fulfill the aim, since they guarantee full collaboration. If one can accept the possible deviation between the cost allocations of Nucleolus SMP+ and Nucleolus MP+ and the Nucleolus baseline cost allocation, these two mechanisms are to be preferred instead of the other mechanisms presented in this paper. However, if such deviations are unacceptable, cost allocation mechanisms with added side constraints must be excluded and one has to choose among the other mechanisms.

Further research involve different rules for the process when companies are invited and join the collaboration. In this paper we end a path when a company declines their cost saving offer or is rejected by any of the committed companies. It is reasonable to assume that some other company could still join the collaboration. It is also reasonable to assume that a company that declines its cost saving offer might reconsider at a later step of the path if said company could register more than once and thus receive another cost saving offer.

The results presented in this paper are based on one case study, with data taken from eight companies and from forestry transports carried out during one month. In order to check the reliability of our results, and possibly verify them, the cost allocation mechanisms should be applied to further case studies.

Another possible continuation is to apply these ideas to other applications and thus check the generality of the results. There are no methodological assumptions that are case or application specific. However, the results depend on the characteristic function values, which in turn depend on the collaboration’s potential for cost reductions. Collaborations in some applications might be more beneficial than in other applications.