Applying the Principle of Locality to Improve the Shortest Path Algorithm(10.1007_s10586-016-0696-0)

13Cluster ComputingThe Journal of Networks, Software Tools and ApplicationsISSN 1386-7857Volume 20Number 1Cluster Comput (2017) 20:301-309DOI 10.1007/s10586-016-0696-0Applying the locality principle to improve the shortest path algorithmWang Xinghui, Li Jianyi, Li Xinrong &Wang HuijuanYour article is protected by copyright and all rights are held exclusively by Springer Science +Business Media New York. This e-offprint is for personal use only and shall not be self-archived in electronic repositories. If you wish to self-archive your article, please use the accepted manuscript version for posting on your own website. You may further depositthe accepted manuscript version in any repository, provided it is only made publicly available 12 months after official publicationor later and provided acknowledgement is given to the original source of publicationand a link is inserted to the published article on Springer's website. The link must be accompanied by the following text: "The final publication is available at ”.13Applying the locality principle to improve the shortest path algorithmWang Xinghui1·Li Jianyi1·Li Xinrong1·Wang Huijuan1Received:6August2016/Revised:10November2016/Accepted:18November2016/Published online:28November2016©Springer Science+Business Media New York2016Abstract When shortest path algorithm be used in real time road network monitoring system,the time complexity of the algorithm is becoming the bottleneck of the system.the paper proposes a solution to improve the shortest path algorithm. By making use of the k-ary-reverse tree and locality prin-ciple,this improved algorithm keeps the data operation,in priority queue,be localized in a small range.So the time complexity of this improved shortest path algorithm is opti-mized from O(nlog2n)to O(k×n);the parameter k denotes the average count of adjacency edges to each vertex,and n denotes the total count of vertexes in the network.Note that, the parameter k mainly depends on the edges density in the network.Generally speaking,the mean value of parameter k is not more than4in the road network,i.e.the time complex-ity of the improved algorithm is optimized from O(nlog2n)to O(n)in the road network.So the paper makes a conclusion that there is a linear correlation between the time complexity and the vertexes count n in the improved algorithm. Keywords Road networks·Shortest path·Locality principle·Dijkstra algorithm1IntroductionThe application of shortest path algorithm is often encoun-tered in software engineering,such as GIS-navigation,QoS computing in computer networks[1],Road network monitor-ing system and so on.With the help of Dijkstra’s algorithm, B Wang Xinghuiwangxinghui@1School of Computer and Remote Sensing Information Technology,North China Institute of Aerospace Engineering,Langfang065000,Hebei,China the evacuation route in higher and close building could be given in case of emergency[2].In order to get the optimal placement of PMUs,the single-source shortest-path algo-rithm is used to obtain the minimum CI cost[3].Making use of the optimized Dijkstra algorithm,the images can be stitched automatically with less Matching Mean Square Error and more stable results than other similar methods[4].By using the Dijkstra’s algorithm all the possible shortest cycles could be located in a weighted graph in polynomial time[5]. In addition,the shortest path algorithm can also be used to determine the main cutting edge curve in the rake face that minimizes the drilling power[6].Many improved shortest path algorithms have been pro-posed in recent years,such as shortest path algorithm based on bucket structure[7],the cycled shortest path problem[8], ETFA[9](Ebb tidefish algorithm,which aim for tolerable velocity of convergence and a better precision)and Proba-bilistic Extension of Dijkstra’s Algorithm[10].In addition, applying the approach of“data envelopment analysis”,an path with the maximum efficiency is determined[11].In recent years,the author took part in the project of the road network monitoring system(RNMS)for Beijing munic-ipality.During the project of RNMS,the author improved one shortest path algorithm which is based on k-ary-reverse tree, but when the author tested this algorithm in practice,he found that the time complexity of this algorithm is smaller than the theory.By further studying and improving this algorithm,the approach that the paper proposed,made the time complexity reduce from O(nlog2n)to O(k×n).In the following sections, the paper will not only describe this improved shortest path algorithm in theory,but also give the testing result to verify it.The paper is organized as follows.In the second section of the paper,it will introduce the k-ary-reverse tree which is the fundamental structure of the algorithm.The design guideline of the improved shortest path algorithm will be introduced123in the third section,which also includes the algorithm’sflow chart and run time storage structure.In Sect.4,the paper will discuss the principle of locality.The algorithm’s time com-plexity and space complexity will be given in Sect.5.In Sect. 6,the paper will analyze the testing result of this improved algorithm.The last section is the summary for commenting the advantages and disadvantages of this improved algorithm.2K-ary-reverse treeThe structure of urban road network is usually in the shape of grid.In particular situation,the intersection offive or six roads will be involved in road network.Without losing of generality,this paper makes use of k-ary-reverse tree in terms of of this particular situation.for each vertex in k-ary-reverse tree,although it can be routed by more than one vertex,each vertex only depends on one vertex.The logical structure of priority queue and k-ary-reverse tree in the process of calculating the shortest path is depicted in Fig.1.As the data carrier,priority queue and k-ary-reverse tree share the common node in memory.In fact,it is no need to create a new k-ary-reverse tree separately.When the node which contains the target vertex is removed from the front of the priority queue,the path along the depen-dence pointer(from the target node to the source node) happens to be the expected shortest path.3Algorithm guidelineThe purpose of shortest path algorithm is tofind one shortest path from source vertex o to target vertex t.Generally speak-ing,the problem of shortest path can be described as follow. The input of the shortest path algorithm is a graph G=(V,E) in which V denotes the set of vertexes,and E denotes the set of edges.The algorithm also assumes that G is connected, the length l(e)>0(e∈E)and for each e(e∈E),l(e)is the unique shortest path between its two endpoints.Let P(o,t) denotes the shortest path from source vertex o to target vertex t,and let|P(o,t)|be its length(i.e.the length of all edges in the shortest path).So P(o,t)is the output of the shortest pathalgorithm.Fig.1The activity diagram of k-ary-reverse treeFor each vertex v,the algorithm maintains the value w(v) for the length of the shortest path(from o to v)which has been found so far.Besides,the algorithm also maintains the value r(v)by which the vertex v is routed,i.e.the value r(v) records the precursor node of v in the shortest path(from o to v).Initially,w(o)=0,w(v)=∞,and r(v)=null(for each v∈v).Dijkstra’s algorithm divides the vertex set V into three part:the determined set V1{v|P(o,v)has been determined by the algorithm,v∈V},the semi-determined set V2{v|for each v∈V−V1,v is the adjacency vertex to the vertex in V1}and the undetermined set for remaining vertex V3{v|v∈V−V1−V2}.During the process of calculating the shortest path,The procedure of the algorithm is as follows.Moves the vertex v with the minimum value w(v)from V2to V1;(step1)For each edge<v,x>(<v,x>∈E,x∈V2∪V3), if w(v)+l(<v,x>)<w(x),lets w(x)=w(v)+l(< v,x>)and r(x)=v;(step2)if x∈V3,moves x from V3to V2.(step3)Repeated the steps from1to3,until the target vertex is found and moved from V2to V1.In engineering,a priority queue or heap will bring more convenience than array to the process of calculating the short-est path.As is described in Sect.2,the operation of adding data to queue is the bottleneck to the improved algorithm.3.1Design guidelineIt follows the order of length increasing to nearly all the shortest path algorithm,when the algorithm calculates the shortest path.Lemma1The next shortest path to be generated is always a one-edge extension of an already generated shortest path.Proof Making use of the proof of contradiction,this theorem can be proved easily.To put it another way,lemma1can also be considered by the way as follow:the sub path of each shortest path must be one shortest path.Define‘n’denotes the count of vertexes,‘k’denotes the count of adjacency edges of one vertex,and‘m’denotes the length of the priority queue.We can conclude theorem2as follow.Theorem1Except the source vertex,each vertex will be located the position in the priority queue for not more than k times.Proof Each vertex needs to be added into the priority queue for only one time,this is thefirst time to locate the position of the vertex in priority queue.It’s no need to locate the position of one vertex,if the vertex has been out of the priority queue,123so the algorithm needs to locate the position for each vertex at most‘k−1’times.Hence,the maximum times of position locating is‘1’+‘k−1’times,i.e.k times.Definition1One vertex,can be called Spark-Vertex,if all it’s adjacency vertexes do not route by it.The path from the source vertex to the Spark-Vertex can be called Local Maximum Shortest Path(LMSP for short).Theorem2If the times of position locating for one vertex in the priority queue happen to be k times,the vertex must be the Spark-Vertex.Proof Let V v={x|for∀x∈V,vertex x is the adjacency vertex to v,v∈V.},V r={r|∀r(r∈V v),vertex r is routed by vertex v,v∈V.}.If the vertex v has been located the position in the priority queue for k times,it means all vertexes that adjacent to v have dequeued from the priority queue,that is to say,all vertexes that adjacent to v is in set V1(the determined set),only the vertex v itself is leaving in V2(the semi-determined set).Right now,the algorithm has been separating the vertex v and all vertexes that adjacent to v into two set V2and V1,i.e.Vertex v is in V2and all vertexes that adjacent to v is in V1.so at this time,V r=ϕ.Hereby,by using Theorem1and Definition1,It can be concluded that, there is no vertex routed by vertex v in the adjacency vertex set of v.So vertex v can be called the Spark-Vertex.The Spark-Vertex has great potential for application.Gen-erally speaking,the Spark-Vertex marks the traffic jam cross in the real time road network.As the important information, the Spark-Vertex is very useful for vehicle navigation in GIS or other related software.In addition,such vertexes can be signed easily during the process of calculating the shortest path,so it is no need to calculate such vertexes separately.3.2The improvementBased on the theory above,the design idea of the improved algorithm is described as follows.For thefirst,put the source vertex into the priority queue;Second,get the vertex h from thefirst node of the pri-ority queue by calling the‘dequeue’function,if vertex h is the target vertex,the routing path from the source vertex to the target vertex is the expected shortest path,the algorithm terminates;Third,put all adjacency vertexes of h into the priority queue;Hereby,for each adjacency vertex a of vertex h,three conditions is needed to be considered.If vertex a has been out of the priority queue,then we do nothing for such vertexes;if vertex a has existed in the priority queue,we have to decide whether the route dependency of vertex a need to be updated or not;if vertex a hasn’t yet been putted into the priority queue,then put it into the priority queue.Fourth,repeats the step2–3,until the target vertex has been found.These four steps of the shortest path algorithm can be shown in the form offlow chart as Fig.2.3.3Priority queue and k-ary-reverse treeThe vertexes involved by the priority queue spread around the source vertex uniformly during the process of the cal-culating shortest path.This process does not stop until the target vertex has been found.Therefore,the nearer the dis-tance(between the source vertex and the target vertex),the faster the calculation.In this improved algorithm,the paper adopt the combina-tion of priority queue and k-ary-reverse tree to design this algorithm.In engineering,a serious of arrays instead of the k-ary-reverse tree are used to record the dependency informa-tion between vertexes,but the k-ary-reverse tree also plays an important role in at lest two aspects.For thefirst,the k-ary-reverse tree could describe the run-time storage struc-ture of the algorithm,whether the algorithm makes use of it or not.For the second,the algorithm’s efficiency could be improved by expanding the application of k-ary-reverse tree. For example,the path of k-ary-reverse tree can be used in the form of the shared path[12].As the shared path,k-ary-reverse tree not only stores the information of each vertex in the map,such as the depended vertex,the dependency vertex with maximum or minimum weight,but also keeps the data operation be localized in a small range.So the algorithm’s efficiency can be improved greatly.Note that,the k-ary-reverse tree records the dependency information among vertexes.The order of the shortest path, as the arrow(solid line)shown in Fig.3,starts from the target vertex‘t’to the source vertex‘o’.This result seems to violate the original intention of the shortest path algorithm,but it is not the defect of this improved algorithm,it is just determined by the characteristic of k-ary-reverse tree.The order of the shortest path can be reversed by one stack if it’s needed.If this algorithm is used in the engineering,it needs to make some adjustments.For thefirst,for each node which is got by the“dequeue”operation should be put into an array(or list)temporarily,you may need to handle such nodes in the near future;The second,when the priority queue is empty, the k-ary-reverse tree,as is shown in Fig.3,happens to be the desired single source shortest path.The third,do not forget to release such nodes in which the count of its dependency is zero,the Spark-Vertex is the typical vertex for such nodes. 4Principle of localityThe history for the locality principle can be tracked to the last century,60to70years’,engineers found that,a storage unit123Fig.2Theflow chart of thealgorithmbeing accessed tends to gather in a small continuous area, when they observe the process of CPU accessing memory. Working set is just based on this theory.The working set idea is based on the assumption that the pages seen in the back-ward window are likely to be used again in the near future. Generally speaking,the locality principle can be described in two aspects as follow.1.Temporal Locality:if a data item is being accessed,itwill be re-visited likely in the near future.Program loop, stack is the reason for temporal locality.2.Spatial Locality:the data item which will be used in thenear future and the data item now being used have the near address distribution in memory.The reason of spa-tial locality includes executing the instruction sequence,continuous data storage in array and so on.The locality principle is a general phenomenon in network,sofinding out and making use of this principle is the ways,proposed by the paper,to maximum the efficiency of thealgorithm and minimum the resource that the algorithm uses.Now,let’s discuss the movement of the priority queue.Given a non-negative value r,let R={r|r=max|P(o,v)|}represents the radius of the network.Let C o,r={v|v∈V,| P(o,v)|≤r}be the vertexes set that included by radius r.During the calculation of shortest path,the behavior of thepriority queue is in the shape of a spiral(as the curve shownin Fig.4),it moves from source vertex o to target vertex t123Fig.3The diagram of shortestpathFig.4The activity diagram of priority queue(1)gradually,i.e.the radius r of the priority queue is increasing gradually.Figure5describes the movement of the priority queue vividly.In this process,for each vertex‘v that will be added into or deleted from the priority queue,it is worth noting that,the value w(v)will become more and more large at macro level;at the same time,the change of w(v)fluctuates within a narrow range at the micro level.The locality prin-ciple just exists in this process.How tofind and make use of this principle will determine the efficiency of the shortest path algorithm.For each loop in the shortest path algorithm,the algorithm moves the smallest vertex v from V2to V1;at the same time,it involves all adjacency vertexes of v from V3to V2.The algo-rithm terminates when the target vertex has been extracted or all vertexes have been moved to V1.If the count of the operations(adding node,removing node,updating nodeand Fig.5The activity diagram of priority queue(2)searching node)in the priority queue is nearly to zero,we can conclude that,the time complexity of this process is O(n); that is,there is a linear correlation between the time com-plexity and the vertexes count n.Although the efficiency of algorithm can be improved by the principle of locality,it is still necessary to solve at least four problems as follow.1.Finding vertex in the priority queue;As an example,considering the case when one vertex, named‘v’,which is need to be added into the prior-ity queue,had existed in the priority queue.Right now, the algorithm needs to decide whether the dependency information of vertex‘v’needs to be updated or not.So finding vertex‘v’in the priority queue is essential to this123operation.Making use of one auxiliary array,the time complexity offinding a vertex in the priority queue is O(1).2.Adding new vertex to the priority queue;This section is mainly to discuss the situation that when one new vertex is needed to be added into the priority queue.Generally speaking,the average cost of this oper-ation is m/2times(for the queue that is in the type of list)or log(2m)times(for the queue that is in the type of array or heap).Note that,‘m’denotes the length of the queue or array.Based on the locality principle,the time complexity for this operation is nearly to O(1).3.Adjusting the position of one vertex in the priority queue;If the algorithm needs to adjust the position of one vertex in the priority queue.The time complexity for this oper-ation is also nearly to O(1)in terms of locality principle and k-ary-reverse tree.4.Removing vertex from the priority queue;It needs only one step to remove vertex from the priority queue,so the time complexity of this operation is O(1).Nearly all the single shortest path algorithm could not avoid the four problems above.The paper proposes the solu-tion,i.e.locality principle,to solve the four problems above. The k-ary-reverse tree also plays an important role in this solution(checking Sects.2and3.2for more information about the k-ary-reverse tree).Therefore,by making use of the localized characteristic of data in and out of the priority queue,the efficiency of the shortest path algorithm can be optimized greatly.The next section will analyze the complexity of this improved algorithm.5Complexity analysis5.1Space complexityIn the process of calculating the shortest path,three auxiliary arrays are needed.Array W:it records the temporary weight for each vertex.Array S:it records the state(used,using,has not been used)of each vertex.Array R:it records the dependence information of each vertex.So the space complexity for this improved algorithm is O (3n).5.2Time complexityBased on the locality principle in the priority queue that the improved algorithm used,the paper proposes one theorem as follow.Theorem3Based on the locality principle in the priority queue,the time complexity of the single source shortest path algorithm can be optimized to O(k×n).Proof The algorithm needs to calculate n times in its outer loop,and k times in its inner loop which reflects average count of adjacency edges by one vertex in the network(check-ing Fig.2for more information).Hereby,the average times of queuefluctuation could be neglected for the reason of the locality principle(checking the last portion of Sect.4 for more detail about the locality principle).So the time complexity of this improved algorithm can be considered to O(k×n).Therefore,the locality principle makes the time complex-ity decrease from O(n×log2n)down to O(k×n).In order to further verify the correctness of this theory,The team has done a series of testing on the improved algorithm.The test-ing data will be described in the next section. 6Algorithm testA map which consists of73vertexes and233road sections is selected to carry out an overall testing.The testing pro-duces a total of5329samples of shortest paths,i.e.the testing includes all point-to-point paths from that map.For each shortest path,the test objects include the total times of cal-culation,the total times of queuefluctuation and the total counts of the related vertexes.After the testing,these data is divided into several groups by the‘length’(the count of vertexes from source vertex to target vertex in the shortest path)of the shortest path,i.e.the shortest path with the same length are divided into the same group.The testing results are shown in Table1.The abscissa in Fig.6represents the count of vertexes of the shortest path in road network,and ordinate represents the times of calculating and the count of related vertexes.Figure6shows us the information that,the total times of calculation growths with the increasing of the distance (between source vertex and target vertex).It gives out the computational cost of the shortest path algorithm in three aspects:the count of the related vertexes(the line with the diamond node in the bottom level),the average times of queue fluctuation(the line with the square node in the middle level) and the total times of calculation(the line with the triangular node in the up level).The abscissa in Fig.7denotes the count of vertexes of the shortest path.The calculation formula of this result is described as follow.F[i]=⎛⎝⎛⎝n ij=1f j⎞⎠/ni⎞⎠/⎛⎝⎛⎝n ij=1c j⎞⎠/ni⎞⎠(1)123Table1The result of testing dataI II III IV V VI29.9056.3287.586232 1.305 338.16727.92115.880407 2.403 481.20559.92224.960526 3.253 5127.91793.95633.559590 3.811 6169.377122.65141.329605 4.098 7204.641145.83748.283601 4.238 8230.362161.10653.837566 4.278 9251.134172.82158.509491 4.292 10265.372179.32862.404403 4.252 11274.000181.41165.408316 4.189 12277.590179.51067.620234 4.105 13280.468177.16569.500158 4.035 14281.667174.20770.80587 3.978 15280.816170.46971.78132 3.912 I.The count of vertexes from source vertex to target vertex in the shortest pathII.Average times of calculationIII.Average times of queuefluctuationIV.Average count of related vertexesV.The count of samplesplexity Factor(K)Fig.6time complexity of algorithmNote that,f j denotes the average times of queuefluctuation for the sample j.c j denote the average count of related ver-texes for the sample j.The count of total samples is n i,while i denotes the count of vertexes from source vertex to target vertex in the shortest path.F[i]means the average times of queuefluctuation by one vertex(Checking Table1for more information about the data in formula5.2).From Fig.7it can be found that the average count of queue fluctuation by one vertex is about3times.As the common knowledge,the average count of adjacency edges in road net-works is not more than4.So combination with Theorem2,It can be concluded that,the queuefluctuation can beneglected Fig.7the average times of queuefluctuation by onevertexFig.8The result of complexity coefficient kin the process of calculating the shortest path.This conclu-sion also shows that the locality principle takes effect in the process of calculating the shortest path.Although the total times of calculating increase with the length of the shortest path,the complexity coefficient k remains unchanged as is shown in Fig.8.The complexity coefficient k,as the testing results,can be calculated by the formula as below.k[i]=⎛⎝⎛⎝n ij=1t j⎞⎠/ni⎞⎠/⎛⎝⎛⎝n ij=1c j⎞⎠/ni⎞⎠(2)Note that,t j denotes the average times of calculation in sam-ple j;the means of parameters c j,n i is the same to Fig.7.The complexity coefficient k,as is shown in Fig.8,is stabilized between4and4.5.this is exactly what the paper expected.The curve has a tendency to decrease as is shown in Figs. 7and8.The reason is that,along with the increasing of the length of the shortest path,the source vertex or the target vertex gets close to the edge of the road network,and then it123makes the count of vertexes which should be involved in the calculation reduce,so it results in the downward trend of the curve in Figs.7and8.At last,the coefficient value k,confirms the effectiveness of the locality principle that is used in the improved shortest path algorithm again.7ConclusionThis algorithm is based on the road network,but not limited to the road network.It is also suitable for other networks,such as computer network,wireless sensor network and so on.By making use of the principle of locality,the time complexity of the shortest path algorithm is optimized from O(nlog2n) to O(n).So the paper makes a conclude that there is a linear correlation between the time complexity and the vertexes count n in this improved algorithm.Combination with artificial intelligence algorithm is one new trend of shortest path algorithm optimization in recent years.Such as genetic algorithm based on Dijkstra algo-rithm[13,14],making using of Markov model as the decision support for shortest path calculation[15–17],the DRSSPP (Distributionally Robust Stochastic Shortest Path Problem) on NP-hard problem[18]and so on.Therefore,this is one direction of the further improvement and application for the algorithm proposed by the paper.Acknowledgements The authors would like to thank the Science and technology project of Hebei Province(15210909),the Scien-tific&Technical Research Foundation of Hebei Province(15212113) and the Scientific research fund for young of North China Institute of Aerospace Engineering(KY201419)forfinancial support. References1.Jane,C.-C.,Laih,Y.-W.:System travel time reliability:a measureof the quality of service of networks.Qual.Reliab.Eng.Int.32(3), 805–815(2016)2.Sabri,N.A.M.,Basari,A.S.H.:The utilisation of Dijkstra’s algo-rithm to assist evacuation route in higher and close building.J.Comput.Sci.11(2),330–336(2015)3.Hooshmand,R.-A.,Fesharaki,F.H.:IEEE Trans.Smart Grid7(1),84–93(2016)4.Zhicheng,W.,Yufei,C.,Zewei,Z.,Weidong,Z.:An automaticpanoramic image mosaic method based on graph model.Multime-dia Tools Appl.75(5),2725–2740(2016)5.Fugang,C.,Han,R.,Ni,C.:Finding shorter cycles in a weightedgraph.Graphs Comb.32(1),65–77(2016)6.Bin,L.,Liangshan,X.:The energy conservation optimizationdesign of the cutting edges of the twist drill based on Dijkstra’s algorithm.Int.J.Adv.Manuf.Technol.82(5),889–900(2016)7.Wen-hong,W.E.I.,Qing-xia,L.I.,Zhao-quan,C.A.I.:A single-source shortest path algorithm based on the bucket structure.Comput.Eng.Sci.34(4),77–81(2012)8.Aini,A.,Salehipour,A.:Speeding up the Floyd-Warshall algorithmfor the cycled shortest path problem.Appl.Math.Lett.25(1),1–5 (2012)9.Zhenyu,M.,Jeng-Shyang,P.,Abdulhameed,A.:A new meta-heuristic ebb-tide-fish-inspired algorithm for traffic navigation.Telecommun.Syst.62(2),403–415(2016)10.Galan-Garcia,J.L.,Aguilera-Venegas,G.,Galan-Garcia,M.A.,Rodriguez-Cielos,P.:A new Probabilistic Extension of Dijkstra’s Algorithm to simulate more realistic trafficflow in a smart city.put.267,780–789(2015)11.Amirteimoori,A.:An extended shortest path problem:a data envel-opment analysis approach.Appl.Math.Lett.25(11),1839–1843 (2012)12.He,R.,Lin,B.:Dynamic Power-aware shared path protection algo-rithms in WDM mesh mun.8(1),55–65(2013) 13.Min,H.,Ren,L.,Lee,L.H.:Model and algorithm for4PLRP withuncertain delivery time.Inf.Sci.330,211–255(2016)14.Xuezhi,Z.H.U.:Shortest Path Problem Based on Genetic Algo-rithms(D).University of Science and Technology of China,HeFei (2015)15.Sun,J.,Liu,H.X.:Stochastic eco-routing in a signalized trafficnetwork.Transp.Res Part C7,110–128(2015)16.Wang,Q.,Wang,Q.:Restricted epidemic routing in multi-community delay tolerant networks.IEEE Trans.Mobile Comput.14(8),1686–1697(2015)17.Tan,X.,Yuan,W.,Tsang,D.H.:A stochastic shortest path frame-work for quantifying the value and lifetime of battery energy storage under dynamic pricing.IEEE Trans.Smart Grid99,1–10 (2015)18.Cheng,J.,Leung,J.,Lisser,A.:New reformulations of distribution-ally robust shortest path put.Oper.Res.74,196–204(2016)Wang Xinghui received hisB.S.degree in Beijing Instituteof Petrochemical Technology in2004.He was a software engineerin China Daheng Group Inc,Bei-jing Image Vision TechnologyBranch since2004.He receivedhis M.S.degree in China Uni-versity of Petroleum(Beijing)in2012.He worked in North ChinaInstitute of Aerospace Engineer-ing since2012.He is currentlya lecture in the Department ofComputer and Remote SensingInformation Technology,North China Institute of Aerospace Engineering.His research interests include computer graphics,pattern recognition and artificial intelligence.123。