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 |
Keywords:
service network design; design-balanced constraints; single-path constraints; local branching; relaxation induced neighborhood searchSoftware:
SPOTReferences:
| [1] | Ahuja, R. K.; Magnanti, T. L.; Mirchandani, P., Network flow-theory, algorithm, and applications, (1993), Prentice-Hall Englewood Cliffs, NJ · Zbl 1201.90001 |
| [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 · Zbl 1122.68012 |
| [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. 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.
