Abstract

Abstract

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.

Keywords— transportation, car-sharing, ride-sharing, vehicle scheduling problem, column generation

1 Introduction

Studying the development of mobility during the last decades, one can easily observe that we are facing a strong wind of change. While some years ago the main developments were related to technological improvements, the introduction of e-mobility was a first step towards an ongoing kind of revolution. From there, a new understanding of mobility developed and we are now facing a future where “owning cars” is replaced by “being mobile”. Users preferably only specify cornerstones of their travel — such as origins and destinations, latest arrival times or preferable modes of transport (MOT) — and rely on an information system to provide an (optimal) assignment of modes of transport to their demands. This attitude is supported by mobility concepts like vehicle sharing (car and bike), easy access to mobility via mobility cards, and Mobility as a Service (Mulley, Nelson, & Wright, 2018). We observe these developments not only in the private sector but also in the area of corporate mobility. Increasingly, companies are trying to change their view on their corporate mobility by switching from individually assigned cars towards Mobility as a Service for their employees. Companies strive to have an overall green and sustainable profile and employees are aware of the importance to contribute to a greener world, even if their travel time of a trip might increase. Instead of supporting further developments in corporate mobility privileging a few selected users, we are aiming at providing sustainable corporate mobility concepts that ensure at least the same level of mobility, while increasing positive impacts (e.g., cost reduction, ecological sustainability, and employee satisfaction).

This work is part of an applied research project SEAMLESS (http://www.seamless-project.at), in which the project partners are implementing the discussed ideas including the supporting algorithms in their companies. The major goal of the project is the development of novel corporate mobility concepts aiming at providing mobility to the company (and its employees) instead of only providing cars. This includes the introduction of car pools that can be used by the employees on a smart assignment strategy. Additional modes of transport are incorporated like bikes, (public) bike- and car-sharing, public transport and users can co-ride with each other. Ride-sharing saves resources, such as cars and energy, it is considered to have a good environmental footprint and can solve congestion problems. Masoud and Jayakrishnan (2017) report that for private cars in the US with four seats, only around 1.7 seats are actually used on average. This number decreases to only 1.2 for work-based trips, which shows the underutilization of cars, especially company cars. The increasing number of empty seats in cars and an increasing number of users asking for rides, imply motivation to elaborate a sophisticated ride-sharing system. Furthermore, not only the sharing economy is increasing but also a combined and integrated use of various modes of transport. To avoid pollution and congestion problems, various cities give incentives to use (a combination of) ”greener” modes of transport (CIVITAS, 2020; Stadtentwicklung Wien, 2020). As transportation is one of the biggest producers of emissions (Commission, 2016), it is vital to consider sustainability aspects, shift to more sustainable modes and enhance the environmental footprint.

The package of mobility offers can be seen as an extended car pool. It is crucial to assign the right vehicle to the right mobility need — e.g., if someone is aiming to travel a short distance in the city, public transport is better suited than a conventionally driven minivan. In return, the minivan is the right choice if an employee has to transport some special equipment to a meeting at a location about 300 kilometers away. This implies that it is necessary to estimate the mobility demand, allowing the user to specify preferred modes of transport, and to determine the number (and types) of cars to be owned in the car pool as well as the mobility offers provided to the employees like mobility cards or access to public vehicle sharing systems. Although sharing reduces costs and environmental impact, the complexity in fleet management increases. This directly implies that computational support is necessary to be able to efficiently handle the fleet.

We study the multimodal car- and ride-sharing problem in a company having one or more offices from where the employees have to visit various customers during office hours (e.g., for business meetings). We consider a fixed and unique employee-to-meeting assignment and a fixed latest arrival time. This results in a fixed sequence of tasks (also referred to as trip) for every employee with several stops, starting and ending at predefined (but possibly different) depots. A pool of vehicles is provided to the employees (also referred to as users) who can jointly use them (car-sharing). Furthermore, up to two users may co-ride on specific legs or routes with each other (ride-sharing).

We model the trips as arcs in a directed acyclic graph. Vehicle routes consist of one or more trips, whereas the driver of these trips may change at the depot. Similar to the vehicle scheduling problem, the available vehicles cover the scheduled trips resulting in vehicle routes. As the pool of cars is restricted, only a subset of the trips will be covered by the shared vehicles. In order to cover all mobility requests in the best possible way, further MOTs such as bikes or public transport are used. If a trip is not covered by car, the cheapest other MOT will be used.

This paper and the project objectives focus on adapting future mobility considerations to a corporate setting. However, the results can easily be adapted for different closed groups with a predefined set of users, such as home communities, suburban areas, or simply a network of users with predefined locations where the cars must be picked-up at and returned to. Furthermore, the model can easily be adapted to bikes, segways, cargobikes, (electric) scooters, and other sharing offers.

As the problem is modeled as an extended vehicle scheduling problem (VSP) with multiple depots, we contribute to the body of this specific problem too. The VSP assigns a set of vehicles to a set of scheduled trips, such that costs are minimized and each trip is covered by exactly one vehicle (Baita, Pesenti, Ukovich, & Favaretto, 2000). There are three main differences between the vehicle scheduling problem and the MMCRP. First, in our case not all trips need to be covered. Second, the multi-depot VSP assumes that all vehicles return to their original depot. We allow for different, but predetermined, start and end points. Third, we have to avoid that users co-ride in parallel on different trips. Hence we add a tailored ride-sharing constraint to the model. The MMCRP can be transformed into a kind of vehicle scheduling problem by having infinite cost for all other modes of transport, forcing the solution to cover all trips and allowing for different start and end depots. The MMCRP can also be formulated as a VSP with profits, which only - related to the idea of the vehicle routing problem (VRP) with profits - covers trips that are profitable.

The contributions of this paper are as follows:

• We introduce the novel MMCRP derived from a real-world application, and formulate it as an extended

• We present a two-layer decomposition of the problem. In the first layer, trips starting and ending at

• Computational results confirm that large instances can be solved to near-optimality in reasonable time

The paper is organized as follows: First, in Section 2, we discuss related work focusing on car- and ride-sharing as well as the VSP. Then, we provide a detailed problem description of the MMCRP in Section 3. The solution approach and the auxiliary graph that is used in our algorithm are described in Section 4. Based on the auxiliary graph we present a direct formulation of the MMCRP in Section 4.1. In Section 4.2, we present a path formulation of the problem and show how its linear relaxation can be solved through delayed column generation in Section 4.3. In Section 4.4 we explain how the pricing problem can be solved through dynamic programming and propose various heuristics for improving the computational effort. Section 5 presents the computational experiments. The paper is concluded in Section 6 by summing up the achieved results, and proposing ideas for future research.

2 Related work

Recently, car- and ride-sharing have received considerable attention, and several variants of the problem have been studied. Mourad, Puchinger, and Chu (2019) provide a thorough overview on models and algorithms for optimizing shared mobility. In the following section, we review closely related problems, including car-sharing, ride-sharing, and the vehicle scheduling problem focusing on column generation based approaches.

2.1 Car-sharing

Car-sharing systems involve a pool of cars that are shared among a set of users, who are usually known in advance (in public car-sharing systems these would be subscribers, in our case employees). The MMCRP without ride-sharing reduces to a car-sharing problem. Jorge and Correia (2013) and Brandst¨atter et al. (2016) review car-sharing optimization problems in detail. Most optimization studies consider publicly available systems and focus on rather strategic problems. In our setting we consider a car-sharing system available to a closed community only and focus on planning the daily operations. Many studies focus on public car-sharing systems and tackle problems such as charging station placement (Boyacı, Zografos, & Geroliminis, 2015; Brandst¨atter, Kahr, & Leitner, 2017) or relocation of cars between stations (Boyacı et al., 2015; Kek, Cheu, & Chor, 2006). Latest works increasingly also tackle the operational characteristics of car-sharing systems such as the effect of temporal and spatial flexibility on the performance of one-way electric car-sharing systems

2020), or dynamic relocation policies (Repoux, Kaspi, Boyacı, & Geroliminis, 2019).

2.2 Ride-sharing

Ride-sharing describes co-riding of one or more users between an origin and a destination or sub-paths of it. This is also the main idea of the MMCRP, where we do not only exploit the various MOTs in the best possible way, but try to merge rides by allowing ride-sharing if it is beneficial. In the following we review some related studies addressing ride-sharing.

Dial-a-ride problems (DARP) or the closely related pick-up-and delivery problem (PDP) are often used to formulate ride-sharing activities (Hosni, Naoum-Sawaya, & Artail, 2014; Li, Krushinsky, Reijers, & Woensel,

2014; Qu & Bard, 2012). An exhaustive review of these problems can be found in Ho et al. (2018).

Masoud and Jayakrishnan (2017) propose a decomposition algorithm to solve a many-to-many ride-matching problem to optimality in a time-expanded network. Participants only provide the origin, destination and latest/earliest times, which is similar to our problem statement. In contrast to our problem, they strictly split riders and drivers. Huang, Zhang, Si, and Leung (2016) formulate a two-stage problem minimizing total cost for long-term car-pooling. Drivers are selected, passengers assigned, and for each driver a traveling salesman problem (TSP) is solved considering constraints regarding fairness and preferences. Bit-Monnot, Artigues, Huguet, and Killijian (2013) compute a driver’s and passenger’s individual paths including the mutual sub-path between two (to be determined and synchronized) points. Mutual trips are followed by their individual paths towards the driver’s and passenger’s destination. As in our work, they also include public transport and walking before/after ride-sharing, however the focus of the work is to determine the optimal pick-up and drop-off locations for requests.

A number of works study commuter trips (Baldacci, Maniezzo, & Mingozzi, 2004; Knapen et al., 2014; Regue, Masoud, & Recker, 2016), whereas we focus on trips during working hours from/to meetings with customers. Chen, Mes, Schutten, and Quint (2019) aim at minimizing the cost of commuters and business traffic of a company, which consists of the cost incurred from vehicle miles and the costs of penalizing the efficiency losses (arriving too late at meetings, waiting time for transfers, inconvenience and risk with transfers). A constructive heuristic based on savings in miles driven and cars used is introduced. The problem definition is closely related to ours, as not only commuting trips are considered but also business traffic, i.e., travels between meetings. Moreover, they also employ savings as a objective but only use a heuristic approach to solve the problem.

Contrary to other papers, we model our compact problem as a kind of vehicle scheduling problem defined on an acyclic time-space graph, where we do not model pick-ups and deliveries explicitly, but enumerate all possible ride-shares in an auxiliary graph which is used as input to the second stage model.

2.3 Vehicle scheduling problem

The VSP received increasing attention in the early 80s (Bodin & Golden, 1981; Bodin, Golden, Assad, & Ball, 1983), and is mainly applied to time-tabled trips of public transport or crew scheduling. In the following we give a short overview on recent works on the multi-depot variant of the problem (MDVSP) using column generation based approaches to solve it. Further works elaborate the idea of the MDVSP by introducing alternative-fuel vehicles (Adler & Mirchandani, 2016) or considering a heterogeneous fleet of vehicles (Guedes & Borenstein, 2015). An overview of basic vehicle scheduling models is given in Bunte and Kliewer (2009). The MMCRP can be seen as a MDVSP with profits. The literature on the VRP with profits or closely related Orienteering Problem is vast (Gunawan, Lau, & Vansteenwegen, 2016; Speranza, Archetti, & Vigo, 2014). We could not find any publications on the VSP with profits.

The MDVSP was proven to be NP-hard by Bertossi, Cararesi, and Gallo (1987). Column generation was first applied to the MDVSP by Ribeiro and Soumis (1994) and extended by Hadjar, Marcotte, and Soumis (2006) and Groiez, Desaulniers, Hadjar, and Marcotte (2013). Note that these algorithms focus on proven integer optimality of the entire problem, which is not the case in our work. Pepin, Desaulniers, Hertz, and Huisman (2008) compare five heuristic for the MDVSP and conclude that the column generation heuristic performs best assuming enough computational time is available and stability is required. Guedes, Lopes, Rohde, and Borenstein (2016) propose a simple and efficient heuristic approach for the MDVSP. The heuristic first applies state space

(2018) present a new inventory formulation for the MDVSP and a column generation based heuristic propos-

2018) is closely related to the MMCRP. The generalization of the MDVSP allows for slight modification of one trip scheduled time. Trips are multiplied, representing each trip for different starting times. The aim is to find a set of bus schedules that covers every trip exactly once by satisfying vehicle availability and minimize costs. The work introduces a two-phase matheuristic where column generation solving the linear relaxation is embedded in a diving heuristic to derive an integer solution. The sequence of trips is fixed in the first phase by the column generation approach and thereafter the copies of a trip are chosen using a mixed integer program.

Note that all of the above works use either variable fixing or rounding strategies in their approaches. We solve the linear relaxation to optimality by column generation and find the integer solution by solving the original model using the obtained columns. Furthermore, we do not tackle the standard VSP but a kind of MDVSP with profits in which only beneficial arcs are covered by a vehicle. The study by Oukil, Amor, Desrosiers, and Gueddari (2007) is structurally similar to ours, but having some important differences. Oukil et al. (2007) focus on the comparison of the standard and the stabilized column generation approach, and discuss the impact of different time horizons. Both, the stabilization of the column generation and different time horizons, are not subject to our study. They emphasize on the methodological contribution. We combine a theoretical and practical contribution and apply the standard column generation approach, extended by heuristic approaches, to solve the LP-relaxation. Moreover, the underlying graphs differ. As we model ride-sharing directly into the graph we have multiple possibilities to cover tasks and trips. Therefore, we have to make sure that a user is not driving in parallel. Moreover, we allow the vehicle routes to start and end in different depots, which is not the case in Oukil et al. (2007). Similar to Desfontaines and Desaulniers (2018), we work on a multi-graph in which copies of links represent the same connection at different times and, in our case also involving different ride-sharing activities.

3 Problem description

We study the multimodal car- and ride-sharing problem in a company having one or more offices from where the employees have to visit various customers during office hours (e.g., for business meetings). Assuming that a company operates different offices (also referred to as depots), an employee might work in any depot. We note that even though the cases where employees switch their work place are rather rare, we included them because they were mentioned by our company partners. Therefore, it is not necessary that the employee returns to the starting depot after her meeting with a customer. Each customer visit involves one specific employee. We consider fixed and unique employee-to-meeting assignments and a fixed latest arrival time. As we consider business meetings at the customer locations, we assume that even if the employee arrives earlier, the starting time of the meetings will not change. Knowing the fixed starting time of the meeting as well as the length of it, we can calculate in advance the earliest departure time of each ride and do not have to explicitly consider the time of the meeting. This results in a fixed sequence of tasks for every employee with several stops, starting and ending at predefined (but possibly different) depots. We call such a fixed sequence of nodes a trip.

The company operates a finite number of vehicles at each depot and provides possibilities to use other modes of transport such as public transport, bikes, taxis or walk. We assume no start-up cost is associated with vehicles, and depots must have a specific number of vehicles at the beginning and end of the day. With this we assume that we do not have to account for relocations of cars. The employee specifies which modes can be used, since e.g., a person without a driving license cannot be the driver of a car. Moreover, the cars are only interchanged at the depots. This restriction is given from the project partners as changing cars at customer locations would imply too much inconvenience and they reported limited acceptance for handing over cars during a trip. For example, as the meetings of different users are usually not at the same location and/or time, one would need additional meeting points and/or times for the hand-over of the car. Further we consider ride-sharing, which is allowed between users, even when two rides do not have the same origin and/or destination. Ride-sharing may at most involve one co-rider. For further details on users, trips and MOTs see Section 3.1. Ride-sharing is described in more detail in Section 3.2.

The MMCRP aims at determining the optimal MOT-assignment for each trip and to schedule the routes

of the cars, maximizing savings when using a car including ride-sharing compared to any other mobility type whilst ensuring that all customers are visited at the right time by the right employee. The cost for the savings calculations does not only include distance cost but also cost of time (as hourly wages of employees) in order to properly reflect the trade-off between fast (but expensive) and slow (but cheap) MOTs. The savings calculation is outlined in Section 3.3. A vehicle route depicts a route of a vehicle during the day encompassing one or more drivers, handing over the vehicle at a depot including possible ride-sharing activities. Note that for our problem it is sufficient to only explicitly model car routes, as we only schedule the trips for the limited resource (i.e., cars). The remaining trips are assigned to the cheapest other MOT a user is willing to choose. This relies on the realistic assumption that users will rationally choose the next cheapest possibility to travel, if a car is not available. For a better understanding of the problem, an illustrative example is given in Section 3.4.

3.1 Users, trips and modes of transport

We have u users and n tasks given. Each user p has a sequence of tasks ) that need to be covered. User p starts at depot and finishes at a (possibly different) depot according to the user’s wishes. A trip denotes the sequence of nodes of user p starting at and ending at . Each task associated with a latest arrival time and earliest departure time. As we assume a fixed starting time of the task (i.e., the latest arrival time) we also know the earliest departure time by adding the duration of the task to it. Doing so, we do not have to explicitly consider the duration. The driving time between two tasks () using mode of transport , while the cost is . We consider a set of modes of transport K = {car, walk, bike, public, taxi}. Every user of possible modes of transport that can be used. We assume that a pool of shared cars is available at depot at the beginning of the day,

and that

where the cars are parked and the trips start and end. Note that all start and end nodes of a trip connected to the depots d. The demand at the end of a day will typically reflect the forecasted cars needed at the depot on the following day. For the other mobility types (car, walk, bike, taxi), we assume that there is infinite capacity.

If a trip is started by a car, then the car should be used for the full trip. However, ride-sharing can take place between any two nodes of a trip driven by the car. If the co-riding user does not follow the driver for the full trip, then we assume that the cheapest other MOT is used for the rest of the trip. We assume that if a user does not use a car on her own or is not co-riding, then she will take the cheapest other MOT included in her set of MOTs in order to conduct her trip.

3.2 Ride-sharing

Employees can share a ride if it is beneficial. Usually this applies if meetings are visited together or different meetings are nearby or lie on the colleague’s trip. We distinguish between three ride-sharing types: (1) co-

Figure 1: Three examples of ride-sharing illustrated in a time-space network. User p = 1 is going from to = 2 is going from

riding users share the same origin and destination, (2) they have the same origin and distinct destinations or vice versa, (3) they have different origins and destinations. In the following some representative examples are provided.

Each user p has to cover a set of tasks ). We are considering ride-sharing between two users p = 1 and p = 2 on a leg between two tasks (), thus going from and another leg going from = 2. Although our framework can easily be generalized to multi-user ride-sharing, we only consider two user ride-sharing to ensure user satisfaction. By allowing multiple users to share a ride, a user might end up using a disproportional part of the time as a driver for others.

The simplest ride-sharing case occurs when users p = 1 and p = 2 have the same origin and destination, as shown in Figure 1(a). In this case both users can be served on the ride.

We can also have the case in which only the source or destination is shared. Starting with the case where the end destination is shared we have the case shown in Figure 1(b). In this case, user p = 1 has to drive from to pick up user p = 2, and then both drive to the shared end destination where Provided that all time limits are satisfied, the cost of the ride can be calculated as the sum of the individual legs. The case where the origin is shared is handled in a symmetric way. Obviously, this shared ride is only beneficial if the detour for p = 1 is not too large.

In general, both origin and destination can be distinct as illustrated in Figure 1(c). In this case user p = 1 has to drive from to pick up user p = 2, drive this user to her destination and then drive to her own destination . Provided that all time limits are satisfied, the cost of the ride can be calculated as the sum of the individual legs. Please note that the end destination of the driver () must always lie after an intermediate point (e.g., ) as we do not allow to change drivers on the trip.

3.3 Savings calculation

We calculate cost and travel time for each trip. In order to reach the best choice of MOT combination we aim to obtain savings when using a car including ride-sharing compared to any other mobility type rather than focusing on minimizing costs only. Saving is the sum over all savings of included tasks . We consider costs of subsequent tasks () and obtain the savings calculation by considering detouring for ride-sharing. Note that the obtained savings might also be negative. This will occur if the cheapest MOT for a trip is not the car.

In a first step let us compute the savings obtained when no ride-sharing between two subsequent tasks () is considered. The savings of tasks and its fixed successor can be calculated as the difference between cost of using the cheapest other MOT and cost of using the car , such that:

Next, let us assume two users p = 1 and p = 2 whereas ride-sharing is demanded between two tasks (i, j) of user ). We add detour costs to go to/from these tasks. We have to account for additional costs of going from the driver’s (to the starting point of the demanded ride-sharing well as additional cost from the ride-sharing drop-off point to the driver’s original task . This gives us an additional detouring cost between () as well as () for which we only take into account the cost of using the car. We do not change the fixed sequence of a user’s trip, however, we must keep track of whether ride-sharing is conducted between two trips in order to take into account additional detouring cost. Hence for not traversing the original link (and additionally save costs by allowing for ride-sharing between . Therefore, for each task including subsequent ride-sharing we compute the savings as follows:

assuming is its fixed successor and ride-sharing is employed for tasks () between the original sequence (). The saving of trip is then calculated as

In order to provide a more understandable overview, let us assume a trip = 1 considering three tasks to be visited, . The trip starts at and ends at . The user’s trip would then be - . The corresponding savings calculation for trip and without considering ride-sharing is as

In a next step, assume that user p = 1 takes a detour between in order to ride-share with user p = 2 between . Now the sequence would be whereas the fixed successors for our calculations do not change, as described above. We get the respective savings of the above presented trip . We make these calculations for every variant of trip representing all possible ride-sharing trips.

Please note that the same task can be on different trips and have different savings as they represent different rides. Moreover, for the cases where the driver share their origin and/or destination we do not account for all detouring cost such that = 0 and/or = 0, respectively.

car task depot work travel ride-share car cheapest other MOT

Figure 2: Examples without sharing as well as car- and ride-sharing. We have two offices (depots) and four users p = 1, p = 2, p = 3 and p = 4; tasks are denoted as . Background rectangles with lines depict duration of a meeting, dots mean the user is traveling. If the background is not colored, the user is traveling with the cheapest other MOT, purple depicts travel by car, yellow ride-sharing. The arrows illustrate the routes of the two cars.

3.4 Illustrative example

To better illustrate the problem, a possible schedule is shown in Figure 2. We have 4 users (p = 1,p = 2,p = 3,p = 4), 2 cars, and 2 depots (). Each user’s schedule is depicted by one horizontal line connecting depots d and meetings = 1 visits = 2 is assigned to p = 3 visits whilst returning in between to depot and lastly user p = 4 drives to tasks . Background rectangles with lines depict duration of a meeting, dots indicate the user is traveling. If the background is not colored, the user is traveling with the cheapest other MOT, purple denotes travel by car, yellow ride-sharing. The arrows illustrate the traveling of the two cars. Figure 2(a) shows a possible solution without sharing, Figure 2(b) gives an adapted solution with car- and ride-sharing. User p = 4 uses in both figures one car for the whole trip and does not share any rides. In Figure 2(a) the second car is used by user p = 1 for the whole trip. Differently in Figure 2(b) where one of the cars is handed over from user p = 2 to user p = 3 at depot . Furthermore, both drivers of the car take on user p = 1 for some legs of her required trip, shown in yellow. Otherwise, user p = 1 uses the cheapest other MOT.

4 Solution approach

In order to simplify the problem, we reformulate it using a time-space network, in which all possible ride-sharing trips are represented by arcs. We introduce a graph G(V, E), where vertices are given by their time-space coordinates (i.e., time and depot).

Figures 3(a) and (b) show the first step of the graph transformation. We start by modeling the depots d at the start and end of the planning horizon where all trips are connected to and cars are located, as well as denoting the start and end points of a trip , and user tasks depicted as . Solid lines denote trips, dotted ones indicate waiting arcs in the set denoting that the car is not moving. Hence, we start by considering all trips of all users starting at and ending at including tasks q through the whole planning horizon, which then start and end at depot d. In Figure 3(a) we show the starting point of the graph construction whereas user tasks are still in the graph. From this graph, we transform all connections (i.e., all trips) to the arcs as represented in Figure 3(b). As can be seen, we do not explicitly consider the tasks in the graph any more but save all relevant information on the arcs. For each user we enumerate all possible trips from the user’s start depot to the user’s end depot , including possible ride-sharing as described in Section 3. Figure 3(c) gives two possible ride-sharing trips. Figure 3(d) then shows the extension in the trip-based arc representation of Figure 3(a). As can be seen, this gives us multiple arcs between nodes each depicting a possible way how the trip can be conducted. Due to ride-sharing, the start time of two rides may be different even if they consider the same user p starting at the same depot a. A similar observation holds for the end times of two rides for user p.

Every possible trip including any number of co-ride possibilities (including 0) results in a tuple . Here we have that is the start depot of the ride trip depot of trip is the departure time at start depot is the arrival time at end depot saving of the ride, and is a list of visits covered, both for the driver and possible co-rider(s).

For every user be the set of nodes associated with p as driver of the car. Let the set of ride arcs be . The saving of a ride arc

If we assume that is the first possible time, and is the last possible time in the planning horizon,

then for every depot we construct nodes (). The set of nodes can now be defined as

Finally we need to introduce the set of waiting arcs. A waiting arc is inserted between nodes (V in the graph if they correspond to the same depot comes immediately after (i.e., no other

node (exist). Now, the set of arcs can be defined as

Due to the possibly exponential number of ride-sharing combinations, we can have an exponential number of arcs. However, in practice, the number of possible trips for each user p is quite limited.

Note that the problem is modeled as a kind of a vehicle scheduling problem with multiple depots. In the vehicle scheduling problem with multiple depots we have a set Z of trips. A trip z has an associated start time and end time . Two trips can be run in sequence (i.e., they are compatible) if there is sufficient time to get from . Moreover, we have multiple depots, each depot d having a capacity . Every trip has to be run by one vehicle, minimizing the driving costs. A major difference between the vehicle scheduling problem and the MMCRP is that in our case not all trips need to be covered. However,

Figure 3: Illustration of the auxiliary graph in a time-space network.

the vehicle scheduling problem can either be transformed into the MMCRP by having infinite cost for all other modes of transport, forcing the solution to cover all trips or we it can be seen as an extended vehicle scheduling problem with profits.

Complexity: As elaborated, the problem is modeled as a kind of a vehicle scheduling problem. Therefore, it is easy to show that the MMCRP is NP-hard if the number of depots is at least two. We prove the complexity by reduction from the vehicle scheduling problem with 2 depots which was proven to be NP-hard by Bertossi et al. (1987). Notice that, since the vehicle scheduling problem does not consider ride-sharing, the MMCRP with at least 2 depots is NP-hard even without ride-sharing.

4.1 Arc formulation

We first introduce a direct formulation of the MMCRP based on the auxiliary graph G = (V, E) presented in Section 3. For every node we have the set of outgoing arcs and ingoing arcs the set of intermediate nodes denotes all arcs e that cover task q, including co-riding visits. Q denotes the set of all tasks. Finally let denote the savings of arc e. The binary decision variable takes on value 1 if arc e is selected in the solution and 0 otherwise.

The objective (3) maximizes total savings over all arcs. Constraints (4) ensure flow conservation at inter-

mediate nodes . Constraints (5) and (6) ensure that there is a correct number of vehicles

start and end of the time horizon for each depot . Constraints (7) make sure that each task covered at most once. If a given task is not covered, the assigned user will reach the task using the cheapest other MOT.

The model has O(E) variables, and O(V + D) constraints. Hence it is polynomial in the size of the graph. However, the graph G = (V, E) may be large (exponential in the original input size) due to the number of possible co-rides.

Despite the compact arc formulation, but due to the size of the graph, we will see in the computational experiments that only relatively small problems can be solved using this model. We will therefore introduce a stronger but larger formulation based on a path formulation.

4.2 Path formulation

In order to introduce a path formulation of the MMCRP, we assume that all possible routes of all vehicles are enumerated in the set R. Each route must start in node () and finish in a node (), traversing arcs E in the auxiliary graph G = (V, E). The start and end depots d may be different.

Let be the savings of route calculated as the saving by using a car compared to the cheapest other MOT for all arcs on the respective route. Furthermore, let the binary matrix be 1 if route will service task q. Finally, let = 1 if route starts in depot = 1 if route ends in depot d and 0

otherwise. The values

beginning and end of the planning horizon. The binary decision variable takes on value 1 if route chosen, and 0 otherwise.

We can now formulate the MMCRP as follows:

The objective function (9) maximizes the sum of the savings of the selected routes. Constraints (10) make sure that each task is covered at most once. Constraints (11) make sure that exactly

leave depot d at the start of the planning horizon, and constraints (12) make sure that exactly

return to depot d at the end of the planning horizon. Since not all vehicles have to be used, we add the necessary dummy routes to the set R. Finally, constraints (13) define the decision variables to be binary.

4.3 Delayed column generation

Since the number of routes R in model (9)-(13) may be very large we solve its LP-relaxation through column generation.

The restricted master problem considers a subset of routes of all possible routes. In every

occur.

Let be the dual variable corresponding to task covering constraint (10), be the dual variable

corresponding to depot start-inventory constraint (11), and

end-inventory constraint (12). The reduced savings of a route starting at depot d and ending at depot d can be calculated as follows:

The function sums all savings covered by route subtracted by the dual variables

the dual variables

4.4 Pricing problem

The pricing problem generates new promising routes by finding a path with the maximum reduced savings in the time-space network G = (V, E). We find the path using a label setting algorithm.

The pricing problem is solved for each combination of start depot and end depot . Promising routes with positive reduced savings are added to the master problem until no more routes with positive reduced savings can be found.

4.4.1 Dynamic programming

We solve the pricing problem for every pair of start and end depot, using auxiliary graph G = (V, E). We use a label setting algorithm adapted to a DAG. For every node , we have an associated value denoting the path with the so far largest savings to v. Initially for all nodes except the source node, and gradually the value of is increased as paths with higher savings are encountered.

A dynamic program is solved for each pair of depots. However, for each start depot, the dynamic programming algorithm will actually solve the problem for all destination depots. So, we only need to call the dynamic programming algorithm |D| times, resulting in the overall time complexity solving all pricing problems.

Since we have one value for every node, the space complexity of the dynamic programming algorithm is O(|V |). This is clearly overshadowed by the size of the graph.

Notice that when the dynamic programming algorithm terminates we may have several distinct solutions ending at depot d, for different arrival times h. The algorithm may easily be modified to return all these distinct solutions.

4.4.2 Stopping criterion and columns added

In the basic pricing algorithm we run the pricing for each combination of depots such that the column with the most positive reduced savings is added. We denote this strategy as best. Alternatively, we also evaluate the following strategies: first, firstdep, and multiple. In first we stop as soon as a column with positive reduced savings has been found and add this column to the master problem. Again, in each iteration only one column is added. Next, we extend first for every depot combination, and we iterate until the first column with positive reduced savings is found for each combination and terminate thereafter. This means that, when considering two depots and combining each of them, we have at most 4 columns added in each iteration. This is denoted as firstdep. Lastly, in multiple we include all columns with positive reduced savings. Note that we also tried to restrict the number of columns added. However, we did not see a remarkable difference to the non-restricted case.

4.4.3 Heuristic pricing algorithm

Although the pricing problem is solvable in polynomial time in the size of the graph G = (V, E), the number of arcs E may be very large, and we will see in the computational experiments that the pricing problem takes up most of the solution time. We therefore introduce a number of heuristic pricing algorithms, namely statespace, heurprun and heurarcs. When employing one of the heuristic pricing strategies, we search for columns with positive reduced savings and afterwards finish with one of the exact pricing schemes.

statespace: In this method, we reduce the auxiliary graph by merging nodes with similar time in the

time-space graph. The time-horizon is discretized in intervals of 10 minutes. If two nodes, corresponding to the same depot, end up in the same time interval, they are merged. After the merging, there may be multiple arcs between each pair of nodes, so we select the arc with highest savings, and ignore the rest.

heurprun: In this method, we use an aggressive reduction of the graph, by only keeping the savings and

not the time. Hence, for every set of ride arcs we merge start and end times, , into one common artificial time for each user’s start and end depot that, to start with, we only keep track of the ride with largest savings for each user p.

heurarcs: In the original algorithm we construct an auxiliary graph G = (V, E) in which we may have

arcs with both positive and negative savings . Arcs having a negative saving will only be used if they can be combined with arcs having a positive saving. The heuristic pricing algorithm removes all arcs e with negative savings 0 before running the label setting algorithm. This reduces the size of the auxiliary graph.

5 Computational study

The algorithms are implemented in C/C++ and for the solution of the master problem CPLEX 12.6.2 together with Concert Technology 2.9 is used. Tests are carried out using one core of an Intel Xeon 2643 machine with 3.3 GHz and 16 GB RAM running Linux CentOS 6.5. The algorithms are tested on a number of generated instances of increasing size and complexity. Various pricing schemes are compared, and the efficiency of all parts of the code is evaluated. Most of the reported computation times include the generation of the auxiliary graph. The exception is the comparison of the arc formulation to the column generation approach, where only the time to solve the models is stated.

To start the column generation we provide an initial set of dummy columns by inserting route variables such that the master problem is feasible without considering any valid route construction. These dummy variables are leaving and entering a depot (constraints (11)-(12)), but do not cover any tasks. We first solve the linear relaxation of the master problem and thereafter we solve the restricted master problem to integer optimality, using only routes generated in , containing a subset of all routes R with positive reduced savings. In this way we get an upper bound from the column generation based approach, and a lower bound from solving the IP model. Although we cannot guarantee an optimal solution to the original MMCRP in this way, the results will show that in most cases the gap is very small, and the solution quality is more than sufficient for practical applications.

In the following, we first introduce the test instances in Section 5.1. In Section 5.2 we compare the pricing schemes introduced in Section 4.4 and afterwards conduct algorithmic tests in Section 5.3. Finally, we discuss socio-economic aspects in Section 5.4. For a better understanding of the problem we provide a sample solution in the Appendix A.

We show in our results that the column generation approach is an efficient choice to solve the MMCRP. We can solve the biggest instances with 300 users and 40 vehicles within less than one hour on average. Pricing strategy multiple turns out to be the most efficient of the exact methods. The heuristic approaches (statespace, heurprun, heurarcs) do not come with a significant improvement in solution time or quality. Finally, we compare our results to those of the direct formulation presented in Section 4.1.

5.1 Test instances

We generate realistic benchmark instances based on available demographic, spatial and economic data of the city of Vienna, Austria. Five different MOTs are considered: car, walk, bike, public transport, and taxi. Walk, bike, public transport, and taxi are assumed to have an unrestricted capacity there is a limited number of shared cars. For each mode of transport we define a set of properties, described in the following. Information of the car is based on available data (PKW-Mittel Diesel in Beermann et al. (2010)). Distance are calculated between all nodes i and j for all modes of transport . Average travel speed per transport mode are as follows (in km/h): car = 30, walk = 5, bike = 16, public transport = 20, taxi = 30.

into the overall cost calculations. Costs per emitted ton of COand average gross salary in Austria including additional costs for the employer is 19.42e/hour. Variable cost per distance of the car is taken from the available car information in Beermann et al. (2010) and is 0.188e/km. For taxi we take on a value of 1.2e/km. As we only consider distance cost that are variable and no fixed charges, we assume for all other MOTs costs of 0. Additional time is added to denote extra time needed for a certain MOT k, such as additional 10 minutes for cars to account for walking distances from/to the parking lot. This we specify as follows (in seconds): = 300. Distances are based on aerial distances and multiplied by a constant sloping factor for each mode k in order to account for shortcuts/detours usually associated with certain modes of transport. These we define as

Each generated instance represents a distinct company consisting of one or more depots and users, i.e., employees, . The locations of the depots are based on statistical data of office locations in Vienna. The set of possible locations is based on geometric centers of all 250 registration districts of Vienna.

Companies are defined by a fixed number of users u and depots |D|. The number of customer visits, i.e.,

meetings, and their time and location, are then randomly generated based on historic statistical data.

To each user p we associate a subset of MOTs . We assume penalties for constraint violations such as choosing a mode of transport that is not in the user’s choice or for too late arrival. The penalty cost per violation is determined to be 10,000 and directly included into the cost function.

For our calculations, we depict one day only. Each user p has an assigned set of tasks distributed over the day. For the smallest instances on average 95 nodes (comprising meetings/tasks q and start and end depots a, b) and 33 tasks are generated. For the largest instances we have on average 463 tasks. Further information is given in Section 5.4 in Table 7. This leads to about 4-5 assigned nodes per user (including their start and end depots of the trips). The ordered list of tasks for a working day per user p is generated with the following attributes for each task q: latest arrival, earliest departure, service duration, all given in minutes. We already account for ride-sharing in the instance generation where we enforce the proximity of various tasks of different users. First, a predefined sequence of tasks is generated per user p which is then partitioned into separate sets of tasks with newly assigned artificial user if a user returns to the depot more than once during a day. If a user p has more than one simple trip, buffer time at the depot is set to 60 minutes in order to account for, e.g., changing of cars or additional time needed if the previous route was

Instances are named as E

and 9. For example, the first instance in the set of instances with 20 users (u = 20) is denoted E

each combination of u and m we solve a set of 10 instances (E

5.2 Comparison of the different pricing schemes

In this part, we compare different pricing schemes and study heuristic pricing algorithms. We compare four different variants of how and when to add columns to the master problem (described in Section 4.4.2) and three heuristic approaches, as described in Section 4.4.3. We provide insights into different parts of the algorithm and finally choose the variants having the best trade-off between solution time and solution quality. We compare results based on an increasing number of users u = 20, 50, 100, 150, 200, 250, 300 and vehicles m = 2, 4, 10, 20, 40. In our experiments the number of depots is two except for Table 6 where we study instances with more depots. The vehicles are equally split over all depots.

To start with, we study the solution time and solution quality of the different exact pricing schemes described in Section 4.4.2. Notice that all pricing schemes return the same LP-bound, but the IP-solution may be different because a different set of columns may be generated.

In Table 1 we report computational times in seconds and the average gap in percentages between the integer and LP solution for the respective set of instances. The gap between the two solutions is calculated as: (Savings LPSavings IP)/Savings IP. We split the table into combinations of pricing scheme (best, first, firstdep, multiple), number of vehicles (m = 2, 4, 10, 20, 40) and users (u = 150, 200, 250). Note that for multiple we add a row for u = 300 as this is the only exact scheme that was able to solve all instances within the stated time limit of two hours. As it may be seen, we are able to find near optimal solutions with a gap close to 0. For the case with m = 2, which means one vehicle for each depot, we can close the gap for all instances given in the table. The gap increases slightly when more vehicles are added, however only up to a certain point. For instances with more cars (m = 10, 20, 40) we cannot see a significant difference in the gap anymore. All approaches return solutions of approximately equally good quality. However, strategy multiple gives slightly better gaps than the other schemes. In schemes best, first, and firstdep only a very restricted subset of columns is added to the problem in each iteration. However, they might not be the most beneficial for the integer solution. With multiple we add all found columns with positive reduced savings which helps us to identify an integer solution. Given this situation and also for practical reasons, we decided to refrain from implementing a full fledged branch-and-price algorithm. In terms of computational time, for instances with a small number of cars (m = 2, 4) and up to 150 users (u = 150) it does not make a difference which scheme is used. By increasing the number of users and keeping a small fleet we can gradually see a difference. Pricing scheme best performs worst and pricing scheme multiple is, by far, the most efficient in terms of computation time. For the largest comparable instance which can be solved by all schemes (m = 40 and u = 250), computation times differ by a factor of 7: the average run time of pricing scheme multiple amounts to 843 seconds and to 6,145 seconds with pricing scheme best. The biggest instances (u = 300, m = 40) can be solved within less than one hour on average. We can observe in our computational results that the time spent on solving the master problem is usually very small, below three minutes on average, with the exception of instance class u = 100 and m = 10, where we obtain an average value of 1,296 seconds, using pricing scheme first. Most of the computation time is spent on solving the pricing problem. Observing this, we try to decrease computation times by studying three different heuristics to accelerate pricing, namely heurarcs, heurprun, statespace (see Section 4.4.3).

All heuristic approaches use pricing scheme multiple as it turned out to be the most efficient of the introduced exact pricing algorithms. The heuristic pricing schemes are employed as follows: We use the heuristic as long as columns with positive reduced savings can be found. Thereafter, we continue with the chosen exact pricing procedure.

Table 2 gives the average gap between the upper bound and solving the original IP on the same set of columns, and the average computation times in seconds for the heuristic pricing schemes heurarcs, heurprun, statespace, and scheme multiple for the larger instance classes defined by u = 150, 200, 250, 300 and m = 2, 4, 10, 20, 40. We see for all schemes a gap below 1%, and similar computational times. Thus, none of the presented schemes significantly stands out in terms of running times or solution quality.

In Table 3, we present the total number of columns generated when running the respective pricing algorithm over all instances with m = 2, 4, 10, 20, 40. We observe that, as expected, by only adding one column in each iteration (best, first) and one for each depot combination (firstdep) we generate fewer columns than with scheme multiple, which adds all columns with positive reduced savings.

Table 1: Average computation time in seconds and average gap in percentages (%) between the LP solution and the integer solution for the exact pricing schemes for an increasing number of users (u) and vehicles (m). The gap is calculated as: (Savings LP Savings IP)/Savings IP.

Table 2: Average computation time in seconds and average gap in percentages (%) between the LP solution and the integer solution for the heuristic pricing schemes and scheme multiple for u = 150, 200, 250, 300 and an increasing number of vehicles m. The gap is calculated as (Savings LPSavings IP)/Savings IP and reported for increasing number of vehicles (m).

Table 3: Total number of columns generated by the different pricing schemes over all instance classes with a given number of vehicles (m).

The solutions gained when solving the arc formulation and the integer solutions obtained by the column generation algorithm are compared in Table 4. We run the arc formulation on a set of small instances (u = 20, 50, 100 and m = 4) already showing the benefits of the decomposition algorithm. In the first row (computation time (s)) the average computation times to solve the arc formulation (AF), and the column generation algorithm (CG) are given. The stated numbers encompass only the computation times in seconds to solve the respective formulation, thus the enumeration of the trips is excluded. We observe that for the smallest instances the arc formulation is faster. However, for the bigger instances (u = 50, 100), we need a multiple of the time of the column generation algorithm. The gap (gap (%)) between the solution of the arc formulation and the respective integer solution is very low, less than 0.11% for all instances on average. With the column generation approach we are able to solve 9 out of 10 instances of the respective instance

group to optimality (# opt.)

As we assumed and also show in Table 7, the number of arcs generated, and thus the underlying graph, becomes very large and therefore this formulation cannot be used efficiently in a direct formulation. Note that we also tried to run the arc formulation by increasing the relative MIP gap (e.g., to 1%). This, however, did not lead to any improvements as solving the root relaxation takes most of the computational time.

Table 4: Average time in seconds for solving the arc formulation and the column generation based algorithm, average gap in percentages between the solution of the arc formulation (AF) and integer solution of the column generation based algorithm (CG), and number of instances solved to optimality with the column generation based algorithm for instances with an increasing number of users u = 20, 50, 100 and number of vehicles m = 4.

5.3 Algorithmic tests

In the following we use configuration statespace to study how the column generation evolves, the impact of early termination of the column generation and different numbers of depots.

In terms of convergence of the algorithm, we observe the common picture of a steep increase in the objective value during the first iterations and then a long tail until optimality of the LP relaxation has been proven. This means that we are able to find good solutions close to the optimal objective function value in a relatively few iterations. However, the column generation then needs quite a number of iterations in order to find the optimal value. This effect can be exploited for practical applications: the column generation process can be terminated early without loosing much in terms of solution quality. Figures 4(a), (b), (c) and (d) in the Appendix B plot the convergence of the column generation algorithm. The number of iterations is shown on the x-axis and the objective function value on the y-axis. We report results for u = 150 users (a), u = 200 user (b), u = 250 users (c), and u = 300 users (d). Each curve represents the outcome of one instance.

In Table 5 the impact of early termination after about one third of the iterations on the quality of the obtained objective value is shown. As the number of iterations needed to find the optimal solution does not vary much between instances of different size, we assume a common termination criterion for all. Observing that usually about 140-160 iterations are needed to terminate the algorithm, we study early termination after 50 iterations and solve the integer problem on the columns generated so far. Table 5 gives the gap in percentages between the integer and LP solution for each instance with u = 300. The row ”time (s)” shows the average run time in seconds. We observe that we are still able to find good solutions after only one third of the iterations. The computed gap between the original upper bound and solving the IP on the restricted set of columns, using early termination, is at most 6.6% and 2.5% on average, which is good enough for practical applications. Since the algorithm is stopped after about one third of the previously necessary iterations, run times are reduced accordingly.

Table 5: Impact of early termination of the column generation algorithm after 50 iterations for u = 300 and m = 40. Comparison between original upper bound and obtained integer solution after early termination. Gap in percentages and time in seconds are given for the case of early termination (terminate) and the original values obtained from statespace.

In Table 6 we show the impact of increasing the number of depots on the run time of the algorithm. In all previous experiments, two depots were used. We now use 1, 3, and 4 depots. Within the project, the case of 1 depot is chosen as currently a company usually operates one main office (or at maximum two) with shared cars. However, as we are investigating the future sharing economy and different settings of companies we also analyse if our algorithm is capable of dealing with more depots. The number of vehicles is shown as the number of vehicles per depot to allow for a fair comparison. This means that, to obtain the actual total number of vehicles, this number must be multiplied by the number of depots. As expected, computation times increase with rising number of depots, however only to a certain factor and not exponentially. As the pricing algorithm is solved for each pair of depots we are increasing the number of subproblems the pricing algorithm is able to handle. However, as only a few trips start and end at different depots, we can provide reasonable solution times even for the case of four depots. In Table 6 the respective values are provided.

Table 6: Average computation times in seconds for 1, 2, 3 and 4 depots for users u = 20, 50, 100, 150, 200, 250, 300 and vehicle per depot (

5.4 Socio-economic tests

In this section, we summarize the results of our socio-economic tests. All results are obtained using the version of our algorithm with the smallest LP-IP gap, which is multiple. We study savings by ride-sharing, savings by car-sharing and give insights into the instances and strategic decisions regarding the optimal size of the car pool.

Table 7 gives the average number of all trips for each instance class and the average number of simple trips. Simple trips are the arcs without any ride-sharing activities going from start node a to end node b. As we can see, the number is always slightly higher than the number of users, indicating that a set of users return to the depot during the day and start another sequence of nodes in the observed planning horizon. Column ”tasks incl. start/end” gives the average number of nodes, i.e., tasks and start/end depots of a user’s trip, of the instance set. Each user covers about 4-5 nodes, each trip includes on average 3.3 nodes. The column ”tasks” gives the average number of tasks for each instance set. This number ranges from 33 (u = 20) to 463 (u = 250), which gives approximately 1-2 tasks per trip. In the last four columns we give the percentage of tasks and start/end depots covered by a car. Naturally, with a low number of cars (m = 4) and a high number of users (u = 250), only a small subset of tasks will be covered by car. The coverage ranges from 4% to 45%.

Table 7: Number of simple trips, number of all trips, and tasks in the auxiliary graph for an increasing number of users u. The columns on the right give the percentage of nodes including tasks, start and end depots, covered by car for m = 4, 8, 20, 40.

In Table 8, the results obtained from solving the MMCRP are compared to only car-sharing (ratio (1)) and user-dependent car assignment (ratio (2)). The value is given as the savings ratio of MMCRP : car-/ride-sharing.

User dependent car-assignment means that if a user has an assigned car, the selected user will have the car for the whole day and use it for all trips. Moreover, no other user is allowed to use this car and ride-sharing is not possible. If only car-sharing is employed users may hand over the cars during the planning horizon so that a car will have different drivers assigned, however, no ride-sharing is allowed. All tests are run for an increasing number of vehicles (m = 2, 4, 10, 20) and users (u = 20, 50). Instance specific results are reported and summed up in the row ”average”.

By allowing car- and ride-sharing and thus having a more flexible usage of the car pool rather than a restricted usage during a day, we can have up to 1.7 times higher savings in the planning horizon. This is already shown for small-sized instances. As expected, the more flexible the usage of the cars, the more

savings are achieved. Please note that instances E

meaning that these are not included in the average calculations as they would give a somewhat misleading outcome. This is due to the fact that we assumed penalties for constraint violations such as choosing a mode of transport that is not in the user’s choice or for too late arrival. The penalty cost per violation is determined to be 10,000 and directly included into the cost function. Therefore we obtain for some instances very high savings which is mainly due to these penalties included in the objective function. Note that we also excluded values for m = 20 and u = 20 as this setting means that more cars than users are provided.

Table 8: Increase in savings when comparing car-sharing (without ride-sharing), user-dependent car-sharing (i.e., car-sharing without ride-sharing and a user has a car for the whole day) and MMCRP. Ratio (1) reports the factor of improvement in savings in comparison to car-sharing, ratio (2) reports the enhancement when comparing to the user-dependent car-sharing.

When analyzing fleet size, we see initially big savings when adding more vehicles yet the impact diminishes quite fast. For instances with 20 users fewer than 5 vehicles suffice, for 50 users fewer than 10 are certainly enough and when we consider 100 users the breaking point is somewhere between 20 and 30. For larger instances (u = 150, 200, 250, 300), the ideal number of vehicles would be between 20 and 50. Figure 5 in the Appendix B provides illustrative insights into the optimal fleet size for an increasing number of users employed (u = 20, 50, 100, 150, 200, 250, 300). The x-axis represents number of vehicles, the y-axis the objective function value and each line represents a distinct instance of our experiments, whereas the thicker black line in each subfigure shows the average.

Finally, we analyse the average number of arcs and ride-shares in our results. Table 9 summarizes the average number of trips per vehicle route and average ride-sharing activities per arc (ride-sharing per ride). This is shown for the cases of 20 and 50 users and increasing number of vehicles (m = 2, 4, 10, 20 respectively). The average number of trips on a vehicle route gives us an idea of the amount of car-sharing activities. With an increasing number of cars the number of trips on a vehicle route is decreasing. The very small numbers, for example 0.9 for u = 20 and m = 10, are mainly due to unused arcs, meaning that not all of the available cars are used. Moreover, we have on average 1.5-1.7 ride-sharing activities per arc, which is considered to be very high and supports our goal of having a good utilization of the pool of cars. Note that we again exclude values for m = 20 and u = 20 as this setting would mean that more cars than users are provided.

Table 9: Average number of trips per car, and average number of ride-shares per trip

6 Conclusion

Inspired by the concept of sharing economy and future mobility systems, we introduced the multimodal carand ride-sharing problem (MMCRP) that assigns different modes of transport to ride requests. We aimed at deploying a pool of shared cars as efficiently as possible, join ride requests by offering ride-sharing and by assigning different modes of transport to the remaining requests.

We introduced the novel MMCRP and showed that the problem is NP-hard if the number of depots is at least two. The problem remains NP-hard even if ride-sharing is not allowed. In order to circumvent the complexity of modeling ride-shares and additionally assigning further modes of transport, we constructed an auxiliary graph in which all possible ride-sharing rides are enumerated. Ride requests not covered by a car or ride-share are appointed to take the cheapest other MOT. This made it possible to formulate a compact model for the problem as a kind of vehicle scheduling problem. We extend the vehicle sharing problem by allowing for different start and end depots. Moreover, due to the modeling of ride-sharing into the graph, we may have multiple possibilities to cover a trip and have to make sure that a user is not riding in parallel, i.e., that a user is not driving in multiple cars at the same time. Note that the auxiliary graph can be exponential in the original input size. Due to the size of the auxiliary graph, the compact model is also quite complex to solve, hence we proposed a path-based formulation. To solve the path-based formulation we introduced an efficient two-stage decomposition algorithm and relied on well-studied approaches to solve the real-world problem. In the first stage of the decomposition approach, trips were enumerated and afterwards, in the second stage, solved through a column generation approach. The master problem keeps track of the requests and depot balance constraints, while the pricing problem generates improving paths. We showed that the pricing problem can be solved through dynamic programming in polynomial time, measured in the size of the auxiliary graph. The computational results confirmed that large instances can be solved in reasonable time, making it possible to use the algorithm for daily planning of multimodal car- and ride-sharing problems even in a large-scale setup. The two-level decomposition makes it easy to implement additional constraints on co-riding to make it more attractive: This could be limits on detour or driving time, or co-rider preferences. Also the framework can easily be generalized to handle more than one co-rider, which should also be done in future work.

The introduced model targets corporate mobility services. However, it can easily be applied to any

specific network with a predefined set of users in a closed community and is therefore of high importance in current and future concepts of shared mobility systems. Moreover, the MMCRP can be extended to electric cars, where the algorithm must ensure that sufficient time is available at the depot for recharging the cars. Furthermore, the model can be extended to consider several shared modes of transport. This could be electric as well as conventional cars and bikes that are pooled to satisfy the needs of transportation for one or more companies. Bikes might need to be embedded in a rebalancing system, ensuring that the right number of bikes is at the right locations at the beginning and end of the day. Bikes can thus be implemented in a unified model with other shared MOTs considering specific limitations as they cannot be available for ride-sharing. However, as we are considering urban mobility, we can assume that there are shared bikes provided from different independent providers, and therefore this mode of transport is always available for the users and the company does not have to plan the rebalancing on their own. Furthermore, the current model is restricted to a predetermined fixed sequence of tasks. This was considered as given from our practical partners. However, this restricts the model and prevents possible further savings that might benefit from this flexibility. Moreover, the model might profit from allowing changes of drivers on a trip. We note that this restriction was introduced based on information from our industry partners. They reported that there was very limited acceptance for handing over cars during a trip. However, in our future work we plan to address this aspect as well as more flexibility in the timing of user tasks. Lastly, another interesting aspect could be the consideration of uncertain and varying travel times. While time-dependent travel times would not require major changes to our approach, since we already work on a time expanded network, the consideration of uncertainty would require major changes in the design of the solution approach. Furthermore, an unexpected delay of the driver at any point would affect any later co-rider on the route, requiring changes in the schedule during the day, which should also be addressed in future work.

Acknowledgements

This work was supported by the Climate and Energy Funds (KliEn) [grant number 853767]; and the Austrian Science Fund (FWF): P 31366.

References

Adler, J., & Mirchandani, P. (2016, 03). The vehicle scheduling problem for fleets with alternative-fuel vehicles. Transportation Science, 51. doi: 10.1287/trsc.2015.0615

Baita, F., Pesenti, R., Ukovich, W., & Favaretto, D. (2000, 11). A comparison of different solution approaches to the vehicle scheduling problem in a practical case. Computers & Operations Research, 27, 1249-1269. doi: 10.1016/S0305-0548(99)00073-8

Baldacci, R., Maniezzo, V., & Mingozzi, A. (2004). An exact method for the car pooling problem based on lagrangean column generation. Operations Research, 52(3), 422–439. doi: 10.1287/opre.1030.0106

Beermann, M., Jungmeier, G., Wenzel, A., Spitzer, J., Canella, L., Engel, A., . . . Koller, S. (2010). Quo vadis elektroauto? grundlagen einer road map f¨ur die einf¨uhrung von elektro-fahrzeugen in ¨Osterreich (research report No. Project number: IEF.2008.GF.001-01). Graz, Asutria.

Bergmann, F. M., Wagner, S. M., & Winkenbach, M. (2020). Integrating first-mile pickup and last-mile delivery on shared vehicle routes for efficient urban e-commerce distribution. Transportation Research Part B: Methodological, 131, 26 - 62. Retrieved from http://www.sciencedirect.com/science/article/pii/S0191261518310166 doi: https://doi.org/ 10.1016/j.trb.2019.09.013

Bertossi, A., Cararesi, P., & Gallo, G. (1987). On some matching problems arising in vehicle scheduling problems. Networks, 271–281.

Bit-Monnot, A., Artigues, C., Huguet, M.-J., & Killijian, M.-O. (2013). Carpooling: the 2 synchroniza- tion points shortest paths problem. In 13th workshop on algorithmic approaches for transportation modelling, optimization, and systems (atmos).

Bodin, L., & Golden, B. (1981). Classification in vehicle routing and scheduling. Networks, 11(2), 97-108. doi: 10.1002/net.3230110204

Bodin, L., Golden, B., Assad, A., & Ball, M. (1983, 6). Routing and scheduling of vehicles and crews - the state of the art. In (Vol. 10, p. 63-212). Computers and Opertions Research.

Boyacı, B., & Zografos, K. G. (2019). Investigating the effect of temporal and spatial flexibility on the performance of one-way electric carsharing systems. Transportation Research Part B: Methodological, 129, 244 - 272. doi: https://doi.org/10.1016/j.trb.2019.09.003

Boyacı, B., Zografos, K. G., & Geroliminis, N. (2015). An optimization framework for the development of efficient one-way car-sharing systems. European Journal of Operational Research, 240(3), 718 - 733. doi: https://doi.org/10.1016/j.ejor.2014.07.020

Brandst¨atter, G., Gambella, C., Leitner, M., Malaguti, E., Masini, F., Puchinger, J., . . . Vigo, D. (2016, 09). Overview of optimization problems in electric car-sharing system design and management. In (Vol. 22, p. 441-471). doi: 10.1007/978-3-319-39120-5

Brandst¨atter, G., Kahr, M., & Leitner, M. (2017). Determining optimal locations for charging stations of electric car-sharing systems under stochastic demand. Transportation Research Part B: Methodological, 104, 17 - 35. doi: https://doi.org/10.1016/j.trb.2017.06.009

Bunte, S., & Kliewer, N. (2009, Nov 01). An overview on vehicle scheduling models. Public Transport, 1(4), 299–317. doi: 10.1007/s12469-010-0018-5

Chen, W., Mes, M., Schutten, M., & Quint, J. (2019). A ride-sharing problem with meeting points and return restrictions. Transportation Science, 53(2), 401-426. doi: 10.1287/trsc.2018.0832

CIVITAS. (2020). Eccentric. (https://civitas.eu/eccentric, Last accessed on 2020-05-27)

Commission, E. (2016). Transport Emissions - A European Strategy for low-emission mobility. https://ec.europa.eu/clima/policies/transport

Cort´es, C. E., Matamala, M., & Contardo, C. (2010). The pickup and delivery problem with transfers: For- mulation and a branch-and-cut solution method. European Journal of Operational Research, 200(3), 711 - 724. doi: https://doi.org/10.1016/j.ejor.2009.01.022

Desfontaines, L., & Desaulniers, G. (2018). Multiple depot vehicle scheduling with controlled trip shifting. Transportation Research Part B: Methodological, 113, 34 - 53. doi: https://doi.org/10.1016/j.trb.2018 .05.011

Groiez, M., Desaulniers, G., Hadjar, A., & Marcotte, O. (2013, Nov 01). Separating valid odd-cycle and odd- set inequalities for the multiple depot vehicle scheduling problem. EURO Journal on Computational Optimization, 1(3), 283–312. doi: 10.1007/s13675-013-0012-1

Guedes, P. C., & Borenstein, D. (2015). Column generation based heuristic framework for the multiple- depot vehicle type scheduling problem. Computers & Industrial Engineering, 90, 361 - 370. doi: https://doi.org/10.1016/j.cie.2015.10.004

Guedes, P. C., Lopes, W. P., Rohde, L. R., & Borenstein, D. (2016). Simple and efficient heuristic approach for the multiple-depot vehicle scheduling problem. Optimization Letters, 10(7), 1449-1461. doi: 10 .1007/s11590-015-0944-x

Gunawan, A., Lau, H. C., & Vansteenwegen, P. (2016). Orienteering problem: A survey of recent variants, solution approaches and applications. European Journal of Operational Research, 255(2), 315 - 332. doi: https://doi.org/10.1016/j.ejor.2016.04.059

Hadjar, A., Marcotte, O., & Soumis, F. (2006). A branch-and-cut algorithm for the multiple depot vehicle scheduling problem. Operations Research, 54(1), 130-149. doi: 10.1287/opre.1050.0240

Ho, S. C., Szeto, W., Kuo, Y.-H., Leung, J. M., Petering, M., & Tou, T. W. (2018). A survey of dial-a-ride problems: Literature review and recent developments. Transportation Research Part B: Methodological, 111, 395 - 421.

Hosni, H., Naoum-Sawaya, J., & Artail, H. (2014). The shared-taxi problem: Formulation and solution methods. Transportation Research Part B: Methodological, 70, 303 - 318. doi: https://doi.org/10.1016/ j.trb.2014.09.011

Huang, C., Zhang, D., Si, Y.-W., & Leung, S. C. H. (2016). Tabu search for the real-world carpooling problem. Journal of Combinatorial Optimization, 32(2), 492–512. doi: 10.1007/s10878-016-0015-y

Jorge, D., & Correia, G. H. d. A. (2013). Carsharing systems demand estimation and defined operations: A literature review. European Journal of Transport and Infrastructure Research, 13, 201-220.

Kek, A. G. H., Cheu, R. L., & Chor, M. L. (2006). Relocation simulation model for multiplestation shared-use vehicle systems. Transportation Research Record, 1986(1), 81-88. doi: 10.1177/ 0361198106198600111

Knapen, L., Yasar, A., Cho, S., Keren, D., Dbai, A. A., Bellemans, T., . . . Bhaduri, K. (2014). Exploiting graph-theoretic tools for matching in carpooling applications. Journal of Ambient Intelligence and Humanized Computing, 5(3), 393–407. doi: 10.1007/s12652-013-0197-4

Kulkarni, S., Krishnamoorthy, M., Ranade, A., Ernst, A. T., & Patil, R. (2018). A new formulation and a column generation-based heuristic for the multiple depot vehicle scheduling problem. Transportation Research Part B: Methodological, 118, 457 - 487. doi: https://doi.org/10.1016/j.trb.2018.11.007

Li, B., Krushinsky, D., Reijers, H. A., & Woensel, T. V. (2014). The share-a-ride problem: People and parcels sharing taxis. European Journal of Operational Research, 238(1), 31 - 40. doi: https://doi.org/ 10.1016/j.ejor.2014.03.003

Masoud, N., & Jayakrishnan, R. (2017). A decomposition algorithm to solve the multi-hop peer-to-peer ride-matching problem. Transportation Research Part B: Methodological, 99, 1–29. doi: 10.1016/ j.trb.2017.01.004

Masson, R., Lehu´ed´e, F., & P´eton, O. (2014). The dial-a-ride problem with transfers. Computers & Operations Research, 41, 12 - 23. doi: https://doi.org/10.1016/j.cor.2013.07.020

Mourad, A., Puchinger, J., & Chu, C. (2019). A survey of models and algorithms for optimizing shared mobility. Transportation Research Part B: Methodological, 123, 323 - 346. doi: https://doi.org/ 10.1016/j.trb.2019.02.003

Mulley, C., Nelson, J. D., & Wright, S. (2018). Community transport meets mobility as a service: On the road to a new a flexible future. Research in Transportation Economics. doi: https://doi.org/10.1016/ j.retrec.2018.02.004

Oukil, A., Amor, H. B., Desrosiers, J., & Gueddari, H. E. (2007). Stabilized column generation for highly degenerate multiple-depot vehicle scheduling problems. Computers & Operations Research, 34(3), 817 - 834. Retrieved from http://www.sciencedirect.com/science/article/pii/S0305054805001590 (Logistics of Health Care Management) doi: https://doi.org/10.1016/j.cor.2005.05.011

Pepin, A.-S., Desaulniers, G., Hertz, A., & Huisman, D. (2008, Jul 12). A comparison of five heuristics for the multiple depot vehicle scheduling problem. Journal of Scheduling, 12(1), 17. doi: 10.1007/ s10951-008-0072-x

Qu, Y., & Bard, J. F. (2012). A grasp with adaptive large neighborhood search for pickup and delivery problems with transshipment. Computers & Operations Research, 39(10), 2439 - 2456. doi: https:// doi.org/10.1016/j.cor.2011.11.016

Regue, R., Masoud, N., & Recker, W. (2016). Car2work. Transportation Research Record: Journal of the Transportation Research Board, 2542, 102–110. doi: 10.3141/2542-12

Repoux, M., Kaspi, M., Boyacı, B., & Geroliminis, N. (2019). Dynamic prediction-based relocation policies in one-way station-based carsharing systems with complete journey reservations. Transportation Research Part B: Methodological, 130, 82 - 104. doi: https://doi.org/10.1016/j.trb.2019.10.004

Ribeiro, C. C., & Soumis, F. (1994). A column generation approach to the multiple-depot vehicle scheduling problem. Operations Research, 42(1), 41-52. doi: 10.1287/opre.42.1.41

Speranza, M., Archetti, C., & Vigo, D. (2014, 11). Chapter 10: Vehicle routing problems with profits.. doi: 10.1137/1.9781611973594.ch10

Stadtentwicklung Wien. (2020). Step2025 stadtentwicklungsplan wien. (https://www.wien.gv.at/stadtentwicklung/studien/pdf/b008379a.pdf, Last accessed on 2020-05-27)

Modeling and solving the multimodal car- and ride-sharing problem

2020·Arxiv