Combinatorial Bid Generation Problem for Transportation Service Procurement

Abstract

In combinatorial auctions, solving the bid generation problem (BGP) for bidders is critical to achieving efficiency. However, in the recent surge of combinatorial auction research, little attention has been paid to the BGP. In this paper, the BGP faced by transportation service providers is studied. First, the bidder's optimality criterion of a combinatorial bid is clarified, and then the focus is on the bundling method when an OR bid language is used. Through examples, bundles generated by solving the optimal truck routing problem were examined, and it was found that the resulting bid might not be optimal. This heuristic is compared with a simple nearest insertion method. The simulation result shows that whereas the former outperforms the latter in most cases, many times the latter outperforms the former by 5% to 8%.

Get full access to this article

View all access options for this article.

References

Rothkopf

Peke

and Harstad

Computational Manageable Combinational Auctions, Management Science, Vol. 44, 1998, pp. 1131–1147.

Andersson

Tenhunen

and Ygge

Integer Programming for Combinatorial Auction Winner Determination. Proc., 4th International Conference on Multi-agent Systems (ICMAS), Boston, 2000, pp. 108–121.

Xia

Koehler

G. J.

and Whinston

A. B.

Pricing Combinatorial Auctions. European Journal of Operational Research, Vol. 154, 2004, pp. 251–270.

Nisan

Bidding and Allocation in Combinatorial Auctions. Proc., 2nd ACM Conference on Electronic Commerce, Minneapolis, Minn., 2000, pp. 1–12.

Boutilier

and Hoos

Bidding Language for Combinatorial Auctions. Proc., 17th International Joint Conference on Artificial Intelligence (IJCAI), Seattle, Wash., 2001, pp. 1211–1216.

Rassenti

S. J.

Smith

V. L.

and Bulfin

R. L.

A Combinatorial Auction Mechanism for Airport Time Slot Allocation. The Bell Journal of Economics, Vol. 13, 1982, pp. 402–417.

Cramton

Spectrum Auctions, Handbook of Telecommunications Economics ( Cave

Majumdar

and Vogelsang

, eds.), Elsevier Science, Amsterdam, 2002, pp. 605–639.

Hohner

Rich

Reid

Davenport

A. J.

Kalagnanam

Lee

H. S.

and An

Combinatorial and Quantity-Discount Procurement Auctions Benefit Mars, Incorporated and Its Suppliers. Interfaces, Vol. 33, 2003, pp. 23–35.

Epstein

Henriquez

Catalan

Weintraub

G. Y.

and Martinez

A Combinatorial Auction Improves School Meals in Chile. Interfaces, Vol. 32, 2002, pp. 1–14.

10.

Caplice

An Optimization Based Bidding Process: A New Framework for Shipper-Carrier Relationship. Ph.D. thesis. School of Engineering, Massachusetts Institute of Technology, Cambridge, 1996.

11.

Kelly

and Steinberg

A Combinatorial Auction with Multiple Winners for Universal Service. Management Science, Vol. 46, 2003, pp. 586–596.

12.

Ledyard

J. O.

Olson

Porter

Swanson

J. A.

and Torma

D. P.

The First Use of a Combined-Value Auction for Transportation Services. Interfaces, Vol. 32, 2002, pp. 4–12.

13.

Song

and Regan

A. C.

Approximation Algorithms for the Bid Construction Problem in Combinatorial Auctions for the Procurement of Freight Transportation Contracts. ITS-UCI Working Paper, University of California, Irvine, 2002.

14.

Song

and Regan

A. C.

Combinatorial Auctions for Transportation Service Procurement: The Carrier Perspective. In Transportation Research Record: Journal of the Transportation Research Board, No. 1833, Transportation Research Board of the National Academies, Washington, D.C., 2003, pp. 40–46.

15.

Figliozzi

M. A.

Mahmassani

H. S.

and Jaillet

Framework for the Study of Carrier Strategies in an Auction–Based Transportation Marketplace. In Transportation Research Record: Journal of the Transportation Research Board, No. 1854, Transportation Research Board of the National Academies, Washington, D.C., 2003, pp. 162–170.

16.

McGill

and van Ryzin

Revenue Management: Research Overview and Prospects. Transportation Science, Vol. 33, 1999, pp. 233–256.