In recent years, the number of cars is increasing worldwide. In terms of the depletion of oil resources and the environmental pollution, the development of vehicles which have better fuel efficiency and clearness is urgently needed. Therefore, hybrid electric vehicles (HEVs) and electric vehicles (EVs) have attracted a remarkable attention as the next generation vehicles which can run over saving its energy. Since these vehicles do not emit exhaust gas such as CO_2 and NOx, people have expected the possibilities of next generation vehicles including EVs to prevent environmental pollution.

According to the Strategic Energy Plan of Japan[1], Japanese government and companies try to increase the ratio of next-generation cars to 50-70% among unit sales of new cars by 2030. Furtheremore, there is a social demand to minimize the energy consumption of EVs as possible. Thus, the optimal route plannning methods with the optimal charging stands and the minimum charge quantity have been intensively studied[2],[3],[4],[5],[6],[7],[8]. Considering the characteristics of the motor of EVs, the faster you drive the EVs, the more energy it consumes. Because of this characteristic, for EVs, generally a regular route is a low energy consumption route, and highway route is a high energy consumption route. However, violating the drivers' freedom of route selection intensely, this results in disturbing comfortness of EVs and preventing EVs from expanding so that the enviromental improvement is stagnated.

Framework of the Previous Work

Based on such a background, our previous study[9]proposes a multi-objective optimization framework of navigation systems for single EV minimizing the expected value of the electricity consumption by adopting incentive approach. The incentive approach, which has been adopted in various field of research such as economics, intelligent transportation, smart grid, and so on[10],[11],[12], allows the framework proposed in previous work[9]to give flexibility of selecting preferable route candidate.

The EV navigation system proposed in[9]assumes that some route candidates, which have different properties, such as monetary cost, travel time and energy consumption, are suggested to the user, and gives proper incentive for the monetary cost of each route candidates from the view point of how lower its energy consumption is. The more incentive the EV navigation system gives to the lower energy consumption route candidates, the more users may select it on their own will. Therefore, it is expected that the EV navigation system can reduce the expected value of energy consumption of EVs without ignoring the user's freedom of selecting route.

図1: C-T digagram. Three blue plots indicate route candidates suggested to the users by the EV navigation system. The route candidates are characterized by travel cost(C), travel time(T), and energy consumption (circle radius). The lower left region (densely colored region) is more preferable for the users. In this research, we assume that the color gradation is changed linearly with the cost. Incentive makes the travel lower and the circle come into the more densely colored area, hence, the EV navigation system can reduce the expected value of energy consumption of EV.

Problem of the Previous Work

In this previous work[9], we formulate an optimization problem to derive the incentives for each route candidate. In this optimization problem, the derived incentives can be negative, which corresponds to penalty for the users who select the higher energy route candidate. But some users who are given negative incentives may refuse to use the EV navigation system, and this gives rise to loosing opportunities to reduce the energy consumption of EVs. Therefore, we should formulate another optimization problem which derive nonnegative incentives, and examine if it can provide global optimal incentives.

In addition, in our previous work[9], we present the framework which can derive proper incentives for the departure point and destination of a single-user with route selection tendency model. However, this framework do not consider how to derive incentives when the user change his/her route from the planned one along the way in some situation, such as unpredictable road blockade by traffic accident. In this situation, it is needed to decrease the energy consumption from the point around the present location of the EV to the destination. Therefore, the EV navigation system should recalculate new route candidates from the point around the present location of the EV to the destination, and incentives. These new route candidates and incentives can be calculated in the same framework as in our previous work[9], however, the EV navigation system should also calculate the incentive for the segments which the user passed from the departure point to the present location, depending on the energy which the user decreased until he arrives the present location. If these incentives for the passed segments are not appropriate, some user can misapply the EV navigation system. For example, consider the two route candidates which share the same segment until the certain point but opposite characteristics of monetary cost and travel time; earlier arrival time but higher cost, or later arrival time but lower cost. In this case, the users, who want to arrive at the destination as early as possible, should take high cost route. However, if the user takes lower cost route until the crossroad and change the route the crossroad, he/she can get higher incentives than expected, that is, the user can cheat and get extra incentives when he/she use the EV navigation system. Therefore, we must make the incentives for the ``same" passed segments the same value.

Furthermore, the EV navigation system proposed in our previous work[9], which calculates incentives for route candidates suggested to independent users, does not consider how to derive proper incentives for multiple users. Considering multiple users, since the users interact with each other, the traffic congestion may be occurred because the road condition is changed by giving incentives, and some problems such as EVs' peak-load problem are occurred at the charging stations. The impact of the change of traffic condition considering traffic congestion with the traffic flow model and the route selection tendency model has been researched[13]. Moreover, the method, which assigns optimal charging station to EVs for minimizing peak-load of EVs, has been also researched[14],[15],[16],[17],[18],[19]. The EV navigation system has to consider such impacts when it calculstes incentives for the multiple users.

In this research, extending the previous work, we propose two frameworks of the EV navigation system; a framework which allows a single-user to change the route in the middle of the way, and a framework which deals with multi-user. When the single-user changes the route in the middle of the way, the EV navigation system should propose new route candidates from the current place, and give incentive to the segments where the user passed from the departure point. Therefore, the former framework proposes how the EV navigation successively checks if the single-user has to change the route in the middle of the way, and how to calculate proper incentive to the passed segments.

図2: Grand scheme of the proposed framework

On the other hand, in the latter framework we consider the case where some users are forced to wait for charging energy at charging stations. The charging time of EVs is quite longer than that of gasoline cars. Therefore, if charging stations do not have enough chargers, sometimes users who stop at a charging station have to wait in lines to use an energy charger. When the users have to wait for charging at a charging station, they have to spend extra waiting time. In addition, in such a situation, even if they do not move their EVs until waiting, since electric systems such as air conditioners, radios, and so on work, EVs consumes extra energy. Hence, if a user selects a particular route candidate and there is a possibility that the user have to wait at the charging stand, then the tendency of such a route candidate to be selected by the user is decreased. In this research, we call such a situation ``conflict.'' Through the conflict, some users influence each other in terms of their route selection.

図3: The situation where the conflict among the user a and b occurs

In this research, considering the impact of ``conflict,'' we formulate an optimization problem which derives the proper incentives to route candidates suggessted to each user in order to reduce the expected value of total energy consumption of EVs. Mentioned above, when the ``conflict'' occurrs, some users may have to wait at the charging stands until their turns of using chargers come. What is important to consider the impact of ``conflict,'' the length of waiting time at a charging stand is varied depending on the combination of route candidates taken by each user. Hence, by noting the total energy consumption of EVs in each combination of route candidates and likelihood of the users to take each combination, we calculates optimal incentives which minimize the expected value of total energy consumption of EVs.