Clustering heuristic for time-dependent periodic routing problems with complex constraints

• Autorzy: Śliwiński Tomasz

Identyfikatory

DOI

10.7494/dmms.2020.14.2.2690

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

periodic vehicle routing; time windows; assignment problem

PL

okresowe wyznaczanie tras pojazdów; okna czasowe; problem przydziału

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Decision Making in Manufacturing and Services
• Rocznik: 2020
• Tom: Vol. 14, no. 2
• Strony: 181--192
• Opis fizyczny: Bibliogr. 22 poz., rys., tab.

Twórcy

autor

Śliwiński Tomasz

• Warsaw University of Technology, Institute of Control and Computation Engineering, Warsaw,Poland

Bibliografia

• [1] Albiach, J., Sanchis, J.,M., Soler, D., 2008. An asymmetric tsp with time windows and withtime-dependent travel times and costs: An exact solution through a graph transformation. European Journal of Operational Research, 189(3), pp. 789–802.
• [2] Ascheuer, N., Fischetti, M., Groetschel, M., 2000. A polyhedral study of the asymmetrictraveling salesman problem with time windows. Networks, 36, pp. 69–79.
• [3] Ascheuer, N., Fischetti, M., Groetschel, M., 2001. Solving the asymmetric travelling salesmanproblem with time windows by branch-and-cut. Mathematical Programming Series A,90, pp. 475–506.
• [4] Bostel, N., Dejax, P., Guez, P., Tricoire, F., 2008. Multiperiod Planning and Routing ona Rolling Horizon for Field Force Optimization Logistics. In: Golden, B., Raghavan, S.,Wasil, E. (eds.),The vehicle routing problem: latest advances and new challenges. Springer,Berlin, pp. 503–527.
• [5] Bramel, J., Simchi-Levi, D., 1995. A location based heuristic for general routing problems.Operations Research, 43(4), pp. 649–660.
• [6] Cacchiani, V., Hemmelmayr, V.C., Tricoire, F., 2014. A set-covering based heuristic algorithmfor the periodic vehicle routing problem. Discrete Applied Mathematics, 163(1), pp. 53–64.
• [7] Cordeau, J.-F., Laporte, G., Mercier, A., 2001. A unified tabu search heuristic for vehiclerouting problems with time windows. Journal of the Operational Research Society, 52(8), pp. 928–936.
• [8] Fisher, M., Jaikumar, R., 1981. A generalized assignment heuristic for vehicle routing. Networks, 11(2), pp. 109–124.
• [9] Focacci, F., Lodi, A., Milano, M., 2002. A hybrid exact algorithm for the tsptw. INFORMS Journal on Computing, 14(4), pp. 403–417.
• [10] 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. Springer, Berlin, pp. 73–102.
• [11] Gendreau, M., Hertz, A., Laporte, G., Stan, M., 1998. A generalized insertion heuristic for thetraveling salesman problem with time windows.Operations Research, 46(3), pp. 330–335.
• [12] Hurkała, J., 2015. Time-dependent traveling salesman problem with multiple time windows. Annals of Computer Science and Information Systems, 6, 71–78.
• [13] Jong, C., Kant, G., Vliet, A., van, 1996. On finding minimal route duration in the vehiclerouting problem with multiple time windows. Technical Report, Department of Computer Science, Ultrecht University, The Netherlands.
• [14] MacQueen, J.B., 1967. Some methods for classification and analysis of multivariate observation.Proceedings of Fifth Berkeley Symposium on Mathematical Statistics and Probability,Vol. 1. University of California Press, Berkeley, pp. 281–297.
• [15] Michallet, J., Prins, Ch., Amodeo, L., Yalaoui, F., Vitry, G., 2014. Multi-start iterated localsearch for the periodic vehicle routing problem with time windows and time spreadconstraints on services.Computers&Operations Research, 41, pp. 196–207.
• [16] Norouzi, N., Sadegh-Amalnick, M., Alinaghiyan, M., 2015. Evaluating of the particle swarmoptimization in a periodic vehicle routing problem. Measurement, 62, pp. 162–169.
• [17] Ogryczak, W., Sliwiński, T., Hurkała, J., Kaleta, M., Kozłowski, B., Pałka, P., 2018. Large--Scale Periodic Routing Problems for Supporting Planning of Mobile Personnel Tasks. In:Atanassov, K.T., Kacprzyk, J., Kaluszko, A., Krawczak, M., Owsiński, J., Sotirov, S.S.,Sotirova, E., Zadrożny, S. (eds.),Uncertainty and Imprecision in Decision Makingand Decision Support: Cross-Fertilization, New Models and Applications, Springer,pp. 205–216.
• [18] Peng, F., Ouyang, Y., Somani, K., 2013. Optimal routing and scheduling of periodic inspectionsin large-scale railroad networks. Journal of Rail Transport Planning&Management, 3(4), pp. 163–171.
• [19] Reanaud, J., Boctor, F., Laporte, G., 1996. An improved petal heuristic for the vehicle routingproblem. Journal of Operational Research Society, 47(2), pp. 329–336.
• [20] Ryan, D.M., Hjorring, C., Glover, F., 1993. Extensions of the petal method for vehicle routing. Journal of Operational Research Society, 44(3), pp. 289–296.
• [21] Savelsbergh, M., 1992. The vehicle routing problem with time windows: Minimizing routeduration. ORSA Journal on Computing, 4(2), pp. 146–154.
• [22] 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.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021)