Semi-preemptive routing on a linear and circular track

Räbiger, Dirk and Schrader, Rainer (2009) Semi-preemptive routing on a linear and circular track.
Published in: Discrete Optimization Vol. 6 (3). pp. 223-230.

Abstract

The problem of routing a robot (or vehicle) between n stations in the plane in order to transport objects is well studied, even if the stations are specially arranged, e.g. on a linear track or circle. The robot may use either all or none of the stations for reloading. We will generalize these concepts of preemptiveness/nonpreemptiveness and emancipate the robot by letting it choose k le n reload-stations. We will show that the problem on the linear and circular track remains polynomial solvable.


Actions:
Download: [img] PDF - Preprinted Version
Download (144kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: 2 (Google Scholar) | 0 (Web of Science)
Uncontrolled Keywords: dial-a-ride pickup and delivery transportation
Subjects:
  • 05-XX Combinatorics > 05Cxx Graph theory > 05C45 Eulerian and Hamiltonian graphs

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C39 Dynamic programming

  • 68-XX Computer science > 68Rxx Discrete mathematics in relation to computer science > 68R05 Combinatorics

  • 90-XX Operations research, mathematical programming > 90Bxx Operations research and management science > 90B06 Transportation, logistics

    		•
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Schrader
    Related URLs:
    Deposit Information:
    ZAIK Number: zaik2007-530
    Depositing User: Dirk Räbiger
    Date Deposited: 15 Mar 2010 00:00
    Last Modified: 09 Jan 2012 15:38
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/530