In order to plan and schedule a demand-responsive public transportation system, both temporal and spatial changes in demand should be taken into account even at the line planning stage. We study the multi-period line planning problem with integrated decisions regarding dynamic allocation of vehicles among the lines. Given the NP-hard nature of the line planning problem, the multi-period version is clearly difficult to solve for large public transit networks even with advanced solvers. It becomes necessary to develop algorithms that are capable of solving even the very-large instances in reasonable time. For instances which belong to real public transit networks, we present results of a heuristic local branching algorithm and an exact approach based on constraint propagation.

Abstract A rainbow cycle in an undirected edge‐colored graph is a cycle in which all edges have different colors. A rainbow cycle cover of a graph is a set of disjoint rainbow cycles, where each vertex belongs to exactly one cycle. The objective of the rainbow cycle cover problem is to minimize the number of rainbow cycles used to cover the vertices of the graph while the trivial cycle version also keeps the number of isolated vertices (called trivial rainbow cycles) at minimum. We present a branch‐and‐price procedure with column generation to solve both versions of the rainbow cycle cover problem. We compare our results with the literature in terms of computational performance. We also discuss two approaches to possibly improve the performance of the branch‐and‐price procedure.

We propose a new generic framework for solving combinatorial optimization problems that can be modeled as a set covering problem. The proposed algorithmic framework combines metaheuristics with exact algorithms through a guiding mechanism based on diversification and intensification decisions. After presenting this generic framework, we extensively demonstrate its application to the vehicle routing problem with time windows. We then conduct a thorough computational study on a set of well-known test problems, where we show that the proposed approach not only finds solutions that are very close to the best-known solutions reported in the literature, but also improves them. We finally set up an experimental design to analyze the effects of different parameters used in the proposed algorithm.

Abstract A typical network design problem consists of identifying a subnetwork of a given network that satisfies a set of constraints and minimizes the cost of flow. We consider degree‐constrained network design problems where we specify an upper limit on the number of arcs built at each node. We propose two lower bounding techniques using the concept of lower planes. The first lower bound is based on a known lower plane for network design problems; our second lower bound is stronger than the first, yet has the same polynomial computational complexity. We illustrate both lower bounds using a numerical example, test their performance, and present a real‐life case study from the area of railroad planning problems. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

Abstract Railroad planning involves solving two optimization problems: (i) the blocking problem, which determines what blocks to make and how to route traffic over these blocks; and (ii) the train schedule design problem, which determines train origins, destinations, and routes. Once the blocking plan and train schedule have been obtained, the next step is to determine which trains should carry which blocks. This problem, known as the block‐to‐train assignment problem, is considered in this paper. We provide two formulations for this problem: an arc‐based formulation and a path‐based formulation. The latter is generally smaller than the former, and it can better handle practical constraints. We also propose exact and heuristic algorithms based on the path‐based formulation. Our exact algorithm solves an integer programming formulation with CPLEX using both a priori generation and dynamic generation of paths. Our heuristic algorithms include a Lagrangian relaxation‐based method as well as a greedy construction method. We present computational results of our algorithms using the data provided by a major US railroad. We show that we can obtain an optimal solution of the block‐to‐train assignment problem within a few minutes of computational time, and can obtain heuristic solutions with 1–2% deviations from the optimal solutions within a few seconds. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008