Geodesic
Formalization of pickup and delivery problem
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematika, mehanika, fizika, Tome 9 (2017) no. 1, pp. 13-21 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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).
Keywords: routing, optimization, pickup and delivery problem. 
@article{VYURM_2017_9_1_a1,
     author = {E. M. Bronshtein and E. V. Gindullina and R. V. Gindullin},
     title = {Formalization of pickup and delivery problem},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matematika, mehanika, fizika},
     pages = {13--21},
     year = {2017},
     volume = {9},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURM_2017_9_1_a1/}
}
TY  - JOUR
AU  - E. M. Bronshtein
AU  - E. V. Gindullina
AU  - R. V. Gindullin
TI  - Formalization of pickup and delivery problem
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematika, mehanika, fizika
PY  - 2017
SP  - 13
EP  - 21
VL  - 9
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VYURM_2017_9_1_a1/
LA  - ru
ID  - VYURM_2017_9_1_a1
ER  - 
%0 Journal Article
%A E. M. Bronshtein
%A E. V. Gindullina
%A R. V. Gindullin
%T Formalization of pickup and delivery problem
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematika, mehanika, fizika
%D 2017
%P 13-21
%V 9
%N 1
%U http://geodesic.mathdoc.fr/item/VYURM_2017_9_1_a1/
%G ru
%F VYURM_2017_9_1_a1
E. M. Bronshtein; E. V. Gindullina; R. V. Gindullin. Formalization of pickup and delivery problem. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematika, mehanika, fizika, Tome 9 (2017) no. 1, pp. 13-21. http://geodesic.mathdoc.fr/item/VYURM_2017_9_1_a1/

[1] G. Danzig, J. Ramser, “The Truck Dispatching Problem”, Management Science, 6:1 (1959), 80–91 | DOI | MR

[2] http://neo.lcc.uma.es/vrp/

[3] Bronshtein E. M., Zaiko T. A., “Deterministic optimizational problems of transportation logistics”, Automation and Remote Control, 71:10 (2010), 2132–2144 | DOI | MR | Zbl

[4] M. Furtadoa, P. Munaria, R. Morabito, Pickup and delivery problem with time windows: a new compact two-index formulation, Technical Report, Production Engineering Department, Federal University of São Carlos, Rod. Washington Luís, km 235 - SP-310, São Carlos - SP - CEP: 13565-905, Brazil, July 2015 http://www.optimization-online.org/DB_HTML/2015/07/5022.html

[5] R. E. Burkard, E. Cela, P. M. Pardalos, L. S. Pitsoulis, “The quadratic assignment problem”, Handbook of Combinatorial Optimization, Springer US, 1999, 1713–1809

[6] F. Glover, “Improved linear integer programming formulations of nonlinear integer problems”, Management Science, 22 (1975), 455–460 | DOI | MR

[7] E. L. Lawler, “The quadratic assignment problem”, Management Science, 9 (1963), 586–599 | DOI | MR | Zbl

[8] K. S. Ruland, E. Y. Rodin, “The pickup and delivery problem: Faces and branch-and-cut algorithm”, Computers mathematics with applications, 33:12 (1997), 1–13 | DOI | MR | Zbl

[9] L. Kaufmann, F. Broeckx, “An algorithm for the quadratic assignment problem using Benders' decomposition”, European Journal of Operational Research, 1978, no. 2, 204–211

[10] C. Miller, A. Tucker, R. Zemlin, “Integer programming formulations and travelling salesman problems”, J. A.C.M., 7:4 (1960), 326–329 | MR | Zbl

[11] M. Desrochers, G. Laporte, “Improvements and extensions to the Miller–Tucker–Zemlin subtour elimination constraints”, Operations Research Letters, 10:1 (1991), 27–36 | DOI | MR | Zbl

[12] J.-F. Cordeau, G. Laporte, S. Ropke, “Recent models and algorithms for one-to-one pickup and delivery problems”, The Vehicle Routing Problem, Latest Advances and Challenges, eds. B. L. Golden, S. Raghavan, E. A. Wasil, Springer, Boston, 2007, 327–357 | MR

[13] http://www.sintef.no/contentassets/cfb19ab9b7c74

[14] http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/