情報処理学会研究報告 IPSJ SIG Technical Report Vol.2011-AL-133 No /1/ NP % 13 Stamina-Aware Sightseeing Tour Scheduling Method Bing Wu

Size: px

Start display at page:

Download "情報処理学会研究報告 IPSJ SIG Technical Report Vol.2011-AL-133 No /1/ NP % 13 Stamina-Aware Sightseeing Tour Scheduling Method Bing Wu"

しょうぶのあき
4 years ago
Views:

1 NP % 13 Stamina-Aware Sightseeing Tour Scheduling Method Bing Wu, 1 Weihua Sun, 1 Yoshihiro Murata, 2 Keiichi Yasumoto 1 and Minoru Ito 1 Tour schedules are wanted to include multiple sightseeing spots taking into account the user s preference, but the stamina of tourists may be insufficient when doing sightseeing. In this paper, we propose the sightseeing scheduling problem to maximize satisfaction. In this problem, break times are allocated in schedule to hold constraint of stamina. This problem is NP-hard, then it is difficult to solve it in practical time. In order to calculate semi-optimal solution in practical time, we propose the method to plan schedule visiting multiple sightseeing spots with no break times and to allocate the break times among schedule using local search technique. To evaluate the proposed method, we compare our method with the Brute force method through the simulation experiment for the instance with 10 sightseeing spots. As a result, the proposed method composed the schedule whose expected satisfaction is 95.65% of the optimum solution in 13 sec. 1. 1),2) 3) 4) 5) Lin-Kernighan 6) (Simulated Annealing) 7) 8) 10) 11) P-Tour 12) P-Tour P-Tour 13) 1 Graduate School of Information Science, Nara Institute of Science and Technology 2 Graduate School of Information Sciences Hiroshima City University 1 c2011 Information

2 . NP (predatory search) 8) 10) % % 1 2 A B C A1 A2 A3 B1 B2 C1 C (hour) c2011 Information

3 A B C C C1 70 C C2 90 B C V : Q: P : S =< A 0, L 1, A 1, L 2, A 2,,..., L n, A n, L n+1, A 0 > A 0 / A i A i =< v, actt, rest > L i L i P v V, actt Q, rest Q actt rest rest (3) 3 v.arrive Ai actt.conp actt.recv actt.stayt rest.restt L i.movet actt.sat L i.sat S Sat(S) Sat(S) = A i.actt.sat + L i.sat (1) i=0 i= G = (V, E): dist(v 1, v 2): v 1, v 2 { pre(ai.v, A 0.v.arrive) if A 0.v.arrive S.goalt sat(a i ) = (2) 0 otherwise sat(a i ) S pre(a i.v, A 0.v.arrive) A i.v A 0.v.arrive A 0 A 0.v.arrive S A 0 S.goalt S 17:00 α α L i (3) 3 c2011 Information

4 { (α Li.movet)/2 if sat(a i) > 0 sat(l i ) = (3) 0 otherwise A i RemSt(A i ) (4) (5) RemSt(A i ) = { Min(RemSt(Ai 1 ) + A i.actt.conp + A i.actt.recv, MaxSt) if i > 0 (4) InitSt otherwise A i.actt.recv = A i.rest.restt habitus (5) MaxSt InitSt habitus A i.actt.conp A i.actt.recv v i Recovery(i) (6) { habitus Resti.restt if RemSt(A i+1 ) + A i+1.actt.conp < 0 Recovery(i) = (6) 0 otherwise (7) A i.v V, A i+1.actt.conp RemSt(A i) (7) S (8) A i.actt.stayt + i=0 A i.actt.restt + i=0 L i.movet S.goalt S.startt (8) i=1 S.goalt S.start / MaximizeSat(S)s.t.constraints(7) (8) (9) 2.3 NP (TSP) TSP NP 3. (predatory search) 8),10) 3.1 Linhares Linhares (TSP) 8) (VLSI) 10) Liu 9) ( 1 ) v i V ( a ) v i v i.actt j A i v i.actt greed ( 2 ) v i.actt greed stayt shortest ( 3 ) (S.goalt - S.startt) stayt shortest number greed destinations ( 4 ) number greed destinations 4 c2011 Information

5 v i v i.actt greed current solution ( 5 ) ( a ) A 0 current solution A 0 S ( b ) S ( c ) S goalt b current solution ( d ) b ( e ) current solution satisfaction S goalt 0 ( 6 ) C presearch C presearch ( a ) V v a v b v a v a v a.actt greed changed solution ( b ) 5 changed solution satisfaction ( c ) current solution satisfaction changed solution satisfaction current solution changed solution ( 7 ) current solution S goalt 5.b current solution 5.b ( 8 ) current solution v i.actt j.greed value (10) v i.actt j.greed value = v i.actt j.sat/(v i.actt j.stayt + v i.actt j.conp/habitus) (10) Spotlevel, Orderlevel, Actlevel Actlevel A ( 1 ) A x ( 2 ) Spotlevel = 1 A x M V M V M ( 3 ) A x V 1... V M ( 4 ) Spotlevel M ( 5 ) A y V V Spotlevel ( 6 ) Orderlevel = 1 ( 7 ) V Spotlevel 3M 2 A y O 1... O 3M v 1 v 2 2 ( 8 ) Orderlevel 3M 14 ( 9 ) O Orderlevel N O Orderlevel N A 1,... A N c2011 Information

6 A best ( 10 ) A best A y A y = A best 5 12 ( 11 ) Orderlevel = Orderlevel + 1 Orderlevel = [ 3M / β ] Orderlevel = 3M [3M/β] [x] x ( 12 ) 8 ( 13 ) A x A y A x = A y 15 ( 14 ) Spotlevel = Spotlevel + 1 Orderlevel = 1 Spotlevel = [ M/ γ ] Spotlevel = M [M/γ] ( 15 ) 4 β γ (1) (2) CPU Celeron 2.00GHz 2.00GB OS WindowsXP Professional PC Java kg MaxSt = 900, habitus = m 9000m , 1.5, ) 30km/h α β = γ = 3 4 a 1h b 1.5h c 2h a 1h b 1.5h c 2h ISC Interim Solution of Calculation(ISC) (1) c2011 Information

7 5 = / 100% ISC % 2.33% 1.78% -1.76% % 2.49% 3.56% -2.97% % 7.67% 2.39% -4.35% % 4.34% 1.12% -2.25% % 3.57% 1.59% -1.89% 0ms s 0.47s 12.99s 106.2min 6 = / 100% ISC % 2.03% 5.16% % 0.48% 5.39% % -2.29% 4.23% % -7.17% 3.94% % -5.49% 4.46% 12.4ms 7.82h 2.61s 62.13s ISC % ( ) , 6,8,10,12,14,16,18,20,22,24 6,8,10, (6) (8) (10) (12) 1.37min 18.44min 106.2min min 5. TSP 95.65% c2011 Information

8 3 1) Baus, J., Krüger, A., Wahlster,W., A Resource Adaptive Mobile Navigation System, Proc. of 2002 Int l. Conf. on Intelligent User Interfaces 2002 (IUI-02), pp (2002). 2) Tang, F., You, I., Guo, M., Guo, S., Context-aware workflow management forintelligent navigation applications in pervasive environments, Intelligent Automation and Soft Computing, Vol. 16, No. 4, pp (2010). 3) Butz, A., Baus, J., Krüger, A., Lohse, M., A Hybrid Indoor Navigation System, Proc. of 2001 Int l. Conf. on Intelligent User Interfaces 2001 (IUI2001), pp (2001). 4) Cheverst, K., Davies, N., Mitchell, K., Friday, A. and Efstratiou, C., Developing a context-aware electronic tourist guide: some issues and experiences, Proc. of 2000 ACM Special Interest Group on Computer-Human Interaction (SIGCHI-00) pp (2000). 5) Rehrl, K.,Leitinger, S.,Bruntsch,S. and Mentz, H. J., Assisting orientation and guidance for multimodal travelers in situations of modal change, Proc. of 2005 IEEE Int l. Conf. on Intelligent Transportation Systems (ITSC-05) pp (2005). 6) Helsgaun, K., An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic, European Journal of Operational Research, Vol. 126, No. 1, pp (2000). 7),,,,,,, Vol.47, No.12, pp (2006) 8) Linhares, A., State-space search strategies gleaned from animal behavior: a traveling salesman experiment, Biological Cybernetics, Vol.78, No.3,pp (1998). 9) Liu, C., Wang, D., Predatory search algorithm with restriction of solution distance, Biological Cybernetics, Vol.92, No.5,pp (2005). 10) Linhares, A., Synthesizing a predatory search strategy for VLSI layouts, IEEE Trans. on Evolutionary Computation, Vol.3, Iss.2, pp (1999). 11) Ahuja, R. K., Ergun, O., Orlin, J. B., and Punnen, A. P., A survey of very large-scale neighborhood search techniques, Discrete Applied Mathematics 123, pp (2002). 12) Maruyama, A., Shibata, N., Murata, Y., Yasumoto, K. and Ito, M., P-Tour: A Personal Navigation System for Tourism, Proc. of World Congress on ITS, pp (2004). 13),,,,,, Vol.3, No.1, pp (2010). 14) Club.Panasonic,, 8 c2011 Information

12) NP 2 MCI MCI 1 START Simple Triage And Rapid Treatment 3) START MCI c 2010 Information Processing Society of Japan

12) NP 2 MCI MCI 1 START Simple Triage And Rapid Treatment 3) START MCI c 2010 Information Processing Society of Japan 1 1, 2 1, 2 1 A Proposal of Ambulance Scheduling System Based on Electronic Triage Tag Teruhiro Mizumoto, 1 Weihua Sun, 1, 2 Keiichi Yasumoto 1, 2 and Minoru Ito 1 For effective life-saving in MCI (Mass