This study investigates randomized constructive heuristics for the Vehicle Routing Problem with Time Windows (VRPTW), focusing on the Nearest Neighbor, Best Insertion, and Regret-k heuristics. While these methods are fundamental deterministic initializers for metaheuristics like Ant Colony Optimization (ACO), their potential within a randomized, multi-start framework remains under-explored. We propose a novel randomization strategy for the Regret-k heuristic — a topic previously absent from the literature — by distinguishing between the customer selection ("who") and insertion position ("where") decisions. Specifically, we introduce a probabilistic selection mechanism proportional to regret values. The proposed heuristics are implemented in C++ bound to Python and evaluated on classic Solomon and Gehring & Homberger benchmarks (100 - 1000 customers) following DIMACS 2021 conventions. Results are compared against Best Known Solutions and the state-of-the-art Hybrid Genetic Search (HGS), offering new insights for the design of efficient hybrid metaheuristics.