Modeling and solving the multimodal car- and ride-sharing problem
  We introduce the multimodal car- and ride-sharing problem (MMCRP), in which a
pool of cars is used to cover a set of ride requests, while uncovered requests
are assigned to other modes of transport (MOT). A car's route consists of one
or more trips. Each trip must have a specific but non-predetermined driver,
start in a depot and finish in a (possibly different) depot. Ride-sharing
between users is allowed, even when two rides do not have the same origin
and/or destination. A user has always the option of using other modes of
transport according to an individual list of preferences.
  The problem can be formulated as a vehicle scheduling problem. In order to
solve the problem, an auxiliary graph is constructed in which each trip
starting and ending in a depot, and covering possible ride-shares, is modeled
as an edge in a time-space graph. We propose a two-layer decomposition
algorithm based on column generation, where the master problem ensures that
each request can only be covered at most once, and the pricing problem
generates new promising routes by solving a kind of shortest path problem in a
time-space network. Computational experiments based on realistic instances are
reported. The benchmark instances are based on demographic, spatial, and
economic data of Vienna, Austria. We solve large instances with the column
generation based approach to near optimality in reasonable time, and we further
investigate various exact and heuristic pricing schemes.
