© M. El Moufid et al., published by EDP Sciences, 2019

1 Introduction

In these modern times, roads congestion can be considered as one of cities major problems today. This “scourge” strikes almost every major metropolis in the world, affecting both the so-called developed countries, as well as those considered still under development. In addition to its negative impact on citizens accessibility in cities, traffic congestion has a negative impact on cities air pollution and its economic development.

In order to cope with these kinds of problems that are increasingly causing complications in various cities around the world, several researches, technical and logistical means are being implemented to investigate potential solutions to reduce their harmful effects.

The current trend is to encourage people to use different modes of public transport in cities [1], taking advantage of advances in information and communication technologies [2]. This will reduce the toxic emissions of private vehicles and the duration of journeys in cities by minimizing delays due to congestion or the search for car parks [3].

In this sense, several solutions are focused on determining optimal multimodal paths to go from a starting point to a desired destination inside a city by using combinations of various available means of transport. These algorithms make it possible to consider at least two possible transport modes and to determine the optimal combination for each trip between two points [4]. For example, the iterative algorithm proposed by Angelica and Giovanni [5] considers a public transport network − composed of metro and other modes − that takes into account the possibility of changing modes of transport as well as the associated constraints for solving the problem of the shortest multimodal path.

However, during a user's journey, several parameters can change and have an impact on both the duration and cost of each travel arc; including the traffic situation on each roadway, the availability of each car park in question, as well as any unforeseen events (accidents, breakdowns, etc.) in the considered multimodal network [6].

To take account of these variations, the algorithm must have a general real-time view of the state of each considered mode of transport. This will allow it to update multiple parameters, such as the estimated cost and duration for each arc, etc. and to subsequently generate the optimal path for each user.

An efficient multimodal traffic management system should therefore allow it users to define paths that best corresponds to theirs requests while taking into account the real time situation of the selected modes of transport. This system can also offer it users a set of preferred criteria [7]. Once a user destination and multimodal network preferences had been set, he receives a list of the paths that are regularly updated along the journey in order to consider the different real time changes in parameters of the multimodal network.

2 Related works

Up to date, a variety of academic and commercial solutions have been proposed in order to improve urban mobility by firstly exploiting more than one mode of transport (i.e. taxi, bus, tramway, metro) and secondly by optimizing the lookup for vacant spots in parking areas [8]. However, few solutions have been proposed to route users from their location to a desired destination point and provide parking availability.

The Mobility Recommender System proposed by Sergio and Silvia [9] can be considered as one of the most effectives solutions that manages the multimodal urban transport problematic by taking into account constraints related to the availability of car parks. This system accompanies travelers in their decision-making process by generating different ranked lists of possible multimodal door-to-door routes including parking spaces. The paths parameters (cost, duration, etc.) are determined by exploiting heterogeneous data sources. Data that are concerning different modes of public transports are considered static while those that are describing the availability of parking are considered dynamic [9]. The proposed solution couldn't consequently be able to consider the various disturbances that may occur either on the road network or on a public transport line.

Concerning the algorithmic aspect of the problem, special attention, in the literature, has been given to the two-criteria problems using exact methods such as Branch and Bound [10–12] and Dynamic programming [13,14]. Other metaheuristic approaches have shown a great robustness to find very good multimodal paths in a static or a dynamic environment [15].

These resolution approaches, even if they are effective for small size problems, there is no exact procedure that is effective, given the simultaneous difficulties of the N-P hard complexity and the multicriteria aspect of the problem.

By cons, several studies have been devoted to solve the problem separately by studying one of the aspects of multimodal urban transport management. In our work, we cite three main research topics on the theme:

• The Query of the shortest path between two nodes in a road network.

• Smart Parking Management.

• Traffic road Management

2.1 Query of the optimal path in multimodal transport network

While studying networks, one of the most encountered problems in this research field is the search of the shortest path, especially in telecommunications and logistics [16]. Thus, if the Dijkstra algorithm is considered one of the oldest and most widespread problem-solving algorithms, a comparative study between a few algorithms used to determine the shortest path shows the efficiency of the algorithm A* [17].

However, in the case of multimodal transports, the studied networks are more complex since they contain different arcs, where each one is referring to an urban transport mode [18].

Therefore, a genetic algorithm is developed to allow the user to plan his itinerary and to update it during his travel (depending on the real-time data). This genetic algorithm is defined in Figure 1.

To take into account every change in the arc parameters, the weight of each arc of the road network is updated in real time. To do so, an approach-based on both the history of GPS sensors installed on cars and the regression of the neighboring kth (kernel method)-makes it possible to predict the state of tracks and traffic [19], in order to deduce the wanted paths.

Another way to generate the shortest path in the case of urban mobility is to consider the use of a set of cars equipped with GPS, so that each driver can compare the time it took him to go from one point to another with the time it took the other drivers who used other paths, and to deduce the optimal solutions to take for subsequent experiments [20].

Fig. 1 Genetic algorithm description.

2.2 Improve the probability of finding an available parking spot

According to a study conducted at the University of California-Los Angeles in 2006, 30% of the traffic at peak hours is due to the search for a place in a parking [5]. The PGI are (Parking Guidance and Information) are designed to allow drivers to improve the probability of finding a parking space and to find the cheapest possible solution. In the case of a centralized system that manages a set of on street and/or off street parking, a multi-agent system based on negotiations between drivers and car parks [21], and managing the competitive aspect between users who have chosen the same car park [22], can be developed to achieve the best possible allocation.

The optimal allocation of a group of drivers to a set of car parks can be a considered as a deterministic problem, and the allocation of the parking spaces be can be solved by a linear program according to the logic FIFO (first request served) [23], or a heuristic (genetic algorithm) [24].

In this case, the following conditions should be verified:

• The reservation of a place can be spontaneous.

• The availability of car parking spots in real time is exactly determined thanks to the establishment of Internet-of-Things tools (sensors, image processing) [25].

However, even if the number of available places at a given time can be known using sensors and/or cameras, it wouldn't be sufficient data. In fact, to be closer to reality, the probabilistic parameters of the model should be considered. Once a destination has been determined, the driver doesn't know the parking lot with the highest probability of being free when he arrives. To determine this probability, it would be necessary to gather ahead some few data such as: the user's current position, his destination and the current availability of car parks. Then, based on these elements and previous statistics, the system should be able to estimate the arrival time of the user to the desired parking [26,27].

2.3 Traffic congestion management

To manage the congestion in real time and to allow users to follow the optimal path to reach their destinations using IoT tools, the vehicles can communicate with both each other's and with infrastructures (Road Station Unit, Base Station, etc.). Thus, vehicles can create a large network where each one is considered a node. Such kind of network is called: Vehicular Ad-hoc Network (VANets).

To optimize the dissemination of messages concerning the traffic situation on each arc of the road network, several solutions have been proposed [28] to exploit the information concerning the state of roads infrastructure. We summarize in Table 1.

3 Proposed model

3.1 Definition

In our study, we first consider a multimodal network consisting of the following modes of transport: private transports (i.e. user cars), tramways and trains.

Then, in order to switch from a private transport mode to another, users will have to park their cars in the closest parking lot to their next transport mode station, which leads us to consider car parking lots into our study.

As for parameters, they are chosen according to each user priorities: the minimization of the cost or duration of travel, the preference for one or multiple transport modes, or the degree of flexibility in terms of the number of changes to be authorized by the user.

The process of determining and choosing the multimodal path by a user is described by the Business Process Model and Notation Model presented in Figure 2.

• 1.

  A user determines his destination and classifies the parameters according to his priorities and then sends them to the multimodal transport management system.

• 2.

  The system then determines the list of all possible paths leading to the user's destination and classifies them according to his proposed parameters.

• 3.

  The user validates the most appropriate path, and sends it to the system.

• 4.

  The system registers the choice of the user.

• 5.

  Re-calculates the routes in order to determine the optimal path, while considering the situation of each arc in real time.

• 6.

  Following the occurrence of one of these two events:

  • The expiration of a system-determined refresh duration.

  • New user's request.

• 7.

  The newly generated paths are compared to the last path validated by the user (according to the priority parameters). If one of the generated paths is more optimal, it is proposed again to the user for validation.

• 8.

  Steps 3, 4 and 5 are repeated until the user reaches his destination or requests a process shutdown.

Fig. 2 Process of the system.

3.2 System parameters

In our model, we consider an urban multimodal transport network composed of a set of car parks added to the following means of transport: the private vehicle, the tramway, the train and the possibility of walking.

Each arc of the network can be characterized by the duration a user needs to browse it, and the associated cost to pay (Tab. 2). Some of these data are gathered statically such as timetables of the public transports passage or dynamically as when it requires the driving time on an arc.

The objective functions of the model depend on the priority parameters of each user. For example, a person who wants to reach an urgent meeting in the city center will prefer the optimum path in terms of reliability and duration of the trip even if it will make him pay more. A person who does not like to drive his own vehicle in areas where the traffic jam rate is high will opt for the routes whom arcs are public transport.

The objective of this system is therefore to optimize a multi-objective function while respecting the constraints of both the multimodal network and the users. The system will have as inputs the status of the traffic on reach real time and the availability of each parking lot, and will allow each user having entered his preferences to have the list of paths classified according to his choices.

3.3 Model formulation

Let G = (V, E, M, P) be the network graph under consideration, where V is a set of vertices in the multimodal network. E is a set of edges, corresponding to all possible transportation paths. M is a collection of transportation modes and P is a set of parking spaces considered in the graph.

Let P_a be a path from o to d (o, d ∈ V). Given a vertices j, the forward star and the backward star of j are denoted, respectively by and .

Symbol description:

• x _ijm : Binary variable indicating whether the arc (i, j) belonging to mode m is used.

• : Cost function of the arc (i, j) with mode according to the criterion l_k .

• : Cost function of the transfer from mode m to mode n at node i according to criterion l_k .

• : Cost function of the path starting at point i belonging to mode m and stopping at point j belonging to mode n

• C_p : Cost of using parking p.

• x_p : Binary variable indicating whether the parking p is taken.

• : Binary variable indicating changing travel mode from mode m to mode n at node i.

G = (V, E, M, P) is a multimodal transport network which includes cost functions according to a set of L criterions; L = {l ₁, l ₂,...}. let l ₁ be the duration criterion, l ₂ the cost criterion for example. Other criterions can be considered according to the user preferences. The decision variables are x_ijm , x_p , and . The multi-objective optimization model with the goal of L = {l ₁,l ₂,l _3,…} criterions is as follows: S.T:(1) (2)

The first objective function is to find the optimal paths in terms of duration, while the second objective function is to propose the optimal paths interms of monetary cost.

The fisrt constraint ensures that the obtained path goes from the origin o to the destination d.

Constraint (2) ensures that the predecessor to a private mode arc, is a private mode arc too.

4 Proposed approach

A multimodal route choice can prove to be a much more complex task with respect to a simple car route. In fact, travelers could find themselves suffering from an overload of choices since too many options should be evaluated. The potential availability of real-time information may help to streamline this process by providing necessary parameters of each multimodal arc. Moreover, in the literature on decision support system for traffic and transportation optimization, we encountered some solutions whereas the proposed mobility suggestion contains information about the expected availability of the parking, and the troubles they may occur on the transport network.

The solution we propose in this work is composed of three subsystems detailed in Figure 3 and communicating with each other: The User, the Data Generator and the Calculator.

Fig. 3 Architecture of the proposed system.

4.1 The user

This entity represents the interface between the set of the users and the two other components of the system: the “Data Generator” and the “Calculator”. It is responsible of the user identification task, location of their actual locations, destinations and preferences. This data could be used by the “calculator” to first determine the possible multimodal paths and secondly to rank the solutions generated according to the user preferences

A USER entity would also be a source of road traffic data for the “DATA GENERATOR”. Indeed, while traveling in a private vehicle, a user remains in communication with the DATA GENERATOR which allow the Road Traffic Agent to update the parameters of each road arc. The communication process is detailed in the following paragraph (THE ROAD TRAFFIC AGENT).

4.2 The data generator

In this work, we propose a system that relies on heterogeneous information sources to gather the needed arcs parameters to determine different potential suggestions to a user request.

This process requires the development of a software module suited to model, collect, classify and generate the information needed by the system, mainly gathered from the Train-Agent, the Parking-Agent, the Tramway agent and the Road Traffic Agent and communicated to CALCULATOR via Interface Agent.

The interface agent: Based the data generated by the other agents of the subsystem data generator, the interface agent entity manages these heterogeneous data to make them exploitable by the CALCULATOR.

The interface agent is provided with a memory that, according to the possible paths generated by the computer, allows first the allocation of a dynamic sub-memory containing the concerned arcs structured as adjacency list and second to retrieve the numerical values of the parameters of the arcs from other DATA GENERATOR agents in real time.

The design of this entity allows, according to each request, the integrating of the data retrieved from heterogeneous systems through a layer named Knowledge Layer created following each user request [33].

The Parking Agent: this entity main role is to:

• keep having a precise real-time view of the availability of city car parks.

• Predict the arrival time of each vehicle to each parking based on road state and the previous history.

• Take into account all the main events in the city [34].

The Train Agent and the Tramway Agent: are designed to provide not only the timetable of the concerned train or tramway arc, but the intended location of the train or tramway when the user is expected to use it. These predictions should be based on models that consider not only the normal transit frequency of each transit mode (train or tramway), but also any disturbance on a public transport line such as accidents, eventual breakdowns of a mode or the occurrence of a special event in the city as a football match [34].

The Road Traffic Agent is responsible for determining all the road traffic parameters required when a user is requesting the private mode. In fact, using the static data of the road map and the history of use of each road arc, this agent is able to foresee the state of the traffic, and then lists the parameters of each arc which could be traveled by the user.

To take into consideration the troubles that may occur on the road network, in particular traffic jam, road traffic accident, road works, etc., the Road Traffic Agent ask for confirmations in real time from users on a concerned road arc. For instance, based on the difference between the regular and the actual speed of a vehicle, this agent sends a list of eventual causes of this deviation to which a user can confirm or deny the origin of this delay. This road traffic management officer is used recently by several technological solutions (Waze for example) [35].

4.3 The calculator

The CALCULATOR entity is used to solve the multi-criteria and multi-objective problem concerning the optimal urban multimodal path according to a sequential process in three steps. Calculations are executed by three agents according to the following algorithm.

The Generation Agent: Generates possible multimodal paths according to the destination cited by the user. The resulting paths must meet logical and technical constraints; once a user has left his private vehicle in a parking lot, the proposed solution should no longer contain a return to private mode.

The Evaluation Agent: Determines the different parameters of each path given by The Generation Agent based Erreur de traductionon the one hand on the Data generated by “The Data Generator”, and on the hand, on the parameters set by a user.

The ranking Agent: Ranks the obtained solutions based on both the user preferences and the parameters of the generated paths. The ranking process is based on the Pareto-Ranking approach since parameters to optimize in our study (time, cost, comfort level, etc.) conflict each other. The population (set of solutions) of generated solutions is then ranked according to a dominance rule.

The three previous agents operate according to the Algorithm 1.

5 Simulation and results

5.1 Hardware specifications

• Cache Memory: 3 MB (L3 Cache)

• Processor: Intel® Core™ i3-370M Processor 2.40 GHz*

• Memory: 4 GB (2 GB × 2) DDR3 SDRAM*2

• Memory Speed: 1066 MT/s

5.2 Simulation parameters

In our study we consider three multimodal transport networks composed of 500, 1000 and 15000 nodes (example of Casablanca in Morocco) respectively. we consider two objective functions to optimize:

• l ₁: cost.

• l ₂: Duration

The numerical data considered in our study are limited in the following intervals: l ₁ ∈ [6, 20] MDhs and l ₂ ∈ [12, 65] min.

We consider 3 levels of preferences/weights (1, 2 or 3) for each of the two criterions l ₁ and l ₂; according to the user's preferences, objectives functions are weighted and classified.

We consider two approaches to resolutions for responding to user queries. The first approach is to determine the optimal paths in three steps:

• 1.

  Determination of the optimal paths according to each of the two criteria based on the dynamic approach proposed in [36].

• 2.

  Calculation of the overall objective function. This function is a weighting of weight for the two objective functions and defined as follow:

(3)

• 3.

  Classification of objective functions obtained.

The second approach, on which our work is based, can be defined according to the three steps:

• 1.

  Determination of possible multimodal paths between origin and destination using the Direct.

• 2.

  Evaluation of the obtained paths.

• 3.

  Calculation of the overall objective function. This function is a weighting of weight for the two objective functions (cost and time). This function is defined in equation (3).

• 4.

  Classification of objective functions obtained.

Figure 4 summarizes the simulation results for the arithmetic mean of 10 queries in each of the 5 multimodal network transports.

5.3 Results and discussions

The results of the simulation in Figure 4 show that from a network of more than 1000 nodes, the second approach becomes much more efficient. In these simulations, we considered two parameters for which pareto convergence is ensured by the second approach. Similarly for reasons of simplification, we considered a simple weighting for the two objective functions (cost and duration).

The proposed approach will also make it possible to save all the possible multimodal paths between two nodes that can be used directly without making the same calculations, which will make it possible to constitute a rather important database. The approach represents a great advantage since our perspectives consist in integrating artificial intelligence to solve the problem of multimodal urban networks.

Fig. 4 Comparison between two approaches in terms of execution time.

6 Conclusions

The problem of multimodal travel assistance is a topical issue that is increasingly of concern for transport companies, as it has a direct impact on the quality of service offered to users. However, existing information transport systems are generally mono-modals, usually not considering private vehicle as a mode of transport, not offering to lookup for available parking lots, and do not provide accompaniment during travel to consider the disturbances that can occupy on the transport network.

The proposed system makes it possible to generate for users the information needed for their displacements in order to validate the most appropriate path to reach their destinations. The system accompanies the user along his journey to warn him about any disturbance that may happen on a public transport line (breakdown, power failure, etc.) or on the Road Traffic network (accident, traffic jam, etc.). These data make it possible to update the parameters of the paths and subsequently to propose new paths more appropriate to the request of the user.

In our approach, in order to be able to retrieve data from existing systems that may be heterogeneous, we propose a distributed system to define the relationships that can take place between these systems. Similarly, to deal with the interactions and interoperability of current systems, we use a multi-agent system. We therefore explain the particularities of the system, the agents involved, the interactions, communications and coordination between these agents.

The proposed approach allows, not only to consider the different modes of public transport of a city, but also integrates the possibility of using partially or totally the private vehicle and then park it in one of the car parks of the city thing that has not been integrated in most studies and system proposals.

The simulation results show the interest of adopting the second approach consisting on generating possible paths between origin and destination points, then evaluating them according to the preferences of the user before proposing the best suited to the user's request. This approach is not only a benefit in terms of execution time, but will also make it easier to include artificial intelligence for the work that will follow.

As a perspective, we propose a comparative study concerning the algorithms of solving the multi-objective and multi-criteria problems for the optimal multimodal path according to the preferences of the users based in artificial intelligence. Similarly, we propose a state of the art on data management techniques in order to be able to deduce the optimal multimodal paths from previous experiments without being obliged each time to do the calculations again.

References

All Tables

All Figures

	Fig. 1 Genetic algorithm description.
In the text

	Fig. 2 Process of the system.
In the text

	Fig. 3 Architecture of the proposed system.
In the text

	Fig. 4 Comparison between two approaches in terms of execution time.
In the text