David Pisinger

Miriam Enzi, Sophie N. Parragh, David Pisinger

Motivated by the change in mobility patterns, we present a scheduling approach for a vehicle-sharing problem, considering several alternative modes of transport, from a company viewpoint with centralized planning. We consider vehicle-sharing in a company having one or more depots and a fixed number of users, i.e. employees. The users have appointments with a fixed location and fixed start and end times. A vehicle must be used for a full trip of a user from depot to depot. We aim at assigning vehicles to user trips so as to maximize savings compared to other modes of transport. We first consider that only one type of vehicle is used, and second that multiple vehicle types can be used. For the first case, we show that the vehicle-sharing problem can be formulated as a minimum-cost flow problem. Secondly, if multiple types of vehicles are available the problem can be formulated as a multi-commodity flow problem. These formulations make the problem applicable in daily operations due to efficient solution methods. We provide a comprehensive computational study for both cases on instances based on demographic, spatial, and economic data of Vienna. We show that our formulations for this problem solve these instances in a few seconds, which makes them usable in an online booking system. In the analysis we discuss different potential settings. We study the optimal composition of a shared fleet, restricted sets of modes of transport, and variations of the objective function.

Miriam Enzi, Sophie N. Parragh, David Pisinger et al.

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 arc 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.

Henrik Reif Andersen, Tarik Hadzic, David Pisinger

In many AI domains such as product configuration, a user should interactively specify a solution that must satisfy a set of constraints. In such scenarios, offline compilation of feasible solutions into a tractable representation is an important approach to delivering efficient backtrack-free user interaction online. In particular,binary decision diagrams (BDDs) have been successfully used as a compilation target for product and service configuration. In this paper we discuss how to extend BDD-based configuration to scenarios involving cost functions which express user preferences. We first show that an efficient, robust and easy to implement extension is possible if the cost function is additive, and feasible solutions are represented using multi-valued decision diagrams (MDDs). We also discuss the effect on MDD size if the cost function is non-additive or if it is encoded explicitly into MDD. We then discuss interactive configuration in the presence of multiple cost functions. We prove that even in its simplest form, multiple-cost configuration is NP-hard in the input MDD. However, for solving two-cost configuration we develop a pseudo-polynomial scheme and a fully polynomial approximation scheme. The applicability of our approach is demonstrated through experiments over real-world configuration models and product-catalogue datasets. Response times are generally within a fraction of a second even for very large instances.