An Assignment Heuristicfor Time-Dependent Periodic Routing Problemswith Complex Constraints

• Autorzy: Tomasz Śliwiński
• Języki publikacji: EN

Abstrakty

EN

Periodic routing and scheduling is of the utmost importance in many industrieswith 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. Thepaper addresses the assignment of customers to salesmen for the future services performed ina periodic fashion. It can be seen as the decomposition phase of the periodic vehicle routingproblem PVRP into a number of Periodic Traveling Salesman Problems (PTSP). The proposedalgorithm seeks the best assignment by taking into account diverse system requirements,constraints and expected operational costs including time windows, time-dependent traveltimes and costs, and labor laws.(original abstract)

Słowa kluczowe

EN

Trade; Heuristics; m-commerce; Algorithms

PL

Handel; Heurystyka; Handel mobilny; Algorytmy

• Czasopismo: Decision Making in Manufacturing and Services
• Rocznik: 2020
• Tom: 14
• Numer: nr 2
• Strony: 181--192

Twórcy

autor

Tomasz Śliwiński

• Warsaw University of Technology

Bibliografia

• 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.
• Ascheuer, N., Fischetti, M., Groetschel, M., 2000. A polyhedral study of the asymmetrictraveling salesman problem with time windows. Networks, 36, pp. 69-79.
• 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.
• 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.
• Bramel, J., Simchi-Levi, D., 1995. A location based heuristic for general routing problems. Operations Research, 43(4), pp. 649-660.
• 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.
• 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.
• Fisher, M., Jaikumar, R., 1981. A generalized assignment heuristic for vehicle routing. Networks, 11(2), pp. 109-124.
• Focacci, F., Lodi, A., Milano, M., 2002. A hybrid exact algorithm for the tsptw. Informs Journal on Computing, 14(4), pp. 403-417.
• 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.
• 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.
• 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., 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.
• 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.
• 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.
• Norouzi, N., Sadegh-Amalnick, M., Alinaghiyan, M., 2015. Evaluating of the particle swarmoptimization in a periodic vehicle routing problem. Measurement, 62, pp. 162-169.
• 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.
• 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.
• 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.
• 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.
• Savelsbergh, M., 1992. The vehicle routing problem with time windows: Minimizing routeduration. ORSA Journal on Computing, 4(2), pp. 146-154.
• Tricoire, F., Romauch, M., Doerner, K.F., Hartl, R.F, 2010. Heuristics for the multiperiod orienteering problem with multiple time windows. Computers&Operations Research,37(2), pp. 351-367.

Identyfikatory

DOI

10.7494/dmms.2020.14.2.2690181