Tramp ship routing and scheduling with voyage separation requirements
Tóm tắt
In this paper we explore tramp ship routing and scheduling. Tramp ships operate much like taxies following the available demand. Tramp operators can determine some of their demand in advance by entering into long-term contracts and then try to maximise profits from optional voyages found in the spot market. Routing and scheduling a tramp fleet to best utilise fleet capacity according to current demand is therefore an ongoing and complicated problem. Here we add further complexity to the routing and scheduling problem by incorporating voyage separation requirements that enforce a minimum time spread between some voyages. The incorporation of these separation requirements helps balance the conflicting objectives of maximising profit for the tramp operator and minimising inventory costs for the charterer, since these costs increase if similar voyages are not performed with some separation in time. We have developed a new and exact branch-and-price procedure for this problem. We use a dynamic programming algorithm to generate columns and describe a time window branching scheme used to enforce the voyage separation requirements which we relax in the master problem. Computational results show that our algorithm in general finds optimal solutions very quickly and performs much faster compared to an earlier a priori path generation method. Finally, we compare our method to an earlier adaptive large neighbourhood search heuristic and find that on similar-sized instances our approach generally uses less time to find the optimal solution than the adaptive large neighbourhood search method uses to find a heuristic solution.
Tài liệu tham khảo
Andersson H, Duesund JM, Fagerholt K (2011) Ship routing and scheduling with cargo coupling and synchronization constraints. Comput Ind Eng 61(4):1107–1116
Bakkehaug R, Rakke JG, Fagerholt K, Laporte G (2016) An adaptive large neighborhood search heuristic for fleet deployment problems with voyage separation requirements. Transp Res C Emerg Technol 70:129–141
Christiansen M, Fagerholt K, Ronen D (2004) Ship routing and scheduling: status and perspectives. Transp Sci 38(1):1–18
Christiansen M, Fagerholt K, Nygreen B, Ronen D (2007) Maritime transportation. In: Barnhart C, Laporte G (eds) Transport. Handbooks in operations research and management science, vol 14. Elsevier, North-Holland, Amsterdam, pp 189–284
Christiansen M, Fagerholt K, Nygreen B, Ronen D (2013) Ship routing and scheduling in the new millennium. Eur J Oper Res 228(3):467–483
Conforti M, Cornuéjols G, Kapoor A, Vušković K (2001) Perfect, ideal and balanced matrices. Eur J Oper Res 133(3):455–461
Cordeau J-F, Desaulniers G, Desrosiers J, Solomon MM, Soumis F (2002) VRP with time windows. In: Toth P, Vigo D (eds) The vehicle routing problem, chap. Society for Industrial and Applied Mathematics, Philadelphia, pp 157–194
Desaulniers G, Desrosiers J, Solomon MM (eds) (2005) Column generation. Springer, New York
Desrochers M, Soumis F (1988) A reoptimization algorithm for the shortest path problem with time windows. Eur J Oper Res 35:242–254
Dohn A, Rasmussen MS, Larsen J (2011) The vehicle routing problem with time windows and temporal dependencies. Networks 58(4):273–289
Drexl M (2013) Applications of the vehicle routing problem with trailers and transshipments. Eur J Oper Res 227(2):275–283
Dror M (1994) Note on the complexity of the shortest path models for column generation in vrptw. Oper Res 42(5):977–978
Gélinas S, Desrochers M, Desrosiers J, Solomon MM (1995) A new branching strategy for time constrained routing problems with application to backhauling. Ann Oper Res 61:91–109
Hemmati A, Stålhane M, Hvattum LM, Andersson H (2015) An effective heuristic for solving a combined cargo and inventory routing problem in tramp shipping. Comput Oper Res 64:274–282
Irnich S (2008) Resource extension functions: properties, inversion, and generalization to segments. OR Spectrum 30(1):113–148
Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. In: Desaulniers G, Desrosiers J, Solomon MM (eds) Column generation, chap 2. Springer, New York, pp 33–66
Norstad I, Fagerholt K, Hvattum LM, Arnulf HS, BjØrkli A (2015) Maritime fleet deployment with voyage separation requirements. Flex Serv Manuf J 27(2–3):180–199
Padberg M (1973) On the facial structure of set packing polyhedra. Math Program 5(1):199–215
Rasmussen MS, Justesen T, Dohn A, Larsen J (2012) The home care crew scheduling problem: preference-based visit clustering and temporal dependencies. Eur J Oper Res 219:598–610
Reinhardt LB, Clausen T, Pisinger D (2013) Synchronized dial-a-ride transportation of disabled passengers at airports. Eur J Oper Res 225(1):106–117
Ronen D (1983) Cargo ships routing and scheduling: survey of models and problems. Eur J Oper Res 12(2):119–126
Ronen D (1993) Ship scheduling: the last decade. Eur J Oper Res 71(3):325–333
Ryan DM, Foster B (1981) An integer programming approach to scheduling. Computer scheduling of public transport. Urban passenger vehicle and crew scheduling. In: Proceedings of an international workshop, pp 269–280
Sigurd MM, Ulstein NL, Nygreen B, Ryan DM (2005) Ship scheduling with recurring visits and visit separation requirements. In: Desaulniers G, Desrosiers J, Solomon MM (eds) Column generation. Springer, New York, pp 225–245
Steinzen I, Suhl L, Kliewer N (2009) Branching strategies to improve regularity of crew schedules in ex-urban public transit. OR Spectrum 31(4):727–743
Stålhane M, Andersson H, Christiansen M, Fagerholt K (2014) Vendor managed inventory in tramp shipping. Omega (United Kingdom) 47:60–72
Stålhane M, Andersson H, Christiansen M (2015) A branch-and-price method for a ship routing and scheduling problem with cargo coupling and synchronization constraints. EURO J Transp Logist 4(4):421–443
UNCTAD. Review of maritime transport 2013 (2013). http://unctad.org/en/PublicationsLibrary/rmt2013_en.pdf
Vilhelmsen C, Larsen J, Lusby RM (2015) Tramp ship routing and scheduling—models, methods and opportunities. Technical Report, Department of Management Engineering, Technical University of Denmark
Vilhelmsen C (2014) Tramp ship routing and scheduling—incorporating additional complexities. Ph.D. thesis, Technical University of Denmark. Available via findit.dtu.dk