Single Vehicle One Commodity Pickup and Delivery Problem

Whole list of computational results of the paper Bike sharing system: solving the static rebalancing problem, with D. Chemla and R. Wolfler Calvo


The instances are taken from the paper A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery, DAM 145, 2004, by H. Hernandez Pérez and H. Salazar González. For a first set of instances, the initial number of bikes on each vertex is 10 and the target number is 10 plus the original demand. For a second set of instances, the initial number of bikes on each vertex is 30 and the target number is 30 plus three times the original demand.

The instances are solved with the help of a branch-and-cut method. Two branching schemes have been tested. The first one, called reliability branching, is an usual branching on variables. The second one, called degree branching, is a branching on the degree constraint in the MIP formulation.

For more details, see our paper.

The algorithms have been coded in C++, embedded into SCIP and tested on a PC AMD Athlon 5600+ clocked at 2.8 GHz, with 16 GB RAM.



  • Results for the instances with an initial number of bikes of 10 per vertex:
    reliability branching
    degree branching

  • Results for the instances with an initial number of bikes of 30 per vertex:
    reliability branching
    degree branching