Seminar: Dealing with the weather - the Canadian tour operator problem on paths Event as iCalendar

15 April 2015

2 - 3pm

Venue: Room 439.G10

Location: Ground Level, UniServices House, 70 Symonds Street

Host: Dr Richard Clarke

Contact email: rj.clarke@auckland.ac.nz

 

A Department of Engineering Science seminar by Sabine Buttner, University of Kaiserslautern, Germany.

 

Abstract:

A tour operator needs to find a closed tour for a tourist bus through a given road network. The lengths of the roads are known, but nevertheless, some of the edges might be blocked by avalanches and this is known only when reaching one of its endpoints. The intended tour has to be adapted immediately if necessary. The tour operator has the option to avoid visiting a node by paying a (known) refund to the tourists. The goal is to minimise the sum of the overall travel costs plus refunds.

The problem is an online variant of the prize-collecting traveling salesman problem with the online feature adapted from the known Canadian traveller problem. In this talk, we restrict ourselves to cases in which the underlying graph is a simple path and give a lower bound and a matching algorithm on the competitive ratio - the standard tool when analysing online optimisation problems. Furthermore, we go beyond competitive analysis and present the effect of resource augmentation.