Optimization Online


Variants in Modeling Time Aspects for the Multiple Traveling Salesmen Problem with Moving Targets

Anke Stieber(stiebera***at***hsu-hh.de)
Armin Fügenschuh(fuegenschuh***at***hsu-hh.de)

Abstract: The multiple traveling salesmen problem with moving targets (MT-SPMT) is a generalization of the classical traveling salesmen problem (TSP), where the targets (cities or objects) are moving over time. Additionally, for each target a visibility time window is given. The task is to find routes for several salesmen so that each target is reached exactly once within its visibility time window and the sum of all traveled distances of all salesmen is minimal. Applications of the described problem class can be found, e.g., in supply logistics and in the defense sector. Such instances can be very large in the number of variables and therefore time consuming to solve numerically. In handling the time aspect in different ways we present four distinct modeling approaches for the MTSPMT. First we present a time-discrete formulation embedded in a time-expanded network. The second model uses big-M constraints to arrange the time in a continuous way, which leads to a quadratic programming problem. The other two models comprise a time-relaxation approach where time-feasibility is ensured by solving a number of subprograms. For modeling of the subprograms to reintegrate time, again two possibilities are available: time discretization and applying big-M constraints. The solution procedure to solve the time-relaxed variants is proposed and computational results for randomly generated test instances to compare all different modeling approaches are presented. For problem instances with a fine discretization the time-relaxed variant with continuous times is the most promising one with respect to computational running times.

Keywords: Dynamic traveling salesmen problem, Moving targets, Time-relaxation, Integer linear programming, Second-order cone programming

Category 1: Applications -- OR and Management Sciences (Scheduling )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Category 3: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Angewandte Mathematik und Optimierung Schriftenreihe AMOS#46 (2016), Helmut Schmidt University / University of the Federal Armed Forces Hamburg, Germany

Download: [PDF]

Entry Submitted: 06/29/2016
Entry Accepted: 06/29/2016
Entry Last Modified: 06/29/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society