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.


    Access

    Access via TIB

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    A winner determination problem of tendering transportation services


    Contributors:

    Published in:

    Publication date :

    2006


    Size :

    13 Seiten, 3 Tabellen, 22 Quellen




    Type of media :

    Article (Journal)


    Type of material :

    Print


    Language :

    German




    Competitive tendering of rail services

    European Conference of Ministers of Transport | TIBKAT | 2007


    Competitive tendering of rail services

    European Conference of Ministers of Transport | TIBKAT | 2007


    Competitive Tendering of Rail Services

    OECD / European Conference of Ministers of Transport | SLUB | 2007


    The Danish Experience of Tendering Winter Services

    Carstensen, A. / Permanent International Association of Road Congress | British Library Conference Proceedings | 1998