We introduce a new generalization of the traveling salesman problem with pickup and delivery, that stems from applications in maritime logistics, in which each node represents a port and has a known draft limit. Each customer has a demand, characterized by a weight, and pickups and deliveries are performed by a single ship of given weight capacity. The ship is able to visit a port only if the amount of cargo it carries is compatible with the draft limit of the port. We present an integer linear programming formulation and we show how classical valid inequalities from the literature can be adapted to the considered problem. We introduce heuristic procedures and a branch-and-cut exact algorithm. We examine, through extensive computational experiments, the impact of the various cuts and the performance of the proposed algorithms.


    Access

    Download


    Export, share and cite



    Title :

    The traveling salesman problem with pickups, deliveries, and draft limits



    Publication date :

    2018-01-01



    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    000




    The Traveling Salesman Problem with Pickups, Deliveries, and Handling Costs TRANSPORTATION SCIENCE 2010 44: 383-399

    Battarra, M. / Erdogan, G. / Laporte, G. et al. | British Library Online Contents | 2010



    The Vehicle Routing Problem with Divisible Deliveries and Pickups

    Nagy, Gábor / Wassan, Niaz A. / Speranza, M. Grazia et al. | British Library Online Contents | 2015