Multiperiod Multi Traveling Salesmen Problem Considering Time Window Constraints with an Application to a Real World Case

Haluk Yapicioglu ()
Additional contact information
Haluk Yapicioglu: Anadolu University

Networks and Spatial Economics, 2018, vol. 18, issue 4, No 1, 773-801

Abstract: Abstract This study arises from a real world problem. In the problem, a number of university representatives are required to visit a number of exam locations departing from a central location and returning back to the same location. Each location may be visited in one of four different periods; however these visits must be done in pre-specified time windows. Time windows may be different from location to location and across periods for the same location. The problem is modeled as a multi-period multi traveling salesmen problem with time window constraints. Earlier attempts to solve the resulting models using mixed integer linear programming approach proved to be ineffective. Hence two stochastic heuristic search techniques, based on simulated annealing (SA) and robust tabu search (RTS), are used. For this, a new solution representation and associated decoding and encoding mechanisms are developed. Proposed approaches are tested on various problem instances, and performance of the solution approaches are discussed. Finally, a real case is considered for which a method for obtaining travel distance and travel time matrices from Google Distance Matrix API is developed. The results obtained from the real case is also discussed and future research directions are provided.

Keywords: Multi Traveling Salesmen Problem; Time Windows; Simulated Annealing; Robust Tabu Search (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s11067-017-9367-9 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:kap:netspa:v:18:y:2018:i:4:d:10.1007_s11067-017-9367-9

Ordering information: This journal article can be ordered from
http://www.springer. ... ce/journal/11067/PS2

DOI: 10.1007/s11067-017-9367-9

Access Statistics for this article

Networks and Spatial Economics is currently edited by Terry L. Friesz

More articles in Networks and Spatial Economics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().