Metaheuristic algorithm for ship routing and scheduling problems with time window

Alhamad, Khaled; Alrashidi, Azizah; Alkharashi, Sameh Article Metaheuristic algorithm for ship routing and scheduling problems with time window Cogent Business & Management Provided in Cooperation with: Taylor & Francis Group Suggested Citation: Alhamad, Khaled; Alrashidi, Azizah; Alkharashi, Sameh (2019) : Metaheuristic algorithm for ship routing and scheduling problems with time window, Cogent Business & Management, ISSN 2331-1975, Taylor & Francis, Abingdon, Vol. 6, pp. 1-16, https://doi.org/10.1080/23311975.2019.1616351 This Version is available at: https://hdl.handle.net/10419/206184 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by/4.0/ OPERATIONS, INFORMATION & TECHNOLOGY | RESEARCH ARTICLE Metaheuristic algorithm for ship routing and scheduling problems with time window Khaled Alhamad 1 *, Azizah Alrashidi 1 and Sameh Alkharashi 1 Abstract: This paper describes a Tabu Search (TS) heuristic for a Ship Routing and Scheduling Problem (SRSP). The method was developed to address the problem of loading cargos for many customers using heterogeneous ships. Constraints include delivery time windows imposed by customers, the time horizon by which all deliveries must be made, and ship capacities. The proposed algorithm aims to minimize the overall cost of shipping operation without any violations. The TS algorithm is compared with a similar method that uses the Set Partitioning Problem (SPP) in terms of solution quality and computational time. The results of a computational investigation are presented. Solution quality and execution time are explored with respect to problem size and parameters controlling the TS such neighborhood size. It is found that while the SPP method solves small-scale problems efficiently, treating large-scale problems with this method becomes complicated due to computational problems; however, the TS method can overcome this challenge. Furthermore, TS consistently returns near-optimal solution within a reasonable time. Subjects: Operational Mathematics; Optimization; Computational Logic Keywords: Maritime transportation; scheduling; routing; tabu search; integer programming 1. Introduction The steady growth in international trade over many years has resulted in an increased need for freight transportation. Maritime transportation is the major conduit of international trade, where it plays a key role in international trade as it represents low-cost transportation for high volume and long-distance shipments. The statistics provided by the United Nations Conference on Trade and Development UNCTAD (U. Nation, 2016) show that the world economy heavily depends on seaborne trade. Seaborne trade supports production, trade, and consumption activities by guaranteeing the efficient movement and timely availability of raw materials ABOUT THE AUTHOR Khaled Alhamad is currently an associate professor, PhD and Head of Laboratory Technology Department, College of Technological Studies, Kuwait. His research interests include optimization, integer programming, heuristic method, scheduling, transportation. PUBLIC INTEREST STATEMENT This paper talks about the problem of scheduling the movement of vessels overseas to deliver goods of specific types (such as crude oil or coal) to customers, in the time required by the customer. On the other hand, to reduce the expenses of the movement of the fleet to the lowest possible. These expenses include fuel costs (bunker consumption), operation costs, and port dues. A mathematical algorithm tool called Tabu Search (TS) was presented to create a schedule for a fleet of vessels that could deliver goods to customers in a timely and cost-effective manner. Alhamad et al., Cogent Business & Management (2019), 6: 1616351 https://doi.org/10.1080/23311975.2019.1616351 © 2019 The Author(s). This open access article is distributed under a Creative Commons Attribution (CC-BY) 4.0 license. Received: 13 July 2018 Accepted: 28 April 2019 First Published: 13 May 2019 *Corresponding author: Khaled Alhamad, Technological Science Department, College of Technological Studies, Shuwaikh, Kuwait E-mail: [email protected] Reviewing editor: Jingxin Dong, United Kingdom Additional information is available at the end of the article Page 1 of 16 and finished goods. According to the statistics provided in (U. Nation, 2016)(seeTable1), the total international maritime transportation has increased greatly in terms of weight since 1970. This increase in maritime trade has resulted in parallel growth in the world maritime fleet. Ships operate under different conditions than other transportation modes. Christiansen et al. (Christiansen, Fagerholt, & Ronen, 2004) presented these differences: (1) ships pay port dues, (2) ships can be diverted at sea, and (3) a ship’sjourneytakesdaysorweeks. Conversely, ships and aircraft share a higher uncertainty in their operations because of their dependence on weather conditions and technology. Therefore, the operational environment of ships differs from the other transportation modes, and ships have different routing and scheduling problems. Christiansen et al. (Christiansen et al., 2004) presented a summary of these differences among other freight shipping modes. Christiansen et al. (Christiansen, Fagerholt, Nygreen, & Ronen, 2013) also presented the most recent review of ship routing and scheduling, where research on ship routing and scheduling problems during the new millennium is reviewed. Certain highlights are that the number of papers doubles every decade, and research on marine inventory routing, liner shipping, and optimal speed is leading the research efforts. The Ship Routing and Scheduling Problem (SRSP) addressed in this paper involves routing a fleet of controlled and chartered ships, with limited heterogeneous capacities, from an origin to various port customers around the world with known demands and predefined time window constraints. The types of ship investigated in this research are bulk ships which transport raw materials such as iron ore and coal, or tanker ships which transport crude oil, chemicals, and petroleum products. The route cost of a ship consists of fuel costs (bunker consumption), operation costs, and port dues. The objective is to minimize the total cost of serving all cargos while violating no constraint. Routing and scheduling of ships requires a significant level of fleet management planning. Any significant improvement of routing and scheduling will result in substantial cost savings. Cho and Perakis (Cho & Perakis, 2001) presented a mixed integer programming model for the ship scheduling problem with a single loading port. Si-Hwa Kim and Kyung-keun Lee (Kim & Lee, 1997) considered the ship owner’s scheduling problem in bulk trade and solved it using a set-packing model. The model sought to maximize the net profit. Gatica and Miranda (Gatica & Miranda, 2011) developed a network-based model for the routing and scheduling of a heterogeneous fleet. The Table 1. World seaborne trade Year Total (all shipments) Millions of tons loaded 1970 2566 1980 3704 1990 4008 2000 5984 2006 7700 2007 8034 2008 8229 2009 7858 2010 8408 2011 8784 2012 9197 2013 9548 2014 9843 2015 10 047 Alhamad et al., Cogent Business & Management (2019), 6: 1616351 https://doi.org/10.1080/23311975.2019.1616351 Page 2 of 16 objective is to minimize the total operating cost of serving a set of trip cargo contracts considering time window constraints at both the origin and destination of cargos. Brønmo et al. (Brønmo, Christiansen, & Nygreen, 2007b) used integer programming to solve the problem. All feasible routes are generated priori, where the optimal cargo quantities are found by solving a linear programming problem. The solution for the SRSP is solved using a SPP. Brønmo et al. (Brønmo, Nygreen, & Lysgaard, 2010) used branch-and-price to generate columns during the solution process. Andersson et al. (Andersson, Duesund, & Aderholt, 2011) present a mathematical formulation for a tramp ship routing problem. The researchers proposed three alternative solution methods based on path flow formulations and a priori column generation, where the objective is to maximize the profit. All the above approaches are capable of producing feasible solutions for SRSP. However, the simplest problem in routing and scheduling has high computational complexity, as evidenced by solution times of exact algorithms. Therefore, due to the exponential size of the solution space, it is unlikely that these optimization procedures can be used for large-scale problems. Heuristic methods, such as Simulated Annealing (SA) (Kirkpatrick, Gelatt, & Vecchi, 1983), Genetic Algorithm (GA) (Holland, 1975), or Tabu Search (TS) (Glover, 1986), which produce optimal or near-optimal solutions with acceptable computational time, are attractive alternatives. To our knowledge, there is minimal research work on SRSP using heuristic methods; most published works focus on Vehicle Routing and Scheduling (VRS). Moon et al. (MoonCorrespondence, Qiu, & Wang, 2014) used the GA to address a tramp ship routing model of fleet deployment in a hub-and-spoke network. Many random generated problem instances were solved using a mathematical programme and the GA with local search. A comparison of the results showed the efficiency of the GA with local search. Alhamad et al. (Al-Hamad, Al-Ibrahim, & Al-Enezy, 2012) also addressed SRSP using GA. The representation of each chromosome is an integer string of the number of shipments in the problem, while each gene is the integer number of a specific ship assigned to that original shipment. The objective is to minimize the overall operation cost. Sherali et al. (Sherali, Al-Yakoop, & Hassan, 1999) presented an industrial SRSP, where the cargo owner controls the fleet of ships and no optional spot cargos, which makes it different from the paper presented here. The objective is to minimize the overall cost. Korsvik and Fagerholt (Korsvik & Fagerholt, 2010) used TS to solve ship the routing and scheduling encountered by many tramp shipping companies transporting bulk products, where the objective is to maximize the profit instead of minimizing the overall costs as in this paper. The researchers used TS to help the planner to determine the optimal cargo quantities in each route. The computational results showed that optimal or near-optimal solutions for real-life cases were produced within a reasonable time. The shipping operations planner needs to frequently reschedule within a very short time frame, since ocean shipping is a very dynamic business. The main contribution of this research is to develop an efficient TS algorithm for the SRSP with flexible cargo quantities and to serve all customers with no violation of the constraint and with minimum overall cost. Tabu search (TS), proposed and developed by Glover (Glover, 1986), is a memory-based search strategy that guides the local search to continue its search beyond the optimum local solution. This procedure occurs by storing the most recently visited solutions in a tabu list (forbidden list) for a number of iterations to prevent any repletion or cycling. The lifetime moves that remain in the tabu list is called tabu tenure, and it could be a variable or fixed size. The control rule to refresh the tabu list is first-in first-out for the moves that are entered into the tabu list. However, a specific move or solution can be overridden in the tabu list when the move leads to a solution better than any currently available solutions. This condition is called aspiration criteria. TS begins by generating an initial solution, and the investigation uses an insert and swap move to search an optimal or near optimal solution. Moreover, to improve the solution, intensification and diversification Alhamad et al., Cogent Business & Management (2019), 6: 1616351 https://doi.org/10.1080/23311975.2019.1616351 Page 3 of 16 mechanisms are used. Intensification more carefully explores the region that has previously been visited, while diversification forces the steering search to unexplored areas of the search space. To measure the quality of this TS heuristic method, an exact method is used by adapting the Set Partitioning Problem (SPP) for small-scale problems. This paper is arranged as follows: section 2presents a mathematical formulation of SRSP. Section 3provides information regarding using TS with insert and swap moves where intensification and diversification techniques are used. Section 4provides the methodology of the exact approach SPP. Overall computational results and analysis are presented and described in section 5. Finally, conclusions are provided in section 6. 2. Mathematical formulation The SRSP addressed here is defined as each of a given number of ships with different capacities that will serve one or more cargos on each trip, where each ship can make more than one trip within the time horizon, and where the route for a specific ship is the total of all trips the ship has made. The requirements of all cargos must be satisfied. Each cargo has an imposed delivery time window according to the agreed contract with the company. Unloading must occur within the delivery time window. If the ship arrives before the time window, it must wait until the start of the delivery time window before unloading. The objective function, which seeks to minimize the overall cost, considers all the transportation expenses, fuel consumption, crew wages, maintenance, fixed cost of chartered ship, and other expenses. This problem is defined formally as follows: NC is a set of vertices (cargos), i¼0;1; :::; NC fg ,where0 is the origin, and NC is the total number of cargos to be served. There is a set of ships, NS,whereNSv1 is the total number of controlled ships belonging to the company with different capacities and the same speed. NSv2is a fleet of chartered ships, where the company can resort to the market to charter if there are insufficient ships to deliver all cargos. It is assumed that all chartered ships will be available at the beginning of the schedule. The total number of all ships used is NS ¼NSv1þNSv2. Let schedule S¼ði;kÞ:i2NC;k2NSfg, which means that cargo iis served by ship k, where all constraints are satisfied. Consider, for example, 5 cargos are served using 2 ships, A and B, as shown in Figure 1. The route of ship A states that the ship loaded from the origin (zero) to serve cargo 3 then returns to the origin to load cargo 4 then returns to the origin. The route of ship B proceeds in the same manner as the route of ship A to serve cargos 1, 2, and 5. Cargo ican be served only once by ship kfrom either controlled or chartered ships. Ship capacities are different, and cargo ihas demand. This statement assumes that there is sufficient capacity available to satisfy all cargo demands. Each cargo has predefined time window. Time window constraints are presented by an earliest arrival time and a latest arrival time. 3. Tabu search The SRSP is solved using the TS method, proposed and developed by Glover (Sherali et al., 1999). The most important characteristic of TS is the use of memory for the solution to solve difficult problems. There are many techniques used in TS such as attributes, tabu list, tabu list size (tenure), intensification, diversification, neighborhood, and neighborhood size, move and evaluation of the move, all which are adapted in our approach. Parameters defining the neighborhood size N.size and the tabu list size are considered critical in terms of solution quality and computation time. The A A B B B Schedule 0 3 0 4 0 1 0 2 5 0 Figure 1. Example of schedule of 2 ships serving 5 cargos. Alhamad et al., Cogent Business & Management (2019), 6: 1616351 https://doi.org/10.1080/23311975.2019.1616351 Page 4 of 16 most important point in a TS is the need for experimentation to choose the best parameters and their values for each specific type of problem. The methodology of solving this problem begins by arranging all cargos in sequence according to their departure time from the origin to serve them. Therefore, the cargo with the earliest departure time will be considered cargo number one and so on for other cargos. Thereafter, an initial solution will be generated to begin seeking the solution. 3.1. Initial solution The initial solution sois constructed using a greedy algorithm, which is a practical and straightforward algorithm. A greedy algorithm is implemented by first selecting the lowest overall cost ship among all fleets of ships according to the operation cost. Second, a route is created for this ship starting from cargo number one. At the same time, all constraints are satisfied, such as capacity and delivery time window. Once the first selected ship has finished, the same procedure for the second cheapest cost overall ship will be implemented, until no cargo remains. Any remaining cargo will be assigned to spot the ship, which is costly. Greedy Algorithm. (1) Until number of nc=0 (2) set nc=NC (3) set count = 0 (4) choose k, where k2NS,kis the cheapest and k‚hold (5) Select cargo i, where i‚served, (6) If ksatisfies all constraints, then cargo iserved by ship k,i2served count = count + 1 nc=nc–1 If count nc,then go to (5) Else,k2hold go to (3) (7) End Until The result is illustrated in Table 2: where cargo 1 is served by ship D; cargo 2 is served by ship A, and so on, until the last cargo nis served by ship k. The following section explains the methodologies of solving this type of problem using the TS method and separately describes the characteristic of each component of the method. 3.2. The neighbourhood structures The idea behind generating neighboring solutions is to improve the initial solution to the optimal or near optimal solution, where an initial solution sois constructed using a greedy algorithm. Then, Table 2. Schedule for all cargos with their ships cargo 1 2 ………….. n Ship D A ………… k Alhamad et al., Cogent Business & Management (2019), 6: 1616351 https://doi.org/10.1080/23311975.2019.1616351 Page 5 of 16 each solution so2Sis associated with an attribute set AðsÞ¼ ði;kÞ:i¼1; :::; NS; fk¼1; :::; NCg, where (i,k) means that cargo iis served using ship k. The construction of the neighborhood for initial solution sois implemented using two operator moves, insert and swap moves. The methodology of insert move operates by deleting attribute (i,k) from set A(s) and attempts to replace it with another attribute (i,k’). This methodology means that cargo iis removed from ship kand assigned to another ship k’where kÞk0. Inserting cargo iin the route of ship k’is executed to minimize the overall cost f(c). There are several approaches for insert move, where the process can delete one, two, or three cargos from the ship’s route and attempt to insert them into another ship’s routes, which, in this paper, are named 1-insert, 2-insert, and 3-insert move mechanisms. The insert process begins from the first cargo in ship k’route, where the insert trail assigns cargo iinto position i0. If constraints are not satisfied, the insert trail will carry on to position i0þ(minus and plus signs are the position order before or after cargo i0). If the attempt fails, the process continues to the second cargo i00using the same procedure, and so on, until the last cargo in the route. If ship k’cannot hold cargo i, the insert trail will transfer to ship k’’ until the last ship; otherwise, cargo iwill be assigned to spot ship. The 1-insert, 2-insert, and 3-insert move mechanisms adopted in this paper produce a suitable solution, while they take more computational time in the delete-insert procedure. Figure 2illustrates several types of insert moves. Comment: If two or more cargos are deleted from the route of ship k(as Schedule n, where cargos 2 and 5 are deleted), the first cargo will be selected randomly, and the next will be inserted into the route of ship k’. The same procedure applies for the second cargo and so on. For example, in Figure 2, the first cargo selected to be inserted into ship route A is 5; the next is cargo 2. The swap operator exchanges the position of two or more cargos. This swap removes two attributes (i,k) and (j,k’), where iÞjand kÞk0, from A(s) and interchanges them with two new attributes, (i,k’) and (j,k). If three cargos are selected, (i,k), (i’,k’), and (i’’,k’’), whereiÞi0Þi00, and kÞk0Þk00, the swap operation will be operated as (i’’,k), (i,k’), and (i’,k’’). All constraints must be satisfied, such as loading and unloading time windows or the capacity of the ship. Any infeasible schedule will be rejected. Furthermore, the schedule with the lowest overall cost f(c) will be chosen. Figure 3illustrates the swap operator procedure. When the insert operation is completed in that ship route, the attribute (i,k) will be forbidden for a number of iterations (or (i,k) and (j,k’) for the swap operator). That statement means that A A B B B S0 0 3 0 4 0 1 0 2 5 0 Schedule 1 0 3 0 4 0 1 0 2 5 0 Schedule 2 0 3 0 4 0 1 0 2 5 0 N(S) Schedule 3 0 3 0 4 0 1 0 2 5 0 Schedule n 0 3 0 4 0 1 0 2 5 0 2 3 333 3 3 333 11 1 3 55 5 222 222 Figure 2. The insert move procedure with three types of move mechanisms: 1-insert, 2-insert, and 3-insert. Alhamad et al., Cogent Business & Management (2019), 6: 1616351 https://doi.org/10.1080/23311975.2019.1616351 Page 6 of 16 attribute (i,k) will be assigned as a tabu status (tabu list). A tabu list usually consists of a list of moves the search has recently encountered. The moves on the tabu list cannot be revisited for a particular number of iterations called tabu tenure (tn of iterations). The tabu list helps the search to move from a previously visited section of the search space and to execute more extensive exploration. In this model, there are two tabu lists, one for the insert move and the other for the swap move. Moreover, the value of tabu tenure could be fixed or set as a variable, in this paper, the tabu tenure was set as a variable. However, move that remain in the tabu list for long periods of time may restrict the search process from proceeding and may cause to end sooner. Therefore, tabu tenure tn is fixed at 7–11 iterations. Conversely, this restriction can be revoked (canceled) by an aspiration criterion, for either insert or swap, if that move allowed the search to reach a solution with an overall cost f*(c) smaller than the best solution ever obtained. Number of neighborhood is considered a critical point in the moves operation. If the number of neighborhood is excessively small, it will restrict the search; a suitable solution is less likely to be found. Conversely, if the number of neighborhood is excessively large, it loses its purpose of diminishing the neighborhood size. A suitable trade-off can be obtained by experimentation. To use the TS heuristic method, there are three types of decision variables to solve SRSP (Figure 4). The first decision variable isrik, where i2NS and k2NC, is 1 if cargo iis served by ship k, and 0 otherwise. wik, the second decision variable, denotes the actual arrival time for ship kserving cargo i. The last decision variable is fðcÞ, which denotes the overall cost serving all cargos. Decision variables: rik 21;0 1 if cargo iis on the route of ship k, and 0 otherwise. wik actual arrival time for ship kserving cargo i. fðcÞtotal cost serving all cargos. Parameters: NS total number of ships, where ship k21;2; :::; NS fg , NC total number of cargos, where cargo i21;2; :::; NC fg , Titravel time (days) from origin to cargo i, Tij travel time (days) from port of cargo ito port of cargo j, eiearliest start time of the delivery of the cargo i, lilatest finish time of the delivery of the cargo i, lditime (days) to load cargo i, uditime (days) to unload cargo i, qkcapacity of ship k, A A B B B S0 0 3 0 4 0 1 0 2 5 0 Schedule 1 0 3 0 2 0 1 0 4 5 0 Schedule 2 0 1 0 4 0 3 0 2 5 0 N(S) Schedule n0 5 0 1 0 4 0 2 3 0 Figure 3. The swap move procedure. Alhamad et al., Cogent Business & Management (2019), 6: 1616351 https://doi.org/10.1080/23311975.2019.1616351 Page 7 of 16 Avkavailability of ship kat origin, diquantity of cargo i, pdiport due at customer of cargo i, cvkoperating cost per day for ship kin journey, avkavailable time for ship kat origin, Cik the cost of serving cargo iusing ship k, InTer denotes the number of iterations needed to search in the current region, where θ2InTer DivIter denotes the number of times the search diversifies into a new region, The variable of actual arriving time wik to deliver cargo iusing ship kcan be computed using one of the following two equations: wik ¼avkþldiþTi(1) wik ¼ei;If avkþldiþTi<ei(2) No No Yes Yes Yes No Yes No Is N = STOP N = N+1 Create an initial solution using Greedy Algorithm M = 0, N = 0 Neighbouring using insert move Is M = Assigning a tabu list for the attributes Override tabu list f(c)=f*(c) M= 0 Neighbouring using swap move Is f*(c)<f(c) Assigning a tabu list for the attributes Override tabu list f(c)=f*(c) M= 0 M= M+1 Diversify to new region Is f*(c)<f(c) Create an initial solution Figure 4. Flowchart of the TS process. Alhamad et al., Cogent Business & Management (2019), 6: 1616351 https://doi.org/10.1080/23311975.2019.1616351 Page 8 of 16 suitable solution. On the other hand, shipping companies often minimize the overall cost, which in turn maximizes the profit. This technique and not the traditional manner (ad hoc) will achieve this goal in a reasonable time and using a scientific method. Funding This work was supported by the Khaled Moh Alhamad. Author details Khaled Alhamad 1 E-mail: [email protected] Azizah Alrashidi 1 E-mail: [email protected] Sameh Alkharashi 1 E-mail: [email protected] 1 Laboratory Technology Department, College of Technological Studies, PAAET, P.O. Box 42325, Shuwaikh 70654, Kuwait.. Citation information Cite this article as: Metaheuristic algorithm for ship routing and scheduling problems with time window, Khaled Alhamad, Azizah Alrashidi & Sameh Alkharashi, Cogent Business & Management (2019), 6: 1616351. References Al-Hamad, K., Al-Ibrahim, M., & Al-Enezy, E. (2012). A genetic algorithm for ship routing and scheduling problem with time window. American Journal of Operations Research,2(3), 417–429. doi:10.4236/ ajor.2012.23050 Andersson, H., Duesund, J., & Aderholt, K. (2011). Ship routing and scheduling with cargo coupling and synchronization constraints. Computers & Industrial Engineering,61, 1107–1116. doi:10.1016/j. cie.2011.07.001 Brønmo, G., Christiansen, M., & Nygreen, B. (2007b). Ship routing and scheduling with flexible cargo size. Operational Research Society,58(9), 1167–1177. doi:10.1057/palgrave.jors.2602263 Brønmo, G., Nygreen, B., & Lysgaard, J. (2010). Column generation approaches to ship scheduling with flexible cargo sizes”.European Journal of Operational Research,200, 139–150. doi:10.1016/j. ejor.2008.12.028 Cho, S.-C., & Perakis, N. (2001). An improved formulation for bulk cargo ship scheduling with a singlr loading port”.Maritime Policy and Management,28, 339–345. doi:10.1080/03088830010002755 Christiansen, M., Fagerholt, K., Nygreen, B., & Ronen, D. (2013). Ship routing and scheduling in the new millennium. European Journal of Operational Research, 228,467–483. doi:10.1016/j.ejor.2012.12.002 Christiansen, M., Fagerholt, K., & Ronen, D. (2004). Ship routing and scheduling: Status and perspectives. Transportation Science,38(1), 1–18. doi:10.1287/ trsc.1030.0036 Gatica, R. A., & Miranda, P. A. (2011). Special issue on Latin-American research: A time based discretization approach for ship routing and scheduling with variable speed. Networks and Spatial Economics,11(3), 465–485. doi:10.1007/s11067-010-9132-9 Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers and Operations Research,13, 533–549. doi:10.1016/03050548(86)90048-1 Holland, J. H. (1975). Adaption in natural and artificial systems. Ann Arbor, MI: University of Michigan Press. Kim, S.-H., & Lee, -K.-K. (1997). An optimization-based decision support system for ship scheduling. Computer and Industrial Engineering,33, 689–692. doi:10.1016/S0360-8352(97)00223-4 Kirkpatrick, S., Gelatt, J., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science,220, 671–680. doi:10.1126/science.220.4598.671 Korsvik, J., & Fagerholt, K. (2010). A tabu search for ship routing and scheduling with flexible cargo quantities. Journal of Heuristics,16, 117–137. doi:10.1007/ s10732-008-9092-0 MoonCorrespondence, I. K., Qiu, Z. B., & Wang, J. H. (2014). A combined tramp ship routing, fleet deployment, and network design problem. Maritime Policy & Management,42,68–91. Sherali, H. D., Al-Yakoop, S. M., & Hassan, M. M. (1999). Fleet management models and algorithms for oil-tanker routing and scheduling problem. IIE Transactions,31, 395–406. doi:10.1080/ 07408179908969843 U. Nation. (2016). Review of maritime transportation. United Nations Conference on Trade and Development (UNC-TAD). Retrieved from https:// unctad.org/en/PublicationsLibrary/rmt2016_en.pdf 0 50 100 150 200 250 300 350 400 450 500 20 24 28 32 36 Number of car g os Average computing time to obtain objective value Figure 5. Computational times between SPP and TS (CPU [s]). Dots line represents TS average time consumption.The straight line represents SPP average time consumption. Alhamad et al., Cogent Business & Management (2019), 6: 1616351 https://doi.org/10.1080/23311975.2019.1616351 Page 15 of 16 © 2019 The Author(s). This open access article is distributed under a Creative Commons Attribution (CC-BY) 4.0 license. You are free to: Share —copy and redistribute the material in any medium or format. Adapt —remix, transform, and build upon the material for any purpose, even commercially. The licensor cannot revoke these freedoms as long as you follow the license terms. Under the following terms: Attribution —You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use. No additional restrictions You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits. Cogent Business & Management (ISSN: 2331-1975) is published by Cogent OA, part of Taylor & Francis Group. Publishing with Cogent OA ensures: •Immediate, universal access to your article on publication •High visibility and discoverability via the Cogent OA website as well as Taylor & Francis Online •Download and citation statistics for your article •Rapid online publication •Input from, and dialog with, expert editors and editorial boards •Retention of full copyright of your article •Guaranteed legacy preservation of your article •Discounts and waivers for authors in developing regions Submit your manuscript to a Cogent OA journal at www.CogentOA.com Alhamad et al., Cogent Business & Management (2019), 6: 1616351 https://doi.org/10.1080/23311975.2019.1616351 Page 16 of 16