برنامه ریزی تصادفی مدل تعیین برنده برای توقیف کامیون حامل تأمین تجهیزات تحت عدم قطعیت حمل و نقل

We propose a two-stage stochastic integer programming model for the winner determination problem (WDP) in combinatorial auctions to hedge the shipper’s risk under shipment uncertainty. The shipper allows bids on combinations of lanes and solves the WDP to determine which carriers are to be awarded lanes. In addition, many other important comprehensive business side constraints are included in the model. We demonstrate the value of the stochastic solution over one obtained by a deterministic model based on using average shipment volumes. Computational results are given that indicate that moderately sized realistic instances can be solved by commercial branch and bound solvers in reasonable time.

Procurement of truckload (TL) transportation services is an important outsourcing activity for a shipper when the in-house logistics capacity is insufficient to transport the freight in dedicated movements from origins to destinations. One important means for allocating the shipments to carriers in the TL setting is for the shipper to use an auction. The basic item for sale is a lane which is defined as a contract between the shipper and a carrier that requires a carrier to move a dedicated shipment of a particular (estimated) volume from an origin to a destination. Typically, auctions in practice involve the sale of single lanes only. This often poses risks for bidders since there might be several lanes that that might be of interest and every lane in this set must be won separately. Obtaining an incomplete set of items may render the set much less valuable or even worthless. This phenomenon in simultaneous single item auctions is called the exposure problem see Bykowsky et al. (1995). Consequently, bidders are often less aggressive in bidding due to the fear of obtaining an incomplete set of lanes and as a result economic efficiency of outcomes may suffer. As an alternative, combinatorial auctions have been widely suggested for TL transportation procurement to lessen the exposure of bidders (carriers) which consequently could lead to more efficient allocations. A combinatorial auction is a simultaneous multiple item auction format that allows bidders to place a single bid on a set of distinct items to express synergies that exist for certain items see Parkes (1999). The synergies in lanes arise from combinations of lanes that enable carriers to reduce empty repositioning costs. For example, if a lane A requires the movement of freight from city i to j and there was no freight movement required from j to i, then a truck may have to return to city i without any load thereby incurring empty repositioning costs. Depending on the carrier’s cost of repositioning, it may not be worthwhile for a carrier to accept lane A. A better situation for a carrier would involve obtaining another lane B in addition to lane A that would require transporting a shipment from j to i. The combination of lanes A and B may be more profitable. So carrier may wish to service a package consisting of A and B or nothing at all. In a combinatorial auction, a carrier could submit single bids for several distinct lanes and if a bid were successful then the carrier would obtain the right to serve all lanes within the set (package) submitted, or otherwise there would be no obligation to ship any incomplete set. This would minimize the risks for carriers in obtaining only a subset of lanes that are not worth much, or that would incur a loss in servicing the incomplete set of won lanes due to different repositioning costs. Caplice and Sheffi (2003) indicate the value of combinatorial auctions in transportation procurement, and discuss some lessons from practice. Ledyard et al. (2002) present their experience of using combinatorial auctions for Sears Logistics Services and report Sears has been savings millions of dollars annually on outsourced transportation costs by using their multi-round combinatorial auctions mechanism. Elmaghraby and Keskinocak (2003) describe the experience of Home Depot in using a single round combinatorial auction mechanism for procuring TL transportation service to ship freight among its thousands of stores. Lee et al. (2007) and Song and Regan (2002) describe models that aid carriers in determining a set of valuable lanes to bid for in a combinatorial auction. However, there are still challenges in the use and design of combinatorial auctions see Abrache et al. (2007) for a comprehensive discussion of the issues. In particular, the auctioneer has to solve an NP-hard integer program to determine the bidders (carriers) that are to receive lanes. This problem is also known as the winner determination problem (WDP) see Rothkopf et al. (1998). The winner determination problem in its most basic form is equivalent to the weighted set packing problem see Rothkopf et al., 1998. In this setting a bidder submits a subset of items from a given ground set and places a bid amount associated with the subset. The auctioneer then selects which subsets to take to maximize (minimize) revenue (cost) subject to not allocating more than one of each item. In the context of TL procurement, a subset is a set of lanes that a carrier (bidder) submits with an associated offer amount that represents the payment that the carrier wishes to obtain for servicing the set of lanes for the shipper. There has been much recent activity in developing and analyzing both exact and approximate methods for the weighted set packing problem as well as generalizations of the basic WDP problem. See for instance, Rothkopf et al., 1998, Sandholm, 2002, Kwon, 2005 and Andersson et al., 2000 where the focus is on the WDP with a single unit of each item. Leyton-Brown et al., 2000 and Gonen and Lehmann, 2000 extend the WDP for multi-unit combinatorial auctions and Sandholm and Suri (2001) study the impact of side constraints on the WDP. See Lehmann et al. (2006) for a recent discussion of the WDP. Caplice and Sheffi (2003) provide several optimization models for assigning carriers to lanes (winner determination) without and with package bids, and discuss how to enrich the basic assignment model by including the business side constraints. Song and Regan (2002) present alternative formulations for bid structuring and evaluation. In addition, there has been important work in designing bidding languages to enable complex bidding expression see Abrache et al., 2003 and Boutilier and Hoos, 2001. One important factor not included in winner determination models for TL procurement is shipment volume uncertainty. Most lanes specify volume as an estimated quantity and lanes are awarded before the actual volume requirements are known. Thus, assignments of lanes to carriers may not be optimal after volume uncertainty has resolved. For example, a carrier that wins a set of lanes may be asked to ship volumes on the lanes that are far less than expected and may not receive as much revenue as originally planned. Or volume may be greater than the expected amount such that an assigned carrier may not have sufficient truckload capacity. In this case, the shipper may need to procure additional third-party services at extra cost to meet actual volume demand. In either case, uncertainty can have a detrimental effect and the winner determination should properly account for this possibility. In this paper, we incorporate uncertainty in shipment volume into the winner determination problem for TL procurement. In particular, we formulate a two-stage stochastic integer program (SIP) to hedge the shipper’s risk under uncertainty. Stochastic programs are mathematical programs that explicitly incorporate uncertainty in parameters see Kall and Wallace, 1995 and Birge and Louveaux, 1997. Uncertainty is represented as scenarios each of which represents a possible value for a parameter that is random. The first-stage decisions correspond to assigning carriers to lanes based on submitted packages before uncertainty in shipment volumes has been resolved. The second-stage decisions correspond to assigning actual volume to the carriers after uncertainty of shipment volume has been realized. We assume a finite number of scenarios for shipment volume on lanes each occurring with a probability according to a discrete distribution. We also show the value of the stochastic solution over deterministic solutions obtained from a related deterministic model that uses the average volume instead of scenarios. Carrier bids are structured to specify a range of volume that is acceptable for a given subset of lanes and an associated revenue amount to be received per unit volume shipped for a volume amount within the specified range. If a carrier is included in the first-stage decisions, and the realized volume is less than the lower volume bound specified in her bid, then the carrier will have the right to move this lower volume but at a benefit of the lower bound volume times the per unit volume revenue. This feature is included to encourage bidders to participate in the auction without fear of winning a set of lanes in which little volume is realized by guaranteeing a winning carrier’s minimum desired volume for her specified set of lanes. If the shipper experiences volume on allocated lanes that is greater than the upper bounds specified by winning carriers, then the shipper must procure additional third-party services that is assumed to be more costly in general than by procuring through the combinatorial auction. The stochastic program aims to find a set of carriers at the first stage so that the expected costs of paying winning carriers and using additional third-party carriers or paying carriers to ship below their minimum volume requirements are minimized subject to meeting actual volume realizations under all specified scenarios. Furthermore, shippers will often wish to guarantee that if a carrier is awarded any business, then it has to be for a certain minimum threshold amount, which is typically used to ensure that a carrier wins enough business to support a pool operation see Caplice and Sheffi (2003). These amounts are called “threshold volumes” and these type of constraints are “if-then constraints”. In our model, the inclusion of the range of shipment volumes submitted by each carrier completely captures this basic idea: the upper bound of the range matches the maximum number of trucks committed to the auctioneer; and the lower bound of the range matches the threshold volume. In addition, we include other practical side constraints and features for the shipper such as ensuring that the number of winning carriers is within a certain minimum and maximum range, ensuring minimum and maximum override constraints. Also, the objective function is formulated so that incumbent carriers can be favored based on the setting of an appropriate parameter. The main objective of the paper is to demonstrate that stochastic integer programming can be a relevant and useful modeling framework for winner determination in truckload combinatorial auctions where shipment uncertainty is an important factor along with including a comprehensive set of business side constraints. Stochastic integer programming is a very challenging class of problems. However, we find that branch and bound solvers such as CPLEX can handle reasonable sized instances. Very large instances will require specialized algorithmic approaches and we do not pursue these directions in this paper and instead focus on stochastic programming as a viable modeling framework for winner determination in environments where uncertainty is an issue. The rest of the paper is organized as follows. The paper briefly reviews two-stage stochastic programming in Section 2. Section 3 introduces the two-stage stochastic winner determination model. Section 4 presents a deterministic version of the stochastic model with similar constraints and business considerations. Section 5 introduces the benchmarking method used to measure the performance of the stochastic model and demonstrates the value of the stochastic solution. An example is provided in Section 6 to illustrate the stochastic model. The computational results are given in Section 7. Section 8 concludes the paper.

We have developed a two-stage stochastic integer programming model for the winner determination problem in combinatorial auctions for TL procurement that incorporates shipment volume uncertainty and that includes many important business side constraints. We have shown the value of the stochastic solution over the deterministic version of the problem. Moderately sized instances of the stochastic winner determination can be solved by commercial solvers in reasonable time. The contribution of the paper to the literature is the incorporation of uncertainty in TL combinatorial auctions through the use of stochastic programming. In particular, to the best of our knowledge this work represents one of the first attempts to model uncertainty in combinatorial auctions and the first to use stochastic programming in combinatorial auctions. Important future research directions include developing decomposition methods for the stochastic model in order to handle large-scale instances and of methods to generate problem instances that are reflective of real world TL procurement auctions. Also, in the current model, volume-based discount is not allowed. However, in TL transportation practice, it is common. Including the volume-based discount to the bid structure will lead to a non-linear integer model, i.e., a step function associated with the volume-based discount. This could also be promising extension for future research.