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 ho…