A Comparative Study of Two Models for Handling Transportation Cost in Combinatorial Auctions

A Comparative Study of Two Models for Handling Transportation Cost in Combinatorial Auctions

Fu-Shiung Hsieh (Chaoyang University of Technology, Taiwan)
Copyright: © 2020 |Pages: 23
DOI: 10.4018/IJDSST.2020070104
OnDemand PDF Download:
List Price: $37.50
10% Discount:-$3.75


Although combinatorial auctions have been extensively studied, the factor of transportation cost has not been considered in most studies. Without considering transportation cost, the profits of the seller cannot be determined accurately. The goals of this article are to propose models, develop a solution methodology for the winner determination problem (WDP) in combinatorial auctions and study the effects of transportation cost on the seller's profits. Two models are proposed: one model considers transportation cost in WDP whereas the other one does not take transportation cost into account in WDP but calculates the transportation cost based on the solution obtained. The author formulates the WDPs for these two models and proposes a solution method. The author then analyzes and compares the two models to illustrate the advantage of taking transportation cost into account in combinatorial auctions. Finally, the author studies the influence of transportation cost on combinatorial auctions by examples and demonstrate effectiveness of our approach.
Article Preview

1. Introduction

One of the recent trends in the development of auction mechanisms is combinatorial auctions. In combinatorial auctions, bidders can place bids on a combination of goods according to personal preferences rather than just individual items. It is beneficial to adopt combinatorial auction model if complementarities exist between the items to be auctioned. There are many well-known combinatorial auction examples, including the auctioning of Federal Communications Commission's radio spectrum licenses, the sales of airport time slots, allocation of delivery routes, carpool and trading goods (de Vries & Vohra 2003; Rassenti et al. 1982; Zhang, et al. 2019; Hsieh & Guo 2019; Hsieh et al. 2019). For example, application of combinatorial auctions in carpooling systems can be found in (Hsieh et al. 2019). Combinatorial double auctions also provide an efficient mechanism to trade goods in an electronic marketplace (Hsieh & Guo 2019). Combinatorial auctions have been extensively studied (Abrache et al. 2004; Catalán et al. 2009; Harsha et al. 2010; Leskelä et al. 2007; Meeus et al. 2009; Özer & Özturan 2009; Perugini et al. 2005; Sandholm, 2000; Yang et al. 2009). An excellent survey on combinatorial auctions can be found in the papers of de Vries & Vohra (2003) and Pekeč & Rothkopf (2003).

Combinatorial auctions can improve the efficiency of trading goods between buyers and sellers. However, the winner determination problem (WDP) is notoriously difficult to solve from a computational point of view (Rothkopf et al., 1998), (Xia et al., 2005) due to the exponential growth of the number of combinations. The combinatorial auction problem can be modelled as a set packing problem (SPP) (Andersson et al., 2000), (Fujishima, 1999), (Hoos and Boutilier, 2000), (Vemuganti, 1998), (Xia et al., 2005) . Sandholm mentioned that determining the winners so as to maximize revenue in combinatorial auction is NP-complete (Sandholm, 1999), (Sandholm, 2000), (Sandholm, 2002). Many algorithms have been developed for combinatorial auction problems. Exact algorithms have been developed for the SPP problem, including iterative deepening A* search (Sandholm, 2000) and the direct application of available CPLEX IP solver (Andersson et al., 2000). Gonen and Lehmann proposed branch and bound heuristics for finding optimal solutions for multi-unit combinatorial auctions (Gonen and Lehmann, 2000). Jones and Koehler studied combinatorial auctions using rule-based bids (Jones and Koehler, 2002). In (Guo et al., 2005; Hsieh & Lin, 2012; Hsieh & Liao, 2015a; Hsieh & Liao, 2015b), the authors proposed a Lagrangian heuristic and a Lagrangian relaxation approach (Fisher, 2004) for combinatorial auctions and combinatorial reverse auctions, respectively.

Complete Article List

Search this Journal:
Volume 15: 1 Issue (2023): Forthcoming, Available for Pre-Order
Volume 14: 4 Issues (2022): 1 Released, 3 Forthcoming
Volume 13: 4 Issues (2021)
Volume 12: 4 Issues (2020)
Volume 11: 4 Issues (2019)
Volume 10: 4 Issues (2018)
Volume 9: 4 Issues (2017)
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing