Solving a bi-objective winner determination problem in a transportation procurement auction
This paper introduces a bi-objective winner determination problem which arises in the procurement of transportation contracts via combinatorial auctions. The problem is modelled as an extension to the set covering problem and considers the minimisation of the total procurement costs and the maximisation of the service-quality level of the execution of all transportation contracts tendered. To solve the problem, an exact branch–and–bound algorithm and eight variants of a multiobjective genetic algorithm are proposed. The algorithms are tested using a set of new benchmark instances which comply with important economic features of the transportation domain. For some smaller instances, the branch–and–bound algorithm finds all optimal solutions. Large instances are used to compare the relative performance of the eight genetic algorithms. The results indicate that the quality of a solution depends largely on the initialisation heuristic and suggest also that a well-balanced combination of different operators is crucial to obtain good solutions. The best of all eight genetic algorithms is also evaluated using the small instances with the results being compared to those of the exact branch–and–bound algorithm.
Nutzung und Vervielfältigung:
Alle Rechte vorbehalten