Open Access 14092021  Original Article
The biobjective multimodal carsharing problem
Published in: OR Spectrum  Issue 2/2022
Abstract
The aim of the biobjective multimodal carsharing problem (BiOMMCP) is to determine the optimal mode of transport assignment for trips and to schedule the routes of available cars and users whilst minimizing cost and maximizing user satisfaction. We investigate the BiOMMCP from a usercentred point of view. As user satisfaction is a crucial aspect in shared mobility systems, we consider user preferences in a second objective. Users may choose and rank their preferred modes of transport for different times of the day. In this way, we account for, e.g., different traffic conditions throughout the planning horizon. We study different variants of the problem. In the base problem, the sequence of tasks a user has to fulfil is fixed in advance and travel times as well as preferences are constant over the planning horizon. In variant 2, timedependent travel times and preferences are introduced. In variant 3, we examine the challenges when allowing additional routing decisions. Variant 4 integrates variants 2 and 3. For this last variant, we develop a branchandcut algorithm which is embedded in two biobjective frameworks, namely the \(\epsilon \)constraint method and a weighting binary search method. Computational experiments show that the branchand cut algorithm outperforms the MIP formulation and we discuss changing solutions along the Pareto frontier.
1 Introduction
Today, most of the world’s population lives in urban environments and cities continue to grow (United NationsDepartment of Economic and Social Affairs 2018). Urban mobility is therefore a key topic for a sustainable future. When considering a city’s infrastructure, the available mobility offers are plentiful. Public transportation provides efficient connections; some commuters use their car; others prefer bikes, scooters or even taxi. Besides, a trend towards sharing is clearly visible in mobility (DriveNow, Uber, etc.). In short, mobility as we use it and see it is changing. This comes with a whole new stream of optimization problems. Only recently, Mourad et al. (2019) provided a survey on the vast topic of optimizing shared mobility.
The (privately owned) car is diminishing as the prevailing mode of transport in urban areas (VCÖ  Mobilität der Zukunft 2020). In Vienna (Austria), the number of cars per capita is constantly decreasing (Martin 2020; Statistik Wien 2020). People prefer other modes of transport (MOT). The modal split of cars shrank from 31% to 25% within the last decade. Within the same time period, bikes, public transportation and walking increased their modal split by 2 percentage points to 7%, 38% and 30%, respectively (Wiener 2010, 2019). Thus, people move to alternative, more environmentally friendly MOTs.
Advertisement
Additionally, citizens increasingly use sharing systems (VCÖ  Mobilität der Zukunft 2020). In Germany, the number of shared cars has increased fivefold within ten years; there are almost twelve times more users than a decade ago (Bundesverband CarSharing eV 2020). In Vienna (Austria), one shared car eliminates the need of five privately owned ones (MA 18  Stadtentwicklung und Stadtplanung Wien 2015). At maximum 10% of the cars in Austrian households simultaneously drive on the roads. Many car owners use their vehicles only a couple of times per year. In Lisbon (Portugal), only 3% of the cars will be needed if all trips are covered by car and ridesharing. 95% parking space can be freed up (VCÖ  Mobilität der Zukunft 2020). Moreover, carsharing saves up to 44 million carkilometres in Vienna annually. This equals to approximately 7000 tons of CO\(_2\) (MA 18  Stadtentwicklung und Stadtplanung Wien 2015). Hence, by using carsharing, resources can be employed more efficiently, it is more environmentally friendly, and newly available space can be gained as, e.g., green space in urban areas (VCÖ  Mobilität der Zukunft 2020).
The importance of rethinking mobility is clearly visible in the presence of prominent concepts in various cities. Vienna targets a split of 80:20 where 20% of the trips are covered by cars, the others by public transportation, bikes or walking. The idea is to extend the mobility offers with profound sharing concepts and to move towards the vision of a ’Smart City’ (Stadtentwicklung Wien 2020). Madrid is aiming to establish a holistic ’Mobility as a Service’ concept offering realtime information and including over 30 shared mobility options (CIVITAS 202 2020). Within novel mobility concepts, bikes are receiving exceptional attention. Vienna almost doubled the cycling network in the last decade and accomplished a similar increase in kilometres driven on specific legs (Fahrrad 2020; MA 46 2020). Paris presents the ’Plan Vélo’ where the target is to emerge to the world’s bike capital. The ambition is to minimize the space for cars and make space for bike usage and pedestrians (Paris en Selle 2020).
Novel mobility concepts and reconsidering mobility play an important role not only in a private environment, but also in a corporate setting. Companies increasingly aim to provide mobility concepts for their employees. This work is part of an applied research project SEAMLESS (http://www.seamlessproject.at), in which project partners, such as the Austrian Post AG or TSystems Austria GesmbH, strive for the implementation of the discussed ideas. The target is to reduce a onetoone assignment of company cars, employ more environmentally friendly MOTs and strive for shared mobility where each employee gets her preference. This goes hand in hand with companies aiming for a greener carbon footprint and enhancing employee satisfaction (SEAMLESS 2020).
Traveller experience needs to be taken into account in the design of novel mobility systems and is key to its success with users (Al Maghraoui et al. 2019). Thus, when studying mobility, convenience and user preferences are crucial. However, from an operator perspective the cost factor plays an important role as well and usually costefficiency is in conflict with a MOT’s convenience. This ’convenience’ is difficult to measure and must be tackled on an individual user level. As we observe, and also other authors studying mobility have outlined (Ferrero et al. 2018), including user preferences can decide on the ’win or lose’ of a system. Therefore, we investigate the tradeoff between minimizing cost and enhancing the individual satisfaction of a user in a mobility system. Combining these parameters and providing the decision maker with a set of efficient solutions will lead to an enhanced acceptance of such a system.
Advertisement
Motivated by this, we study the biobjective multimodal carsharing problem where we assign MOTs to trips and find car and, depending on the variant, also user routes throughout a day. We formulate two objectives to minimize cost and maximize user satisfaction. We further take into account the possibility of variation in user preferences and travel times throughout the day, becoming timedependent input parameters. We refer to carsharing throughout the paper as to where a group of users is mutually using a pool of cars. Note that the output aims to provide an optimal assignment of MOTs throughout a day using timedependent travel times.
Our main contributions are:The paper is organized as follows: In Sect. 2, we review related work. Section 3 introduces the BiOMMCP where Sect. 3.1 gives a problem formulation, followed by the formal description in Sect. 3.2 for all four variants. In Sect. 4, we describe the implemented solution approach. As most of the variants are solved as a mixed integer program (MIP) with the generic MIP solver CPLEX, we focus on the branchandcut developed for the last variant of the model, described in Sect. 4.2. Moreover, we introduce a set of valid inequalities in Sect. 4.1 and describe the biobjective frameworks used in this paper in Sect. 4.3. Section 5 summarizes our computational study. Finally, we draw conclusions and we give an outlook to future work in Sect. 6.

We introduce the biobjective multimodal carsharing problem (BiOMMCP). We present four variants of the problem, discussing increased flexibility of the timings of the visits: we present the model (i) with fixed task sequences and without timedependent travel times and user preferences, (ii) with fixed time sequences and including timedependent travel times and user preferences, (iii) no fixed sequences and no timedependent travel times or preferences and lastly (iv) open sequences of tasks and timedependent travel times and user preferences.

We propose a branchandcut algorithm for the most complex problem variant examined in this paper. The algorithm is embedded into two biobjective frameworks, namely the \(\epsilon \)constraint method and a weighting binary search method. We show that for both frameworks it is highly beneficial to add cuts in the form of constraints from prior iterations to the following iterations.

We provide a thorough analysis where we (i) compare different solution approaches for the models and (ii) give insights into the tradeoffs between costminimization and enhancing usercentred MOT preferences.
2 Related work
Research addressing the design and implementation of carsharing systems has risen over the past years. Many existing papers focus on strategic decision making, such as the design of services, infrastructure (e.g. design/location of facilities or charging stations) or fleet management. Nevertheless, various papers stress the importance of integrating the user related attributes in optimization problems tackling sharing systems. A comprehensive literature review has been presented by Ferrero et al. (2018).
A large amount of research has been performed on data collection, data analysis and simulationbased studies in order to assess the potential impacts of carsharing systems. Most of these studies have been conducted on citywide public systems. Demand for carsharing systems and impacts on mobility behaviour are typically assessed through questionnaires (Zhou and Kockelman 2011; Sioui et al. 2013). The potential and effects of such systems are then often determined through simulationbased approaches (Ciari et al. 2014). From an operational perspective, problems considered in the carsharingrelated literature are mainly concerned with relocating, recharging and servicing vehicles (de Almeida Correia and Antunes 2012; Nair and MillerHooks 2014; Weikl and Bogenberger 2013). The problem we are introducing in this article, however, is an operational problem for planning trips and allocating means of transport in a closed system where travel demand is known in advance. Embedding carsharing in a multimodal system, and especially treating it in a biobjective formulation, is a novel way of addressing carsharing from a usercentered perspective.
In a different line of research, ridesharing has attracted an increased amount of interest in the last years. Major research efforts have been made in analysing and designing such services. Strategic and tactical decisions as well as the development of new algorithms for daily operations have also been in focus of recent work. A comprehensive survey on such approaches can be found in Mourad et al. (2019). A large number of case studies mainly based on simulation and data analysis have been published on the potential impact and feasibility of various sharing schemes with a focus on ridesharing (Calvo et al. 2004; d’Orey and Ferreira 2014; Maciejewski et al. 2016; Tachet et al. 2017).
For the first two variants of our proposed problem, where the task sequence is fixed, we refer to the Fixed Sequence Arc Selection Problem (FSASP) which was introduced by Garaix et al. (2010) and proven to be NPhard. The FSASP considers a fixed sequence of nodes that are linked by multiple arcs. Choosing an arc between two nodes is the subject of determination. This problem applies to the first two variants of our problem in this paper. Note that only recently Huang et al. (2017) shortly stressed that this research direction can be a good basis for further algorithmic work, naming home appliance delivery companies as an example. As we additionally determine the sequence of visited nodes, we can detect similarities to the VRP (Toth and Vigo 2002; Eksioglu et al. 2009) in our work. Our paper introduces a kind of multitrip VRP (Cattaruzza et al. 2016) with heterogeneous vehicles and multiple depots on a multi graph. Garaix et al. (2010) were among the first who studied VRPs with alternative arcs between each pair of nodes. VRPs with multiple attributes (Garaix et al. 2010) or multigraphs in the VRP stream have gained increasing attention in the past years (Doppstadt et al. 2016; Ben Ticha et al. 2017, 2018, 2019; Huang et al. 2017), whereas, of course, mutlimodality significantly enlarges the set of possible solutions (Caramia and Guerriero 2009). Research considering various attributes on arcs is fairly recent, yet highly important to consider as one connection of nodes usually implies specific tradeoffs (usually time vs. cost) which are not considered on a classical graph. We consider the characteristics of different modes of transport as well as timedependent preferences and costs jointly on one arc. We refer to Gendreau et al. (2015), for a review on timedependent routing problems. However, we could not find any work introducing timedependent preferences on modes of transport in a carsharing context.
Integrating customeroriented aspects into optimization problems, or more specific vehicle routing problems, is a topic of increasing interest. In Vidal et al. (2019), a detailed analysis through VRP variants also tackling customercentred objectives is provided. As an example, the cumulative VRP (Ngueveu et al. 2010; Silva et al. 2012) replaces the classical minimum cost objective function with the minimization of individual customer arrival times. MartínezSalazar et al. (2015) introduce a customercentric multitrip VRP with a single vehicle minimizing the sum of customer waiting times to receive a specific service. On a somewhat different but related topic, Braekers et al. (2016) introduce a biobjective routing and scheduling problem for home care where the second objective minimizes client inconvenience. In our work, we optimize user preferences for MOTs as a second objective function. Jozefowiez et al. (2008) review numerous papers tackling multiple objectives in the context of VRPs. They name the most common objectives to be cost, length of the tour, balance or problem specific objectives. Since then, various papers have been published. Recently, it seems that there is a vast amount of published research with environmental (Abad et al. 2018; Alexiou and Katsavounis 2015; Androutsopoulos and Zografos 2017; Demir et al. 2014; Eskandarpour et al. 2019; Ghannadpour and Zarrabi 2019; Toro et al. 2017; Tricoire and Parragh 2017; Govindan et al. 2019; Anderluh et al. 2019; Grabenschweiger et al. 2018) or external social criteria (Ghannadpour and Zarrabi 2019; Govindan et al. 2019; Nolz et al. 2014; Anderluh et al. 2019; Grabenschweiger et al. 2018) as alternative objectives.
Multiobjective optimization gives a deeper insight into the solution pool of a problem. However, there might exist a large number of tradeoff solutions. The target is to find an efficient set of solutions that cannot be optimized in one objective without worsening another one. Those efficient solutions are then called Pareto optimal solutions. There is a vast amount of works on exact as well as heuristic approaches to solve for multicriteria optimization problems. Prevailing metaheuristics in this field are evolutionary algorithms such as the NSGAII (Deb et al. 2000) or the SPEAII (Gharari et al. 2016). However, only recently Matl et al. (2019) have shown that singleobjective VRP heuristics can be efficiently used in an \(\epsilon \)constrainedbased method. The \(\epsilon \)constraint method (Yh et al. 1971; Srinivasan and Thompson 1976) is one of the prevailing methods to solve multiobjective optimization problems. It repeatedly solves a singleobjective optimization problem by considering the other objectives in terms of constraints. Further widely applied frameworks to solve multiobjective problems are the twophase method (Visée et al. 1998), the weighted sum approach (Aneja and Nair 1979) or, more recently, the balanced box method (Boland et al. 2015) and the weighting binary search method (RieraLedesma and SalazarGonzález 2005). These socalled criterion space methods embed a singleobjective optimization problem and systematically enumerate the Pareto frontier. However, recent works focus on adapting the branchandbound algorithm to solve the multiobjective case in a single run (Stidsen et al. 2014; Vincent et al. 2013; Parragh and Tricoire 2019; Adelgren and Gupte 2017). A recent overview of exact methods for multiobjective optimization is provided in Ehrgott et al. (2017). A detailed overview of general multiobjective combinatorial optimization is provided by Ehrgott and Gandibleux (2003). For our study, we choose the \(\epsilon \)constraint method as well as a weighting binary search as they are relatively simple to implement and have shown to be very efficient. The latter one is based on the algorithm proposed by RieraLedesma and SalazarGonzález (2005), who developed a weighting method and conduct a binary search in the objective space. Moreover, similar to Bérubé et al. (2009), we use a branchandcut approach relying on previous information for subsequent problems by adding cuts to the subproblem. Similarly in RieraLedesma and SalazarGonzález (2005), cuts from prior iterations are added to the cut pool for further iterations. Contrary to RieraLedesma and SalazarGonzález (2005) and Bérubé et al. (2009), we add detected cuts as hard constraints, showing better results for our problem setting.
3 The biobjective multimodal carsharing problem
In the following, we describe the BiOMMCP and give a formal description of the variants of the problem studied in this paper.
3.1 Problem description
The BiOMMCP aims to assign modes of transport to user trips and determining car routes during a day whilst minimizing cost and maximizing user satisfaction by accounting for MOT preferences.
Each user trip starts in a depot, covers a set of tasks and ends in a depot again. A user may have more than one trip during a day. A route is a sequence of trips during a day. Note that we introduce car routes and user routes: A car route schedules the trips covered by one car during a day, whereas the car is handed over at the depot from one user to another. A user route consists of all the trips assigned to one user during a day, whereas the user may change MOTs between trips (i.e. at the depot).
We consider a closed group of users and a set of possible MOTs. A pool of cars is given and all other MOTs are considered to have infinite capacity. With this assumption, we are able to cover all demanded trips. This also has practical implications as, e.g., there is usually no spatial or temporal limit on the availability of public transport in a city during a day. This also holds for bikes, as due to several bikesharing offers, we can assume that bikes are available at any time in a city. Each user may give preference scores to the available MOTs where we assume the lower the score the better the MOT is rated (scale 110 where 1 is best). Moreover, depending on the variant of the problem, users may determine preferences for different times of the day, resulting in timedependent userbased MOT preferences. Furthermore, we introduce timedependent travel times as, e.g., the car drive will take longer through rushhour than at noon. As our cost function also comprises cost of time, the adapted travel times will have an impact on the cost function. Note that even though travel times may be stochastic, we can plan within a deterministic setting as we use timedependent travel times for all modes of transport.
The goal of the BiOMMCP is to cover a set of trips for a given planning horizon by assigning MOTs to trips and determine car routes (optionally also user routes) for a closed community. The locations of the start and end points as well as the tasks of a trip are fixed. This means, it is known in advance which user will visit which task. Depending on the considered variant of the problem, the sequence of the tasks may vary.
We investigate four variants of the introduced problem:
Model 1 (m1)
In the first variant we assume that each user follows a fixed sequence of tasks, starting and ending at a fixed (but possibly different) depot. Preferences are given for each MOT for each user. We aim to find the best MOT to trip assignment and to determine the car routes. The objectives are to minimize costs and MOT preferences. In this variant, user routes are assumed to be given.
Model 2 (m2)
In this variant, we assume the same setting as in model m1 but include timedependent MOT preferences and travel times. The target is to find the best MOT to trip assignment and schedule the car routes from a pool of cars whilst minimizing timedependent costs and user preferences. Again, user routes are input to the problem.
Model 3 (m3)
In the third variant, we consider a fixed user to tasks assignment, and start and end locations. However, the sequence of tasks within a trip as well as the sequence of user trips are subject of determination. This means that we have to, in addition to car routes, find user routes throughout a day. The objectives are again to minimize costs and user preferences.
Model 4 (m4)
This model is a combination of model m2 and m3: we consider timedependent user preferences and travel times as well as variable task and trip sequences. Thus, we intend to determine the MOT assignment, schedule car as well as user routes whilst minimizing both timedependent MOT preferences of users and costs.
3.2 Formal description
We now formally introduce different variants and their respective mathematical formulations, using the following notation (also summarized in Table 1):
Table 1
Mathematical notation used in the formal description of the BiOMMCP
Sets and nodes  
P  Set of users 
R  Set of trips 
\(Q_r \subseteq Q\)  Set of tasks of trip r as a subset of the set of tasks 
\(a_r\)  Start node of a trip r 
\(b_r\)  End node of a trip r 
\(G_r\)  Set of nodes on a trip r 
D  Set of depots 
K  Set of modes of transport 
L  Set of legs 
\(L^,L^+\)  Set of ingoing/outgoing legs 
\(L_v^,L_v^+\)  Set of ingoing/outgoing legs of node v 
\(L_d^,L_d^+\)  Set of ingoing/outgoing legs of depot d 
\(L_{p}\)  Set of legs assigned to user p 
\(L_r\)  Set of legs on a trip r 
\(L_{vp}\)  Set of legs of a user p going in/out of a node v 
\(L_{vk}^,L_{vk}^+\)  Set of ingoing/outgoing legs of node v by MOT k 
\(L_{vp}^,L_{vp}^+\)  Set of ingoing/outgoing legs of node v by user p 
T  Set of time periods 
S  Subset of the set of nodes \(G_r\) of a trip r 
\(A_p \subseteq A\)  Set of trip start nodes of a user p as a subset of the set of trip start nodes 
\(B_p \subseteq B\)  Set of trip end nodes of a user p as a subset of the set of trip end nodes 
V  Set of all nodes 
\(V'\)  Set of nodes without depots, V \(\setminus \) D 
T  Set of time periods 
\(\mathcal {R}\)  Set of infeasible paths 
\(\mathcal {R}_{car}\)  Set of infeasible car routes 
\(\mathcal {R}_{p}\)  Set of infeasible user routes 
\(\gamma _p\)  Start node of person p 
\(\phi _p\)  End node of person p 
Input parameter  
\(W_{dk},\overline{W}_{dk}\)  Number of MOTs k in depot d at beginning/end of the planning horizon 
\(\sigma _{pk},\sigma ^t_{pk}\)  Preference value of a person p for MOT k (for time period t) 
\(\theta _{l}\)  Preference of leg l 
\(y_l\)  Origin of leg l 
\(z_l\)  End of leg l 
\(c_{l}\)  Cost of leg l 
\(u_l\)  User of leg l 
\(m_l\)  MOT of leg l 
h  Maximal waiting time 
H  End of planning horizon 
M  Big M 
\(t_l\)  Driving time of leg l 
\(s_v\)  Service time at node v 
\(o_l\)  Interval start of leg l 
\(e_l\)  Interval end of leg l 
\(\mathcal {W}\)  Accumulated waiting time 
\(\Delta \)  Value stating how much a route can be moved forward 
F  Forward slack, \(F=\mathcal {W}+\Delta \) 
Decision variables  
\(x_{l}\)  1 if leg l is chosen, 0 otherwise 
\(\tau _l\)  Departure time of leg l 
Given is a set of users P and a set of trips R, where each trip \(r \in R\) has a set of tasks \(Q_r\) assigned. A trip starts in a depot \(a_r\), ends in depot \(b_r\) and covers in between one or more tasks q. We store all nodes assigned to a trip r in the set \(G_r\), where \(r = \{a_r,q^r_1,q^r_2,...,b_r\}\). Note that a user p might cover more than one trip during a day. The set of tasks \(Q_r\) is known in advance, whereas each task q is unique and may only be in one set \(Q_r \subseteq Q\), where Q denotes the set of all tasks. We model the connections between two subsequent tasks as a leg l.
Furthermore, we consider a set of depots D, which are artificial nodes representing start/end points of car routes during a day, i.e. each route starts and ends here. The start depot d is connected to all starting nodes a, and conversely each end node b is connected to the end depot \(d'\).
We consider a set of modes of transport K = car,public,bike, where public comprises public transportation including walking. If a trip starts by a MOT, then the MOT will be used for the full trip. We assume at each depot \(d \in D\) an available number of MOTs k at the beginning and end of the planning horizon, denoted as \(W_{dk}\) and \(\overline{W}_{d'k}\), respectively.
We denote the set of all nodes by V and \(V'\) be the set of nodes without the set D, such that \(V' = V \setminus D\). For every node \(v \in V\), we have the set of outgoing legs \(L_{vk}^+\) and ingoing legs \(L_{vk}^\) by MOT k. All legs are stored in the set of all legs L. We store any relevant information on the legs.
Each user p assigns a preference value \(\sigma _{pk}\) to each of the given modes of transport \(k \in K\). Note that, as we also minimize the preference objective, we assume that the lower the score, the better the user values the mode of transport. As a leg l refers to exactly one mode of transport k and one user p, we assign the value \(\sigma _{pk}\) to the respective leg l, denoted as \(\theta _l\). The cost value \(c_l\) of a leg l consists of variable distance cost, cost of time and cost of emissions. For more information, we refer to Sect. 5.1.
For timedependent user preferences, we define a set of time periods \(t \in T\) during the day. A time period replicates, e.g., rushhours. Each user p determines a preference value \(\sigma ^t_{pk}\) for each of the given time periods t and MOT k. In the case when a leg l completely lies within a period t the preference value of the leg \(\theta _{l}\) equals \(\sigma ^t_{pk}\). In the case where the leg covers more than one period, we calculate a weighted average of the preference values. As our cost also depends on time, we also adapt the cost term considering time dependencies in the same way.
Figure 1a shows an example of a simple trip r. It starts in node a and ends in b whilst visiting \(q_0\) and \(q_1\). We insert legs for each mode of transport (denoted by different lines) between each node and assign the respective cost and preference value, given in brackets as (\(c_l\),\(\theta _l\)). We do not consider timedependent travel times or user preferences here. Figure 1b shows the same trip as Fig. 1a, but considers time dependencies. Therefore, three time periods are indicated as \(t_0,t_1,t_2\). For each leg, we have cost and preference values for each of the respective periods. The legs between \(q_0\) and \(q_1\) lie completely within one time period and can therefore be taken as they are. For the others, we compute the share of each time period on the leg and get the respective preference value and cost by computing the weighted average.
×
3.2.1 Model 1 (m1)
In model m1, the sequence of tasks is fixed, resulting in predetermined trips \(r \in R\). We connect each a with its fixed successor q, each task q with its fixed successor \(q'\) or, if the trip only covers one task, the trip end node b. For every pair of end and start nodes (b, a) where a is ahead in time, we insert an additional artificial leg with costs and preferences 0, in order to allow for the connection of car routes covering more than one trip throughout the day.
Each leg in the graph results in a tuple \(\{(u_l,y_l,z_l,m_l,c_l,\theta _l)\}\) where \(u_l\) is the assigned user, \(y_l\) and \(z_l\) are the origin and end of the leg, \(m_l\) the assigned MOT, \(c_l\) the cost and \(\theta _l\) the preference value.
The introduced binary decision variable \(x_{l}\) takes on value 1 if leg l is chosen and 0 otherwise.
With this, we can introduce a compact formulation for the first version of the BiOMMCP.The objective (1) minimizes total cost and objective (2) minimizes usercentred MOT preferences. Constraints (3) make sure that each node v is covered by exactly one leg l. Constraints (4) ensure flow conservation at nodes \(v \in V'\) for every MOT k. Constraints (5) and (6) restrict the number of available MOTs \(W_{dk}, \overline{W}_{d'k}\) at the start and end of the time horizon. Constraints (7) define the domains of the decision variables.
$$\begin{aligned} \text{ min }&\quad \sum \limits _{l \in L} c_{l} x_{l} \end{aligned}$$
(1)
$$\begin{aligned} \text{ min }&\quad \sum \limits _{l \in L} \theta _{l} x_{l} \end{aligned}$$
(2)
$$\begin{aligned} \text{ s.t }&\sum \limits _{k \in K} \sum \limits _{l \in L_{vk}^+} x_{l} = 1&\forall v \in V' \end{aligned}$$
(3)
$$\begin{aligned}&\sum \limits _{l \in L_{vk}^} x_{l} = \sum \limits _{l \in L_{vk}^+} x_{l}&\forall v \in V', k \in K \end{aligned}$$
(4)
$$\begin{aligned}&\sum \limits _{l \in L_{dk}^+} x_{l} \le W_{dk}&\forall d \in D, k \in K \end{aligned}$$
(5)
$$\begin{aligned}&\sum \limits _{l \in L_{d'k}^} x_{l} \le \overline{W}_{d'k}&\forall d' \in D, k \in K \end{aligned}$$
(6)
$$\begin{aligned}&x_{l} \in \{0,1\}&\forall l \in L \end{aligned}$$
(7)
3.2.2 Model 2 (m2)
We extend the previous model by introducing timedependent MOT preferences and costs. We assume fixed times of tasks q. With this, and as we know the driving time of a leg, we can exactly determine start and end times of the leg and thus assign a preference value.
As we store all relevant information directly on the leg l, we do not have to model time explicitly. This results in the same tuple \(\{(u_l,y_l,z_l,m_l,c_l,\theta _l)\}\) as before, with a modified value of \(\theta _l\) and \(c_l\). As we only have a change in the data, but the model remains unchanged, we use model m1 again.
3.2.3 Model 3 (m3)
In model m3, we have to determine the sequence of tasks per user (ensuring no subtours) as well as consider the scheduling of trips each user is taking. Therefore, the underlying graph has to be adapted. We again consider the set of all nodes V, the set of intermediate nodes \(V'\), the set of depots D, the set of MOTs K, the set of legs L, and the set of users P. We define sets \(A_p\) and \(B_p\) containing all start nodes a and end nodes b of a user p, respectively. These sets will consist of exactly one node, if a user is taking only one trip, two if the user has two trips, etc. Previously, to assure car routes, we only connected an end node b of a trip to a start node a of another trip if a was ahead in time of b. As we are not considering any fixed times/sequences anymore, we connect every b to every a if they are in the same physical depot. Similarly, we connect all nodes belonging to one set \(G_r\), yet not changing the predetermined start and end nodes of one trip. For now, we do not consider timedependent preferences on legs. Note that the tasks lying on a specific trip are fixed, meaning that if a user previously had two trips, the user will again cover two trips.
In order to prevent parallel trips of one user, the user routes are modelled into the graph. Doing so, we add new artificial nodes \(\gamma _p\) and \(\phi _p\) for each user p where the user starts and ends the respective route during a day (similar to the idea of the \(d \in D\) where all MOT flows start). We connect the respective \(\gamma _p\) to all start nodes \(a \in A_p\) of one user p and conversely the respective \(\phi _p\) to all \(b \in B_p\). We connect user trips by inserting a leg l between b, a of the same user. Note that, instead of modifying the underlying graph, we also used additional constraints in the model. However, this formulation turned out to be very weak.
As the sequence of tasks of a trip is not fixed, we determine the departure time \(\tau _l\) of a leg l. By assuring increasing times of legs, we also avoid subtours. Additionally, in order to avoid unrealistic long waiting times at nodes, we assume that a user can wait for a maximum amount of time before she continues her trip, e.g. 30 min, denoted as h.
Model m3 can now be stated as follows, where decision variables \(\tau _l\) give the departure time of leg l, H depicts the end of the planning horizon, M denotes a big M, \(t_l\) is the travel time of a leg l and \(s_v\) the duration of the task.Constraints (8) set the time variables and take care of subtour elimination within trips. Constraints (9) ensure that a user is leaving at the latest h minutes after the end of the task. Constraints (10) restrict the latest departure time at any task to be at the end of the time horizon. Constraints (11) and (12) make sure that each user is starting her route in node \(\gamma _p\) and ending in node \(\phi _p\). Constraints (13) and (14) balance the flows of start and end nodes of user p. Constraints (15) eliminate parallel trips. Finally, constraints (16) make sure that decision variables \(\tau \) are nonnegative.
$$\begin{aligned} \text{ min }&\qquad(1) \nonumber \\ \text{ min }&\qquad(2) \nonumber \\ \text{ s.t }&\qquad(3)(7) \nonumber \\&\tau _l + t_l + s_v  \tau _n \le M (2  x_l  x_n)&\forall l \in L_{vk}^, n \in L_{vk}^+, v \in V', k \in K \end{aligned}$$
(8)
$$\begin{aligned}&\sum \limits _{l \in L^_v} (\tau _l + t_l x_l) + s_v \ge \sum \limits _{l \in L^+_v} \tau _{l}  h&\forall v \in V' \end{aligned}$$
(9)
$$\begin{aligned}&\tau _l \le H x_l&\forall l \in L \end{aligned}$$
(10)
$$\begin{aligned}&\sum \limits _{l \in L_{\gamma _p}^+} x_{l} = 1&\forall p \in P \end{aligned}$$
(11)
$$\begin{aligned}&\sum \limits _{l \in L_{\phi _p}^} x_{l} = 1&\forall p \in P \end{aligned}$$
(12)
$$\begin{aligned}&\sum \limits _{l \in L^{}_{vp}} x_{l} = \sum \limits _{l \in L^+_{v}} x_{l}&\forall v \in A_p, p \in P \end{aligned}$$
(13)
$$\begin{aligned}&\sum \limits _{l \in L_{v}^} x_{l} = \sum \limits _{l \in L_{vp}^{+}} x_{l}&\forall v \in B_p, p \in P \end{aligned}$$
(14)
$$\begin{aligned} \tau _l + t_l +&s_v  \tau _n \le M (2  x_l  x_n) \quad \forall l \in L^_{vp}, n \in&L^+_{vp}, v \in V' \cup \{\gamma _p,\phi _p\}, p \in P \end{aligned}$$
(15)
$$\begin{aligned}&\tau _{l} \ge 0&\forall l \in L \end{aligned}$$
(16)
3.2.4 Model 4 (m4)
Lastly, in addition to a flexible sequence of tasks, in model m4 we add timedependent MOT preferences to the model. This is mainly done by adapting the graph and by adding one constraint to the model m3.
We discretize time in intervals of \(\alpha \) minutes and duplicate each leg \(l \in L\) for each interval. Note that timedependent MOT preferences are derived from the user preference values \(\sigma ^t_{pk}\).
We extend the leg information by adding the start and end times of the interval lying on the leg; this results in the tuple \(\{(u_l,y_l,z_l,m_l,c_l,\theta _l,o_l,e_l)\}\) where \(o_l\) gives the start time and \(e_l\) the respective end time of the interval.
Finally, we append the following constraints to model m3:Constraints (17) make sure that \(\tau _l\) of leg l lies within the predetermined times.
$$\begin{aligned} o_l x_l \le \tau _l \le e_l \quad \forall l \in L \end{aligned}$$
(17)
The resulting model relies on both binary and continuous variables. We adapt this and use a reformulation that is of exponential size but relies on binary variables only. We replace constraints (8), (9), (10), (15), (16), and (17) by infeasible path constraints (Ascheuer et al. 2000) (for car routes and user routes) and subtour elimination constraints.
Let \(\mathcal {R}_{car}\) denote the set of infeasible car routes and \(\mathcal {R}_{p}\) be the set of infeasible user routes. V(S) gives the nodes of the set S, where S is a subset of the set of nodes on a trip \(G_r\). Legs of an infeasible path \(\rho \) are denoted as \(L(\rho )\). Model m4b can be stated as follows:Constraints (18)–(19) eliminate the infeasible paths of cars and users. We sum over all legs l of the respective infeasible path \(\rho \) and set it infeasible by denoting that at least one leg cannot be on the route. Constraints (20) are subtour elimination constraints. We set the constraints for all trips r where we store the nodes of each trip in the set \(G_r\).
$$\begin{aligned} \text{ min }&\qquad(1) \nonumber \\ \text{ min }&\qquad(2) \nonumber \\ \text{ s.t }&(3)(7), (11)(14) \nonumber \\&\sum \limits _{l \in L(\rho )} x_l \le L(\rho )  1&\forall \rho \in \mathcal {R}_{car} \end{aligned}$$
(18)
$$\begin{aligned}&\sum \limits _{l \in L(\rho )} x_l \le L(\rho )  1&\forall \rho \in \mathcal {R}_p \end{aligned}$$
(19)
$$\begin{aligned}&\sum \limits _{l {\in L(S)}} x_l \le {S}  1&\forall S \subseteq {G_r}, r \in R, {S \ne \emptyset } \end{aligned}$$
(20)
4 Solution approach
In the following, we first introduce valid inequalities in Sect. 4.1. By embedding the models into biobjective optimization frameworks, described in Sect. 4.3, the scalarized models m1, m2, and m3 are solved with CPLEX. We can solve realworld sized instances within seconds, as we will show in our computational results. However, as expected, m4 is more challenging to solve. Therefore, we develop a branchandcut algorithm in Sect. 4.2 for model m4b.
4.1 Valid inequalities
In order to strengthen the models m3, m4, and m4b, the following set of valid inequalities is used.
We know that all legs of a trip must be covered by a single MOT. Therefore, we can say that either MOT k is going into node v, or any other MOT \(g \ne k\) out of a node v, but not both. Assuming that the ingoing legs of a node v are stored in the set \(L^_{vg}\) and all outgoing legs of a node v are stored in the set \(L^+_{vk}\), we can state:In m3, m4, and m4b, we only require that the sum over all outgoing legs of a node must be equal to 1. In the following valid inequality, the sum over all ingoing legs \(l \in L_{vk}^\) using MOTs k of a node v has to be equal to 1:Since a car may cover more than one trip, but has to take at least one if it departs from the depot d, the number of trips started with a car (leaving from any node \(a \in A\)) has to be greater or equal to the sum of cars leaving any depot \(d \in D\). Ingoing legs of the start nodes a using MOT k are given in the set \(L_{ak}^\); outgoing legs of the depot d are given in the set \(L_{dk}^+\). The constraint is valid for cars only. Thus, we sum over all the ingoing legs of any node a, which then has to be greater or equal to the sum over all outgoing legs of any depot d:Assuming that a user p has been assigned a single task only, then a full user route will be: \(\gamma _p  a_p  q  b_p  \phi _p\). This means the shortest possible user route consists of four legs. Assuming that all legs assigned to a user p are stored in the set \(L_p\), we can formulate:Assuming that a trip has at least one task, then each trip will consist of at least three nodes (\(aqb\)) and thus two legs. The sum over all legs of a trip r is at least the number of nodes assigned to the respective trip, given in the set \(G_r\), minus 1. :As we know the number of tasks a person is covering, we also know the number of legs the person will cover in the solution. Therefore, we can introduce the following constraint where \(L_p\) is the set of legs of a person
p and \(V_p\) gives the nodes assigned to person p:We add cycle constraints, meaning that we can only go either from v to \(v'\) or from \(v'\) to v, but not both. We store all legs that start in v and end in \(v'\) in the set \(L^{(v,v')}\) and vice versa in \(L^{(v',v)}\). With this, we formulate the following valid inequality:The above valid inequalities are used to strengthen m3, m4, and m4b. We now propose additional valid inequalities which are used to strengthen only m4 and m4b.
$$\begin{aligned} \sum _{l \in L^+_{vk}} x_l + \sum _{g \in K: g \ne k}\sum _{l \in L^_{vg}} x_l = 1 \quad \forall v \in V', k \in K \end{aligned}$$
(21)
$$\begin{aligned} \sum \limits _{k \in K} \sum \limits _{l \in L_{vk}^} x_{l} = 1 \quad \forall v \in V' \end{aligned}$$
(22)
$$\begin{aligned} \sum \limits _{a \in A} \sum \limits _{l \in L_{ak}^} x_{l} \ge \sum \limits _{d \in D} \sum \limits _{g \in L_{dk}^+} x_{g} \quad {\hbox {with}\, k = \hbox {car}} \end{aligned}$$
(23)
$$\begin{aligned} \sum \limits _{l \in L_p} x_l \ge 4 \quad \forall p \in P \end{aligned}$$
(24)
$$\begin{aligned} \sum \limits _{l \in L^_v: v \in G_r} x_l \ge G_r  1 \quad \forall r \in R \end{aligned}$$
(25)
$$\begin{aligned} \sum \limits _{l \in L_p} x_l = V_p  1 \quad \forall p \in P \end{aligned}$$
(26)
$$\begin{aligned} \sum \limits _{l \in L^{(v,v')}} x_l + \sum \limits _{l \in L^{(v',v)}} x_l \le 1 \quad \forall (v,v') \in L \end{aligned}$$
(27)
Let us consider a node v, a leg l leaving the node v, and an ingoing leg g. As described in Section 3.2.4, for the timedependent setting of the model, the legs contain intervals with the possible start and end time information (o, e). With this, we know that the start and end times of the outgoing leg l have to be greater than the times of the ingoing leg g. Therefore, if the start and end times of the ingoing leg g are greater than the times of the outgoing leg l, meaning that the ingoing leg would happen later in time, only one of them can be used:As any outgoing leg of a node v has to be later than the ingoing leg of the respective node, we can further eliminate all outgoing legs of a node v that are timed before a chosen ingoing leg of the respective node. Therefore, we adapt equation (28), where we assume an ingoing leg \(g \in L^_v\) of a node v and sum over all outgoing legs \(l \in L^+_v\) with smaller start and end times as the ingoing leg; thus, \(o_l < o_g\) and \(e_l < e_g\). Then, at most one of the respective legs can be chosen. Conversely, considering an outgoing leg l and summing over all ingoing legs \(g \in L^_v\) with an interval greater than the one of the outgoing legs (\(o_g > o_l\),\(e_g > e_l\)), we can again say that at most one leg can be chosen. Both valid inequalities can be formulated as follows:If the beginning of the interval \(o_l\) of the outgoing leg l is greater than the end of the interval \(e_g\) of the ingoing leg g plus the time of the ingoing leg \(t_g\) plus the service time at the node \(s_v\) plus the maximum waiting time h, then these legs are not compatible in time. Again, considering a node v with outgoing legs \(L^+_v\) and ingoing legs \(L^_v\), we can state the following valid inequalities:If the beginning interval \(o_g\) of the ingoing leg g plus the travel time of the ingoing leg \(t_g\) plus the service time of the node \(s_v\) is greater than the end of the interval \(e_l\) of the outgoing leg l, then these legs cannot be used together. We can again put this into two valid inequalities as follows:
$$\begin{aligned} o_l< o_g {\wedge } e_l < e_g \iff x_l + x_g \le 1 \quad \forall l \in L^+_v, g \in L^_v, v \in V' \end{aligned}$$
(28)
$$\begin{aligned} x_g + \sum _{l \in L^+_v: o_l< o_g {\wedge } e_l < e_g} x_l \le 1 \quad \forall g \in L^_v, v \in V' \end{aligned}$$
(29)
$$\begin{aligned} x_l + \sum _{g \in L^_v: o_g> o_l {\wedge } e_g > e_l} x_g \le 1 \quad \forall l \in L^+_v, v \in V' \end{aligned}$$
(30)
$$\begin{aligned} x_g + \sum _{l \in L^+_v: o_l > e_g+t_g+s_v+h} x_l \le 1 \quad \forall g \in L^_v, v \in V' \end{aligned}$$
(31)
$$\begin{aligned} x_l + \sum _{g \in L^_v: o_l > e_g+t_g+s_v+h} x_g \le 1 \quad \forall l \in L^+_v, v \in V' \end{aligned}$$
(32)
$$\begin{aligned} x_g + \sum _{l \in L^+_v: o_g+t_g+s_v > e_l} x_l \le 1 \quad \forall g \in L^_v, v \in V' \end{aligned}$$
(33)
$$\begin{aligned} x_l + \sum _{g \in L^_v: o_g+t_g+s_v > e_l} x_g \le 1 \quad \forall l \in L^+_v, v \in V' \end{aligned}$$
(34)
4.2 Branchandcut for m4b
In order to solve model m4b, we develop a branchandcut algorithm. Branchandcut algorithms make use of a subset of constraints and iteratively add further constraints in a cuttingplane fashion. Usually, constraint sets of exponential size are excluded which reduces the model to a reasonable size. In our case, we separate the infeasible path constraints (18)–(19), but we enumerate all subtour elimination constraints, since trips are usually very short. Separation algorithms are then called to determine whether the current solution is feasible by checking the omitted constraints. Note that the separation algorithms can be called on any relaxed solution or only on incumbent ones. Our strategy is based on the latter case, where we only call the algorithms if a new incumbent solution is found. If the separation algorithm detects a violation, the respective constraint is added as a cut to the model and the model is consecutively resolved. This is repeated until no violating constraints are detected and an optimal solution is found.
In our model, a route (path) may be infeasible due to (i) user related constraints, (ii) shared cars related constraints, and (iii) synchronization requirements between user and car routes. Therefore, we first check if all user routes are feasible, then if all car routes are feasible and finally if they are both simultaneously feasible. The respective separation procedures are described in the following.
4.2.1 Separation of infeasible user routes
We separate infeasible user routes for each user \(p \in P\). Let \(\overline{x}\) denote the solution at the current node in the branchandbound tree. We start the construction of the route \(\rho \) at node \(\gamma _p\). We denote the currently considered node as node v. From the starting point, we append the outgoing leg l at node v (v.outgoing) if \(\overline{x}_l=1\) to the route \(\rho \) and update v to be the end node of leg l (l.endNode). We do this until we hit the user end depot \(\phi _p\).
In the following, we consider a forward slack F, consisting of an accumulated waiting time \(\mathcal {W}\) and a value stating how much we could move the whole route such that the solution would still be feasible, given as \(\Delta \) and \(F=\mathcal {W}+\Delta \). The current time stamp is given as \(\tau \). Before checking the route \(\rho \) for time feasibility, we initialize F, \(\mathcal {W}\), \(\tau \) to 0, and \(\Delta =\infty \).
We iterate through the route as long as all time constraints are respected. We start by checking the second leg l on route \(\rho \) and systematically take the consecutive one. Thus, considering the current leg l leaving node v, we set \(\tau =\tau +s_v+t_{l1}\) and update \(\mathcal {W}\) and \(\Delta \). The accumulated waiting time is calculated as the current waiting time plus either the maximum possible waiting time h or the remaining time to the end of the interval \(e_l\), such that \(\mathcal {W}=\mathcal {W}+\hbox {min}\{\hbox {max}\{0,e_l\tau \},h\}\). We can further push the whole route to the end of the given interval \(e_l\) or by the previously stored \(\Delta \). We update \(\Delta =\hbox {min}\{\Delta ,\hbox {max}\{0,e_l(\tau +\mathcal {W})\}\}\) and compose \(F=\mathcal {W}+\Delta \). If the current time \(\tau \) lies within the respective interval of leg l (\(o_l,e_l\)), we can proceed to the next leg. If not, we try to push the route to the starting interval \(o_l\) of the current leg l, but at maximum by adding F, such that \(\tau =\tau +\hbox {min}\{\hbox {max}\{0,o_l\tau \},F\}\). If the adapted \(\tau \) violates the timing restrictions, the corresponding infeasible path constraint is generated. If \(\tau \) is feasible (\(o_l \le \tau < e_l\)), we can update \(\mathcal {W}\) and \(\Delta \) and proceed with the next leg. To update the values, we have to deduct the respective time used up of the forward slack. For this, we first adapt \(\Delta \) by stating \(\Delta =\Delta +\hbox {min}\{\mathcal {W}(\tau \tau '),0\}\), where \(\tau '\) denotes the time stamp before adding the time slack F. The waiting time is updated as \(\mathcal {W}=\hbox {max}\{\mathcal {W}(\tau \tau '),0\}\). The pseudocode is outlined in Appendix in Algorithm 1.
4.2.2 Separation of infeasible car routes
We further aim to detect infeasible paths regarding cars violating time constraints. We adopt the same idea as above, except following car routes. Starting depots of cars are \(d \in D\). Note that, as we might have more than one trip originating from one node d, we slightly adapt the construction of the route \(\rho \) by considering node d multiple times as a starting node for the construction of the route \(\rho \). We store the outgoing leg l of node v with \(\overline{x}_l=1\) and the MOT k = car in the route \(\rho \). Whilst constructing, we save the number of trips on the current route, as we only consider routes with more than one trip. Timing restrictions for a single trip are already covered in the user route separation. If the route \(\rho \) consists of multiple trips, we follow the same steps as previously described in the separation algorithm of user routes. The pseudocode is given in Algorithm 2 in Appendix.
4.2.3 Synchronization of routes
It is not sufficient to check user and car routes separately for infeasibility. We also have to check if the user and car routes are synchronized, i.e. if the user who has taken over a car is at the depot at the respective time. In order to do so, we consider the whole solution and we store the used legs in the subset \(L'\) and obtain the sets \(L'^_{vk}, L'^+_{vk}, L'^_{vp}, L'^+_{vp}\) (\(\overline{x}_l\) = 1 in the current solution), and we solve the following small LP derived from constraints (8), (9) and (15):Constraints (35) and (36) synchronize the car and user route with the decision variable \(\tau \). Furthermore, constraints (37) make sure that the waiting time at a node is not exceeded.
$$\begin{aligned}&\tau _l + t_l + s_v \le \tau _{{n}}&\forall l \in L'^_{vk}, n \in L'^+_{vk}, v \in V', k \in K \end{aligned}$$
(35)
$$\begin{aligned}&\tau _l + t_l + s_{{v}} \le \tau _{{n}}&\forall l \in L'^_{vp}, n \in L'^+_{vp}, v \in V' \cup U, p \in P \end{aligned}$$
(36)
$$\begin{aligned}&\tau _{{l}} + t_{{l}} + s_v \ge \tau _{{n}}  h&\forall l \in L'^_{vk}, n \in L'^+_{vk}, v \in V', {k \in K} \end{aligned}$$
(37)
The above constraints are infeasible if the respective user and car are not at the same time at the same place. Therefore, we can assume that either a car trip or an arc connecting the user trips is infeasible. Thus, we insert into the set \(L''\) all legs from the set \(L'\) that are taken by car or are connecting user trips in the current incumbent solution, and we add the following constraint:
$$\begin{aligned} \sum _{l \in L''} x_l \le L''  1 \end{aligned}$$
(38)
4.2.4 Strengthened infeasible path constraints
The infeasible paths introduced before in the form of constraint (18) and constraint (19) are very weak. We strengthen them as follows:Let \(\mathcal {L}'\) contain all legs with the same start node y, end node z, and MOT k but earlier or later intervals (o, e) than the last checked leg of the separation algorithm, i.e. where the infeasiblity was detected. Let \(l'\) be the last checked leg and \(\tau \) the current departure time. If \(\tau > e_{l'}\), meaning that we have jumped over the interval; then, the set \(\mathcal {L}'\) contains all legs with the same respective y, z, k but \(o < o_{l'}\). This means that if we missed the interval, then also all prior ones will be too early. Conversely, if the interval of leg \(l'\) could not be reached, thus \(\tau < o_{l'}\), we put all legs with the same y, z, k as leg \(l'\) but \(o > o_{l'}\) into the set \(\mathcal {L}'\). Hence, if we were not able to reach the respective interval, then also all later legs will not be reachable.
$$\begin{aligned} \sum _{l \in \rho } x_l + \sum _{l \in \mathcal {L}'} x_l + \sum _{l \in \mathcal {L}''} x_l \le \rho   1 \end{aligned}$$
(39)
The set \(\mathcal {L}''\) also depends on whether we are not able to reach the leg’s interval or we miss it. We consider all legs on the route \(\rho \) except the last checked leg \(l'\), denoted as \(\rho '\). Considering \(\tau < o_{l'}\), thus the time stamp lies before the start of the interval, then the set \(\mathcal {L}''\) contains the respective counterparts of all legs in \(\rho '\) with the same y, z, k but with an interval that lies behind the last saved \(\tau \). If we miss the interval of \(l'\), such that \(\tau > e_{l'}\), we assume that we cannot push any prior leg any further. In this case, we detect the respective duplications of the legs in \(\rho '\) with a higher interval such that the interval of any leg l is greater than \(o_{l''}\), where \(l''\) depicts the leg assigned to \(\rho \).
Moreover, we store all checked legs to the vector \(\rho _\mathrm{short}\). We know that the last leg is incompatible with the prior ones and can therefore add the following constraint:
$$\begin{aligned} \sum _{l \in \rho _\mathrm{short}} x_l + \sum _{l \in \mathcal {L}'} x_l + \sum _{l \in \mathcal {L}''} x_l \le \rho _\mathrm{short}  1 \end{aligned}$$
(40)
4.3 Biobjective frameworks
We embed our models into two biobjective frameworks. For m1, m2, and m3 we use the \(\epsilon \)constraint method. The branchandcut algorithm to solve m4b is embedded into both frameworks, namely the \(\epsilon \)constraint method and a weighting binary search method.
4.3.1 The \(\epsilon \)constraint method
The \(\epsilon \)constraint method iteratively solves singleobjective problems where one objective is kept in the objective function and the other one is moved to the set of constraints. After each iteration, the respective constraint in the constraint set is reduced by a certain \(\epsilon \). As we only consider integer variables and coefficients, we define the \(\epsilon \)value to be 1. For example, let us consider the cost function (1) as the main objective, and the preferences objective (2) is moved to the constraint as: \(\sum _{l \in L} \theta _l x_l \le \Omega  \epsilon \). \(\Omega \) is iteratively adapted, inserting the preference value from the previous subproblem, and is initially set to \(\infty \). We solve the problems in a lexicographic order, meaning that in each iteration two MIPs are solved. The algorithm stops once the second extreme point of the Pareto frontier (with the minimal second objective) is reached.
4.3.2 A weighting binary search method
As a second framework, we use a binary search in the objective space that is based on the algorithm introduced by RieraLedesma and SalazarGonzález (2005). The idea is to use a weighting method and iteratively enumerate the Pareto frontier. To start the algorithm, the extreme points of the Pareto frontier are calculated and stored as \(\left( f^{(1)}_1,f^{(1)}_2\right) \) and \(\left( f^{(2)}_1,f^{(2)}_2\right) \). \(f^{(1)}_1\) and \(f^{(2)}_1\) give the first, e.g. cost, solutions, of the respective extreme points, and conversely, \(f^{(1)}_2\) and \(f^{(2)}_2\) give the value of the second objectives, in our case: preferences. Thus, the objective value is set as \(\omega f^*_1 + (1\omega )f^*_2\), where \(f^*\) denotes the cost and preference function of the new solution. The weight \(\omega \) is calculated as \(\frac{\alpha }{\alpha + 1}\), where \(\alpha = \frac{f^{2}_2  f^{1}_2}{f^{1}_1  f^{2}_1}\). At each iteration, we add three constraints: (1) \(f^*_1 < f^{2}_1\), (2) \(f^*_2 < f^{1}_2\), and (3) \(\omega f^*_1 + (1  \omega )f^*_2 \le \omega f^{(1)}_1 + (1  \omega ) f^{(2)}_2  1\). The latter one makes sure that only nondominated points are generated. The values of the new solutions are then used for the following iterations where the next weights will be calculated with the values \(\left( f^{(1)}_1,f^{(1)}_2\right) \) and \(\left( f^{*}_1,f^{*}_2\right) \), as well as with \(\left( f^{*}_1,f^{*}_2\right) \) and \(\left( f^{(2)}_1,f^{(2)}_2\right) \). The algorithm terminates once no more values can be taken to calculate new weights.
Enhancements For both methods, we seize the biobjective characteristics of our problem: we store the cuts generated in the prior iterations and add them as constraints to the next models. Considering the \(\epsilon \)constraint method, we do this within one iteration (the min cost problem receives the cuts from the min preference model), as well as from one iteration to another. As for the binary search, we only solve one MIP with the respective objective function within each iteration. Therefore, we only pass on cuts from one solution to another.
5 Computational study
The models and the branchandcut algorithm are implemented in C++ and solved with CPLEX 12.9. Tests are carried out using one core of an Intel Xeon Processor E52670 v2 machine with 2.50 GHz running Linux CentOS 6.5. Unless otherwise stated, a time limit of 12 is used.
5.1 Test instances
For our computational study, we use realistic benchmark instances based on available demographic, spatial and economic data of Vienna, Austria. They are based on those used in Enzi et al. (2020a) and Enzi et al. (2020b). Note that the instances represent a company within a city; thus, the data do not aim to replicate the population of the whole city.
One instance set represents a distinct company consisting of one or more offices (or depots) D and users, i.e. employees, P. The number of tasks and their location are randomly generated.
In the original instances, each user may use a subset of the available MOTs \(K^p \subseteq K\). Based on this binary assignment of MOTs to users, we generate preference scores on a scale from 110, where 1 is best and 10 is worst. For example, if a user has cars in her set of MOTs but no public transportation, then this user will get a lower (better) score on cars and a higher (worse) one on public transportation. The detailed assignments used for the following study are included in Table 10 in Appendix. In the timedependent setting, we consider seven different time periods t: prerushhour, rushhour, after rushhour, normal daytime traffic, prerushhour, rushhour and after rushhour. Here we deduct/add for each preference score a certain number (see Table 11 in Appendix). Furthermore, we implement an increase/decrease in cost and time for the respective time periods (see Table 11 in Appendix). For this, we assume a factor \(\beta \) which is then multiplied with the base cost. For example, we assume that taking the car during rushhour takes longer than at noon. We assume \(\beta = 1.4\), which is then multiplied with the base cost, e.g. 5. This gives us cost of 7 for the rushhour for the respective leg. Naturally also the driving times of the legs are adapted accordingly. We calculate a weighted average of cost and preferences if a leg covers more than one periods.
Three different MOTs are considered: car, public transportation including walk and bike. For our study, we assume that all MOTs have an unrestricted capacity. Note that the original setting assumes a limited and fixed pool of cars, which is reasonable for the discussed problem. However, for our first results for the BiOMMCP we decided to let the number of cars be unlimited, to explore the computational efficiency without restricting the number of shared cars. Distances, time and cost are calculated between all nodes for all modes of transport. Emissions are translated into costs and, together with variable distance cost and cost of time, included into the overall cost calculations and summarized in \(c_l\). The respective preference value \(\theta _l\) is taken from the above presented values.
Instances are named as E_P_I, where P is the number of users, and the instance number I is between 0 and 9. For example, the first instance in the set of instances with 20 users (\(P = 20\)) is denoted E_20_0. For instance group with P users, we solve a set of 10 instances (E_u_0 to E_u_9) and report the average values.
5.2 Enhancements and preprocessing
In the following paragraphs, we shortly list the enhancements and preprocessing that we conducted.
Relative MIPgap In our first tests, CPLEX provided weakly dominated solutions or skipped some of the solutions from the Pareto set due to the default relative MIPgap. Therefore, we put a strict MIP gap tolerance of 0.0000. We compared the output with different tolerances regarding computational efficiency and could not notice a remarkable difference. Therefore, unless otherwise stated, the computational results are based on a MIPgap tolerance of 0.0000.
Warm start For models m3 and m4, we provide CPLEX with a starting solution. The starting solution is constructed by simply reading the sequence of the tasks as given in the instance file. For model m4, we also track the according times and make sure that the times and intervals match. In the starting solution, public transportation is used on all trips. Moreover, after each iteration we store the solution and provide CPLEX with a MIP start. The MIP start will be infeasible but values can be stored for a possible repair.
Graph reduction Initially for model m4, we duplicate each leg every \(\alpha \) minutes. Assuming that we have a planning horizon of 12 hours and discretize time in steps of 15 minutes, we end up with 48 duplicates of one leg. However, these legs are very similar to each other or even equal as the time periods t may cover various hours. Therefore, in order to reduce the size of the graph, we merge legs with equal weights.
Table 2 gives an overview of the size of the graphs. The table gives information on the introduced models for an increasing number of users (P = 20, 50, 100, 150, 200, 250, 300). For m1 and m2, the underlying graph has the same size as only the preference and cost values on the legs are changing. Row ’\(\overline{V'}\)’ gives the average number of nodes, ’\(\overline{R}\)’ the average number of trips, and row ’\(\overline{L}\)’ the average number of legs in the respective graphs. We observe that the underlying graphs of the first two models have a moderate number of legs as the sequences are predetermined. In models m3, m4, and m4b, the sequence is subject of determination which leads to an increasing number of connecting legs, which is increased even further when time dependency is considered in models m4 and m4b. Row ’m4,m4b+GR’ shows the number of the legs in the graph after the graph reduction.
Table 2
Average number of nodes (\(\overline{V'}\)), trips (\(\overline{R}\)) and legs (\(\overline{L}\)) for models m1, m2, m3, m4, m4b and an increasing number of users \(P=20,50,100,150,200,250,300\)
\(P=\)  20  50  100  150  200  250  300  

\(\overline{V'}\)  95  242  476  714  951  1179  1422  
\(\overline{R}\)  31  76  147  218  287  358  427  
\(\overline{L}\)  m1, m2  416  1188  2612  4340  6315  8734  11,038 
m3  947  4190  13,394  27,756  46,503  70,492  99,462  
m4,m4b  13,479  41,077  93,079  150,877  216,989  276,626  356,713  
m4,m4b+GR  3984  13,995  34,780  61,310  92,790  127,155  167,645 
5.3 Algorithmic tests
In this section, we study the computational efficiency of the introduced variants of the model. We start by comparing the four models (m1, m2, m3, m4) in their basic form, i.e. without adding valid inequalities or using the branchandcut algorithm. Afterwards, we analyse the impact of valid inequalities on model m3. Finally, we focus on solving the most challenging model m4. We compare the reformulation of m4 to m4b, i.e. if the branchandcut algorithm comes with any improvements in computational efficiency. We aim to detect the enhancements by adding valid inequalities, using the branchandcut algorithm and choose the best framework (out of the two introduced) to solve model m4b.
5.3.1 Comparison of models m1, m2, m3, and m4
In a first step, we compare the four models regarding their run times. Table 3 shows the average computational time in seconds needed to solve an instance group. We first look into results without any valid inequalities or cut generation, given in the rows m1, m2, m3, and m4. The models are embedded in the \(\epsilon \)constraint method and enumerated by setting either the cost function as the objective (cost) or the user preferences as the objective (pref). Results are given for instance sets for which we were able to solve all 10 instances. Run times for m1 and m2 are very short. We can solve realworldsized instances with 300 users in less than 5 minutes. For m1, the direction of the \(\epsilon \)constraint method has no impact. In the case of m2, setting pref as first objective results in shorter run times. Models m3 and m4 are ’harder’ to solve. For model m3, we can see a significant increase in the average run times for the instance group with \(P=50\). The largest instance set we can solve comprises 100 users in the case of m3. Adding valid inequalities reduces computational times by a factor of 3 for this instance size (m3VI) and \(P=100\). With m4 we cannot solve any complete instance set. We will go into more detail on m4, its possible extensions and the respective results later. Using the best setting of the proposed branchandcutbased algorithm, we are able to enumerate the whole Pareto frontier within about 3,000 seconds, on average.
Table 3
Average computational times in seconds for models m1, m2, m3, m3VI, m4, m4bVIBnCBiO and an increasing number of users \(P=20,50,100,150,200,250,300\) for both directions (cost, pref) in the \(\epsilon \)constraint method
\(P=\)  20  50  100  150  200  250  300  

m1  cost  0.3  3.0  15.8  45.2  88.1  163.4  247.3 
pref  0.3  3.0  15.8  43.6  85.1  160.9  238.5  
m2  cost  0.7  5.5  35.4  92.0  188.2  319.8  428.5 
pref  0.5  4.4  29.8  79.8  165.3  288.2  399.9  
m3  cost  7.4  498.5  17,707.6  –  –  –  – 
pref  7.7  1037.3  –  –  –  –  –  
m3VI  cost  8.0  480.4  5743.2  –  –  –  – 
pref  8.5  874.5  5577.5  –  –  –  –  
m4  cost  –  –  –  –  –  –  – 
pref  –  –  –  –  –  –  –  
m4bVIBnCBiO  cost  3511.9  –  –  –  –  –  – 
pref  2730.7  –  –  –  –  –  – 
Table 4 summarizes the average number of Pareto optimal solutions per instance set. The number of solutions is moderately increasing with number of users P. Comparing m1 and m3, we see almost the same number of Pareto optimal solutions on average per instance set. If we compare the increased cost in computational complexity coming with m3, we could argue that dissolving the sequences where no timedependent information is given is not worthwile. We will investigate the shape of the Parento frontiers in a subsequent section in order to obtain a better understanding of the resulting solutions. Comparing m1 with m2, we can see a distinct increase in optimal solutions on the frontier, even though we only introduced timedependent cost and preferences. Finally, m4 gives by far the highest number of optimal solutions for the small instance set of \(P=20\).
Table 4
Average number of Pareto optimal solutions for models m1, m2, m3, m4 for an increasing number of users \(P=20,50,100,150,200,250,300\)
\(P=\)  20  50  100  150  200  250  300 

m1  18  73  159  250  349  464  518 
m2  34  164  346  555  767  993  1073 
m3  18  72  158  –  –  –  – 
m4  141  –  –  –  –  –  – 
5.3.2 Introducing valid inequalities for model m3
We now analyse the impact of the proposed valid inequalities (VI) in more detail. Table 5 presents the computational times in seconds solving m3 without additional information (m3) and by adding valid inequalities (21)–(27) as well as subtour elimination constraints (20) as user cuts (m3VI). We use both, costs (cost) and preferences (pref), respectively, as the ’main’ objective function in the \(\epsilon \)constraint method. Results are given for \(P = 100,150\) and listed for each instance. Row ’# solved’ shows the number of instances solved with the respective model. We can observe that for some of the instances, e.g. E_100_8, for both cost and pref, the execution time is higher with the valid inequalities than without them. However, on average adding additional information in the form of valid inequalities improves computation times by a factor of approximately 4. Even for instance E_100_2, where we were not able to enumerate the whole Pareto frontier within 12 hours with the base model, we are now able to get the frontiers from either side in less than 3 hours. For the case where \(P=150\) and pref, we are able to solve all but two instances, however, all with relatively long computational times. Direction cost shows longer run times for all solved instances, whereas for two more cases, in total four, the total Pareto frontier cannot be enumerated. None of the instances with \(P=150\) has been solved without the valid inequalities. Furthermore, we were not able to solve any of the instances with \(P=200\) using m3 or m3VI.
Table 5
Average computational times in seconds for \(P=100,150\) solving m3 without valid inequalities (m3) and the same model including valid inequalities (m3VI) and having either cost (cost) or preferences (pref) set as the objective function in the \(\epsilon \)constraint method
cost  pref  cost  pref  

m3  m3VI  m3  m3VI  m3  m3VI  m3  m3VI  
E_100_0  2419  2852  3212  2628  E_150_0  TO  TO  TO  TO 
E_100_1  3329  3104  2513  2777  E_150_1  TO  TO  TO  39,507 
E_100_2  35,758  7275  TO  8504  E_150_2  TO  TO  TO  41,675 
E_100_3  3382  3544  3281  3892  E_150_3  TO  37,060  TO  20,507 
E_100_4  24,162  4177  25,159  4553  E_150_4  TO  TO  TO  TO 
E_100_5  27,186  6655  25,587  6062  E_150_5  TO  19,766  TO  14,098 
E_100_6  11,152  9814  11,403  9092  E_150_6  TO  18,352  TO  13,640 
E_100_7  24,112  9245  22,085  6880  E_150_7  TO  38,193  TO  21,112 
E_100_8  3398  5204  2685  3678  E_150_8  TO  30,083  TO  23,643 
E_100_9  22,771  5561  28,090  7708  E_150_9  TO  TO  TO  35,617 
# solved  10  10  9  10  0  5  0  8 
5.3.3 Solving model m4
We now compare different approaches for solving m4. Table 6 shows the run times for (i) model m4 (m4(\(\epsilon \))), (ii) m4 with valid inequalities (m4VI(\(\epsilon \))), (iii) model m4b with valid inequalities, and infeasible path constraints in the form of (39)(40) added through cut generation and embedded into the \(\epsilon \)constraint method (m4bVIBnC(\(\epsilon \))), (iv) the biobjective branchandcut, which is similar to the previous variant but we pass the cuts generated as constraints from one solution to another (m4bVIBnCBiO(\(\epsilon \))), (v) model m4b solved by branchandcut embedded in the weighting binary search method (m4bVIBnC(\(\omega \))), and (vi) the branchandcut used to solve m4b using the weighting binary search method and passing cuts to subsequent iterations (m4bVIBnCBiO(\(\omega \))). Again all results are given for both directions, cost and pref in the case of the \(\epsilon \)constraint scheme. In the case of the binary search, both objectives are combined in one weighting objective function. Times are in seconds. Row ’# solved’ gives the number of instances solved. Results are given for each instance for \(P=20\).
Using model m4(\(\epsilon \)) and the direction cost, only one instance is solved, using pref as the main objective, two instances can be solved within 12 hours of computation time. Adding valid inequalities (m4VI(\(\epsilon \))), we are able to increase the number of instances solved to 6 for the direction cost and to 7 for the direction pref. Still for most of the instances the run times exceed 10,000 seconds.
Moving from the model with the time variables (m4) to the entirely integer model (m4b) with cut generation, we can improve run times considerably by at least a factor of 10 (column m4bVIBnC(\(\epsilon \))). Yet, we are still not able to enumerate the whole frontier for instance E_20_9. By seizing the biobjective character of the model and handing over detected infeasible paths as constraints from one iteration of the \(\epsilon \)constraint scheme to the next, we further increase in the algorithms’ computational efficiency (m4bVIBnCBiO(\(\epsilon \))). Note that different to most works, we add the detected infeasible paths not to a cut pool but explicitly to the set of constraints. All instances with \(P=20\) can now be solved for m4. The last two columns of Table 6 show the results obtained by applying the weighting method and conducting a binary search in the objective space. It is again clearly visible, that the approach where cuts are passed on from iteration to another, enhances computation times and thus seizing the biobjective character of the models is beneficial. Nevertheless, the run times are not comparable to ’m4bVIBnCBiO(\(\epsilon \))’. The reason is that the binary search algorithm calls the solver approximately twice as often as the \(\epsilon \)constraint.
As noted, instance E_20_9 requires significantly more time for computing the Pareto frontier than all the others. The reason is that it is the only instance with \(P=20\) which has one user with three trips. The total number of trips or average number of trips per person are in line with the other instances. Thus, the maximum number of trips per user has a significant impact.
Note that we add all found infeasible paths to the set of constraints instead of adding them to a cut pool. As the number of cuts generated is relatively small and is also decreasing over time, the additional constraints are of a manageable size. However, we have tried both approaches and computational times confirmed the efficiency of our approach.
Table 6
Average computational times in seconds for each instance of \(P=20\) solving m4 using different approaches
m4(\(\epsilon \))  m4VI(\(\epsilon \))  m4bVIBnC(\(\epsilon \))  m4bVIBnCBiO(\(\epsilon \))  m4bVIBnC(\(\omega \))  m4bVIBnCBiO(\(\omega \))  

cost  pref  cost  pref  cost  pref  cost  pref  
E_20_0  TO  26,780  12,663  7,190  779  743  206  192  669  324 
E_20_1  TO  TO  TO  TO  2957  2099  455  407  1823  621 
E_20_2  TO  20,437  13,504  9339  737  793  168  159  608  192 
E_20_3  TO  TO  29,772  18,012  856  890  192  189  711  294 
E_20_4  TO  TO  TO  23,490  2447  1798  473  420  1681  560 
E_20_5  TO  TO  19,823  10,810  743  781  327  190  712  322 
E_20_6  TO  TO  31,309  26,751  1982  1557  399  369  1244  590 
E_20_7  TO  TO  TO  TO  3383  2436  628  496  2555  716 
E_20_8  TO  TO  32,790  18,522  892  948  333  256  729  414 
E_20_9  TO  TO  TO  TO  TO  TO  31,937  24,629  TO  TO 
# solved  0  2  6  7  9  9  10  10  9  9 
The above results show that ’m4bVIBnCBiO(\(\epsilon \))’ (with direction pref) is, for our problem setting, more efficient than ’m4bVIBnCBiO(\(\omega \))’. As discussed, this is mainly due to the increase in the number of MIPs that have to be solved. Table 7 compares the run times of the two approaches for \(P=50\). The table shows similar results as above. The \(\epsilon \)constraint method is able to solve more instances and also, if the instance is solved by both approaches, results in shorter computation times.
Table 7
Average computational times for each instance for \(P=50\) solving m4b by branchandcut embedded in the \(\epsilon \)constraint method (m4bVIBnCBiO(\(\epsilon \))) and in the weighting binary search algorithm (m4bVIBnCBiO(\(\omega \)))
m4bVIBnCBiO(\(\epsilon \))  m4bVIBnCBiO(\(\omega \))  

E_50_0  16,712  31,100 
E_50_1  TO  TO 
E_50_2  TO  TO 
E_50_3  13,759  22,657 
E_50_4  5876  13,954 
E_50_5  41,764  TO 
E_50_6  TO  TO 
E_50_7  TO  TO 
E_50_8  4746  7907 
E_50_9  TO  TO 
As we have seen, it is beneficial to exploit the biobjective nature of the underlying optimization problem by using previously generated cuts in subsequent iterations. In Fig. 2, we show the number of cuts added at each iteration for one chosen instance, namely E_20_0. Figure 2a and b shows the results for the \(\epsilon \)constraint method, first without adding the cuts as constraints at each iteration and then by using the generated cuts in the respective submodels. Figure 2c and d gives the number of cuts added at each iteration for the weighting method conducting a binary search. As we can see, solving each subproblem individually generates a much higher number of cuts at each iteration, whereas in the other case, where we propagate cuts from iteration to iteration, we drastically reduce the cuts added at each subproblem. This is valid for both methods. Moreover, by comparing Fig. 2b and d, we see that the binary search method actually produces fewer cuts in later iterations. The reason is that the binary search method detects solutions, where infeasibility needs to be proven. This also results in two times more iterations for this method. Nevertheless, we can clearly observe that for either approach, the additional information from prior iterations has a remarkable impact on cut generation iterations.
Table 8 gives the number of cuts added per iteration on average for both the \(\epsilon \)constraint method as well as the binary search approach for each instance in the set with \(P=20\). We show the case where each iteration is using only the current information (m4bVIBnC(\(\epsilon \)), m4bVIBnC(\(\omega \))) and where we use information in the form of cuts added as constraints from prior iterations (m4bVIBnCBiO(\(\epsilon \)), m4bVIBnCBiO(\(\omega \))). We can clearly see that without additional information we use up to 100 times more cuts. As discussed prior, the binary search method has a lower average number, but more iterations are conducted.
Table 8
Average number of cuts added at each iteration for instances with \(P=20\) solving m4b by branchandcut embedded in the \(\epsilon \)constraint method (m4bVIBnC(\(\epsilon \))) or the weighting binary search (m4bVIBnC(\(\omega \))), and by adding detected infeasible paths constraints to the model (m4bVIBnCBiO(\(\epsilon \)),m4bVIBnCBiO(\(\omega \)))
\(P=20\)  E_20_0  E_20_1  E_20_2  E_20_3  E_20_4  E_20_5  E_20_6  E_20_7  E_20_8  E_20_9 

m4bVIBnC(\(\epsilon \))  120.0  205.1  180.2  223.0  227.5  179.1  208.3  189.8  179.8  1694.9 
m4bVIBnCBiO(\(\epsilon \))  1.3  3.3  2.1  5.2  7.6  6.8  7.9  4.3  3.2  70.2 
m4bVIBnC(\(\omega \))  49.8  105.0  68.6  94.1  109.7  67.3  89.6  97.7  63.0  – 
m4bVIBnCBiO(\(\omega \))  1.4  2.4  1.2  1.5  4.0  2.9  4.5  2.2  1.6  – 
×
5.4 Managerial insights
We briefly discuss managerial implications. We start by looking at the respective Pareto frontiers for a chosen set of instances. Then we continue by studying different MOT compositions when solving different variants of the model. Note that the models provide the decision maker with a range of tradeoff solutions. Based on this solution pool, the decision maker derives actions and takes the best solution fitting to their requirements.
5.4.1 Comparison of Pareto frontiers for models m1, m2, m3, and m4
Figure 3 shows the Pareto frontiers for instances E_20_0 and E_20_9. The xaxis represents preferences, yaxis cost. Note that for both instances only three frontiers are visible. This is because the frontier of m1 is hidden behind m3. For these small instances, the additional freedom to choose sequences of tasks and trips is not giving any improvement to the model. Frontiers for m2 are similar in their shape for both instances and, however, slightly differ in their relation to the other curves, especially to m3(m1). Introducing timedependent values for m2, lower (better) overall preferences but higher cost are obtained, visible as a shift to the left on the xaxis and a shift upwards on the yaxis. The increased cost comes from the additional time needed during specific daytimes. Note that we usually have a \(\beta > 1\), meaning that we rarely decrease the driving time compared to the base scenario (except for public transportation, where we assume shorter cycle times for, e.g., rushhours). For m4, the length of the frontier exceeds all the other curves. It is clearly visible that with timedependent preferences and cost as well as flexible sequences, we have a greater set of Pareto optimal solutions. Also, the curve is shifting to the left corner, meaning that we have better overall cost as well as preferences. The average cost and preference values for instances with \(u=20\) are: 505 and 2,878 for m1, 548 and 2,272 for m2, 505 and 2,878 for m3, 476 and 1,591 for m4, respectively. Concluding, we can say that time dependencies do have a great impact when solving the biobjective multimodal carsharing problem. Furthermore, we observe that only dissolving the fixed sequence does not come with high improvements, but in combination with time dependencies a greater amount of solutions as well as lower cost and better user satisfaction are obtained.
×
5.4.2 MOT assignment for models m1, m2, m3, and m4
Finally, let us have a closer look at the MOTs assigned. We analyse the number of trips covered by each MOT (car, bike, public transportation), for two instances, namely E_20_0 and E_20_9, for all four models m1, m2, m3, m4. In Fig. 4, we show the respective Pareto frontier for the four models and include the number of trips taken by each MOT for the respective Pareto optimal solution. Note that the number of trips that are covered by a car does not have to be equal to the number of cars used in total as a car might take more than one trip during a day.
Starting with m4, we observe a similar development for both instances for all MOTs. With increasing (worse) preferences, and decreasing cost, we gradually assign more cars and less bikes. The number of trips taken by public transportation is more or less constant. Thus, most costefficient, considering time dependencies, are car trips; best preferences give bike trips. A car is, in our instance set, the fastest mode of transport. As we include time in the cost function, this also makes cars often the cheapest option. Moreover, our study gives relatively good timedependent preference scores to bikes, as it is, e.g., good in rushhours to avoid congestion or overcrowded public transportation. This of course has a great impact on the resulting tendencies in the final results.
For the other models, the picture is slightly different and instance dependent. Generally, we can say for m1, m2, and m3 the number of trips taken by bike is decreasing with lower cost and higher (worse) preferences. The number of trips taken by public transportation is increasing with higher (worse) preferences and lower cost.
Comparing the extreme points of all Pareto frontiers for all models regarding their composition, we can conclude: for m1 and m3 we always assign more cars and public transportation to the cost optimal solution (except for one instance for m3); the number of trips taken by public transportation and cars decreases with higher cost but better preferences. Bikes are preferred by the preference optimal solutions, and increase with less cost. Also for m2 we can observe that the number of bikes assigned is decreasing with increasing cost and lower (better) preferences. The opposite holds for public transportation. We can figure an unchanged level of trips being assigned to public transportation for m4. For m4, lower cost and higher (worse) preferences lead to more cars assigned and, conversely, more bikes are assigned with an increase in cost, and decrease in preferences.
×
Table 9 provides a better overview of the MOTs assigned to trips for each instance set and model. The numbers are given as averages over all instances within an instance set. Rows ’av’ provide the average of the average number of trips by the respective MOT (car, bike, public). ’min’ gives the average of the minimum number of trips conducted by the respective MOT, and ’max’ gives the average maximum number. The results are organized by model (m1, m2, m3, m4), MOTs, and number of users \(P=20,50,100,150,200,250,300\).
Generally, we observe that bikes are very often assigned and used for the highest number of trips on average. m3 assigns about the same amount of cars and public transportation. m2 always shows the highest number of trips taken by public transportation. Thus, by having the choice between MOTs for a trip with a fixed sequence, public transportation is preferred. m4 has a very high number of trips taken by bikes.
Note that the composition of the mobility offers varies a lot among the models. Furthermore, the difference between the minimums and maximums of the assigned MOTs is usually very high, which means that the solutions are changing considerably over the course of the Pareto frontier. This means that, from a decision makers perspective, considering the proposed tradeoffs and variants of the problem has a big impact on the MOTs used in a mobility system. Assigning different MOTs influences the usercentred objective to a great extent. With this results we can confirm the relevance of this study and conclude that it is highly beneficial to consider not only cost but also userpreferences when operating a shared mobility system.
Table 9
Average values of average number of MOT assigned to trips (av), minimum (min) or maximum (max) for models m1, m2, m3, m4 for an increasing number of users \(P=20,50,100,150,200,250,300\). Considered modes of transport are car, bike and public transportation
P  m1  m2  m3  m4  

Car  Bike  Public  Car  Bike  Public  Car  Bike  Public  Car  Bike  Public  
av  20  7.7  11.7  11.4  2.2  11.6  17.1  8.1  10.5  12.1  6.3  20.0  4.5 
min  4.5  4.7  6.8  0.8  5.0  11.5  4.7  3.9  7.5  1.8  12.1  2.5  
max  10.6  19.3  15.9  4.5  16.8  23.6  10.9  18.3  16.4  14.6  26.3  6.8  
av  50  23.4  29.9  23.0  3.1  27.9  45.3  23.3  27.6  25.3  21.6  45.0  10.0 
min  11.0  11.5  14.4  1.8  11.2  29.1  11.8  9.1  16.4  5.3  29.8  5.1  
max  33.9  50.6  32.3  6.5  43.6  61.1  34.9  46.2  34.9  41.0  62.0  14.5  
av  100  47.1  54.2  45.3  5.9  54.2  86.5  47.3  54.0  45.4  –  –  – 
min  22.5  20.8  30.1  2.9  19.9  54.1  23.8  19.9  31.0  –  –  –  
max  71.7  93.9  57.0  13.2  82.8  120.0  72.0  87.9  61.4  –  –  –  
av  150  72.7  82.7  62.2  10.8  81.4  125.4  66.4  86.9  64.8  –  –  – 
min  37.5  34.3  41.8  6.4  32.7  82.3  33.5  35.5  45.6  –  –  –  
max  106.1  138.2  79.4  21.0  121.0  171.4  102.4  136.5  86.4  –  –  –  
av  200  94.6  108.6  83.9  15.4  107.4  164.3  –  –  –  –  –  – 
min  48.5  39.5  55.1  10.3  40.1  105.4  –  –  –  –  –  –  
max  142.1  183.3  107.0  25.3  163.1  227.3  –  –  –  –  –  –  
av  250  120.0  137.0  101.2  20.9  137.1  200.3  –  –  –  –  –  – 
min  62.2  53.0  65.3  14.3  51.5  129.5  –  –  –  –  –  –  
max  177.7  230.4  130.4  37.7  201.8  279.6  –  –  –  –  –  –  
av  300  131.2  163.8  132.5  19.6  163.2  244.7  –  –  –  –  –  – 
min  70.3  62.7  88.4  13.8  57.8  158.5  –  –  –  –  –  –  
max  194.7  268.7  171.9  36.6  239.7  347.3  –  –  –  –  –  – 
6 Conclusion and future work
Inspired by the change in mobility patterns, we study the biobjective multimodal carsharing problem where we assign modes of transport to trips as well as cars and user routes. As objectives, we consider costs and usercentred preferences. Both objectives are, depending on the variant of the model, studied with time dependencies. We model different cost/times as well as preferences during a day, as people might want to avoid driving through rushhour by car. We introduce four different variants of the model where we gradually dissolve a fixed sequence of tasks and trips as well as introduce the effect of the timedependent values. The increase in flexibility in the model comes with an increase in the complexity as well as an increase in the number of Pareto optimal solutions. Therefore, we reformulate the last variant, without fixed sequences and time dependencies, to a purely integer model and propose a branchandcut algorithm. We show that our branchandcut algorithm can enumerate the Pareto frontier for prior nontractable instances within seconds. We embed the algorithm into two biobjective frameworks, namely the \(\epsilon \)constraint method and a weighting binary search method. We show that adding previously detected infeasible path constraints to subsequent iterations reduces computational times considerably. In our computational study, we observe that only dissolving the fixed sequence does not come with high improvements. However, in combination with time dependencies, a greater amount of solutions as well as lower cost and better user satisfaction is obtained. Moreover, we observe that the solutions change significantly along the Pareto frontier. This confirms the relevance of this study. We conclude that it is highly beneficial to consider not only cost but also userpreferences when operating a shared mobility system.
Even though we are able to show a significant enhancement in computational efficiency for a set of instances, our approach has limitations. Enumerating the whole Pareto frontier for instances with users having more than two trips throughout a day seems challenging. Thus, future work should tackle this issue by focusing on the development of a separation algorithm adjusted to these specific characteristics. Moreover, specific matheuristics where the relative MIPgap is increased or the \(\epsilon \) value adapted may lead to promising further improvement in run times. Furthermore, the development of metaheuristics should enable an increase in computational efficiency for the proposed problem. Finally, as this work only optimizes average scores of preferences, a minmax approach is planned for future work in order to improve the integration of preferences on a user level.
Acknowledgements
This work has been partially funded by the Climate and Energy Funds (KliEn) under Grant Number 853767. This research was funded in whole or in part by the Austrian Science Fund (FWF) [P 31366]. For the purpose of open access, the author has applied a CC BY public copyright licence to any Author Accepted Manuscript version arising from this submission.
Declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.