GRASP with Hybrid Path Relinking for Bi-Objective Winner Determination in Combinatorial Transportation Auctions

The procurement of transportation services via large-scale combinatorial auctions involves a couple of complex decisions whose outcome highly influences the performance of the tender process. This paper examines the shipper's task of selecting a subset of the submitted bids which efficiently trades off total procurement cost against expected carrier performance. To solve this bi-objective winner determination problem, we propose a Pareto-based greedy randomized adaptive search procedure (GRASP). As a post-optimizer we use a path relinking procedure which is hybridized with branch-and-bound. Several variants of this algorithm are evaluated by means of artificial test instances which comply with important real-world characteristics. The two best variants prove superior to a previously published Pareto-based evolutionary algorithm.

RFIDice - Augmenting Tabletop Dice with RFID

Augmented dice allow players of tabletop games to have the result of a roll be automatically recorded by a computer, e.g., for supporting strategy games. We have built a set of three augmented-dice-prototypes based on radio frequency identification (RFID) technology, which allows us to build robust, cheap, and small augmented dice. Using a corresponding readout infrastructure and a sample application, we have evaluated our approach and show its advantages over other dice augmentation methods discussed in the literature.