A Sequential Workforce Scheduling and Routing Problem for the Retail Industry: A Case Study

Abstract

This study investigated the operational workforce scheduling and routing problem of a leading international retail company. Currently, the company plans to launch a new product into the Turkish market, which will be used in all its retail stores across the country. For the best marketing outcome, branding of all retail stores needs to be renewed by an outsourced workforce with a minimum of cost and time. We framed this as a workforce scheduling and routing optimization problem. Therefore, a two-stage solution was proposed. The retail stores were partitioned into disjoint regions in the first stage, and the schedules were optimized in the second stage. We employed the k-means clustering algorithm for constructing these regions. Two different heuristic approaches were applied to solve regional scheduling in the second stage of the algorithm since the resulting scheduling problem is NP-hard. Finally, a computational analysis was performed with real data and the results are discussed.

Keywords

• Workforce Scheduling and Routing
• Integer Programming
• Heuristics

References

1. Algethami, H., & Landa-Silva, D. (2015). A study of genetic operators for the workforce scheduling and routing problem. In Proceedings of the 11th Metaheuristics International Conference (MIC 2015, pp. 1-11). Agadir; Morocco.
2. Allaoua, H., Borne, S., Létocart, L., & Calvo, R. W. (2013). A matheuristic approach for solving a home health care problem. Electronic Notes in Discrete Mathematics, 41, 471-478. https://doi.org/10.1016/j. endm.2013.05.127
3. Bektas, T. (2006). The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, 34(3), 209-219. https://doi.org/10.1016/j.omega.2004.10.004
4. Berkhout, C. (2015). Retail marketing strategy: Delivering shopper delight. Kogan Page Publishers, USA.
5. Bredström, D., & Rönnqvist, M. (2008). Combined vehicle routing and scheduling with temporal precedence and synchronization constraints. European Journal of Operational Research, 191(1), 19-31. https://doi. org/10.1016/j.ejor.2007.07.033
6. Castillo-Salazar, J. A., Landa-Silva, D., & Qu, R. (2016). Workforce scheduling and routing problems: literature survey and computational study. Annals of Operations Research, 239(1), 39-67. https://doi. org/10.1007/s10479-014-1687-2
7. Chandran, N., Narendran, T. T., & Ganesh, K. (2006). A clustering approach to solve the multiple traveling salesmen problem. International Journal of Industrial and Systems Engineering, 1(3), 372-387. https:// doi.org/10.1504/IJISE.2006.009794
8. Davendra, D. (Ed.). (2010). Traveling salesman problem: Theory and applications. BoD–Books on Demand.

9. Friske, M. W., Buriol, L. S., & Camponogara, E. (2022). A relax-and-fix and fix-and-optimize algorithm for a Maritime Inventory Routing Problem. Computers & Operations Research, 137, 105520. https:// doi.org/10.1016/j.cor.2021.105520
10. Gilbert, K. C., & Hofstra, R. B. (1992). A new multiperiod multiple traveling salesman problem with heuristic and application to a scheduling problem. Decision Sciences, 23(1), 250-259. https://doi. org/10.1111/j.1540-5915.1992.tb00387.x
11. Goel, V., Furman, K. C., Song, J. H., & El-Bakry, A. S. (2012). Large neighborhood search for LNG inventory routing. Journal of Heuristics, 18(6), 821-848. https://doi.org/10.1007/s10732-012-9206-6
12. Ip, W. H., Wang, D., & Cho, V. (2012). Aircraft ground service scheduling problems and their genetic algorithm with hybrid assignment and sequence encoding scheme. IEEE Systems Journal, 7(4), 649-657. https:// doi.org/10.1109/JSYST.2012.2196229
13. Johnson, D. S., & McGeoch, L. A. (2018). The traveling salesman problem: a case study. In E. Aarts & J. Lenstra (Ed.), Local Search in Combinatorial Optimization (pp. 215-310). Princeton: Princeton University Press, USA. https://doi.org/10.1515/9780691187563-011
14. Kara, I., & Bektas, T. (2006). Integer linear programming formulations of multiple salesman problems and its variations. European Journal of Operational Research, 174(3), 1449-1458. https://doi.org/10.1016/j. ejor.2005.03.008
15. Kovacs, A. A., Parragh, S. N., Doerner, K. F., & Hartl, R. F. (2012). Adaptive large neighborhood search for service technician routing and scheduling problems. Journal of Scheduling, 15(5), 579-600. https:// doi.org/10.1007/s10951-011-0246-9
16. Liu, X., Luo, M., & Zhao, Y. (2019). Integrating route optimisation with vehicle and unloading dock scheduling in LCL cargo collection. International Journal of Shipping and Transport Logistics, 11(2-3), 262-280. https://doi.org/10.1504/IJSTL.2019.099273
17. Lloyd, S. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129-137. https://doi.org/10.1109/TIT.1982.1056489
18. MacKay, D. (2003). An example inference task: Clustering. Information Theory, Inference and Learning Algorithms, 20, 284-292.
19. Mankowska, D. S., Meisel, F., & Bierwirth, C. (2014). The home health care routing and scheduling problem with interdependent services. Health Care Management Science, 17(1), 15-30. https://doi.org/10.1007/ s10729-013-9243-1
20. Masutti, T. A., & de Castro, L. N. (2008, July). A Clustering Approach Based on Artificial Neural Networks to Solve Routing Problems. In 2008 11th IEEE International Conference on Computational Science and Engineering (pp. 285-292). IEEE. https://doi.org/10.1109/CSE.2008.58
21. Misir, M., Smet, P., Verbeeck, K., & Vanden Berghe, G. (2011). Security personnel routing and rostering: a hyper-heuristic approach. In Proceedings of the 3rd International Conference on Applied Operational Research (Vol. 3, pp. 193-205). Tadbir; Canada.
22. Necula, R., Raschip, M., & Breaban, M. (2018). Balancing the subtours for multiple TSP approached with ACS: Clustering-based approaches vs. MinMax formulation. In EVOLVE-A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation VI (pp. 210-223). Springer, Cham. https://doi. org/10.1007/978-3-319-69710-9_15
23. Nuriyev, U., Ugurlu, O., & Nuriyeva, F. (2018). A Simple Algorithm for The Multi-Depot Multiple Traveling Salesman Problem. In. Proceedings of the 6th International Conference on Control and Optimization with Industrial Applications (Vol. 2, pp. 235-237). Baku; Azerbaijan.
24. Pratap, S., Zhang, M., Shen, C. L., & Huang, G. Q. (2019). A multi-objective approach to analyse the effect of fuel consumption on ship routing and scheduling problem. International Journal of Shipping and Transport Logistics, 11(2-3), 161-175. https://doi.org/10.1504/IJSTL.2019.099270
25. Song, J. H., & Furman, K. C. (2013). A maritime inventory routing problem: Practical approach. Computers & Operations Research, 40(3), 657-665. https://doi.org/10.1016/j.cor.2010.10.031
26. Uggen, K. T., Fodstad, M., & Nørstebø, V. S. (2013). Using and extending fix-and-relax to solve maritime inventory routing problems. TOP, 21(2), 355-377. https://doi.org/10.1007/s11750-011-0174-z
27. Ugurlu, O. (2018). Rotalama problemleri için algoritmik yaklaşımlar. Doktora Tezi, Ege Üniversitesi, Fen Bilimleri Enstitüsü, İzmir.
28. Venkateswara Reddy, P., Kumar, A. C. S., Bhat, M. S., Dhanalakshmi, R., & Parthiban, P. (2010). Balanced centroids (BC) k-means clustering algorithm to transform MTSP to TSP. International Journal of Logistics Economics and Globalisation, 2(3), 187-197. https://doi.org/10.1504/IJLEG.2010.036299