A three-phase matheuristic for capacitated multi-commodity fixed-cost network design with design-balance constraints
Tóm tắt
This paper proposes a three-phase matheuristic solution strategy for the capacitated multi-commodity fixed-cost network design problem with design-balance constraints. The proposed matheuristic combines exact and neighbourhood-based methods. Tabu search and restricted path relinking meta-heuristics cooperate to generate as many feasible solutions as possible. The two meta-heuristics incorporate new neighbourhoods, and computationally efficient exploration procedures. The feasible solutions generated by the two procedures are then used to identify an appropriate part of the solution space where an exact solver intensifies the search. Computational experiments on benchmark instances show that the proposed algorithm finds good solutions to large-scale problems in a reasonable amount of time.
Tài liệu tham khảo
Andersen, J., Crainic, T.G., Christiansen, M.: Service network design with management and coordination of multiple fleets. Eur. J. Oper. Res. 193(2), 377–389 (2009a)
Andersen, J., Crainic, T.G., Christiansen, M.: Service network design with asset management: formulations and comparative analyzes. Transp. Res. C. 17(2), 207–397 (2009b)
Andersen, J., Christiansen, M., Crainic, T.G., Grønhaug, R.: Branch-and-price for service network design with asset management constraints. Transp. Sci. 46(1), 33–49 (2011)
Armacost, A.P., Barnhart, C., Ware, K.A.: Composite variable formulations for express shipment service network design. Transport. Sci. 36(1), 1–20 (2002)
Balakrishnan, A., Magnanti, T.L., Mirchandani, P.: Network design. In: Dell’Amico, M., Maffioli, F., Martello, S. (eds.) Annotated Bibliographies in Combinatorial Optimization, pp. 311–334. Wiley, New York (1997)
Barnhart, C., Krishnan, N., Kim, D., Ware, K.: Network design for express shipment delivery. Comput. Optim. Appl. 21(3), 239–262 (2002)
Chouman, M., Crainic, T.G.: A MIP-Tabu Search Hybrid Framework for Multicommodity Capacitated Fixed-Charge Network Design. Technical Report CIRRELT-2010-31. Centre interuniversitaire de recherche sur les réseaux d’entreprise, la logistique et les transports, Université de Montréal, Montréal (2010)
Christiansen, M., Fagerholt, K., Nygreen, B., Ronen, D.: Maritime transportation. In: Barnhart, C., Laporte, G. (eds.) Transportation. Handbooks in Operations Research and Management Science, vol. 14, pp. 189–284. North-Holland, Amsterdam (2007)
Cordeau, J.-F., Toth, P., Vigo, D.: A survey of optimization models for train routing and scheduling. Transp. Sci. 32(4), 380–404 (1998)
Crainic, T.G.: Network design in freight transportation. Eur. J. Oper. Res. 122(2), 272–288 (2000)
Crainic, T.G., Kim, K.: Intermodal transportation, Chap. 8. In: Barnhart, C., Laporte, G. (eds.) Transportation. Handbooks in Operations Research and Management Science, vol. 14, pp. 467–537. North-Holland, Amsterdam (2007)
Ghamlouche, I., Crainic, T.G., Gendreau, M.: Cycle-based neighbourhoods for fixed-charge capacitated multicommodity network design. Oper. Res. 51(4), 655–667 (2003)
Ghamlouche, I., Crainic, T.G., Gendreau, M.: Path relinking, cycle-based neighbourhoods and capacitated multicommodity network design. Ann. Oper. Res. 131, 109–133 (2004)
Glover, F.: Tabu search—Part I. ORSA J. Comput. 1(3), 190–206 (1989)
Glover, F.: Tabu search—Part II. ORSA J. Comput. 2(1), 4–32 (1990)
Glover, F.: A template for scatter search and path relinking. In: Hao, J., Lutton, E., Ronald, E., Schoenauer, M., Snyers, D. (eds.) Artificial Evolution. Lecture Notes in Computer Science, vol. 1363, pp. 13–54. Springer, Berlin (1997)
Glover, F., Laguna, M., Martí, R.: Fundamentals of scatter search and path relinking. Control Cybern. 39(3), 653–684 (2000)
Kim, D., Barnhart, C., Ware, K., Reinhardt, G.: Multimodal express package delivery: a service network design application. Transp. Sci. 33(4), 391–407 (1999)
Magnanti, T.L., Wong, R.: Network design and transportation planning: models and algorithms. Transp. Sci. 18(1), 1–55 (1984)
Minoux, M.: Network synthesis and optimum network design problems: models, solution methods applications. Networks 19, 313–360 (1989)
Pedersen, M.B., Crainic, T.G., Madsen, O.B.G.: Models and Tabu search meta-heuristics for service network design with asset-balance requirements. Transp. Sci. 43(2), 158–177 (2009)
Smilowitz, K.R., Atamtürk, A., Daganzo, C.F.: Deferred item and vehicle routing within integrated networks. Transp. Res. E 39, 305–323 (2003)