The delay constrained least cost (DCLC) problem is to find the least cost path in a graph subject to a delay constraint. First formulated in the context of routing in computer networks, the DCLC model also applies to problems of path planning and other decision problems. DCLC is NP-complete. Many heuristic methods have been proposed for it. This note presents two new methods based on the k-shortest-path (kSP) approach. These heuristic methods one centralized, the other distributed-are both polynomial. In numerical experiments the proposed algorithms almost always find the optimal paths.