Combinatorial optimization problems often rely on heuristic algorithms to generate efficient solutions. However, the manual design of heuristics is resource-intensive and constrained by the designer’s expertise. Recent advances in artificial intelligence, particularly large language models (LLMs), have demonstrated the potential to automate heuristic generation through evolutionary frameworks. Recent works focus only on well-known combinatorial optimization problems like the traveling salesman problem and online bin packing problem when designing constructive heuristics. This study investigates whether LLMs can effectively generate heuristics for niche, not yet broadly researched optimization problems, using the unit-load pre-marshalling problem as an example case. Building on the Evolution of Heuristics (EoH) framework, we introduce two prompt augmentation strategies: Contextual EoH (CEoH), which incorporates problem-specific descriptions to enhance in-context learning, and Literature-Based CEoH (LitCEoH), which integrates heuristic insights drawn from domain literature via a novel prompt design. We conduct extensive computational experiments comparing EoH, CEoH, and LitCEoH across a wide range of problem instances. Results show that CEoH and LitCEoH enable smaller LLMs to generate high-quality heuristics more consistently and even outperform larger models. Further, we find LitCEoH to improve scalability to diverse instance configurations. The code is available: https://github.com/nico-koltermann/LitCEoH (Zenodo upload: https://zenodo.org/records/15609821 ).