An efficient encoding scheme for a new multiple-type museum visitor routing problem with must-see and select-see exhibition rooms

Yi-Chih Hsieh; Peng-Sheng You

doi:10.2991/ijcis.2017.10.1.45

<Previous Article In Issue

Download article (PDF)

Next Article In Issue>

Volume 10, Issue 1, 2017, Pages 677 - 689

An efficient encoding scheme for a new multiple-type museum visitor routing problem with must-see and select-see exhibition rooms

Authors

Yi-Chih Hsiehyhsieh@nfu.edu.tw

Department of Industrial Management, National Formosa University, Huwei, Yunlin 632, TAIWAN

Peng-Sheng You^*^,psyuu@mail.ncyu.edu.tw

Department of Business Administration, National ChiaYi University, Chia-Yi 600, TAIWAN

^*Corresponding author: psyuu@mail.ncyu.edu.tw

Corresponding Author

Peng-Sheng Youpsyuu@mail.ncyu.edu.tw

Received 15 December 2015, Accepted 17 January 2017, Available Online 1 February 2017.

DOI: 10.2991/ijcis.2017.10.1.45 How to use a DOI?
Keywords: museum visitor routing problem; algorithm; lower bound; encoding
Abstract: We present a new multiple-type museum visitor routing problem (MT-MVRP) in which a museum’s exhibition rooms are classified into must-see and select-see rooms. A novel encoding scheme is proposed to simultaneously determine the scheduling of rooms for all of the groups and an immune based evolutionary algorithm is developed to solve the MT-MVRP. Additionally, the lower bound of the makespan for the MT-MVRP is derived. The numerical results of the immune based algorithm on three museums in Taiwan are discussed and compared with those by the other approaches.
Copyright: © 2017, the Authors. Published by Atlantis Press.
Open Access: This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

1. Introduction

Visiting a museum is a common extracurricular activity; it can also be an educational experience. Browsing the website of a museum, visitors can preview the plot of exhibition rooms and the introduction of exhibits in advance. Additionally, a few of museums have tour guides to show the visitors around the exhibits; during this tour, the origin of the exhibits, as well as other important details, will be discussed with visitors.

Usually, there are two main types of visitors for the museum, namely, individual visitor and group visitor (see Fig. 1). The former visits a museum based upon his/her own interests and may prefer to see some specific exhibits for a longer period of time. However, the latter visits a museum in groups and ignores the individual interests of exhibits. In addition, group visitors have to follow the tour guide to appreciate the exhibits with the same route.

For individual visitors, most of researchers devoted to developing a personalized schedule system without the consideration of congestion or queuing in the museum. The main goal of the personalized schedule system is to arrange a route for an individual visitor, or a group, such that he/she is able to appreciate important or interested exhibits efficiently within a given period of visiting time and his/her satisfaction is maximized. For individual visitors, Le Berre et al.¹ studied a personalized museum routing problem. Based upon the visitor’s preference of exhibits and other requirements, e.g., time restriction, they developed a planning approach to design a personalized schedule such that his/her satisfaction was maximized.

Based upon various interest functions of artwork objective values, Mathias et al.² proposed an integer linear programming and a natural language processing to the schedule optimal route for individual visitors. Lykourentzou et al.³ classified individual visitors into four animal metaphors, namely, ant, butterfly, fish and grasshopper, and also pointed that smart routing and recommendations can improve the quality of experience of museum for visitors.

For group visitors, to avoid the congestion or queuing in the museum, most of researchers devoted to scheduling the routes for all groups simultaneously. It was usually assumed that the multiple groups were from the same organization (e.g., school or company) and arrived at the museum at the same time by buses. The main goal of the multi-group schedule is to effectively arrange various routes for all multiple groups to avoid the congestion or queuing in the museum and then they can quickly depart from the museum together. For group visitors, Chou and Lin⁴ investigated a museum visitor routing problem (MVRP) with multiple groups in which each group had to visit all museum exhibition rooms such that the maximal completion time of the groups (i.e., makespan) was minimized. In 2010, Yu et al.⁵ studied a similar MVRP and derived a lower bound for the makespan. They applied a simulated annealing approach with a neighborhood search for solving the MVRP and compared the numerical results with those of the other evolutionary approaches: the conventional simulated annealing approach, genetic algorithm and ant colony optimization approach.

The conventional MVRP, considered in Chou and Lin⁴ and Yu et al.⁵, assumed that all groups had to visit all exhibition rooms once in a museum. However, since there are several exhibition rooms in a medium or large museum, it is sometimes impossible for each group to visit all of the exhibition rooms before the museum closes. Consequently, visiting all must-see exhibition rooms and some of the select-see exhibition rooms is more practical than visiting all of the exhibition rooms.

In this paper, we focus on the MVRP for group visitors and introduce a new multiple-type MVRP (MTMVRP), a more generalized MVRP, in which the exhibition rooms in a museum are classified into must-see and select-see exhibition rooms. The must-see exhibition rooms are ones that all groups have to visit, while the select-see exhibition rooms are ones that each group can visit or not visit. If the must-see exhibition rooms and the number of select-see exhibition rooms are given for all of the groups, the MT-MVRP can be used to schedule the sequence of the exhibition rooms, including the must-see and select-see rooms, for all groups, such that the maximal completion time of the groups is minimized. In 2014, Salazar-Aguilar et al.⁶ studied a multi-district team orienteering problem for road maintenance in which all tasks were divided into mandatory and optional maintenance activities. They assumed that if an optional task was completed, then a non-negative score was awarded. The objective of their problem was to maximize the total scores for optional tasks with a time restriction. Their concept of mandatory/optional maintenance activity is similar to that of the must-see/select-see exhibition rooms in this paper. However, for the convenience of computation, they assumed that the maximal number of possible routes of maintenance tasks was given. Since this assumption reduced the feasible region of solutions and the solution obtained by their approach was not the best one for the original problem.

In Taiwan, the introduced MT-MVRP is practical for students since they are usually divided into several groups or buses and arrive at the museum at the same time. Due to the time restriction, all groups have to appreciate all special exhibitions in the museum and visit some of the other general exhibitions assigned by school. Thus, the MT-MVRP aims to simultaneously schedule the routes of the must-see and select-see exhibition rooms for all groups of students, such that they can quickly depart from the museum together.

In addition, the introduced MT-MVRP generalizes the conventional MVRP considered by Chou and Lin⁴ and Yu et al.⁵, whose problem involves must-see exhibition rooms only. Since the conventional MVRP is an NP-hard problem (Yu et al.⁵), the considered MT-MVRP in this paper is also an NP-hard problem. In 2007, Chou and Lin⁴ have showed that the conventional MVRP was similar to the open-shop scheduling problem (OSSP), in which visitors are treated as jobs, exhibition rooms are viewed as machines and the maximal completion time of the groups is the makespan. Additionally, the moving time from one exhibition room to another can be modeled as the sequence dependent setup time of a machine. Therefore, we next survey the various approaches for solving OSSP and MVRP.

Adiri and Aizikowitz⁷ and Fiala⁸ proposed polynomial time algorithms to solve the OSSP with special structures. Because the general OSSP is NP-hard, Brucker et al.⁹ and Dorndorf et al.¹⁰ developed a branch-and-bound approach to obtain the exact solution. However, the branch-and-bound approach is time consuming, especially with large problem sizes. Gueret and Prins¹¹ adopted the concept of the bipartite graph to develop two approximation algorithms to solve the OSSP. Brasel et al.¹² and Liaw¹³ proposed an insertion algorithm and a recursive algorithm, respectively, to solve the OSSP. Additionally, several artificial evolutionary algorithms have also been developed for solving the OSSP. Genetic algorithms were developed by Taillard¹⁴, Fang et al.¹⁵, and Prins¹⁶. A simulated annealing approach was used by Liaw¹⁷. The Tabu search approach was used by Alcaide et al.¹⁸ and Liaw¹⁹. Panahi and Tavakkoli-Moghaddam²⁰ proposed a hybrid ant colony optimization approach for a multi-objective OSSP. For the conventional MVRP, Chou and Lin⁴ and Yu et al.⁵ proposed a simulated annealing approach to solve it; a neighborhood approach was then adopted to improve the solution. In this method, the sequence of 1 to (no. of rooms) × (no. of groups) is used to represent a feasible solution for scheduling the groups.

In this paper, we investigate a new MT-MVRP in which each group has to visit all must-see exhibition rooms and a given number of select-see exhibition rooms. The properties and the lower bound of the makespan for the MT-MVRP are also derived. A novel encoding scheme is presented to simultaneously determine the scheduling of the must-see and select-see exhibition rooms for all of the groups. Note that this encoding scheme can be embedded in most of evolutionary algorithms such as genetic algorithm (GA), particle swarm optimization (PSO) and immune based algorithm (IA). Due to numerous reports of successful applications of IA, e.g. Huang²¹ and Hsieh and You²², we adopt IA as our solution approach in this paper. Additionally, to further analyze the effectiveness of the adopted IA, we also use the other well-known evolutionary algorithms, GA and PSO, to solve. Numerical results of IA on three museums in Taiwan are discussed and compared with those by GA and PSO.

The rest of this paper is organized as follows. In Section 2, the notations, assumptions, and mathematical programming of the MT-MVRP are presented. Based upon the dominated exhibition room, we derive the properties and the lower bound of the makespan for the MT-MVRP in this section. In Section 3, the new encoding scheme for simultaneously determining the scheduling of the must-see and select-see exhibition rooms for all of the groups is presented. A simple example is also illustrated. The numerical results on three museums in Taiwan are reported and discussed in Section 4. Finally, the conclusions are summarized in Section 5.

2. A New Multiple-Type Museum Visitor Routing Problem (MT-MVRP)

2.1. Notation

Parameters

n	the number of groups.
M	the number of nodes in the museum in which nodes 1, 2, …, M−2 denote exhibition rooms 1, 2, …, M−2; nodes M−1 and M denote the exit and the entrance, respectively.
i	the index for group, 1 ≤ i ≤n.
k	the index for exhibition room, 1 ≤ k ≤ M; k = M−1 denotes the exit and k = M denotes the entrance.
m₁	the number of must-see exhibition rooms for groups. For simplicity, assume that exhibition rooms 1, 2,…, m₁ are must-see exhibition rooms.
m₂	the number of select-see exhibition rooms for groups.
M₁	={1, 2,…, m₁}, the set of must-see exhibition rooms for groups..
M₂	={m₁+1, m₁+2,…, M−2}, the candidate set of select-see exhibition rooms for groups.
v_ik	the time required to visit exhibition room k for group i, 1≤i≤n, 1≤k≤M.
m_hk	the time required to move from exhibition room h to exhibition room k, 1≤h≤M, 1≤k≤M, h≠k.
B	a big positive number.

Decision variables

x_ijk	if group i visits exhibition room k before group j then x_ijk=1, otherwise x_ijk=0, 1≤i≤n, 1≤j≤n, i≠j, 1≤k≤M.
y_ihk	if group i visits exhibition room h before exhibition room k then y_ihk=1, otherwise y_ihk=0, 1≤i≤n, 1≤h≤M, 1≤k≤M, h≠k.
u_ik	if group i visits exhibition room k then u_ik=1, otherwise u_ik=0, 1≤i≤n, 1≤k≤M.
c_ik	the completion time to visit exhibition room k for group i, 1≤i≤n, 1≤k≤M. k=M−1 denotes the exit and k=M denotes the entrance.

2.2. Assumption

(a)
There are n groups that will visit M−2 exhibition rooms. Note that node M−1 denotes the exit and node M denotes the entrance.
(b)
Group i has to visit m₁+m₂ exhibition rooms, where m₁ is the number of must-see exhibition rooms and m₂ is the number of select-see exhibition rooms. Note that, for a MT-MVRP, m₁ and m₂ are given.
(c)
There are no restrictions on the routing sequence of the exhibition rooms for all of the groups.
(d)
Each exhibition room can only contain one group at a time, i.e., one tour guide in an exhibition room.
(e)
The visit of a group in each exhibition room cannot be interrupted.
(f)
MT-MVRP aims to simultaneously: (i) choose the m₂ select-see exhibition rooms from M₂ for each group, and (ii) determine the routing sequence of the exhibition rooms, including the must-see and select-see rooms, such that the maximal completion time of the groups is minimized.

2.3. Mathematical programming model

(1)Min Max1≤i≤nci,M−1

(2)stcik−vik−mhk+(1−yihk)B ≥cih+(uih−1)B+(uik−1)B 1≤i≤n,1≤h≤M−3,h+1≤k≤M−2

(3)cih−vih−mhk+yihkB ≥cik+(uih−1)B+(uik−1)B 1≤i≤n,1≤h≤M−3,h+1≤k≤M−2

(4)cjk−cik+(1−xijk)B≥vjk+(uik−1)B+(ujk−1)B 1≤i≤n−1,j≥i+1,1≤k≤M−2

(5)cik+cjk+xijkB≥vik+(uik−1)B+(ujk−1)B 1≤i≤n−1, j≥i+1, 1≤k≤M−2

(6)cik≥mMk+vik+(uik−1)B,1≤i≤n,1≤k≤M−2

(7)ci,M−1≥cik+mk,M−1+(uik−1)B,1≤i≤n,1≤k≤M−2

(8)uik=1,1≤i≤n,1≤k≤m1

(9)∑k=m1+1M−2uik=m2,1≤i≤n

(10)2(xijk+xjik)≤uik+ujk 1≤i≤n,1≤j≤n,i≠j,1≤k≤M–2

(11)2(yihk+yikh)≤uih+uik 1≤i≤n,1≤h≤M–2,1≤k≤M–2,h≠k

(12)yiMk=1,1≤i≤n,1≤k≤M–2

(13)yik,M−1=1,1≤i≤n,1≤k≤M–2

(14)xijk∈{0,1}, 1≤i≤n, 1≤j≤n, i≠j, 1≤k≤M

(15)yihk∈{0,1},1≤i≤n,1≤h≤M,1≤k≤M,h≠k

(16)uik∈{0,1},1≤i≤n, 1≤k≤M

The objective function (1) aims to minimize the maximal completion time of the groups. Constraints (2) and (3) restrict that each group can visit one exhibition room at a time. Constraints (4) and (5) confine that each exhibition room can only contain one group at a time. Constraints (6) and (7) compute the completion time of group i by adding the moving time. Constraint (8) confines that all must-see rooms have to be visited for each group. Constraint (9) limits the number of select-see rooms for each group. Constraints (10) and (11) confine that if a room is not visited, then its corresponding x_ijk, x_jik, y_ihk and y_ikh must be zero. Constraints (12) and (13) confine that each group must enter and leave from the museum. Constraints (14) to (16) are the ranges for decision variables.

Note that, in (1) to (16), we have to determine x_ijk, y_ihk and u_ik which involve the selection of the select-see exhibition rooms for each group and the routing sequence of the exhibition rooms for all of the groups; as such, it is a combination and permutation problem. Consequently, the new introduced MT-MVRP involves both the combination problem and the permutation problem.

2.4. Properties and the lower bound of MT-MVRP

The properties and the lower-bound of makespan for the MT-MVRP are shown below.

Lemma 2.1

The considered MT-MVRP generalizes the conventional MVRP.

Proof

If all select-see exhibition rooms are required to visit, i.e., m₂=|M₂|, then each group has to visit all of the exhibition rooms. As such, the considered MT-MVRP leads to the conventional MVRP.

Lemma 2.2

The considered MT-MVRP generalizes the conventional OSSP.

Proof

If (i) all select-see exhibition rooms are required to visit, i.e., m₂=|M₂|, then each group has to visit all of the exhibition rooms, and (ii) the exhibition rooms are viewed as machines and the visitors are treated as jobs, then the considered MT-MVRP leads to the conventional OSSP.

Definition 2.3

An exhibition room k is called as a dominated room if v_ik≥v_ik′ for all 1≤i≤n, 1≤k≤M−2, 1≤k′≤M−2, k≠k′.

Lemma 2.4

If there exists a dominated must-see exhibition room k∈M₁, then LB=∑i=1nvik+min1≤k≤M−2mk,M−1+min1≤k≤M−2mM,k is a lower bound for the makespan of MT-MVRP.

Proof

If there exists a dominated must-see exhibition room k∈M₁, then v_ik≥v_ik′ for all 1≤i≤n, 1≤k′≤M−2, k′≠k. Since exhibition room k is a must-see room, all groups have to visit this room. The lower bound of the total visiting time for all of the groups is ∑i=1nvik . Since min m_k_,M-1 and min m_M_,k are the lower bounds of the moving time from the entrance and exit, LB=∑i=1nvik+min1≤k≤M−2mk,M−1+min1≤k≤M−2mM,k is a lower bound for the makespan.

Theorem 2.5

If there exists a scheduling with makespan MinMax1≤i≤nci,M−1=LB , then the scheduling is globally optimal.

Proof

The proof is straightforward by Lemma 2.4 and omitted.

3. Methodology

3.1. Immune based evolutionary algorithm

In this section, we present an immune based approach for the MT-MVRP. To shorten the paragraph of this paper, we refer to Huang²¹ and Weissman and Cooper²³ for the details of the immune system and its mechanism. The primary steps of the proposed immune based algorithm (IA) are similar to those of Hsieh and You²² and Hsieh and You²⁴.

The steps are as follows:

Step 1.
Randomly generate an initial population of strings; each string is a random permutation of 1, 2, …, I, where I=(m₁+m₂)×n is the total number of exhibition rooms visited for all groups.
Step 2.
Evaluate the makespan for each string in the current population.
Step 3.
Select the best g strings with the best makespan.
Step 4.
Clone the best g strings selected in Step 3 by using the genetic operation process, i.e., crossover and mutation (Michalewicz²⁵).
Step 5.
Calculate the new makespan for the new strings from Step 4. Select the superior strings in the memory set and update the memory set with the superior strings. Note that the strings with too similar structures will be eliminated.
Step 6.
Check the stopping criterion of the maximum generations. If not stop, go to Step 2, otherwise go to the next step.
Step 7.
Stop. Report the optimal or near optimal solution(s) from the memory set.

3.2. New encoding scheme

We now present the main steps of the novel encoding scheme for the sequence of the exhibition rooms for all groups. In the encoding scheme, we convert a random permutation of 1, 2,…, I to represent a feasible routing sequence of exhibition rooms for all groups, where I=(m₁+m₂)× n is the total number of exhibition rooms visited for all groups.

The main steps of the new encoding scheme are as follows. Note that, in the steps, R is the index for rooms.

Step 0.
R=ϕ, given n, m₁, m₂, M₁, M₂.
Step 1.
Generate a random permutation of 1 to I, termed T, where I=the total number of exhibition rooms visited for all groups, including the must-see and select-see exhibition rooms.
Step 2.
Based upon the total number of exhibition rooms for each group, divide T into 2n groups with T = (T₁₁∪T₁₂) ∪… (T_i₁∪T_i₂) ∪ … ∪ (T_n₁∪T_n₂).
Step 3.
Construct a table as Table 1. For each i, 1≤ i ≤ n, execute the following steps in (a) and (b).
1. (a)
  1. (i)
    p=0. S₁=M₁.
  2. (ii)
    Let w=max{T_i₁}. Add the {(w mod (m₁−p))+1}^th number in set S₁ to its corresponding location in R; delete it from set S₁. That is, R(index) = the {(w mod (m₁−p))+1}^th number in set S₁.
  3. (iii)
    Delete w from T_i₁. Let p=p+1 and repeat (ii) until T_i₁ = ϕ.
2. (b)
  1. (i)
    p=0. S₂=M₂.
  2. (ii)
    Let w=max{T_i₂}. Add the {(w mod (|M₂|−p))+1}^th number in set S₂ to its corresponding location in R; delete it from set S₂. That is, R(index)=the {(w mod (|M₂|−p))+1}^th number in set S₂.
  3. (iii)
    Delete w from T_i₂. Let p=p+1 and repeat (ii) until T_i₂ = ϕ.
Step 4.
Follow the sequence of T, from 1, to I, and its corresponding value in R to construct the routes for all groups.

3.3. Example

Assume that there are five groups that will visit five exhibition rooms in a museum. Suppose that exhibition rooms 1 and 2 are must-see rooms for all of the groups. Additionally, all groups have to visit two select-see exhibition rooms from rooms 3, 4 and 5. That is, n=5, M₁={1,2}, M₂={3,4,5}, |M₂|=3, m₁=m₂=2. The step by step process of the encoding procedure for this example is shown below.

Step 0.
R = ϕ. M₁={1,2}, M₂={3,4,5}, m₁ = m₂ = 2, 1≤i≤5.
Step 1.
Since each group has to visit 4 rooms, I=20(=4×5). Suppose that T=12-5-16-19-3-4-11 -9-15-14-2-10-8-13-6-17-18-20-1-7 is a random permutation of 1 to 20.
Step 2.
As shown in Table 1, divide T into 2n=10 groups with T=(T₁₁∪T₁₂) ∪… ∪ (T₅₁∪T₅₂), where T₁₁ = {12,5}, T₁₂={16,19}, …, T₅₁={18, 20}, T₅₂={1,7}.
Step 3.
i=1.
1. (a)
  (i) p=0. S₁={1,2}. (ii) w=max{12,5}=12. Since {(w mod (m₁−p))+1}={(12 mod (2-0))+1}=1, the 1^st number in S₁={1,2} is 1. R(1)=1. S₁={1,2}−{1}={2}. (iii) T₁₁={12,5}−{12}={5}. p=1. (ii) w=max{5}=5. Since {(w mod (m₁−p))+1}={(5 mod (2-1))+1}=1, the 1^st number in S₁={2} is 2. R(2)=2. (iii) T₁₁={5}−{5}=ϕ.
2. (b)
  (i) p=0. S₂={3,4,5}. (ii) w=max{16,19}=19. Since {(w mod (|M₂|−p))+1}={(19 mod (3-0))+1}=2, the 2^nd number in S₂={3,4,5} is 4. R(4)=4. S₂={3,4,5}−{4}={3,5}. (iii) T₁₂= {16,19}−{19}={16}. p=1. (ii) w= max{16} =16. Since {(16 mod (3-1))+1=1, the 1^st number in S₂={3,5} is 3. R(3)=3. (iii) T₁₂={16}−{16}=ϕ.
i=2.
1. (a)
  (i) p=0. S₁={1,2}. (ii) w=4. R(6)=1. S₁={1,2}−{1}={2}. (iii) T₂₁={3,4}−{4}={3}. p=1. (ii) w=3. R(5)=2. (iii) T₂₁={3}−{3}= ϕ.
2. (b)
  (i) p=0. S₂={3,4,5}. (ii) w=11. R(7)=5. S₂={3,4,5}−{5}={3,4}. (iii) T₂₂={11,9}−{11}={9}. p=1. (ii) w=9. R(8)=4. (iii) T₂₂={9}−{9}= ϕ.
i=3.
1. (a)
  (i) p=0. S₁={1,2}. (ii) w=15. R(9)=2. S₁={1}. (iii) T₃₁={14}. p=1. (ii) w=14. R(10)=1. (iii) T₃₁= ϕ.
2. (b)
  (i) p=0. S₂={3,4,5}. (ii) w=10. R(12)=4. S₂={3,5}. (iii) T₃₂={2}. p=1. (ii) w=2. R(11)=3. (iii) T₃₂= ϕ.
i=4.
1. (a)
  (i)p=0. S₁={1,2}. (ii) w=13. R(14)=2. S₁={1}. (iii) T₄₁={8}. p=1. (ii) w=8. R(13)=1. (iii) T₄₁=ϕ.
2. (b)
  (i) p=0. S₂={3,4,5}. (ii) w=17. R(16)=5. S₂={3,4}. (iii) T₄₂={6}. p=1. (ii) w=6. R(15)=3. (iii) T₄₂= ϕ.
i=5.
1. (a)
  (i) p=0. S₁={1,2}. (ii) w=20. R(18)=1. S₁={2}. (iii) T₅₁={18}. p=1. (ii) w=18. R(17)=2. (iii) T₅₁= ϕ.
2. (b)
  (i) p=0. S₂={3,4,5}.(ii) w=7. R(20)=4. S₂={3,5}. (iii) T₅₂={1}. p=1. (ii) w=1. R(19)=5. (iii) T₅₂= ϕ.
Step 4:
The completed sequence R for this example is shown in Table 1. Following the sequence of T from 1 to 20, we may construct the following routing sequence of rooms with the use of G and R in Table 1. Note that this routing sequence of rooms can be further used to construct Gantt chart for all groups.

Table 1.

Encoding scheme for the example

The assignment of routing sequence:

G₅(5)→G₃(3)→G₂(2)→G₂(1)→G₁(2)→G₄(3)→G₅(4)→G₄(1)→G₂(4)→G₃(4)→G₂(5)→G₁(1)→G₄(2)→G₃(1)→G₃(2)→G₁(3)→G₄(5)→G₅(2)→G₁(4)→G₅(1) where G_i(k) denotes that group i visits exhibition room k. That is, in the Gantt chart, we assign Group 5 to visit exhibition room 5 firstly; we then assign Group 3 to visit exhibition room 3 secondly, and so on. Note that in this example, Group 1 visits rooms 2, 1, 3, 4 (in this order); Group 2 visits rooms 2, 1, 4, 5, Group 3 visits rooms 3, 4, 1, 2, Group 4 visits rooms 3, 1, 2, 5, and Group 5 visits rooms 5, 4, 2, 1. However, the random sequence T in Table 1 shows that no two groups will visit a room at the same time. For example, Groups 3 and 4 will visit room 3, but G₃(3) is the 2^nd task to assign and G₄(3) is the 6^th task to assign in T. In other words, Group 3 visits room 3 before Group 4 does.

4. Numerical Results and Discussions

4.1. Test problems and experimental results

In this paper, based upon the new encoding scheme, we develop an immune evolutionary algorithm for solving the instances of three museums in Taiwan (i.e., Yunlin Palm Puppets Museum, National Museum of History, and Chung Tai Museum). The plot plans and the moving times (minute) of these three museums are illustrated in Figs. 2 through 4. The time it takes to move from the entrance to the exhibition rooms and the exit are listed in Tables 2 through 4. Additionally, the time it takes to visit each exhibition room is illustrated in Tables 2 to 4.

Visiting time (min)	Room 1	Room 2	Room 3	Room 4

Group 1	16.5	15.1	30.1	27.5
Group 2	16.3	15.8	31.1	27.5
Group 3	17.6	16.5	30.3	28.0
Group 4	16.9	16.2	32.8	29.0
Group 5	17.3	16.4	32.8	28.2

Moving time (min)	Room 1	Room 2	Room 3	Room 4

Room 1	--	0.4	1.4	1.6
Room 2	0.4	--	1.4	1.6
Room 3	1.4	1.4	--	1.0
Room 4	1.6	1.6	1.0	--
Entrance	0.6	0.6	1.6	1.8
Exit	0.6	0.6	1.6	1.8

Table 2.

Visiting time and moving time for groups in Yunlin Palm Puppets Museum (Problem 1)

Visiting time (min)	Room 1	Room 2	Room 3	Room 4	Room 5	Room 6

Group 1	15.2	10.5	20.4	22.6	12.2	14.4
Group 2	15.1	10.9	20.5	22.5	12.3	14.3
Group 3	15.1	10.7	20.4	22.2	12.4	14.3
Group 4	15.4	10.6	20.5	22.6	12.3	14.3
Group 5	15.3	10.2	20.0	22.5	12.6	14.6
Group 6	15.8	11.1	21.0	23.0	13.3	15.6
Group 7	15.7	11.4	21.1	22.9	12.8	15.5
Group 8	15.8	11.9	20.9	23.3	12.9	15.3
Group 9	16.7	11.6	21.4	24.0	13.4	15.1
Group 10	16.6	11.2	21.1	23.1	13.6	15.7

Moving time (min)	Room 1	Room 2	Room 3	Room 4	Room 5	Room 6

Room 1	--	0.6	1.1	1.5	1.5	1.5
Room 2	0.6	--	0.7	1.1	1.3	1.7
Room 3	1.1	0.7	--	0.8	1.0	1.4
Room 4	1.5	1.1	0.8	--	0.6	1.0
Room 5	1.5	1.3	1.0	0.6	--	0.6
Room 6	1.5	1.7	1.4	1.0	0.6	--
Entrance	0.3	0.7	1.2	1.6	1.6	1.6
Exit	1.6	1.8	1.5	1.1	0.7	0.3

Table 3.

Visiting time and moving time for groups in National Museum of History (Problem 2)

Visiting time (min)	Room 1	Room 2	Room 3	Room 4	Room 5	Room 6	Room 7	Room 8

Group 1	9.2	10.1	13.3	12.1	15.0	16.2	20.1	17.1
Group 2	9.3	10.4	13.5	12.0	15.2	16.3	20.3	17.0
Group 3	9.3	10.2	13.6	12.3	15.4	16.0	20.1	17.0
Group 4	9.4	10.2	13.5	12.2	15.5	16.4	20.3	17.0
Group 5	9.3	10.4	13.2	12.5	15.1	16.5	20.1	17.2
Group 6	9.5	10.7	13.9	12.7	15.6	17.1	20.7	17.9
Group 7	9.7	10.8	13.7	12.8	15.8	16.8	20.5	17.6
Group 8	9.6	10.6	14.0	13.0	15.9	16.6	20.9	17.8
Group 9	9.6	10.9	13.9	12.9	16.0	16.8	21.0	18.7
Group 10	9.8	10.8	13.9	13.0	15.9	17.2	21.0	18.7
Group 11	9.9	11.9	14.5	13.5	16.3	17.7	22.7	19.4
Group 12	10.1	11.2	14.2	13.6	16.7	17.7	21.9	19.3
Group 13	10.0	11.2	15.8	14.4	17.4	17.5	21.2	18.8
Group 14	10.2	12.6	15.9	14.1	16.5	18.6	22.0	19.7
Group 15	10.7	12.7	15.6	13.9	16.6	17.9	21.5	19.3

Moving time (min)	Room 1	Room 2	Room 3	Room 4	Room 5	Room 6	Room 7	Room 8

Room 1	--	0.6	1.8	1.9	1.8	2.3	2.4	2.3
Room 2	0.6	--	1.8	1.9	1.8	2.3	2.4	2.3
Room 3	1.8	1.8	--	0.7	0.6	1.9	2.0	1.9
Room 4	1.9	1.9	0.7	--	0.7	2.0	2.1	2.0
Room 5	1.8	1.8	0.6	0.7	--	1.9	2.0	1.9
Room 6	2.3	2.3	1.9	2.0	1.9	--	0.7	0.6
Room 7	2.4	2.4	2.0	2.1	2.0	0.7	--	0.7
Room 8	2.3	2.3	1.9	2.0	1.9	0.6	0.7	--
Entrance	0.8	0.8	2.0	2.1	2.0	2.5	2.6	2.5
Exit	0.8	0.8	2.0	2.1	2.0	2.5	2.6	2.5

Table 4.

Visiting time and moving time for groups in Chung Tai Museum (Problem 3)

To analyze the performance of the proposed approach in this paper, we vary the number of must-see and select-see exhibition rooms for these three museums, such that the percentages of the rooms visited by the groups range from 50% to 100%. Note that the MT-MVRP leads to the conventional MVRP when the percentage of rooms visited by the groups is 100%. More details of the test instances, including the number of must-see and select-see exhibition rooms for these three museums, are shown in Table 5. Overall, there are 14 test instances in the numerical experiments.

Problem	Instance	n	Rooms (A)	Must-see		Select-see		Percentage of visit (B+C)/A

				NOB (B)	Room no.	NOB (C)	Room no.
1	1	5	4	1	1	1	2,3,4	50.0%
	2	5	4	1	1	2	2,3,4	75.0%
	3	5	4	2	1,2	1	3,4	75.0%
	4	5	4	2	1,2	2	3,4	100.0%

2	5	10	6	1	1	2	2,3,4,5,6	50.0%
	6	10	6	1	1	4	2,3,4,5,6	83.0%
	7	10	6	2	1,2	3	3,4,5,6	83.0%
	8	10	6	2	1,2	4	3,4,5,6	100.0%

3	9	15	8	2	1,2	2	3,4,5,6,7,8	50.0%
	10	15	8	2	1,2	4	3,4,5,6,7,8	75.0%
	11	15	8	3	1,2,3	3	4,5,6,7,8	75.0%
	12	15	8	3	1,2,3	4	4,5,6,7,8	87.5%
	13	15	8	4	1,2,3,4	3	5,6,7,8	87.5%
	14	15	8	4	1,2,3,4	4	5,6,7,8	100.0%

Note: NOB=No. of Rooms to be selected.

Table 5.

Test instances for three museums

For each instance, we test our immune based evolutionary algorithm 50 times; hence, the total number of trials in this study was 700 (= 14 instances × 50 times) for IA. In the experiments, the parameters of the proposed immune based evolutionary algorithms were set as: population=100, generation=1000, crossover=0.6878, mutation=0.1.

To further analyze the performance of the adopted immune based algorithm (IA), we also test the other well-known evolutionary algorithms, genetic algorithm (GA) and particle swarm optimization (PSO) algorithm. The introduction of GA and PSO are referred to Goldberg²⁶ and Kennedy and Eberhart²⁷, respectively. The parameters of GA are set as those of IA, and the parameters of PSO, based upon our preliminary experiments, are set as population=100, generation= 3000, c₁=0.7 (cognitive scaling parameter), c₂=0.1 (social scaling parameter).

The proposed IA, GA and PSO were coded in MATLAB. All numerical results were computed on a PC with an Intel(R) Core(TM) i7-2600 CPU3.4GHz RAM 4GB. The numerical results are reported in Table 6; the results illustrate the best solution, the average solution, the standard deviation of the solution, CPU time (seconds) of algorithm, the gap of the best solution of IA and the lower bound.

Problem	Instance	n	R	IA				GA				PSO				LB	Gap

				Best	Avg.	Std.	CPU(s)	Best	Avg.	Std.	CPU(s)	Best	Avg.	Std.	CPU(s)
1	1	5	4	85.8	85.80	0.00	206.86	85.8	85.80	0.00	124.43	85.8	85.80	0.00	112.72	85.5	0.35%
	2	5	4	86.6	86.91	0.44	335.02	86.6	89.19	3.00	192.27	86.6	86.73	0.14	253.61	85.5	1.29%
	3	5	4	86.6	87.91	1.75	187.10	86.8	94.65	3.18	124.86	86.6	90.40	1.68	154.62	85.5	1.29%
	4	5	4	160.3	160.30	0.00	369.43	160.3	160.30	0.00	172.88	160.3	160.30	0.00	286.21	158.3	1.26%

2	5	10	6	158.6	158.60	0.00	1416.51	158.6	158.60	0.00	366.99	158.6	158.60	0.00	550.80	157.3	0.83%
	6	10	6	158.6	158.60	0.00	2509.42	158.6	158.60	0.00	712.89	158.6	171.58	3.75	1066.26	157.3	0.83%
	7	10	6	158.6	163.06	2.34	2025.61	169.6	170.09	0.43	569.31	169.9	175.21	3.61	820.73	157.3	0.83%
	8	10	6	231.4	231.40	0.00	2739.70	231.4	231.48	0.57	634.60	231.4	231.65	0.88	1087.95	229.3	0.92%

3	9	15	8	166.3	176.27	0.23	2614.34	176.1	177.75	2.70	557.38	176.1	176.28	0.19	856.93	166.3	0.00%
	10	15	8	176.3	180.64	2.67	3204.77	179.4	189.71	10.33	1100.73	222.4	233.65	5.19	1612.73	166.3	6.01%
	11	15	8	216.5	216.50	0.00	3902.33	216.5	217.70	4.07	898.97	216.5	224.37	4.94	1164.49	214.1	1.12%
	12	15	8	216.5	217.51	2.06	4432.34	216.5	222.89	10.65	1428.07	261.2	277.99	6.26	1453.72	214.1	1.12%
	13	15	8	216.5	217.43	1.62	3742.47	216.5	222.60	11.32	1200.98	261.3	270.92	5.81	1182.30	214.1	1.12%
	14	15	8	319.5	319.50	0.00	1653.48	319.5	320.32	2.90	1358.04	326.8	339.26	6.31	1404.51	315.9	1.14%

LB=lower-bound of makespan. R=Rooms.

Table 6.

Numerical results of instances for three museums by IA, GA and PSO (50 trials)

4.2. Discussion

From Table 6, it is seen that:

(a)
For each test instance, with an increase in the number of exhibition rooms visited, the best completion time of the groups increases in a stair-type format. For example, in Problem 2, the completion time of the groups for Instances 5, 6 and 7 is 158.6 for IA; the completion time of the groups for Instance 8 is 231.4 for IA. The results imply that the completion time does not necessarily increase when the number of rooms visited is small. Similar results can be found for those of GA and PSO.
(b)
For all instances, IA, GA and PSO can effectively solve the MT-MVRP. Moreover, IA is superior to both GA and PSO for Instances 7, 9 and 10. For example, for Instance 10, the best solution by IA is 176.3, however, it is 179.4 and 222.4 for GA and PSO, respectively.
(c)
For each problem, the standard deviation of the 50 solutions for the various test instances is pretty low for IA. This implies that the adopted IA is stable enough to solve the MT-MVRP. For example, in the 14 test instances, the standard deviation of the 50 solutions is zero for 7 instances by IA. However, for GA and PSO, there are only 4 and 3 instances respectively with zero standard deviation for the 50 solutions. This also implies that IA is more stable than GA and PSO.
(d)
For each problem, with an increase in the number of exhibition rooms visited, the CPU time of obtaining the solution is stable or increases slightly. For example, for Problem 2, the CPU time of Instances 5 to 8 is 1416.51, 2509.42, 2025.61 and 2739.70 for IA, respectively. Similar results can be found for those of GA and PSO.

Note that GA and PSO are faster than IA. For example, for Problem 2, the CPU time of Instances 5 to 8 is 366.99, 712.89, 569.31 and 634.60 for GA.
(e)
The lower bound by the Theorem 2.5 in Section 2.4 was effective for most of the test instances, except for Instance 10 in Problem 3. The main reason for the large gap of 6.01% in Table 6 is that the visiting time for the must-see exhibition room was much smaller than for those of the other exhibition rooms. For example, in Table 4, the visiting times for exhibition rooms 1 and 2 were much smaller than those of exhibition rooms 3 and 4. However, for the other instances, the numerical results by the IA were close to the lower bounds of the makespan by Theorem 2.5. This implies that the proposed approach can effectively solve the MT-MVRP. It further implies that the lower bound of the makespan derived in this paper is effective, especially when the visiting time for the dominated exhibition room is larger than those of the other exhibition rooms.

5. Conclusions

(a)
We have introduced a new multiple-type museum visitor routing problem (MT-MVRP) which involves a combination of exhibition rooms and the routing of groups. As shown, the presented MT-MVRP generalizes both the conventional MVRP and the open-shop scheduling problem (OSSP).
(b)
We have developed the mathematical programming for the MT-MVRP and illustrated that it is an NP-hard problem.
(c)
We have derived the properties and the lower bound for the MT-MVRP, based on the dominated exhibition room. The numerical results have shown that the derived lower bound of the makespan is effective, especially when the visiting time for the dominated exhibition room is larger than those of the other exhibition rooms.
(d)
We have presented a novel encoding scheme to simultaneously determine the scheduling of the must-see and select-see exhibition rooms for all of the groups. The encoding scheme has been embedded in IA to solve the MT-MVRP.
(e)
We have reported, discussed and compared the numerical results of three museums in Taiwan for IA, GA and PSO. On the whole, numerical results have shown that the solutions by IA are superior to those of GA and PSO.
(f)
We have shown the effectiveness of the proposed approach and the derived lower bounds of the makespan.

In the future, one may extend this work with the consideration of group’s preference of exhibits or apply the other intelligence evolutionary algorithm for solving the considered problem.

Acknowledgements

The authors thank Mr. J.S. Chen for the collection of partial numerical results of experiments and two anonymous reviewers for their helpful comments and suggestions that greatly improved the presentation of this paper. This research is supported by Ministry of Science and Technology, Taiwan, under grant No. MOST 103-2221-E-150-026 and MOST 104-2221-E-150-022-MY2.

References

1.D Le Berre, P Marquis, and S Roussel, Planning personalized museum visits, in Proc. of the 23 Int. Conf. on Automated Planning and Scheduling ICAPS (2013), pp. 380-388. https://www.aaai.org/ocs/index.php/ICAPS/ICAPS13/paper/download/6025/6207

2.M Mathias, A Moussa, F Zhou, J-M Torres-Moreno, M-S Poli, D Josselin, M El-Bèze, AC Linhares, and F Rigat, Optimisation using natural language processing: personalized tour recommendation for museums, in Proc. of the 2014 Federated Conf. on Computer Science and Information Systems (2014), pp. 439-446.

3.I Lykourentzou, X Claude, Y Naudet, E Tobias, A Antoniou, G Lepouras, and C Vasilakis, Improving museum visitors’ quality of experience through intelligent recommendations: a visiting style-based approach, in Workshop Proc. of the 9th Int. Conf. Intelligent Environments (2013), pp. 507-518.

4.SY Chou and SW Lin, Museum Visitor Routing Problem with the Balancing of Concurrent Visitors, Complex Systems Concurrent Engineering, Springer-Verlag, New York, 2007. book chapter,

5.VF Yu, SW Lin, and SY Chou, The museum visitor routing problem, Appl. Math. Comput, Vol. 216, 2010, pp. 719-729.

6.MA Salazar-Aguilar, A Langevin, and G Laporte, The multi-district team orienteering problem, Comput. & Oper. Res, Vol. 41, 2014, pp. 76-82.

7.I Adiri and N Aizikowitz, Open shop scheduling problems with dominated machines, Nav. Res. Log. Quarterly, Vol. 36, 1989, pp. 273-281.

8.T Fiala, An algorithm for the open-shop problem, Math. Oper. Res, Vol. 8, 1983, pp. 100-109. http://dx.doi.org/10.1287/moor.8.1.100

9.P Brucker, J Hurink, B Jurish, and B Wostmann, A branch and bound algorithm for the open-shop problem, Discrete Applied Mathematics, Vol. 76, 1997, pp. 43-59.

10.U Dorndorf, E Pesch, and T Phan-Huy, Solving the open shop scheduling problem, J. Sched, Vol. 4, No. 3, 2001, pp. 157-174.

11.C Gueret and C Prins, Classical and new heuristics for the open-shop problem: a computational evaluation, Eur. J. Oper. Res, Vol. 107, 1998, pp. 306-314.

12.H Brasel, T Tautenhahn, and F Werner, Constructive heuristic algorithms for the open shop problem, Computing, Vol. 51, 1993, pp. 95-110.

13.CF Liaw, An iterative improvement approach for the nonpreemptive open shop scheduling problem, Eur. J. Oper. Res, Vol. 111, 1998, pp. 509-517.

14.E Taillard, Benchmarks for basic scheduling problems, Eur. J. Oper. Res, Vol. 64, 1993, pp. 278-285.

15.HL Fang, P Ross, and D Corne, A promising hybrid GA/heuristic approach for open-shop scheduling problems, in Proc. of the 11th European Conf. on Artificial Intelligence (Amsterdam, Netherlands, 1994).

16.C Prins, Competitive genetic algorithms for the open-shop scheduling problem, Math. Method. Oper. Res, Vol. 52, 2000, pp. 389-411.

17.CF Liaw, Applying simulated annealing to the open shop scheduling problem, IIE Trans, Vol. 31, 1999, pp. 457-465.

18.D Alcaide, J Sicilia, and D Vigo, Heuristic approaches for the minimum makespan open shop problem, TOP, Vol. 5, 1997, pp. 283-296. http://link.springer.com/article/10.1007/BF02568554

19.CF Liaw, A tabu search algorithm for the open shop scheduling problem, Comput. Oper. Res, Vol. 26, 1999, pp. 109-126.

20.H Panahi and R Tavakkoli-Moghaddam, Solving a multi objective open shop scheduling problem by a novel hybrid ant colony optimization, Expert Sys. Appl, Vol. 38, 2011, pp. 2817-2822.

21.SJ Huang, Enhancement of thermal unit commitment using immune algorithms based optimization approaches, Electr. Pow. Energ. Syst, Vol. 21, 1999, pp. 245-252.

22.YC Hsieh and PS You, An immune evolutionary approach for the label printing problem, Int. J. Comput. Int. Sys, Vol. 7, 2014, pp. 515-523.

23.IL Weissman and MD Cooper, How the immune system develops, Sci. Am, Vol. 269, 1993, pp. 33-40. http://www.scientificamerican.com/magazine/sa/1993/09-01/

24.YC Hsieh and PS You, An effective immune based two-phase approach for the optimal reliability-redundancy allocation problem, Appl. Math. Comput, Vol. 218, 2011, pp. 1297-1307.

25.Z Michalewicz, Genetic Algorithm + Data Structures = Evolution Programs, Springer-Verlag, New York, 1994.

26.DE Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, MA, 1989. ISBN:0201157675

27.J Kennedy and RC Eberhart, Particle Swarm Optimization, in Proc. IEEE Int. Conf. on Neural Networks (Piscataway, NJ, 1995), pp. 1942-1948.

<Previous Article In Issue

Download article (PDF)

Next Article In Issue>

Journal: International Journal of Computational Intelligence Systems
Volume-Issue: 10 - 1
Pages: 677 - 689
Publication Date: 2017/02/01
ISSN (Online): 1875-6883
ISSN (Print): 1875-6891
DOI: 10.2991/ijcis.2017.10.1.45 How to use a DOI?
Open Access: This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

Cite this article

ris enw bib

TY  - JOUR
AU  - Yi-Chih Hsieh
AU  - Peng-Sheng You
PY  - 2017
DA  - 2017/02/01
TI  - An efficient encoding scheme for a new multiple-type museum visitor routing problem with must-see and select-see exhibition rooms
JO  - International Journal of Computational Intelligence Systems
SP  - 677
EP  - 689
VL  - 10
IS  - 1
SN  - 1875-6883
UR  - https://doi.org/10.2991/ijcis.2017.10.1.45
DO  - 10.2991/ijcis.2017.10.1.45
ID  - Hsieh2017
ER  -

download .riscopy to clipboard