Recent research suggests that users of a recommender system may like to receive useful unexpected suggestions that provide a pleasant surprise. This concept, called serendipity, is one of the aspects that have been proposed to meet user expectations for the recommendations they receive. Introducing serendipity means going beyond the “more of the same” aspect that past recommender systems are criticized for. A new approach has recently been proposed to create user models from their previous ratings. In this paper, we show how this user modelling approach can be used to investigate the relationship between users’ preferences, their previous ratings and their judgments related to serendipity. Experiments in the movie domain show that the more relevant an item is to a user, the more willing the user is to discover attributes that are unfamiliar to him, as long as these attributes do not play an important role in his ratings.

Distance metric learning algorithms aim to learn how to measure similarities between data objects in a metric space. In the context of clustering, metric learning typically relies on side-information provided by experts, most commonly expressed in the form of pairwise constraints. In this setting, algorithms for metric learning execute data transformations that bring pairs of data points involved in must-link constraints close together, whereas pair of points involved in cannot-link constraints are moved away from each other. One caveat to such methods is that they can considerably change the original data distribution properties. With that in mind, we propose a Lagrangian-based approach to assist distance metric learning algorithms for clustering. Our method is developed to identify the least impactful transformations to the original data space, while still learning a more suitable metric space for grouping the data using the provided side information. Our results demonstrate that the proposed methodology is able to achieve a competitive clustering performance with respect to truth classification. Furthermore, the method is able to provide more accurate views of the transformed datasets, which can lead to more reliable clustering interpretations.

Abstract In this article, we study the capacitated team orienteering problem where split deliveries are allowed. A set of potential customers is given, each associated with a demand and a profit. The set of customers to be served by a fleet of capacitated vehicles has to be identified in such a way that the profit collected is maximized, while satisfying constraints on the maximum time duration of each route and the vehicle capacity constraints. When split deliveries are allowed, each customer may be served by more than one vehicle. We show that the profit collected by allowing split deliveries may be as large as twice the profit collected under the constraint that each customer has to be served by one vehicle at most. We then present a branch‐and‐price exact algorithm and a hybrid heuristic. We show the effectiveness of the proposed approaches on benchmark instances and on a new set of instances that allow us to computationally evaluate the impact of split deliveries. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(1), 16–33 2014

Abstract In this article, we study a variant of the capacitated team orienteering problem, that is the problem where a fleet of vehicles, each with a constraint on the time available, is given to serve profitable customers with the objective of maximizing the collected profit. We study the variant where customers may be only partially served (incomplete service) and, if beneficial, also by more than one vehicle (split deliveries). We will analyze the maximum theoretical increase of the profit due to the incomplete service and to the split deliveries. We also computationally measure such increase on a set of instances, by means of an exact algorithm on small/medium size instances and of two heuristics on instances of larger size. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(2), 135–145 2014

We consider an inventory routing problem in discrete time where a supplier has to serve a set of customers over a multiperiod horizon. A capacity constraint for the inventory is given for each customer, and the service cannot cause any stockout situation. Two different replenishment policies are considered: the order-up-to-level and the maximum-level policies. A single vehicle with a given capacity is available. The transportation cost is proportional to the distance traveled, whereas the inventory holding cost is proportional to the level of the inventory at the customers and at the supplier. The objective is the minimization of the sum of the inventory and transportation costs. We present a heuristic that combines a tabu search scheme with ad hoc designed mixed-integer programming models. The effectiveness of the heuristic is proved over a set of benchmark instances for which the optimal solution is known.

This article describes new construction and postoptimization heuristics for the Undirected Rural Postman Problem. Extensive computational tests indicate that some combinations of these heuristics consistently produce optimal or high-quality solutions.