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. Although price is the main driver, a shipper may take into account many additional considerations, including upper bounds on the number of winning carriers in total, per load location, per country of destination, and the maximal transport volume any carrier is allowed to win. The winner determination problem is the problem of finding an allocation of the lanes to the carriers so as to minimize total transportation costs such that each lane is assigned to exactly one carrier and the additional constraints are satisfied. The winner determination problem is extremely hard in practice, and most carriers resort to simple rules of thumb to select the winning carriers. This is no surprise. It is proved that the problem is NP-hard in the strong sense. It is modeled the winner determination problem as an ILP problem (integer linear programming). It is tried and solved the model by use of CPLEX, a state-of-the-art ILP solver. Tested on a comprehensive set of instances generated along the characteristics of a real world case of a European chemical shipper with about 4000 laens, CPLEX is capable of solving instances with no more than 270 lanes to optimality, underlining the practical difficulty of the winner determination problem. It is also developed a fast randomized heuristic. It is shown that it performs remarkably well, with a gap of no more than 0.8 % from optimality. This performance supports the conclusion that the heuristic can be used to obtain good approximations quickly for realistic, much larger instances.
A winner determination problem of tendering transportation services
Zeitschrift für Betriebswirtschaft ; 76 , 2 ; 125-137
2006
13 Seiten, 3 Tabellen, 22 Quellen
Article (Journal)
German
Competitive tendering of rail services
TIBKAT | 2007
|Competitive tendering of rail services
TIBKAT | 2007
|Competitive Tendering of Rail Services
SLUB | 2007
|The Danish Experience of Tendering Winter Services
British Library Conference Proceedings | 1998
|