×

A branch-price-and-cut method for a ship routing and scheduling problem with split loads. (English) Zbl 1349.90129

Summary: We present a branch-price-and-cut method to solve a maritime pickup and delivery problem with time windows and split loads. The fleet of ships is heterogeneous and fixed for the planning horizon, and no common depot exists. The cargoes picked up and delivered consist of both mandatory and optional cargoes, and each cargo may be split among several ships. The objective is to design a route for each ship that will maximize the total profit from transporting all the mandatory and a subset of the optional cargoes. To solve this problem we introduce a new path-flow formulation, which we solve by branch-price-and-cut. The subproblem is a new variant of the elementary shortest path problem with resource constraints, where a multi-dimensional knapsack problem is solved to compute optimal cargo quantities. Further, we present new valid inequalities for this problem, and adaptations of existing inequalities successfully used to solve related problems in the literature. Finally, the computational results show that for certain types of instances, our solution method outperforms existing methods proposed in the literature.

MSC:

90B06 Transportation, logistics and supply chain management
90B35 Deterministic scheduling theory in operations research
90B80 Discrete location and assignment
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andersson, H.; Christiansen, M.; Fagerholt, K., The maritime pickup and delivery problem with time windows and split loads, Information Systems and Operational Research, 49, 79-91 (2011) · Zbl 07683591
[2] Archetti, C.; Bouchard, M.; Desaulniers, G., Enhanced branch and price and cut for vehicle routing with split deliveries and time windows, Transportation Science, 45, 3, 285-298 (2011)
[3] Archetti, C.; Savelsbergh, M. W.P.; Speranza, M. G., Worst-case analysis for split delivery vehicle routing problems, Transportation Science, 40, 2, 226-234 (2006)
[4] Archetti, C.; Savelsbergh, M. W.P.; Speranza, M. G., To split or not to split: that is the question, Transportation Research Part E, 44, 1, 114-123 (2008)
[5] Barnhart, C.; Johnson, E. L.; Nemhauser, G. L.; Savelsbergh, M. P.W.; Vance, P. H., Branch-and-price: column generation for solving huge integer programs, Operations Research, 46, 3, 316-329 (1998) · Zbl 0979.90092
[6] Belenguer, J. M.; Martinez, M. C.; Mota, E., A lower bound for the split delivery vehicle routing problem, Operations Research, 48, 5, 801-810 (2000) · Zbl 1106.90380
[7] Berbeglia, G.; Cordeau, J.-F.; Gribkovskaia, I.; Laporte, G., Static pickup and delivery problems: a classification scheme and survey, TOP, 15, 1-31 (2007) · Zbl 1121.90001
[8] Christiansen, M.; Fagerholt, K.; Nygreen, B.; Ronen, D., Maritime transportation, (Barnhart, C.; Laporte, G., Transportation. Handbooks in operations research and management science, vol. 14 (2007), Elsevier Science), 189-284
[9] Christiansen, M.; Fagerholt, K.; Ronen, D., Ship routing and scheduling: status and perspectives, Transportation Science, 38, 1, 1-18 (2004)
[10] Desaulniers, G., Branch-and-price-and-cut for the split delivery vehicle routing problem with time windows, Operations Research, 33, 1, 3-14 (2009)
[11] Desrosiers, J.; Dumas, Y.; Solomon, M.; Soumis, F., Time constrained routing and scheduling, (Ball, M.; Magnanti, T.; Monma, C.; Nemhauser, G., Network routing. Handbooks in operations research and management science, vol. 8 (1995), Elsevier Science), 35-139 · Zbl 0861.90052
[12] Dror, M.; Laporte, G.; Trudeau, P., Vehicle routing with split deliveries, Discrete Applied Mathematics, 50, 239-254 (1994) · Zbl 0801.90082
[13] Dror, M.; Trudeau, P., Savings by split delivery routing, Transportation Science, 23, 2, 141-145 (1989) · Zbl 0668.90044
[14] Dumas, Y.; Desrosiers, J.; Soumis, F., The pickup and delivery problem with time windows, European Journal of Operational Research, 54, 7-22 (1991) · Zbl 0736.90028
[15] Frizzel, P. W.; Griffin, J. W., The bounded split delivery vehicle routing problem with grid network distances, Asia-Pacific Journal of Operational Research, 9, 1, 101-116 (1995)
[16] Frizzel, P. W.; Griffin, J. W., The split delivery scheduling problem with time windows and split deliveries, Computers & Operations Research, 22, 6, 655-667 (1995) · Zbl 0827.90072
[17] Gendreau M, Dejax P, Feillet D, Gueguen C. Vehicle routing with time windows and split deliveries. Working paper, CIRRELT, Canada; 2010.; Gendreau M, Dejax P, Feillet D, Gueguen C. Vehicle routing with time windows and split deliveries. Working paper, CIRRELT, Canada; 2010. · Zbl 1056.90014
[18] Ho, S. C.; Haugland, D., A tabu search heuristic for the vehicle routing problem with time windows and split deliveries, Computers Operations & Research, 31, 12, 1947-1964 (2009) · Zbl 1074.68614
[19] Irnich, S.; Desaulniers, G., Shortest path problems with resource constraints, (Desaulniers, G.; Desrosiers, J.; Solomon, M., Column generation. GERAD 25th anniversary series (2005), Springer), 33-65 · Zbl 1130.90315
[20] Jin, M.; Liu, K.; Bowdon, R. O., A two-stage algorithm with valid inequalities for the split delivery vehicle routing problem, International Journal of Production Economics, 105, 228-242 (2007)
[21] Jin, M.; Liu, K.; Eksioglu, B., A column generation approach for the split delivery vehicle routing problem, Operations Research Letters, 36, 265-270 (2008) · Zbl 1144.90339
[22] Korsvik, J.; Fagerholt, K.; Laporte, G., A large neighborhood search heuristic for ship routing and scheduling with split loads, Computers & Operations Research, 38, 2, 474-483 (2011) · Zbl 1231.90093
[23] Lawrence, S. A., International sea transport: the years ahead (1972), Lexington Books: Lexington Books Lexington, MA
[24] Lee, C. G.; Epelman, M. A.; White, C. C.; Bozer, Y. A., A shortest path approach to the multiple-vehicle routing problem with split pick-ups, Transportation Research Part B, 40, 265-284 (2006)
[25] Nowak, M.; Ergun, O.; White, C. C., Pickup and delivery with split loads, Transportation Science, 42, 1, 32-43 (2008)
[26] Røpke, 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)
[27] Savelsbergh, M.; Sol, M., Drive: dynamic routing of independent vehicles, Operations Research, 46, 474-490 (1998) · Zbl 0987.90511
[28] Sierksma, G.; Tijssen, G. A., Routing helicopters for crew exchanges on off-shore locations, Annals of Operations Research, 76, 261-286 (1997) · Zbl 0895.90133
[29] UNCTAD, Review of maritime transportation. Technical report, United Nations, New York and Geneva; 2008.; UNCTAD, Review of maritime transportation. Technical report, United Nations, New York and Geneva; 2008.
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.