Issuu

Optimizing Tourist Landmark Visits in Bangalore Using a Special Case of TSP

Jay Jeswani1

1National Public School Indiranagar, Bengaluru, Karnataka 560008

Abstract - This paper presents a novel approach to optimizing tourist landmark visit sequences in Bangalore using a Time-Dependent Travelling Salesman Problem (TDTSP) with Soft Time Windows formulation. The research addresses the challenge of creating efficient tourist itineraries that account for temporal variations in crowd levels, dynamic travel times due to traffic variability, and flexible visit timing preferences. Our model incorporates temporal cost functions based on crowd density patterns, dynamic edge weights reflecting traffic conditions, and soft time windowconstraints that allow schedule flexibility with penalty costs. The methodology is applied to four major Bangalore landmarks: Brigade Road (KLING), Chinnaswamy Stadium, Bangalore Palace, and Lalbagh Garden. Analysis of temporal patterns reveals significant day-of-week variations, with Sunday showing peak crowding levels (24-55% busy) and Monday consistently showing minimum crowding (12-18% busy) across all landmarks. Travel time analysis demonstrates variability factors of 2.3-2.7x between minimum and maximum durations, emphasizing the need for time-dependent optimization. The proposed algorithm considers these temporal variations to generate optimal tourist routes that adapt to changing conditions. This work contributes to the growing field of smart tourism systems and provides a practical framework for tourism optimization in metropolitanareas.

Key Words: Travelling Salesman Problem, Tourism Optimization, Time-Dependent Routing, Soft Time Windows,SmartTourism,Bangalore

1.INTRODUCTION

The tourism industry has experienced unprecedented growth in recent years, with urban destinations like Bangalore attracting millions of visitors annually. As the Silicon Valley of India, Bangalore combines rich historical heritage with modern technological infrastructure, creating unique opportunities for smart tourism applications. However, tourist route planning remains a complex optimization challenge, particularly when considering temporal variations in crowd levels, traffic conditions,andvisitorpreferences.

Traditional tourist route planning approaches often rely on static models that fail to account for the dynamic

nature of urban environments. The Travelling Salesman Problem(TSP)hasbeenextensivelystudiedinoperations research,butitsapplicationtotourismrequiressignificant modifications to handle temporal constraints and realworld complexities. The emergence of smart city initiatives and IoT infrastructure provides new opportunities to develop sophisticated optimization modelsthatcanadapttochangingconditions.

This research addresses the gap between classical TSP formulations and practical tourism optimization requirements by proposing a Time-Dependent TSP with Soft Time Windows (TD-TSP-STW) model. The approach incorporates temporal cost functions based on crowd density patterns, dynamic edge weights reflecting traffic variability, and flexible time window constraints that balanceefficiencywithtouristpreferences.

1.1 Research Motivation

Urban tourism faces several critical challenges that traditional optimization approaches cannot adequately address. Temporal variations in crowd levels significantly impact tourist experience, with popular landmarks experiencing dramatic changes in visitor density throughoutthedayandweek.Dynamictrafficconditionsin metropolitan areas like Bangalore create substantial variations in travel times between attractions, making static routing algorithms ineffective. Tourist preferences for flexible scheduling require optimization models that can accommodate soft constraints rather than rigid time windows.

The COVID-19 pandemic has further emphasized the importance of crowd-aware tourism planning, making temporal optimization not just a convenience but a necessityforsafeandenjoyabletouristexperiences.Smart tourism systems that can dynamically adapt to changing conditions represent the future of urban tourism management.

1.2 Literature Review

The application of TSP variants to tourism optimization hasgainedsignificantattentioninrecentyears.Gavalaset al. [6] provided a comprehensive survey of algorithmic approaches for tourist trip design problems, highlighting

International Research Journal of Engineering and Technology (IRJET) e-ISSN: 2395-0056

Volume: 12 Issue: 08 | Aug 2025 www.irjet.net p-ISSN: 2395-0072

the need for multi-objective formulations that consider time constraints, budget limitations, and tourist preferences. Vansteenwegen et al. [18] discussed the orienteering problem as a framework for tourism route optimization, emphasizing the importance of profit maximizationwithintimeconstraints.

Recent advances in time-dependent TSP formulations have opened new possibilities for tourism applications. Arigliano et al. [1] presented exact and anytime approaches for solving the time-dependent traveling salesman problem with time windows, demonstrating the computational feasibility of such models for practical applications. Lera-Romero et al. [11] developed dynamic programmingmethodsfortime-dependentTSP,providing theoreticalfoundationsforefficientsolutionalgorithms.

The integration of crowd-aware systems with routing optimization has emerged as a critical research area. Wu et al. [19] developed temporal aware networks for crowd counting, while Chen et al. [3] introduced multifaceted datasets for context-aware spatio-temporal crowd mobility prediction. These advances provide the technological foundation for implementing crowd-aware tourismoptimizationsystems.

Multi-objective optimization approaches have shown promise in tourism contexts. Arbolino et al. [2] applied multi-objective optimization techniques to tourism sustainability planning, while Shojatalab et al. [16] developed new multi-objective models for tourism systems with fuzzy data. These works demonstrate the importance of balancing multiple competing objectives in tourismoptimization

1.3 Research Contributions

This paper makes several novel contributions to the field oftourismoptimization:

1. Novel TD-TSP-STW Formulation: Development of a time-dependent TSP model with soft time windows specifically designed for tourism applications, incorporating temporal cost functionsanddynamicedgeweights.

2. Bangalore Tourism Context: First comprehensive application of advanced TSP formulations to Bangalore tourism optimization, creating a framework applicable to other metropolitan areas.

3. Crowd-Aware Cost Modeling: Integration of temporal cost functions based on crowd density patterns and day-of-week popularity variations, with empirical analysis showing up to 37 percentagepointvariationsbetweenpeakandoffpeakdays.

4. Practical Implementation Framework: Development of mathematical formulations and

algorithmic approaches suitable for real-time tourismapplications.

5. Temporal Pattern Analysis: Comprehensive analysis of crowd patterns and travel time variabilityinBangalore, revealingconsistent dayof-week effects and significant traffic-induced variations.

2. PROBLEM STATEMENT

2.1 Tourism Route Optimization Challenge

The tourism route optimization problem in Bangalore involves determining the optimal sequence of visits to multiple landmarks while considering temporal constraints, varying crowd levels, and dynamic travel times.Thechallengeiscomplicatedbyseveralfactors:

1. Temporal crowd variations that affect tourist experienceandsatisfaction

2. Dynamic traffic conditions that create timedependenttravelcosts

3. Flexible scheduling preferences that require soft timewindowconstraints

4. Multi-objective optimization balancing efficiency, cost,andtouristsatisfaction

2.2 Mathematical Problem Formulation

LetG=(V,E)beacompletegraphrepresentingthetourism network, where V = {0, 1, 2, ..., n} represents the set of locations (with 0 being the starting/ending point) and E representsthesetofedgesconnectingalllocationpairs.

DecisionVariables

xij(t): Binary variable equal to 1 if tourist travels from locationitolocationjstartingattimet,0otherwise

τi:Arrivaltimeatlocation i

ei -:Earlyarrivalpenaltyatlocation i

ei+:Latearrivalpenaltyatlocation i Parameters

cij(t): Time-dependent travel cost from location i to j whendepartingattime t

si:Servicetime(visitduration)atlocation i

[ai,bi]:Preferredtimewindowforvisitinglocation i

αi -,αi+:Penaltycoefficientsforearlyandlatearrivalsat location i

pi(t):Crowddensityfunctionatlocation i attime t

International Research Journal of Engineering and Technology (IRJET) e-ISSN: 2395-0056

ObjectiveFunction

The objective function minimizes total travel costs and timewindowviolationpenalties:

( ) ( ) ∑( )

Theconstraintsareasfollows:

FlowConservation

( )

TimeWindowConstraints(Soft)

TemporalConsistency ( ) ( )

SubtourElimination

( ) | | * + | |

2.3

Time-Dependent Cost Functions

Thetime-dependenttravelcostfunctionincorporatesboth traffic-basedtraveltimeandcrowd-basedwaitingtime:

( ) ( ) ( ( ))

Where,

 tij(t) = Traffic-dependent travel time from i to j at timet

 pj(t)=Crowdpenaltyatdestinationjattimet

 dij =Basedistancebetweenlocationsiandj

 w1,w2,w3:Weightingcoefficients

3. METHODOLOGY

3.1 Algorithm Framework

The proposed solution methodology combines exact optimization techniques with heuristic approaches to handle the computational complexity of the TD-TSP-STW model. The algorithm framework consists of three main components:



Preprocessing Module: Data preparation and temporalcostfunctioncomputation

 Optimization Engine: Core TD-TSP-STW solver withbranch-and-boundapproach

Post-processing Module: Solution validation and performanceevaluation

3.2 Temporal Cost Function Computation

Thetemporal costfunctionsarecomputedusinghistorical crowddataandtrafficpatterns

CrowdDensityModeling

Crowd density at location i at time t is modeled using a combination of periodic functions and day-of-week variations:

i(t)=βi ·[1+αi ·sin(2πt/T)+γi ·dow(t)] where,

βi =Basecrowdlevelatlocationi

αi =Amplitudeofperiodiccrowdvariation

T=Periodofcrowdcycle(typically24hours)

γi =Day-of-weekadjustmentfactor

dow(t)=Day-of-weekfunction

Traffic-DependentTravelTime

Traffic-dependent travel times are modeled using time-ofdaytrafficpatterns:

tij(t)=dij ·[1+δij ·traffic_factor(t)]

where traffic_factor(t) represents the normalized traffic congestionattimet.

3.3 Optimization Algorithm

Figure 1-3 show the complete algorithm flow including initialization,optimizationloop,andterminationcriteria.

Theoptimizationalgorithmfollowsamodifiedbranch-andboundapproachwiththefollowingkeyfeatures:

 Branching Strategy: Time-dependent branching basedondeparturetimes

 Bounding Mechanism: Lower bounds computed usingrelaxedtimewindows

 Pruning Rules: Early termination of branches basedoncostthresholds

 HeuristicInitialization:Nearestneighborheuristic withtimewindows

International Research Journal of Engineering and Technology (IRJET) e-ISSN: 2395-0056

Volume: 12 Issue: 08 | Aug 2025 www.irjet.net p-ISSN: 2395-0072

3.4 Implementation Details

DataStructures

 Time-indexedadjacencymatricesforstoringtimedependentcosts

 Priority queues for managing search nodes in branch-and-bound

 Hash tables for memoization of subproblem solutions

ComputationalComplexity

The worst-case time complexity of the algorithm is O(n²2^n·T),wherenisthenumberoflocationsandTisthe number of time discretization points. However, practical performance is significantly better due to pruning and boundingstrategies.

4. BENGALURU CASE STUDY

4.1 Study Area and Data Collection

Thecasestudyfocusesonfourmajortouristlandmarksin Bangalore:

 Brigade Road (KLING): Major shopping and entertainmentdistrict

Fig -2:AlgorithmtoComputeVisitCost Fig -3:AlgorithmtoSuggestItinerary

 Chinnaswamy Stadium (C.std): Premier cricket stadiumandsportsvenue

 Bangalore Palace: Historical monument and architecturallandmark

 Lalbagh Garden: Botanical Garden and recreationalarea

LandmarkCharacteristics

Table -1: LandmarkVisitScheduleandDistancefromHub

Landmark Suggested Visit Time Distance from Hub (approx.)

KLING 12:00PM

Chinnaswamy Stadium(C.std) 1:00PM 0.8km

BangalorePalace 2:00PM 3.9km

LalbaghGarden 3:00PM 5.1km

TravelTimeData

Distanceandtraveltimedatawerecollectedusing:

 GoogleMapsAPIfortrafficinformation

 HistoricaltrafficpatternsfromGoogleMapsAPI

 OperatinghoursfromGoogleMapsAPI

International Research Journal of Engineering and Technology (IRJET) e-ISSN: 2395-0056

 Distanceandhourlydayofweekbasedtraveltime datafromGoogleMapsAPI

Table -2: EstimatedTravelTimeBetweenSelected Landmarks

From To

–

Palace Chinnaswamy Stadium 3.833–10.25+

Note:"+"denotesvariabilityduetotraffic.

4.2 Temporal Patterns Analysis

CrowdDensityPatterns

Table -3: LandmarkPopularity(%Busy)byDay

Landmark Sat Sun Mon Tue Wed Thu Fri

KLING 19 24 12 13 14 15 15

CStd 29 39 16 19 22 21 24

Theanalysisrevealsdistincttemporalpatterns:

 Weekday vs Weekend variations: Significantly different crowd patterns with Sunday showing peakcrowding(24-55%)acrossalllandmarks

 Time-of-day effects: Suggested visit times range from12:00PMto3:00PMforoptimalsequencing

 Monday minimum crowding: Consistently lowest crowd levels on Mondays (12-18%) across all landmarks

TrafficVariability

Trafficanalysisshows:

 Peakcongestionperiods:8-10AMand6-8PM

 Route-dependentvariations:Differentpatternsfor differentlandmarkpairs

 Travel time ranges: Significant variability with factors of 2.3-2.7x between minimum and maximumtraveltimes

4.3 Experimental Setup

ParameterSettings

 Timediscretization:30-minuteintervals

 Planninghorizon:8hours(typicaltourismday)

 Penalty weights: α^- = 0.5, α^+ = 1.0 (late penaltieshigher)

 Costweights:w₁=0.6,w₂=0.3,w₃=0.1

BenchmarkComparisons

TheproposedTD-TSP-STWalgorithmiscomparedagainst:

 Nearest Neighbor Heuristic: Simple greedy approach

 RandomTour:Baselinecomparison

5. RESULTS AND DISCUSSION

5.1 Temporal Pattern Analysis

Theexperimentalresultsdemonstratesignificanttemporal variationsinlandmarkcrowdingpatterns:

Table -4: SummaryStatisticsofCrowdDensityVariations

Landmark Average Busy % Peak Day (%) Off-Peak

Day-of-WeekPatterns

Thedatarevealsconsistentpatternsacrossalllandmarks:

 Sunday peak crowding: All landmarks experience maximumcrowdingonSundays(24-55%)

 Monday minimum crowding: Consistently lowest visitordensityonMondays(12-18%)

 Weekend effect: Saturday and Sunday show 2-3x highercrowdlevelscomparedtoweekdays

 Mid-week stability: Tuesday through Thursday showrelativelystable,moderatecrowdlevels

TravelTimeVariability

Thetraveltimedatashowssignificantvariability:

 Phoenix to Lalbagh: 30.8 to 71 minutes (2.3x variation)

 Lalbagh to Palace: 12 to 31.66 minutes (2.6x variation)

International Research Journal of Engineering and Technology (IRJET) e-ISSN: 2395-0056

Volume: 12 Issue: 08 | Aug 2025 www.irjet.net p-ISSN: 2395-0072

 Palace to C.std: 3.833 to 10.25+ minutes (2.7x variation)

This variability emphasizes the importance of timedependent optimization models that can adapt to traffic conditions.

5.2 Sensitivity Analysis

Distance-BasedClustering

Analysisofthelandmarksrevealsnatural clusteringbased ondistancefromhub:

 Near cluster: KLING (hub), C.std/Chinnaswamy Stadium(0.8km)

 Mid-range cluster: Palace (3.9 km), Lalbagh (5.1 km)

This clustering suggests potential for zone-based optimizationstrategieswheretouristscanminimizetravel byvisitingnearbylandmarkssequentially.

TemporalConstraintImpact

Table -5: OptimalVisitStrategiesbyDayType

Day Type Recommended Strategy Rationale

Weekday (Mon-Thu) Standardsequence:KLING →C.std→Palace→ Lalbagh

Lowcrowdlevels allowflexibility

Friday Modifiedsequencewith earlierstarts Moderatecrowd buildupinafternoon

Weekend Reversesequenceorearly morningstarts Avoidpeakcrowding atpopularsites

The soft time window formulation provides several advantages:

 Increased feasibility compared to hard time windows

 Better tourist satisfaction through flexible scheduling

 Reduced computational complexity in constraint handling

5.3

Practical Implications

The analysis provides actionable insights for tourism planning:

 Monday Optimization: With consistently low crowd levels (12-18%), Mondays offer the best experienceforcomprehensivetours

 WeekendStrategies:Sundaypeaks(24-55%busy) suggest either early morning starts or selective landmarkvisits

 Time Buffer Requirements: Given travel time variations of 2.3-2.7x, tourists should allocate generousbuffersbetweenlandmarks

 Distance-Aware Planning: The 0.8-5.1 km range between landmarks makes walking feasible for some connections but requires transport for others

6. CONCLUSION

This research presents a novel approach to tourism route optimization using Time-Dependent TSP with Soft Time Windows, successfully addressing the complex challenges of urban tourism planning. The proposed methodology demonstrates the importance of incorporating temporal variations in crowd levels and traffic conditions for effectivetouristitineraryplanning.

6.1 Key Contributions

Theresearchmakesseveralimportantcontributionstothe field:

- Theoretical Framework: Development of a comprehensive TD-TSP-STW formulation that captures real-world tourism optimization complexity with temporal cost functions and dynamicedgeweights

- Empirical Analysis: Comprehensive analysis of temporal patternsinBangaloretourism,revealing consistent day-of-week effects and significant traveltimevariability

- PracticalInsights:Identificationofoptimalvisiting strategies based on crowd patterns, with Monday showing consistently lowest crowding (12-18%) andSundaypeaksreaching24-55%

- Optimization Framework: Mathematical formulation suitable for adaptation to different metropolitantourismcontexts

6.2 Implications for Smart Tourism

The findings have significant implications for smart tourismsystemdevelopment:

 Temporal awareness is crucial for tourist satisfaction,withcrowdlevelsvaryingbyupto37 percentagepointsbetweenpeakandoff-peakdays

 Dynamic optimization must account for travel timevariationsof2.3-2.7xduetotrafficconditions

 Day-specific strategies can significantly improve tourist experiences by avoiding peak crowding periods

International Research Journal of Engineering and Technology (IRJET) e-ISSN: 2395-0056

Volume: 12 Issue: 08 | Aug 2025 www.irjet.net p-ISSN: 2395-0072

 Distance-based clustering of landmarks enables moreefficientrouteplanning

6.3 Limitations and Constraints

Severallimitationsshouldbeacknowledged:

 Data granularity is limited to daily averages withoutintra-daytemporalresolution

 Static landmark selection does not account for personalpreferencesorinterests

 Traffic prediction relies on historical patterns ratherthanreal-timedata

 Weather impacts and special events are not incorporatedinthecurrentmodel

7. FUTURE WORK

7.1 Algorithmic Enhancements

Futureresearchdirectionsinclude:

 Machine Learning Integration: Incorporating neural networks for better crowd prediction and touristpreferencemodeling

 Multi-objectiveOptimization:Extendingthemodel to handle multiple competing objectives simultaneously

 Robust Optimization: Developing approaches that handle uncertainty in travel times and crowd levels

 Distributed Computing: Implementing parallel algorithmsforlarge-scaleapplications

7.2 System Integration

 IoTIntegration:Connectingwithsmartcitysensor networksforreal-timedata

 Mobile Applications: Developing user-friendly interfacesfortouristinteraction

 Multi-modal Transportation: Incorporating public transitandride-sharingoptions

 Sustainability Metrics: Adding environmental impactconsiderations

7.3 Broader Applications

Themethodologycanbeextendedto:

 Multi-city tourism optimization across metropolitanregions

 Grouptourismwithmultipletouristpreferences

 Seasonal tourism planning with long-term scheduling

 Business travel optimization with different constraintstructures

7.4 Validation and Testing

Futureworkshouldinclude:

 Larger-scale field studies with diverse tourist populations

 Cross-cultural validation in different urban environments

 Long-term performance monitoring to assess systemeffectiveness

 Economic impact analysis of optimized tourism systems

REFERENCES

[1] Arigliano, A., Ghiani, G., Grieco, A., Guerriero, E., & Plana, I. (2023). Exact and anytime approach for solving the time dependent traveling salesman problem with time windows. European Journal of OperationalResearch,309(3),1147-1160.

[2] Arbolino, R., Boffardi, R., & Ioppolo, G. (2021). Multiobjectiveoptimizationtechnique:Anovelapproachin tourism sustainability planning. Journal of EnvironmentalManagement,285,112016.

[3] Chen, L., Zhang, C., Wilson, C., Gao, J., & Zhao, D. (2025). STContext: A multifaceted dataset for developing context-aware spatio-temporal crowd mobility prediction models. arXiv preprint arXiv:2501.03583.

[4] Christofides, N. (1976). Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report 388, Graduate School of Industrial Administration,Carnegie-MellonUniversity.

[5] Dantzig, G. B., Fulkerson, R., & Johnson, S. (1954). Solution of a large-scale traveling-salesman problem. OperationsResearch,2(4),393-410.

[6] Gavalas, D., Konstantopoulos, C., Mastakas, K., & Pantziou, G. (2014). A survey on algorithmic approaches for solving tourist trip design problems. JournalofHeuristics,20(3),291-328.

International Research Journal of Engineering and Technology (IRJET) e-ISSN: 2395-0056

[7] Hameed, I. A., & Boctor, F. F. (2019). Multi-objective solution of traveling salesman problem with time. StudiesinComputationalIntelligence,845,131-142.

[8] Held,M.,&Karp,R.M.(1970).Thetraveling-salesman problem and minimum spanning trees. Operations Research,18(6),1138-1162.

[9] Hillier,F.S.,&Lieberman,G.J.(2014).Introductionto operationsresearch(10thed.).McGraw-Hill.

[10] Karnataka State Tourism Development Corporation. (2024). Karnataka tourism development report. GovernmentofKarnataka.

[11] Lera-Romero, G., Sartori, J., & Urrutia, S. (2022). Dynamic programming for the time-dependent traveling salesman problem. Optimization Online, 7558.

[12] Li, J., Ma, Q., Cui, R., & Tang, H. (2024). A survey on deep learning-based algorithms for the traveling salesman problem. Frontiers of Computer Science, 18(4),184701.

[13] Lin, S., & Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling-salesman problem.OperationsResearch,21(2),498-516.

[14] Nemhauser, G. L., & Wolsey, L. A. (2014). Integer and combinatorialoptimization.JohnWiley&Sons.

[15] Nocedal, J., & Wright, S. J. (2006). Numerical optimization(2nded.).Springer.

[16] Shojatalab,G.,Nasseri,S.H.,&Mahdavi,I.(2023).New multi-objective optimization model for tourism systemswithfuzzydataandnewapproachdeveloped epsilon constraint method. OPSEARCH, 60(3), 10181037.

[17] Sui, J., Ding, S., Xia, B., Liu, R., & Bu, D. (2024). NeuralGLS: Learning to guide local search with graph convolutional network for the traveling salesman problem. Neural Computing and Applications, 36(17), 9687-9706.

[18] Vansteenwegen, P., Souffriau, W., & Van Oudheusden, D. (2011). The orienteering problem: A survey. European Journal of Operational Research, 209(1), 110.

[19] Wu,X.,Liang,Y.,Huang,J.,Zhang,X.,Li,Y.,&Wang,X. (2020). Fast video crowd counting with a temporal aware network. IEEE Transactions on Image Processing,29,5450-5463.

[20] Zheng, J.,Liang,Y.,& Wang, D.(2022).Particleswarm algorithm and its application in tourism route design andoptimization.PMCArticlePMC8983212.