All types of underground mine access serve as permanent openings to transfer men and extracted material throughout the life of an operation. Development and operating costs are predominantly controlled by the haul road length. However, the most common method to design the main haul road is to rely on the empirical knowledge of skilled mine design experts. This is sufficient for simple mine layouts. However, determination of the optimum path without violating navigation constraints in complex underground networks may be challenging even for the leading design specialists. Therefore, a new methodology is required to obtain the optimal haul road path considering kinematic constraints like minimum turning radius and maximum grade. It is also important that the method can avoid structural defect zones (faults, joints) or any kind of undesired regions. This study aims to provide an algorithmic solution to this major design problem. Investigating the shortest path for a haul road using evolutionary optimization, a novel contribution was made in underground mine planning. Genetic algorithm was explored as an efficient alternative compared to the global optimizers due to its computational advantages. Another original contribution was the new mutation operators specifically developed for underground mining. They distinguish the algorithm from similar studies in other disciplines. The algorithm was confirmed to be superior compared to the human-made plans based on a case study that involves six real underground mines. Although global optimization provides the best path, exponential time solutions make it infeasible as the problem scale grows. The genetic algorithm provides a suboptimal path with no considerable loss in quality and yet ensures the constraints even for the large-scale underground operations. (C) 2019 Elsevier B.V. All rights reserved.