Given a graph whose arc traversal times vary over time, the time-dependent travelling salesman problem (TDTSP) consists in finding a Hamiltonian tour of least total duration covering the vertices of the graph. The contribution of this paper is twofold. First, we describe a lower and upper bounding procedure that requires the solution of a simpler (yet NP-hard) asymmetric travelling salesman problem (ATSP). In addition, we prove that this ATSP solution is optimal for the TDTSP if all the arcs share a common congestion pattern. Second, we formulate the TDTSP as an integer linear programming model for which valid inequalities are devised. These inequalities are then embedded into a branch-and-cut algorithm that is able to solve instances with up to 40 vertices.

This article introduces a variant of the conflict-free pickup and delivery problem with time windows in which speeds can be regulated. The problem arises in several areas of transportation and logistics including routing and scheduling of automated guided vehicles in port terminals and coordination of unmanned aerial vehicles in controlled airspace. A particular aspect of this problem is that at most one vehicle can traverse an arc of the transportation network at any time. The problem studied in this paper is to determine the vehicle paths and speeds on each arc of the path in such a way that no conflicts arise, the time windows are met, and the total energy consumption is minimized. A branch-and-bound algorithm is described in which a lower bound is obtained by solving a separable nonlinear problem in quadratic time. If the solution of the relaxation is not conflict free, a set of space-based and time-based branching constraints are generated to resolve the detected conflicts. Computational experiments show that, when compared with a state-of-the-art approach, the proposed method is able to generate a larger number of feasible solutions (42% on average) and reduce the computation time by an order of magnitude. Moreover, the approach results in an average energy savings of around 70%.