1. Proceedings
  2. I3M
  3. 2019
  4. HMS
  5. 10.46354/i3m.2019.hms.005

An algorithm for the capacitated vehicle routing problem for picking application in manual warehouses

  • a Eleonora Bottani  , 
  • b Giorgia Casella  , 
  • c Caterina Caccia  , 
  • d Roberto Montanari 
  • a,b,c,d Department of Engineering and Architecture, University of Parma, viale delle Scienze 181/A, 43124 Parma, Italy
Cite as
Bottani E., Casella G., Caccia C., Montanari R. (2019). An algorithm for the capacitated vehicle routing problem for picking application in manual warehouses. Proceedings of the 21st International Conference on Harbor, Maritime and Multimodal Logistic Modeling & Simulation (HMS 2019), pp. 35-40. DOI: https://doi.org/10.46354/i3m.2019.hms.005

Abstract

Given that warehouses play a central role in modern supply chains, this study proposes the application of an algorithm for the capacitated vehicle routing problem (CVRP) based on the two-index vehicle flow formulation developed by Baldacci, Hadjiconstantinou, and Mingozzi (2004) for picking purposes in manual warehouses. The study of Theys et al. (2010) is first used to represent the warehouse using a Steiner traveling salesman problem (TSP). Then, a calculation of the picking tour’s length is obtained applying the Manhattan distance. Finally, the algorithm for the CVRP is solved through a cutting plane with the addition of termination criteria related to the capacity of picker. The study analyzes four different warehouse configurations, processing five picking list each. The analysis is carried out exploiting the commercial software MATLAB®, to determine the solution that minimize distance of the order picking tour. The results obtained in MATLAB® show the effectiveness of the chosen algorithm applied to the context of manual order picking.

References

  1. Baldacci R., Hadjiconstantinou E., Mingozzi A. 2004. An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Operation Research,
    52(5), 723-738.
  2. Bottani E., Montanari R., Rinaldi M. 2019. Development and testing of software tool for
    warehouse design and picking optimisation. International Journal of Management and
    Decision Making, 18(2), 119-150.
  3. Cheng C.-Y., Chen Y.-Y., Chen T.-L., Jung-Woon Yoo J. 2015. Using a hybrid approach based on the particle swarm optimization and ant colony optimization to solve a joint order batching and picker routing problem. International Journal of Production Economics, 170, 805-814.
  4. Daniels R., Rummel J., Schantz R. 1998. A model for warehouse order picking. European Journal of Operational Research, 105(1), 1-17.
  5. De Koster R., Le-Duc T., Zaerpour N. 2012. Determining the number of zones in a pickand- sort order picking system. International Journal of Production Research, 50(3), 757- 771.
  6. De Santis R., Montanari R., Vignali G., Bottani E. 2018. An adapted ant colony optimization
    algorithm for the minimization of the travel distance of pickers in manual warehouses. European Journal of Operational Research,
    267(1), 120-137.
  7. Dukic G., Oluic C. 2007. Order-picking methods: Improving order-picking efficiency. International Journal of Logistics Systems and Management, 3(4), 451-460.
  8. Ferrari E., Gamberi M., Mancini R., Pareschi A., Persona A., Regattieri A. 2003. The optimization of a picker to product Order Picking System: a supporting decision tool based on a multi-parametric simulation approach. Proceedings of the 21st international conference of the system dynamics society. July 20-24, New York City (USA).
  9. Gademann N., van de Velde S. 2005. Order batching to minimize total travel time in a parallel-aisle warehouse. IIE Transactions (Institute of Industrial Engineers), 37(1), 63-75.
  10. Grosse E., Glock C., Ballester-Ripoll R. 2014. A simulated annealing approach for the joint order batching and order picker routing problem with weight restrictions. International Journal of Operations and Quantitative Management, 20(2), 65-83.
  11. Hsieh L.-F., Tsai L. 2006. The optimum design of a warehouse system on order picking efficiency. International Journal of Advanced Manufacturing Technology, 28(5-6), 626-637
  12. Karasek J. 2013. An overview of warehouse optimization. International Journal of
    Advances in Telecommunications, Electrotechnics, Signals and Systems, 2(3).
  13. Muter I., Öncan T. 2015. An exact solution approach for the order batching problem. IIE Transactions (Institute of Industrial Engineers), 47(7), 728-738.
  14. Theys C., Bräysy O., Dullaert W., Raa B. 2010. Using a TSP heuristic for routing order pickers in warehouses. European Journal of Operational Research, 200(3), 755-763.
  15. Žulj I., Glock C., Grosse E., Schneider M. 2018. Picker routing and storage-assignment strategies for precedence-constrained order picking. Computers and Industrial Engineering, 123, 338-347.