Operations Research Letters vol:36 issue:3 pages:333-337
The latency problem with profits is a generalization of the minimum latency problem. In this generalization it is not necessary to visit all clients, however, visiting a
client may bring a certain revenue. More precisely, in the latency problem with profits, a server and a set of n clients, each with corresponding profit p_i (1 ≤ i ≤ n), are given. The single server is positioned at the origin at time t = 0 and travels with unit speed. When visiting a client, the server receives a revenue of p_i - t, with t the time at which the server reaches client i (1 ≤ i ≤ n). The goal is to select clients and find a route for the server such that total collected revenue is maximized. We formulate a dynamic programming algorithm to solve this problem when all clients are located on a line. We also consider the problem on the line with k servers and prove NP-completeness for the latency problem on the line with k non-identical servers and release dates. In this proof we also settle the complexity of an open problem in de Paepe et al. .