The joint network vehicle routing game with optional customers

We consider logistic collaborations where multiple carriers collaborate by consolidating demands, combining delivery routes, and serving new customers. Logistic collaborations are known to provide numerous benefits such as an increase in profit as well as a reduction in emissions for all parties involved. One of the challenges associated with collaborations is the allocation of the additional profits. To this end, we model the corresponding profit allocation problem as a collaborative game. Here, the profit obtained by any subset of the collaborating carriers depends on the new customers served by the remaining carriers. Specifically, we try to determine an allocation in the core based on both the best-case profit and the worst-case profit that each subset of carriers can attain. To achieve this, we propose a heuristic row generation algorithm. We verify the performance of this algorithm on instances derived from benchmark instances of the capacitated vehicle routing problem. We show that our heuristic algorithm scales well with respect to the number of carriers considered and provides allocations similar to those obtained by enumerating all best-case and worst-case profits of each coalition.

The authors are exclusively responsible for the content of their research papers published in the series Les Cahiers du GERAD. Copyright and moral rights for the publications are retained by the authors and the users must commit themselves to recognize and abide the legal requirements associated with these rights. Thus, users: • May download and print one copy of any publication from the public portal for the purpose of private study or research; • May not further distribute the material or use it for any profitmaking activity or commercial gain; • May freely distribute the URL identifying the publication. If you believe that this document breaches copyright please contact us providing details, and we will remove access to the work immediately and investigate your claim.

Introduction
Collaborative transportation among carriers has the potential to greatly increase the efficiency of their transportation networks. By collaborating, the carriers can significantly reduce their cost (Guajardo and Rönnqvist, 2015), increase their service levels, and improve their market share (Gansterer and Hartl, 2018). Moreover, such collaborations are known to provide numerous other benefits including reductions in noise pollution, road congestion, and green house gas emissions as shown by Ballot and Fontane (2010) and Pérez-Bernabeu et al. (2014).
In this paper, we study a horizontal collaboration among multiple carriers, each responsible for multiple customers with a given demand. It is assumed that each carrier serves the demand of its customers from a single depot, using a limited fleet of capacitated vehicles. Moreover, we assume that the carriers are rational and aim to maximise their profits. The carriers may collaborate by consolidating demands and combining delivery routes. As a consequence, the carriers are likely to have residual capacity. This residual capacity can be used by the carriers to generate additional profits by collectively serving new customers. We focus on the profit allocation problem that arises when multiple carriers collaborate by consolidating demands, combining delivery routes, and collectively serving new customers.
Profit, or equivalently, cost allocation problems in collaborative transportation are often modelled as cooperative games (Guajardo and Rönnqvist, 2015). A cooperative game is defined as a pair consisting of a set of players, also known as the grand-coalition, and a characteristic function which maps each subset of players, also referred to as a coalition, to a value. We choose to interpret this value as the profit of a coalition, i.e., the value created by the collaboration. We aim to allocate the profit of the grand-coalition to the players such that each player has an incentive to cooperate. To this end, it is common to consider core allocations (Guajardo and Rönnqvist, 2015). A core allocation is an allocation such that the profit allocated to each coalition exceeds the profit which the coalition would be able to obtain without any form of collaboration with the remaining players of the grand-coalition.
Originally, collaborative transportation was studied from the perspective of the customers, rather than the carriers. Göthe-Lundgren et al. (1996), Engevall et al. (1998) and Engevall et al. (2004) consider a setting in which multiple customers are served by a single carrier. More specifically, Engevall et al. (1998) consider the cost allocation problem where all customers are served on a single route, whereas Göthe-Lundgren et al. (1996) and Engevall et al. (2004) consider the cost allocation problem where all customers are served on multiple routes. The aim of the allocation problem is to allocate the cost in a fair manner to each of the customers. To this end, Engevall et al. (1998) model their problem as a travelling salesman game (TSG), which was originally proposed by Fishburn and Pollak (1983). Moreover, Göthe-Lundgren et al. (1996) and Engevall et al. (2004) model their cost allocation problem as a vehicle routing game (VRG), as originally proposed by Göthe-Lundgren et al. (1996).
More recently, collaborative transportation has also been studied from the perspective of carriers. For example, Krajewska et al. (2008) and Dai and Chen (2015) study a profit allocation problem which arises from a collaboration among freight carriers, each with a set of pickup and delivery requests with time windows. In a cooperative setting, the carriers, or players, collaborate by collectively serving their requests. The goal of the corresponding profit allocation problem is to allocate the profit to the carriers, rather than to the customers. Similarly, Zakharov and Shchegryaev (2015) and van Zon et al.
(2019) study a collaboration among multiple carriers, each with multiple customers corresponding to delivery requests, which have to be satisfied from a single depot. In contrast to Krajewska et al. (2008) and Dai and Chen (2015), they formulate the problem as a cost allocation problem, with the aim to allocate the cost of the grand-coalition to the carriers.
The previously mentioned studies are mainly concerned with optimising the efficiency of the existing routing networks through collaborative transportation, but do not consider any additional gains which could be obtained as a consequence of the collaboration. For example, in a collaboration among multiple carriers, each carrier has a fleet at its disposal. By consolidating demands and combining delivery routes, the carriers are able to utilise their capacity more efficiently. As a result, less vehicles may be needed for the transportation and additional customers may be served with their residual capacity for a profit.
The setting of van Zon et al. (2019) is closest to ours. The authors define the cost of a coalition as the optimal objective value to a capacitated vehicle routing problem (CVRP) of the customers belonging to the coalition. They model their cost allocation problem as the joint network vehicle routing game (JNVRG). Moreover, they propose a row generation algorithm to determine a core allocation.
In the previous multiple-player settings, a collaboration between players is established when it becomes profitable for each player to serve customers of other players or to have some of their own customers served by others. In this case, a single customer can easily foster a collaboration between two players as it, generally, does not require a large capacity to be served. On the other hand, it might yield only a small profit increase that might be exceeded by potential overhead collaboration costs.
We believe that a larger profit increase induced by a collaboration can be achieved when the reason for collaborating is to gather sufficient capacity to service an additional large demand. The typical example that we have in mind is the following. To benefit from an economy of scale, a company with multiple branches may require to be supplied by the same carrier. Therefore, to acquire the branches of this company as customers (all together), a carrier must have sufficient capacity or must collaborate with one or several other carriers. This is the type of collaboration that we study in this paper.
We generalize the setting of van Zon et al. (2019) by assuming that there exist multiple clusters of optional customers (each composed, e.g., of branches of a company) which are not assigned to one of the players. A coalition obtains a reward for visiting all customers of a cluster. In this case, we cannot simply define the profit of a coalition, as it is not trivial to determine how the clusters of optional customers are allocated among the coalitions. The allocation of the clusters can be modelled by means of combinatorial auctions (Gansterer and Hartl, 2018). However, by doing so, it is not immediately clear to each of the players what the profit of a coalition is. We choose to consider both a best-case profit as well as a worst-case profit for each coalition. In the best case, we assume that a coalition can freely select the clusters of optional customers it is willing to serve, thereby obtaining the maximum profit. On the other hand, in the worst case, we assume that the remaining players form a coalition and select the clusters of optional customers which benefit them the most. In this case, the original coalition can only select the clusters of optional customers which have not been selected by the remaining players. In this manner, we aim to provide an accurate representation of the profit which the coalition may attain. Our goal is to try to determine an allocation in the core as defined by the best-case profit. However, if this core is empty, we try to determine an allocation in the core as defined by the worst-case profit, or show that the core as defined by the worst-case profit is empty.
Our contributions are as follows. First, we define a new cooperative game which, to the best of our knowledge, has not been studied before. Here, we consider the profits which can be obtained by consolidating demands, combining delivery routes, and collectively serving new customers. For each coalition, we consider both the worst-case and best-case profits that can be obtained, depending on the manner in which the clusters of optional customers are allocated. In the best case, we assume that each coalition can freely select which clusters of optional customers to serve. On the other hand, in the worst case, we assume that the players not included in the coalition get to freely select which clusters of optional customers to serve first. Thereafter, the coalition can only select among the remaining clusters which ones to serve. Secondly, we propose a heuristic row generation algorithm to determine allocations in the cores as defined by the best-case and the worst-case profit, or to show that both cores are empty. The corresponding row generation subproblem is a generalisation of a vehicle routing problem with profits. We propose a branch-and-price-and-cut algorithm for the subproblem. To this end, we adapt several well-known acceleration strategies for the problem.
The remainder of this paper is structured as follows. First, in Section 2, we formally introduce the grouped capacitated profitable tour problem with contract customers (GCPTPCC). Moreover, we introduce the joint network vehicle routing game with optional customers (JNVRGOC), which is a cooperative game based on the GCPTPCC. Here, we also introduce the core as an allocation concept.
In Section 3, we propose a heuristic row generation algorithm in order to determine a profit allocation. We formulate the row generation subproblem as a mixed integer programming problem in Section 3.1 and develop a branch-price-and-cut algorithm for solving the subproblem in Section 3.2. Next, we describe acceleration strategies for the row generation algorithm in Section 3.3. In Section 4, we report numerical results obtained on instances derived from the vehicle routing instances of Augerat (1995). Finally, we present our concluding remarks in Section 5.
2 The joint network vehicle routing game with optional customers Before presenting the JNVRGOC, we introduce the GCPTPCC which is initially defined for a single carrier. Consider a complete directed graph In contrast to the optional customers, the contract customers in V c all have to be visited and no reward is given for visiting these customers. With each arc (v, w) ∈ A, a travel cost c vw ≥ 0 is associated, which we assume to adhere to the triangle inequality. Furthermore, each customer v ∈ V c ∪ V o has a demand d v > 0. A limited number of vehicles k with capacity Q is available at the depot to satisfy the demands by visiting customers along routes. A route is defined as a simple cycle, starting and ending at the depot, such that the total demand of the visited customers does not exceed vehcile capacity. Here, we assume that The GCPTPCC is the problem of constructing routes in such a way that the profit, i.e., the total rewards minus the total costs, is maximised and every contract customer v ∈ V c is visited. We denote the optimal objective value of a GCPTPCC on the graph induced by the vertex sets V o and V c as GCPTPCC (V o , V c ). To the best of our knowledge, the GCPTPCC has not been studied before. However, van Zon et al. (2019) study the grouped capacitated profitable tour problem (GCPTP), which can be seen as a special case of the GCPTPCC in which no contract customers are considered.
The definition of the GCPTPCC can be generalized to consider multiple collaborating carriers as proposed below. To do so, we need to define one depot per carrier, with its associated vehicle fleet. Nevertheless, in this paper, we assume that there is a single depot for all players which may be seen as a super-depot regrouping the players' individual depots that are assumed to be near each other. The model and algorithm presented below can, however, be easily adapted to the multiple-depot case.
We consider the profit allocation problem that arises when multiple carriers collaboratively serve both contract customers and selected optional customers. Here, we assume that the sets of optional customers as well as the routes used to service them are chosen according to an optimal solution of a GCPTPCC. The overall profit obtained by executing this solution needs to be allocated among the carriers in a fair manner. To this end, we define a cooperative game based on the GCPTPCC, which we call the JNVRGOC. A cooperative game is defined as a pair N, v , where the grand-coalition N = {1, . . . , n} denotes the set of players, v : P(N ) → R the profit of a coalition S ⊆ N , and P(N ) the power set of N . Here, each player i ∈ N is assumed to have a finite fleet of k i vehicles with capacity Q available. Hence, a coalition S ⊆ N has i∈S k i vehicles available. Moreover, we also assume that each player i ∈ N has a set of contract customers V c i for which the demand has to be fulfilled, with The profit of a coalition S ⊆ N depends on how the clusters of optional customers are allocated among the coalition S and the remaining players N \S. Here, we consider two specific cases. First, we consider the best-case profit v B (S) that coalition S can obtain. In the best case, coalition S can freely select clusters of optional customers to serve. We define the best-case profit v B (S) as follows where we add the stand-alone routing costs p c i = −GCPTPCC(∅, V c i ) of the contract customers belonging to the coalition, in order to ensure that the value created by the coalition is properly represented by v B (S). Note that v B (S) is obtained not only by visiting sets of optional clusters but also by visiting more efficiently the contract customers of the players in S. Secondly, we consider the worst-case profit v W (S) of a coalition S ⊆ N , in which we assume that the remaining players N \S form a coalition and can freely select which clusters of optional customers to serve. This may significantly lower the profit that coalition S can obtain. We define the worst-case profit as follows where M (N \S) ⊆ M denotes the subset of indices l of the optional customer clusters V o l which are not supplied in an optimal solution to v B (N \S). Notice that there might be several optimal solutions, but we retain only one of them. In this paper, we consider and compare both the best-case profit and the worst-case profit by means of the following profit function where We define the JNVRGOC as a cooperative game N, v α .

Profit allocation
The aim of the JNVRGOC is to allocate the profit of the grand-coalition to the players. We denote a profit allocation by y ∈ R n , where y i is the profit allocated to player i ∈ N . Furthermore, we define y(S) = i∈S y i for S ⊆ N . Given α ∈ [0, 1], a profit allocation y ∈ R n is said to be individually rational if and only if y i ≥ v α ({i}) for all i ∈ N . Moreover, y is efficient if and only if y(N ) = v(N ). Given α ∈ [0, 1], the set I( N, v α ) of efficient and individually rational allocations is known as the imputation set. This set is seen as a minimum requirement for cooperation as each player benefits relative to his stand-alone profit. Note that given α 1 ≥ α 2 it holds that Moreover, it may be the case that the imputation set is empty for all α ∈ [0, 1], as illustrated in the example in Appendix A.
Often, profits (or costs) are allocated by means of core allocations. A core allocation is an allocation which is both efficient and group rational. Here, given α ∈ [0, 1], an allocation y is said to be group rational if and only if y(S) ≥ v α (S) for all S ⊆ N . We denote the core, i.e., the set of all core allocations, by Core( Next, we provide an example to illustrate the differences between the worst-case core and the best-case core.
Example 2.1 Consider the 3-player instance of the JNVRGOC with N = {1, 2, 3} as presented in Figure 1. Let Moreover, let k i = 1 for each player i ∈ N and assume that all vehicles have a capacity Q = 4. There is a single cluster of optional customers which is defined as Assuming that c ij = c ji for all (i, j) ∈ A, the relevant arc costs are given in Figure 1. Note that due to the symmetry of the instance, the profits are solely dependent on the size of a coalition. For this reason, we choose a specific coalition of a certain size to determine the profit for all coalitions of this size.
Secondly, we consider the worst-case profits. For the singleton coalitions, the worst-case profits are trivial (v W ({i}) = 0, ∀i ∈ N ) as no optional customers can be visited. On the other hand, it is nontrivial for the coalitions of size 2. For example, consider coalition {1, 2}. This coalition can be visited using route (0, 1, 2, 0) at cost 10, Hence, despite the fact that no optional customers can be visited, the coalition is still profitable. Finally, recall that the worst-case profit of the grand-coalition is equal to the best-case profit, i.e., v W (N ) = 11.
One can observe that, for example, y B = (3, 4, 4) is a best-case core allocation. On the other hand, y W = (9, 1, 1) is clearly not a best-case core allocation. However, y W still belongs to the worst-case core. Both allocations, as well as the worst-case and best-case cores are visualised in Figure 2. At each of the corner points, a single player is allocated a profit of 11 (e.g., player 1 is associated with the lower-left corner), whereas the other players are allocated zero profit. All efficient allocations can be written as convex combinations of these allocations. Hence the largest triangle is the convex hull of these allocations. Each solid line in the figure corresponds to a best-case rationality constraint, whereas each dashed line to a worst-case rationality constraint. Moreover, the arrow indicates the feasible halfspace. The best-case core is represented by the dark triangle, whereas the worst-case core is represented by the grey hexagon. In the remainder of this paper, we aim to find an allocation for the JNVRGOC in the best-case core. However, if the best-case core is empty, we try to find an allocation in the worst-case core by minimally relaxing the best-case rationality constraints. To this end, we consider the following linear programming problem To obtain an allocation which is as close as possible to the best-case core, objective function (4) tries to maximise α, which is considered as a decision variable. Constraints (5) enforce the rationality constraints whose right-hand sides are linear functions of α, whereas constraint (6) is the efficiency constraint. Moreover, constraints (7) and (8) define the variable domains.
Note that if there exists an optimal solution α and y to (4)-(8) for which α = 1, it holds that y is in the best-case core. Alternatively, if (4)-(8) has no feasible solution, then the worst-case core is empty.

A heuristic row generation algorithm
Two main challenges have to be considered when solving (4)-(8) to optimality. First, there are exponentially many rationality constraints (5) in the number of players. Second, the optimal objective values of two GCPTPCCs have to be computed for each coalition. Here, it is important to note that the GCPTPCC is a generalisation of the NP-hard CVRP (Lenstra and Kan, 1981), which is well-known to be computationally expensive to solve.
Algorithm 1 Profit allocation heuristic 1: Set q = 0, Ω 1 = ∅, and Υ 1 = ∅. 2: Compute v(N ). 3: repeat 4: q = q + 1. 5: Solve (10)-(15) to optimality using row generation and let α q be the optimal value. 6: if α q = 1 then 7: Set Θq = ∅ 8: else 9: Update Υq. 10: Let Θq ⊆ Υq be the set of coalitions for which constraints (11) are tight. 11: for S ∈ Θq do 13: Determine v B (S). 14: end for 15: for S ∈ Θq do 16: Determine v W (S). 17: end for 18: Set In similar studies, both challenges are alleviated by applying row generation to the rationality constraints (see Göthe-Lundgren et al., 1996, Engevall et al., 2004, Drechsel and Kimms, 2010, Dai and Chen, 2015, van Zon et al., 2019. Violated rationality constraints are identified by means of a row generation subproblem. Consider an optimal solution α and y to (4) and (6)-(8). A violated rationality constraint (5) can be identified by solving the following row generation subproblem However, if α = 1, it is not at all obvious how subproblem (9) can be solved efficiently due to the inclusion of the worst-case profit of coalition S. Alternatively, one could try to apply row generation by using lower bounds on the worst-case profits of the coalitions but it does not seem easy to determine such tight bounds. As a consequence, we were unable to devise an efficient row generation algorithm for solving (4)-(8) to optimality.
For instances with a small number of players, we can simply enumerate both the best-case profits as well as the worst-case profits. However, for instances with a larger number of players, enumeration is no longer tractable. Instead of solving (4)-(8) to optimality, we propose an iterative heuristic algorithm to determine allocations in the best-case core or possibly in the worst-case core, if the best-case core is empty. At each iteration q, this algorithm solves a relaxation of (4)-(8) to determine an allocation. This relaxation is obtained by relaxing the constraints (5) for all coalitions except those in a subset Ω q ⊆ P(N ). It writes as follows: The objective function (10) still aims at maximizing the value of α which is replaced by α q at iteration q. Constraints (11) are the relaxed rationality constraints (the term involving v W (S) is omitted), whereas constraints (12) are the non-relaxed ones. The efficiency constraint is given by (13). Finally, the variable bounds are enforced through (14) and (15).
The proposed profit allocation heuristic is described in Algorithm 1, where Υ q denotes the set of constraints (11) that are initially considered in model (10)-(15) at iteration q, i.e., those whose best-case profits have already been computed. We start by setting q = 0, Ω 1 = ∅, and Υ 1 = ∅, and we compute v(N ) by solving a GCPTPCC for the grand-coalition N . Then, we perform the following steps iteratively, incrementing the iteration counter q at each iteration (Step 4). First, in Step 5, we solve (10)-(15) to optimality using row generation and store the computed optimal value α q . To this end, we relax the constraints (11) except those associated with a coalition S ∈ Υ q and find any tight or violated best-case rationality constraints by solving a row generation subproblem (see Sections 3.1 and 3.2), which implies computing the best-case profit v B (S) for each corresponding coalition S. If α q = 1, it means that an allocation in the best-case core has been found and the algorithm stops after setting Θ q = ∅ in Step 7 to meet the repeat loop exiting criterion in Step 20. Otherwise, after updating set Υ q in Step 9 by appending the coalitions for which a constraint (11) was generated in Step 5, we identify in Step 10 the best-case rationality constraints (11) that are tight at optimality and define Θ q as the set of their associated coalitions. For these coalitions, we would like to compute their worst-case profits and convert their corresponding relaxed rationality constraints (11) into non-relaxed constraints (12). To compute these worst-case profits, we need to compute the best-case profits of their complements with respect to N (if not computed yet) and, more specifically, identify the clusters of optional customers that are not covered in the computed optimal solutions. Consequently, in Step 11, we determine the set Θ q of the complements for which their best-case profits have not been computed yet. Thereafter, for each coalition S ∈ Θ q , we compute its best-case profit v B (S) in Step 13 and, for each coalition S ∈ Θ q , we find its worst-case profit in Step 16. Finally, we determine Ω q+1 and Υ q+1 . We stop iterating when Θ q = ∅ and output the last allocation found in Step 5.

The row generation subproblem
Consider an incumbent solution (α q , y ) to (10)-(15) at iteration q. We identify tight or violated rationality constraints (11) at iteration q by means of the following row generation subproblem If SP (α q , y ) ≥ 0, we have identified a tight or violated best-case rationality constraint of the form y(S) ≥ αv B (S). Otherwise, (α q , y ) is optimal for (10)-(15) and all tight rationality constraints have been generated at iteration q. Note that the profit of a coalition has not yet been determined and is part of solving the subproblem.
As proposed by van Zon et al. (2019), the subproblem can be modelled as a GCPTP where we consider an additional constraint with regards to the number of vehicles used. We formulate the GCPTP as the following mixed integer program. Let R denote the set of feasible routes in G = (V, A). Let c r be the cost of route r which is given by the sum of the costs of its arcs. Also, let the coefficient a rv be equal to the number of times customer v is included in route r. Hence, a rv = 0 if customer v is not included in r and a rv = 1 if customer v is included exactly once in r. Next, for each route r ∈ R, define a binary decision variable x r such that x r = 1 if and only if route r is selected in the solution. Furthermore, for each l ∈ M , we define the binary decision variable z l such that z l = 1 if and only if all customers of V o l are visited exactly once in the solution. For each optional customer v ∈ V o l , let l(v) = l and, for each contract customer v ∈ V c of player i ∈ N , let i(v) = i. Finally, let s i be a binary variable that indicates whether or not player i ∈ N belongs to the selected coalition S.
Given this notation, the subproblem can be formulated as follows: Objective function (17) searches to maximize the amount by which a rationality constraint (11) is violated with respect to the incumbent solution (α q , y ). Constraints (18) (11) in Step 5 of Algorithm 1, the set of constraints (21) also contains constraints associated with previously identified coalitions for which (11) is tight. Finally, the binary requirements on the decision variables are enforced through (22)-(24).
Given a solution (x , z , s ) to model (17)- (24), the selected coalition S is given by If (x , z , s ) is optimal, its best-case profit is derived from the solution as: Note that model (17)-(24) can also be used to compute the values of v B (S) and v W (S) whenever necessary. Indeed, v B (S) with S ⊆ N can be obtained by solving (17)-(24) with s i = 1 for i ∈ S and s i = 0 for i ∈ N \S. Moreover, given an optimal solution (x , z ) to v B (N \S), v W (S) can be determined by solving (17)-(24) with z l = 0 for each l ∈ M such that z l = 1, s i = 1 for i ∈ S and s i = 0 for i ∈ N \S.

A branch-price-and-cut algorithm for the subproblem
We propose a branch-price-and-cut algorithm for solving the row generation subproblem (17)-(24) which potentially involves a large number of route variables. Branch-price-and-cut is a branch-andbound algorithm where column generation is applied to solve the linear relaxations encountered in the search tree and cuts are added as needed to strengthen them. In this context, the linear relaxation of (17)-(24) is called the master problem. Its solution by column generation proceeds iteratively as follows. At each iteration, a so-called restricted master problem, which is defined as the master problem limited to a subset of its variables, is first solved to yield an optimal pair of primal and dual solutions. Then, to check the optimality of this solution for the complete master problem, a pricing problem that searches for positive reduced cost variables is solved. If such variables are found, they are added to the restricted master problem before starting a new iteration. Otherwise, column generation stops with an optimal solution to the master problem and a valid upper bound for the current branch-andbound node. A detailed description of the pricing problem is given in Section 3.2.1. To improve the upper bound provided by the master problem solution, the adapted rounded capacity cuts described in Section 3.2.2 are generated. Finally, to derive integer solutions, we apply the branching strategy presented in 3.2.3 if required.

Pricing problem
The column generation pricing problem is used to identify route variables with a positive reduced cost or to show that no such variable exists. Let λ v ≥ 0, v ∈ V c , µ v ≥ 0, v ∈ V o , and σ denote the dual variables associated with constraints (18), (19), and (20), respectively. The reduced costc r of a route variable x r , r ∈ R, can be expressed asc where A r ⊂ A is the subset of arcs included in route r and the modified arc costsc vw for (v, w) ∈ A are given byc As proposed for many vehicle routing problems (see Costa et al., 2019), we model the pricing problem as an elementary shortest path problem with resource constraints (ESPPRC, see Irnich and Desaulniers, 2005), namely, a load resource to account for vehicle capacity and customer resources for imposing route elementarity. Moreover, we solve the pricing problem using a labelling algorithm in which the labels are stored in buckets corresponding to demand and customer pairs, similar to the algorithm proposed by Martinelli et al. (2014). Here, we enforce route elementarity by means of the unreachable resources introduced by Feillet et al. (2004).
Given that the computational complexity of the ESPPRC is N P -hard in the strong sense, we apply several well-known acceleration strategies with regard to the pricing problem. First of all, we relax the master problem by allowing non-elementary routes. More specifically, we consider the ng-route relaxation of Baldacci et al. (2011), which has been shown to provide a good trade-off between weaker upper bounds for the master problem and reduced computational effort to solve the pricing problem. Given a predefined neighborhood U v ⊂ V c ∪ V o for each customer v ∈ V c ∪ V o (say, its 16 closest customers), a non-elementary route that contains a cycle starting with customer w can be generated if and only if this cycle contains a node v such that w ∈ U v . With such a relaxation, the coefficients a rv may take values larger than one.
We also apply decremental state space relaxation as proposed by Righini and Salani (2008). Here, we initially allow non ng-routes to be generated by only considering a subset of the unreachable resources. However, if a non ng-route is generated, then the subset of unreachable resources is enlarged such that this route can be no longer generated, after which the pricing problem is solved again.
Finally, we first solve the pricing problem in a heuristic manner to find any positive reduced cost variables. Only if no routes have been generated by solving the problem heuristically, we solve the pricing problem to optimality. Moreover, we also terminate the labelling algorithm early if the number of routes with a positive reduced cost which have been identified exceeds a certain threshold. Appendix B describes in detail the column generation process.

Valid inequalities
To limit the number of nodes in the search and usually the overall computational time, it is common to improve the upper bound obtained from the master problem by adding valid inequalities. Before branching, we first consider an adaptation of the well-known rounded capacity cuts (Laporte et al., 1985). Consider a subset of customers W ⊆ V c ∪ V o and let k(W ) = w∈W d w /Q be a lower bound on the number of vehicles required to service the customers in W . The traditional rounded capacity cuts would write as follows: where b vw r indicates how often route r ∈ R uses arc (v, w) ∈ A. It stipulates that at least k(W ) vehicles must traverse an arc entering in W . This inequality would be valid only if all customers in W must be visited. This is not the case for the row generation subproblem. Therefore, we develop a modified version of the rounded capacity cuts that reduce the right-hand side according to the selected players and selected optional customer clusters.
be a lower bound on the number of vehicles required to service the optional (resp. contract) customers in cluster V o l for l ∈ M (resp., set V c i for i ∈ N ). For a subset of customers W ⊆ V c ∪ V o , we formulate the corresponding modified rounded capacity cut as follows: where M (W ) denotes the subset of optional customer cluster indices l ∈ M for which W ∩ Here, we reduce the total number of vehicles required to serve the customers in W if either an optional customer cluster in M (W ) or the contracted customer set of a player in N (W ) is not covered exactly once in a solution. In that case, the number of vehicles required for serving W is reduced by a lower bound on the number of vehicles required to serve the customers in the corresponding cluster or set. Note that if z l = 1 for all subsets in M (W ) and s i = 1 for all players in N (W ), then (30) is equivalent to (29).
Proof. To show that inequality (30) is valid for conv(χ), it is sufficient to show that any solution S ∈ χ satisfies (30). LetŜ = (x,ŝ,ẑ) ∈ χ. Let W (Ŝ) ⊆ W be the subset of customers in W that are visited in solutionŜ andW (Ŝ) = W \ W (Ŝ) the subset of those that are not visited. First, let us deduce an upper bound on k(W ): The first equality comes from the definition of k(W ), whereas the second arises from a partition of the customers in W into the customers in W (Ŝ), the uncovered optional customers, and the uncovered contract customers. The first inequality stems from the properties of the ceiling function. The second one ensues from the relations (W (Ŝ) . Finally, the last equality is obtained from the definitions of k(W (Ŝ)), k o (l), and k c (i) combined with the facts thatẑ l = 0 for all l ∈ M (W ) andŝ i = 0 for all i ∈ N (W ).
Second, using the upper bound (31), we find the following lower bound on k(W (Ŝ)): Third, because only the customers in W (Ŝ) are visited inŜ, we can replace k(W ) by k(W (Ŝ)) in the traditional inequality (29) for W : and use the lower bound (32) to deduce inequality (30).
Next, we provide an example to illustrate that the modified capacity inequalities (30) can also cut off part of the feasible region if some of the player variables s i or the cluster variables z l are non-integral. A solution to the linear relaxation of (17)-(24) could have the following non-zero route variables x (0,1,2,0) = 2 3 , x (0,1,3,0) = 1 3 and x (0,2,3,0) = 1 3 . Let W = {1, 2, 3} be such that s 1 = s 2 = 1 and z 1 = 2 3 . It follows that the right-hand side of inequality (30) equals 5 3 while its left-hand side equals 4 3 . Hence, this modified rounded capacity inequality is violated.
To separate the modified rounded capacity cuts, we first run the heuristics provided by the package of Lysgaard et al. (2004) to separate the regular rounded capacity cuts and, then, check if each subset of customers returned yields a violated modified rounded capacity cut. A maximum of 100 cuts is added at a time.
To conclude this section, we would like to mention that we also implemented the limited-memory subset row cuts (lm-SRCs) of size 3, originally proposed by Pecin et al. (2016). In general, the lm-SRCs have shown to provide a good trade-off between an increase in computational time and a decrease in integrality gap (Pecin et al., 2017). However, we observed that they did not improve the computational performance of our algorithm. We believe that this is caused by the relatively small number of customers that can be included in a feasible route for our instances. Therefore, these cuts are not present in the final version of our algorithm.

Branching strategy
To derive integer solutions, we use the following hierarchical branching strategy. When an optimal solution to the master problem is fractional and branching is required, this strategy selects the first branching entity taking a fractional value according to the following order: 1. The sum of the player variables i∈N s i ; 2. A player variable s i ; 3. The sum of the cluster variables l∈M z l ; 4. A cluster variable z l ; 5. The total number of vehicles used r∈R x r ; 6. An arc-flow variable r∈R b vw r x r .
When multiple entities are available, the one taking the closest fractional value to 0.5 is chosen. Moreover, when choosing a node to branch on, we choose the node with the largest upper bound.

Acceleration strategies
In this section, we describe two acceleration strategies that can be applied to the basic row generation algorithm described in Section 3. First, throughout the algorithm, we store all generated columns in a pool which is shared among all branch-price-and-cut procedures. Hence, this pool is not only used when solving row generation subproblems, but also when determining best-case profits and worstcase profits. In this manner, we can generally provide a good initial set of columns for any call to a branch-price-and-cut algorithm.
Secondly, for the row generation subproblem, we terminate the branch-price-and-cut procedure as soon as a coalition corresponding to a violated or tight rationality constraint is identified, when an integral solution with a non-negative value is found. Here, it should be noted that the profit which has been determined for this coalition is not necessarily optimal. Hence, we still need to determine the best-case profit of the identified coalition, after which we add the corresponding best-case rationality constraint.

Computational results
In this section, we first describe the instances used for our computational experiments and present our experimental plan. Then, we report the computational results obtained and discuss the quality of the computed solutions.

Instances and experimental setup
We constructed instances of the JNVRGOC based on the CVRP instances of Augerat (1995) as follows. Specifically, we considered the instances of the A-set which involve between 31 and 79 customers in total. For each of these instances, we defined nine JNVRGOC instances by considering 3, 5 and 7 players as well as 3, 5 and 7 clusters of optional customers. Recall that the number of customers is given by |V |−1. We assigned the first n 0.7(|V |−1) n customers to the players, such that i(v) = (v mod n)+1 with v ∈ 1, . . . , n 0.7(|V |−1) n . The remaining customers n 0.7(|V |−1) n + 1, . . . , |V | were divided among the clusters of optional customers such that l(v) = v − n 0.7(|V |−1) n + 1 mod m + 1 with v ∈ n 0.7(|V |−1) n + 1, . . . , |V | .
Consider an instance of the JNVRGOC with players {1, . . . , n}, contract customers V c and optional customers V o . For each instance, we assign each player i ∈ N precisely enough vehicles to cover its own customers: k i = v∈V c i dv Q . Moreover, given a cluster of optional customers V o l with l ∈ M , we define the reward p o l as −0.8 · GCPTPCC(∅, V o l ), where −GCPTPCC(∅, V o l ) denotes the optimal value of a CVRP defined over the customers in V o l . We solved these instances using four algorithms. The first algorithm, denoted by rg, is the row generation algorithm described in Section 3.2. To determine the performance of the modified capacity cuts (30), we also consider an algorithm, denoted by rg no mcc, which is the row generation algorithm rg but excluding the modified rounded capacity cuts. Moreover, we also execute two enumeration algorithms enum rg and enum all. The former enumerates a priori the best-case profit for each coalition, and only determine the worst-case profit for coalitions associated with tight rationality constraints at each iteration of Algorithm 1. In the latter, we enumerate the best-case profit and the worst-case profit for each coalition, which allows us to solve (4)-(8) to optimality. Algorithms enum rg and enum all are used as benchmarks with respect to computation times and optimal solution values, respectively.
All algorithms were implemented in C++, using IBM ILOG Optimiser 12.8.0 to solve any linear programming problems. The computations were conducted on a single thread of an Intel Xeon Gold 6130 @ 2.1 GHz with a turbo of 3.7 GHz and 16 GB of RAM. Unless otherwise specified, a time limit of 7,200 seconds (2 hours) is enforced for solving each instance.
Summarised results obtained for these small instances are shown in Table 1. They are grouped by the number of players n and the number of optional customer clusters m. For each algorithm, two columns are presented to report the number of instances solved to optimality within the time limit (OP T ), and the average time taken to solve these instances (T ). For each (n, m) combination, we were able to solve significantly more instances with algorithm rg than with algorithm rg no mcc. For example, we solved 8 of the 10 instances with 7 players and 3 clusters of optional customers with algorithm rg, compared to only 2 instances with algorithm rg no mcc. This clearly demonstrates the effectiveness of the modified capacity cuts. Moreover, the effectiveness of the row generation algorithm is illustrated by comparing algorithms rg no mcc and enum rg. Here, we can see that even without the capacity cuts, algorithm rg no mcc is able to solve more instances than enum rg for the 7 player instances. For these instances, the difference is much more striking when comparing algorithms rg and enum rg Furthermore, it can be seen that algorithm rg does not outperform the enumeration algorithms enum rg and enum all for instances with 3 players. For these instances, only 6 coalitions have to be considered, which causes most, if not all, coalitions to be generated by the row generation algorithm with the additional overhead of solving the row generation subproblem multiple times. However, for the 7-player instances, we are able to solve significantly more instances with algorithm rg in significantly less time when compared to enum rg and enum all. Here, it should be noted that enum all is an exact algorithm whereas algorithms rg and rg enum may yield a solution that is not feasible to (4)-(8).
Next, we discuss the performance of algorithm rg in more detail. A summary with respect to the performance of this algorithm for each combination (n, m) is provided in Table 2. We consider the following summary statistics: the number of instances solved (OP T ), the average run time in seconds (T ), and the average number of rationality constraints of the form (11) that have been generated (I). Moreover, we also consider the proportions of the time spent solving the row generation subproblems (T i ) and all other routing problems (T g ), as well as the average number of best-case (BP ) and worst-case (W P ) problems solved. Finally, we also list the average number of branch-and-bound nodes explored (BBN ) and the modified capacity cuts generated (M CC). It should be noted that the averages are computed only over the instances which were solved before reaching the time limit. The complete computational results for each individual instance can be found in Appendix C. On average 42%, 30% and 15% of all possible coalitions were generated by algorithm rg on the 3, 5 and 7-player instances that have been solved, respectively. Here, it should be noted that the maximum number of coalitions which could have been generated is equal to 6, 30 and 126 for the 3, 5 and 7-player instances, respectively. Clearly, the percentage of coalitions generated decreases as the number of players increases, which illustrates the effectiveness of a row generation procedure for instances with a relatively high number of players. Moreover, the average size of coalitions generated is 1.7, 3.0 and 3.4 for the 3, 5 and 7-player instances, respectively.
The time spent on the heuristic is almost split equally between solving the row generation subproblems and determining best-case and worst-case profits. However, we can observe that less subproblems are solved than the number of profits computed, which shows that computing profits is on average less time-consuming. This is not surprising given that, to do so, some player and cluster variables are fixed. Moreover, it is interesting to note that, for 3-player instances, the best-case profits have been determined for almost every coalition. This is clearly not the case for the 5 and 7-player instances. Finally, we can observe that the total numbers of branch-and-bound nodes explored and cuts generated increase with the number of players but not with the number of optional customer clusters.
To conclude this section, let us remark that we also considered instances in which each player was assigned an additional vehicle compared to the minimum number of vehicles required. However, these instances did not provide any additional insights and, therefore, their results have not been included in this paper.

Solution quality
In this section, we assess the quality of the solutions produced by algorithm rg. To do so, we compare them with the optimal solutions obtained for model (4)-(8), namely, those computed by algorithm enum rg. To find more optimal solutions with this algorithm and, thus, make a comparison on a larger number of instances, we have increased its time limit to 36,000 seconds. The time limit imposed for algorithm rg has, however, remained equal to 7,200 seconds.
The results are summarised in Table 3. For each combination of n and m, 26 instances were considered. For each algorithm, we report the number of instances solved to optimality within their respective time limit (OP T ) and the average objective value of the computed solution, denoted α for algorithm rg and α for algorithm enum all. Moreover, when algorithm enum all was able to compute the best-case and worst-case profits of all coalitions, it becomes possible to determine if the allocation obtained by algorithm rg is feasible for model (4)-(8) and, if so, what is the objective value of this allocation according to this model. The columns SH and IN F indicate the number of instances for which both algorithms terminated before their respective time limit and, among these instances, the number of allocations computed by algorithm rg that are infeasible for model (4)-(8), respectively. Indeed, such an allocation y can be infeasible if there exists no α value such that all constraints (5) hold, i.e., if there exists a coalition S for which y(S) < v W (S). Finally, for both algorithms, column α sh reports the average value of the computed coalitions according to model (4)-(8). Because algorithm enum all computes an optimal solution, the value of α sh obtained by algorithm rg is always less than or equal to that derived by algorithm enum all. The gap between these two values indicates the quality of the solution computed by algorithm rg. Again, the complete results for each instance are provided in Appendix C. From these results, we make the following observations. First, if we consider the objective value α , we see that players are on average allocated at least 96%, 83% and 66% of their best-case profit for the 3, 5 and 7-player instances, respectively. Here, it is interesting to note that players are on average allocated less profit relative to their best-case profit if the size of the grand-coalition increases. A similar pattern occurs with respect to the optimal value α, which is on average 96%, 78% and 58% for the 3, 5 and 7-player instances, respectively. We believe that the decrease in relative allocated profit is partially accounted for by the structure of the instances. For example, consider a given instance with a fixed number of optional customer clusters. Recall that each player has precisely enough vehicles to cover its contract customers. Hence, the overall number of vehicles is likely to be larger for a larger number of players as the customers are served less efficiently. The larger number of vehicles may cause smaller coalitions to already be able to serve most clusters of optional customers, thereby reducing the value created by having many players collaborating. As a consequence, each coalition is allocated less when compared to their best-case profit.
Moreover, we observe that the worst-case profit core is non-empty for all instances solved by the algorithm enum all. This suggests that the allocation is suitable for use in practice as there is always an incentive to cooperate. Here, it should be noted that the allocation computed by algorithm rg may not be in the worst-case profit core, even if it is non-empty. Specifically, in 3%, 33% and 36% of the cases, this allocation is not in the worst-case profit core for the 3, 5 and 7-player instance, respectively, as indicated by the values reported in the columns SH and IN F . However, for the allocations that are in the worst-case core, the objective value is comparable to that of the optimal allocation com-puted by algorithm enum all (see both columns α sh ). The average deviations between these values are 1%, 7% and 13% on average for the 3, 5 and 7-player instances, respectively.
For each computed allocation, the carriers are given an incentive to collaborate as they are allocated at least as much profit when compared to their worst-case profit. However, in theory, the collaboration between multiple carriers may be hindered if an allocation is proposed which is not in the worst-case core. If this is the case, a subset of carriers may want to leave the collaboration. Nonetheless, in practice, it is very difficult for a subset of carriers to verify whether an allocation is in the worst-case core. Moreover, if a subset of carriers identifies that a given allocation is not in the worst-case core, the corresponding violated rationality constraints can be incorporated after which a new allocation can be easily determined.

Concluding remarks
We proposed a heuristic row generation algorithm to determine core allocations for the JNVRGOC, based on both the worst-case profit and the best-case profit. Our computational experiments have shown that an enumeration algorithm which requires computing the worst-case and best-case profits for all possible coalitions becomes rapidly inefficient as the number of players increases. At the opposite, the performance of our row generation approach is less impacted by such an increase. Moreover, our results suggest that the modified capacity cuts do significantly reduce the computation time for the row generation algorithm. As for the quality of the solutions produced by the proposed heuristic, we find that the average deviation of their values with respect to those of the optimal allocations is relatively small. On the other hand, our approach might sometimes fail to find an allocation in the worst-case core when it is not empty.
In order to improve the performance of our algorithm it is crucial to be able to estimate good lower bounds for the worst-case profits. It would require further research to determine such lower bounds.

Appendix A Emptiness of the imputation set
Consider the 3-player instance of the JNVRGOC with N = {1, 2, 3} as presented in Figure 4.

B Details on the column generation algorithm
The column generation algorithm proceeds as follows. At each iteration, the restricted master problem is solved. If the number of columns it contains exceeds 5000, then all positive reduced cost columns are removed and stored in a pool of columns. Then we seek negative reduced cost columns using different procedures. As soon as one procedure finds negative reduced cost columns, these columns are added to the restricted master problem which is then re-optimized to start a new iteration. The procedures, which are called in the following order, are as follows: 1. Check if any of the columns in the pool of previously removed columns have a negative reduced cost; 2. Apply heuristic labelling algorithm HLA1; 3. Apply heuristic labelling algorithm HLA2; 4. Apply heuristic labelling algorithm HLA3; 5. Apply heuristic labelling algorithm HLA4; 6. Apply heuristic labelling algorithm HLA5; 7. Apply heuristic labelling algorithm HLA6; 8. Apply the exact labelling algorithm.
All labelling algorithms solve the ng-route relaxed pricing problem, where the neighbourhoods consist of the 16 closest customers. In heuristics HLA1 to HLA4, we do not apply decremental state-space relaxation because dominance is performed only on the reduced cost of a route and a network of reduced size is considered. In HLA1 to HLA4, we restrict the arcs to the arcs between each customer and its 2, 4, 8 and 12 closest neighbours, respectively. In HLA5, HLA6 and the exact labelling algorithm, decremental state-space relaxation is applied as full dominance is considered. However, in HLA5 and HLA6, a reduced network is considered, namely, we restrict the arcs to the arcs between each customer and its 2 and 4 closest neighbours, respectively.

C Detailed results for the algorithms RG and EN U M ALL
In Tables C.1-C.9, we present detailed results for each instance solved with algorithms rg and enum all. For each instance, we report the following statistics for algorithm rg: α : The objective value returned by algorithm rg; α: The objective value of the computed allocation with respect to (4)-(8); T : The overall computation time in seconds; I: The number of rationality constraints of the form (11) generated; T i : The percentage of time taken to solve the row generation subproblem; T g : The percentage of time taken to solve all routing problems excluding the row generation subproblem; BP : The number of best-case profits computed, including that for the grand-coalition; W P : The number of worst-case profits computed; BBN : The overall number of nodes explored in all branch-price-and-cut procedures; M CC: The overall number of modified capacity cuts generated.