A winner determination problem of tendering transportation services |
| |
Authors: | Linda van Norden Jo van Nunen Steef van de Velde |
| |
Institution: | (1) Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, P.O. Box 5031, 2600 GA Delft, The Netherlands;(2) RSM Erasmus University, P.O. Box 1738, 3000 DR Rotterdam, The Netherlands;(3) RSM Erasmus University, P.O. Box 1738, 3000 DR Rotterdam, The Netherlands |
| |
Abstract: | Summary For the tendering of long-term transportation contracts in the bulk industry, shippers use bidbooks that specify for each
lane the load location, the destination, the product and the volume that has to be transported over the next so many years.
Bidbooks are sent out to a preselected group of carriers, who subsequently quote a price for each of the lanes. After the
return of the bidbooks, the shipper determines the winning carriers. The winner determination problem is the problem of finding
an allocation of the lanes to the carriers so as to minimize total transportation costs. The winner determination problem
is NP-hard in the strong sense. We model the winner determination problem as an integer linear programming (ILP) problem and
try and solve the model by use of CPLEX, a state-of-the-art ILP solver. It turns out, that the model can solve problems optimally
with no more than 270 lanes. We also develop a fast randomized heuristic, and we show that it performs remarkably well, with
a gap of no more than 0.8% from optimality.
Zusammenfassung Zum Abschluss langfristiger Transportvertr?ge in der Massengüterindustrie bedienen sich die Spediteure bestimmter Angebotsbücher,
in denen für jede Tour die Ladestation, der Zielort, sowie die zu transportierende Produktart und deren Volumen für die n?chsten
Jahre spezifiziert werden. Die Angebotsbücher werden an eine ausgew?hlte Gruppe von Transportunternehmen geschickt, die dann
für jede Tour einen Preis angeben. Auf dieser Grundlage bestimmt der Spediteur dann die Transportunternehmen, die die Zuteilung
der Touren erhalten. Dabei wird die Verteilung der Touren auf die Transportunternehmen in der Weise vorgenommen, dass die
gesamten Transportkosten minimiert werden. Das Auswahlproblem ist NP-hard in strengem Sinne. Wir modellieren das Auswahlproblem
als ganzzahliges lineares Programmierungsproblem (ILP) und testen bzw. l?sen es mit Hilfe mit CPLEX, einem Standardl?sungsansatz
für ganzzahlige lineare Programmierung. Dabei zeigt sich, dass Modelle bis zu 270 Touren optimal gel?st werden k?nnen. Zugleich
wird auch eine Heuristik entwickelt und vorgestellt, deren L?sung nur unwesentlich von der Optimall?sung entfernt liegt.
|
| |
Keywords: | Integer linear programming applications transportation tendering reverse auction |
本文献已被 SpringerLink 等数据库收录! |
|