Abstract
This paper presents a method to solve the periodic vehicle routing problem with service frequency. The problem consists in finding a set of paths for a crew of vehicles to deliver products or services to a set of customers in a discrete planning horizon subject to constraints as vehicle capacity, distance-time constraints, time windows, and the variable demand that implies a not defined frequency. Our method solves iteratively two mixed integer programming models. The first one assigns customers to be visited on the planning horizon. The second finds paths to visit the customers for each period. However, in case of non-feasibility a set of rules modify the allocation and the process starts again until the solution is obtained. We present an example to illustrate the method.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Pinedo, M.L.: Planning and Scheduling in Manufacturing and Services. Springer, New York (2009). https://doi.org/10.1007/978-1-4419-0910-7
Böttcher, M., Fähnrich, K.-P.: Service systems modeling: concepts, formalized meta-model and technical concretion. In: Demirkan, H., Spohrer, J.C., Krishna, V. (eds.) The Science of Service Systems, pp. 131–149. Springer, US (2011). https://doi.org/10.1007/978-1-4419-8270-4_8
Spohrer, J., Maglio, P.P., Bailey, J., Gruhl, D., Spohrer, J., Maglio, P.P., Bailey, J., Gruhl, D.: Steps toward a science of service systems. In: The 2007 IEEE International Conference on Information Reuse, pp. 71–77. IEEE Computer Society (2007)
Demirkan, H., Spohrer, J.C., Krishna, V.: Introduction of the science of service systems. In: Demirkan, H., Spohrer, J.C., Krishna, V. (eds.) The Science of Service Systems, pp. 1–11. Springer, Boston (2011). https://doi.org/10.1007/978-1-4419-8270-4_1
López-Santana, E.R., Méndez-Giraldo, G.A.: A knowledge-based expert system for scheduling in services systems. In: Figueroa-García, J.C., López-Santana, E.R., Ferro-Escobar, R. (eds.) WEA 2016. CCIS, vol. 657, pp. 212–224. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-50880-1_19
Beltrami, E.J., Bodin, L.D.: Networks and vehicle routing for municipal waste collection. Networks 4, 65–94 (1974)
Russell, R., Igo, W.: An assignment routing problem. Networks 9, 1–17 (1979)
Christofides, N., Beasley, J.E.: The period routing problem. Networks 14, 237–256 (1984)
Tan, C.C.R., Beasley, J.E.: A heuristic algorithm for the period vehicle routing problem. Omega 12, 497–504 (1984)
Fisher, M.L., Jaikumar, R.: A generalized assignment heuristic for vehicle routing. Networks 11, 109–124 (1981)
Drummond, L.M.A., Ochi, L.S., Vianna, D.S.: An asynchronous parallel metaheuristic for the period vehicle routing problem. Future Gener. Comput. Syst. 17, 379–386 (2001)
Mourgaya, M., Vanderbeck, F.: Column generation based heuristic for tactical planning in multi-period vehicle routing. Eur. J. Oper. Res. 183, 1028–1041 (2007)
Cordeau, J.-F., Gendreau, M., Laporte, G.: A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks 30, 105–119 (1997)
Hadjiconstantinou, E., Baldacci, R.: A multi-depot period vehicle routing problem arising in the utilities sector. J. Oper. Res. Soc. 49, 1239 (1998)
Cordeau, J.-F., Laporte, G., Mercier, A.: A unified tabu search heuristic for vehicle routing problems with time windows. J. Oper. Res. Soc. 52, 928–936 (2001)
Francis, P., Smilowitz, K., Tzur, M.: The period vehicle routing problem with service choice. Transp. Sci. 40, 439–454 (2006)
Rodriguez, S., Correa, D., López-Santana, E.: An alternative iterative method to periodic vehicle routing problem. In: Cetinkaya, S., Ryan, J.K. (eds.) IIE Annual Conference and Expo 2015, pp. 2001–2010 (2015)
López-Santana, E.R., Romero Carvajal, J.: A hybrid column generation and clustering approach to the school bus routing problem with time windows. Ingeniería 20, 111–127 (2015)
Patiño Chirva, J.A., Daza Cruz, Y.X., López-Santana, E.R.: A hybrid mixed-integer optimization and clustering approach to selective collection services problem of domestic solid waste. Ingeniería 21, 235–247 (2016)
Acknowledgments
We thank Fair Isaac Corporation (FICO) for providing us with Xpress-MP licenses under the Academic Partner Program subscribed with Universidad Distrital Francisco Jose de Caldas (Colombia). We thanks to Daniel Correa and Sebastian Rodriguez, students of Universidad Distrital for your help with the programming of the models.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
López-Santana, E., Franco, C., Giraldo, G.M. (2018). A Two-Phase Method to Periodic Vehicle Routing Problem with Variable Service Frequency. In: Gervasi, O., et al. Computational Science and Its Applications – ICCSA 2018. ICCSA 2018. Lecture Notes in Computer Science(), vol 10961. Springer, Cham. https://doi.org/10.1007/978-3-319-95165-2_37
Download citation
DOI: https://doi.org/10.1007/978-3-319-95165-2_37
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-95164-5
Online ISBN: 978-3-319-95165-2
eBook Packages: Computer ScienceComputer Science (R0)