Hybrid meta-heuristic algorithms for solving network design problem. (English) Zbl 1121.90024
Summary: Network design problem has been, and is, an important problem in transportation. Following an earlier effort in designing a meta-heuristic search technique by an ant system, this paper attempts to hybridize this concept with other meta-heuristic concepts such as genetic algorithm, simulated annealing, and tabu search. Seven hybrids have been devised and tested on the network of Sioux Falls. It has been observed that the hybrids are more effective to solve the network design problem than the base ant system. Application of the hybrid containing all four concepts on a real network of a city with over 2 million population has also proved to be more effective than the base network, in the sense of finding better solutions sooner.
MSC:
| 90B06 | Transportation, logistics and supply chain management |
| 90B10 | Deterministic network models in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Software:
Tabu searchReferences:
| [1] | Abdulaal, M.; LeBlanc, L. J., Continuous equilibrium network design models, Transportation Research, Part B, 13, 19-32 (1979) |
| [2] | Ahmad, N. U., An analytical decision model for resource allocation in highway maintenance management, Transportation Research A, 17A, 2, 133-138 (1983) |
| [3] | Boyce, D. E.; Farhi, A.; Weischedel, R., Optimal network design problem: A branch and bound algorithm, Environment and Planning, 5, 519-533 (1973) |
| [4] | Cantarella, G.E., Pavone, G., Vitetta, A., Heuristics for the network design problem. In: Ewg 2002 (the 13th Mini Euro Conference), Bari, Italy.; Cantarella, G.E., Pavone, G., Vitetta, A., Heuristics for the network design problem. In: Ewg 2002 (the 13th Mini Euro Conference), Bari, Italy. · Zbl 1142.90345 |
| [5] | Chelouah, R.; Siarry, P., Genetic and Nelder-Mead algorithms hybridized for a more accurate global optimization of continuous multiminima functions, European Journal of Operational Research, 148, 335-348 (2003) · Zbl 1035.90062 |
| [6] | Chen, M.; Sul Alfa, A., A network design algorithm using a stochastic incremental traffic assignment approach, Transportation Science, 25, 215-224 (1991) · Zbl 0729.90985 |
| [7] | Costa, D., An evolutionary tabu search algorithm and the NHL scheduling problem, INFORM, 33, 161-178 (1995) · Zbl 0833.90095 |
| [8] | Cree, N.D., Maher, M.J., Paechter, B., 1998. The continuous equilibrium optimal network design problem: A genetic approach. In: Bell, M.G.H. (Eds.), Transportation Networks: Recent Methodological Advances. Selected Proceedings of the 4th Euro Transportation Meeting, pp. 163-174.; Cree, N.D., Maher, M.J., Paechter, B., 1998. The continuous equilibrium optimal network design problem: A genetic approach. In: Bell, M.G.H. (Eds.), Transportation Networks: Recent Methodological Advances. Selected Proceedings of the 4th Euro Transportation Meeting, pp. 163-174. |
| [9] | Dantzig, G. D.; Harvey, R. P.; Lansdowne, Z. F.; Robinson, D. W.; Maier, S. F., Formulating and solving the network design problem by decomposition, Transportation Research, 13B, 5-17 (1979) |
| [10] | De Werra, D.; Hertz, A., Tabu: A Application to Neural Networks, OR Spectrum, 11, 131-141 (1989) · Zbl 0672.90089 |
| [11] | Dorigo, M.; Gambardella, L. M., Ant colonies for the traveling salesman problem, BioSystems, 43, 73-81 (1997) |
| [12] | Dorigo, M., Maniezzo, V., Colorni, A., 1991. The ant system: An autocatalytic optimization process. Technical Report TR91-016, Politecnico Di Milano.; Dorigo, M., Maniezzo, V., Colorni, A., 1991. The ant system: An autocatalytic optimization process. Technical Report TR91-016, Politecnico Di Milano. · Zbl 0912.90240 |
| [13] | Dorigo, M.; Maniezzo, V.; Colorni, A., The ant system: Optimization by a colony of cooperating agent, IEEE Transactions on Systems, Man and Cybernetics, Part B, 26, 1, 1-13 (1996) |
| [14] | Fleurent, C.; Ferland, J., Genetic Hybrids for the quadratic assignment problem, DIMACS Series in Mathematics Theoretical Computer Science, 16, 190-206 (1999) |
| [15] | Friesz, T. L.; Cho, H. J.; Mehta, N. J.; Tobin, R. L.; Anadalingam, G., A simulated annealing approach to the network design problem with variational inequality constraints, Transportation Science, 26, 1, 18-26 (1992) · Zbl 0764.90084 |
| [16] | Glover, F.; Kelly, J. P.; Laguna, M., Genetic algorithms and tabu search: Hybrids for optimization, Computer & Operations Research, 22, 1, 111-134 (1995) · Zbl 0813.90093 |
| [17] | Goldberg, D. E., Genetic Algorithm Optimization (1989), Addison-Wesley Publishing Company: Addison-Wesley Publishing Company Reading, Mass · Zbl 0721.68056 |
| [18] | Greistorfer, P., Hybrid genetic tabu search for cyclic scheduling problem, (Meta-Heuristics Advances and Trends in Local Search Paradigms for Optimization (1998), Klower: Klower Boston) · Zbl 0970.90032 |
| [19] | Haghani, A. E.; Daskin, M. S., Network design application of an extraction algorithm for network aggregation, Transportation Research Record, 944, 37-46 (1983) |
| [20] | Hertz, A.; Widmer, M., Guidelines for the use of metaheuristics in combinatorial optimization, European Journal of Operational Research, 151, 247-252 (2003) · Zbl 1053.90053 |
| [21] | Hoang, H. H., Topological optimization of networks: A nonlinear mixed integer model employing generalized benders decomposition, IEEE Transaction on Automatic Control, 27, 164-169 (1982) · Zbl 0472.90068 |
| [22] | Holmberg, K.; Hellstrand, J., Solving the uncapacitated network design problem by a Lagrangian heuristic and branch-and-bound, Operations Research, 46, 2, 247-259 (1998) · Zbl 0979.90060 |
| [23] | Kim, H.; Nara, K.; Gen, M., A method for maintenance scheduling using GA combined with SA, Computers Industrial Engineering, 27, 477-486 (1994) |
| [24] | LeBlanc, L. J., An algorithm for discrete network design problem, Transportation Science, 9, 183-199 (1975) |
| [25] | Lee, C. K.; Yang, K. I., Network design of one-way streets with simulated annealing, Papers in Regional Science, 32, 2, 119-134 (1994) |
| [26] | Magnanti, T. L.; Wong, R. T., Network design and transportation planning: models and algorithms, Transportation Science, 18, 1, 1-55 (1984) |
| [27] | Maniezzo, V.; Gambardella, L. M.; Deluigi, F., Ant colony optimization, (Onwubolu, G. C.; Babu, B. V., New Optimization Techniques in Engineering (2003), Springer-Verlag), (www.idsia.ch&z.drule;∼luca&z.drule;ACO.2004.pdf) |
| [28] | Onwubolu, G. C., Emerging Optimization Techniques in Production Planning and Control (2002), Imperial College Press: Imperial College Press London · Zbl 1006.90028 |
| [29] | Poorzahedy, H.; Abulghasemi, F., Application of ant system to network design problem, Transportation, 32, 251-273 (2005) |
| [30] | Poorzahedy, H.; Turnquist, M. A., Approximate Algorithms for the Discrete Network Design Problem, Transportation Research, Part B, 16, 45-56 (1982) |
| [31] | Resende, M.G.C., Pardalos, P.M., Eksioglu, S.D., 1999. Parallel Metaheuristics for Combinatorial Optimization, www.research.att.com; Resende, M.G.C., Pardalos, P.M., Eksioglu, S.D., 1999. Parallel Metaheuristics for Combinatorial Optimization, www.research.att.com |
| [32] | Sadek, A.W., 2001. A hybrid simulated annealing and case-based reasoning approach for computationally intensive transportation problem: Rationale and design issues. In: TRB, 80th Annual Meeting, Washington, DC.; Sadek, A.W., 2001. A hybrid simulated annealing and case-based reasoning approach for computationally intensive transportation problem: Rationale and design issues. In: TRB, 80th Annual Meeting, Washington, DC. |
| [33] | Salmon, P.; Sibani, P.; Frost, R., Facts, Conjectures and Improvements for Simulated Annealing (2002), SIAM Society of Industrial & Applied Mathematics: SIAM Society of Industrial & Applied Mathematics Philadelphia, PA. · Zbl 1070.90137 |
| [34] | Solanki, R. S.; Gorti, J. K.; Southworth, F., Using decomposition in large-scale highway network design with quasi-optimization heuristic, Transportation Research, Part B, 32, 127-140 (1998) |
| [35] | Steenbrink, P. A., Optimization of Transport Network (1974), John Wiley: John Wiley NewYork |
| [36] | Steenbrink, P. A., Transportation network optimization in the Dutch integral transportation study, Transportation Research, 8, 11-27 (1974) |
| [37] | Taillard, E.D., Gambardella, L.M., 1997. Adaptive memories for the quadratic assignment problem. Technical Report IDSIA-79-97, Lugano, Switzerland.; Taillard, E.D., Gambardella, L.M., 1997. Adaptive memories for the quadratic assignment problem. Technical Report IDSIA-79-97, Lugano, Switzerland. |
| [38] | Wong, R. T., Introduction and Recent Advances in Network Design Models and Algorithms, (Florian, M., Transportation Planning Models (1984), North-Holland: North-Holland Amsterdam) · Zbl 0594.90086 |
| [39] | Yang, H.; Bell, M. G.H., Models and algorithms for road network design: A review and some new developments, Transport Review, 18, 3, 257-278 (1998) |
| [40] | Yin, Y., Genetic algorithm-based approach for bilevel programming models, Journal of Transportation Engineering: ASCE, 26, 2, 115-120 (2000) |
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.
