ACO-Based Neighborhoods for Fixed-charge Capacitated Multi-commodity Network Design Problem

Document Type : Research Paper

Authors

1 Assistant Professor, Department of Rail Transportation Engineering, Iran University of Science and Technology, Tehran, Iran

2 MSc Grad., Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran

Abstract

The fixed-charge Capacitated Multi-commodity Network Design (CMND) is a well-known problem of both practical and theoretical significance. Network design models represent a wide variety of planning and operation management issues in transportation telecommunication, logistics, production and distribution. In this paper, Ant Colony Optimization (ACO) based neighborhoods are proposed for CMND problem. In the proposed neighborhoods, first, an open arc based on the incumbent solution is closed; then, by using an ant colony optimization algorithm called Ant Colony System (ACS), a new solution is generated by constructing new paths for the demands delivered on the closed arc. An algorithm is presented to construct new paths by using ACS algorithm for demands with continuous volume. A sub mixed integer programming (MIP) model is then created by joining the ACS and incumbent solutions. The generated sub-MIP is solved by using an MIP solver and its solution is considered as a neighborhood. In order to evaluate the proposed neighborhoods, an algorithm is developed. The algorithm parameters are tuned by using design of experiments. To assess the algorithm, several benchmark problems with different sizes are used. The statistical analysis shows the efficiency and effectiveness of the proposed algorithm compared to the best approaches found in the literature.

Keywords

References

- Balakrishnan, A., Magnanti, T. L. and Mirchandani, P. (1997) “Chapter: Network design”, In: (1997) Annotated Bibliographies in Combinatorial Optimization”. Ed. Dell’Amico, M.
- Maffioli, F. and Martello, S.,  New York : John Wiley and Sons, pp. 311-329.
- Chouman, M. and Crainic, T. G. (2010) “An MIP-Tabu search hybrid framework for multicommodity capacitated fixed charge network design”, In: CRT-2010, Ed. 31th, CIRRELT, Université de Montréal.
- Chouman, M., Crainic, T. G. and Gendron, B. (2003) “A cutting-plane algorithm based on cut set inequalities for multi commodity capacitated fixed charge network design”, In: CRT-2003, Ed. 16th, Centre der Echerchesurles Transports, Universitéde Montréal.
- Chouman, M., Crainic, T. G. and Gendron, B. (2009) “A cutting-plane algorithm for multicommodity capacitated fixed-charge network design”, In: CIRRELT, Centre de Recherche sur les Transports, Universite de Montreal, Montreal.
- Costa, A. M. (2005) “A survey on benders decomposition applied to fixed-charge network design problems”. Computers & Operations Research, Vol. 32, No. 6, pp. 1429–1450.
- Coy, S., Golden, B., Runger, G. and Wasil, E. (2001) “Using experimental design to find effectiveparameter settings for heuristics”, Journal of Heuristics, Vol. 7, No. 1, pp. 77-97.
- Crainic, T.G. (1999) “Network design in freight transportation”. European Journal of Operational Research, Vol. 122, No. 2, pp. 272-288.
- Crainic, T.G. and Gendron, B.  (2002) “Cooperative parallel tabu search for capacitated network design”. Journal of Heuristics, Vol. 8, No. 6, pp. 601-627.
- Crainic, T.G., Frangioni, A. and Gendron, B. (2001) “Bundle-based relaxation methods for multicommodity capacitated fixed charge network design”. Discrete Applied Mathematics, Vol. 112, No. 1, pp. 73-99.
- Crainic, T.G., Gendreau, M. and Farvolden, J.M. (2000) “A simplex-based tabu search method for capacitated network design”. INFORMS Journal on Computing, Vol. 12, No.3, pp. 223–236.
- Crainic, T.G., Gendreau, M. and Hernu, G. (2004) “A solpe scaling/ Lagrangian perturbation heuristic with long-term memory for multi commodity capacitated fixed-charge network design”. Journal of Heuristics, Vol.10, No. 5, pp. 525-45.
- Crainic, T.G., Li, Y. and Toulouse, M. (2006) “A first multi level cooperative algorithm for capacitated multi commodity network design”. Computers & Operations Research, Vol. 33, No. 9, pp. 2602–2622.
- Danna, E., Rothberg, E. and Le Pape, C. (2005) “Exploring relaxation induced neighborhood s to improve MIP solutions”. Mathematical Programming, Vol. 102, No. 1, pp. 71-90.
- Dorigo, M. and Gambardella, L.M. (1997) “A cooperative learning approach to the traveling salesman problem”. IEEE Transaction on Evolutionary Computation, Vol. 1, No. 1, pp. 53–66.
- Dorigo, M., Maniezzo, V. and Colorni, A. (1991) “Ant system: An autocatalytic optimizing process”, Dipartimento di Elettronica e Informazione, Politecnico di Milano.
-  Dorigo, M. and Stutzle, T. (2004) “Ant colony optimization”, MIT Press Cambridge.
- Dorigo, M., Caro, G. D. and Gambardella, L. M. (1999) “Ant algorithms for discrete optimization”. Artificial Life, Vol. 5, No. 2, pp. 137–172.
- Freund, J. E. (1992) “Mathematical statistics”. 5th ed. Prentice-Hall, New Jersey.
- Gendron, B. and Crainic, T.G. (1994) “Relaxations for multi commodity capacitated network design problems”. In: CRT-94, Ed. 5th, Centre der Echerchesurles Transports, Université de Montréal.
- Gendron, B. and Crainic, T. G. (1996) “Bounding procedures for multicommodity capacitated fixed charge network design problems”. In: CRT-96, Ed. 6th. Centre de Recherche sur les Transports, Universite de Montreal.
- Ghamlouche, I., Crainic, T. G. and Gendreau, M. (2003) “Cycle-based neighborhoods for fixed-charge capacitated multi commodity network design”. Operations Research, Vol. 51, No. 4, pp. 655–667.
- Ghamlouche, I., Crainic, T.G. and Gendreau, M. (2004) “Path relinking, cycle-based neighborhoods and capacitated multi commodity network design”. Annals of Operations Research, Vol. 131, No. 1-4, pp. 109–133.
- Glover, F., Laguna, M. and Martí, F. (2009) “Fundamentals of scatter search and path relinking”. Control and Cybernetics, Vol. 29, No. 3, pp. 653-684.
- Holmberg, K. and Yuan, D. (2000) “A Lagrangian heuristic based branch-and-bound approach for the capacitated network design problem”. Operations Research, Vol. 48, No. 3, pp. 461-481.
- Magnanti, T.L. and Wong, R.T. (1986) “Network design and transportation planning: Models and algorithms”. Transportation Science, Vol. 18, No.1, pp. 1-55.
- Martín, I.R. and González, J.J.S. (2010) “A local branching heuristic for the capacitated fixed-charge network design problem”. Computers & Operations Research, Vol. 37, No. 3, pp. 575-581.
Minoux, M. (1986) “Network synthesis and optimum network design problems: Models, solution methods and applications”. Networks, Vol. 19, No. 3, pp. 313-360.
Montgomery, D.C. (2009) “Design and Analysis of Experiments”, 7th ed., John Wiley and Sons.
- Montgomery, D. C. and Runger, G. (2006) “Applied statistics and probability for engineering”. 3rd ed.,  New York: John Wiley.
- Ridge, E. and Kudenko, D. (2010) “Tuning an algorithm using design of experiments”. In: Experimental methods for the analysis of optimization algorithms, Ed. Bartz-Beielstein, T., Chiarandini, M., Paquete, L. and Preuss, M. Springer Berlin Heidelberg. pp. 265–286.
- Socha, K., Sampels, M. and Manfrin, M. (2003) “Ant algorithms for the university course timetabling problem with regard to the state-of-the-art”. In: Proceedings of the 3rd European Workshop on Evolutionary Computation in Combinatorial Optimization (EvoCOP), UK. pp. 334–345.
- Stützle, T. and Dorigo, M. (1999) “ACO algorithms for the traveling salesman problem”. Evolutionary Algorithms in Engineering and Computer Science, pp. 163-183.
- Talbi, E. G. (2009) “Metaheuristics: From design to implementation”, New York: John Wiley & Sons.
- Yaghini, M. and Kazemzadeh, M. R. A. (2012a) “Multicommodity network design problem in rail freight transportation planning”. In: Paper presented at the 8th International Conference on Traffic and Transportation Studies, Changsha, China.
- Yaghini, M. and Kazemzadeh, M. R. A. (2012b) “A simulated annealing algorithm for unsplittable capacitated network design”. International Journal of Industrial Engineering, Vol. 23, No. 2, pp. 91-100.
- Yaghini, M., Ahmadi, H. R., Barati, E., and Saghian, Z. (2013) “A tabu search algorithm for the railroad blocking problem”. Journal of Transportation Engineering,  Vol. 139, No. 2.
- Yaghini, M., Karimi, M., Rahbar, M. and Akhavan, R. (2011) “A hybrid simulated annealing and simplex method for fixed-cost capacitated multicommodity network design”. International Journal of Applied Metaheuristic Computing , Vol. 2, No. 4, pp. 13-28.
- Yaghini, M., Momeni, M. and Sarmadi, M. (2012a) “A simplex–based simulated annealing algorithm for node–arc capacitated multicommodity network design”. Applied Soft Computing, Vol. 12, No. 9, pp. 2997-3003.
- Yaghini, M., Momeni, M. and Sarmadi, M. (2012b). “Solving train formation problem using simulated annealing algorithm in a simplex framework”. Journal of Advanced Transportation (in press).
- Yaghini, M., Momeni, M. and Sarmadi, M. (2013a). “An improved local branching approach for train formation planning”. Applied Mathematical Modelling, Vol. 37, No. 4, pp. 2300–2307.
- Yaghini, M., Rahbar, M. and Karimi, M. (2013b). “A hybrid simulated annealing and column generation approach for capacitated multicommodity network design”. Journal of the Operational Research Society, Vol. 64, No. 7, pp. 1010–1020.
International Journal of Transportation Engineering
Volume 1, Issue 4 - Serial Number 4
April 2014
Pages 311-334

Files

Share

How to cite

Statistics