This paper proposes a new method to provide personalized tour recommendation for museum visits. It combines an optimization of preference criteria of visitors with an automatic extraction of artwork importance from museum information based on Natural Language Processing using textual energy. This project includes researchers from computer and social sciences. Some results are obtained with numerical experiments. They show that our model clearly improves the satisfaction of the visitor who follows the proposed tour. This work foreshadows some interesting outcomes and applications about on-demand personalized visit of museums in a very near future.
A first model developed in 2010 @cite_10 proposes to formulate the visitor routing problem as an extension of the open shop scheduling problem (in which each visitor group is a job and each interesting room is a machine). Each visitor group has to pass through all rooms but it is impossible for two groups of visitors to be simultaneously in the same room. This restriction can lead to non optimal or infeasible solutions if there are more visitor groups than rooms in the museum (which is the case if we consider each single visitor as a group).
@cite_10
2040552073 1853087932 2232622878 2090424605
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. We investigate the exact solution of the vehicle routing problem with time windows, where multiple trips are allowed for the vehicles. In contrast to previous works in the literature, we specifically consider the case in which it is mandatory to visit all customers and there is no limitation on duration. We develop two branch-and-price frameworks based on two set covering formulations: a traditional one where columns (variables) represent routes, that is, a sequence of consecutive trips, and a second one in which columns are single trips. One important difficulty related to the latter is the way mutual temporal exclusion of trips can be handled. It raises the issue of time discretization when solving the pricing problem. Our dynamic programming algorithm is based on concept of groups of labels and representative labels. We provide computational results on modified small-sized instances (25 customers) from Solomon’s benchmarks in order to evaluate and compare the two methods. Results show that some difficult instances are out of reach for the first branch-and-price implementation, while they are consistently solved with the second. In this paper, we consider the problem of designing personalised museum visits. Given a set of preferences and constraints a visitor might express on her visit, the aim is to compute the tour that best matches her requirements. The museum visits problem can be expressed as a planning problem, with cost optimization. We show how to bound the number of steps required to find an optimal solution, via the resolution of an instance of the shortest complete walk problem. We also point out an alternative encoding of the museum visits problem as an optimization problem with pseudo-Boolean constraints and a linear objective function. We have evaluated several constraints solvers, a planner and a tailored solver on a number of benchmarks, representing various instances of the museum visits problem corresponding to real museums. Our empirical results show the feasibility of both the planning and the constraint programming approaches. Optimal solutions can be computed for short visits and "practically good" solutions for much longer visits. In the capacitated vehicle routing problem, introduced by Dantzig and Ramser in 1959, we are given the locations of n customers and a depot, along with a vehicle of capacity k, and wish to find a minimum length collection of tours, each starting from the depot and visiting at most k customers, whose union covers all the customers. We give a quasi-polynomial time approximation scheme for the setting where the customers and the depot are on the plane, and distances are given by the Euclidean metric.