In the dial-a-ride problem, users formulate transportation requests between an origin and a destination. Transportation is carried out by a fleet of vehicles that provide a shared service. The problem is to design a set of minimum cost vehicle routes satisfying capacity, duration, time window, pairing, precedence and ride time constraints. We propose a mixed-integer programming formulation of the problem. We then describe a branch-and-cut approach that uses new valid inequalities for the problem as well as known valid inequalities for the TSP with precendence constraints and the VRP with time windows.

In the m-Peripatetic Salesman Problem (m-PSP) the aim is to determine m edge disjoint Hamiltonian cycles of minimum total cost on a graph. This presentation describes exact branch-and-cut solution procedures for the undirected m-PSP based on a 3-index formulation, a 2-index relaxation and a verification formulation.

We present a new branch-and-cut algorithm for the capacitated vehicle routing problem. The algorithm uses a variety of cutting planes, including capacity, framed capacity, strengthened comb, multistar, partial multistar, extended hypotour inequalities, and classical Gomory mixed-integer cuts. Computational results are presented which include new optimal solutions for three benchmark problems.