Single Vehicle One Commodity Pickup and Delivery ProblemBike 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. reliability branching degree branching reliability branching degree branching |