An integrative cooperative search framework for multi-decision-attribute combinatorial optimization: application to the MDPVRP. (English) Zbl 1346.90706
Summary: We introduce the integrative cooperative search method (ICS), a multi-thread cooperative search method for multi-attribute combinatorial optimization problems. ICS musters the combined capabilities of a number of independent exact or meta-heuristic solution methods. A number of these methods work on sub-problems defined by suitably selected subsets of decision-set attributes of the problem, while others combine the resulting partial solutions into complete ones and, eventually, improve them. All these methods cooperate through an adaptive search-guidance mechanism, using the central-memory cooperative search paradigm. Extensive numerical experiments explore the behavior of ICS and its interest through an application to the multi-depot, periodic vehicle routing problem, for which ICS improves the results of the current state-of-the-art methods.
MSC:
| 90C27 | Combinatorial optimization |
| 90B40 | Search theory |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
multi-attribute combinatorial optimization; integrative cooperative search; meta-heuristics; decision-set decomposition; multi-depot periodic vehicle routingSoftware:
VRPReferences:
| [1] | (Alba, E., Parallel metaheuristics: A new class of algorithms (2005), John Wiley & Sons: John Wiley & Sons Hoboken, NJ) · Zbl 1094.90052 |
| [2] | Badeau, P.; Gendreau, M.; Guertin, F.; Potvin, J.-Y.; Taillard, E., A parallel tabu search heuristic for the vehicle routing problem with time windows, Transportation Research Part C: Emerging Technologies, 5, 2, 109-122 (1997) |
| [3] | Baldacci, R.; Bartolini, E.; Mingozzi, A.; Valletta, A., An exact algorithm for the periodic routing problem, Operations Research, 59, 1, 228-241 (2011) · Zbl 1218.90118 |
| [4] | Baldacci, R.; Mingozzi, A., A unified exact method for solving different classes of vehicle routing problems, Mathematical Programming A, 120, 2, 347-380 (2009) · Zbl 1180.90260 |
| [5] | Benders, J. F., Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik, 4, 238-252 (1962) · Zbl 0109.38302 |
| [6] | Berger, J.; Barkaoui, M., A parallel hybrid genetic algorithm for the vehicle routing problem with time windows, Computers & Operations Research, 31, 12, 2037-2053 (2004) · Zbl 1100.90503 |
| [7] | Bertsekas, D.; Tsitsiklis, J., Parallel and distributed computation, numerical methods (1989), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0743.65107 |
| [8] | Bouthillier, A. L.; Crainic, T. G.; Kropf, P., A guided cooperative search for the vehicle routing problem with time windows, IEEE Intelligent Systems, 20, 4, 36-42 (2005) |
| [9] | Cantú-Paz, E., Theory of parallel genetic algorithms, (Alba, E., Parralel metaheuristics: A new class of algorithms (2005), John Wiley & Sons: John Wiley & Sons Hoboken), 425-445 · Zbl 1137.90723 |
| [10] | Cordeau, J.-F.; Laporte, G.; Mercier, A., A unified tabu search heuristic for vehicle routing problems with time windows, Journal of the Operational Research Society, 52, 928-936 (2001) · Zbl 1181.90034 |
| [11] | Crainic, T. G., Network design in freight transportation, European Journal of Operational Research, 122, 2, 272-288 (2000) · Zbl 0961.90010 |
| [12] | Crainic, T. G., Parallel computation, co-operation, tabu search, (Rego, C.; Alidaee, B., Metaheuristic optimization via memory and evolution: Tabu search and scatter search (2005), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA), 283-302 · Zbl 1072.90055 |
| [13] | Crainic, T. G., Parallel solution methods for vehicle routing problems, (Golden, B. L.; Raghavan, S.; Wasil, E. A., The vehicle routing problem: latest advances and new challenges (2008), Springer: Springer New York), 171-198 · Zbl 1187.90046 |
| [14] | Crainic, T. G.; Chiara, B. D.; Nonato, M.; Tarricone, L., Tackling electrosmog in completely configured 3G networks by parallel cooperative meta-heuristics, IEEE Wireless Communications, 13, 6, 34-41 (2006) |
| [15] | Crainic, T. G.; Cun, B. L.; Roucairol, C., Parallel branch and bound algorithms, (Talbi, E. G., Parallel combinatorial optimization (2006), John Wiley & Sons: John Wiley & Sons New York), 1-28 |
| [16] | Crainic, T. G.; Frangioni, A.; Gendron, B., Bundle-based relaxation methods for multicommodity capacitated network design, Discrete Applied Mathematics, 112, 73-99 (2001) · Zbl 1026.90010 |
| [17] | Crainic, T. G.; Hail, N., Parallel meta-Heuristics applications, (Alba, E., Parallel metaheuristics: A new class of algorithms (2005), John Wiley & Sons: John Wiley & Sons Hoboken, NJ), 447-494 · Zbl 1137.90023 |
| [18] | Crainic, T. G.; Toulouse, M., Explicit and emergent cooperation schemes for search algorithms, (Maniezzo, V.; Battiti, R.; Watson, J.-P., Learning and intelligent optimization. Learning and intelligent optimization, Lecture Notes in Computer Science, volume 5315 (2008), Springer-Verlag: Springer-Verlag Berlin), 95-109 |
| [19] | Crainic, T. G.; Toulouse, M., Parallel meta-heuristics, (Gendreau, M.; Potvin, J.-Y., Handbook of metaheuristics (2010), Springer), 497-541 |
| [20] | Crainic, T. G.; Toulouse, M.; Gendreau, M., Parallel asynchronous tabu search for multicommodity location-allocation with balancing requirements, Annals of Operations Research, 63, 277-299 (1996) · Zbl 0851.90033 |
| [21] | Crainic, T. G.; Toulouse, M.; Gendreau, M., Towards a taxonomy of parallel tabu search algorithms, INFORMS Journal on Computing, 9, 1, 61-72 (1997) · Zbl 0891.90094 |
| [22] | Dantzig, G. B.; Wolfe, P., Decomposition principle for linear programs, Operations Research, 8, 1, 101-111 (1978), also Econometrica 9(4), 1961 · Zbl 0093.32806 |
| [23] | (Drezner, Z.; Hamacher, H. (2002), Springer Verlag: Springer Verlag Berlin) |
| [24] | Gendron, B.; Crainic, T. G., Parallel branch-and-bound algorithms: Survey and synthesis, Operations Research, 42, 6, 1042-1066 (1994) · Zbl 0824.90096 |
| [25] | Geoffrion, A. M., Elements of large-scale mathematical programming, Management Science, 16, 652-675 (1970) · Zbl 0209.22801 |
| [26] | Golden, B. L.; Assad, A. A.; Wasil, E. A., Routing vehicles in the real world: Applications in the solid waste, beverage, food, dairy, and newspaper industries, (Toth, P.; Vigo, D., The vehicle routing problem (2002), SIAM: SIAM Philadelphia, PA), 245-286 · Zbl 1076.90546 |
| [27] | (Golden, B. L.; Raghavan, S.; Wasil, E. A. (2008), Springer: Springer New York) |
| [28] | Grötschel, M.; Monma, C.; Stoer, M., Design of survivable networks, (Ball, M.; Magnanti, T.; Monma, C.; Nemhauser, G., Network models. Handbooks in operations research and management science, volume 7 (1995), North-Holland: North-Holland Amsterdam), 617-672 · Zbl 0839.90132 |
| [29] | Guignard, M.; Kim, S., Lagrangean decomposition: A model yielding stronger Lagrangean bounds, Mathematical Programming, 39, 215-228 (1987) · Zbl 0638.90074 |
| [30] | Hachemi, N. E.; Crainic, T. G.; Lahrichi, N.; Rei, W.; Vidal, T., Solution integration in combinatorial optimization with applications to cooperative search and rich vehicle routing, Publication CIRRELT-2014-40, Centre interuniversitaire de recherche sur les réseaux d’entreprise, la logistique et le transport (2014), Université de Montréal: Université de Montréal Montréal, QC, Canada |
| [31] | Hadjiconstantinou, E.; Baldacci, R., A multi-depot period vehicle routing problem arising in the utilities sector, Journal of the Operational Research Society, 49, 12, 1239-1248 (1998) · Zbl 1140.90331 |
| [32] | Hartl, R. F.; Hasle, G.; Jansens, G. K., Special issue on rich vehicle routing problems, Central European Journal of Operations Research, 13 (2006) · Zbl 1203.90007 |
| [33] | Homberger, J.; Gehring, H., Two evolutionary metaheuristics for the vehicle routing problem with time windows, INFOR, 37, 297-318 (1999) · Zbl 07677595 |
| [34] | Homberger, J.; Gehring, H., A two-phase hybrid metaheuristics for the vehicle routing problem with time windows, European Journal of Operational Research, 162, 220-238 (2005) · Zbl 1132.90378 |
| [35] | Jin, J.; Crainic, T. G.; Løkketangen, A., A cooperative parallel metaheuristic for the capacitated vehicle routing problems, Computers & Operations Research, 44, 33-41 (2014) · Zbl 1307.90024 |
| [36] | Kang, K. H.; Lee, Y. H.; Lee, B. K., An exact algorithm for multi depot and multi period vehicle scheduling problem, Computational science and its applications - ICCSA 2005, Lecture notes in computer science, 350-359 (2005), Springer: Springer Berlin/Heidelberg |
| [37] | Lasdon, L. S., Optimization theory for large systems (2002), Dover Publications: Dover Publications Mineola, N.Y. · Zbl 0991.90001 |
| [38] | Luque, G.; Alba, E.; Dorronsoro, B., Parallel genetic algorithms, (Alba, E., Parralel metaheuristics: A new class of algorithms (2005), John Wiley & Sons: John Wiley & Sons Hoboken), 107-125 · Zbl 1278.90471 |
| [39] | Magnanti, T. L.; Wong, R., Network design and transportation planning: Models and algorithms, Transportation Science, 18, 1, 1-55 (1984) |
| [40] | Mingozzi, A., The multi-depot periodic vehicle routing problem, Abstraction, reformulation and approximation, Lecture notes in computer science, 347-350 (2005), Springer: Springer Berlin/Heidelberg |
| [41] | Rochat, Y.; Taillard, E. D., Probabilistic diversification and intensification in local search for vehicle routing, Journal of Heuristics, 1, 1, 147-167 (1995) · Zbl 0857.90032 |
| [42] | Taillard, E. D., Parallel iterative search methods for vehicle routing problems, Networks, 23, 661-673 (1993) · Zbl 0804.90045 |
| [43] | (Talbi, E. G., Parallel combinatorial optimization (2006), Wiley-Interscience, Wiley & Sons: Wiley-Interscience, Wiley & Sons Hoboken, NJ) |
| [44] | Talukdar, S.; Baerentzen, L.; Gove, A.; de Souza, P., Asynchronous teams: Cooperation schemes for autonomous agents, Journal of Heuristics, 4, 295-321 (1998) · Zbl 1071.90560 |
| [45] | Talukdar, S.; Murthy, S.; Akkiraju, R., Assynchronous teams, (Glover, F.; Kochenberger, G., Handbook in metaheuristics (2003), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA), 537-556 · Zbl 1175.90076 |
| [46] | (Toth, P.; Vigo, D., The vehicle routing problemSIAM monographs on discrete mathematics and applications (2002), SIAM: SIAM Philadelphia, PA) · Zbl 0979.00026 |
| [47] | Toulouse, M.; Thulasiraman, K.; Glover, F., Multi-level cooperative search: a new paradigm for combinatorial optimization and an application to graph partitioning, (Amestoy, P.; Berger, P.; M. Daydé, M.; Duff, I.; Frayssé, V.; Giraud, L.; Ruiz, D., 5th international Euro-par parallel processing conference. 5th international Euro-par parallel processing conference, Lecture notes in computer science, volume 1685 (1999), Springer-Verlag: Springer-Verlag Heidelberg), 533-542 |
| [48] | Vahed, A. R.; Crainic, T. G.; Gendreau, M.; Rei, W., A path relinking algorithm for a multi-depot periodic vehicle routing problem, Journal of Heuristics, 19, 3, 497-524 (2013) |
| [49] | Vidal, T.; Crainic, T. G.; Gendreau, M.; Lahrichi, N.; Rei, W., A hybrid genetic algorithm for multi-depot and periodic vehicle routing problems, Operations Research, 60, 3, 611-624 (2012) · Zbl 1260.90058 |
| [50] | Vidal, T.; Crainic, T. G.; Gendreau, M.; Prins, C., Heuristics for multi-attribute vehicle routing problems: A survey and synthesis, European Journal of Operational Research, 231, 1, 1-21 (2013) · Zbl 1317.90006 |
| [51] | Vidal, T.; Crainic, T. G.; Gendreau, M.; Prins, C., Timing problems and algorithms: Time decisions for sequences of activities, Networks, 65, 2, 102-128 (2015) · Zbl 1390.90486 |
| [52] | Vidal, T.; Crainic, T. G.; Gendreau, M.; Prins, C., A unified solution framework for multi-attribute vehicle routing problems, European Journal of Operational Research, 234, 3, 658-673 (2014) · Zbl 1304.90004 |
| [53] | Yang, W. T.; Chu, L. C., A heuristic algorithm for the multi-depot periodic vehicle routing problem, Journal of Information & Optimization Sciences, 22, 359-367 (2000) · Zbl 1018.90002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
