×

Heuristics for dynamic and stochastic routing in industrial shipping. (English) Zbl 1349.90871

Summary: Maritime transportation plays a central role in international trade, being responsible for the majority of long-distance shipments in terms of volume. One of the key aspects in the planning of maritime transportation systems is the routing of ships. While static and deterministic vehicle routing problems have been extensively studied in the last decades and can now be solved effectively with metaheuristics, many industrial applications are both dynamic and stochastic. In this spirit, this paper addresses a dynamic and stochastic maritime transportation problem arising in industrial shipping. Three heuristics adapted to this problem are considered and their performance in minimizing transportation costs is assessed. Extensive computational experiments show that the use of stochastic information within the proposed solution methods yields average cost savings of 2.5% on a set of realistic test instances.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
90B06 Transportation, logistics and supply chain management
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Azaron, A.; Kianfar, F., Dynamic shortest path in stochastic dynamic networks: ship routing problem, European Journal of Operational Research, 144, 138-156 (2003) · Zbl 1037.90053
[2] Bent, R. W.; Van Hentenryck, P., Scenario-based planning for partially dynamic vehicle routing with stochastic customers, Operations Research, 52, 977-987 (2004) · Zbl 1165.90600
[3] Berbeglia, G.; Cordeau, J.-F.; Laporte, G., Dynamic pickup and delivery problems, European Journal of Operational Research, 202, 8-15 (2010) · Zbl 1176.90048
[4] Bertsimas, D. J.; Simchi-Levi, D., A new generation of vehicle routing research: robust algorithms, addressing uncertainty, Operations Research, 44, 286-304 (1996) · Zbl 0855.90053
[5] Bullo, F.; Frazzoli, E.; Pavone, M.; Savla, K.; Smith, S. L., Dynamic vehicle routing for robotic systems, Proceedings of the IEEE, 99, 1482-1504 (2011)
[6] Cheng, L.; Duran, M. A., Logistics for world-wide crude oil transportation using discrete event simulation and optimal control, Computers and Chemical Engineering, 28, 897-911 (2004)
[7] Christiansen, M.; Fagerholt, K.; Ronen, D., Ship routing and scheduling: status and perspectives, Transportation Science, 38, 1-18 (2004)
[8] Christiansen, M.; Fagerholt, K.; Nygreen, B.; Ronen, D., Maritime transportation, (Barnhart, C.; Laporte, G., Handbooks in operations research and management science (2007), Elsevier: Elsevier Amsterdam), 189-284
[9] Cordeau, J.-F.; Laporte, G.; Mercier, A., A unified tabu search heuristic for vehicle routing problems with time windows, Journal of the Operational Research Society, 52, 928-936 (2001) · Zbl 1181.90034
[10] Fagerholt, K., A computer-based decision support system for vessel fleet scheduling—experience and future research, Decision Support Systems, 37, 35-47 (2004)
[11] Fagerholt, K.; Lindstad, H., TurboRouter: an interactive optimisation-based decision support system for ship routing and scheduling, Maritime Economics and Logistics, 9, 214-233 (2007)
[12] Flatberg, T.; Hasle, G.; Kloster, O.; Nilssen, E. J.; Riise, A., Dynamic and stochastic vehicle routing in practice, (Zeimpekis, V. S.; Tarantilis, C. D.; Giaglis, G. M.; Minis, I. E., Dynamic fleet management: concepts, systems, algorithms & case studies. Operations research computer science interfaces series, vol. 38 (2007), Springer: Springer New York), 41-64, [chapter 3]
[13] Gendreau, M.; Laporte, G.; Séguin, R., Stochastic vehicle routing, European Journal of Operational Research, 88, 3-12 (1996) · Zbl 0913.90094
[14] Gendreau, M.; Guertin, F.; Potvin, J.-Y.; Séguin, R., Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries, Transportation Research Part C, 14, 157-174 (2006)
[15] Ghiani, G.; Guerriero, F.; Laporte, G.; Musmanno, R., Real-time vehicle routing: solution concepts, algorithms and parallel computing strategies, European Journal of Operational Research, 151, 1-11 (2003) · Zbl 1033.90014
[16] Hvattum, L. M.; Løkketangen, A.; Laporte, G., Solving a dynamic and stochastic vehicle routing problem with a sample scenario hedging heuristic, Transportation Science, 40, 421-438 (2006)
[17] Hvattum, L. M.; Løkketangen, A.; Laporte, G., A branch-and-regret heuristic for stochastic and dynamic vehicle routing problems, Networks, 49, 330-340 (2007) · Zbl 1141.90337
[18] Hwang, H.-S.; Visoldilokpun, S.; Rosenberger, J. M., A branch-and-price-and-cut method for ship scheduling with limited risk, Transportation Science, 42, 336-351 (2008)
[19] Ichoua, S.; Gendreau, M.; Potvin, J.-Y., Exploiting knowledge about future demands for real-time vehicle dispatching, Transportation Science, 40, 211-225 (2006)
[20] Jaillet, P.; Lu, X., Online traveling salesman problems with service flexibility, Networks, 58, 137-146 (2011) · Zbl 1229.90164
[21] Kang, M. H.; Choi, H. R.; Kim, H. S.; Park, B. J., Development of a maritime transportation planning support system for car carriers based on genetic algorithm, Applied Intelligence, 36, 585-604 (2012)
[22] Korsvik, J. E.; Fagerholt, K.; Laporte, G., A tabu search heuristic for ship routing and scheduling, Journal of the Operational Research Society, 61, 594-603 (2010)
[23] Lo, H. K.; McCord, M. R., Adaptive ship routing through stochastic ocean currents: general formulations and empirical results, Transportation Research Part A, 32, 547-561 (1998)
[24] Madsen, O. B.G.; Ravn, H. F.; Rygaard, J. M., A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities and multiple objectives, Annals of Operations Research, 60, 193-208 (1995) · Zbl 0839.90033
[25] Mitrović-Minić, S.; Laporte, G., Waiting strategies for the dynamic pickup and delivery problem with time windows, Transportation Research Part B, 38, 635-655 (2004)
[26] Mitrović-Minić, S.; Krishnamurti, R.; Laporte, G., Double horizon based heuristics for the dynamic pickup and delivery problem with time windows, Transportation Research Part B, 38, 669-685 (2004)
[27] Powell, W. B., A stochastic formulation of the dynamic assignment problem, with an application to truckload motor carriers, Transportation Science, 30, 195-219 (1996) · Zbl 0884.90078
[28] Psaraftis, H. N., Dynamic vehicle routing problems, (Golden, B. L.; Assad, A. A., Vehicle routing: methods and studies (1988), North-Holland: North-Holland Amsterdam), 223-248
[29] Psaraftis, H. N., Dynamic vehicle routing: status and prospects, Annals of Operations Research, 61, 143-164 (1995) · Zbl 0839.90037
[30] Ronen, D., Cargo ships routing and scheduling: survey of models and problems, European Journal of Operational Research, 12, 119-126 (1983)
[31] Ronen, D., Ship scheduling: the last decade, European Journal of Operational Research, 71, 325-333 (1993) · Zbl 0800.90568
[32] Savelsbergh, M. W.P.; Sol, M., DRIVE: dynamic routing of independent vehicles, Operations Research, 46, 474-490 (1998) · Zbl 0987.90511
[33] Schilde, M.; Doerner, K. F.; Hartl, R. F., Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports, Computers and Operations Research, 38, 1719-1730 (2011) · Zbl 1215.90014
[34] Secomandi, N.; Margot, F., Reoptimization approaches for the vehicle-routing problem with stochastic demands, Operations Research, 57, 214-230 (2009) · Zbl 1181.90043
[35] Swihart, M. R.; Papastavrou, J. D., A stochastic and dynamic model for the single-vehicle pick-up and delivery problem, European Journal of Operational Research, 114, 447-464 (1999) · Zbl 0949.90006
[36] Thomas, B. W., Waiting strategies for anticipating service requests from known customer locations, Transportation Science, 41, 319-331 (2007)
[38] Van Hentenryck, P.; Bent, R. W.; Upfal, E., Online stochastic optimization under time constraints, Annals of Operations Research, 177, 151-183 (2010) · Zbl 1229.90112
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.