Lecturer

• O.Univ.Prof.Dr. Richard Hartl

Dates & Places

• Thursday 2:00-4:00 p.m. (BWZ, Seminarraum 1)
• Starting on March 10, 2011

Study Programs

• Mag. internationale Betriebswirtschaft (KFK Production Management,  KFK SupplyChain Management, KFK Transportation Logistics)
• Mag. Betriebswirtschaft (KFK Production Management,  KFK Supply Chain Management, KFK Transportation Logistics)
• partly also KFK Operations Research
• Wirtschaftsinformatik alter Studienplan (Bakk., Mag., KFK Produktionsmanagement)

Course Content

• This course (Seminar) will focus on "(Team) Orienteering Problems".
• The basic model is the travelling salesman problem (TSP, "Handlungsreisendenproblem", "Rundreiseproblem", see introductory course ABWL Produktion & Logistik, VK, and the KFK course "transportation logistics")
• While in the basic TSP every customer must be visited, in Orienteering Problems or, more generally, in "TSPs with profit" a number of "customers must be selected for visit and at each customer location a certain benefit/profit is collected. Then, a trade-off between tour length and total collected profit must be found. Variants of the "TSPs with profit" are:
• A) The Orienteering Problem (OP), where the total tour length is restricted and under this constraint a maximum profit must be collected. The name comes from the orienteering game "Orientierungslauf" (although strictly speaking this is more like a normal TSP).
• B) The Price collecting TSP, where a certain minimum profit must be collected and the cost must be minimized
• C) Profitable tour problem (PTP), where collected profit minus traveling cost is maximixed
  

• If collecting the profits is distributed over several vehicles/persons with limited capacity, this is called 
• A) Team Orienteering Problem (TOP), 
• B) price collecting VRP, 
• C) Capacitated Profitable tour problem (CPTP)
• or more generally speaking, VRP with profits.
• Various applications are possible
• In tourism a tourist wants to find the best tradeoff between visiting a large number of sights and a limited time budget.
• On the other hand, salespersons have to select the potential customers to be visited on the next day(s) in order to maximize the expected sales volume.

• All these problems are np-hard and heuristic solution methods are typically applied.

• Basic models and approaches from the literature will be discussed and some recent research articles will be presented. 

Requirements

• regular presence and participation in discussion
• literature study
• presentation
• term paper (Seminararbeit)

Prerequisites

• This course (Seminar) is intended as the final course in a KFK. Thus, it should only be taken after some other courses in the corresponding area.
• Minimum requirement for admission is
•  the course „Operations Management“ (old "Studienplan") or 
• "Transportation Logistics (TL)", "Production Analysis", or "Supply Chain Management" (new "Studienplan")

Basic Literature 

• C. Archetti, D. Feillet, A. Hertz, M.G. Speranza (2009): The capacitated team orienteering and profitable tour problems, Journal of the Operational Research Society 60, 831 - 842.
  Only chapters 1 und 2.  >> download

• D. Feillet, P. Dejax, M. Gendreau (2005): Traveling salesman problems with profits. Transportation Science 39: 188–205.
  Everything except for Chapters 4.2 and 5.  >> download

Schedule "Würfelteil"

• The first part of the course is a so called "Würfelseminar", i.e. certain topics are to be prepared by all participants. Every 10 minutes, say, a different person will be asked (at random -> Würfel) to present the next pages of the underlying literature. The purpose is
      (i) to obtain some common knowledge base by all participants, and 
      (ii) to facilitate discussion.
• Literature for the "Würfelseminar": see "basic literature" above
• Schedule: 
  March 10: Introduction
  March 17:  no course unit, time for preparation
  March 24: "Würfelteil",  basic literature above to be prepared
  March 31:  continuation of "Würfelteil",  basic literature above to be prepared
  April 7:  continuation of "Würfelteil",  basic literature above to be prepared
• April 14 to May 19: break and easter holidays
• May 26: Presentation by students
• June 6: Presentation by students
• June 9: Presentation by students
• Note that after June 9 there is no possibility to give a presentation

Schedule "Spezialteil"

Term paper (Seminararbeit)

• A first version of the term paper should be available at the presentation. The final version can be handed in before the end of the semester.
• For guidelines concerning the term paper see:
  http://prolog.univie.ac.at/teaching/downloads/WissArbeiten.pdf
• For information concerning plagiarism and good scientific conduct see: http://prolog.univie.ac.at/teaching/downloads/Rechtliche%20Grundlagen_Infoblatt_070207.pdf