Tour Planning for Sightseeing with Time-Dependent Satisfactions of Activities and Traveling Times

Takashi Hasuike, Hideki Katagiri, Hiroe Tsubaki, Hiroshi Tsuda

Department of Mathematical Sciences, Faculty of Science and Engineering, Doshisha University, Kyoto, Japan.
Graduate School of Engineering, Hiroshima Univeristy, Hiroshima, Japan.
Graduate School of Information Science and Technology, Osaka Univeristy, Osaka, Japan.
Multidimensional Data Analysis Group, Department of Data Science, The Institute of Statistical Science, Tokyo, Japan.

DOI: 10.4236/ajor.2013.33034                

Abstract

This paper proposes a new personal tour planning problem with time-dependent satisfactions, traveling and activity duration times for sightseeing. It is difficult to represent the time-dependent model using general static network models, and hence, Time-Expanded Network (TEN) is introduced. The TEN contains a copy to the set of nodes in the underlying static network for each discrete time step, and it turns the problem of determining an optimal flow over time into a classical static network flow problem. Using the proposed TEN-based model, it is possible not only to construct various variations with time of costs and satisfactions flexibly in a single network, but also to select optimal departure places and accommodations according to the tour route with tourist’s favorite places and to obtain the time scheduling of tour route, simultaneously. The proposed model is formulated as a 0 - 1 integer programming problem which can be applied by existing useful combinatorial optimization and soft computing algorithms. It’s also equivalently transformed into several existing tour planning problems using some natural assumptions. Furthermore, comparing the proposed model with some previous models using a numerical example with time-dependent parameters, both the similarity of these models in the static network and the advantage of the proposed TEN-based model are obtained.

Keywords

Tour Planning Problem; Time-Dependent Parameters; Time-Expanded Network; Mathematical Modeling

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	C. Zhu, J. Q. Hu, F. Wang, Y. Xu and R. Cao, “On the Tour Planning Problem,” Annals of Operations Research, Vol. 192, No. 1, 2012, pp. 67-86. doi:10.1007/s10479-010-0763-5
[2]	R. A. Abbaspour and F. Samadzadegan, “Time-Dependent Personal Tour Planning and Scheduling in Metropolises,” Expert Systems with Applications, Vol. 38, No. 10, 2011, pp. 12439-12452. doi:10.1016/j.eswa.2011.04.025
[3]	W. Souffriau, P. Vansteenwegen, J. Vertommen, G. V. Berghe and D. V. Oudheusden, “A Personalized Tourist Trip Design Algorithm for Mobile Tourist Guides,” Applied Artificial Intelligence, Vol. 22, No. 10, 2008, pp. 964-985. doi:10.1080/08839510802379626
[4]	K. G. Zografos and K. N. Androutsopoulos, “Algorithms for Itinerary Planning in Multimodal Transportation Networks,” IEEE Transactions on Intelligent Transportation System, Vol. 9, No. 1, 2008, pp. 175-184. doi:10.1109/TITS.2008.915650
[5]	W. Bohte and K. Maat, “Deriving and Validating Trip Purposes and Travel Modes for Multi-Day GPS-Based Travel Surveys: A Large-Scale Application in the Netherlands,” Transportation Research Part C: Emerging Technologies, Vol. 17, No. 3, 2009, pp. 285-297. doi:10.1016/j.trc.2008.11.004
[6]	D. Ettema, T. Garling, L. E. Olsson and M. Friman, “Outof-Home Activities, Daily Travel and Subjective WellBeing,” Transportation Research Part A: Policy and Practice, Vol. 44, No. 9, 2010, pp. 723-732. doi:10.1016/j.tra.2010.07.005
[7]	T. Y. Hu, C. C. Tong, T. Y. Liao and W. M. Ho, “Simulation-Assignment-Based Travel Time Prediction Model for Traffic Corridors,” IEEE Transactions on Intelligent Transportation Systems, Vol. 13, No. 3, 2012, pp. 12771286. doi:10.1109/TITS.2012.2190061
[8]	A. Khosravi, E. Mazloumi, S. Nahavandi, D. Creighton and J. W. C. Van Lint, “Prediction Intervals to Account for Uncertainties in Travel Time Prediction,” IEEE Transactions on Intelligent Transportation Systems, Vol. 12, No. 2, 2011, pp. 537-547. doi:10.1109/TITS.2011.2106209
[9]	X. Cai, D. Sha and C. K. Wong, “Time-Varying Universal Maximum Flow Problems,” Mathematical and Computer Modelling, Vol. 33, No. 4-5, 2001, pp. 407-430. doi:10.1016/S0895-7177(00)00252-1
[10]	M. Florian, G. Bushell, J. Ferland, G. Guerin and L. Nastansky, “Engine Scheduling Problem in a Railway Network,” Canadian Journal of Operational Research and Information Processing, Vol. 14, No. 2, 1976, pp. 121138.
[11]	D. J. Zawack and L. T. Gerald, “Dynamic Space-Time Network Flow Model for City Traffic Congestion,” Transportation Science, Vol. 21, No. 3, 1987, pp. 153-162. doi:10.1287/trsc.21.3.153
[12]	F. G. Engineer, G. L. Nemhauser and M. W. P. Savelsgergh, “Dynamic Programming-Based Column Generation on Time-Expanded Network: Application to the Diala-Flight Problem,” INFORMS Journal on Computing, Vol. 23, No. 1, 2011, pp. 105-119. doi:10.1287/ijoc.1100.0384
[13]	Y. Guo, T. Mellouli, L. Suhl and M. P. Thiel, “A Partially Integrated Airline Crew Scheduling Approach with TimeDependent Crew Capacities and Multiple Home Bases,” European Journal of Operational Research, Vol. 171, No. 3, 2006, pp. 1169-1181. doi:10.1016/j.ejor.2005.01.024
[14]	C. Hane, C. Barnhart, E. L. Johnson, R. E. Marsten, G. L. Nemhauser and G. Sigismondi, “The Fleet Assignment Problem: Solving a Large Integer Program,” Mathematical Programming, Vol. 70, No. 2, 1995, pp. 211-232. doi:10.1007/BF01585938
[15]	N. Kliewer, T. Mellouli and L. Suhl, “A Time-Space Network Based Exact Optimization Model for Multi-Depot Bus Scheduling,” European Journal of Operational Research, Vol. 175, No. 3, 2006, pp. 1616-1627. doi:10.1016/j.ejor.2005.02.030
[16]	N. Shah, S. Kumar, F. Bastani and I. L. Yen, “Optimization Models for Assessing the Peak Capacity Utilization of Intelligent Transportation Systems,” European Journal of Operational Research, Vol. 216, No. 1, 2012, pp. 239251. doi:10.1016/j.ejor.2011.07.032
[17]	S. Yan and C. Y. Chen, “An Optimization Model and a Solution Algorithm for the Many-to-Many Car Pooling Problem,” Annals of Operations Research, Vol. 191, No. 1, 2011, pp. 37-71. doi:10.1007/s10479-011-0948-6
[18]	J. C. Chu, S. Yan and K. L. Chen, “Optimization of Earth Recycling and Dump Truck Dispatching,” Computers & Industrial Engineering, Vol. 62, No. 1, 2012, pp. 108-118. doi:10.1016/j.cie.2011.08.022
[19]	J. J. Jarvis and H. D. Ratliff, “Some Equivalent Objectives for Dynamic Network Flow Problems,” Management Science, Vol. 28, No. 1, 1982, pp. 106-109. doi:10.1287/mnsc.28.1.106
[20]	M. R. Silver and O. L. de Weck, “Time-Expanded Decision Networks: A Framework for Designing Evolvable Complex Systems,” Systems Engineering, Vol. 10, No. 2, 2007, pp. 167-186. doi:10.1002/sys.20069
[21]	M. Fischetti, J. S. Gonzalez and P. Toth, “Solving the Orienteering Problem through Branch-and-Cut,” INFORMS Journal on Computing, Vol. 10, No. 2, 1998, pp. 133-148. doi:10.1287/ijoc.10.2.133
[22]	I. M. Chao, B. L. Golden and E. A. Wasil, “A Fast and Effective Heuristic for the Orienteering Problem,” European Journal of Operational Research, Vol. 88, No. 3, 1996, pp. 475-489. doi:10.1016/0377-2217(95)00035-6
[23]	J. L. Kennington and C. D. Nicholson, “The Uncapacitated Time-Space Fixed-Charge Network Flow Problem; an Empirical Investigation of Procedures for Arc Capacity Assignment,” INFORMS Journal of Computing, Vol. 22, No. 2, 2009, pp. 326-337. doi:10.1287/ijoc.1090.0354
[24]	Q. Wang, X. Sun, B. L. Golden and J. Jia, “Using Artificial Neural Networks to Solve the Orienteering Problem,” Annals of Operations Research, Vol. 61, No. 1, 1995, pp. 111-120. doi:10.1007/BF02098284
[25]	M. Gendreau, G. Laporte and F. Semet, “A Tabu Search Heuristic for the Undirected Selective Traveling Salesman Problem,” European Journal of Operational Research, Vol. 106, No. 2-3, 1998, pp. 539-545. doi:10.1016/S0377-2217(97)00289-0
[26]	H. Tang and E. Miller-Hooks, “A Tabu Search Heuristic for the Team Orienteering Problem,” Computers & Operations Research, Vol. 32, No. 6, 2005, pp. 1379-1407. doi:10.1016/j.cor.2003.11.008
[27]	L. Ke, C. Archetti and Z. Feng, “Ants Can Solve the Team Orienteering Problem,” Computers & Industrial Engineering, Vol. 54, No. 3, 2008, pp. 648-665. doi:10.1016/j.cie.2007.10.001
[28]	P. Fattahi, M. S. Manesh and A. Roshani, “A New Solution Seed for Job Shop Scheduling Problem,” Applied Mechanics and Materials, Vol. 110-116, 2012, pp. 38993905.
[29]	M. Seker and N. Noyan, “Stochastic Optimization Models for the Airport Gate Assignment problem,” Transportation Research Part E: Logistics and Transportation Review, Vol. 48, No. 2, 2012, pp. 438-459. doi:10.1016/j.tre.2011.10.008
[30]	J. Elias, F. Martignon and G. Carello, “Very Large-Scale Neighborhood Search Algorithm for the Design of Service Overlay Networks,” Telecommunication Systems, Vol. 49, No. 4, 2012, pp. 391-408. doi:10.1007/s11235-010-9381-4
[31]	M. Fischetti, J. J. Salazar-González and P. Toth, “The Generalized Traveling Salesman and Orienteering Problems,” In: G. Gutin and A. P. Punnen, Eds., The Traveling Salesman Problem and Its Variations, Kluwer Academic Publisher, Dordrecht, 2002, pp. 609-662.