×

Industrial and tramp ship routing problems: closing the gap for real-scale instances. (English) Zbl 1441.90032

Summary: Recent studies in maritime logistics have introduced a general ship routing problem and a benchmark suite based on real shipping segments, considering pickups and deliveries, cargo selection, ship-dependent starting locations, travel times and costs, time windows, and incompatibility constraints, among other features. Together, these characteristics pose considerable challenges for exact and heuristic methods, and some cases with as few as 18 cargoes remain unsolved. To face this challenge, we propose an exact branch-and-price (B&P) algorithm and a hybrid metaheuristic. Our exact method generates elementary routes, but exploits decremental state-space relaxation to speed up column generation, heuristic strong branching, as well as advanced preprocessing and route enumeration techniques. Our metaheuristic is a sophisticated extension of the unified hybrid genetic search. It exploits a set-partitioning phase and uses problem-tailored variation operators to efficiently handle all the problem characteristics. As shown in our experimental analyses, the B&P optimally solves 239/240 existing instances within one hour. Scalability experiments on even larger problems demonstrate that it can optimally solve problems with around 60 ships and 200 cargoes (i.e., 400 pickup and delivery services) and find optimality gaps below 1.04% on the largest cases with up to 260 cargoes. The hybrid metaheuristic outperforms all previous heuristics and produces near-optimal solutions within minutes. These results are noteworthy, since these instances are comparable in size with the largest problems routinely solved by shipping companies.

MSC:

90B06 Transportation, logistics and supply chain management
90B35 Deterministic scheduling theory in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C59 Approximation methods and heuristics in mathematical programming
90C35 Programming involving graphs or networks

Software:

TaxiSimulation; VRP
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Andersson, H.; Christiansen, M.; Fagerholt, K., The maritime pickup and delivery problem with time windows and split loads, INFOR: Information Systems and Operational Research, 49, 2, 79-91 (2011) · Zbl 07683591
[2] Baldacci, R.; Mingozzi, A.; Roberti, R., New route relaxation and pricing strategies for the vehicle routing problem, Operations Research, 59, 5, 1269-1283 (2011) · Zbl 1233.90059
[3] Bertsimas, D.; Jaillet, P.; Martin, S., Online vehicle routing: The edge of optimization in large-scale applications, Operations Research, 67, 1, 143-162 (2019)
[4] Borthen, T.; Loennechen, H.; Wang, X.; Fagerholt, K.; Vidal, T., A genetic search-based heuristic for a fleet size and periodic routing problem with application to offshore supply planning, EURO Journal on Transportation and Logistics, 7, 2, 121-150 (2018)
[5] Brønmo, G.; Christiansen, M.; Fagerholt, K.; Nygreen, B., A multi-start local search heuristic for ship scheduling—a computational study, Computers & Operations Research, 34, 3, 900-917 (2007) · Zbl 1120.90031
[6] Brown, G. G.; Graves, G. W.; Ronen, D., Scheduling ocean transportation of crude oil, Management Science, 33, 3, 335-346 (1987)
[7] Bulhões, T.; Hà, M.; Martinelli, R.; Vidal, T., The vehicle routing problem with service level constraints, European Journal of Operational Research, 265, 2, 544-558 (2018) · Zbl 1374.90043
[8] Christiansen, M.; Fagerholt, K., Ship routing and scheduling in industrial and tramp shipping, (Toth, P.; Vigo, D., Vehicle routing (2014), Society for Industrial and Applied Mathematics), 381-408
[9] Christiansen, M.; Fagerholt, K.; Nygreen, B.; Ronen, D., Maritime transportation, (Barnhart, C.; Laporte, G., Transportation (2007), Elsevier), 189-284
[10] Christiansen, M.; Fagerholt, K.; Nygreen, B.; Ronen, D., Ship routing and scheduling in the new millennium, European Journal of Operational Research, 228, 3, 467-483 (2013) · Zbl 1317.90112
[11] Christofides, N.; Mingozzi, A.; Toth, P., Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations, Mathematical Programming, 20, 255-282 (1981) · Zbl 0461.90067
[12] Contardo, C.; Martinelli, R., A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints, Discrete Optimization, 12, 129-146 (2014) · Zbl 1308.90144
[13] Desaulniers, G.; Lessard, F.; Hadjar, A., Tabu search, partial elementarity, and generalized k-path inequalities for the vehicle routing problem with time windows, Transportation Science, 42, 3, 387-404 (2008)
[14] Duhamel, C.; Lacomme, P.; Prodhon, C., Efficient frameworks for greedy split and new depth first search split procedures for routing problems, Computers & Operations Research, 38, 4, 723-739 (2011) · Zbl 1202.90028
[15] Dumas, Y.; Desrosiers, J.; Soumis, F., The pickup and delivery problem with time windows, European Journal of Operational Research, 54, 1, 7-22 (1991) · Zbl 0736.90028
[16] Fagerholt, K., A computer-based decision support system for vessel fleet scheduling - Experience and future research, Decision Support Systems, 37, 1, 35-47 (2004)
[17] Fagerholt, K.; Christiansen, M., A combined ship scheduling and allocation problem, Journal of the Operational Research Society, 51, 7, 834-842 (2000) · Zbl 1055.90549
[18] Fagerholt, K.; Christiansen, M., A travelling salesman problem with allocation, time window and precedence constraints â an application to ship scheduling, International Transactions in Operational Research, 7, 3, 231-244 (2000)
[19] Glover, F.; Hao, J.-K., The case for strategic oscillation, Annals of Operations Research, 183, 1, 163-173 (2009) · Zbl 1214.90097
[20] Gschwind, T.; Irnich, S.; Rothenbcher, A.-K.; Tilk, C., Bidirectional labeling in column-generation algorithms for pickup-and-delivery problems, European Journal of Operational Research, 266, 2, 521-530 (2018) · Zbl 1403.90114
[21] Hemmati, A.; Hvattum, L. M., Evaluating the importance of randomization in adaptive large neighborhood search, International Transactions in Operational Research, 24, 5, 929-942 (2016) · Zbl 1371.90142
[22] Hemmati, A.; Hvattum, L. M.; Fagerholt, K.; Norstad, I., Benchmark suite for industrial and tramp ship routing and scheduling problems, INFOR: Information Systems and Operational Research, 52, 1, 28-38 (2014) · Zbl 07683730
[23] Jepsen, M.; Petersen, B.; Spoorendonk, S.; Pisinger, D., Subset-row inequalities applied to the vehicle-routing problem with time windows, Operations Research, 56, 2, 497-511 (2008) · Zbl 1167.90413
[24] Korsvik, J. E.; Fagerholt, K.; Laporte, G., A tabu search heuristic for ship routing and scheduling, Journal of the Operational Research Society, 61, 4, 594-603 (2009)
[25] Korsvik, J. E.; Fagerholt, K.; Laporte, G., A large neighbourhood search heuristic for ship routing and scheduling with split loads, Computers & Operations Research, 38, 2, 474-483 (2011) · Zbl 1231.90093
[26] Martinelli, R.; Pecin, D.; Poggi, M., Efficient elementary and restricted non-elementary route pricing, European Journal of Operational Research, 239, 1, 102-111 (2014) · Zbl 1339.90061
[27] Muter, I.; Birbil, S.; Sahin, G., Combination of metaheuristic and exact algorithms for solving set covering-type optimization problems, INFORMS Journal on Computing, 22, 4, 603-619 (2010) · Zbl 1243.90257
[28] Nagata, Y.; Bräysy, O.; Dullaert, W., A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows, Computers & Operations Research, 37, 4, 724-737 (2010) · Zbl 1175.90046
[29] Pecin, D.; Contardo, C.; Desaulniers, G.; Uchoa, E., New enhancements for the exact solution of the vehicle routing problem with time windows, INFORMS Journal on Computing, 29, 3, 489-502 (2017) · Zbl 1378.90027
[30] Prins, C., A simple and effective evolutionary algorithm for the vehicle routing problem, Computers & Operations Research, 31, 12, 1985-2002 (2004) · Zbl 1100.90504
[31] Prins, C.; Labadi, N.; Reghioui, M., Tour splitting algorithms for vehicle routing problems, International Journal of Production Research, 47, 2, 507-535 (2009) · Zbl 1231.90388
[32] Righini, G.; Salani, M., New dynamic programming algorithms for the resource constrained elementary shortest path problem, Networks, 51, 3, 155-170 (2008) · Zbl 1144.90514
[33] Ronen, D., Cargo ships routing and scheduling: survey of models and problems, European Journal of Operational Research, 12, 2, 119-126 (1983)
[34] Ropke, S.; Cordeau, J.-F., Branch and cut and price for the pickup and delivery problem with time windows, Transportation Science, 43, 3, 267-286 (2009)
[35] L-2017-7
[36] Sigurd, M. M.; Ulstein, N. L.; Nygreen, B.; Ryan, D. M., Ship scheduling with recurring visits and visit separation requirements, (Desaulniers, G.; Desrosiers, J.; Solomon, M. M., Column generation (2005), Springer US: Springer US Boston, MA), 225-245 · Zbl 1246.90065
[37] Stålhane, M.; Andersson, H.; Christiansen, M.; Cordeau, J.-F.; Desaulniers, G., A branch-price-and-cut method for a ship routing and scheduling problem with split loads, Computers & Operations Research, 39, 12, 3361-3375 (2012) · Zbl 1349.90129
[38] Subramanian, A.; Uchoa, E.; Ochi, L. S., A hybrid algorithm for a class of vehicle routing problems, Computers & Operations Research, 40, 10, 2519-2531 (2013) · Zbl 1348.90132
[39] Accessed 6 September 2018
[40] Velasco, N.; Castagliola, P.; Dejax, P.; Guéret, C.; Prins, C., A memetic algorithm for a pick-up and delivery problem by helicopter, (Pereira, F. B.; Tavares, J., Bio-inspired algorithms for the vehicle routing problem (2009), Springer Berlin Heidelberg), 173-190
[41] Vidal, T., Technical note: Split algorithm in O(n) for the capacitated vehicle routing problem, Computers & Operations Research, 69, 40-47 (2016) · Zbl 1349.90136
[42] Vidal, T.; Crainic, T. G.; Gendreau, M.; Lahrichi, N.; Rei, W., A hybrid genetic algorithm for multidepot and periodic vehicle routing problems, Operations Research, 60, 3, 611-624 (2012) · Zbl 1260.90058
[43] Vidal, T.; Crainic, T. G.; Gendreau, M.; Prins, C., A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows, Computers & Operations Research, 40, 1, 475-489 (2013) · Zbl 1349.90137
[44] Vidal, T.; Crainic, T. G.; Gendreau, M.; Prins, C., A unified solution framework for multi-attribute vehicle routing problems, European Journal of Operational Research, 234, 3, 658-673 (2014) · Zbl 1304.90004
[45] Vidal, T.; Crainic, T. G.; Gendreau, M.; Prins, C., Time-window relaxations in vehicle routing heuristics, Journal of Heuristics, 21, 3, 329-358 (2015)
[46] Vidal, T.; Crainic, T. G.; Gendreau, M.; Prins, C., Timing problems and algorithms: time decisions for sequences of activities, Networks, 65, 2, 102-128 (2015) · Zbl 1390.90486
[47] Vidal, T.; Maculan, N.; Ochi, L.; Penna, P., Large neighborhoods with implicit customer selection for vehicle routing problems with profits, Transportation Science, 50, 2, 720-734 (2016)
[48] Wilson (2018). Accessed: 2018-09-06 https://www.wilsonship.no/en.
[49] Zachariadis, E.; Kiranoudis, C., A strategy for reducing the computational complexity of local search-based methods for the vehicle routing problem, Computers & Operations Research, 37, 12, 2089-2105 (2010)
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.