Formalization of pickup and delivery problem

The problems of routing like ONE-TO-ONE or Traveling Salesman Problem with Pickup and Delivery (TSPPD) consist in forming a cycle of the minimal length that guarantees a shipment from manufacturers to customers in case of the shipment from each producer to a specific customer. In particular, the problem occurs in case of delivery of passengers (for example, by a taxi company). Some properties of the set problem are specified. The range of quadratic, integer linear and mixed integer linear formalizations of such problems, in which the number of limitations grows polynomially with the increase in the number of points, is considered. In particular, Boolean elements of a permutation matrix, two-index and three-index variables, which describe a precedence relation, are used as variables. In the context of such formalizations it is possible to use optimization packages. We have conducted the computational experiment with the help of CPLEX 12.6 package. The mixed integer linear three-index model was record-breaking in terms of productivity based on randomly generated data. It's found out that some additional limitations significantly improve the effectiveness of a solution. Meanwhile, the use of some other restrictions negates the effectiveness. In most cases the limitedness of RAM is a factor which hinders the solution of high dimension problems.
In case of some additional restrictions the problem is solved for a set of points, suggested by a library proposed by Heidelberg University (Germany). When using the mixed integer linear model, solutions of extremely high dimension problems are obtained (up to 391 pairs of points). The prospects of applying these models consist in RAM expansion and improvement of CPLEX optimization package. Some scholars note that CPLEX 11 (2007) works 30 000 times faster than CPLEX 1 (1991).