Solving a bi-objective winner determination problem in a transportation procurement auction
- PDF / 307,277 Bytes
- 14 Pages / 595.276 x 790.866 pts Page_size
- 45 Downloads / 180 Views
ORIGINAL PAPER
Solving a bi-objective winner determination problem in a transportation procurement auction Tobias Buer • Giselher Pankratz
Received: 5 February 2009 / Accepted: 14 April 2010 / Published online: 13 June 2010 Springer-Verlag 2010
Abstract This paper introduces a bi-objective winner determination problem which arises in the procurement of transportation contracts via combinatorial auctions where bundle bidding is possible. The problem is modelled as a bi-objective extension to the set covering problem. We consider both the minimisation of the total procurement costs and the maximisation of the service-quality level at which the transportation contracts are executed. Taking into account the size of real-world transport auctions, a solution method has to cope with problems of up to some hundred contracts and a few thousand bundle bids. To solve the problem, we propose a bi-objective branch-andbound algorithm and eight variants of a multiobjective genetic algorithm. Artificial benchmark instances that comply with important economic features of the transport domain are introduced to evaluate the methods. The branch-and-bound approach is able to find the optimal trade-off solutions in reasonable time for very small instances only. The eight variants of the genetic algorithm are compared among each other by means of large instances. The best variant is also evaluated using the small instances with known optimal solutions. The results indicate that the performance largely depends on the initialisation heuristic and suggest also that a well-balanced combination of genetic operators is crucial to obtain good solutions.
T. Buer (&) G. Pankratz Department of Information Systems, Faculty of Business Administration and Economics, University of Hagen, 58084 Hagen, Germany e-mail: [email protected] G. Pankratz e-mail: [email protected]
Keywords Winner determination Combinatorial auction Multiobjective optimisation Branch-and-bound Genetic algorithm
1 Procurement of transportation contracts Shippers, like retailers as well as industrial enterprises, often procure the transportation services they require via reverse auctions, where the objects under auction are transportation contracts. Usually, such contracts are designed as framework agreements lasting for a period of 1–3 years, and defining a pick-up location, a delivery location, and the type and volume of goods that are to be transported between both locations. Additionally, further details such as a contract-execution frequency, e.g., delivery twice a week, and the required quality of service, e.g., a predefined on-time delivery rate, are specified in a transportation contract. A carrier can bid for one or more contracts. In each bid, the carrier states how much he wants to be paid for accepting the specified contracts. Transportation procurement auctions are of high economic relevance. Caplice and Sheffi [4] report on the size of real-world transportation auctions in which they were involved over a period of 5 years.
Data Loading...
