Travel websites like Google Maps promise the seamless creation of multimodal itineraries according to individual traveler preferences. The engines of these websites are based on efficient techniques of mathematical optimization and can search multimodal itineraries in negligible runtime as long as the number of traveler preferences is small. However, due to the large number and variety of mobility services, the solution space of multimodal itineraries is often complex. Hence, the search process is not transparent to individual traveler, and it is hard for them to assess the impact of their preferences on the set of created multimodal itineraries. In this position paper, we propose to make the search of individualized multimodal itineraries more explainable. Demonstrating the idea of solution sampling and using a large data set of multimodal mobility services, we derive information on the solution space and demonstrate how these can support travelers in the adaptation of their preferences and in the creation of a set of individualized itineraries. 1 Management Science Group, Otto von Guericke University Magdeburg, Universitätsplatz 2, 39016 Magdeburg, Germany
In recent years, the number and variety of mobility services has risen considerably.
Especially innovative mobility services such as bike, car and ride sharing services have
emerged and complement traditional mobility services such as scheduled trains and
buses. Following recent mobility surveys, travelers expect a reasonable choice of
itineraries created from their individual preferences such as travel time, price, number of
transfers, mode, waiting time and walking distance [
Travel websites such as Google Maps promise the seamless creation of a set of
individualized itineraries, but usually remain very simple in discovering and considering
individual preferences. The reason is that the search of multimodal itineraries requires
quantifications of traveler preferences. Then, these can be considered through
constraints of established mathematical models and be solved with efficient solution
techniques of multimodal network search. However, state-of-the-art solution techniques are
limited in the number of preferences they can consider efficiently. Delling et al. [
With regard to the consideration of multiple traveler preferences, from a
mathematical-optimization point of view, hierarchical objective functions are common. These
functions optimize for one objective first (e.g. minimize travel times) and focus on
secondary objectives subsequently (e.g. minimize the number of transfers). However, as it
is well-known for hierarchical objective functions, depending on how tight the
constraints are, there may be either no feasible solution at all or a very large number of
solutions [
In this position paper, we propose the idea of the individualized creation of multimodal travel itineraries. Based on efficient mathematical modeling and solution techniques and using a large data set of German mobility services, we demonstrate the potential and limitations of “black-box” mathematical optimization and discuss how to include more complex traveler preferences. With solution sampling, we present a simple idea to identify characteristics of the solution space and empower travelers to restrict or enhance their preferences interactively. 2
Figure 1 illustrates the common way of searching multimodal itineraries. Given
formalized traveler preferences, a multimodal routing algorithm such as REGL-CSPP,
introduced by [
We propose a data-driven decision support system that uses solution sampling in conjunction with searching multimodal travel itineraries. Figure 2 visualizes our idea: By systematically re-running a multimodal routing algorithm, we retrieve valuable meta-information about the solution space characteristics, which can be used to explain the solution space to travelers as well as empower them to reduce/extend the retrieved set of itineraries. This implies identifying promising solutions on the one hand, but also partially infeasible solutions on the other hand, allowing the traveler to reflect on the importance and impact of their preferences. For instance, in case the traveler sets the upper bound for travel time to 4 hours, a favored solution taking 4 hours and 5 minutes might still be relevant. In addition, solution space characteristics can be used to derive typical relationships between preferences. For instance, for some types of itineraries, there might be a linear relationship between travel time and price, which can help the traveler to adjust their preferences systematically.
In the end, the proposed decision support system could be integrated in a multimodal routing app to enable an explainable search of multimodal itineraries for the traveler. In the following, based on real-world multimodal mobility service data from Germany, we will detail our idea of a more explainable search through solution sampling. 3
To guide travelers in their search of multimodal travel itineraries, we focus on retrieving solution space characteristics through solution sampling. Solution sampling builds on the repeated execution of efficient solution techniques for the multimodal search of itineraries (in our case: REGL-CSPP). Our framework consists of four steps: 1. Two-dimensional analysis of each traveler preference 2. Merge of the created sets of itineraries 3. Removal of dominated itineraries 4. Dynamic reduction/extension of the set of itineraries
For step 1, given a request for a specific source and a target of an itinerary, for
all parameters ∈ with being the set of quantifiable traveler preferences, we identify
“reasonable” parameter intervals [ , ]. The lower bound of the parameter can be
easily determined by running REGL-CSPP without any constraints. Algorithmic details
are provided in [
Position Paper: Explainable Search of Multimodal Itineraries 153 to identify the two-dimensional solution set , , we set the parameter “travel time” as the objective and rerun REGL-CSPP with different upper bounds for the parameter “price” starting with the identified upper bound . By iteratively softening the restriction (e.g., by dividing the interval of price into equally sized buckets) and re-running REGL-CSPP with that specific restriction, we can identify itineraries with different prices that are all optimal with regard to travel time.
For step 2, we merge all itineraries searched based on two-dimensional sets
, ∀ , ∈ | ≠ into one comprehensive set . Then, in step 3, dominated
itineraries are removed. An itinerary dominates an itinerary if is no worse in any
parameter ∈ than [
For step 4, the set of non-dominated itineraries is reduced if needed. In case the
number of created itineraries in is sufficient, i.e. it is in a predefined interval
[ , ], e.g. [
To demonstrate our approach of systematic sampling, we create information about the search space for multimodal itineraries between several major cities in Germany. The experimental setting considers a large amount of data on current mobility services and different modes of transportation as well as innovative ridesharing services such as “BlaBlaCar”. Modelled as a time-expanded network, the entire network for one specific day of operation consists of approximately 6 million nodes and 200 million arcs. As exemplary traveler preferences, we consider travel time, price and number of transfers. We estimate price information for public transit systems, as these are not given in their respective published GTFS data. We analyze long-distance trips between large cities in Germany assuming a start time for the itinerary at 9 am.
As result of solution sampling, Figure 3 shows information on the relationship between the preferences “price” and “travel time” as well as between “price” and “number of transfers” for long-distance trips between Berlin and Munich, Nuremberg and Hamburg as well as Dortmund and Berlin. For price versus travel time, to ensure the comparability, we normalized the parameters between 0 and 1. A travel time of “0” indicates the itinerary with the smallest occurrence for travel time, whereas a travel time of “1” represents the itinerary with the highest occurrence for travel time. e c ir P
Travel Time
Number of Transfers
Significant differences in the relationship between the parameters travel time and price can be discovered. For itineraries between Berlin and Munich (indicated by triangles), a traveler has to invest quite a significant amount of time until large cost savings can be realized. In comparison, prices are much lower when investing only slightly more travel time for traveling between Dortmund and Berlin (indicated by circles). Between Nuremberg and Hamburg (indicated by rectangles), a roughly linear relationship between travel time and costs can be discovered.
Minor differences can be seen for the relationship between the parameters “number of transfers” and “price”. For itineraries between Berlin and Munich as well as between Dortmund and Berlin, a traveler has to be willing to transfer at least once in order to achieve substantial price savings. Further transfers do not result in significant savings. For itineraries between Nuremberg to Hamburg, travelers realize the highest savings in case of transferring twice.
The identification of these aggregated relationships between relevant traveler preferences can be communicated to travelers and help guiding them in the solution space. Thereby, we empower travelers to interactively individualize the set of itineraries. For instance, it can be of high relevance for a price-sensitive traveler to have an idea which of their individual preferences has a high impact on the price for the respective itinerary and thereby help assessing which of the preferences should be relaxed/restricted to reduce/extend the set of itineraries under investigation. In recent years, there has been tremendous progress in the field of searching multimodal travel itineraries. While the search of individualized itineraries for a given and limited set of preferences is possible, this often comes as a black-box search, and it is hard for travelers to interact with the search engine in a way that can help finding more individualized itineraries. We propose the idea of solution sampling to benefit from the stateof-the-art algorithms in network search while deriving characteristics of the solution space that can be helpful to make the search process more explainable to travelers.
Although search engines and mathematical optimization form an important part in
finding individualized multimodal itineraries, a more comprehensive framework is
needed to provide travelers and customers in general with more “white-box” solutions.
Alt et al. [