Tasks performed
Professor in operations research, with the following research interests:
 Integer programming for optimization problems.
 Approximation algorithms and heuristics.
 Graph theory.
 Optimization methods applied to health care logistic problems.
Background
For a detailed CV, see http://home.himolde.no/~seur/
Publications

Eide, Line; Årdal, Gro Cesilie Håhjem; Evsikova, Nataliia; Hvattum, Lars Magnus & Urrutia, Sebastián (2020). Loaddependent speed optimization in maritime inventory routing. Computers & Operations Research.
ISSN 03050548.
123, s 1 12 . doi:
10.1016/j.cor.2020.105051
Show summary
Maritime inventory routing problems involve determining optimal routes for seagoing vessels between ports while managing the inventory of each port. Normally, such problems are considered with the vessels operating at fixed sailing speeds. However, the speed of vessels can typically be adjusted within an interval, and the actual fuel consumption depends on both the load and the speed of the vessel. The fuel consumption function combines speed and load in a nonlinear manner, but can be approximated through linearization. In this work, to evaluate the importance of taking into account that both speeds and load levels influence the fuel costs, the resulting solutions are contrasted with solutions from the case where speeds and travel costs are taken as constants, as well as the case where speed is a decision, but the cost considered to be independent of the load. For either of these cases, loaddependent speed optimization can be added as a postprocessing step. Computational experiments show that combining speed and load do have an impact on the selection of routes in maritime inventory routing problems, and that proper modelling of the fuel consumption can reduce sailing costs significantly. On the test instances considered, taking into account speed while ignoring the load leads to cost savings of around 38%. Considering the fuel consumption as a function of speed and load when planning leads to additional cost savings of 28%.

Pereira, Armando Honorio; Mateus, Geraldo Robson & Urrutia, Sebastián (2020). Branchandcut algorithms for the parborescence star problem. International Transactions in Operational Research.
ISSN 09696016.
. doi:
10.1111/itor.12857
Show summary
Given a connected digraph, a vertex designated as the root, and an integer p,theparborescence star problemis to choose p vertices besides the root and deﬁne a reverse arborescence spanning them. Each vertex outsidethe arborescence must be assigned to one vertex inside it. The objective of the problem is to minimize arborescence and assignment costs. We propose two formulations for the problem and prove theoretical resultsabout their strength. Moreover, we develop branchandcut algorithms based on each one of the formulations and improve an earlier branchandcut algorithm for the problem with an exact separation method.Additionally, we show that ﬁnding a feasible solution for an arbitrary instance is NPhard and introducepreprocessing procedures for the problem. The proposed algorithms are evaluated with a set of benchmarkinstances from the literature. For small and mediumsized instances, our proposed algorithms provide thebest results when compared to the existing algorithm from the literature. For large instances, the proposedalgorithms are shown to be competitive with the existing approach.Keywords: integer programming, branch and cut, arborescence, wireless sensor networks

Faraj, Marcelo Fonseca; Urrutia, Sebastián & Sarubbi, Joao F M (2019). Gamma deployment problem in grids: hardness and new integer linear programming formulation. International Transactions in Operational Research.
ISSN 09696016.
27(6), s 2740 2759 . doi:
10.1111/itor.12759
Show summary
Vehicular networks are mobile networks designed for the domain of vehicles and pedestrians. These networks are an essential component of intelligent transportation systems and have the potential to ease traffic management, lower accident rates, and offer other solutions to smart cities. One of the most challenging aspects in the design of a vehicular network is the distribution of its infrastructure units, which are called roadside units (RSUs). In this work, we tackle the gamma deployment problem that consists of deploying the minimum number of RSUs in a vehicular network in accordance with a quality of service metric called gamma deployment. This metric defines a vehicle as covered if it connects to some RSUs at least once in a given time interval during its whole trip. Then, the metric parameterizes the minimum percentage of covered vehicles necessary to make a deployment acceptable or feasible. In this paper, we prove that the decision version of the gamma deployment problem in grids is NPcomplete. Moreover, we correct the multiflow integer linear programming formulation present in the literature and introduce a new formulation based on set covering that is at least as strong as the multiflow formulation. In experiments with a commercial solver, the set covering formulation widely outperforms the multiflow formulation with respect to running time and linear programming relaxation gap. Keywords: gamma deployment; complexity; integer linear programming.

Urrutia, Sebastián; Milanés, Anolan Yamilé & Løkketangen, Arne (2015). A dynamic programming based local search approach for the double traveling salesman problem with multiple stacks. International Transactions in Operational Research.
ISSN 09696016.
22(1), s 61 75 . doi:
10.1111/itor.12053
Show summary
The double traveling salesman problem with multiple stacks consists in determining a pair of routes (pickup and delivery) for a unique vehicle in two different and disjoint networks. It models a realistic transportation problem with loading/unloading constraints imposed by having a set of lastinfirstout (LIFO) stacks used for storing the goods being transported. The arrangement of the items in the container determines the loading plan that in terms constrains both routes. In this paper, we propose a novel local search approach. The local search heuristic is applied to the loading plan instead of working directly on the routes. A dynamic programming algorithm is used to map the loading plan solution into corresponding optimal routes. Computational results show that the proposed approach is competitive with stateoftheart heuristics for the problem.
View all works in Cristin

Bentsen, Håkon; Hvattum, Lars Magnus & Urrutia, Sebastián (2019). A review of Binary Integer Programming applications and solution methods.
Show summary
Binary Integer Programming (BIP) covers a large variety of different problems, with many real world applications. This work first reviews the scientific literature with the aim of creating an overview of the most important applications of pure BIP models. The literature review is conducted using different search strings in order to find the relevant papers from prominent online databases. The findings are then filtered manually and categorized by application. There are relatively few general purpose solvers for BIP, and computational experiments are conducted to show their performance on benchmark instances from the literature, covering a wide variety of applications. Based on these results, we argue that there is a need for improved general purpose solvers for BIP problems, with a performance level closer to what is found in specialized solvers. Keywords: programming, mixedinteger

Hvattum, Lars Magnus; Zaitseva, Anna & Urrutia, Sebastián (2018). Profit maximization in inventory routing problems.

Oppen, Johan; Cavalcante, Evellyn; Samer, Phillippe & Urrutia, Sebastián (2016). Combinatorial relaxation bounds and preprocessing for berth allocation problems.

Sampaio, Afonso Henrique; Urrutia, Sebastián & Oppen, Johan (2015). A decomposition approach to solve the quay crane scheduling problem.

Milanés, Anolan Yamilé; Urrutia, Sebastián & Løkketangen, Arne (2013). Uma heurística paralela na GPU para o problema do Caixeiro Viajante Duplo com Múltiplas Pilhas.

Urrutia, Sebastián; Milanés, Anolan Yamilé & Løkketangen, Arne (2013). A GPU algorithm for the DTSPMS.

Løkketangen, Arne; Milanés, Anolan Yamilé & Urrutia, Sebastián (2012). Double TSP with multiple stacks  strategic oscilliation and heuristic search.

Urrutia, Sebastián & Løkketangen, Arne (2012). A Dynamic Programming based Local Search Approach for the Double Traveling Salesman Problem with Multiple Stacks.

Urrutia, Sebastián; Milanés, Anolan Yamilé & Løkketangen, Arne (2012). A strategic oscillation heuristic for the double Traveling Salesman Problem with multiple stacks.
Show summary
The extended abstract describes a new heuristic for the Double Traveling Salesman Problem with Multiple Stacks. Preliminary computational results indicate that the heuristics performance is very similar to that of state of the art algorithms.
View all works in Cristin
Published Aug. 13, 2019 10:20 AM
 Last modified Jan. 2, 2020 6:46 PM