Clustering heuristic for time-dependent periodic routing problems with 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 utmost importance in many industries with mobile personnel working in the field: sales representatives, service technicians, suppliers, etc. The resulting optimization problems are of large scale and complexity, mostly due to discrete, combinatorial nature of the systems and due to complicated, nonuniform constraints. In many cases the long-term stability of the customer to personnel allocation is required, leading to the decomposition of the major problem into single employee subproblems.The paper deals with building clusters of customers visited by a single salesperson. The procedure takes into account diverse system requirements and constraints, possible traveling schedules and expected operational costs. The difficulty of the problem lies in its large scale and constraints complexity as well as in troublesome objective evaluation for the given solution. The general solution concept is presented. Its usefulness is supported by the results of the computational experiments.
References
Albiach, J., Sanchis, J., and Soler, D.M. (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, 789-802.
Ascheuer, N., Fischetti, M. and Groetschel, M. (2000). A polyhedral study of the asymmetric traveling salesman problem with time windows. Networks, 36, 69-79.
Ascheuer, N., Fischetti, M., and Groetschel, M (2001). Solving the asymmetric travelling salesman problem with time windows by branch-and-cut. Mathematical Programming Series A, 90, 475-506.
Bramel, J. and Simchi-Levi, D. (1995). A location based heuristic for general routing problems. Operations Research, 43(4), 649-660.
Fisher, M.L., and Jaikumar, R. (1981). A generalized assignment heuristic for vehicle routing. Networks, 11(2), 109-124.
Focacci, F., Lodi, A. and Milano, M. (2002). A hybrid exact algorithm for the tsptw. INFORMS Journal on Computing, 14(4), 403-417.
Gendreau, M., Hertz, A., Laporte, G. and Stan, M. (1998). A generalized insertion heuristic for the traveling salesman problem with time windows. Operations Research, 46(3), 330-335.
Hurkała, J. (2015). Minimum route duration algorithm for traveling salesman. Vehicle Routing and Logistics Optimization, June 8-10, Vienna, Austria.
Hurkała, J. (2015) Time-dependent traveling salesman problem with multiple time windows. Annals of Computer Science and Information Systems, 6, 71-78.
Jong, C., Kant, G. and van Vliet, A. (1996). On finding minimal route duration in the vehicle routing problem with multiple time windows. Tech. Rep.
MacQueen. J.B. (1967). Some methods for classication and analysis of multi-variate observation. In Proceedings of Fifth Berkeley Symposium on Mathematical Statistics and Probability, volume 1, pages 281-297. University of California Press.
Ogryczak, W., Śliwiński, T., Hurkała, J. Kaleta. M., Kozłowski, B. and Palka, P. (2016). Planning and management of mobile personnel tasks with time-dependent routing problems. In Proceedings of the BOS 2016 conference [in press].
Reanaud, J., Boctor, F.F., and Laporte, G. (1996). An improved petal heuristic for the vehicle routing problem. Journal of Operational Research Society, 47, 329-336.
Ryan, M., Hjorring, D.C. and Glover, F. (1993). Extensions of the petal method for vehicle routing. Journal of Operational Research Society, 44, 289-296.
Savelsbergh, M.W.P. (1992). The vehicle routing problem with time windows: Minimizing route duration. ORSA Journal on Computing, 4(2):146-154.
Tricoire, F., Romauch, M., Doerner, K.F. and Hartl, R.F.(2010). Heuristics for the multi-period orienteering problem with multiple time windows. Computers & Operations Research, 37, 351-367.
Downloads
Published
How to Cite
Issue
Section
License
Remeber to prepeare, sign and scan copyright statement
The content of the journal is freely available according to the Creative Commons License Attribution 4.0 International (CC BY 4.0)
Accepted 2020-12-14
Published 2021-01-27
