Irina Gribkovskaia

• Kisialiou, Yauheni; Gribkovskaia, Irina & Laporte, Gilbert (2021). Periodic supply vessel planning under demand and weather uncertainty. INFOR: Information Systems and Operational Research. ISSN 0315-5986. doi: 10.1080/03155986.2021.1907872. Show summary

  We solve a periodic supply vessel planning problem under demand and weather uncertainty, arising in offshore of oil and gas production. Our study is motivated by the case of the Norwegian energy operator Equinor which supplied us with data. The aim is to determine an optimal fleet composition and a least-cost vessel schedule under uncertain demand at the installations and uncertain weather conditions. We present a methodology incorporating a metaheuristic within a discrete-event simulation model which, applied iteratively for the increasing values of reliability level parameters, yields a vessel schedule of least expected cost. Keywords: supply vessel planning, offshore logistics, uncertainty, reliable vessel schedules, metaheuristic, discrete-event simulation, recourse

• Abu-Marrul, Victor; Martinelli, Rafael; Hamacher, Silvio & Gribkovskaia, Irina (2020). Matheuristics for a parallel machine scheduling problem with non-anticipatory family setup times : application in the offshore oil and gas industry. Computers & Operations Research. ISSN 0305-0548. 128(April), p. 1–19. doi: 10.1016/j.cor.2020.105162. Show summary

  In this paper, we address a variant of a batch scheduling problem with identical parallel machines and non-anticipatory family setup times to minimize the total weighted completion time. We developed an ILS and a GRASP matheuristics to solve the problem using a constructive heuristic and two MIP-based neighborhood searches, considering two batch scheduling mathematical formulations. The problem derives from a ship scheduling problem related to offshore oil & gas logistics, the Pipe Laying Support Vessel Scheduling Problem (PLSVSP). The developed methods overcome the current solution approaches in the PLSVSP literature, according to experiments carried out on a benchmark of 72 instances, with different sizes and characteristics, in terms of computational time and solution quality. New best solutions are provided for all medium and large-sized instances, achieving a reduction of more than 10% in the objective function of the best case. Keywords: parallel machine scheduling, family scheduling, batch scheduling, matheuristic, offshore industry logistics, ship scheduling

• Kisialiou, Yauheni; Gribkovskaia, Irina & Laporte, Gilbert (2019). Supply vessel routing and scheduling under uncertain demand. Transportation Research Part C: Emerging Technologies. ISSN 0968-090X. 104(July), p. 305–316. doi: 10.1016/j.trc.2019.04.011. Show summary

  We solve a supply vessel planning problem arising in upstream offshore petroleum logistics. A fleet of supply vessels delivers all the necessary equipment and materials to a set of offshore installations from an onshore supply base, according to a delivery schedule or sailing plan. Supply vessels, being the major cost contributor, are chartered on a long-term basis. The planning of supply vessels implies resolving the trade-off between the cost of the delivery schedule and the reliability of deliveries on the scheduled voyages, i.e. the service level. The execution of a sailing plan is affected by stochastic demands at the installations since a high demand fluctuation quite often leads to insufficient vessel capacity to perform a voyage according to the sailing plan. In addition, the average demand level at the installations may change over time, while the number of vessels in the sailing plan remains the same. Maintaining a reliable flow of supplies under stochastic demand therefore leads to additional costs and reduced service level. We present a novel methodology for reliable supply vessel planning and scheduling, enabling planners to construct delivery schedules having a low expected total cost. The methodology involves the construction of delivery schedules with different reliability levels using an adaptive large neighborhood search metaheuristic algorithm combined with a discrete event simulation procedure for the computation of the expected solution cost. Keywords: maritime logistics, supply vessel planning, recourse, reliable vessel schedules, metaheuristic, simulation

• Kisialiou, Yauheni; Gribkovskaia, Irina & Laporte, Gilbert (2018). The periodic supply vessel planning problem with flexible departure times and coupled vessels. Computers & Operations Research. ISSN 0305-0548. 94(June), p. 52–64. doi: 10.1016/j.cor.2018.02.008. Show summary

  In upstream offshore petroleum logistics, periodic supply vessel planning plays an important role since it ensures the replenishment of offshore installations on a regular basis with all the necessary equipment and materials from an onshore base. The problem involves the determination of the fleet composition and of the vessel schedules over a given time horizon. We present an extended version of this prob- lem involving flexible departures from the base and the possibility of coupling vessels by swapping their schedules. We propose a voyage-based model that can be solved exactly for small- and medium-size instances. For the solution of larger instances, we have developed an adaptive large neighborhood heuris- tic, which yields optimal or near-optimal solutions relatively fast on small- and medium- size instances. Its performance on larger instances is significantly better than that of alternative algorithms previously developed for the same problem. Keywords: offshore logistics, vehicle routing, periodic supply vessel planning, adaptive large neighborhood search

• Kisialiou, Yauheni; Gribkovskaia, Irina & Laporte, Gilbert (2018). Robust supply vessel routing and scheduling. Transportation Research Part C: Emerging Technologies. ISSN 0968-090X. 90(May), p. 366–378. doi: 10.1016/j.trc.2018.03.012. Show summary

  We solve the problem of tactical supply vessel planning arising in the upstream offshore petroleum logistics. Supply vessels deliver all the necessary materials and equipment to offshore installations from an onshore supply base according to a delivery schedule. The planning of supply vessels should be done so that their number is minimized and at the same time provide a reliable flow of supplies from the base. The execution of a weekly sailing plan is affected by weather conditions, especially in winter time. Harsh weather conditions increase the number of vessels required to perform the operations as well as the service times at the installations, and thus disrupt the schedule, leading to additional costs and reduced service level. We present a methodology for robust supply vessel planning enabling a trade-off analysis to be made between the schedules’ service level and vessels’ cost. The methodology involves the generation of multiple vessel schedules with different level of robustness using an adaptive large neighbourhood search metaheuristic and a subsequent discrete event simulation procedure for the assessment of the service level. To control the level of robustness we developed a concept of slacks and incorporated it into the metaheuristic algorithm.

• Norlund, Ellen Karoline & Gribkovskaia, Irina (2017). Environmental performance of speed optimization strategies in offshore supply vessel planning under weather uncertainty. Transportation Research Part D: Transport and Environment. ISSN 1361-9209. 57(December), p. 10–22. doi: 10.1016/j.trd.2017.08.002. Show summary

  Supply vessels serving oil and gas installations at sea are a major emission source of greenhouse gases in offshore logistics. Speed optimization strategies applied in tactical vessel planning significantly reduce fuel consumption and thus emissions. Nevertheless, the environmental performance of these strategies in rough weather conditions is difficult to estimate as the duration of supply vessel operations is weather dependent. In this paper we develop a simulation-optimization tool which estimates the average fuel consumption for weekly vessel schedules. The schedules are constructed by using speed optimized vessel voyages which are simulated under different weather conditions. Results of experiments on real instances show that rough weather conditions increase fuel consumption and costs. The application of speed optimization strategies reduces fuel consumption both in winter and summer, but the reduction may be at the expense of a fixed vessel cost increase in the winter season. Keywords: green maritime logistics, emissions, speed optimization, supply vessel operations, ship routing and scheduling, weather uncertainty

• Norlund, Ellen Karoline & Gribkovskaia, Irina (2015). Modal split in offshore supply network under the objective of emissions minimization. Transportation Research Part D: Transport and Environment. ISSN 1361-9209. 35, p. 160–174. doi: 10.1016/j.trd.2014.11.018. Show summary

  We study modal split under the objective of emissions minimization in the transportation of cargo from centralized vendors in the oil and gas industry to decentralized supply bases on the Norwegian coast. The supply network includes direct road transport and a sea route along the coast. To gain insight into modal split decisions between road and sea transport from the shipper’s perspective multi-period mixed integer optimization models are formulated. Particularly the models give possibilities to examine how weekly demand patterns at supply bases, cargo commitments to sea transport, storage possibilities at supply bases, and shipper’s responsibility for a certain share of vessel capacity may effect the emissions and the modal split. Experiments on real data from an oil and gas company operating offshore show that the size of the share of vessel capacity and the possibility for storage at supply bases are the major determinants for a larger shift to environmentally friendly sea transport. The models can be used as means for making decisions regarding how a shipper can commit to sea transport to achieve less emissions.

• Norlund, Ellen Karoline; Gribkovskaia, Irina & Laporte, Gilbert (2015). Supply vessel planning under cost, environment and robustness considerations. Omega. The International Journal of Management Science. ISSN 0305-0483. 57(B), p. 271–281. doi: 10.1016/j.omega.2015.05.006. Show summary

  Offshore oil and gas installations need reliable cargo deliveries. The vessels supplying these installations on a periodic basis are expensive and constitute a source of emissions of greenhouse gases. Incorporating vessel speed optimization into the supply vessel planning process may significantly reduce fuel consumption and hence emissions. In addition, speed optimization may yield cost reductions if the number of vessels used does not increase. A main uncertainty factor, especially in the winter season, is the weather conditions which impact sailing and service times. Cost minimization and the application of speed optimization strategies may have implications on the robustness of weekly supply vessel schedules since idle times in the schedules are reduced. We develop a simulation-optimization based methodology that considers costs, emissions and robustness in the generation of weekly supply vessel schedules. Results of analyses conducted on real instances show that robustness requirements may yield both increased emissions and costs in the winter season. However, depending on instance characteristics, different degrees of robustness can be incorporated with both costs and emissions reductions through speed optimization.

• Qian, Fubin; Strusevich, Vitaly A.; Gribkovskaia, Irina & Halskau sr, Øyvind (2015). Minimization of passenger takeoff and landing risk in offshore helicopter transportation: Models, approaches and analysis. Omega. The International Journal of Management Science. ISSN 0305-0483. 51, p. 93–106. doi: 10.1016/j.omega.2014.09.002. Show summary

  Offshore petroleum industry uses helicopters to transport the employees to and from installations. Takeoff and landing represent a substantial part of the flight risks for passengers. In this paper, we propose and analyze approaches to create a safe flight schedule to perform pickup of employees by several independent flights. Two scenarios are considered. Under the non-split scenario, exactly one visit is allowed to each installation. Under the split scenario, the pickup demand of an installation can be split between several flights. Interesting links between our problem and other problems of combinatorial optimization, e.g., parallel machine scheduling and bin-packing are established. We provide worst-case analysis of the performance of some of our algorithms and report the results of computational experiments conducted on randomly generated instances based on the real sets of installations in the oil fields on the Norwegian continental shelf. This paper is the first attempt to handle takeoff and landing risk in a flight schedule that consists of several flights and lays ground for the study on more advanced and practically relevant models.

• Gribkovskaia, Irina; Halskau sr, Øyvind & Kovalyov, Mikhail Y. (2015). Minimizing takeoff and landing risk in helicopter pickup and delivery operations. Omega. The International Journal of Management Science. ISSN 0305-0483. 55(September), p. 73–80. doi: 10.1016/j.omega.2015.02.010. Show summary

  The problem of minimizing total helicopter passenger risk caused by takeoffs and landings is studied. There are passenger pickup and delivery demands to be satisfied at given points by flights starting and ending in the same heliport and visiting several points. For each point, the delivery demand is the number of passengers to be transported from the heliport to this point and the pickup demand is the number of different passengers to be transported from this point to the heliport. Each pickup and delivery demand must be satisfied in full by one flight. There are an upper bound on the number of flights and an upper bound on the helicopter passenger capacity. The objective function is a linear combination of the numbers of passengers involved in takeoffs and landings at visited points. A solution is characterized by the number of flights, sets of visited points and their sequences for all flights. Properties of optimal solutions are established. Several cases are proved NP-hard. A quadratic boolean programming formulation and two dynamic programming algorithms are suggested for the general case. Computer experiments demonstrated that they are able to solve real-life instances. Polynomial time algorithms are presented for special cases. Implementation of the suggested solutions into the real helicopter operations should decrease the number of fatalities.

• Kisialiou, Yauheni; Gribkovskaia, Irina & Gribkovskaia, Victoria (2015). A simulation model for the assessment of the northern sea route troughput. In Jæger, Bjørn (Eds.), NOFOMA 2015 : Post Conference Proceedings, Molde, 3-5 June 2015, Nordic Logistics Research Network. Nordic Logistics Research Network. ISSN 978-82-7962-207-9. p. 175–189.
• Sopot, Eugen & Gribkovskaia, Irina (2014). Routing of Supply Vessels to with Deliveries and Pickups of Multiple Commodities. Procedia Computer Science. ISSN 1877-0509. 31, p. 910–917. doi: 10.1016/j.procs.2014.05.343. Show summary

  This paper considers a single vehicle routing problem with pickups and deliveries of multiple commodities where each customer requires both pickup and delivery of several types of goods from a single depot. This problem arises in offshore upstream logistics and is relevant for the oil and gas companies operating offshore. Offshore installations need to be supplied with several types of goods from an onshore base, and also some cargo need to be transported from the installations back to the base. Supply operations from and to the base are performed by supply vessels, which have separate compartments for different types of cargo. In this paper we present a mathematical formulation for the problem and describe a metaheuristic algorithm yielding non- Hamiltonian routes where customers may be visited once or twice. Computational tests show that the algorithm outperforms CPLEX optimization solver in speed on instances of medium size and generates high quality solutions for large-size instances compared to the Unified Tabu Search algorithm. Keywords: vehicle routing; pickup and delivery; multiple commodities; metaheuristics; offshore logistics.

• Maisiuk, Yauhen & Gribkovskaia, Irina (2014). Fleet Sizing for Offshore Supply Vessels with Stochastic Sailing and Service Times. Procedia Computer Science. ISSN 1877-0509. 31, p. 939–948. doi: 10.1016/j.procs.2014.05.346. Show summary

  In this paper we address a supply vessel planning problem arising in servicing oil and gas offshore installations. Supply vessels provide offshore installations with necessary supplies on periodic basis from offshore supply bases according to weekly sailing schedules. The execution of weekly schedules during the year is affected by weather conditions influencing on sailing time and service duration at installations. When the contracted vessel cannot complete a voyage before the start of its next planned voyage, a vessel from the spot market is hired to perform it. Deciding on the number of supply vessels hired to perform operations from a supply base for a year ahead has a strong economic effect on the total annual vessel costs. We present a discrete-event simulation model for evaluation of alternative fleet size configurations taking into consideration uncertainty in weather conditions and future spot vessel rates. The model is validated and tested on real data.

• Shyshou, Aliaksandr; Gribkovskaia, Irina; Laporte, Gilbert & Fagerholt, Kjetil (2013). A Large Neighbourhood Search Heuristic for a Periodic Supply Vessel Planning Problem Arising in Offshore Oil and Gas Operations. INFOR: Information Systems and Operational Research. ISSN 0315-5986. 50(4), p. 195–204. doi: 10.3138/infor.50.4.195. Show summary

  The periodic supply vessel planning problem arises in supply operations performed by a heterogeneous fleet of vessels operating from an onshore base to offshore installations. These vessels must supply the installations on a periodic basis. Given a planning horizon, the problem consists of determining the fleet composition as well as the vessel schedules. This paper proposes a large neighbourhood search heuristic capable of solving large instances of the problem. On small instances for which an optimal solution is known, the heuristic consistently finds optimal or near-optimal solutions. It can also solve larger instances which are intractable by an exact algorithm. Keywords: Maritime transportation, offshore logistics, routing and scheduling, large neighbourhood search heuristic.

• Norlund, Ellen Karoline & Gribkovskaia, Irina (2013). Reducing emissions through speed optimization in supply vessel operations. Transportation Research Part D: Transport and Environment. ISSN 1361-9209. 23, p. 105–113. doi: 10.1016/j.trd.2013.04.007. Show summary

  This paper examines how optimizing sailing speeds can reduce supply vessels emissions in the upstream supply chain to offshore installations. We introduce several speed optimization strategies to be used in construction of periodic vessel schedules. The strategies consider vessel waiting times before the start of service at installations and at supply base. Tests carried out on real instances from Statoil’s activities on the Norwegian continental shelf indicate that a 25% emissions and fuel cost reductions can be achieved without fleet size increase.

• Qian, Fubin; Gribkovskaia, Irina; Laporte, Gilbert & Halskau sr, Øyvind (2012). Passenger and pilot risk minimization in offshore helicopter transportation. Omega. The International Journal of Management Science. ISSN 0305-0483. 40(5), p. 584–593. doi: 10.1016/j.omega.2011.11.003. Show summary

  In the offshore petroleum industry, employees are transported to and from the offshore installations by helicopter, which represents a major risk. This paper analyzes how to improve transportation safety by solving the helicopter routing problem with a risk objective expressed in terms of expected number of fatalities. A mathematical model is proposed and a tabu search heuristic is applied to this problem. Three routing policies are considered: a direct routing policy, a Hamiltonian routing policy, and a general routing policy. Extensive computational experiments are conducted on instances derived from real data in order to assess and compare these policies under a travel time, a passenger risk and a combined passenger and pilot risk objective. Several management insights can be derived from this study. In particular, our results show that passenger transportation risk can be reduced by increasing travel time at the expense of pilot risk. This can be achieved through a reduction of the average number of passengers onboard by applying either a Hamiltonian or a general routing policy. Our methodology can also be used to derive an equitable distribution of risk between passengers and pilots, considering that pilots fly much more frequently than passengers.

• Qian, Fubin; Gribkovskaia, Irina & Halskau sr, Øyvind (2011). Helicopter routing in the Norwegian oil industry : including safety concerns for passenger transport. International Journal of Physical Distribution & Logistics Management. ISSN 0960-0035. 41(4), p. 401–415. doi: 10.1108/09600031111131959. Show summary

  PURPOSE - In the Norwegian offshore oil industry, helicopters have been used as a major mode of transporting personnel to and from offshore installations for decades. Helicopter transportation represents one of the major risks for offshore employees. The purpose of this paper is to study the safety of helicopter transportation in terms of the expected number of fatalities on an operational planning level. DESIGN/METHODOLOGY/APPROACH - Based on an analysis of helicopter accidents, this paper proposes a mathematical model that can aid in the planning of routes for the fleet in order to minimize the expected number of fatalities. FINDINGS - A theorem proven in this paper tells that hub-and-spoke configuration is the best way of routing helicopters in terms of minimizing expected number of fatalities. Computational results indicate that the expected number of fatalities may be reduced at the expense of longer travel time by implementing the proposed method into planning of routes for helicopter fleet. RESEARCH LIMITATIONS/IMPLICATIONS - The main limitation is the present inability to solve large problem instances. PRACTICAL IMPLICATIONS - The suggested tool is able to provide decision makers with a set of solutions from which they can choose the one with the best trade-off between travel time and transportation safety. ORIGINALITY/VALUE - The mathematical model and theoretical results for route planning with a safety-based objective are original.

• Gribkovskaia, Irina; Kurhuzava, Lidziya & Svirydava, Yuliya (2011). Development of routing planning tools for a distribution company. In Hammervoll, Trond (Eds.), The 23rd Annual NOFOMA Conference 9–10 June 2011, Harstad, Norway: Logistics and Supply Chain Management in a High North perspective: Conference proceedings. Nordic Logistics Research Network. ISSN 8245302287. p. 405–421.
• Shyshou, Aliaksandr; Gribkovskaia, Irina & Barceló, Jaume (2010). A simulation study of the fleet sizing problem arising in offshore anchor handling operations. European Journal of Operational Research. ISSN 0377-2217. 203(1), p. 230–240. doi: 10.1016/j.ejor.2009.07.012. Show summary

  A fleet sizing problem arising in anchor handling operations related to movement of offshore mobile units is presented in this paper. Typically, the intensity of these operations is unevenly spread throughout the year. The operations are performed by dedicated vessels, which can be hired either on the long-term basis or on the spot market. Spot rates are frequently a magnitude higher than long-term rates, and vessels are hired on the spot market if there is a shortage of long-term vessels to cover the ongoing anchor handling operations. Deciding the cost-optimal fleet of vessels on the long-term hire to cover future operations is a problem facing offshore oil and gas operators. This decision has a heavy economic impact as anchor handling vessels are among the most expensive ones. The problem is highly stochastic because durations of anchor handling operations vary and depend on uncertain weather conditions. Moreover, future spot rates for anchor handling vessels are extremely volatile. The objective of this paper is to describe a simulation model for the fleet sizing problem. The study was initiated by the largest Norwegian offshore oil and gas operator and has received considerable acceptance among the planners.

• Gribkovskaia, Irina; Kovalev, Sergey & Werner, Frank (2010). Batching for work and rework processes on dedicated facilities to minimize the makespan. Omega. The International Journal of Management Science. ISSN 0305-0483. 38(6), p. 522–527. doi: 10.1016/j.omega.2010.01.002. Show summary

  We study a planning problem of an imperfect production of a single product. The product is assumed to be continuously divisible. There are two facilities: a main facility dedicated to the original production and a facility dedicated to re-manufacturing defective units coming from the main facility. Units fabricated on the main facility are inspected for quality in batches. The quality inspection requires some time and can be performed on-line or off-line. After the inspection has been completed, defective units of the inspected batch are transported to the re-manufacturing facility. The transportation also requires some time. We assume that the fraction of the defective units is the same in each batch on the manufacturing facility and that the re-manufacturing facility is perfect. Given a demand for good quality units of the product and an upper bound K on the number of batches, the problem is to find a sequence of batch sizes such that the makespan, i.e., the time of the demand satisfaction, is minimized. We suggest a linear programming formulation, prove several properties of an optimal solution, and finally develop an O(log K) time solution algorithm. A similar per time unit cost minimization problem is studied as well.

• Hoff, Arild; Gribkovskaia, Irina; Laporte, Gilbert & Løkketangen, Arne (2009). Lasso solution strategies for the vehicle routing problem with pickups and deliveries. European Journal of Operational Research. ISSN 0377-2217. 192(3), p. 755–766. doi: 10.1016/j.ejor.2007.10.021. Show summary

  This paper considers the vehicle routing problem with pickups and deliveries (VRPPD) where the same customer may require both a delivery and a pickup. This is the case, for instance, of breweries that deliver beer or mineral water bottles to a set of customers and collect empty bottles from the same customers. It is possible to relax the customary practice of performing it pickup when delivering at it customer, and postpone the pickup until the vehicle has sufficient free capacity. In the case of breweries, these solutions will often consist of routes in which bottles are first delivered until the vehicle is partly unloaded, then both pickup and delivery are performed at the remaining customers, and finally empty bottles are picked Lip front the first visited customers. These customers are revisited in reverse order. thus giving rise to lasso shaped solutions. Another possibility is to relax the traditional problem even more and allow customers to be visited twice either in two different routes or at different times oil the same route, giving rise to it general solution. This article develops a tabu search algorithm capable of producing lasso solutions. A general solution can be reached by first duplicating each customer and generating a Hamiltonian solution oil the extended set of customers. Test results show that while general solutions outperform other solution shapes in term of cost. their computation cart be time consuming. The best lasso solution generated within it given time limit is generally better than the best general solution produced with the same computing effort. (c) 2007 Elsevier B.V. All rights reserved.

• Billaut, Jean-Charles; Gribkovskaia, Irina & Strusevich, Vitaly A. (2008). An improved approximation algorithm for the two-machine open shop scheduling problem with family setup times. IIE Transactions. ISSN 0740-817X. 40(4), p. 478–493. Show summary

  We consider the problem of scheduling families of jobs in a two-machine open shop so as to minimize the makespan. The jobs of each family can be partitioned into batches and a family setup time on each machine is required before the first job is processed, and when a machine switches from processing a job of some family to a job of another family. For this NP-hard problem the literature contains (5/4)-approximation algorithms that cannot be improved on using the class of group technology algorithms in which each family is kept as a single batch. We demonstrate that there is no advantage in splitting a family more than once. We present an algorithm that splits one family at most once on a machine and delivers a worst-case performance ratio of 6/5.

• Gribkovskaia, Irina & Laporte, Gilbert (2008). One-to-many-to-one single vehicle pickup and delivery problem, The vehicle routing problem : latest advances and new challenges / Bruce Golden, S. Raghavan, Edward Wasil (eds.). Springer. p. 359–377. Show summary

  In One-to-Many-to-One Single Vehicle Pickup and Delivery Problems a vehicle based at the depot must make deliveries and pickups at customers locations before returning to the depot. Several variants can be defined according to the demand structures and sequencing rules imposed on pickups and deliveries. In recent years there have been an increased interest in this family of problems. New formulations and efficient heuristics capable of yielding general solutions (unrestricted in shape) have been proposed. In addition, some new and interesting extensions have been analyzed, including problems with selective pickups and problems with capacitated customers. The purpose of this chapter is to review these developments

• Gribkovskaia, Irina; Laporte, Gilbert & Shlopak, Alexander (2008). A tabu search heuristic for a routing problem arising in servicing of offshore oil and gas platforms. Journal of the Operational Research Society. ISSN 0160-5682. 59(11), p. 1449–1459. Show summary

  This paper introduces a pickup and delivery problem encountered in servicing of offshore oil and gas platforms in the Norwegian Sea. A single vessel must perform pickups and deliveries at several offshore platforms. All delivery demands originate at a supply base and all pickup demands are also destined to the base. The vessel capacity may never be exceeded along its route. In addition, the amount of space available for loading and unloading operations is limited at each platform. The problem, called the Single Vehicle Pickup and Delivery Problem with Capacitated Customers consists of designing a least cost vehicle (vessel) route starting and ending at the depot (base), visiting each customer (platform), and such that there is always sufficient capacity in the vehicle and at the customer location to perform the pickup and delivery operations. This paper describes several construction heuristics as well as a tabu search algorithm. Computational results are presented.

• Gribkovskaia, Irina; Laporte, Gilbert & Shyshou, Aliaksandr (2008). The single vehicle routing problem with deliveries and selective pickups. Computers & Operations Research. ISSN 0305-0548. 35(9), p. 2908–2924. doi: 10.1016/j.cor.2007.01.007. Show summary

  The single vehicle routing problem with deliveries and selective pickups (SVRPDSP) is defined on a graph in which pickup and delivery demands are associated with customer vertices. The difference between this problem and the single vehicle routing problem with pickups and deliveries (SVRPPD) lies in the fact that it is no longer necessary to satisfy all pickup demands. In the SVPPDSP a pickup revenue is associated with each vertex, and the pickup demand at that vertex will be collected only if it is profitable to do so. The net cost of a route is equal to the sum of routing costs, minus the total collected revenue. The aim is to design a vehicle route of minimum net cost, visiting each customer, performing all deliveries, and a subset of the pickups. A mixed integer linear programming formulation is proposed for the SVRPDSP. Classical construction and improvement heuristics, as well as a tabu search heuristic (TS), are developed and tested on a number of instances derived from VRPLIB. Computational results show that the solutions produced by the proposed heuristics are near-optimal. There is also some evidence that the best solutions identified by the heuristics are frequently non-Hamiltonian and may contain one or two customers visited twice. (c) 2007 Elsevier Ltd. All rights reserved.

• Gribkovskaia, Irina; Halskau, Øyvind & Laporte, Gilbert (2007). The bridges of Konigsberg - A historical perspective. Networks. ISSN 0028-3045. 49(3), p. 199–203. Show summary

  The Bridges of Konigsberg is one of the most famous problems in graph theory. In the summer of 2005, two of the authors visited Konigsberg, now called Kaliningrad. This article provides geographical and historical information on Konigsberg and its bridges, as well as updated information on the current day situation. (c) 2007 Wiley Periodicals, Inc.

• Gribkovskaia, Irina; Halskau, Øyvind; Laporte, Gilbert & Vlcek, Martin (2007). General solutions to the single vehicle routing problem with pickups and deliveries. European Journal of Operational Research. ISSN 0377-2217. 180(2), p. 568–584. Show summary

  The single vehicle routing problem with pickups and deliveries (SVRPPD) is defined on a graph in which pickup and delivery demands are associated with the customer vertices. The problem consists of designing a least cost route for a vehicle of capacity Q. Each customer is allowed to be visited once for a combined pickup and delivery, or twice if these two operations are performed separately. This article proposes a mixed integer linear programming model for the SVRPPD. It introduces the concept of general solution which encompasses known solution shapes such as Hamiltonian, double-path and lasso. Classical construction and improvement heuristics, as well as a tabu search heuristic, are developed and tested over several instances. Computational results show that the best solutions generated by the heuristics are frequently non-Hamiltonian and may contain up to two customers visited twice. (c) 2006 Elsevier B.V. All rights reserved.

• Berbeglia, Gerardo; Cordeau, Jean-François; Gribkovskaia, Irina & Laporte, Gilbert (2007). Static pickup and delivery problems: a classification scheme and survey. TOP - An Official Journal of the Spanish Society of Statistics and Operations Research. ISSN 1134-5764. 15(1), p. 1–31. Show summary

  Pickup and delivery problems constitute an important class of vehicle routing problems in which objects or people have to be collected and distributed. This paper introduces a general framework to model a large collection of pickup and delivery problems, as well as a three-field classification scheme for these problems. It surveys the methods used for solving them.

• Aas, Bjørnar; Gribkovskaia, Irina; Halskau, Øyvind & Shlopak, Alexander (2007). Routing of supply vessels to petroleum installations. International Journal of Physical Distribution & Logistics Management. ISSN 0960-0035. 37(2), p. 164–179. Show summary

  Purpose - In the Norwegian oil and gas industry the upstream logistics includes providing the offshore installations with needed supplies and return flow of used materials and equipment. This paper considers a real-life routing problem for supply vessels serving offshore installations at Haltenbanken off the northwest coast of Norway from its onshore supply base. The purpose of the paper is to explore how the offshore installation's limited storage capacity affects the routing of the supply vessels aiming towards creating efficient routes. Design/methodology/approach - A simplified version of the real-life routing problem for one supply vessel is formulated as a mixed integer linear programming model that contains constraints reflecting the storage requirements problem. These constraints ensure that there is enough capacity at the platform decks and that it is possible to perform both pickup and delivery services. Findings - The model has been tested on real-life-sized instances based on data provided by the Norwegian oil company Statoil ASA. The tests show that in order to obtain optimal solutions to the pickup and delivery problem with limited free storage capacities at installations, one has to include in the formulation the new sets of constraints, the storage feasibility and the service feasibility requirements. In addition, two visits to some platforms are necessary to obtain optimality. Research limitations/implications - The main limitation is the present inability to solve large cases. Originality/value - The contribution of this paper is to provide a better insight into a real-life routing problem which has a unique feature arising from the limited deck capacity at the offshore installations that complicates the performance of service. This feature has neither been discussed nor modeled in the vehicle routing literature before, hence the formulation of the problem is original and reveals some interesting results

• Aas, Bjørnar; Gribkovskaia, Irina; Halskau, Øyvind & Shlopak, Alexander (2006). Routing of supply vessels serving oil and gas installations in the Norwegian Sea, Economic order quantities assuming generalised order costs. NOFOMA.
• Gribkovskaia, Irina; Gullberg, Bjørn Olav; Hovden, Karl J. & Wallace, Stein W. (2006). Optimization model for a livestock collection problem. International Journal of Physical Distribution & Logistics Management. ISSN 0960-0035. 36(2), p. 136–152. Show summary

  Abstract: Purpose ? The value chain of the Norwegian meat production industry has recently been through major structural changes resulting in increased flows and transportation needs at all levels. The purpose of this paper is to present results of the initial stage of a five-year research project between the Norwegian Meat Research Centre, Norwegian meat companies and Molde University College. The main goal of the project is to develop a decision support system for the transport of live animals to a slaughterhouse to reduce transportation costs while maintaining high level of livestock welfare and meat quality, as these are three main factors for the profitability of both farmers and industry. Design/methodology/approach ? The paper presents a mixed integer programming model that combines vehicle routing and inventory control. We introduce the possibility for multiple routes for a given vehicle on a given day in a multiple-period planning perspective. Arrival times of the loaded vehicles to the slaughterhouse are controlled by production (slaughter) rate and inventory level at the abattoirs so that the supply of animals for slaughter is steady and production breaks are avoided. Livestock welfare is secured by the route duration constraints. Findings ? The model has been formulated and tested on small data sets. The major future challenge is to solve real-life problems from the involved companies. Research limitations/implications ? The main limitation is the present inability to solve large cases. Originality/value ? The model combining transportation and inventory control in a setting of animal welfare constraints is original

• Gribkovskaia, Irina; Lee, Chung-Yee; Strusevich, Vitaly A. & De Werra, Dominique (2006). Three is easy, two is hard: open shop sum-batch scheduling problem refined. Operations Research Letters. ISSN 0167-6377. 34(4), p. 459–464. Show summary

  For the two-machine open shop sum-batch problem to minimize the makespan an optimal schedule is known to contain one, two or three batches on each machine, and finding a two-batch optimal schedule is NP-hard. We adapt the open shop algorithm by de Werra for finding a three-batch optimal schedule in linear time. (c) 2005 Elsevier B.V. All rights reserved.

View all works in Cristin

• Skriabin, Anton; Kovalenko, Alina & Gribkovskaia, Irina (2021). Simulation models for fleet sizing and cargo throughput analysis in Arctic shipping.
• Kovalenko, Alina & Gribkovskaia, Irina (2020). The analyses of infrastructure and transit cargoes through Arctic region.
• Gribkovskaia, Irina & Bøthun, Sunniva (2020). Det er viktig for oss å vise vår solidaritet. [Newspaper]. Romsdals Budstikke.
• Maisiuk, Yauhen & Gribkovskaia, Irina (2017). Evaluation of methods for construction of robust supply vessel schedules with discrete-event simulation. Show summary

  Supply vessel planning problem arises in offshore oil and gas logistics, where a fleet of vessels provides cargo deliveries to offshore installations on a periodic basis from an onshore supply base. The objective is to define an optimal fleet composition and a least-cost weekly sailing plan of scheduled vessels' voyages. The problem is defined as a fleet-sizing and periodic routing problem with multiple time windows at installations and voyage duration constraints. Weather conditions change dynamically and may significantly influence vessels' sailing and service times, resulting in sailing plan infeasibility. The planners need vessel plans with sufficient robustness to offset the impact of weather conditions and avoid use of additional vessels. Known approaches for construction of robust vessel schedules consist of generation of shortest duration voyages and solution of a set covering model. In some approaches, voyage slacks are incorporated during voyage generation phase based on planners' experience. In other approaches, shortest generated voyages are simulated over multiple replications of wave height evolution to compute voyage robustness measure or to assign voyage duration. In this study, we evaluate robustness of vessel schedules constructed by different robustness approaches with the developed discrete-event simulation model. It simulates weekly sailing schedules repetitively over seasonal horizon over multiple replications of weather scenarios. Multi-site multivariate seasonal sea state modeling is based on nonparametric numerical resampling and intra-day hind-cast metocean data. Experiments are conducted on real-based instances from an oil and gas company. We examine the impact of various instance characteristics on robustness of weekly sailing schedules.

• Kisialiou, Yauheni & Gribkovskaia, Irina (2017). Heuristic based approach for generation of cost-effective and robust supply vessel schedules. Show summary

  In this work, we address the problem of supply vessel planning that arises in the upstream offshore oil and gas logistics. Supply vessels deliver all the necessary materials and equipment to offshore installations from an onshore supply base. Delivery takes place according to a weekly sailing plan (delivery schedule). Charter cost of supply vessels is the largest cost contributor in the upstream offshore supply. Therefore, planning of supply vessels should be done so that their number is minimized and in the same time providing reliable ow of supplies from the base not allowing for the downtime at installations. Execution of weekly sailing plan is affected by weather conditions, especially in the wintertime. Harsh weather conditions increase vessels sailing and service time at installations and thus disrupt the schedule that leads to additional costs and reduced service level. We present a developed heuristic-based approach incorporating post-optimization simulation procedure enabling to create cost-effective and robust vessel schedules valid for a certain season, which enhances the possibility of generating schedules for the real large-size problem instances with the preferred trade-offs between robustness and vessel costs.

• Maisiuk, Yauhen & Gribkovskaia, Irina (2015). Recourse strategies in weather dependent supply vessel operations.
• Sopot, Eugen & Gribkovskaia, Irina (2014). Vehicle routing problems with deliveries and pickups of multiple commodities.
• Maisiuk, Yauhen & Gribkovskaia, Irina (2014). Modelling of supply vessel operations with simulation. Show summary

  Supply vessel schedules are generated according to service requirements of offshore installations characterized by cargo demand and weekly visit frequency. Stochastic factors such as weather uncertainty influence on the execution of schedules so that some visits are not performed. We consider several strategies how the cargo not delivered as planned may be shipped later. To compare the strategies and analyze their performance a discrete-event simulation model is developed. Tests on real data illustrate how application of these strategies for annual horizon reduces the number of delayed visits.

• Kisialiou, Yauheni; Shcherbanin, Yury & Gribkovskaia, Irina (2014). Analysis of logistics capabilities for gas transportation in the Arctic. Show summary

  Exploration of hydrocarbons reserves in the Arctic requires development of logistics capacities and transport infrastructure. Effect of the global warming and year-around navigation on the Northern Sea Route facilitate downstream transportation of gas extracted in the Arctic via the route to Asia-Pacific markets. Using simulation model we study the implications of the ice breaking fleet availability, climate conditions and regulations for navigation on the route throughput. Simulation is performed for several scenarios of LNG transportation between different ports by different LNG carriers.

• Hubin, Aliaksandr; Norlund, Ellen Karoline & Gribkovskaia, Irina (2014). Evaluating robustness of speed optimized supply vessel schedules. Show summary

  Offshore installations need supply vessel services on a regular basis. Weather uncertainty impacts on how service is performed. We incorporate different robustness and speed optimization strategies into the two-phase optimization procedure for generation of supply vessel schedules. To compare performance of these strategies by evaluating robustness of generated schedules with different service parameters a discrete-event simulation model is developed. Based on results from simulation strategies for improving robustness incorporated into the simulation model are applied to modify the schedules.

• Gribkovskaia, Irina & Norlund, Ellen Karoline (2014). Robust supply vessel planning with speed optimization. Show summary

  The oil and gas industry needs reliable transport of cargo between onshore bases and offshore installations. Weather uncertainty and sailing speed should be taken into account in supply vessel planning. To address the problem of generating robust and green supply vessel schedules a method combining discrete-event simulation with speed optimization algorithms for voyage generation and applying stochastic optimization for schedule construction is developed. Results of tests on real instances show increased robustness and reduced emissions compared to deterministic planning with constant speed.

• Norlund, Ellen Karoline & Gribkovskaia, Irina (2014). Modal split in offshore upstream supply chain under the objective of emissions minimization. Show summary

  We assess modal split in the offshore upstream supply chain of cargo from vendors to supply bases along the Norwegian coast under the objective of emissions minimization. To gain insight into drivers for modal split between road and sea transport from the shipper’s perspective a multi-period mixed integer optimization model is formulated. The model is used to study how different demands, inventory policies at bases and shipper commitments to sea transport affect modal split. The results show that commitments and inventories are major drivers towards environmental friendly sea transport.

• Maisiuk, Yauhen & Gribkovskaia, Irina (2014). Strategic fleet sizing for offshore supply vessels with stochastic service time.
• Gribkovskaia, Irina; Norlund, Ellen Karoline & Maisiuk, Yauhen (2014). Routing and fleet sizing for offshore supply vessels. In ., . (Eds.), ROUTE 2014 : International Workshop on Vehicle Routing, Intermodal Transport and Related Areas : June 1-4, 2014. Technical University of Denmark.
• Maisiuk, Yauhen & Gribkovskaia, Irina (2014). Fleet sizing for offshore supply vessels with stochastic sailing and service times.
• Sopot, Eugen & Gribkovskaia, Irina (2014). A simulation model for evaluation of supply vessel schedule robustness under demand uncertainty.
• Gribkovskaia, Irina; Norlund, Ellen Karoline & Maisiuk, Yauhen (2014). Routing and fleet sizing for offshore supply vessels.
• Maisiuk, Yauhen & Gribkovskaia, Irina (2013). Fleet sizing for offshore supply vessels. Show summary

  Supply vessels provide offshore installations with necessary supplies on periodic basis from an onshore base according to weekly sailing plans. Each plan is built for a certain time horizon to guarantee required level of service to offshore installations at least cost. In a sailing plan several voyages are assigned to each vessel. The execution of sailing plans is affected by stochastic weather conditions. A vessel may not perform all visits within the planned voyage duration because of bad weather influencing vessel's sailing and service time. In such cases, additional vessels may be needed. Deciding on the number of supply vessels to hire on the long-term basis is an important part of the strategic fleet size planning. We present a discrete-event simulation model that evaluates alternative fleet size configurations of vessel fleet size for an annual time horizon. Keywords: Fleet Sizing, Routing, Simulation.

• Sopot, Eugen; Gribkovskaia, Irina & Laporte, Gilbert (2012). Routing of supply vessels to offshore installations with deliveries and pickups of multiple commodities. Show summary

  Offshore installations are dependent on periodic deliveries of various goods from an onshore supply base and continuously generate pickup demands. We consider the problem of routing supply vessels to offshore installations as a multi-commodity vehicle routing problem with pickups and deliveries. To guarantee the existence of a feasible solution to the problem it is assumed that each installation may be visited once or twice. We propose a variable neighborhood search heuristic algorithm for the single vessel variant of this problem.

• Maisiuk, Yauhen & Gribkovskaia, Irina (2012). A simulation study of the fleet sizing problem for offshore supply vessels. Show summary

  The supply vessels provide offshore installations with supplies from an onshore base according to weekly sailing plans. The goal is to decide the cost-optimal fleet of vessels on the long-term hire. The problem is stochastic as sailing speed and service time depend on uncertain weather conditions. Due to delays some installations may not be served within the planned route duration, and not received supplies have to be delivered later. We propose a discrete-event simulation model which evaluates alternative fleet size configurations depending on several strategies of later delivery of supplies.

• Qian, Fubin; Gribkovskaia, Irina; Laporte, Gilbert & Halskau sr, Øyvind (2012). Passenger and pilot risk minimization in offshore helicopter transportation. Show summary

  In the offshore petroleum industry, employees are transported to and from offshore installations by helicopter, which represents a major risk. We analyze how to improve transportation safety by solving the helicopter routing problem with a risk objective expressed in terms of expected number of fatalities. A mathematical model is proposed and a tabu search heuristic is applied to this problem. Three routing policies are considered: a direct routing policy, a Hamiltonian routing policy, and a general routing policy. Extensive computational experiments are conducted on instances derived from real data in order to assess and compare these policies under a travel time, a passenger risk and a combined passenger and pilot risk objective. Several management insights can be derived from this study. In particular, our results show that passenger transportation risk can be reduced by increasing travel time at the expense of pilot risk. This can be achieved through a reduction of the average number of passengers onboard by applying either a Hamiltonian or a general routing policy. Our methodology can also be used to derive an equitable distribution of risk between passengers and pilots, considering that pilots fly much more frequently than passengers. Furthermore, the helicopter routing problem is addressed as a multi-objective optimization problem. Two scenarios are considered for the cost objective. The cost objective may contain only travel time, or it is a combined travel time and service time. We apply a multi-objective genetic algorithm and an epsilon-constraint approach based on tabu search to instances derived from real data. Computational results show that the generic algorithm is capable of generating a large number of high quality solutions within reasonable times for the multi-objective helicopter routing problem. As compared to the genetic algorithm, the epsilon-constraint approach generates a small number of better quality solutions and requires more computing time.

• Norlund, Ellen Karoline & Gribkovskaia, Irina (2012). Reducing emissions in offshore supply vessel planning by speed optimization. Show summary

  Supply vessel activities, being crucial for the offshore oil and gas production, are the main source of emissions in the upstream offshore supply chain. The primary way to decrease emissions from vessels is by fuel consumption reduction. We address how to reduce fuel consumption in supply vessel activities by considering speed optimization when creating supply vessel schedules. The algorithm used for determining fleet mix and generating vessel schedules for a given time horizon consists of pre-generation of feasible voyages and packing them into vessel schedules using a set partitioning optimization model where the sum of the total vessel charter cost and the fuel cost is minimized. We propose four speed optimization strategies and show how to combine the supply vessel planning algorithm with these strategies to reduce emissions. In the first strategy, the basic solution is first found with the design vessel speed. Then, we iteratively run the algorithm with decreased speed until it generates a solution with increased fleet size, and choose the solution yielding the maximum reduction in fuel consumption compared with the basic solution. The three other strategies are speed optimization algorithms determining speed on voyage legs during voyage generation phase. One is reducing speed on a voyage leg if it is possible without violating voyage arrival times. Another is utilizing the total voyage idle time to determine the speed for each leg by rescheduling arrival times. The last is a recursive algorithm determining speed on each leg utilizing service time windows. Results of computational tests on real instances show that fuel consumption reduction can be achieved through utilization of waiting time for service and slacks in vessel schedules. The best strategy, yielding between 17% and 25% reduction in fuel consumption without an increase in the fleet size, is to optimize speed on each sailing leg.

• Norlund, Ellen Karoline & Gribkovskaia, Irina (2012). Speed strategies for green supply vessel planning. Show summary

  We study how to reduce emissions in supply vessel activities through speed optimization when planning vessel schedules by solving a MIP model for a pre-generated set of voyages. Several speed strategies, determining speed for the entire voyage or optimizing speed for each voyage leg, are proposed. These strategies are applied either a priori during voyage generation or a posterior to the voyages in the constructed schedule. Results of tests on several real-life instances show that emissions can be significantly reduced when using speed optimization in supply vessel planning.

• Gribkovskaia, Irina; Halskau sr, Øyvind & Qian, Fubin (2012). On routing and risk minimization in offshore helicopter transportation. Show summary

  Helicopters are often used for transporting crews to and from offshore installations. Helicopter transportation is regarded as one of the main risks in the offshore industry and the oil companies want to minimize this risk. We show how the expected number of fatalities can be reduced by applying different routing strategies. We present trade-offs between the number of helicopters used and the expected risk using real data from the Norwegian offshore industry.

• Qian, Fubin; Gribkovskaia, Irina; Laporte, Gilbert & Halskau sr, Øyvind (2011). Improving transportation safety for passenger and pilot in offshore helicopter routing. Show summary

  In the offshore petroleum industry, employees are transported back and forth to the offshore installations by helicopter, which represents a major risk. A mathematical model and a tabu search heuristic are proposed to improve transportation safety by minimizing risk for passengers and pilots in terms of the expected number of fatalities in helicopter transportation. Three routing policies are implemented and compared: a direct service policy, a Hamiltonian solution policy, and a general solution policy. Computational results show that transportation risk can be reduced by using some extra flying hours, compared to the classical solutions which only consider total travel time under a Hamiltonian solution policy. Under general solution policy, low risk solutions for both passengers and pilots are obtained when minimizing the total risk. We also attempt to achieve equitable distribution of risk between passengers and pilots considering that pilots fly much more frequently than passengers.

• Qian, Fubin; Gribkovskaia, Irina; Laporte, Gilbert & Halskau sr, Øyvind (2011). Passenger and pilot risk minimization in offshore helicopter transportation. Show summary

  In the offshore petroleum industry, employees are transported to and from the offshore installations by helicopter, which represents a major risk. This paper analyzes how to improve transportation safety by solving the helicopter routing problem with an objective expressed in terms of expected number of fatalities. A mathematical model is proposed and a tabu search heuristic is applied to this problem. Three routing policies are considered: a direct service policy, a Hamiltonian solution policy, and a general solution policy.Extensive computational experiments are conducted.

• Gribkovskaia, Irina; Shyshou, Aliaksandr; Qian, Fubin; Laporte, Gilbert; Fagerholt, Kjetil & Halskau sr, Øyvind (2011). Vehicle routing problems arising in servicing offshore oil installation.
• Gribkovskaia, Irina; Kurhuzava, Lidziya & Svirydava, Yuliya (2011). Development of routing planning tools for a distribution company.
• Shyshou, Aliaksandr; Gribkovskaia, Irina; Fagerholt, Kjetil & Laporte, Gilbert (2010). Heuristic solution method for a supply vessel planning problem arising in offshore oil and gas operations.
• Shyshou, Aliaksandr; Fagerholt, Kjetil; Gribkovskaia, Irina & Laporte, Gilbert (2010). A large neighbourhood search heuristic for a periodic supply vessel planning problem arising in offshore oil and gas operations. Show summary

  Upstream logistics in the Norwegian oil industry includes, along with other activities, providing the offshore installations with necessary supplies. These are periodically delivered to the installations by supply vessels from onshore bases. This paper proposes a large neighbourhood heuristic for a real-world periodic supply vessel planning problem faced by StatoilHydro, the largest Norwegian offshore oil and gas operator. However, the model and the algorithm provided in the paper are of wide applicability. The problem calls for the simultaneous determination of a repetitive weekly sailing plan and of the configuration of the supply vessel fleet. Computational comparisons with an exact solution method results demonstrate the competitiveness of the heuristic.

• Qian, Fubin; Gribkovskaia, Irina & Halskau, Øyvind (2010). Helicopter routing in the Norwegian oil industry : including safety concerns for passenger transport. Show summary

  PURPOSE: In the Norwegian offshore oil industry, helicopters have been used as a major mode of transporting personnel to and from offshore installations for decades. Helicopter transportation represents one of the major risks for offshore employees. The purpose of this paper is to study the safety of helicopter transportation in terms of the expected number of fatalities on operational planning level. METHOD: Based on an analysis of helicopter accidents, this paper proposes a mathematical model that can aid the planning of routes for the fleet in order to minimize the expected number of fatalities. FINDINGS: A theorem proven in this paper tells that hub-and-spoke configuration is the best way of flying helicopter in terms of minimizing expected number of fatalities. Computational results indicate the expected number of fatilities may be reduced at the expence of longer travel time by implementing the proposed method into route planning for the helicopter fleet. LIMITATIONS: The main limitation is the present inability to solve large instances. IMPLICATIONS: The suggested procedure is able to provide the decision-makers with a set of solutions from which they can choose the best trade-off between travel time and transportation safety. VALUE: The mathematical model and theoretical results for route planning with a safety-based objective are original.

• Qian, Fubin; Gribkovskaia, Irina; Laporte, Gilbert & Halskau, Øyvind (2010). A tabu search heuristic for offshore helicopter routing problem with focus on passenger safety. Show summary

  A mathematical model is proposed to improve passenger transportation safety by minimizing the expected number of fatalities in offshore helicopter transportation. Tabu search heuristics are developed. Both the mathematical model and heuristics are capable of producing general solutions, namely solutions allowing a second visit to installations. Computational results show that safety performance can be significantly improved by introducing general solution strategy to helicopter routing problem.

• Shyshou, Aliaksandr; Gribkovskaia, Irina & Barceló, Jaume (2009). Offshore anchor handling operations : a simulation analysis of different vessel fleet configurations. Show summary

  We present a fleet sizing problem arising in anchor handling operations related to movement of offshore mobile units. The operations are performed by dedicated vessels, which can be hired either on the long-term or spot basis. We propose a simulation-based approach to decide the cost-optimal fleet of vessels on the long-term hire to cover future operations.

• Shyshou, Aliaksandr; Gribkovskaia, Irina & Barceló, Jaume (2009). A simulation model for the fleet sizing problem arising in offshore anchor handling operations, Abctract CD of OYSSEUS Workshop 2009 International Workshop on Freight Transportation and Logistics, Çesme, Turkey, 2009-05-26 - 2009-05-29. ODYSSEUS.
• Shyshou, Aliaksandr; Gribkovskaia, Irina & Barceló, Jaume (2009). A simulation model for the fleet sizing problem arising in offshore anchor handling operations.
• Gribkovskaia, Irina & Shyshou, Aliaksandr (2009). A simulation study of the fleet sizing problem arising in offshore anchor handling operations.
• Shyshou, Aliaksandr; Gribkovskaia, Irina & Barceló, Jaume (2009). Offshore anchor handling operations : a simulation analysis of different vessel fleet configurations, Program and Abstracts of Optimization Days 2009, GERAD - HEC Montréal, Canada, 2009-05-04 - 2009-05-06. GERAD Group for Research in Decision Analysis - HEC Montréal. Show summary

  We present a fleet sizing problem arising in anchor handling operations related to movement of offshore mobile units. The operations are performed by dedicated vessels, which can be hired either on the long-term or spot basis. We propose a simulation-based approach to decide the cost-optimal fleet of vessels on the long-term hire to cover future operations.

• Gribkovskaia, Irina & Laporte, Gilbert (2008). Solving a family of pickup and delivery vehicle routing problems arising in reverse logistics and the supply of oil and gas platforms.
• Gribkovskaia, Irina & Laporte, Gilbert (2008). Solving a family of pickup and delivery vehicle routing problems arising in reverse logistics and the supply of oil and gas platforms, ECCO XXI - Dubrovnik, Croatia, May 29-31. 2008 : Conference Proceedings. Croatian Operational Research Society (HDOI). p. 38–39. Show summary

  Real world routing problems are often presented by large and complex models, and instances of realistic size are very hard to solve. In most cases one cannot fins optimal solutions, but has to use heuristic solution methods to find good solutions. It is, however, also of interest to find optimal solutions for smaller instances for comparisons with heuristic methods. We show that small instances of a real-world routing and inventory problem can be solved to optimality by using a column generation approach. Our problem deals with transportation of animals for slaughter in Norway, and standard models for routing problems have to be extended to mirror important details from the real world. In this case, especially two aspects are interesting: 1. A solution (route plan) has to fit to both the slaughter plan and inventory capacities at the slaughterhouse. This means we add global inventory constraints to our routing problem. 2. When different animal types are transported on the same vehicle, they have to be kept in separate compartments on board the vehicle for animal welfare reasons. This leads to a loading problem, where the visiting order of farms plays an important role in determining the total capacity of each vehicle. Computational results and comparisons to heuristic methods are presented.

• Gribkovskaia, Irina; Laporte, Gilbert & Shyshou, Aliaksandr (2007). The single vehicle routing problem with deliveries and selective pickups. Show summary

  The Single Vehicle Routing Problem with Deliveries and Selective Pickups (SVRPDSP) is defined on a graph in which n pickup and delivery demands are associated with customer vertices. In the SVRPDSP, all deliveries must be performed, but pickups are optional. The pickup demand of a customer is either fully collected, in which case it generates a revenue, or it is not collected at all. In other words, partial pickups are not allowed. The SVRPDSP consists of designing a vehicle route containing the depot and all customers, satisfying the following conditions: 1) all deliveries are performed; 2) some pickups may be performed. This definition does not specify the number of visits made at each customer. If no pickup is made, or if the pickup and the delivery are performed during the same visit, the number of visits is one, and it is two otherwise. The SVRPDSP is NP-hard since it reduces to the Traveling Salesman Problem (TSP) if none of the customers has a pickup demand and the vehicle capacity is sufficient to accommodate all the delivery demands. In the SVRPDSP a pickup revenue is associated with each vertex, and the pickup demand at that vertex will be collected only if it is profitable to do so. The net cost of a route is equal to the sum of routing costs, minus the total collected revenue. The aim is to design a vehicle route of minimum net cost, visiting each customer, performing all deliveries, and a subset of the pickups. Applications of this problem arise in reverse logistics. A mixed integer linear programming formulation, including lifted inequalities, is proposed for the SVRPDSP. Classical construction and improvement heuristics, as well as a tabu search heuristic, are developed and tested on a group of instances (with n ranging from 16 to 101) derived from VRPLIB. Extensive computational results show that the solutions produced by the proposed heuristics are near-optimal. There is also some evidence that the best solutions identified by the heuristics are frequently non-Hamiltonian and may contain one or two customers visited twice.

• Bakhrankova, Krystsina; Gribkovskaia, Irina & Haugen, Kjetil Kåre (2007). Production planning in continuous process industries. Show summary

  Production planning is at the core of manufacturing flow management - one of the key supply network business processes. A significant theoretical basis related to production planning for different manufacturing processes has been established in the extant literature. The classic product-process matrix has been put forward to match the product features with the process characteristics, distinguishing between the four process types: jumbles, disconnected line, connected line, and continuous flows. The last process type corresponds to continuous process industries that are least researched with respect to specific optimization issues. This disbalance has developed due to traditional contrasting of discrete and continuous environments without a proper differentiation between distinct process industries. In this paper we concider conceptual and optimization issues related to production planning incontinuous process industries with nondiscrete products. The purpose of this paper is to locate continuous nondiscrete production within existing theoretical frameworks, discuss general features of continuous process industries and clarify their core production planning characteristics, contrasting them with other manufacturing process types. In particular, we consider a concrete example of a continuous nondiscrete manufacturing environment to further refine its features and discuss known formalization methods applied to production planning for similar settings, assessing their potential use for the system in question. Finally, we develop a mathematical optimization model for the incumbent production system allowing a better utilization of production capacity with respect to energy costs while synchronizing production and distribution planning in the holistic supply network context

• Gribkovskaia, Irina (2007). Single vehicle pickup and delivery problem with capacitated customers, Sixth International Colloquium on Graphs and Optimization : Abstract Booklet. Schweizerische Vereinigung für Operations Research. Show summary

  The single vehicle pickup and delivery problem with capacitated customers is encountered in servicing of offshore oil and gas platforms. A single vessel must perform pickups and deliveries at several offshore platforms where all delivery demands originate at a supply base and all pickup demands are also destined to the base. The vessel capacity may never be exceeded along its route. In addition, the amount of space available for loading and unloading operations is limited at each platform. The problem consists of designing a least cost vehicle (vessel) route starting and ending at the depot (base), visiting each customer (platform) making all pickups and deliveries, and such that there is always sufficient capacity in the vehicle and at the customer location to perform the pickup and delivery operation. We present a mathematical model as well as several construction heuristics and a tabu search algorithm yielding general where any customer can be visited either once or twice.

• Bakhrankova, Krystsina; Gribkovskaia, Irina & Haugen, Kjetil Kåre (2007). Production planning in continuous process industries, Proceedings of the 19th Annual Conference for Nordic Researchers in Logistics, NOFOMA 2007 / Halldórsson, Á., Stefánsson, G. (Eds.) (CD-ROM). The Nordic Logistics Research Network; NOFOMA. p. 69–84.
• Gribkovskaia, Irina & Laporte, Gilbert (2007). Solving a family of single vehicle pickup and delivery problems by tabu search. Show summary

  In 1-M-1 pickup and delivery single vehicle routing problem a vehicle delivers from a depot to a set of customers as well as pickups at the same customers before returning to the depot. We propose a unified tabu search heuristic for several variants of the problem: the general case, the case with customers having limited capacity, the case with selective pickups, and the case with constraints on the time-lag or sequencing order between the pickup and delivery visits at the customer location.

• Gribkovskaia, Irina (2007). Routing of supply vessels to offshore oil and gas platforms.
• Gribkovskaia, Irina (2007). Single vehicle pickup and delivery problem with capacitated customers. Show summary

  The single vehicle pickup and delivery problem with capacitated customers is encountered in servicing of offshore oil and gas platforms. A single vessel must perform pickups and deliveries at several offshore platforms where all delivery demands originate at a supply base and all pickup demands are also destined to the base. The vessel capacity may never be exceeded along its route. In addition, the amount of space available for loading and unloading operations is limited at each platform. The problem consists of designing a least cost vehicle (vessel) route starting and ending at the depot (base), visiting each customer (platform) making all pickups and deliveries, and such that there is always sufficient capacity in the vehicle and at the customer location to perform the pickup and delivery operation. We present a mathematical model as well as several construction heuristics and a tabu search algorithm yielding general where any customer can be visited either once or twice.

• Gribkovskaia, Irina (2007). Single vehicle pickup and delivery problem with capacitated customers [ppt]. Show summary

  We introduce a pickup and delivery problem encountered in the servicing of offshore oil and gas platforms in the Norwegian Sea. A single vessel must perform pickups and deliveries at several offshore platforms. All delivery demands originate at a supply base and all pickup demands are also destined to the base. The vessel capacity may never be exceeded along its route. In addition, the amount of space available for loading and unloading operations is limited at each platform. The problem, called the Single Vehicle Pickup and Delivery Problem with Capacitated Customers (SVPDPCC) consists of designing a least cost vehicle (vessel) route starting and ending at the depot (base), visiting each customer (platform), and such that there is always sufficient capacity in the vehicle and at the customer location to perform the pickup and delivery operations. A mixed integer linear programming model yielding general solutions allowing for up to two visits at customers is proposed, and the impact of the new stipulations on the solutions is analyzed. We have developed several construction heuristics as well as a tabu search algorithm. Our best heuristic consists of applying tabu search starting with an initial solution generated with construction heuristic which combines nearest neighbour, cheapest insertion and backward merging procedures. The solutions produced by our algorithm may be Hamiltonian or not, depending partly on vertex demands and relative locations.

• Gribkovskaia, Irina; Laporte, Gilbert; Vlcek, Martin & Halskau, Øyvind (2006). General solutions to the single Vehicle Routing Problem with pickups and deliveries, Proceedings of Odysseus 2006 : the Third International Workshop on Freight Transportation and Logistics.
• Halskau, Øyvind; Gribkovskaia, Irina; Gribkovskaia, Irina & Nordli, Atle (2006). Economic order quantities assuming generalised order costs.
• Gribkovskaia, Irina; Laporte, Gilbert; Vlcek, Martin & Halskau, Øyvind (2006). General solutions to the single Vehicle Routing Problem with pickups and deliveries.
• Aas, Bjørnar; Gribkovskaia, Irina; Shlopak, Alexander & Halskau, Øyvind (2006). Routing of supply vessels serving oil and gas installations in the Norwegian Sea. Show summary

  In the Norwegian oil and gas industry the upstream logistics includes providing the offshore installations with needed supplies and return flow of used materials and equipment. A part of these activities is planning of routes for supply vessels. This paper considers a real-life routing problem for supply vessels serving offshore installations at Haltenbanken outside the northwest coast of Norway from the supply base in Kristiansund. For the time being, the planning takes place for one vehicle at a time. Thus, we present the problem as a single vehicle routing problem with pickups and deliveries (SVRPPD). When solving this class of problems it was commonly assumed that all customers are visited once on a vehicle route shaped as a cycle. However, relaxation of the “one-visit” assumption can lead to different routing options that encompass the traditional cycle and may be superior in terms of travelling cost. In such non-traditional general solutions each customer is allowed to be visited either once for combined pickup and delivery, or twice, when the first visit is used for the delivery and pickup is performed on the second visit on the way back to the depot. Further, the reallife problem considered has a unique feature arising from the limited deck capacity at the offshore installations that complicates the performance of service and has never been treated in the literature on routing planning. This paper introduces a mixed integer linear programming model yielding general solutions for SVRPPD extended with a new set of constraints. The constraints ensure that there is enough free space at the platform deck and at the supply vessel deck to perform delivery and pickup operations. The model is tested on reallife sized instances based on data provided by the Norwegian oil company Statoil. Results of the tests show that in order to obtain optimal solutions to the SVRPPD with limited free storage capacities at installations one has to include in the formulation the possibility of two visits at platforms, the storage feasibility and the service feasibility requirements.

• Halskau, Øyvind; Gribkovskaia, Irina; Laporte, Gilbert & Vlcek, Martin (2005). Heuristic algorithms for the travelling salesman problem with pickup and delivery demands and non-simultaneous services. Show summary

  Recently, there has been an increasing interest in vehicle routing problems with pickup and delivery demands (VRPDP), see [1, 2, 3, 4,]. Traditionally such problems have been solved as backhauls problems where all the delivery customers are visited first and all the pickup customers are visited afterwards. Another traditional approach has been to perform the two kinds of services simultaneously, that is, a customer is only visited once. However, this last restriction does not necessarily give the best solution. In some cases it may be convenient or cost effective to perform the two services non-simultaneously. We restrict ourselves to only one vehicle. We consider a travelling salesman problem with pickup and delivery demands (TSPPD) where all demands originate from a depot and all pickups are brought back to the depot, but where a customer can be visited once or twice. We propose a constructive heuristic for the above problem. The heuristic can yield feasible solutions where the degree of any node in the solution can in principle be either 2, 3 or 4. Hence, the resulting route performed by the vehicle can take many different shapes. We test the heuristic together with a tabu search algorithm on a number of cases taken from a public library.

• Gribkovskaia, Irina; Gullberg, Bjørn Olav; Hovden, Karl J. & Wallace, Stein W. (2005). Optimization model for a livestock collection problem. Show summary

  The value chain of the Norwegian meat production industry has recently been through major structural changes resulting in increased flows and transportation needs at all levels. This work presents results of the initial stage of a five-year research project between Norwegian Meat Research Center, Norwegian meat companies and Molde University College. The main goal of the project is to develop a decision support system for transportation of live animals to a slaughter house to reduce transportation costs while maintaining high level of livestock welfare and meat quality, as these are three main factors for the profitability of both farmers and the meat industry. The aim of this paper is to introduce a new yet very practical supply chain management problem as a mixed integer linear programming model. The model presented is a combined vehicle routing and production planning problem. We introduce the possibility for multiple routes for a given vehicle on a given day in a multiple-period planning perspective. Arrival times of the loaded vehicles to the slaughter house are controlled by production (slaughter) rate and inventory level at the abattoirs so that the supply of animals for slaughter is steady and production breaks are avoided. Livestock welfare is secured by the route duration constraints. The output of the model provides starting and ending times for each route together with arrival times at each farm.

• Halskau, Øyvind; Aas, Bjørnar & Gribkovskaia, Irina (2004). Pick-up and deliveries from a depot with capacity restrictions at the customers.
• Gribkovskaia, Irina; Halskau, Øyvind; Håkonsen, Jan Kolbjørn & Richstad, Ole Kristian (2004). Effect of time windows on distribution costs.
• Gribkovskaia, Irina & Halskau, Øyvind (2003). Heuristics for the pick-up and delivery problem with one vehicle and non-Hamiltonian routes. Show summary

  The pick-up and delivery problem as a generalisation of the classical Vehicle Routing Problem has recently received a certain attention in the literature. This is especially true for planning situations dealing with only one vehicle, that is, a generalisation of the Travelling Salesman Problem and situations where all the delivery demands are brought from a depot to the delivery customers and all the pick-up demands are brought back to the depot. Several heuristics are proposed by several different authors. However, the existing approaches to this problem seem to only consider Hamiltonian cycles as a result of the heuristics. We show that there will be situations where Hamiltonian cycles are inferior to other sub-graphs in terms of costs. In order to obtain such solutions one must relax the assumption that each customer is served only once, that is we assume that the services for at least one of the customers can be performed non-simultaneously. We present two different heuristics that can yield different solutions to the above problem. The solutions can either be Hamiltonian cycles or more complicated sub-graphs like lassos or combinations of paths and sub-cycles. We present some preliminary results for the heuristics.

• Halskau, Øyvind & Gribkovskaia, Irina (2003). Heuristics for pickup and delivery problems allowing non-simultaneous services.
• Buvik, Arnt & Gribkovskaia, Irina (2002). Specific assets and hierarchical governance in manufacturer-supplier relationships : the moderating effect of bargaining power on buyer influence in industrial business-to-business relationships. Show summary

  In a basic model of transaction cost analysis (TCA), neither market power nor power based on resource-dependence play a significant role. In this article the authors examine wheter the buyer's bargaining power influences the alignment of hierarchical governance in buyer-supplier relationships. Data from a survey of 183 industrial purchasing relationships provide empirical support for the theoretical predictions. The empirical findings demonstrate that the buying firm's bargaining power does affect its ability to have hierarchical governance implemented to safeguard specific assets in business-to-business relationships. When the buying firm's bargaining power is high, buyer-specific assets are strongly related to high buyer influence in supplier relationships. On the other hand, in relationships where the buyer possess low or modest bargaining power, employment of buyer-specific assets does weaken the buying firm's ability to exercise influence over the supplier firm. The empirical findings indicate that resource-dependence considerations offer an important complement to transaction cost analysis when we consider the transacting parties' ability to provide safeguarding arrangements by hierarchical governance

• Gribkovskaia, Irina; Halskau, Øyvind & Lium, Arnt-Gunnar (2002). Distribution within the norwegian co-operation meat industry.
• Kisialiou, Yauheni; Gribkovskaia, Irina & Laporte, Gilbert (2018). Supply vessel routing and scheduling under uncertain demand . Høgskolen i Molde - Vitenskapelig høgskole i logistikk. ISSN 978-82-7962-246-8.
• Kisialiou, Yauheni; Gribkovskaia, Irina & Laporte, Gilbert (2017). An adaptive large neighborhood search heuristic for the periodic supply vessel planning problem with flexible departures and coupled vessels . Høgskolen i Molde - Vitenskapelig høgskole i logistikk. ISSN 978-82-7962-221-5.
• Kisialiou, Yauheni; Gribkovskaia, Irina & Laporte, Gilbert (2017). Robust supply vessel routing and scheduling. Molde University College - Specialized University in Logistics. ISSN 978-82-7962-225-3. Show summary

  We solve the problem of tactical supply vessel planning arising in the upstream offshore petroleum logistics. Supply vessels deliver all the necessary materials and equipment to offshore installations from an onshore supply base. Delivery takes place according to a weekly sailing plan called the vessel delivery schedule. The charter cost of supply vessels is the largest cost contributor in the upstream offshore supply. The planning of supply vessels should therefore be done so that their number is minimized and should at the same time provide reliable flow of supplies from the base. The execution of a weekly sailing plan is affected by weather conditions, especially in wintertime. Harsh weather conditions increase the number of vessels required to perform the operations as well as the service times at the installations, and thus disrupt the schedule, leading to additional costs and reduced service level. We present a metaheuristic capable of generating cost-efficient and robust vessel schedules. Keywords: maritime logistics; supply vessel planning; vehicle routing; robust vessel schedules.

• Norlund, Ellen Karoline; Gribkovskaia, Irina & Laporte, Gilbert (2015). Supply vessel planning under cost, environment and robustness considerations. Høgskolen i Molde - Vitenskapelig høgskole i logistikk. ISSN 978-82-7962-196-6. Show summary

  Offshore oil and gas installations need reliable cargo deliveries. The vessels supplying these installations on a periodic basis are expensive and constitute a source of emissions of greenhouse gases. Incorporating speed optimization into the supply vessel planning process may significantly reduce fuel consumption and hence emissions. In addition, speed optimization may yield cost reductions if the number of vessels used does not increase. A main uncertainty factor, especially in the winter season, is the weather conditions which impact sailing and service times. Cost minimization and the application of speed optimization strategies may have implications on the robustness of weekly supply vessel schedules since idle times in the schedules are reduced. We develop a simulation-optimization based methodology that considers costs, emissions and robustness in the generation of weekly supply vessel schedules. Results of analyses conducted on real-based instances show that robustness requirements may yield both increased emissions and costs in the winter season. However, depending on instance characteristics, different degrees of robustness can be incorporated with both costs and emissions reductions through speed optimization.

• Norlund, Ellen Karoline & Gribkovskaia, Irina (2014). Environmental performance of speed optimization strategies in offshore supply vessel planning under weather uncertainty. Høgskolen i Molde - Vitenskapelig høgskole i logistikk. ISSN 978-82-7962-190-4. Show summary

  Supply vessels serving oil and gas installations at sea are a major emission source of greenhouse gases in offshore logistics. Speed optimization strategies applied in tactical vessel planning significantly reduce fuel consumption and thus emissions. Nevertheless, environmental performance of theses strategies in rough weather conditions is difficult to estimate as the duration of supply vessel operations is weather dependent. In this paper we develop a simulation-optimization tool which estimates average fuel consumption for weekly vessel schedules. The schedules are constructed by using speed optimized vessel voyages which are simulated under different weather conditions. Results of tests on real instances show that rough weather conditions increase fuel consumption and costs. Application of speed optimization strategies reduces fuel consumption both in winter and summer, but the reduction may be at the expence of a fixed vessel cost increase in the winter season

• Gribkovskaia, Irina; Halskau sr, Øyvind & Kovyalov, Mikhail Y. (2012). Minimizing takeoff and landing risk in helicopter pickup and delivery operations. Høgskolen i Molde - Vitenskapelig høgskole i logistikk. ISSN 978-82-7962-156-0. Show summary

  The problem of minimizing total helicopter passenger risk caused by takeoffs and landings is studied. There are passenger pickup and delivery demands to be satisfied at given points. Each point is visited once. There are upper bound on the number of flights and upper bound on the helicopter passenger capacity. The objective function is a linear combination of the numbers of passengers involved in takeoffs and landings at visited points. A solution is characterized by the number of flights, sets of visited points and their sequences for all flights. Properties of optimal solutions are established. Several cases are proved NP-hard. A dynamic programming algorithm is suggested for the general case. Effcient and easy for implementation algorithms are presented for the following cases: 1) a single flight, 2) the number of visited points not exceeding the number of flights, and 3) an unbounded helicopter capacity, equal risk coeffcients, and pickup demand equal to delivery demand at each point. Implementation of the suggested solutions into the real helicopter operations should decrease the number of fatalities in helicopter operations.

• Gribkovskaia, Irina; Kovalev, Sergey & Werner, Frank (2009). Lot-sizing for an imperfect continuous production on two machines. Otto-von-Guericke-Universitat Magdeburg. Show summary

  We study the problem of planning the production of new and recovery of defective units of the same product. The product is assumed to be continuously divisible. There are a main facility dedicated to the original production and a facility dedicated to re-manufacturing defective units coming from the main facility. Units fabricated on the main facility are inspected for quality in batches. The quality inspection requires some time and can be performed on-line or off-line. After the inspection has been completed, defective units of the inspected batch are transported to the re-manufacturing facility. The transportation also requires some time. We assume that the fraction of the defective units is the same in each batch on the manufacturing facility and that the re-manufacturing facility is perfect. Given a demand for good quality units of the product and an upper bound K on the number of batches, the problem is to find a sequence of batch sizes such that the manufacturing cycle time is minimized. We suggest a linear programming formulation, prove several properties of an optimal solution, and finally develop an O(log K) time solution algorithm. A similar per time unit cost minimization problem is studied as well.

• Gribkovskaia, Irina & Laporte, Gilbert (2007). One-to-many-to-one single vehicle pickup and delivery problems. GERAD - Group for Research in Decision Analysis. Show summary

  In One-to-Many-to-One Single Vehicle Pickup and Delivery Problems a vehicle based at the depot must make deliveries and pickups at customers locations before returning to the depot. Several variants can be defined according to the demand structures and sequencing rules imposed on pickups and deliveries. In recent years there has been an increased interest in this family of problems. New formulations and efficient heuristics capable of yielding general solutions (unrestricted in shape) have been proposed. In addition, some new and interesting extensions have been analyzed, including problems with selective pickups and problems with capacitated customers. The purpose of this chapter is to review these developments. Dans les problèmes de cueillette et livraison de type 'un-à-plusieurs-à-un', un véhicule basé au dépôt doit effectuer des cueillettes et livraisons chez un ensemble de clients avant de retourner au dépôt. On peut définir plusieurs variantes de ces problèmes selon la structure de la demande et les règles de séquencement imposées sur les cueillettes et les livraisons. Au cours des dernières années, on a assisté à un intérêt accru pour ces problèmes. En particulier, on a proposé de nouvelles formulations donnant lieu à des solutions dont la forme n'est pas contrainte (des solutions dites générales). De plus, plusieurs nouvelles extensions intéressantes ont été analysées, incluant des problèmes avec cueillettes sélectives ou avec clients de capacité limitée. Le but de ce chapitre est de passer ces développements en revue

• Gribkovskaia, Irina; Halskau, Øyvind & Aas, Bjørnar (2005). Routing of supply vessels serving oil and gas installations in the Norwegian Sea. Høgskolen i Molde. ISSN 82-7962-066-4. Show summary

  This paper considers a routing problem for a single vehicle with pick-up and delivery demands (SVRPPD) where all delivery demands start from a depot and all pickup demands are brought back to the depot serving a set of customers. Such problems are encountered in many practical situations. Traditionally such problems have been treated under an explicit assumption of backhauls - all delivery demands performed first and then all pickup demands at the end of the route - or tacitly - when such demands are mixed along the route, all customers are served one and only one time. However, recent research has shown that these traditional ways of solving such problems not always lead to the optimal result. If one relaxes the tacit assumption that all customers only shall be visited once, several different routing options can appear. One such solution can be a so-called lasso-solution. In such solution the first customer on a route is visited twice. On the first visit, only the delivery service is performed, hence creating more free space on the vehicle. On the way back to the depot, the same customer is visited a second time, now in order to perform the pickup service. Other types of sub-graphs can also be superior to the lasso solution and/or the traditional solutions. In this paper we relax the assumption that each installation only can be visited once and offer a mathematical model for solving SVRPPD. Further, tacitly in the SVRPPD it is always assumed that there are no capacity restrictions for storing goods at the customers' sites. We consider such a situation and offer an extended mathematical programming model for the SCRPPD with capacity restrictions at the customers. We apply these models to a real case. The case considered in this paper is taken from the Norwegian off-shore activities where a set of off-shore installations outside the west-coast of Norway are served by the use of supply vessels. In this real problem the oil and gas installations have limited space for storing cargo on the installations' deck. All the mathematical models presented and applied to the situation yield different optimal solutions to the real routing problem, showing the necessity of the extensions. Not very much research has been done on such kind of problems and a lot of new challenges and possibilities arise

View all works in Cristin