On the collaboration uncapacitated arc routing problem

On the Collaboration Uncapacitated Arc Routing Problem Elena Fernández ∗ 1 , Dario Fontana † 2 , and M. Grazia Speranza ‡ 2 1 Department of Statistics and Operation Research, Universitat Politècnica de Catalunya-BcnTech, Spain 2 Department of Economics and Management, University of Brescia, Italy Abstract This paper introduces a new arc routing problem for the optimization of a collaboration scheme among carriers. This yields to the study of a protable uncapacitated arc routing problem with multiple depots, where carriers collaborate to improve the prot gained. In the rst model the goal is the maximization of the total prot of the coalition of carriers, independently of the individual prot of each carrier. Then, a lower bound on the individual prot of each carrier is included. This lower bound may represent the prot of the carrier in the case no collaboration is implemented. The models are formulated as integer linear programs and solved through a branch-and-cut algorithm. Theoretical results, concerning the computational complexity, the impact of collaboration on prot and a game theoretical perspective, are provided. The models are tested on a set of 971 instances generated from 118 benchmark instances for the Privatized Rural Postman problem, with up to 102 vertices. All the 971 instances are solved to optimality within few seconds. 1 Introduction Collaboration among carriers becomes more and more valuable because of surging pressures to improve protability and to reduce costs. Nowadays, collaborative transportation is regarded as one of the major trends in transportation research. Indeed, increasing carrier insurance and fuel costs combined with a more intense market competition lead carriers to look for new and more ecient solutions. Primarily, carriers ∗ [email protected] † dario.fon[email protected] ‡ sp[email protected] 1 focus on reducing costs looking for ecient route planning and scheduling. These costs are strongly correlated with the location of customers. Whereas a carrier would benet from having its customers concentrated in the same area, for a number of reasons they may end up being geographically dispersed. This forces the carrier to create long routes for its vehicles, with associated high cost in terms of vehicles usage and drivers time. It is often the case that customers that are inconveniently located for a carrier are conveniently located for a dierent carrier. Thus, a collaborating set of carriers can redistribute the customers, opening up, through collaboration, cost saving opportunities otherwise non achievable. In general, there are dierent types of carriers: general, regional or functional. The general carrier is non specialized and has the assets and the logistics to serve all its customers taking care of all kinds of item distributions. Instead, a regional carrier is more bound to a dened geographical service area whereas a functional carrier serves a specic market or specic goods that require a specialization in transportation. Hence, for instance, a regional carrier can rely on a general one to serve customers outside its service area, or a general carrier can choose to handle particular goods (such as furniture, frozen foods) through a functional carrier. Logistic collaboration can be pushed further considering that it allows carriers to increase the average load of the vehicles. In fact, also in the case the customers are located in the same area, the load to be delivered in a trip by a carrier may be substantially lower than the vehicle capacity and make the individual trip non protable. A carrier that has to deliver a certain amount of goods that lls only part of the capacity of its smallest vehicle may borrow a vehicle of the right size from another carrier or transfer the load on a vehicle of another carrier traveling to the same area at the same time. Increasing attention to the environmental impact of emissions in cities represents an additional strong motivation to study collaboration among carriers, since local authorities increasingly push carriers to nd new policies and new technological and logistical solutions that improve city logistics. In [31] challenges and pressures faced by carriers to cooperate to make urban freight transport more ecient are pointed out, and best practices actually brought into practice in The Netherlands are presented. Recently, collaboration has been enhanced by advances in information and communication technology that have enabled information sharing among carriers. Information can be shared in two alternative ways. In a centralized collaboration scheme, a central decision maker redistributes customers and/or logistic assets among carriers. This decision maker may be a third party who acts in a non-partisan way or may be a large carrier that resorts to other carriers to manage all its orders and customers. In a decentralized collaboration scheme, carriers exchange their orders individually or in clusters. In this case, carriers cooperate at the same level trusting each other for the information shared. All the above considerations and approaches apply to both truckload or less-than-truckload carriers. 2 In this paper, we focus on situations where collaboration is managed in a centralized way. We consider a set of carriers cooperating under the guidance of a central station that acts in a non-partisan way. Each carrier has a depot and a set of customers. Each customer is represented with an arc and its service generates a revenue. Each carrier identies a subset of customers that it wants or needs to serve. These customers may be the most easily served, the most protable or the most strategic ones. The remaining customers are dened as shared customers, that is customers that may be served by other carriers. A shared customer may end up being served by the carrier that decided to share it, when combined with customers shared by other carriers. Part of the revenue of a shared customer goes to the carrier that decided to share the customer and part goes to the carrier that actually serves it. We allow a shared customer not to be served by any carrier of the coalition. In this case the revenue is not collected by any carrier. This corresponds to the situation where the customer is not protable for any carrier of the collaborating group and in a further phase a dierent and interested carrier will be searched. We assume that each carrier has one vehicle and that vehicle capacity is not relevant, that is the vehicles are uncapacitated. The motivation for studying this problem comes from potential applications. In general, applications arise in private companies oering services which allow competition and collaboration, and where customers may be modelled as arcs of a network. As an example we mention home pick-up and delivery, including private mail and small packaging distribution, and taxi services. For example, the problem that we address can model a group of independent taxi drivers collaborating under the guidance of a central station. We call the proposed problem, that may be seen as belonging to the class of arc routing problems with prots, Collaboration Uncapacitated Arc Routing Problem (CUARP). We study two dierent variants of the CUARP. In the rst one the goal is the maximization of the total prot of the coalition of carriers, independently of the individual prot of each carrier. The second variant includes a lower bound on the individual prot of each carrier. This lower bound may represent the prot of the carrier in the case no collaboration is implemented. We formulate mixed integer programming models for the two variants of the problem and study their relations with well-known arc routing problems. We also look at the CUARP from a game theory perspective. As it is usual in arc routing problems, the proposed formulations have a number of connectivity constraints which is exponential in the number of customers. This leads us to study the separation problem for such constraints. We solve the formulations for the two proposed variants with a branch-and-cut algorithm and quantify the impact of collaboration. Starting from 118 benchmark instances for the Privatized Rural Postman problem, we generate a total of 971 instances, with 2 or 3 carriers and varying characteristics, such as dierent locations of the depots and dierent thresholds for the prot. We solve all instances within few seconds. On each instance we compare the optimal solution obtained in the case where no collaboration is allowed with the case where collaboration is allowed, and show that the prot of the coalition increases up to twice or even three times the prot achieved without collaboration. 3 The rest of the paper is organized as follows. Section 2 introduces the relevant literature. The two variants of the CUARP are formally described and formulated in Section 3. Section 4 presents the theoretical results. In Section 5 we describe the separation procedure for the connectivity constraints that is used in the branch-and-cut algorithm. Data generation and computational experiments are described in Section 6. Finally, conclusions and future work are discussed in Section 7. 2 Literature review The literature on collaboration in transportation can be divided in two streams, one on vertical and the other on horizontal collaboration. Vertical collaboration arises when shippers and customers collaborate to help each other optimize their objective, while horizontal collaboration takes place when shippers collaborate among them (and/or the same do customers) at the same logistic level. Ergun et al. [19] develop a collaboration model among shippers, involving only full truckload companies, to identify tours that minimize asset repositioning costs. The same authors discuss in [18] how to reduce truckload transportation cost through the identication of repeatable, dedicated continuous move tours using collaboration among carriers to reduce the need for repositioning and lowering costs. Mason et al. [28] focus on customer driven supply chain and freight management with the aim of studying if collaborative models for management transportation give optimized solutions. Some authors addressed carrier collaboration from a perspective of costs and prots allocations, possibly within a game theory context. Figliozzi [20] proposes a setting in which a set of carriers, each with its own customers, has some incentive to submit all customers requests to a centralized collaborative decision making mechanism based on sequential second-price auction. Ozener et al. [30] focus, instead, on reducing costs through collaboration. Given a set of lanes carriers have to serve, their aim is to set up a process to exchange lanes either sharing or not sharing information about customers and/or side payments. Argawal and Ergun [1] study transportation networks that operate as an alliance among dierent carriers. They focus on formation of alliances and network design using both mathematical programming and game theory to investigate the mechanism that leads to an optimal collaborative strategy. In contrast to those studies, in our setting we deal with a network of carriers (regional or functional) that form a coalition to collaborate and we consider as a given fact that collaboration is better than competition, as pointed out in Argawal [2], Meyer [29], and Fugate [21]. Audy et al. [9] and Krajewska et al. [26] are case oriented papers. The former deals with the supply chain of the Canadian furniture industry, while the latter deals with more general coalitions among carriers. Both make use of game theory to allocate cost among companies, customers, carriers and coalitions. In particular, in [26] the authors also use the classic Shapley value to allocate costs among carriers and coalitions of carriers. In [23] various criteria are presented to allocate costs using classical game 4 theory in a vehicle routing problem. Our perspective in this paper is quite dierent. While we do not focus on cost allocation among carriers, we study how to improve prots for the whole carriers network within the framework of a xed collaboration agreement by stating our model as a prize-collecting arc routing problem with several carriers and depots. Since the CUARP belongs to the class of arc routing problems with prots, we next recall some relevant literature related to this class. Christodes et al. [12] present a directed version of the Rural Postman Problem (RPP) [27], which is later generalized as the Directed Protable RPP (DPRPP) in [7], where some arcs may not be served by paying a penalty for each of them. Aráoz et al. [6] propose the Privatized Rural Postman Problem (PRPP) whose objective is to nd a tour maximizing the prot gained, starting and ending at a xed depot. Dierent variants of this problem were proposed by several authors. We mention the Clustered Prize-Collecting Arc Routing Problem introduced by Aráoz et al. [4] and its windy version studied by Corberán et al. [13]. For a comprehensive survey on arc routing with prots we refer to Archetti et al. [8]. Dierently from the above studies, we focus on a multi-depot model to optimize collaboration among carriers. 3 Collaboration Uncapacitated Arc Routing Problem The CUARP can be stated as follows. We consider a set of carriers, each with one depot and one vehicle. We assume that the problem is uncapacitated and do not consider capacity constraints on vehicles. Customers are represented as arcs of a graph and are served when the vehicle traverses the corresponding arcs. Carriers reach a collaboration agreement, described in the following, under the guidance and surveillance of a third party central decision maker. The goal is to nd one route for each carrier, in the framework of the collaboration agreement, such that the prot is maximized. The collaboration scheme that we study is the following. Each customer is associated with a specic carrier. Each carrier partitions its customers in two sets: • customers the carrier must serve because of contractual obligations or other types of considerations, such as relevance or convenience; • customers the carrier is willing to share with other carriers, because of a low level of geographical synergies with other customers or a low protability. The customers of the rst type are called required and form the required set , whereas the customers of the second type are called shared and form the shared set . Required and shared customers are called demand customers. We will refer both to customers associated with (or assigned to) carriers and to carriers associated with (or assigned to) customers. We note that each customer is assigned to one carrier, whereas there are 5 usually several customers assigned to one carrier. While required customers must be served by their associated carrier, shared customers can be served by any carrier. We allow a shared customer not be served by any carrier of the coalition. This corresponds to the situation where the customer is not protable for any carrier and, in the later stage, a carrier that does not belong to the coalition will be searched. Each customer, if served, will pay an amount of money to its associated carrier. For each shared customer the associated carrier will share part of this revenue with the carrier that will end up actually serving the customer. Carriers determine the side payment for each shared customer for the case it will be served by a dierent carrier. Each customer can be served at most once and by only one carrier. Thus, the revenue is collected only the rst time the corresponding arc is traversed, even if the arc is traversed more than once. If a shared customer is not served, a penalty is charged to the associated carrier. Every time an arc is traversed a cost is charged, independently of whether or not it corresponds to a demand arc. We identify carriers with vehicles, depots, and routes, and assume that routes start and end at the same depot. In order to state the CUARP formally, we rst introduce some notation. Let G= (V, A) be a strongly connected directed graph with vertex set V={1, . . . , n} and arc set A . When needed, arcs will be denoted by their end-vertices a= (u, v) . A non-negative traversal cost ca is associated with each arc a∈A . The subset of demand arcs (customers) is denoted by D⊂A , and the subsets of required and shared customers by R and S , respectively. We have D=R∪S and R∩S=∅ . A non-negative value ra is associated with each demand arc a∈D , which represents the money oered by customer a in exchange of service. Furthermore, a non-negative value ga≤ra is associated with each shared arc a∈S , which represents the side payment from the associated carrier to the carrier that provides the service to a . A positive value φa is also associated with each shared arc a∈S , which is the penalty that the associated carrier must pay for not serving customer a . Let L={1, . . . , k} be the index set for the carriers, each of them with a depot located at a vertex of the graph, denoted by vl∈V , l∈L . We also use VL={vl|l∈ L} ⊂ V to denote the set of all depots and Il=L\ {l} , for l∈L . For each l∈L we denote by Dl the subset of demand customers associated with l , and by Rl=Dl∩R and Sl=Dl∩S its associated required and shared customers, respectively. Customers in Dl , Rl , and Sl will be referred to as l -demand , l -required and l -shared customers, respectively. For l∈L , Dl=RlSSl and RlTSl=∅ . We also have, D=Sl∈LDl , R=Sl∈LRl , and S=Sl∈LSl . 6 We use the following standard notation. For a nonempty proper subset F⊆V , γ(F) = {a= (u, v)∈A|u, v ∈F}, set of arcs with both vertices in F , δ+(F) = {a= (u, v)∈A|(u∈F, v /∈F)}, set of arcs that start in F and end out of it, δ−(F) = {a= (u, v)∈A|(u /∈F, v ∈F)}, set of arcs that start out of F and end in it. Finally, for each H⊆A we dene y(H) as P a∈H ya . In the CUARP, we impose that for any carrier l∈L , each l -required arc a∈Rl is served by carrier l . Instead, an l -shared arc a∈Sl can be served either by carrier l or by a dierent carrier h∈Il , or not served at all. A customer a∈D oers a non-negative amount of money ra in exchange of service. Carrier l collects the revenue ra for each l -required arc a∈Rl as well as for each served l -shared arc a∈Sl , even if it is served by a dierent carrier h∈Il . If carrier h serves an l -shared arc a∈Sl , it collects the non-negative side payment ga from carrier l . Therefore, the side payment ga is added to the prot of carrier h and subtracted from the prot of carrier l . If an l -shared arc a∈Sl is not served by any carrier, then the revenue ra is not collected by carrier l , and carrier l gives no side payment ga to any other carrier. However, in this case carrier l has to pay the penalty φa . All routes start and end at the depot of their associated carrier. While carriers with a non-empty required set must certainly perform a route, it is possible for a carrier with empty required set to perform no route. If performed, the route of such a carrier will only serve shared arcs. Carrier l pays a cost ca each time arc a∈A is traversed in its route. The total prot of carrier l∈L is the dierence between its total income and its total costs and side payments, including penalties. The aim of the CUARP is to maximize the total prot of the coalition of carriers. 3.1 Formulations To formulate the CUARP we dene the following two sets of decision variables, which identify the arcs that are served and traversed by each carrier l∈L . For each a∈A , let yl a=(1 if a is served by vehicle l , 0 otherwise. xl a= number of times vehicle l traverses a . Associated with a solution (xl a, yl a) we dene the following functions for each carrier 7 l∈L : Cl 1=X a∈A caxl a, total traveling cost for carrier l , Cl 2=X a∈Sl φa(1 −yl a), total penalty payed by carrier l , Cl=Cl 1+Cl 2, total cost for carrier l , Pl 1=X a∈Dl rayl a+X a∈Sl"(ra−ga)X i∈Il yi a#, prot collected by carrier l from l -demand customers, Pl 2=X i∈Il X a∈Si gayl a!, total side payments collected by carrier l from other carriers, Pl=Pl 1+Pl 2−Cl, total prot of carrier l . Furthermore, the set of constraints (C) models the collaboration agreement among carriers: (C)                            xl(δ+(u)) = xl(δ−(u)) l∈L , u∈V (1) xl(δ+(vl)) ≥1l∈L with Rl6=∅ (2) xl(δ+(vl)) ≥yl al∈L with Rl=∅ , a∈S (3) xl(δ+(F)) ≥yl al∈L , F⊂V\ {vl} , a∈γ(F) (4) yl a= 1, a ∈Rl , l∈L (5) X l∈L yl a≤1a∈S (6) yl a≤xl aa∈A , l∈L . (7) Flow-in ow-out constraints (1) guarantee the symmetry of the vertices, because the number of incoming arcs must be equal to the number of outgoing arcs. Constraints (2) and (3) guarantee that the carriers routes start from their depots. While (2) imposes a route to any carrier l∈L with non-empty required set, constraints (3) only impose a route to carriers with empty required sets who serve some shared arc. Constraints (4) guarantee that the route of each carrier is connected. Given a subset F⊂V\{vl} , if an arc a∈γ(F) is served, then some arc b∈δ+(F) must be traversed at least once. Hence, each carrier travels a connected route because if it serves some arc from a subset of arcs which does not contain the depot then it has to leave the subset. Note, however, that Constraints (4) do not prevent subtours containing no served arc. Since such subtours produce no prot, they will never appear in any optimal solution. Constraints (4), together with constraints (1)-(3), also guarantee that each carrier route ends at its depot. Constraints (5) force carrier l to serve all l -required arcs, whereas inequalities (6) ensure that l -shared arcs are served by at most one carrier. Finally, inequalities (7) impose that all arcs served by a given carrier are traversed by that carrier. 8 We introduce now the mathematical programming formulation for the CUARP, where we maximize the total prot of the coalition of carriers: zc= max X l∈L Pl (8) (C) (9) xl a∈Z+, a ∈A, l ∈L;yl a∈ {0,1}, a ∈D, l ∈L. (10) Remark 3.1 In the CUARP carriers exchange side payments corresponding to shared arcs served by carriers dierent from the ones they are assigned to. This means that if, for a given arc a∈Sl , some carrier i∈Il takes ga for serving l -shared arc a , then carrier l takes ra−ga . Thus, the prot collected by all carriers is: X l∈LPl 1+Pl 2−Cl=X l∈L X a∈Dl rayl a+X a∈Sl"(ra−ga)X i∈Il yi a#+X i∈IlX a∈Si gayl a!−X l∈L Cl= X l∈L X a∈Dl rayl a+X a∈Sl raX i∈Il yi a−Cl! where the last equality follows as the following two sums cancel out since: X l∈LX a∈Sl gaX i∈Il yi a=X l∈LX i∈IlX a∈Si gayl a. Hence, the objective function (8) can be reformulated as: max X l∈L X a∈Dl rayl a+X a∈Sl raX i∈Il yi a−Cl!. (11) Therefore, the optimal solution to a CUARP instance is independent of the side payments ga , a∈S , since (11) does not depend on the side payments ga , a∈S , and the domain (1) - (7) is independent of the side payments as well. Thus, we have that an optimal solution to a CUARP instance with side payments ga , a∈S is also optimal to a CUARP instance with side payments g0 a , a∈S , if all other data remain unchanged. In the CUARP we can force carriers not to collaborate by adding a constraint that prevents carrier l from serving arcs outside its demand set: yi a= 0, a ∈Sl, i ∈Il. 9 as thresholds fullls the individual rationality condition. Hence, the solution of the 2 carrier t -CUARP belongs to the core of the game when we set the n -CUARP prots as thresholds. In this case, the core is always non empty if the instance is feasible. In contrast, we cannot assure that the solutions of the t -CUARP with more than 2 carriers or with general thresholds belong to the core of the game. Even if the thresholds are set to the value of individual prot without collaboration, 2 or more carriers may collude to achieve a greater prot than that of the grand coalition. We might ensure that the t -CUARP prot allocation belongs to the core of the game, by adding a new set of constraints to the t -CUARP, imposing for each subset of carriers a minimum prot of at least its CUARP prot. However, adding this new set of constraints may cause the instance to become infeasible and the core of the cooperative game be empty. In a set of experiments this is what happened. Either the core was empty or the solution was identical to the solution without collaboration. Hence, we solved the t -CUARP adding only individual thresholds which are those that directly matter to the carriers. 5 The branch-and-cut algorithm Inequalities (4) impose the connectivity of the route associated with each carrier with its depot. As the number of such constraints is exponential in the number of vertices in the input graph, |V| , we use a separation procedure that allows us to incorporate them in the formulation only when needed. Next, we describe the separation algorithm that we used for the exact solution of the CUARP and of the t -CUARP. The separation procedure uses as input vectors ˆx= (ˆxl)l∈L∈R|A|×|L| and ˆy= (ˆyl)l∈L∈R|A|×|L| satisfying constraints (1)(3) and (5)-(7). The output of the algorithm will indicate whether or not there exists some inequality (4) violated by ˆx and ˆy . In this case the algorithm will return one such inequality, i.e. the index of a carrier l∈L , a set F⊂V\{vl} and an arc a∈γ(F) such that the corresponding constraint (4) is violated by ˆx and ˆy . For each carrier l∈L , let Gl(ˆxl)=(Vˆxl, Aˆxl) denote the support graph of ˆxl , with Aˆxl={a∈A|ˆxl a>0} , and Vˆxl=V(Aˆxl) the subset of vertices incident with some arc of Aˆxl . To separate inequalities (4), associated with a given carrier l∈L , we consider the support graph Gl(ˆxl) . If G(ˆxl) is not connected, then each connected component with vertex set C⊆Vˆxl\ {vl} such that ˆy(γ(C)) >0 denes a violated constraint (4) for carrier l , since ˆxl(δ+(C)) = 0 and ˆyl a>0 , for some a∈γ(C) . If G(ˆxl) is connected, we compute the tree of min-cuts Tl(ˆx) relative to the capacities vector ˆxl (see, for instance, [22, 24]). Then, we use an adaptation of the algorithm of Belenguer and Benavent [10]. For each min-cut δ+(F) , vl/∈F , represented in Tl(ˆx) , we identify the arc ˆa∈γ(F) of maximum value, i.e. ˆa∈arg max{ˆyl a|a∈γ(F)} . Now, if ˆxl(δ+(F)) <ˆyl ˆa , the connectivity constraint (4) associated with l , F and ˆa is violated by ˆxl and ˆyl . The above separation is exact and similar to the procedure used by other authors to separate connectivity constraints similar to (4) for other arc routing problems [11, 3, 4, 13]. 16 The computational complexity of the above algorithm is dominated by that of the algorithm to obtain the min-cut tree associated with each carrier, which is O(|V|4) as pointed out in [22] and in [24]. 6 Data generation and computational results We present in this section the numerical results obtained on a series of computational experiments. Programs were coded in Java using CPLEX 12.5 library (64 bit) for the solution of the mixed integer problems. Default parameters were used. All tests were run on a HP Z400 Workstation, 64 bit, 3.33 GHz, 12.0 RAM. Since there are no available CUARP benchmark instances, we generated instances from the 118 PRPP benchmark instances used in [5]. These PRPP instances were derived from well-known RPP instances, which are divided in ve groups. The rst group contains two data sets, A and B, obtained from the Albaida Spain Graph (see Corberán and Sanchis [14]). The second group contains the 24 instances (labeled P) of Christodes et al. [12]. The last three groups contain instances from Hertz et al. [25]: 36 instances with vertices of degree 4 and RPP disconnected required edge sets (labeled D), 36 grid instances (labeled G), and 20 randomly generated instances (labeled R). Below we explain how the remaining data of the instances were dened. First, the original undirected graph is transformed in a directed graph in the following way. • All arcs are dened from edges of the original graph (see [5]).  Each original edge is transformed in two arcs with probability 0.1 , and in one single arc with probability 0.9. In the latter case, the direction of the arc is randomly chosen with equal probability.  Arcs inherit their costs from the original edges. When two arcs are generated from the same edge, both arcs have the same cost. • If needed, when all original edges have been considered, additional arcs are dened to guarantee that the resulting graph is strongly connected.  For each pair of vertices, u, v ∈V , for which the directed graph dened earlier contains no path from u to v , we dene a non-demand arc (u, v) and assign to it the cost of the shortest path in the undirected graph connecting u and v . • Demand arcs are selected starting from the required edges of [5], as follows:  If the original edge is a demand edge that has been transformed in two arcs, both transformed arcs become demand arcs with probability 0.15. Otherwise, one transformed arc is randomly selected as demand arc while the other one becomes non-demand. 17  If the original edge is a demand edge that has been transformed in one single arc, the transformed arc becomes a demand arc.  If the original edge is non-demand the transformed arc(s) is(are) non-demand. • The prot of each demand arc a∈D is dened as ra= 2be , where be is the prot of the undirected edge in the corresponding PRPP instance [5]. If e is a required edge of the RPP instance, be is a number randomly generated from an integer uniform distribution in the range [ ce , 3ce ]. Otherwise, be= 0 . • The side payment of each demand arc a∈D , ga , is set to a fraction β of its prot, i.e. , ga=βra . For each instance, we use two values for β , namely 0.5 and 1. To dene the demand sets, we denote by Puv the shortest path from u to v in the directed graph and by c(Puv) its cost. Then, we dene the following auxiliary set for each carrier l∈L : ¯ Dl={a∈D|wa≤0.75 ∧c(Pvlu)≤c(Pviu), for all i∈Il}, where u denotes the end-vertex of arc a closest to vl and wa a random number in [0,1] associated with arc a . Since the sets ¯ Dl are not necessarily disjoint for dierent carriers the demand sets are nally dened as D1=¯ D1, Dl=¯ Dl\ l−1 [ k=1 ¯ Dk!, l ∈ {2,...,|L|}, Broadly speaking, we assign demand arcs to the carrier with smallest distance from/to its depot with a probability of 75%. Moreover, if through this procedure a required arc belongs to more than one ¯ Dl set, then it is assigned to the required set of the smallest index carrier, among the ones whose ¯ Dl sets contain the arc. To divide each carrier demand set into shared and required sets, rstly, we list all demand arcs for each carrier according to their distance from the depot. Then, the less distant arcs form the required set while the remaining ones the shared set. Shared and required sets are dened to ensure that at least a percentage p of the demand arcs are shared. We x p equal to 50%. We denote with M the vertex most distant from vertex 1 , and with m the vertex whose distance from 1 is the median of all distances from 1 to v∈V . We set the same penalty value for all the shared arcs associated with the same carrier. For each carrier l∈L , this penalty is set to the average prot loss per unserved l -shared arc. That is, for l∈L , a∈Sl , φa=     max (0,$P a∈Sl ra−ca |Sl|%) if Sl is not empty, 0 otherwise. 18 The minimum threshold values tl , l∈L , are given by the prots of the n -CUARP. The instances are available at the following link: http://or-brescia.unibs.it/ instances . Table 3 summarizes information on the instances, which have been grouped according to their characteristics and to their sizes. These instances were generated with 2 depots located at v1= 1 and v2=M . Columns under #inst. and #vertices give, respectively, the number of instances in the group and the number of vertices of the instances in the group. Columns under |R1| and |R2| give the number of 1-required and 2-required arcs, respectively. Similarly, columns under |S1| and |S2| give the number of 1-shared and 2-shared arcs. Table 3: Instance summary #inst. #vertices |R1| |R2| |S1| |S2| AA 1 102 48 34 48 35 AB 1 90 50 23 50 23 P 24 7-50 0-48 2-46 1-48 3-47 D16 9 16 5-8 7-10 5-8 8-11 D36 9 36 15-21 16-21 15-21 17-21 D64 9 64 32-41 20-32 33-42 21-33 D100 9 100 48-67 32-50 49-67 33-50 G16 9 16 0-3 0-3 1-4 1-3 G36 9 36 1-9 3-11 1-9 3-12 G64 9 64 2-13 6-21 3-14 6-22 G100 9 100 8-29 11-32 8-29 12-33 R20 5 20 10-23 5-15 10-24 6-16 R30 5 30 19-37 14-25 19-37 14-26 R40 5 40 25-56 16-47 26-57 17-48 R50 5 50 33-57 26-56 33-58 26-56 Table 4 summarizes the information on the values of the parameters that have been used and the number of tested instances in each case. The complete set of instances consists of 971 instances. Table 4: Number of instances for each combination of parameters Location of depots CUARP n -CUARP CUARP with t -CUARP dierent proportions β of shared/required arcs 0.5 1 v1= 1 , v2=M 118 118 27 (G16) 118 118 v1= 1 , v2=m 118 118 v1= 1 , v2=m , v3=M 118 118 A rst set of experiments was run on the set of instances with two carriers, i.e. L={1,2} , with depots v1 and v2 located at vertices 1 and M , respectively. The results for the CUARP are summarized in Table 5. Columns under CUARP and n - CUARP give the average net prot of carriers for the CUARP and the n -CUARP, respectively. Columns under #S1 and #S2 give the average number of shared arcs served by each carrier, while the column under %serv. gives the average percentage of shared arcs served in total ( 100#S1+#S2 |S1|+|S1| ). Columns under #S12 and #S21 give, respectively, the average number of 1-shared arcs which are served by carrier 2, and vice versa. The column under %exc. gives the average percentage of arcs exchanged between carriers ( i.e. the average percentage of shared arcs that are served by a carrier dierent from the one they are assigned to, 100#S12+#S21 #S1+#S2 ). Column under increase gives the average percentage prot increase due to collaboration ( 100|zc−znc zc| ). Finally, the last column under time gives the average computing times in seconds. 19 The results of Table 5 illustrate the positive eect of the carriers collaboration. The average percentages %serv. and %exc. range in [67.0, 100.0] and in [41.0, 76.7], respectively. This means that there is a reasonable percentage of shared arcs served and exchanged between carriers. The average percentage prot increase of CUARP with respect to n -CUARP ranges in [0.7, 41.1]. In general, the average CPU time required to solve small instances, such as those of P, D16, D36, G16, R20, R30, R40 groups, is less than 1 second. Solving the remaining instances required a little bit more computational eort, which pushed the CPU time up to a max of 158.0 seconds. The average CPU time is equal to 8.3 seconds. In Tables 6 and 7 we summarize the results for the t -CUARP, with β= 0.5 and β= 1 , respectively. We tested separately the instances with these two dierent values of β , which aect the side payments and, thus, the prot threshold constraints. In these tables we have the additional columns increase1 and increase2 that show the prot increase for carrier 1 and 2 . Comparing the results in Tables 6 and 7 with those in Table 5 we note that the average prot increase due to collaboration is smaller in t -CUARP than in CUARP. Instead, the average percentage %serv. may even increase as, for example, for the instances in the D100 group in both cases with β= 0.5 or β= 1 . The CPU times for the t -CUARP are comparable to those of the CUARP. We note that in some groups of instances the t -CUARP value is smaller when β= 1 than when β= 0.5 . For instance, in P %serv. increases from 90.5 (for β= 0.5 ) to 91.1 (for β= 1 ). Still the value of CUARP is greater for β= 0.5 (392.8) than for β= 1 (379.2). This t -CUARP behavior was explained in Remark 3.1 and illustrated in Example 3.2. Table 8 shows the characteristics of the instances that are obtained when displacing the depot of the second carrier ( v2 ) from vertex M to vertex m . Due to how sets Sl and Rl are dened when generating the instances, by displacing v2 the average number of shared arcs increases and the average number of required arcs decreases. Table 9 summarizes the results with this new set of instances. Obviously, results in Table 9 cannot be compared with those in the previous tables, since we deal with completely dierent instances. The CPU times required to solve these new instances are comparable to those required for solving the instances in Table 3. Below we describe the results obtained in the experiments with CUARP and 3 depots, located in vertices 1 , m and M , respectively. We have been able to solve all 118 instances. In Tables 10 and 11 we introduced additional columns to deal with 3 depots. In particular, columns under |R3| , |S3| of Table 10 give the number of 3-required and 3-shared arcs, respectively. In Table 11 columns under #S and #Sexc give, respectively, the average number of shared arcs served and the average number of shared arcs exchanged. In Table 11 we note that the range of the average percentage of served shared arcs ( %serv. ) and the average percentage of exchanged shared arcs and ( %exc. ) is [35.0, 58.5] and [26.4, 46.5], respectively. Moreover, the average percentage prot increase ranges in [0.0, 16.8]. However, comparing these results with those for the CUARP with 2 depots given in Table 5, we note that increasing the number of carriers from 2 to 3 does not necessarily increase the prot. As an example, for the G16 instances, when adding a new depot, increase decreases from 21.5% to 16.8%. The computing times to solve instances with 3 carriers are similar to those required for the instances with 2 carriers. Finally, in order to test the behaviour of the model with dierent proportions of shared/required 20 sets, some additional computational experiments were run. For these experiments we used the instances in G16 with depot located in 1 and in M . Firstly, we restricted the shared sets ensuring that at least 25% of the demand arcs belong to them. Then we enlarge them, ensuring that at least 75% of the demand arcs to be shared. Finally, we set them all as shared arcs. We performed 27 additional computational experiments. In Table 12 we show the prots for each case and each instance. Under columns n - CUARP, CUARP- 25 , CUARP, CUARP- 75 , CUARP- 100 we give the optimal values for n -CUARP, CUARP with 25% of arcs shared, CUARP, CUARP with 75% and 100% of arcs shared, respectively. We note that prot does not decrease when we increase the number of arcs in the shared sets. This is consistent with Remark 4.2. We can conclude that the attractiveness of collaboration increases when we increase the number of shared arcs. Table 5: Results for CUARP n -CUARP CUARP #S1 #S2 #S12 #S21 %serv. %exc. increase time AA 14442.0 24509.0 41.0 41.0 28.0 34.0 98.8 75.6 41.1 46.2 AB 1411.0 17911.0 26.0 47.0 16.0 40.0 100.0 76.7 92.1 21.2 P 379.2 392.9 13.4 12.9 8.3 7.6 90.5 54.7 4.0 0.4 D16 1211.8 1220.9 5.9 7.0 3.8 3.4 79.5 56.1 0.8 0.1 D36 2443.9 2460.6 17.1 15.9 9.1 8.3 90.8 52.7 0.7 0.4 D64 3582.6 3616.6 33.3 27.4 15.6 17.2 94.3 53.8 1.1 2.8 D100 4810.6 4873.2 42.7 54.0 22.4 35.8 97.5 60.2 1.5 14.6 G16 10.3 13.0 1.2 2.7 0.6 1.1 94.4 42.5 21.5 0.1 G36 42.8 51.0 4.8 8.0 2.3 3.0 100.0 41.0 16.0 1.4 G64 87.6 103.7 13.0 11.3 8.2 5.3 100.0 54.1 15.9 9.7 G100 139.9 170.8 21.9 18.0 12.4 9.9 100.0 54.9 18.7 70.3 R20 52221.8 53101.8 12.2 7.4 4.2 4.8 72.5 46.0 2.3 0.1 R30 67804.2 69230.2 15.6 15.2 6.0 9.8 62.8 52.2 2.0 0.3 R40 86734.0 90811.8 21.8 31.8 9.2 20.2 73.1 56.6 19.8 0.6 R50 91811.4 96350.4 28.6 33.8 15.4 21.4 67.0 58.1 9.8 1.1 max 100.0 100.0 92.1 158.0 average 89.5 53.1 9.2 8.3 Table 6: Results for t -CUARP, β= 0.5 n -CUARP CUARP #S1 #S2 #S12 #S21 %serv. %exc. increase1increase2increase time AA 14442.0 18722.0 42.0 39.0 23.0 28.0 97.6 63.0 22.9 30.3 10.5 58.9 AB 1411.0 11946.0 45.0 26.0 19.0 24.0 97.3 60.6 88.2 107.0 39.4 47.9 P 379.2 392.8 12.3 14.0 7.6 8.0 90.5 53.2 4.0 4.1 3.9 0.5 D16 1211.8 1220.4 5.0 7.9 3.2 3.8 79.5 53.1 0.9 0.7 0.7 0.2 D36 2443.9 2460.6 15.2 17.7 9.4 10.4 90.5 59.6 0.9 0.7 0.7 0.6 D64 3582.6 3616.6 31.0 29.9 16.6 20.6 94.5 61.0 1.0 1.2 1.1 9.3 D100 4810.6 4873.2 48.3 48.7 29.1 37.0 97.9 68.2 2.8 0.8 1.5 21.3 G16 10.3 12.2 1.4 2.4 0.6 0.9 94.4 32.0 18.9 5.7 14.3 0.1 G36 42.8 48.9 3.2 9.4 1.0 3.1 98.4 28.6 9.9 17.4 10.8 1.6 G64 87.6 99.7 12.2 12.1 6.4 4.3 100.0 46.6 12.8 20.6 12.8 11.2 G100 139.9 169.0 21.7 18.2 12.6 10.2 100.0 56.2 16.8 16.7 17.2 76.5 R20 52221.8 53061.8 11.6 8.0 4.6 5.8 72.5 50.7 2.1 3.4 2.1 0.2 R30 67804.2 69230.2 18.0 12.8 6.8 8.2 62.8 46.1 1.2 2.4 2.0 0.4 R40 86734.0 90539.0 24.0 29.6 14.6 23.4 73.1 71.8 4.3 7.7 19.5 0.9 R50 91811.4 96350.4 31.0 31.4 18.2 21.8 67.0 62.8 7.0 10.9 9.8 1.9 max 100.0 100.0 88.2 107.0 85.7 158.0 average 89.3 52.6 7.3 7.9 7.1 10.4 21 Table 7: Results for t -CUARP, β= 1 n -CUARP CUARP #S1 #S2 #S12 #S21 %serv. %exc. increase1increase2increase time AA 14442.0 24509.0 41.0 41.0 28.0 34.0 98.8 75.6 41.1 37.8 41.1 18.0 AB 1411.0 17911.0 26.0 47.0 16.0 40.0 100.0 76.7 92.1 106.7 77.3 13.3 P 379.2 392.5 12.2 14.1 6.9 7.5 91.1 44.0 5.3 2.3 3.5 0.7 D16 1211.8 1219.6 5.7 7.2 3.1 3.0 79.5 46.1 0.6 1.0 0.6 0.3 D36 2443.9 2460.3 14.0 19.0 8.3 10.6 90.8 56.7 0.6 0.9 0.7 0.9 D64 3582.6 3616.6 30.7 30.1 15.9 20.1 94.3 59.3 1.1 0.9 1.1 11.0 D100 4810.6 4873.2 52.4 44.4 29.0 32.8 97.7 63.8 1.6 1.8 1.5 23.3 G16 10.3 11.8 1.8 2.1 0.7 0.7 94.4 30.2 24.2 7.9 12.0 0.2 G36 42.8 44.9 5.4 7.2 1.7 1.6 98.4 21.4 11.1 1.2 4.3 2.3 G64 87.6 96.3 10.6 13.8 4.7 4.2 100.0 36.5 9.1 9.6 9.1 15.4 G100 139.9 155.0 19.7 20.2 9.9 9.6 100.0 48.0 10.9 9.4 11.0 100.2 R20 52221.8 53061.8 12.2 7.4 5.0 5.6 72.5 52.9 1.8 4.4 2.2 0.2 R30 67804.2 69190.2 15.4 15.4 6.8 10.8 62.8 56.1 2.5 1.8 1.9 0.8 R40 86734.0 90539.0 29.0 24.6 15.2 19.0 73.1 62.8 21.0 2.7 19.5 1.1 R50 91811.4 96350.4 32.2 30.2 19.0 21.4 67.0 64.3 11.2 8.9 9.8 2.1 max 100.0 80.0 100.0 106.7 85.7 291.9 average 89.5 47.9 8.3 4.9 6.2 12.3 Table 8: Instance summary after moving depots #inst. #vertices |R1| |R2| |S1| |S2| AA 1 102 31 49 31 49 AB 1 90 28 45 28 45 P 24 7-50 1-57 2-49 2-57 2-49 D16 9 16 5-9 6-11 6-9 7-11 D36 9 36 16-22 12-22 16-22 12-22 D64 9 64 26-42 22-39 26-42 22-40 D100 9 100 42-50 50-55 42-40 51-56 G16 9 16 0-2 0-4 1-3 0-4 G36 9 36 2-7 3-12 2-8 3-12 G64 9 64 4-20 6-17 5-21 6-17 G100 9 100 8-27 9-31 9-27 10-31 R20 5 20 8-20 8-20 8-20 9-20 R30 5 30 18-30 14-30 19-30 15-31 R40 5 40 18-67 22-48 19-68 23-48 R50 5 50 31-48 35-66 31-49 35-66 Table 9: Results for CUARP after moving depots n -CUARP CUARP #S1 #S2 #S12 #S21 %serv. %exc. increase time AA 23570.0 23596.0 36.0 43.0 24.0 18.0 98.8 53.2 0.1 13.9 AB 17657.0 17693.0 39.0 34.0 26.0 15.0 100.0 56.2 0.2 10.0 P 380.3 390.9 11.2 14.5 6.6 7.3 91.8 54.7 4.3 0.3 D16 1221.2 1225.6 5.9 6.0 4.3 2.6 73.7 57.2 0.0 0.1 D36 1929.8 2072.8 19.7 12.2 10.6 7.0 87.9 54.5 0.1 0.6 D64 3622.3 3654.8 28.7 31.7 15.2 18.4 94.0 55.9 0.0 2.8 D100 5058.0 5106.2 39.6 55.4 24.8 30.2 94.9 58.0 0.0 14.5 G16 9.8 13.1 1.0 2.9 0.4 1.3 92.2 39.0 0.2 0.1 G36 38.7 45.9 4.7 7.8 3.0 3.9 100.0 54.9 0.2 1.8 G64 86.6 102.2 13.4 10.8 6.7 5.4 100.0 50.5 0.2 9.6 G100 147.0 167.6 20.1 20.2 10.8 10.4 100.0 52.3 0.2 103.8 R20 52781.8 53861.2 10.6 7.4 5.2 4.4 66.6 53.7 0.0 0.1 R30 63098.6 64668.2 13.8 20.2 8.4 11.4 68.5 56.2 0.0 0.2 R40 81383.0 83126.0 21.0 29.8 11.0 17.2 67.4 54.6 0.0 0.8 R50 82934.0 88777.4 30.8 36.8 16.6 15.6 71.4 48.2 0.2 1.5 max 100.0 88.9 0.9 185.1 average 88.6 53.3 0.1 10.5 Table 10: Instance summary with 3 depots #inst. #vertices |R1| |R2| |R3| |S1| |S2| |S3| AA 1 102 40 22 17 41 23 17 AB 1 90 46 11 17 46 12 17 P 24 7-50 1-43 1-42 0-22 2-44 1-42 1-23 D16 9 16 2-5 6-10 1-5 2-6 6-11 2-6 D36 9 36 10-18 10-16 7-11 11-18 10-16 7-12 D64 9 64 27-40 8-22 12-18 27-41 9-23 13-18 D100 9 100 36-61 13-40 19-29 36-62 13-40 20-29 G16 9 16 0-3 0-2 0-2 1-3 1-2 0-2 G36 9 36 1-8 2-10 1-6 1-8 2-10 1-6 G64 9 64 2-13 4-14 2-11 2-13 5-15 2-11 G100 9 100 6-23 7-24 5-14 6-24 8-24 5-14 R20 5 20 6-23 3-24 3-14 6-24 4-24 4-14 R30 5 30 6-40 2-24 3-15 6-40 3-24 415 R40 5 40 6-48 2-31 3-27 6-48 3-31 4-415 R50 5 50 6-53 2-44 3-28 6-54 3-45 4-415 22 Table 11: Results for CUARP with 3 depots n -CUARP CUARP #S#Sexc %serv. %exc. increase time AA 25481.0 25513.0 42.0 16.0 51.9 38.1 0.1 41.8 AB 20898.0 20930.0 44.0 19.0 58.7 43.2 0.2 36.7 P 433.8 445.6 14.3 5.4 46.3 39.2 3.9 1.0 D16 1379.2 1388.1 7.7 3.1 46.5 41.2 0.7 0.1 D36 2661.4 2681.4 17.3 7.2 47.4 41.8 1.0 1.0 D64 4068.2 4015.3 36.8 13.6 57.2 36.9 0.6 9.3 D100 5387.2 5438.0 54.6 18.3 54.7 33.7 1.1 55.5 G16 15.6 18.0 2.9 1.3 66.7 42.8 16.8 0.1 G36 52.4 61.3 6.6 1.9 54.5 26.4 15.5 3.7 G64 111.8 121.7 12.2 4.4 49.4 35.2 6.9 24.6 G100 171.6 191.7 21.4 6.7 50.1 28.7 11.3 248.1 R20 60528.6 60537.8 15.4 5.6 58.5 33.0 0.0 0.2 R30 88964.0 88986.0 16.4 5.2 35.0 30.8 0.0 0.5 R40 115561.6 115582.8 34.6 13.8 45.9 35.9 0.0 1.4 R50 128557.6 128587.0 40.4 18.4 43.0 46.5 0.0 3.2 max 100.0 100.0 80.0 546.3 average 50.6 36.7 4.9 27.2 Table 12: CUARP G16 results with increasing size of shared sets n -CUARP CUARP-25 CUARP CUARP-75 CUARP-100 G0 1 1 1 1 2 G1 3 6 6 6 15 G2 4 6 6 6 8 G3 14 17 17 17 27 G4 10 13 13 13 25 G5 11 14 14 14 30 G6 23 28 28 34 47 G7 13 15 17 17 28 G8 14 14 15 19 31 23 7 Conclusions In this paper, we have introduced two variants of the Collaboration Uncapacitated Arc Routing Problem. This is a protable arc routing problem with multiple depots, where carriers may collaborate to improve the prot gained. An integer linear programming formulation with binary and integer variables has been presented, as well as a branch- and-cut algorithm. In the CUARP the goal is the maximization of the total prot of the coalition. The prot gained by the coalition of carriers never decreases with respect to the case without collaboration. Individual carriers, however, may lose prot in the collaboration scheme modeled by the CUARP. For this reason, we considered a variant where carriers may set thresholds on the prot gained in the collaborative scheme. This variant allocates the prot gained by the coalition in a more balanced way. Interestingly, we analyzed the cooperative game associated with the CUARP and noted that in the case of two carriers the t -CUARP prot allocation is stable because it belongs to the core of the game. Moreover, collaboration may produce an arbitrary large increase of the prot. A set of benchmark instances were generated and the results of extensive computational experiments presented and analyzed. For future research, attention should be focused on the extension of the models proposed to include real-life features of the problem such as time and capacity constraints. Another direction concerns the design of heuristic algorithms for the solution of large instances. Acknowledgements The research of the rst author has been partially supported by the Spanish Ministry of Economy and Competitivity through grant MTM2012-36163-C06-05 and by ERDF funds. This support is gratefully acknowledged. The authors would like to express their appreciation for the valuable and insightful comments made by an anonymous reviewer. References [1] R. Agarwal and Ö. Ergun. Network design and allocation mechanisms for carrier alliances in liner shipping. Operations Research , 58(6):17261742, 2010. [2] R. Agarwal, Ö. Ergun, L. Houghtalen, and O. Ö. Özener. Collaboration in cargo transportation. In Optimization and Logistics Challenges in the Enterprise , pages 373409. Springer, 2009. [3] D. Ahr. Contributions to Multiple Postmen Problems. PhD dissertation, Departament of Computer Science, Heidelberg University, Heidelberg, Germany. 2004. 24 [4] J. Aráoz, E. Fernández, and C. Franquesa. The clustered prize-collecting arc routing problem. Transportation Science , 43(3):287300, 2009. [5] J. Aráoz, E. Fernández, and O. Meza. Solving the prize-collecting rural postman problem. European Journal of Operational Research , 196(3):886896, 2009. [6] J. Aráoz, E. Fernández, and C. Zoltan. Privatized rural postman problems. Computers & Operations Research , 33(12):34323449, 2006. [7] C. Archetti, G. Guastaroba, and M. Speranza. An ilp-rened tabu search for the directed protable rural postman problem. Discrete Applied Mathematics , 163:316, 2014. [8] C. Archetti and M. G. Speranza. Arc routing problems with prots. in Arc Routing: Problems, Methods, and Applications. Á. Corberán and G. Laporte (eds.) MOS-SIAM series on Optimization, 281297, 2015. [9] J.-F. Audy, S. D'Amours, and L.-M. Rousseau. Cost allocation in the establishment of a collaborative transportation agreement: an application in the furniture industry. Journal of the Operational Research Society , 62(6):960970, 2011. [10] J. M. Belenguer and E. Benavent. The capacitated arc routing problem: Valid inequalities and facets. Computational Optimization and Applications , 10(2):165 187, 1998. [11] E. Benavent, A. Corberán and J.M. Sanchis. Linear programming based methods for solving arc routing problems. In Arc Routing: Theory, Solutions and Applications. M. Dror (ed.) Kluwer Academic Publishers, 231275, 2000. [12] N. Christodes, V. Campos, A. Corberán, and E. Mota. An algorithm for the rural postman problem on a directed graph. Mathematical Programming Study , 26: 155166. Springer, 1986. [13] Á. Corberán, E. Fernández, C. Franquesa, and J. M. Sanchis. The windy clustered prize-collecting arc-routing problem. Transportation Science , 45(3):317334, 2011. [14] A. Corberán and J. Sanchis. A polyhedral approach to the rural postman problem. European Journal of Operational Research , 79(1):95114, 1994. [15] T. S. Driessen. A survey of consistency properties in cooperative game theory. SIAM review , 33(1):4359, 1991. [16] H. A. Eiselt, M. Gendreau, and G. Laporte. Arc routing problems, part i: The chinese postman problem. Operations Research , 43(2):231242, 1995. [17] H. A. Eiselt, M. Gendreau, and G. Laporte. Arc routing problems, part ii: The rural postman problem. Operations Research , 43(3):399414, 1995. [18] Ö. Ergun, G. Kuyzu, and M. Savelsbergh. Reducing truckload transportation costs through collaboration. Transportation Science , 41(2):206221, 2007. 25