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.

Effiziente, operative Torbelegung mittels kombinatorischer Auktionen

Das operative Torbelegungsproblem (TBP) z. B. an einem Distributions- oder Cross-dockingzentrum ist ein logistisches Problem, bei dem es gilt, an- und abfahrende Fahrzeuge zeitlich und räumlich so auf die Warenein- und -ausgangstore zu verteilen, dass eine mög-lichst kostengünstige Abfertigung ermöglicht wird. Bisherige Arbeiten, die sich mit dem TBP beschäftigen, lassen Aspekte der Kooperation außer Acht. Dieser Beitrag stellt ein Verfahren vor, durch das der Nachteil einseitig optimaler Torbelegungen überwunden werden kann. Dabei wird auf das Mittel der kombinatorischen Auktionen zurückgegriffen und das TBP als Allokationsproblem modelliert, bei dem Frachtführer um Bündel konsekutiver Einheitszeit-intervalle an den Toren konkurrieren. Mittels eines Vickrey-Clarke-Groves-Mechanismus wird einerseits die Anreizkompatibilität, andererseits die individuelle Rationalität des Auk-tionsverfahrens sichergestellt. Das Verfahren wurde in ILOG OPL Studio 3.6.1 implemen-tiert und die durch Testdaten gewonnenen Ergebnisse zeigen, dass die Laufzeiten gering genug sind, um das Verfahren für die operative (kurzfristige) Planung einzusetzen und so transportlogistische Prozesse für alle Beteiligten wirtschaftlicher zu gestalten.