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

We consider the carrier’s optimal bid generation problem in combinatorial auctions for transportation procurement. Bidders (carriers) employ vehicle routing models to identify sets of lanes (origin-destination pairs) based on the actual routes that a fleet of trucks will follow in order to maximize profit. Routes are constructed by optimally trading off repositioning costs of vehicles and the rewards associated with servicing lanes. The carrier optimization represents simultaneous generation and selection of routes and can incorporate any existing commitment. We employ both column generation and Lagrangian based techniques for solving the carrier optimization model and present numerical results.

Truckload (TL) transportation accounts for a substantial portion of the annual overall billion dollar freight transportation industry in North America. A significant portion of this demand emanates from shippers e.g. manufacturers and retailers that need freight to be transported in dedicated (truckload) movements from origins to destinations. Shippers often need to acquire third party logistics carriers to meet demand since in-house transportation capacity may be insufficient. Usually, contracts for transportation services with carriers are sought through a competitive request for proposals (RFP) process. The basic unit of interest is called a lane which specifies an origin-destination pair for particular freight movement. Carriers usually engage in some form of auction to bid on individual lanes of interest. Shippers evaluate bids on lanes individually and then awards lanes separately to carriers based on several factors e.g. price and business requirements. However, as noted by Caplice (1996), carriers are often driven by economies in scope in obtaining lanes. That is, a carrier may desire to bid on separate lanes that collectively represent a cost efficient service route with respect to minimizing empty miles travel and other repositioning costs. For example, a contract to move freight from Toronto to Montreal would be not be worth as much as a contract that requires movement of freight from Toronto to Montreal and then movement of freight from Montreal and back to Toronto. The first case would involve a trip back to Toronto with an empty load. In general, repositioning empty trucks comprise a substantial portion of operating expenses. In short, carriers seek a set of lanes that are synergistic with respect to repositioning costs. However, many current forms of transportation procurement do not guarantee that a carrier may get a particular cost minimizing set of lanes. A carrier may end up with an incomplete set of lanes that is worth far less than having the complete set or a carrier may incur a loss in servicing the incomplete set of won lanes due to repositioning costs. In auction parlance, the problem of not obtaining a complete set of desired items in a multi-item auction is called the exposure problem (see Bykowsky et al., 1995 and Kwasnica et al., 2005). Transportation procurement auctions in most instances award lanes separately and so may be subject to the exposure problem. In general, it is desirable for auction outcomes to result in efficient allocations where bidders that value the items the most obtain them and pay accordingly the highest for the items. The exposure problem can prevent auctions from achieving high levels of efficiency since bidders may be reluctant to bid aggressively for items in fear of not obtaining a complete set of items which can make generation of revenue difficult for the auctioneer and allow others to obtain items for lower prices. Recently, combinatorial auctions (CA) have been suggested to overcome the exposure problem in auction settings (Kwasnica et al., 2005). Combinatorial auctions are auction formats that allow bidders to place a single bid on a set of distinct items. In the context of transportation procurement carriers could place a single bid on several distinct lanes and if a bid were successful then the carrier would receive the complete set (package) else carriers would receive nothing. This would minimize the risks in obtaining only a subset of lanes that are not worth much. It would also be possible for a carrier to submit multiple packages each consisting of one or more distinct lanes. Combinatorial auctions can result in more efficient allocations in multi-unit auction settings and can be promising mechanisms to allocate lanes since carriers may have substantial synergistic preferences for certain lanes and thus will bid more aggressively for the set without fear of getting an incomplete set. Combinatorial auctions have been suggested for truckload transportation procurement and have been successfully used in several instances. Caplice and Sheffi (2003) discuss the value of combinatorial auctions in transportation procurement and present several optimization models for shippers to assign carriers to lanes. Ledyard et al. (2002), document the experience of Sears in using CA auctions for outsourcing logistics needs and report the successful use of a multi-round CA where Sears has been savings millions of dollars annually on outsourced transportation costs by using their CA mechanism. Elmaghraby and Keskinocak (2003) present the experience of Home Depot in using a single round CA mechanism for outsourcing truckload transportation capacity to move freight between the many thousands of stores of Home Depot. One issue not discussed extensively is on normative methods for carrier bid generation in combinatorial auction settings for transportation procurement i.e. how to determine the best set of lanes. Most CA models assume that bidders know which set of lanes to bid for. In general, the evaluation of packages from the bidding perspective is difficult since there are an exponential number of possible relevant packages for a bidder. Nevertheless, bid generation is an important issue since carriers are driven by economies of scope and thus want lanes that correspond to routes that minimize vehicle reposition costs. Thus, package of lanes should be determined optimally given general information about what lanes are available. Song and Regan (2002) present the first carrier model that uses optimization-based approximation to determine useful packages of lanes that a carrier could bid for in the context of CA for truckload transportation procurement. This work is important in that it is the first to address the bidder evaluation complexity through optimization models in the CA literature. Since there are an exponential number of possible routes it makes sense to use a normative optimization model to find the best routes. Optimization models that can be employed such as those for vehicle routing are computationally difficult to solve. However, a route obtained by using a good approximation for an appropriate optimization will represent a vast improvement over a route generated based on naïve or non-optimization based methods. The method employed by Song and Regan (2002) consists of two phases. A first phase determines heuristically the potential routes that will correspond to potentially useful packages of lanes that a carrier could bid for and then a second phase associates a binary variable with each route (package) generated in the first phase. Each route is constructed so that all relevant operational constraints can be met. Then in a second phase a set partitioning model is constructed based on the binary variables to determine which of the packages to select. The set partitioning model is defined so that routes are selected (i.e. binary variables associated with selected routes are set to 1) subject to minimizing repositioning costs. Finally, the packages selected under the set partitioning model are submitted to the auctioneer in the form of OR bids (an OR bid is a set of packages with associated bid prices so that any subset of these bids that win would be acceptable to a carrier) see Abrache et al., 2004 and Nisan, 2000 for an extensive discussion on logical bid formulations. Song and Regan (2003) also modify the above procedures to incorporate substitutable bids by creating an appropriate set cover model and bid augmentation method. They validate the carrier model in simulations where it is found that carriers that employ the optimization model benefit more than carriers that follow a simple bid selection strategy. In this paper, we propose a carrier optimization model that integrates the generation and selection of routes. In addition, the objective of the carrier optimization model is to maximize utility which we define to be revenue from servicing a set of lanes minus the transportation costs. Given prices for lanes the model selects a package that does not necessarily achieve the least repositioning cost as defined by amount of empty movement as in Song and Regan (2003) but seeks a package that offers the most profit. The goal is to find the optimal tradeoff between the revenue provided by servicing a set of lanes and the associated repositioning costs. This is an important objective since identification of the right set of lanes will depend critically on not just repositioning costs but also on how much revenue a carrier will receive for servicing the lanes. The model is an integer program that also incorporates any existing lane commitments as well as other operational constraints. We give a decomposition approach based on column generation and Lagrangian relaxation. The main contribution of the model is in the consideration of optimal integration of route generation and selection in the presence of operational constraints under utility maximization. The model is a quadratically constrained quadratic integer program for which we develop a decomposition based heuristic. The decomposition strategy involves a partition of the model into a master and a subproblem for which a column generation-like strategy is employed to derive approximate solutions to the original carrier formulation. In addition, the model can be incorporated in multi-round settings by using approximate-price information for lanes based on tentative allocation of lanes in a round (Kwon et al., 2005). In the case of single round auctions, reservation prices for lanes can be used as coefficients in the utility maximization. The paper is organized as follows. First, we discuss auction frameworks for truckload transportation procurement in Section 2. In Section 3 we present notations, definitions, and assumptions that pertain to the carrier optimization model that we develop in Section 4. Section 4 also gives a decomposition of the optimization model. Section 5 presents the algorithms and heuristics for solution of the optimization model in Section 4. Section 6 gives the numerical results. Section 7 addresses the model use in multiple depot situation and concluding remarks are given in Section 8.

Song and Regan (2003) have validated the use of optimization models for carriers in combinatorial auctions for transportation procurement. The contribution of this paper lies in the development of a model that integrates route (package) generation and selection simultaneously, which has never been considered before. In addition, we present a column generation approach to solve the underlying non-linear quadratic integer program which is a unique approach for this class of optimization models. The model represents a utility maximizing decision problem that carriers can use to determine the best packages for bidding in a combinatorial auction. The model trades off revenue from servicing a set of lanes and the physical costs or repositioning. The algorithms that we develop for the carrier model can handle scenarios involving hundreds of lanes. We have considered instances for carrier models with up to 335 lanes and the decomposition algorithm presented effectively computes optimal solutions up to 200 lanes, and we envision the carrier model to be only part of the optimization for the carrier’s entire network. That is, we envision that the carrier model in this paper pertains to a single node (depot) of the carrier. We associate a carrier optimization with a depot to capture realistic features of driver and equipment re-origination (i.e. both often must be returned to the same physical location especially the drivers). If there are more depots then the optimization formulation is used separately for each depot, each depot problem would be responsible for lanes around a certain distance away from the depot which is realistic in practice. If a carrier were capable of servicing thousands of lanes then the there would be a decomposition of lane responsibility per depot. In this manner, tractability can be attained for situations involving thousands of lanes. Combinatorial auctions for transportation procurement are very promising frameworks for procurement of lanes having advantages for both the shipper and carriers. In general, developing models for carriers in this context is an important activity and our future research includes validating the carrier model developed in this paper in a multi-round setting employing single item price information as in Kwon et al. (2005). Another important research direction is in the incorporation of win/loss probabilities for lanes and including the uncertainty in the actual volume that will realize for a given lane. Both of these aspects are important issues in real world TL combinatorial auctions. In particular, approximation dual (price) information can be obtained from WDP solution and be used as coefficient (pjk) for each round of the auction.