This thesis is motivated by a project with Deutsche Bahn focused on offer preparation in rail freight transport, where customers are presented with three train path options in response to a freight train request. The collaboration with DB Netz AG led to an investigation into the efficient computation of these paths, ensuring they are both "good" and "as different as possible." We approached this practical challenge using combinatorial optimization techniques. The thesis begins by outlining the practical aspects of our research collaboration, followed by a theoretical exploration divided into two parts. In Part I, we examine a dual pair of problems on directed graphs with two designated end-vertices. The Almost Disjoint Paths (ADP) problem seeks the maximum number of paths between the end-vertices, ensuring that any two share at most one arc. Conversely, the Separating by Forbidden Pairs (SFP) problem requires selecting the fewest arc pairs such that every path between the end-vertices includes both arcs of a chosen pair. We classify ADP as NP-complete and SFP as Sigma-2-P-complete. Part II addresses a simplified version of the practical project: the Fastest Path with Time Profiles and Waiting (FPTPW) problem. Here, we explore directed acyclic graphs with durations on arcs and time windows at vertices, aiming to find the fastest path from a source to a target vertex while adhering to time constraints. We introduce departure-
