The time-dependent traveling salesman problem with time windows (TDTSPTW) is a variant of the well-known traveling salesman problem with time windows, in which travel times are not assumed to be constant. The TDTSPTW accounts for the effects of congestion at the planning level, being particularly suited for distribution problems in large cities. In this paper we develop a labeling-based algorithm for the TDTSPTW that incorporates partial dominance and generalizes several state-of-the-art components from the time-independent related literature. We propose a framework general enough to be applied to the TDTSPTW and its variant without time windows, with the objective of minimizing the duration or the makespan. As part of the framework, we introduce a new state-space relaxation specifically designed for the time-dependent context. Extensive computational experiments show the effectiveness of the overall approach and the impact of the new relaxation, outperforming several recent algorithms proposed for these variants on more than 9,000 benchmark instances. In addition, we frame the minimum tour duration problem within the time-dependent literature and include it as a benchmark for our algorithm, obtaining improved computation times and 31 new optimal solutions. Summary of Contribution: In this paper, we study the time-dependent traveling salesman problem with time windows (TDTSPTW), a difficult single-vehicle routing problem that incorporates more realistic travel time functions than its classic time-independent counterpart. As a result, the TDTSPTW is harder to solve, as it requires more complex models and algorithms. Using state-of-the-art optimization techniques, we propose an efficient solution approach for the TDTSPTW and some related variants that outperforms the previous approaches in the literature. Our paper emphasizes the importance of algorithmic design and efficient implementations to tackle relevant practical combinatorial optimization problems—in particular, for time-dependent problems. Moreover, the resulting algorithm fosters a new research direction regarding exact algorithms for time-dependent problems using dynamic programming and relaxation techniques. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This research has been funded by Fondo para la Investigación Científica y Tecnológica (FONCyT) [Grants PICT-2016-2677 and PICT-2018-2961] from the Ministry of Science, Argentina, and by the Google Latin America Research Award (LARA) 2019. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.1236 .

Abstract In this paper we implement a branch‐price and cut algorithm for a time dependent vehicle routing problem with time windows in which the goal is to minimize the total route duration. The travel time between two customers is given by a piecewise linear function on the departure time and, thus, it need not remain fixed along the planning horizon. We discuss different alternatives for the implementation of these linear functions within the labeling algorithm applied to solve the pricing problem. We also provide a tailored implementation for one of these alternatives, relying on efficient data structures for storing the labels, and show several strategies to accelerate the algorithm. Computational results show that the proposed techniques are effective and improve the column generation step, solving all instances with 25 customers, 49 of 56 with 50 customers, and many instances with 100 customers. Furthermore, heuristic adaptations are able to find good quality solutions in reasonable computation times.

In this article, we study the (k,c)‐coloring problem, a generalization of the vertex coloring problem where we have to assign k colors to each vertex of an undirected graph, and two adjacent vertices can share at most c colors. We propose a new formulation for the (k,c)‐coloring problem and develop a Branch‐and‐Price algorithm. We tested the algorithm on instances having from 20 to 80 vertices and different combinations for k and c, and compare it with a recent algorithm proposed in the literature. Computational results show that the overall approach is effective and has very good performance on instances where the previous algorithm fails. © 2014 Wiley Periodicals, Inc. NETWORKS, 2014 Vol. 65(4), 353–366 2015

In this article we introduce the problem of finding an optimal path in order to find a stationary object placed in the environment whose map is not a-priory known. At first sight the problem seems to be similar to exploration which has been thoroughly studied by the robotic community. We show that a general framework for search can be derived from frontier-based exploration, but exploration strategies for selection of a next goal to which navigate a robot cannot be simply reused. We present three goal selection strategies (greedy, traveling salesmen based, and traveling deliveryman based) and statistically evaluate and discuss their performance for search in comparison to exploration.