A new mathematical programming formulation for the single-picker routing problem. (English) Zbl 1346.90175
Summary: The Single-Picker Routing Problem deals with the determination of the sequence according to which article locations have to be visited in a distribution warehouse and the identification of the corresponding paths which have to be traveled by human operators (order pickers) in order to collect a set of items requested by internal or external customers. The Single-Picker Routing Problem (SPRP) represents a special case of the classic Traveling Salesman Problem (TSP) and, therefore, can also be modeled as a TSP. Standard TSP formulations applied to the SPRP, however, neglect that in distribution warehouses article locations are arranged in a specifically structured way. When arranged according to a block layout, articles are located in parallel picking aisles, and order pickers can only change over to another picking aisle at certain positions by means of so-called cross aisles. In this paper, for the first time a mathematical programming formulation is proposed which takes into account this specific property. By means of extensive numerical experiments it is shown that the proposed formulation is superior to standard TSP formulations.
References:
| [1] | Bozer, Y. A.; Kile, J. W., Order batching in walk-and-pick order picking systems, International Journal of Production Research, 46, 1887-1909 (2008) · Zbl 1153.90302 |
| [2] | Burkard, R.; Deneko, V. G.; van der Veen, J. A.A.; Woeginger, G. J., Well-solvable special cases of the traveling salesman problem: A survey, SIAM Review, 40, 496-546 (1998) · Zbl 1052.90597 |
| [3] | Claus, A., A new formulation for the traveling salesman problem, SIAM Journal on Algebraic and Discrete Methods, 5, 21-25 (1984) · Zbl 0532.90072 |
| [4] | Dantzig, G. B.; Fulkerson, D. R.; Johnson, S. M., Solution of a large-scale traveling salesman problem, Journal of the Operations Research Society of America, 2, 363-410 (1954) · Zbl 1414.90372 |
| [5] | Filip, E.; Otakar, M., The travelling salesman problem and its application in logistic practice, WSEAS Transactions on Business and Economics, 8, 163-173 (2011) |
| [6] | Gavish, B.; Graves, S. C., The traveling salesman problem and related problems. Working Paper GR-078-78 (1978), Operations Research Center, Massachusetts Institute of Technology |
| [7] | Glover, F.; Punnen, A. P., The travelling salesman problem: New solvable cases and linkages with the development of approximation algorithms, Journal of the Operational Research Society, 48, 502-510 (1997) · Zbl 0882.90124 |
| [8] | Gouveia, L.; Pires, J. M., The asymmetric travelling salesman problem: On generalizations of disaggregated Miller-Tucker-Zemlin constraints, Discrete Applied Mathematics, 112, 129-145 (2001) · Zbl 1054.90059 |
| [9] | Gu, J.; Goetschalckx, M.; McGinnis, L. F., Research on warehouse operation: A comprehensive review, European Journal of Operational Research, 177, 1-21 (2007) · Zbl 1111.90321 |
| [10] | Henn, S.; Koch, S.; Dörner, K. F.; Strauss, C.; Wäscher, G., Metaheuristics for the order batching problem in manual order picking systems, BuR - Business Research, 3, 82-105 (2010) |
| [11] | Henn, S.; Wäscher, G., Tabu search heuristics for the order batching problem in manual order picking systems, European Journal of Operational Research, 222, 484-494 (2012) · Zbl 1253.90008 |
| [12] | Hong, S.; Johnson, A. L.; Peters, B. A., Batch picking in narrow-aisle order picking systems with consideration for picker blocking, European Journal of Operational Research, 221, 557-570 (2012) · Zbl 1253.90009 |
| [13] | Jarvis, J. M.; McDowell, E. D., Optimal product layout in an order picking warehouse, IIE Transactions, 23, 93-102 (1991) |
| [14] | de Koster, R.; Le-Duc, T.; Roodbergen, K. J., Design and control of warehouse order picking: A literature review, European Journal of Operational Research, 182, 481-501 (2007) · Zbl 1121.90385 |
| [15] | de Koster, R.; van der Poort, E., Routing orderpickers in a warehouse: A comparison between optimal and heuristic solutions, IIE Transactions, 30, 469-480 (1998) |
| [16] | Lenstra, J. K.; Rinnooy Kan, A. H.G., Some simple applications of the travelling salesman problem, Operational Research Quarterly, 26, 717-733 (1975) · Zbl 0308.90044 |
| [17] | Letchford, A. N.; Nasiri, S. D.; Theis, D. O., Compact formulations of the Steiner traveling salesman problem and related problems, European Journal of Operational Research, 228, 83-92 (2013) · Zbl 1332.90329 |
| [18] | Matai, R.; Singh, S. P.; Mittal, M. L., Traveling salesman problem: An overview of applications, formulations and solution approaches, (Davendra, D., Traveling salesman problem: Theory and applications (2010), InTech), 1-24 · Zbl 1229.90004 |
| [19] | Miller, C. E.; Tucker, A. W.; Zemlin, R. A., Integer programming formulations and traveling salesman problems, Journal of the Association for Computing Machinery, 7, 326-329 (1960) · Zbl 0100.15101 |
| [20] | Öncan, T.; Altinel, K.; Laporte, G., A comparative analysis of several asymmetric traveling salesman problem formulations, Computers & Operations Research, 36, 637-654 (2009) · Zbl 1179.90321 |
| [21] | Padberg, M.; Sung, T., An analytical comparison of different formulations of the traveling salesman problem, Mathematical Programming, 52, 315-357 (1991) · Zbl 0770.90075 |
| [22] | Petersen, C. G.; Schmenner, R. W., An evaluation of routing and volume-based storage policies in an order picking operation, Decision Science, 30, 481-501 (1999) |
| [23] | Ratliff, H. D.; Rosenthal, A. R., Order-picking in a rectangular warehouse: A solvable case of the traveling salesman problem, Operations Research, 31, 507-521 (1983) · Zbl 0523.90060 |
| [24] | Rego, C.; Gamboa, D.; Glover, F.; Osterman, C., Traveling salesman problem heuristics: Leading methods, implementations and latest advances, European Journal of Operational Research, 211, 427-441 (2011) · Zbl 1237.90209 |
| [25] | Roodbergen, K. J., Layout and routing methods for warehouses (2001), Trial: Trial Rotterdam |
| [26] | Roodbergen, K. J.; de Koster, R., Routing order pickers in a warehouse with a middle aisle, European Journal of Operational Research, 133, 32-43 (2001) · Zbl 0989.90025 |
| [27] | Roodbergen, K. J.; de Koster, R., Routing methods for warehouses with multiple cross aisles, International Journal of Production Research, 39, 1865-1883 (2001) · Zbl 1060.90519 |
| [28] | Tompkins, J. A.; White, J. A.; Bozer, Y. A.; Tanchoco, J. M.A., Facilities planning (2010), John Wiley & Sons: John Wiley & Sons New Jersey |
| [29] | Wäscher, G., Order picking: A survey of planning problems and methods, (Dyckhoff, H.; Lackes, R.; Reese, J., Supply chain management and reverse logistics (2004), Springer: Springer Berlin), 324-370 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
