  


Variants in Modeling Time Aspects for the Multiple Traveling Salesmen Problem with Moving Targets
Anke Stieber(stieberahsuhh.de) Abstract: The multiple traveling salesmen problem with moving targets (MTSPMT) 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 timediscrete formulation embedded in a timeexpanded network. The second model uses bigM constraints to arrange the time in a continuous way, which leads to a quadratic programming problem. The other two models comprise a timerelaxation approach where timefeasibility 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 bigM constraints. The solution procedure to solve the timerelaxed 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 timerelaxed variant with continuous times is the most promising one with respect to computational running times. Keywords: Dynamic traveling salesmen problem, Moving targets, Timerelaxation, Integer linear programming, Secondorder 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  