s2fieldsofstudy:
Business
Computer Science

text:
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.


RECOMMENDATIONS FOR IMPROVING THE ISO 14001 CERTIFICATION BASED ON THE COMPANY’S PERCEPTION ANALYSIS OF THE CERTIFICATION OBSTACLES AND BENEFITS

Introduction: Environmental management systems (EMS) were used commonly by companies to control industrial impacts and support environmental sustainability. In achieving SDG’s indicators to focuses on improving sustainable practices in the company environment, the government faces a tough challenge in increasing ISO 14001 certified companies. This study aimed to analyze the barriers and benefits of ISO 14001 certification in the industrial sector and recommend encouraging companies to carry out ISO 14001 certification. Methods: This study used a descriptive analysis method to identify the perception of ISO 14001 certified company practitioners of the certification barriers and benefits. Through survey questionnaires, data collection was conducted to 83 ISO14001 certified companies with a response rate of 49.4%. Results and Discussion: The main barrier in performing the ISO 14001 was the cost of implementation and certification. The highest benefit of ISO 14001 certification was to improve the company's image. A total of 83% of the companies believed that the benefits of ISO 14001 certification outweighed the costs incurred. Conclusion: The companies did not have significant barriers in conducting the ISO 14001 certification and classified into the medium category. The ISO 14001 certification could provide environmental sustainability, social, market, and economic benefits. The government needs to support the interest of companies in conducting the ISO 14001 implementation by overcoming the obstacles and maximizing the benefits. ORIGINAL RESEARCH Open Access

INTRODUCTION
The industrial sector provides many benefits in improving the community economy and welfare. For example, industrial manufacturing contributes to an income state of around IDR 6,749 trillion and accommodate 6.1 million workers in Indonesia (1)(2). However, industrial activities might also cause environmental degradation such as exploitation of natural resources, loss of biodiversity, environmental pollution, and excessive energy consumption. The industrial sector needs reasonable controlling to carried out based on the company's environmental aspects (3)(4). The results of previous studies showing the percentage of environmental aspects that can arise from the industrial sector including waste, gas emission, energy and water consumption, environmental risk, and noise (5).
The environmental impact of industrial activities is significantly greater in developing countries than in developed countries (6). Companies need to prevent the worse impact by implementing good practices in the environmental management systems (7). A study shows that the EMS implementation could control the significant environmental impacts arising from operational activities and achieve the company's environmental objectives (8). In general, ISO 14001 standard is widely adopted by companies according to their goals in support of environmental sustainability (9). The previous study shows that implementing a comprehensive environmental management system positively correlates with a company's environmental performance, such as resource use, compliance with government regulations, productivity, and stakeholder relations (10). One successful good practice at a textile company is controlling resources and energy consumption (11).
ISO 14001 certification will carry out after the company implemented the EMS protocols. The certification process will assess the conformity of the requirements of the ISO 14001 standard with the whole procedure in the company. Implementation and certification of ISO 14001 provide many benefits related to environmental, commercial, financial, organisational, and social relations (12). However, in addition to obtaining several benefits, companies also face several obstacles in carrying out ISO 14001 certification (13)(14)(15) and determining the outcomes (16). Furthermore will affect the company's decision whether to continue with ISO 14001 certification or not (17). Previous research has been conducted to identify the obstacles faced by companies in implementing ISO 14001 in Indonesia (18). Similar research related to ISO 14001 certification mainly was carried out in several developed countries such as Italy (19)(20), Spain (15), UK (21)(22), Australia (10). However, studies related to this theme are still rarely done in developing countries (18,(23)(24). The ISO 14001 certification in developing countries must be improved, especially in Indonesia, as each country has different regulatory and cultural settings. Improvements need to create a possibility that the environmental management system implemented in developing countries is different from developed countries (25).
The ISO 14001 certification indicates one of the SDG's targets, number 12.6, which focuses on improving sustainable practices in the company environment (26). This commitment is stipulated in Regulation of President of Republic Indonesia No. 59 Year 2017 on Implementation of Achievement of Sustainable Development Goals (27). Implementing the ISO 14001 certification in industrial sectors is also one of the priority programs set out in the Medium Term Development Plan Year 2020-2024. The Indonesian government targets additional 5000 companies to have ISO 14001 certification by 2024 (28). This target is a big challenge for the Indonesian government because certified companies are still low at around 133 companies each year (29).
This study aims to analyse companies points of view regarding the benefits and obstacles of the ISO 14001 certification. Furthermore, this study is expected to increase the interest of companies to carry out the ISO 14001certification and provide recommendations for the government to help companies overcome these obstacles.

METHODS
The type of this study was a quantitative approach. The data respondents collected through a Google Form Application. The population was amount 83 companies that were still being certified by the PT.X as an ISO 14001 agency. PT.X was one of the ISO 14001 certification bodies accredited by the National Accreditation Committee. The respondents' criteria were people who understood and were responsible for the companies' ISO 14001 certification process. To ensured that criteria, we met directly by contacting the person listed in the company data provided by the PT.X. The authors also reiterated that the questionnaires must be filled out by people who met these criteria during the communication with the company personnel, either by telephone, email, or letter via courier. We guaranteed that the identity of the companies and the respondents were kept confidential from disclosure to the public. The distribution of the questionnaires resulted in responses from 41 company representatives.

External Barriers
High cost of implementation and certification (15,17,32,33,36) Increased volume of administrative work and documentation (15,32,44) Difficulty in applying the standard and the complexity of the implementation process (14,20,32) Long certification process (44)

Likert Scale Analysis
The questionnaire used the Likert Scale with a range of 1-5, and the assessment was then analysed the mean, median, and standard deviation. The median value showed the mean value. At the same time, the standard deviation was supposed to show the distribution of data or the average deviation distance of data points. The average result was the primary data used to analyse the obstacle parameters and benefits of ISO 14001 certification. The mean used to categorize the parameter values could indicate the position of the parameter ranking in questions (30). The mean value of the parameters was categorized by using a predetermined criterion score (31). The scores of the criteria used to categorize the mean value of the parameters could be seen in Table  2. The list of obstacles and benefits parameters to ISO 14001 certification was obtained from the literature research. This study used 11 obstacles parameters and 15 benefits parameters of ISO 14001 certification listed in Table 3 and Table 4. The authors also asked about how long the companies have obtained the ISO 14001 certification, perceived difficulty, the costs incurred, the company characteristics and respondent characteristics. The data obtained were processed using SPSS software version 21 and Microsoft Office Excel 2010 and later analysed using descriptive statistical methods.

Validity Test and Reliability Test
The validity of the research instrument was determined by testing the validity and reliability of 30 samples using the Pearson Product-Moment method. The basic formula used to test the validity is as follows: The reliability test showed that the Cronbach Alpha values for the barrier variable and benefit variable were 0.926 and 0.943, respectively. These results stated that all variables were reliable.

Companies Characteristics
The information about company characteristics based on sector and scale could be seen in Tables 5  and 6. The majority were manufacturing companies (65.9%) that produce various products such as medicine, fertilizers, fodder, cables, and electronic goods. Meanwhile, 19.5% engaged in transportation, oil and gas services, and waste treatment services. Moreover, 14.6% of companies were in other sectors (14.6%) such as plantations, trade, and energy.  These companies consisted of exporting companies (43.9%) and non-exporting companies (56.1%). The company's market reached the international market (43.9%), national market (46.3%), and regional market (9.8%). Apart from implementing and being certified to ISO 14001, these companies were also certified to other standards such as ISO 9001, ISO 22000, ISO 45001/OHSAS 18001, and ISO 50001 that shown in Table 7.

Obstacles on the ISO 14001 Certification
The cost of implementation and ISO 14001 certification was high-category obstacles for companies (3.61); whereas, another was included in the moderate category that was the lack of available resources (3.29), lack of additional training related to the environment (3.27), difficulties in implementing standards and the complexity of the implementation process (3.24), increasing volume of administrative and documentation work (3.22), lack of environmental-friendly culture (3.22), time consumption for standard application (3.15), lack of commitment (2.71), and lack of financial capacity (2.66). The frequency distribution of ISO 14001 certification obstacles shown in Table 8. One of the obstacles in carried out ISO 14001 certification was the long-time duration of the certification process. Each company took different times to carry out the certification process, from official registration to certification bodies until to obtain the certificates. Most companies needed about 4-7 months to complete the certification process (59%). Figure 1 showed the average percentage of the ISO 14001 certification duration.
Most of the companies (63%) stated that getting an ISO 14001 certificate was still slightly difficult. Figure 2 showed the information regarding the level of difficulty in obtaining an ISO 14001 certificate.

Benefits on the ISO 14001 Certification
Based on the frequency distribution of ISO 14001 certification in Table 9, it concluded that almost all the benefits of ISO 14001 certification were obtained in the high category. The most dominant benefits of ISO 14001 certification included the improved corporate image, increased compliance/adherence to government regulations, increased customer satisfaction, and increased competitiveness. Based on the data obtained, the companies thought that the market and social benefits outweighed the environmental benefits. Financial benefits in easy access to loans and reduced insurance coverage had the lowest score and fell into the relatively moderate category. Therefore, the benefits of ISO 14001 certification were considered to outweigh the costs. This conclusion can be drawn from Figure 3, which informs that most companies (83%) thought so. In general, it can be concluded that ISO 14001 certification can provide benefits for companies.

ISO 14001 Certification Obstacles Analysis
Based on the respondents' answers, the most critical obstacles were the cost of implementing and certifying with ISO 14001. Furthermore, many studies also said that cost to implemented and certified ISO 14001 was a significant external constraint (11,13,15,18,32). The companies considered that the costs were relatively expensive to carry out ISO 14001 certification. Most of the ISO 14001 certification agency in Indonesia were private with profit-oriented. Certification costs also vary significantly between certification agencies. There is no standard cost of ISO 14001 certification at this time. The amount of the certification fee depends on the contract agreement between the company and the certification agencies.
At the initial implementation, the costs incurred were generally considered to outweigh the benefits and gains (33).
The incurred costs usually covered training fees, consulting fees, processing fees, certification registration fees, and certification maintenance (34). Companies also require high costs for environmental technology investment and maintenance (18). This cost factor determines the sustainability of ISO 14001 certification, especially at small companies (32). Findings in this study showed that companies considered the long term benefits of this certification was greater than the costs incurred. They could still overcome the cost and would continue their certifications. Otherwise, companies would not continue their certification even though they could pay the certification fee. Furthermore, this was evidenced that almost all companies planned to re-certify when the due date.
Another obstacle that needs to be considered is the lack of resources, including personnel, facilities, and technology. Without sufficient resources, it difficult to implemented ISO 14001 properly, primarily to fulfil the clause requirements. Sufficient resources are essential to successfully ensuring the sustainability of the environmental management system implementation (35). Companies also face difficulties in procuring additional training related to the environment, even though it is one of the efforts to support the EMS. Staff training is sometimes not a priority for company management, especially at small companies (36). Although many companies have been able to create training programs, they have not been able to identify training needs correctly. Properly training can lead the employee competence to implement EMS. These competencies in conducting environmental audits, identification and measuring environmental aspects, and controlling the environmental impacts (37).
Other obstacles that need to be considered are difficulties in implementing administrative and documentation work. A previous study at Italian companies showed that the difficulties companies experience experienced an increase in the complexity of procedures due to the implementation of clauses (20). Furthermore, increasing workload occurs because a large amount of documentation must be produced regularly requiring people with special soft skills, this obstacle is directly related to personnel work hours in the company (15).
The lack of an environmentally friendly culture was also a barrier for companies to carry out ISO 14001 certification. The employees and management behaviour would affect the level of contamination and energy consumption (37). Some study mention that low employee involvement and awareness were of the main obstacles in carried out the ISO 14001 certification (14,20). Our study findings, can be concluded that the commitment of top management and employees went synergistically. Therefore, it can increase the company's chances of obtaining more optimal benefits of ISO 14001 certification.
Our study showed that 67% of the companies obtained certificates within 4-7 months after submitting an official application. Obtaining the certificate within 4-7 months is categorized as a relatively brief time and still within reasonable limits. The companies may resolve the obstacles more efficiently and thus can complete the certification process quickly. However, getting certificates faster did not mean that the companies have a better system than to a longer certification process.
In this study, a company's financial capacity was not a significant obstacle. Despite the fact, this is the main barrier faced by a company (23,32). Most of the companies in this study were large companies (82.9%) and thus were possible to have better financial capabilities than small companies (17.1%).

Analysis of ISO 14001 Certification Benefits
This section discusses the benefits obtained by companies after carrying out ISO 14001 certification. These results proved that ISO 14001 certification could significantly benefit the companies in terms of environmental, social, market, and financial benefits. The company image is significant to get a good impression from the public, both regarding its concern for the environment and its product quality. In addition, it will increase the trust of customers and external stakeholders. Companies certified with ISO 14001 widely believed to be environmental-friendly companies.
The benefits of increasing conformity/obedience to government regulations are not significantly different from improving corporate image. The ISO 14001 standards encourage companies to follow government environmental regulations. A company will try to minimize the amount of industrial and domestic waste also the levels of contamination to do not exceed the environmental threshold limit value. This requirement is set out in clause 6.1.3 of ISO 14001, which states that the company must determine how compliance obligations apply (35).
Customer satisfaction increases as a benefit would reach by the company that ISO 14001 certified. A report from Europe showed that European public awareness of environmental issues requires companies to certify ISO 14001 correlated consumer satisfaction with the company (13). Moreover, companies with international markets must be ISO 14001 certified to be accepted by consumers from developed countries with high environmental awareness.
Another benefit is increasing competitiveness between certified and uncertified ISO 14001. A certifying company appeared more superior and more substantial competitiveness than uncertified companies in the markets (38)(39). However, this competitiveness also depends on competing companies. If there are already many competitors certified with ISO 14001, the competitiveness can be insignificant (38).
Implementation of ISO 14001 also improvement the company work culture as good cooperation between employees, communication between management and employees runs smoothly, and increase the responsibilities. The good involvement of company leaders may improve employee participation and motivation. Good cooperation within the company impacted in increasing the productivity indirectly (11,37,40). Besides in improving the company's internal relations, the ISO 14001 certification also improve good relations with the community and regulators to minimize the complaint.
The next benefit is obtaining tenders more easily. Possession of ISO 14001 certification is sometimes required to get offers or compete to get tenders from the government or company partners. Certifying companies with ISO-14001 already usually will choose suppliers who also certified have done. The government provide opportunities to company to participating tenders if they fulfil environmental obligations, which can be proven by possession of ISO 14001 certificate. This benefit was not much different in score from increasing market share and increasing profits from sales. These three benefits can provide financial opportunities for the companies directly. Besides that, the company could easily access soft loans, reduce insurance coverage, investment funds, especially from the financial industry that concern encouraging environmental sustainability.
Some benefits directly correlated to the environment is consisting of decrease pollution, save the energy, use of raw materials, and volume of generated waste. The ISO 14001 implementation encourages companies to strive for cleaner production, for example, by using eco raw materials and reducing the generated waste (41)(42). The companies also monitored the environmental parameters by applying the Life Cycle Assessment principles regularly.
The results showed that the perception of corporate respondents on the social benefits of ISO 14001 certification was greater than other benefits. The environmental benefits of ISO 14001 certification were primarily determined by how the companies internalized the requirements of the ISO 14001 standard. Social benefits are obtained from increasing reputation, which is more symbolic, while market and financial benefits are obtained indirectly after the companies obtain environmental and social benefits. Companies can adopt the ISO 14001 implementation policies for representational purposes, although they will not implement operational activities. The actual operation might be different from the policies. The company's decision to adopt the strategy of implementing ISO 14001 symbolically or substantively can affect the outcomes (43). The companies in the manufacturing sector agreed that ISO 14001 certification increased profits from sales locally and broadly. The manufacturing companies were more benefited significantly from increasing market share than service companies. Based on the benefit analysis, it can be seen that the benefits obtained by the companies were primarily non-cashable.

Recommended Efforts to Promote ISO 14001 Certification
The government might stimulate the company to carry out ISO 14001 certification by overcoming the barriers and optimizing the potential benefits. Cost of implementation and certification was the highest barrier in ISO 14001 certification. The government might overcome the barrier by encouraging more certification bodies from government institutions; in turn, companies can obtain relatively cheaper ISO 14001 certification costs.
The government can also determine the standard cost of ISO 14001 certification for government ISO-14001 certification bodies. Currently, only three certification bodies from government institutions have been accredited by the National Accreditation Committee for a specific scope. Barriers related to difficulties in implementing the ISO 14001 standard, which is considered complex, and to inadequate environmental training, can be overcome by increasing incentives through training and technical guidance related to the ISO 14001 standard for companies. This effort can also improve the competence of company personnel to internalize the certification requirements to obtain optimal environmental benefits.
In optimizing financial benefits i.e., easy access to soft loans as business capital, the government can increase green financing to encourage companies to take the ISO 14001 certification. Green financing is a financial-related policy that encourages financial industry players to provide convenience for those who seek for minimizing possible environmental impacts from their activities. Green financing has been widely carried out in developed countries such as in America and Europe.