An Assignment Heuristicfor Time-Dependent Periodic Routing Problemswith Complex Constraints
DOI:
https://doi.org/10.7494/dmms.2020.14.2.2690Keywords:
mobile personnel management, personnel allocation, vehicle routing, clustering, time dependent, time windows, periodicAbstract
Periodic routing and scheduling is of the utmost importance in many industries with mobile personnel working in the field: sales representatives, service technicians, suppliers, etc. In many cases, the long-term stability of the customer to salesman assignment is required, leading to the decomposition of the major problem into single salesman subproblems. The paper addresses the assignment of customers to salesmen for the future services performed in a periodic fashion. It can be seen as the decomposition phase of the periodic vehicle routing problem PVRP into a number of Periodic Traveling Salesman Problems (PTSP). The proposed algorithm seeks the best assignment by taking into account diverse system requirements, constraints and expected operational costs including time windows, time-dependent travel times and costs, and labor laws.
References
Albiach J., Sanchis J.M. & Soler D. (2008). An asymmetric TSP with time windows and with time-dependent travel times and costs: An exact solution through a graph transformation. European Journal of Operational Research, 189(3), pp. 789–802. DOI: https://doi.org/10.1016/j.ejor.2006.09.099.
Ascheuer N., Fischetti M. & Grötschel M. (2000). A polyhedral study of the asymmetric traveling salesman problem with time windows. Networks, 36(2), pp. 69–79. DOI: https://doi.org/10.1002/1097-0037(200009)36:2<69::AID-NET1>3.0.CO;2-Q.
Ascheuer N., Fischetti M. & Grötschel M. (2001). Solving the asymmetric travelling salesman problem with time windows by branch-and-cut. Mathematical Programming, 90, pp. 475–506. DOI: https://doi.org/10.1007/PL00011432.
Bostel N., Dejax P., Guez P. & Tricoire F. (2008). Multiperiod planning and routing on a rolling horizon for field force optimization logistics. In: Golden B., Raghavan S. & Wasil E. (Eds.), The Vehicle Routing Problem: Latest Advances and New Challenges. Operations Research/Computer Science Interfaces, 43, pp. 503–525. Boston, MA: Springer. DOI: https://doi.org/10.1007/978-0-387-77778-8_23.
Bramel J. & Simchi-Levi D. (1995). A location based heuristic for general routing problems. Operations Research, 43(4), pp. 649–660. DOI: https://doi.org/10.1287/opre.43.4.649.
Cacchiani V., Hemmelmayr V.C. & Tricoire F. (2014). A set-covering based heuristic algorithm for the periodic vehicle routing problem. Discrete Applied Mathematics, 163(1), pp. 53–64. DOI: https://doi.org/10.1016/j.dam.2012.08.032.
Cordeau J.-F., Laporte G. & Mercier A. (2001). A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society, 52(8), pp. 928–936. DOI: https://doi.org/10.1057/palgrave.jors.2601163.
Fisher M.L. & Jaikumar R. (1981). A generalized assignment heuristic for vehicle routing. Networks, 11(2), pp. 109–124. DOI: https://doi.org/10.1002/net.3230110205.
Focacci F., Lodi A. & Milano M. (2002). A hybrid exact algorithm for the TSPTW. INFORMS Journal on Computing, 14(4), pp. 403–417. DOI: https://doi.org/10.1287/ijoc.14.4.403.2827.
Francis P.M., Smilowitz K.R. & Tzur M. (2008). The period vehicle routing problem and its extensions. In: Golden B., Raghavan S. & Wasil E. (Eds.), The Vehicle Routing Problem: Latest Advances and New Challenges. Operations Research/Computer Science Interfaces, 43, pp. 73–102. Boston, MA: Springer. DOI: https://doi.org/10.1007/978-0-387-77778-8_4.
Gendreau M., Hertz A., Laporte G. & Stan M. (1998). A generalized insertion heuristic for the traveling salesman problem with time windows. Operations Research, 46(3), pp. 330–335. DOI: https://doi.org/10.1287/opre.46.3.330.
Hurkała J. (2015). Time-dependent traveling salesman problem with multiple time windows. Annals of Computer Science and Information Systems, 6, pp. 71–78. DOI: https://doi.org/10.15439/2015F311.
de Jong C., Kant G. & van Vliet A. (1996). On Finding Minimal Route Duration in the Vehicle Routing Problem with Multiple Time Windows. Technical report. Utrecht: Department of Computer Science, Utrecht University.
MacQueen J.B. (1967). Some methods for classification and analysis of multivariate observations. In: Le Cam L.M. & Neyman J. (Eds.), Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1, pp. 281–297. Berkeley: University of California Press.
Michallet J., Prins C., Amodeo L., Yalaoui F. & Vitry G. (2014). Multi-start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services. Computers & Operations Research, 41, pp. 196–207. DOI: https://doi.org/10.1016/j.cor.2013.07.025.
Norouzi N., Sadegh-Amalnick M. & Alinaghiyan M. (2015). Evaluating of the particle swarm optimization in a periodic vehicle routing problem. Measurement, 62, pp. 162–169. DOI: https://doi.org/10.1016/j.measurement.2014.10.024.
Ogryczak W., Śliwiński T., Hurkała J., Kaleta M., Pałka P. & Kozłowski B. (2018). Large-scale periodic routing problems for supporting planning of mobile personnel tasks. In: Atanassov K.T. et al. (Eds.), Uncertainty and Imprecision in Decision Making and Decision Support: Cross-Fertilization, New Models and Applications. Advances in Intelligent Systems and Computing, 559, pp. 205–216. Cham: Springer. DOI: https://doi.org/10.1007/978-3-319-65545-1_19.
Peng F., Ouyang Y. & Somani K. (2013). Optimal routing and scheduling of periodic inspections in large-scale railroad networks. Journal of Rail Transport Planning & Management, 3(4), pp. 163–171. DOI: https://doi.org/10.1016/j.jrtpm.2014.02.003.
Renaud J., Boctor F.F. & Laporte G. (1996). An improved petal heuristic for the vehicle routeing problem. Journal of the Operational Research Society, 47(2), pp. 329–336. DOI: https://doi.org/10.1057/jors.1996.29.
Ryan D.M., Hjorring C. & Glover F. (1993). Extensions of the petal method for vehicle routeing. Journal of the Operational Research Society, 44(3), pp. 289–296. DOI: https://doi.org/10.1057/jors.1993.54.
Savelsbergh M.W.P. (1992). The vehicle routing problem with time windows: Minimizing route duration. ORSA Journal on Computing, 4(2), pp. 146–154. DOI: https://doi.org/10.1287/ijoc.4.2.146.
Tricoire F., Romauch M., Doerner K.F. & Hartl R.F. (2010). Heuristics for the multi-period orienteering problem with multiple time windows. Computers & Operations Research, 37(2), pp. 351–367. DOI: https://doi.org/10.1016/j.cor.2009.05.012.
