The museum visitor routing problem

摘要

In the museum visitor routing problem (MVRP), each visitor group has some exhibit rooms of interest. The visiting route of a certain visitor group requires going through all the exhibit rooms that the group wants to visit. Routes need to be scheduled based on certain criteria to avoid congestion and/or prolonged touring time. In this study, the MVRP is formulated as a mixed integer program which is an extension of the open shop scheduling (OSS) problem in which visitor groups and exhibit rooms are treated as jobs and machines, respectively. The time each visitor group spends in an exhibit room is analogous to the processing time required for each job on a particular machine. The travel time required from one exhibit room to another is modeled as the sequence-dependent setup time on a machine, which is not considered in the OSS problem. Due to the intrinsic complexity of the MVRP, a simulated annealing (SA) approach is proposed to solve the problem. Computational results indicate that the proposed SA approach is capable of obtaining high quality MVRP solutions within a reasonable amount of computational time and enables the approach to be used in practice.