Flexible solutions to maritime inventory routing problems with delivery time windows. (English) Zbl 1391.90106
Summary: This paper studies a maritime inventory routing problem with time windows (MIRPTW) for deliveries with uncertain disruptions. We consider disruptions that increase travel times between ports and ultimately affect the deliveries in one or more time windows. The objective is to find flexible solutions that can accommodate unplanned disruptions. We propose a Lagrangian heuristic algorithm for obtaining flexible solutions by introducing auxiliary soft constraints that are incorporated in the objective function with Lagrange multipliers. To evaluate the flexibility of solutions, we build a simulator that generates disruptions and recovery solutions. Computational results show that by incurring a small increase in initial cost (sometimes zero), our planning strategies generate solutions that are often significantly less vulnerable to potential disruptions. We also consider the effect of lead time in being able to respond to the disruptions.
MSC:
| 90B06 | Transportation, logistics and supply chain management |
| 90B05 | Inventory, storage, reservoirs |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Software:
MIRPLibReferences:
| [1] | Ageeva, Y., Approaches to Incorporating Robustness into Airline Scheduling, (2000), Massachusetts Institute of Technology, Ph.D. thesis |
| [2] | Agra, A.; Andersson, H.; Christiansen, M.; Wolsey, L., A maritime inventory routing problem: discrete time formulations and valid inequalities, Networks, 62, 4, 297-314, (2013) · Zbl 1338.90016 |
| [3] | Agra, A.; Christiansen, M.; Delgado, A., Mixed integer formulations for a short sea fuel oil distribution problem, Transp. Sci., 47, 1, 108-124, (2013) |
| [4] | Agra, A.; Christiansen, M.; Delgado, A.; Hvattum, L. M., A maritime inventory routing problem with stochastic sailing and port times, Comput. Oper. Res., 61, 18-30, (2015) · Zbl 1348.90057 |
| [5] | Agra, A.; Christiansen, M.; Figueiredo, R.; Hvattum, L. M.; Poss, M.; Requejo, C., Layered formulation for the robust vehicle routing problem with time windows, Combinatorial Optimization, Second International Symposium, ISCO 2012, Athens, Greece, April 19-21, 2012, Revised Selected Papers, 249-260, (2012), Springer · Zbl 1370.90019 |
| [6] | Agra, A.; Christiansen, M.; Figueiredo, R.; M. Hvattum, L.; Poss, M.; Requejo, C., The robust vehicle routing problem with time windows, Comput. Oper. Res., 40, 856-866, (2013) · Zbl 1349.90152 |
| [7] | Ahmed, S.; Shapiro, A., The sample average approximation method for stochastic programs with integer recourse, Technical Report, ISyE, Georgia Tech, (2002) |
| [8] | Al-Khayyal, F.; Hwang, S.-J., Inventory constrained maritime routing and scheduling for multi-commodity liquid bulk, part i: applications and model, Eur. J. Oper. Res., 176, 1, 106-130, (2007) · Zbl 1137.90303 |
| [9] | Alvarez, J. F.; Tsilingiris, P.; Engebrethsen, E. S.; Kakalis, N. M., Robust fleet sizing and deployment for industrial and independent bulk Ocean shipping companies, INFOR, 49, 93-107, (2011) · Zbl 07683592 |
| [10] | Ben-Tal, A.; El Ghaoui, L.; Nemirovski, A., Robust optimization, (2009), Princeton University Press · Zbl 1221.90001 |
| [11] | Braaten, S.; Gjønnes, O.; Hvattum, L. M.; Tirado, G., Heuristics for the robust vehicle routing problem with time windows, Expert Syst. Appl., 77, 136-147, (2017) |
| [12] | Cacchiani, V.; Caprara, A.; Fischetti, M., A Lagrangian heuristic for robustness, with an application to train timetabling, Transp. Sci., 46, 124-133, (2012) |
| [13] | Chiraphadhanakul, V., Routing and Scheduling Models for Robust Allocation of Slack, (2010), Massachusetts Institute of Technology, Ph.D. thesis |
| [14] | Christiansen, M.; Fagerholt, K., Robust ship scheduling with multiple time windows, Nav. Res. Logist., 49, 611-625, (2002) · Zbl 1007.90504 |
| [15] | Christiansen, M.; Fagerholt, K.; Nygreen, B.; Ronen, D., Maritime transportation, Handbooks in Operations Research and Management Science, 189-284, (2007), Elsevier · Zbl 1142.91300 |
| [16] | Christiansen, M.; Fagerholt, K.; Ronen, D., Ship routing and scheduling: status and perspectives, Transp. Sci., 38, 1-18, (2004) |
| [17] | Fischetti, M.; Monaci, M., Light robustness, Robust and Online Large-Scale Optimization, 61-84, (2009), Springer · Zbl 1266.90196 |
| [18] | Gendreau, M.; Jabali, O.; Rei, W., 50th anniversary invited article - future research directions in stochastic vehicle routing, Transp. Sci., 50, 4, 1163-1173, (2016) |
| [19] | Halvorsen-Weare, E. E.; Fagerholt, K.; Rönnqvist, M., Vessel routing and scheduling under uncertainty in the liquefied natural gas business, Comput. Ind. Eng., 64, 290-301, (2013) |
| [20] | Held, M.; Wolfe, P.; Crowder, H. P., Validation of subgradient optimization, Math Program, 6, 62-88, (1974) · Zbl 0284.90057 |
| [21] | King, A. J.; Wallace, S. W., Modeling with stochastic programming, (2012), Springer Science & Business Media · Zbl 1248.90063 |
| [22] | Kleywegt, A. J.; Shapiro, A.; Homem-de Mello, T., The sample average approximation method for stochastic discrete optimization, SIAM J. Optim., 12, 2, 479-502, (2002) · Zbl 0991.90090 |
| [23] | Lan, S.; Clarke, J.-P.; Barnhart, C., Planning for robust airline operations: optimizing aircraft routings and flight departure times to minimize passenger disruptions, Transp. Sci., 40, 15-28, (2006) |
| [24] | Papageorgiou, D. J.; Cheon, M.-S.; Keha, A. B.; Nemhauser, G. L.; Sokol, J., Mirplib: A maritime inventory routing survey and instance library, (2012) |
| [25] | Papageorgiou, D. J.; Keha, A. B.; Nemhauser, G. L.; Sokol, J., Two-stage decomposition algorithms for single product maritime inventory routing, J. Comput., 26, 4, 825-847, (2014) · Zbl 1304.90020 |
| [26] | Persson, J. A.; Göthe-Lundgren, M., Shipment planning at oil refineries using column generation and valid inequalities, Eur. J. Oper. Res., 163, 3, 631-652, (2005) · Zbl 1071.90508 |
| [27] | Rakke, J.; Andersson, H.; Christiansen, M.; Desaulniers, G., Branch-price-and-cut for creating an annual delivery program of multi-product liquefied natural gas, Technical Report, (2012), Working Paper |
| [28] | Rakke, J.; Stålhane, M.; Moe, C.; Christiansen, M.; Andersson, H.; Fagerholt, K.; Norstad, I., A rolling horizon heuristic for creating a liquefied natural gas annual delivery program, Transp. Res. Part C, 19, 896-911, (2011) |
| [29] | Rocha, R.; Grossmann, I. E.; de Aragão, M. V.P., Cascading knapsack inequalities: reformulation of a crude oil distribution problem, Ann. Oper. Res., 203, 1, 217-234, (2013) · Zbl 1273.90178 |
| [30] | Ronen, D., The effect of oil price on the optimal speed of ships, J. Oper. Res. Society, 33, 1035-1040, (1982) |
| [31] | Rosenberger, J. M.; Johnson, E. L.; Nemhauser, G. L., Rerouting aircraft for airline recovery, Transp. Sci., 37, 408-421, (2003) |
| [32] | Rosenberger, J. M.; Johnson, E. L.; Nemhauser, G. L., A robust fleet-assignment model with hub isolation and short cycles, Transp. Sci., 38, 357-368, (2004) |
| [33] | Schaefer, A. J.; Johnson, E. L.; Kleywegt, A. J.; Nemhauser, G. L., Airline crew scheduling under uncertainty, Transp. Sci., 39, 340-348, (2005) |
| [34] | Schultz, R., Rates of convergence in stochastic programs with complete integer recourse, SIAM J. Optim., 6, 4, 1138-1152, (1996) · Zbl 0868.90088 |
| [35] | Shapiro, A.; Dentcheva, D.; Ruszczyński, A., Lectures on stochastic programming: modeling and theory, 9, (2009), Society for Industrial and Applied Mathematics · Zbl 1183.90005 |
| [36] | Shebalov, S.; Klabjan, D., Robust airline crew pairing: move-up crews, Transp. Sci., 40, 300-312, (2006) |
| [37] | Smith, B. C.; Johnson, E. L., Robust airline fleet assignment: imposing station purity using station decomposition, Transp. Sci., 40, 497-516, (2006) |
| [38] | Song, J.-H.; Furman, K. C., A maritime inventory routing problem: practical approach, Comput. Oper. Res., 40, 657-665, (2013) · Zbl 1349.90596 |
| [39] | Stålhane, M.; Rakke, J.; Moe, C.; Andersson, H.; Christiansen, M.; Fagerholt, K., A construction and improvement heuristic for a liquefied natural gas inventory routing problem, Comput. Ind. Eng., 62, 245-255, (2012) |
| [40] | Tirado, G.; Hvattum, L. M.; Fagerholt, K.; Cordeau, J.-F., Heuristics for dynamic and stochastic routing in industrial shipping, Comput. Oper. Res., 40, 1, 253-263, (2013) · Zbl 1349.90871 |
| [41] | Verweij, B.; Ahmed, S.; Kleywegt, A. J.; Nemhauser, G.; Shapiro, A., The sample average approximation method applied to stochastic routing problems: a computational study, Comput. Optim. Appl., 24, 2-3, 289-333, (2003) · Zbl 1094.90029 |
| [42] | Yen, J. W.; Birge, J. R., A stochastic programming approach to the airline crew scheduling problem, Transp. Sci., 40, 3-14, (2006) |
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.
