×

zbMATH — the first resource for mathematics

Matheuristics for the single-path design-balanced service network design problem. (English) Zbl 1391.90117
Summary: We introduce and study the single-path design-balanced service network design problem, where flow of a commodity must use only one path from origin to destination. We present an arc-based formulation. We propose two approaches respectively based on matheuristics: local branching and relaxation induced neighborhood search. These approaches hybridize metaheuristic strategies and mathematical programming, and use an idea of defining neighborhoods as small mixed integer programs (MIP), and exploring neighborhoods using MIP solvers. We also present an implementation combining these two approaches. In addition, we propose a Lagrangian heuristic to generate a starting solution. Our computational results demonstrate effectiveness of these approaches.

MSC:
90B10 Deterministic network models in operations research
90C59 Approximation methods and heuristics in mathematical programming
90B06 Transportation, logistics and supply chain management
90C11 Mixed integer programming
Software:
SPOT
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahuja, R. K.; Magnanti, T. L.; Mirchandani, P., Network flow-theory, algorithm, and applications, (1993), Prentice-Hall Englewood Cliffs, NJ
[2] Armacost, A. P.; Barnhart, C.; Ware, K. A., Composite variable formulations for express shipment service network design, Transp. Sci., 36, 1-20, (2002) · Zbl 1065.90505
[3] Barnhart, C.; Hane, C. A.; Vance, P. H., Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems, Oper. Res., 48, 318-326, (2000)
[4] Barnhart, Cynthia; Krishnan, Niranjan; Kim, Daeki; Ware, Keith, Network design for express shipment delivery, Comput. Optim. Appl., 21, 239-262, (2002) · Zbl 0994.90009
[5] Chouman, Mervat; Crainic, Teodor Gabriel, Cutting-plane matheuristic for service network design with design-balanced requirements, Transp Sci, 49, 99-113, (2015)
[6] Christiansen M, Fagerholt K, Nygreen B, Ronen D. Maritime transportation. Handb Oper Res Manag Sci 2007;14:189-284.
[7] Cordeau, J.-F.; Toth, P.; Vigo, D., A survey of optimization models for train routing and scheduling, Transp Sci, 32, 380-404, (1998) · Zbl 0987.90507
[8] Coy, S.; Golden, B.; Runger, G.; Wasil, E., Using experimental design to find effective parameter settings for heuristics, J Heurist, 7, 77-97, (2001) · Zbl 0967.90018
[9] Crainic, T. G., Service network design in freight transportation, Eur J Oper Res, 1222, 272-288, (2000) · Zbl 0961.90010
[10] Crainic, T. G.; Gendreau, M., A simplex-based tabu search method for capacitated network design, INFORMS J Comput, 12, 223-236, (2000) · Zbl 1040.90506
[11] Crainic, T. G.; Hewitt, M.; Toulouse, M.; Vu, D. M., Service network design with resource constraints, Transp Sci, (2014), In press
[12] Crainic, T. G.; Kim, K., Intermodal transportation, Transportation, 14, 467-537, (2006)
[13] Danna, E.; Rothberg, E.; Le Pape, C., Exploring relaxation induced neighborhoods to improve MIP solutions, Math Program, 102, 71-90, (2005) · Zbl 1131.90036
[14] Fischetti, M.; Lodi, A., Local branching, Math Program, 98, 23-47, (2003) · Zbl 1060.90056
[15] Gendron B, Crainic TG. Relaxations for multicommodity capacitated network design problems. Tech. rep. Publication CRT-965, Centre de Recherche sur Les Transports, Université de Montréal, Montréal, QC, Canada 1994.
[16] Ghamlouche, I.; Crainic, T. G.; Gendreau, M., Cycle-based neighbourhoods for fixed-charge capacitated multicommodity network design, Oper Res, 51, 655-667, (2003) · Zbl 1165.90360
[17] Ghamlouche, I.; Crainic, T. G.; Gendreau, M., Path relinking, cycle-based neighbourhoods and capacitated multicommodity network design, Ann Oper Res, 131, 109-133, (2004) · Zbl 1067.90014
[18] Holmberg, K.; Yuan, D., A Lagrangian heuristic based branch-and-bound approach for the capacitated network design problem, Oper Res, 48, 461-481, (2000) · Zbl 1106.90381
[19] Kim, D.; Barnhart, C.; Ware, G.; Reinhardt, G., Multimodel express package deliverya service network design application, Transp Sci, 33, 391-407, (1999) · Zbl 0958.90004
[20] Magnanti, T. L.; Wong, R. T., Network design and transportation planningmodels and algorithms, Transp Sci, 18, 1-55, (1984)
[21] Maniezzo, V.; Stützle, T.; Voß, S., Matheuristics—hybridizing metaheuristics and mathematical programming, (2010), Springer US
[22] Nelder, J. A.; Mead, R., A simplex method for function minimization, Comput J, 7, 308-313, (1965) · Zbl 0229.65053
[23] Pedersen, M. B.; Crainic, T. G.; Madsen, O. B.G., Models and tabu search metaheuristic for service network design with asset balance requirments, Transp Sci, 43, 158-177, (2009)
[24] Ridge, E.; Kudenko, D., Engineering stochastic local search algorithms. designing, implementing and analyzing effective heuristics, (Stützle, T.; Birattari, M.; Hoos, H., Lecture notes in computer science, vol. 4638, (2007), Springer Berlin Heidelberg), 46-60
[25] Ridge, E.; Kudenko, D., Tuning an algorithm using design of experiments, (Bartz-Beielstein, Thomas; Chiarandini, Marco; Paquete, Lus; Preuss, Mike, Experimental methods for the analysis of optimization algorithms, (2010), Springer Berlin Heidelberg), 265-286 · Zbl 1206.68380
[26] Rodríguez-Martín, Inmaculada; Salazar-González, Juan José, A local branching heuristic for the capacitated fixed-charge network design problem, Comput Oper Res, 37, 575-581, (2010) · Zbl 1175.90072
[27] Smilowitz, K. R.; Atamtrk, A.; Daganzo, C. F., Deferred item and vehicle routing within integrated networks, Transp Res Part E Logist Transp Rev, 39, 305-323, (2003)
[28] Verter, V.; Kara, B. Y., A path-based approach for hazmat transport network design, Manag Sci, 54, 29-40, (2008)
[29] Vu, D. M.; Crainic, T. G.; Toulouse, M., A three-phase matheuristic for capacitated multi-commodity fixed-cost network design with design-balance constraints, J Heurist, 19, 757-795, (2013)
[30] Yaghini M, Momeni M, Sarmadi M, Ahadi HR. An efficient heuristic algorithm for the capacitated p-median problem. 4OR 2013;11:229-48. · Zbl 1282.90160
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.