Abstract: In this work, we propose a hybrid heuristic in order to
solve the Team Orienteering Problem (TOP). Given a set of points (or
customers), each with associated score (profit or benefit), and a team
that has a fixed number of members, the problem to solve is to visit a
subset of points in order to maximize the total collected score. Each
member performs a tour starting at the start point, visiting distinct
customers and the tour terminates at the arrival point. In addition,
each point is visited at most once, and the total time in each tour
cannot be greater than a given value. The proposed heuristic combines
beam search and a local optimization strategy. The algorithm was
tested on several sets of instances and encouraging results were
obtained.
Abstract: In this paper, the use of beam search and look-ahead strategies for solving the strip packing problem (SPP) is investigated. Given a strip of fixed width W, unlimited length L, and a set of n circular pieces of known radii, the objective is to determine the minimum length of the initial strip that packs all the pieces. An augmented algorithm which combines beam search and a look-ahead strategies is proposed. The look-ahead is used in order to evaluate the nodes at each level of the tree search. The best nodes are then retained for branching. The computational investigation showed that the proposed augmented algorithm is able to improve the best known solutions of the literature on most instances used.