Add to Chrome
Add to Firefox
Add to EdgeMatthias Prandtstetter
Modeling and solving the multimodal car- and ride-sharing problem
Jan 15, 2020
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.
A Resource Allocation based Approach for Corporate Mobility as a Service
Oct 11, 2018
Corporate mobility is often based on fixed assignments of vehicles to employees. Relaxing these fixed assignments while including alternatives such as public transportation, bike sharing, and taxis for the employees' business and private trips could increase fleet utilization, foster the use of battery electric vehicles, and lower the costs for the companies' transportation needs. A system in which all employees specify their mobility demands gives rise to optimization problems concerning the assignment of company cars or alternative modes of transport to satisfy the needs of the users. In this work we introduce the NP-hard mobility offer allocation problem which has similarities to interval scheduling problems. We propose an integer linear programming model and heuristic solution approaches based on large neighborhood search. The efficiency of these methods is based on the usage of suitable conflict graphs. In a computational study, the approaches are evaluated and it is demonstrated that, depending on instances and run-time requirements, either solving the model exactly using a general purpose integer linear programming solver, fast greedy heuristics, or the adaptive large neighborhood search outperforms the others.