an edge in the previous path,then find the shortest path again of vehicles available on the road (shown in line 2 in as a new path.This process will continue until the needed Algorithm 1,where D()and l is introduced in Section number of paths is reached.In this way,these routes are very IV-B.Lo(u,v)is the number of lanes in road (u,v)). close to the shortest path but not strictly the top C shortest ● Cost.The cost()for minimum-cost maximum-flow prob- routes.IRR combines the proximity to the shortest path and lem is the travel time T()for route guidance problem. imperfection of human beings,which can be viewed as the As shown in Eg.(4).it will be a function of the traffic random routing decisions made by some local taxi drivers. flow.However,compared to cost(),T()has an extra parameter w.To solve this problem,we can first replace D.Centralized Solution w with a new parameter,the former intersection t before 1)Motivation:When the traffic is not heavy,simply using entering edge (u,v).cost()will only be used when classical guidance techniques such as GPS can handle all calculating the shortest path in MCMF(.).So if using routing requests without any congestion.So the centralized popular shortest path algorithm such as Dijkstra,SPFA route guidance in this paper focuses on the situation when the and etc..t should be already known when in need of traffic is very heavy,where large number of vehicles needs value cost(u.v).In this way,value of T((t,u,v))can be to travel on the main roads and severe traffic jams are likely used as cost(u,v)in MCMF(). to take place.In these cases,the traffic condition takes on a Extracting Paths.From the result of MCMF(),we single-source single-destination pattern.In this way,the two can execute graph traversals from source to destination, targets of our centralized solution are listed as follows. and extract travel paths one by one until there is no 1)Maximize the number of vehicles that can reach the positive flow on any edges.These travel paths then will destination be assigned to the vehicles with routing request as their 2)Minimize the total time duration from source to desti- routing results. nation(refer to the objective in problem formulation) Algorithm 1 MCMF-R Algorithm In this way,we can solve as many routing requests as possible, Input:routing requests (si,di)for each ciEC while sufficiently reducing the overall travel time of vehicular Output:Ri for ci users at the same time. 1:<u,v>∈E,f(u,v)=0: For vehicle set C to travel from s to d,the routing problem 2 V<u,v>E E:c(u,v)=D().Lo(u,v): can be represented as Fig.2.If we treat traffic as the flow and the travel time as the cost,centralized route guidance problem 3:partition set C into Cj,j=1,2,...,where ciCj share the same routing request (sj,dj) with single source and single destination can be solved as a 4:for all C;do minimum-cost maximum-flow problem,which is the core idea call MCMF(sj,dj,Cj,cost())to update f(); in the centralized solution. 6:end for 7:For each c;EC,extracting path Ri from f(); c)Multi-Source Multi-Destination Routing:In the real world,the routing requests will often have multiple sources and multiple destinations.Since minimum-cost maximum-flow algorithm is designed for single source and single destination, Fig.2:Centralized routing problem can be reduced to a routing before using it we need to first group the vehicles with problem from source s to destination d the same routing request (same si and di).By doing so, the original vehicle set C is partitioned into small subsets, 2)Minimum-Cost Maximum-Flow based Routing: Cj,j=1,2,....Vehicles in the same subset will have a)Minimum-Cost Maximum-Flow Problem:In the the same source and destination (line 3 in Algorithm 1). minimum-cost maximum-flow problem,there is a directed Then we can use minimum-cost maximum-flow algorithm for graph G(V,E)with source sV and destination(sink)d each subset,as shown in line 4 to 6 in Algorithm 1.When V,edge (u,v)EE has capacity c(u,v)>0,flow f(u,v)>0 processing,larger subsets will have higher priority in the order. and cost cost(u,v)>0.The total flow is uev f(s,v)and Besides grouping same routing requests,if the sizes of the the cost of sending this flow is)co) groups are too small to have good routing performances,we The objective of this problem is to find the cheapest possible can also merge the sources/destinations which are near to each way of sending a certain amount of flow through a flow other geographically into one common source/destination to network.The solution used in this paper [16]can be viewed as form larger subsets. 3)Analysis:The MCMF-R is meant to achieve the two a generalization of the maximum-flow algorithm called Ford- Fulkerson algorithm.The main idea is that while the original targets listed in Section IV-D1,which satisfies the objective in Section III.So if the travel time estimation is accurate enough. Ford-Fulkerson algorithm is seeking an augmenting path,this solution aims to find the one with the minimum cost instead the routing result of MCMF-R will be exactly the same as the b)Minimum-Cost Maximum-Flow based Routing:Based theoretical optimal solution in problem definition.By using on the analysis in Section IV-D1,we propose Minimum- MCMF algorithm,MCMF-R can make routing decisions for a vehicle flow at one time instead of a single vehicle,which Cost Maximum-Flow based Routing,MCMF-R for short,to solve the centralized route guidance problem.The algorithm increases the decision speed by the factor of the flow size is shown in Algorithm 1,where MCMF()means calling the In multi-source multi-destination routing part,the order of processing vehicle subsets is critical for routing efficiency and minimum-cost maximum-flow problem solution [16]. fairness.The earlier the subset is fed into MCMF(),the Flow and Capacity.In our routing problem,we re- shorter path it will get.So the best way to minimize the overall gard the traffic flow as f(u,v),so f(u,v) time duration is to process bigger size subset first.For fairness, 2e,w)∈E,w≠uF(u,v,o)l.Capacity c(u,v）is similar this also ensures that the majority of vehicles have the priority to M(),and is calculated as the maximum number to choose better routes.an edge in the previous path, then find the shortest path again as a new path. This process will continue until the needed number of paths is reached. In this way, these routes are very close to the shortest path but not strictly the top |C| shortest routes. IRR combines the proximity to the shortest path and imperfection of human beings, which can be viewed as the random routing decisions made by some local taxi drivers. D. Centralized Solution 1) Motivation: When the traffic is not heavy, simply using classical guidance techniques such as GPS can handle all routing requests without any congestion. So the centralized route guidance in this paper focuses on the situation when the traffic is very heavy, where large number of vehicles needs to travel on the main roads and severe traffic jams are likely to take place. In these cases, the traffic condition takes on a single-source single-destination pattern. In this way, the two targets of our centralized solution are listed as follows, 1) Maximize the number of vehicles that can reach the destination 2) Minimize the total time duration from source to desti￾nation (refer to the objective in problem formulation) In this way, we can solve as many routing requests as possible, while sufficiently reducing the overall travel time of vehicular users at the same time. For vehicle set C to travel from s to d, the routing problem can be represented as Fig.2. If we treat traffic as the flow and the travel time as the cost, centralized route guidance problem with single source and single destination can be solved as a minimum-cost maximum-flow problem, which is the core idea in the centralized solution. s d Fig. 2: Centralized routing problem can be reduced to a routing problem from source s to destination d 2) Minimum-Cost Maximum-Flow based Routing: a) Minimum-Cost Maximum-Flow Problem: In the minimum-cost maximum-flow problem, there is a directed graph GhV, Ei with source s ∈ V and destination (sink) d ∈ V , edge (u, v) ∈ E has capacity c(u, v) > 0, flow f(u, v) ≥ 0 and cost cost(u, v) ≥ 0. The total flow is P u∈V f(s, v) and the cost of sending this flow is P hu,vi∈E f(u, v) · cost(u, v). The objective of this problem is to find the cheapest possible way of sending a certain amount of flow through a flow network. The solution used in this paper [16] can be viewed as a generalization of the maximum-flow algorithm called Ford￾Fulkerson algorithm. The main idea is that while the original Ford-Fulkerson algorithm is seeking an augmenting path, this solution aims to find the one with the minimum cost instead. b) Minimum-Cost Maximum-Flow based Routing: Based on the analysis in Section IV-D1, we propose Minimum￾Cost Maximum-Flow based Routing, MCMF-R for short, to solve the centralized route guidance problem. The algorithm is shown in Algorithm 1, where MCMF(·) means calling the minimum-cost maximum-flow problem solution [16]. • Flow and Capacity. In our routing problem, we re￾gard the traffic flow as P f(u, v), so f(u, v) = hv,wi∈E,w6=u |F(u, v, w)|. Capacity c(u, v) is similar to M(·), and is calculated as the maximum number of vehicles available on the road (shown in line 2 in Algorithm 1, where D(·) and l is introduced in Section IV-B, L0(u, v) is the number of lanes in road hu, vi). • Cost. The cost(·) for minimum-cost maximum-flow prob￾lem is the travel time T (·) for route guidance problem. As shown in Eq.(4), it will be a function of the traffic flow. However, compared to cost(·), T (·) has an extra parameter w. To solve this problem, we can first replace w with a new parameter, the former intersection t before entering edge hu, vi. cost(·) will only be used when calculating the shortest path in MCMF(·). So if using popular shortest path algorithm such as Dijkstra, SPFA and etc., t should be already known when in need of value cost(u, v). In this way, value of T (ht, u, vi) can be used as cost(u, v) in MCMF(·). • Extracting Paths. From the result of MCMF(·), we can execute graph traversals from source to destination, and extract travel paths one by one until there is no positive flow on any edges. These travel paths then will be assigned to the vehicles with routing request as their routing results. Algorithm 1 MCMF-R Algorithm Input: routing requests hsi , dii for each ci ∈ C Output: Ri for ci 1: ∀ < u, v >∈ E, f(u, v) = 0; 2: ∀ < u, v >∈ E, c(u, v) = D(u,v) l · L0(u, v); 3: partition set C into Cj , j = 1, 2, . . ., where ci ∈ Cj share the same routing request hsj , dj i 4: for all Cj do 5: call MCMF(sj , dj , Cj , cost(·)) to update f(·); 6: end for 7: For each ci ∈ C, extracting path Ri from f(·); c) Multi-Source Multi-Destination Routing: In the real world, the routing requests will often have multiple sources and multiple destinations. Since minimum-cost maximum-flow algorithm is designed for single source and single destination, before using it we need to first group the vehicles with the same routing request (same si and di). By doing so, the original vehicle set C is partitioned into small subsets, Cj , j = 1, 2, . . .. Vehicles in the same subset will have the same source and destination (line 3 in Algorithm 1). Then we can use minimum-cost maximum-flow algorithm for each subset, as shown in line 4 to 6 in Algorithm 1. When processing, larger subsets will have higher priority in the order. Besides grouping same routing requests, if the sizes of the groups are too small to have good routing performances, we can also merge the sources/destinations which are near to each other geographically into one common source/destination to form larger subsets. 3) Analysis: The MCMF-R is meant to achieve the two targets listed in Section IV-D1, which satisfies the objective in Section III. So if the travel time estimation is accurate enough, the routing result of MCMF-R will be exactly the same as the theoretical optimal solution in problem definition. By using MCMF algorithm, MCMF-R can make routing decisions for a vehicle flow at one time instead of a single vehicle, which increases the decision speed by the factor of the flow size. In multi-source multi-destination routing part, the order of processing vehicle subsets is critical for routing efficiency and fairness. The earlier the subset is fed into MCMF(·), the shorter path it will get. So the best way to minimize the overall time duration is to process bigger size subset first. For fairness, this also ensures that the majority of vehicles have the priority to choose better routes