This paper presents a new graph theoretic framework for the passenger assignment problem that encompasses simultaneously the departure time and the route choice. The implicit FIFO access to transit lines is taken into account by the concept of available capacity. This notion of flow priority has not been considered explicitly in previous models. A traffic equilibrium model is described and a computational procedure based on asymmetric boarding penalty functions is suggested.
We consider two approaches for solving the classical minimum vertex coloring problem—that is, the problem of coloring the vertices of a graph so that adjacent vertices have different colors and minimizing the number of used colors—namely, constraint programming and column generation. Constraint programming is able to solve very efficiently many of the benchmarks but suffers from a lack of effective bounding methods. On the contrary, column generation provides tight lower bounds by solving the fractional vertex coloring problem exploited in a branch-and-price algorithm, as already proposed in the literature. The column generation approach is here enhanced by using constraint programming to solve the pricing subproblem and to compute heuristic solutions. Moreover, new techniques are introduced to improve the performance of the column generation approach in solving both the linear relaxation and the integer problem. We report extensive computational results applied to the benchmark instances: we are able to prove optimality of 11 new instances and to improve the best-known lower bounds on 17 other instances. Moreover, we extend the solution approaches to a generalization of the problem known as the minimum vertex graph multicoloring problem, where a given number of colors has to be assigned to each vertex.