Modelo real de planificación y rutas bi-objetivoequilibrio entre costes y preferencias de clientes

  1. Amaya Martínez Puras 1
  2. Joaquín A. Pacheco Bonrostro 1
  1. 1 Universidad de Burgos

    Universidad de Burgos

    Burgos, España


Rect@: Revista Electrónica de Comunicaciones y Trabajos de ASEPUMA

ISSN: 1575-605X

Year of publication: 2016

Volume: 17

Issue: 1

Pages: 57-80

Type: Article

More publications in: Rect@: Revista Electrónica de Comunicaciones y Trabajos de ASEPUMA


SCImago Journal Rank

  • Year 2016
  • SJR Journal Impact: 0.123
  • Best Quartile: Q4
  • Area: Economics and Econometrics Quartile: Q4 Rank in area: 553/690
  • Area: Applied Mathematics Quartile: Q4 Rank in area: 498/586

Índice Dialnet de Revistas

  • Year 2016
  • Journal Impact: 0.100
  • Field: ECONOMÍA Quartile: C3 Rank in field: 89/167


  • Social Sciences: C

Scopus CiteScore

  • Year 2016
  • CiteScore of the Journal : 0.2
  • Area: Economics and Econometrics Percentile: 7
  • Area: Applied Mathematics Percentile: 2


A bi-objective model for the design of daily routes of a company over a planning period is analyzed. This model is motivated by a real design problem routes Chemical Analysis Company over a planning horizon and allocation schedules visit to its customers. The two objectives under consideration are: minimizing transport costs and reducing modifications on current customer schedules. For resolution, it has developed an ad hoc methodology based on tabu search in the context of PVRP (Periodic Vehicle Routing Problem). The solution method was developed by application of combined tabu search with MOAMP (Multiobjective Adaptive Memory Procedure) strategy and the results are compared with an implementation of NSGA-II (Non-dominated Sorting Genetic Algorithm), a well-known approach to multi-objective optimization.

Funding information

Este trabajo ha sido realizado con la ayuda de Fondos FEDER y el Ministerio de Economía y Competitividad (a través de los proyecto ECO2013-47129-C4-3-R y ECO2016-76567-C4-2-R) la Junta de Castilla y León (a través del proyecto BU329U14) y la Junta de Castilla y León y Fondos FEDER (a través del proyecto BU062U16). Estas ayudas son reconocidas y agradecidas.


Bibliographic References

  • Gulczynski D., B. Golden, and E. Wasil. (2011) “The period vehicle routing problem: New heuristics and real-world variants”. Transportation Research Part E 47 (5), pp. 648-668.
  • Alegre J., M. Laguna, and J. Pacheco. (2007). “Optimizing the periodic pick-up of raw materials for a manufacturer of auto parts”. European Journal of Operational Research 179 (3) pp. 736-746.
  • Beltrami, E., and L. D. Bodin. (1974). "Networks and Vehicle Routing for Municipal Waste Collection". Networks 4 (1) pp. 65-94.
  • Clarke G., and J. W. Wright. (1964). “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points”. Operations Research 12 (4) pp. 568-581.
  • Russell R. and W. Igo. (1979). “An assignmente routing problem”. Networks 9 pp. 1-17.
  • Christofides N. and J. Beasley. (1984). “The periodic routing problem”. Networks 14 (2) pp. 237-256.
  • Tan C., and J. Beasley. (1984). “A heuristic algorithm for the periodic vehicle routing problem”. Omega 12 (5) pp. 497-504.
  • Golden B. L., and E. A. Wasil. (1987). “Computerized Vehicle Routing in the Soft Drink Industry”. Operations Research 35 (1) pp. 6-17.
  • Russell R. and D. Gribbin. (1991). “A multiphase approach to the period routing problem”. Networks 21 (7) pp. 747-465.
  • Chao I-M., B. Golden, and E. Wasil. (1995). “An improved heuristic for the period vehicle routing problem”, Networks 26 (1) pp. 25-44.
  • Cordeau J., M. Gendreau, and G. Laporte. (1997). “A tabu search heuristic for periodic and multi depot vehicle routing problems”. Networks 30 (2) pp. 105-119.
  • Drummond L., L. Ochl, and D. Vianna. (2001) “An asynchronous parallel metaheuristic for the periodic vehicle routing problem”. Future Generation Computer Systems 17 (4) pp. 379-386.
  • Bertazzi L., G. Paletta, and M.G. Speranza. (2004). “An improved heuristic for the period traveling salesman problem”. Computers & Operations Research 31 (8) pp. 1215-1222.
  • Blakeley F., B. Bozkaya, B. Cao, W. Hall, and J. Knolmajer. (2003). “Optimizing Periodic Maintenance Operations for Schindler Elevator Corporation”. Interfaces 33 (1) pp. 67-79.
  • Nuortio T., J. Kytöjoki, H. Niska, and O. Bräysy. (2006). “Improved route planning and scheduling of waste collection and transport”. Expert Systems with Applications 30 (2) pp. 223–232.
  • Ronen D., and C. A. Goodhart. (2008). “Tactical store delivery planning”. Journal of the Operational Research Society 59 (8) pp. 1047–1054.
  • Pourghaderi A.R., R. Tavakkoli-Moghaddam, M. Alinaghian, and B. Beheshti-Pour. (2008). “A Simple and Effective heuristic for Periodic Vehicle Routing Problem”. Procedings of the IEEE International Conference on Industrial Engineering and Engineering Management IEEM, Singapore, pp. 133-137.
  • Méndez A., D. Palumbo, M. Carnero, y J. Hernández. (2009). “Algoritmos meméticos aplicados a la resolución de un problema de ruteo de vehículos periódico”. Mecánica Computacional 28 pp. 2675-2685.
  • Hemmelmayr, V. C., K. F. Doerner, and R. F. Hartl. (2009). "A Variable Neighborhood Search Heuristic for Periodic Routing Problems". European Journal of Operational Research 195 (3) pp. 791-802.
  • Peixoto T. M. (2010). “Optimization Techniques for the Mixed Urban Rural Solid Waste Collection Problem”. Tesis de Maestría. Faculdade de Engenharia da Universidade do Porto, Portugal.
  • Pirkwieser S., and G. R. Raidl. (2010). “Multilevel Variable Neighborhood Search for Periodic Routing Problems”. Lecture Notes in Computer Science 6022, pp. 226-238.
  • Yu B. and Z. Z.Yang. (2011). “An ant colony optimization model: The period vehicle routing problem with time windows”. Transportation Research Part E 47 (2) pp. 166-181.
  • Meyer A. (2012) “A constraint programming based approach for planning Milk Runs”. 18 International Conference on Principles and Practice of Constraint, Quebec.
  • Vidal T., T. G. Crainic, M. Gendreau, N. Lahrichi, and W. Rei. (2012). “A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems”. Operations Research 60 (3) pp. 611-624.
  • Rademeyer A. L., and R. Bennetto. (2012). “A rich multi-period delivery vehicle master routing problem. A case study”. Proceedings of the 42 CIE, CIE & SAIIE, Cape Town.
  • Vidal T., T.G. Crainic, M. Gendreau, N. Lahrichi and W. Rei. (2012). “A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems”. Operations Research 60 pp. 611-624.
  • Pacheco J., A. Alvarez, I. García, and F. Angel-Bello. (2012). “Optimizing vehicle routes in a bakery company allowing flexibility in delivery dates”. Journal of Operational Research Society 63 (5) pp. 569–581.
  • Pacheco J., I. García, and A. Alvarez. (2014). “Enhancing Variable Neighborhood Search by Adding Memory: Application to a Real Logistic Problem”. Knowledge-Based Systems 62 pp. 28-37.
  • Hemmelmayr, V. C., K. F. Doerner, R. F. Hartl, and S. Rath. (2013). “A heuristic solution method for node routing based solid waste collection problems”. Journal of Heuristics 19 (2) pp. 129-156.
  • Yao, B., P. Hu, M. Zhang, and S. Wang. (2013). “Artificial bee colony algorithm with scanning strategy for the periodic vehicle routing problem”. Simulation-Transactions of the Society for Modeling and Simulation International 89 (6) pp. 762-770.
  • Cacchiani, V., V. C. Hemmelmayr, and F. Tricoire. (2014). “A set-covering based heuristic algorithm for the periodic vehicle routing problem”. Discrete Applied Mathematics 163 (1) pp. 53-64.
  • Francis P., K. Smilowitz, and M. Tzur. (2006). “The Periodic Vehicle Routing Problem with Service Choice”. Transportation Science 40 (4) pp. 439-454.
  • Baldacci R., E. Bartolini, A. Mingozzi, and A. Valletta. (2011). “An Exact Algorithm for the Period Routing Problem”. Operations Research 59 (1) pp. 228-241.
  • Ngueveu, S. U., C. Prins, and R. W. Calvo. (2013). “New Lower Bounds and Exact Method for the m-PVRP”. Transportation Science 47 (1) pp. 38-52.
  • Campbell, A.M., and J. H. Wilson. (2014). “Forty Years of Periodic Vehicle Routing”. Networks 63 (1) pp. 2-15.
  • Current, J., and M. Marsh. (1993). "Multiobjective Transportation Network Design and Routing Problems: Taxonomy and Annotation". European Journal of Operational Research 65 (1) pp. 4-19.
  • Jozefowiez, N., F. Semet, and E.-G. Talbi. (2008). "Multi-objective vehicle routing problems". European Journal of Operational Research 189 (2) pp. 293-309.
  • Pacheco, J., R. Caballero, M. Laguna, and J. Molina. (2013). "Bi-objective Bus Routing: An Application to School Buses in Rural Areas". Transportation Science 47 (3) pp. 397-411.
  • Gómez, J. R., J. Pacheco, and H. Gonzalo-Orden. (2015). “A Tabu Search method for a Bi-objective Urban Waste Collection Problem”. Computer-Aided Civil and Infrastructure Engineering 30 (1) pp. 36-53.
  • Smilowitz, K., M. Nowak, and T. Jiang. (2013). “Workforce Management in Periodic Delivery Operations”. Transportation Science 47 (2) pp. 214-230.
  • Hsieh, Y. C., P. S. You, P. J. Lee, and Y. C. Lee. (2015). “A novel encoding scheme based evolutionary approach for the bi-objective grid patrol routing problem with multiple vehicles”. Scientia Iranica 22 (4) pp. 1576-1585.
  • Caballero, R., J. Molina, and V. Rodríguez-Uría. (2003). “MOAMP: Programación Multiobjetivo Mediante un Procedimiento de Búsqueda Tabú”. Paper read at II Congreso Español de Metaheurísticas y Algoritmos Evolutivos y Bioinspirados (MAEB), at Gijón.
  • García, I., J. Pacheco, and A. Alvarez. (2013). "Optimizing Routes and Stock". Journal of Heuristics 19 (2) pp. 157-177.
  • Feo T.A., and M.G.C. Resende. (1989). “A probabilistic heuristic for a computationally difficult set covering problem”. Operations Research Letters 8 (2) pp. 67–71.
  • Feo T.A., and M.G.C. Resende. (1995). “Greedy randomized adaptive search procedures”. Journal of Global Optimization 6 (2) pp. 109–133.
  • Glover F. (1989). "Tabu Search — Part I”. ORSA Journal on Computing 1 (3) pp. 190-206.
  • 47. Glover F. (1990). "Tabu Search — Part II”. ORSA Journal on Computing 2 (1) pp. 4-32
  • Glover, M., and M. Laguna. (1997). Tabu Search. Boston: Kluwer Academic Publishers.
  • Or, I. (1976). “Traveling salesman-type combinatorial problems and their relation to the logistic of regional blood banking. In Ph.D. dissertation”. Departament of Industrial Engineering and Management Sciences. Northwestern University, Evanston, IL.
  • Taillard, E., P. Badeau, M. Gendreau, F. Guertain, and J. Y. Potvin. (1997). "A Tabu Search heuristic for the Vehicle Routing Problem with Soft Time Windows". Transportation Science 31 (2) pp. 170 186.
  • Deb, K., A. Pratap, S. Agarwal, and T. Meyarivan. (2002). "A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II". IEEE Transactions on Evolutionary Computation 6 (2) pp. 182–197.