Category | Road Type | Urban Speed | Rural Speed |
1 | Motorway | 60 | 70 |
2 | Trunk | 45 | 55 |
3 | Primary | 30 | 50 |
4 | Secondary | 20 | 45 |
5 | Tertiary | 15 | 35 |
6 | Residential/Unclassified | 8 | 25 |
7 | Service | 5 | 10 |
8 | Living street | 5 | 10 |
The emergence of electric vehicle wireless charging technology, where a whole lane can be turned into a charging infrastructure, leads to new challenges in the design and analysis of road networks. From a network perspective, a major challenge is determining the most important nodes with respect to the placement of the wireless charging lanes. In other words, given a limited budget, cities could face the decision problem of where to place these wireless charging lanes. With a heavy price tag, a placement without a careful study can lead to inefficient use of limited resources. In this work, the placement of wireless charging lanes is modeled as an integer programming problem. The basic formulation is used as a building block for different realistic scenarios. We carry out experiments using real geospatial data and compare our results to different network-based heuristics.
Reproducibility: all datasets, algorithm implementations and mathematical programming formulation presented in this work are available at https://github.com/hmwesigwa/smartcities.git
Citation: |
Figure 1. Example of $ \mathcal{G}_r $ with $ r = (u_1, u_2, u_3) $ and $ nLayers = 4 $. $ u_4 $ is an artificial road segment added to capture the final $\textsf{SOC} $ from $ u_3 $. The nodes in the set $ \mathcal{B}_r = \{\mu_{i, j} | i = 4 \text{ or } j = 4\} $ are referred to as the boundary nodes. The out going edges of each node $ \mu_{i, j} $ are determined by an $\textsf{SOC} $ function. Each node represents a discretized $\textsf{SOC} $ value
Figure 2. Optimal solution with a four unit installation budget. The thick ends of the edges are used to indicate the direction of the edge. Taking $ \alpha = 0 $ without any installation, there are 70 number of infeasible routes. An optimal installation of 5 WCLs would ensure zero infeasible routes. With an optimal installation of 4 WCLs, the nodes colored in red, there would have 12 infeasible routes
Figure 3. Directed toy graphs of 26 and 110 vertices used for problems 1 and 2, respectively. The bold end points on the edges of (a) represent edge directions. The graphs are subgraphs of the California road network taken from the dataset SNAP in [47]
Figure 4. Comparison of the different methods. The minimum number of WCL installation needed to eliminate all infeasible routes is $ B $. The nodes colored red indicate location of WCL installation. In (a), we demonstrate the result given by our model requiring a budget of 12 WCL'sin order to have zero infeasible routes. In (b) and (c), we demonstrate solutions from the betweenness and eigenvector heuristics that give budgets of 20 and 23 WCL's, respectively
Figure 5. Figures (a) to (f) are plots showing the number of routes ending with final $\textsf{SOC} $ below a given value via the different models. Legend "model: random routes" represents the solution from the proposed model when 100 routes were chosen uniformly at random with $ \alpha = 0 $ and different budget scenarios. The solution is compared to the solutions from the different centrality measures, a random installation and one with no WCL installation. The $ y $-intercept of the different lines shows the number of infeasible routes for the different methods. Our model gives a smaller number in all cases. The plots go further and show how a specific solution affects the $\textsf{SOC} $ of all routes. As the budget approaches 50%, we demonstrate that our model gives a significant reduction to the number of infeasible routes while also improving the $\textsf{SOC} $ in general of the feasible routes
Figure 7. Histograms showing the number of infeasible routes for different values of $ \alpha $ and $ \beta $ for the Manhattan neighborhood graph. The vertical line indicates the value of $ \alpha $. In (a) with a budget of 10%, our model gives a solution with at least 50% less infeasible routes compared to the betweenness heuristic. In (b), we demonstrate how the effects of a 20% budget on the $\textsf{SOC} $ distribution within the network. In (c), our model gives a solution with at least 25% less infeasible routes
Figure 8. The number of routes ending with final $\textsf{SOC} $ below a given value in the lower Manhattan graph. The solution was obtained with $ \alpha = 0.7 $ and $ \beta = 0.1 $. The blue curve shows the $\textsf{SOC} $ distribution when no WCL are installed. Green and red curves show the $\textsf{SOC} $ distribution after an installation using the proposed model and the betweenness heuristic, respectively. Plot (b) a gives closer look into (a) for the $\textsf{SOC} $ values below 0.7
Table 2. Road category with corresponding speed in Miles/Hr
Category | Road Type | Urban Speed | Rural Speed |
1 | Motorway | 60 | 70 |
2 | Trunk | 45 | 55 |
3 | Primary | 30 | 50 |
4 | Secondary | 20 | 45 |
5 | Tertiary | 15 | 35 |
6 | Residential/Unclassified | 8 | 25 |
7 | Service | 5 | 10 |
8 | Living street | 5 | 10 |
Table 1.
Average number of Infeasible Routes for the different methods while varying the global parameter
$ \alpha $ | Model | $ BTN $ | $ EIG $ | $ CLN $ | $ RND $ |
0 | 3180.4 | 4445.4 | 6761 | 6392.4 | 6637.2 |
0.2 | 7159.2 | 8157.4 | 9236.6 | 8845.6 | 9572.6 |
0.5 | 9388.2 | 9412.6 | 25411.6 | 9388.8 | 10273.8 |
[1] | H. Bar-Gera, Transportation test problems, Website: http://www.bgu.ac.il/~bargera/tntp/. Accessed April, 28 (2009), 2009. |
[2] | Z. Bi, T. Kan, C. C. Mi, Y. Zhang, Z. Zhao and G. A. Keoleian, A review of wireless power transfer for electric vehicles: Prospects to enhance sustainable mobility, Applied Energy, 179 (2016), 413-425. doi: 10.1016/j.apenergy.2016.07.003. |
[3] | P. Bogaert, V. Fack, N. Van de Weghe and P. De Maeyer, On Line Graphs and Road Networks, in topology and Spatial Databases Workshop, Glasgow, Scotland, 2005. |
[4] | S. P. Borgatti, Centrality and aids, Connections, 18 (1995), 112-114. |
[5] | W.-Y. Chang, The state of charge estimating methods for battery: A review, ISRN Applied Mathematics, 2013 (2013), Article ID 953792, 7 pages. doi: 10.1155/2013/953792. |
[6] | Z. Chen, F. He and Y. Yin, Optimal deployment of charging lanes for electric vehicles in transportation networks, Transportation Research Part B: Methodological, 91 (2016), 344-365. doi: 10.1016/j.trb.2016.05.018. |
[7] | D. Cho and J. Kim, Magnetic field design for low emf and high efficiency wireless power transfer system in on-line electric vehicle, in CIRP Design Conference 2011, 2011. |
[8] | R. Church and C. R. Velle, The maximal covering location problem, Papers in regional science, 32 (1974), 101-118. |
[9] | V. Cirimele, F. Freschi and P. Guglielmi, Wireless power transfer structure design for electric vehicle in charge while driving, in Electrical Machines (ICEM), 2014 International Conference on, IEEE, 2014, 2461–2467. doi: 10.1109/ICELMACH.2014.6960532. |
[10] | M. S. Daskin, What you should know about location modeling, Naval Research Logistics (NRL), 55 (2008), 283-294. doi: 10.1002/nav.20284. |
[11] | J. Dong, C. Liu and Z. Lin, Charging infrastructure planning for promoting battery electric vehicles: An activity-based approach using multiday travel data, Transportation Research Part C: Emerging Technologies, 38 (2014), 44-55. doi: 10.1016/j.trc.2013.11.001. |
[12] | R. Z. Farahani, N. Asgari, N. Heidari, M. Hosseininia and M. Goh, Covering problems in facility location: A review, Computers & Industrial Engineering, 62 (2012), 368-407. doi: 10.1016/j.cie.2011.08.020. |
[13] | M. W. Fontana, Optimal Routes for Electric Vehicles Facing Uncertainty, Congestion, and Energy Constraints, PhD thesis, Massachusetts Institute of Technology, 2013. |
[14] | T. Franke, I. Neumann, F. Bühler, P. Cocron and J. F. Krems, Experiencing range in an electric vehicle: Understanding psychological barriers, Applied Psychology, 61 (2012), 368-391. doi: 10.1111/j.1464-0597.2011.00474.x. |
[15] | L. C. Freeman, Centrality in social networks conceptual clarification, Social Networks, 1 (1978), 215-239. doi: 10.1016/0378-8733(78)90021-7. |
[16] | M. Fuller, Wireless charging in california: Range, recharge, and vehicle electrification, Transportation Research Part C: Emerging Technologies, 67 (2016), 343-356. doi: 10.1016/j.trc.2016.02.013. |
[17] | J. S. Gill, P. Bhavsar, M. Chowdhury, J. Johnson, J. Taiber and R. Fries, Infrastructure cost issues related to inductively coupled power transfer for electric vehicles, Procedia Computer Science, 32 (2014), 545-552. doi: 10.1016/j.procs.2014.05.459. |
[18] | M. Greenleaf, O. Dalchand, H. Li and J. P. Zheng, A temperature-dependent study of sealed lead-acid batteries using physical equivalent circuit modeling with impedance spectra derived high current/power correction, IEEE Transactions on Sustainable Energy, 6 (2015), 380-387. doi: 10.1109/TSTE.2014.2371435. |
[19] | A. Gutfraind, I. Safro and L. A. Meyers, Multiscale network generation, in Information Fusion (Fusion), 2015 18th International Conference on, IEEE, 2015,158–165. |
[20] | M. Haklay and P. Weber, Openstreetmap: User-generated street maps, IEEE Pervasive Computing, 7 (2008), 12-18. doi: 10.1109/MPRV.2008.80. |
[21] | T. S. Hale and C. R. Moberg, Location science research: A review, Annals of Operations Research, 123 (2003), 21-35. doi: 10.1023/A:1026110926707. |
[22] | W. E. Hart, C. Laird, J.-P. Watson and D. L. Woodruff, Pyomo–optimization Modeling in Python, vol. 67, Springer Science & Business Media, 2012. |
[23] | W. E. Hart, J.-P. Watson and D. L. Woodruff, Pyomo: Modeling and solving mathematical programs in python, Mathematical Programming Computation, 3 (2011), 219-260. doi: 10.1007/s12532-011-0026-8. |
[24] | F. He, D. Wu, Y. Yin and Y. Guan, Optimal deployment of public charging stations for plug-in hybrid electric vehicles, Transportation Research Part B: Methodological, 47 (2013), 87-101. doi: 10.1016/j.trb.2012.09.007. |
[25] | F. He, Y. Yin and J. Zhou, Integrated pricing of roads and electricity enabled by wireless power transfer, Transportation Research Part C: Emerging Technologies, 34 (2013), 1-15. doi: 10.1016/j.trc.2013.05.005. |
[26] | F. He, Y. Yin and J. Zhou, Deploying public charging stations for electric vehicles on urban road networks, Transportation Research Part C: Emerging Technologies, 60 (2015), 227-240. doi: 10.1016/j.trc.2015.08.018. |
[27] | S. Helber, J. Broihan, Y. Jang, P. Hecker and T. Feuerle, Location planning for dynamic wireless charging systems for electric airport passenger buses, Energies, 11 (2018), 258. doi: 10.3390/en11020258. |
[28] | M. J. Hodgson, A flow-capturing location-allocation model, Geographical Analysis, 22 (1990), 270-279. doi: 10.1111/j.1538-4632.1990.tb00210.x. |
[29] | Y. Huang, S. Li and Z. S. Qian, Optimal deployment of alternative fueling stations on transportation networks considering deviation paths, Networks and Spatial Economics, 15 (2015), 183-204. doi: 10.1007/s11067-014-9275-1. |
[30] | I. Hwang, Y. J. Jang, Y. D. Ko and M. S. Lee, System optimization for dynamic wireless charging electric vehicles operating in a multiple-route environment, IEEE Transactions on Intelligent Transportation Systems, 19 (2018), 1709-1726. doi: 10.1109/TITS.2017.2731787. |
[31] | I. ILOG, Cplex optimization studio, http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer, 2014. |
[32] | Y. J. Jang, Y. D. Ko and S. Jeong, Creating innovation with systems integration, road and vehicle integrated electric transportation system, in Systems Conference (SysCon), 2012 IEEE International, IEEE, 2012, 1–4. doi: 10.1109/SysCon.2012.6189531. |
[33] | Y. J. Jang, Y. D. Ko and S. Jeong, Optimal design of the wireless charging electric vehicle, in Electric Vehicle Conference (IEVC), 2012 IEEE International, IEEE, 2012, 1–5. doi: 10.1109/IEVC.2012.6183294. |
[34] | J. Johnson, M. Chowdhury, Y. He and J. Taiber, Utilizing real-time information transferring potentials to vehicles to improve the fast-charging process in electric vehicles, Transportation Research Part C: Emerging Technologies, 26 (2013), 352-366. doi: 10.1016/j.trc.2012.10.009. |
[35] | G. Jung, B. Song, S. Shin, S. Lee, J. Shin, Y. Kim and S. Jeon, High efficient inductive power supply and pickup system for on-line electric bus, in Electric Vehicle Conference (IEVC), 2012 IEEE International, IEEE, 2012, 1–5. doi: 10.1109/IEVC.2012.6183263. |
[36] | J. Jung, J. Y. Chow, R. Jayakrishnan and J. Y. Park, Stochastic dynamic itinerary interception refueling location problem with queue delay for electric taxi charging stations, Transportation Research Part C: Emerging Technologies, 40 (2014), 123-142. doi: 10.1016/j.trc.2014.01.008. |
[37] | J. E. Kang and W. Recker, Strategic hydrogen refueling station locations with scheduling and routing considerations of individual vehicles, Transportation Science, 49 (2014), 767-783. doi: 10.1287/trsc.2014.0519. |
[38] | M. Khan, M. Chowdhury, S. M. Khan, I. Safro and H. Ushijima-Mwesigwa, Utility maximization framework for opportunistic wireless electric vehicle charging, preprint, arXiv: 1708.07526. |
[39] | J.-G. Kim and M. Kuby, The deviation-flow refueling location model for optimizing a network of refueling stations, international Journal of Hydrogen Energy, 37 (2012), 5406-5420. doi: 10.1016/j.ijhydene.2011.08.108. |
[40] | J.-G. Kim and M. Kuby, A network transformation heuristic approach for the deviation flow refueling location model, Computers & Operations Research, 40 (2013), 1122-1131. doi: 10.1016/j.cor.2012.10.021. |
[41] | Y. Kim, Y. Son, S. Shin, J. Shin, B. Song, S. Lee, G. Jung and S. Jeon, Design of a regulator for multi-pick-up systems through using current offsets, in Electric Vehicle Conference (IEVC), 2012 IEEE International, IEEE, 2012, 1–6. doi: 10.1109/IEVC.2012.6183256. |
[42] | Y. D. Ko and Y. J. Jang, The optimal system design of the online electric vehicle utilizing wireless power transmission technology, IEEE Transactions on Intelligent Transportation Systems, 14 (2013), 1255-1265. doi: 10.1109/TITS.2013.2259159. |
[43] | N. Koirala, F. He and W. Shen, Comparison of two battery equivalent circuit models for state of charge estimation in electric vehicles, in Industrial Electronics and Applications (ICIEA), 2015 IEEE 10th Conference on, IEEE, 2015, 17–22. doi: 10.1109/ICIEA.2015.7334077. |
[44] | M. Kuby and S. Lim, The flow-refueling location problem for alternative-fuel vehicles, Socio-Economic Planning Sciences, 39 (2005), 125-145. doi: 10.1016/j.seps.2004.03.001. |
[45] | M. Kuby and S. Lim, Location of alternative-fuel stations using the flow-refueling location model and dispersion of candidate sites on arcs, Networks and Spatial Economics, 7 (2007), 129-152. doi: 10.1007/s11067-006-9003-6. |
[46] | S. Lee, J. Huh, C. Park, N.-S. Choi, G.-H. Cho and C.-T. Rim, On-Line Electric Vehicle using inductive power transfer system, in 2010 IEEE Energy Conversion Congress and Exposition, IEEE, 2010, 1598–1601. doi: 10.1109/ECCE.2010.5618092. |
[47] | J. Leskovec, K. J. Lang, A. Dasgupta and M. W. Mahoney, Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters, Internet Mathematics, 6 (2009), 29-123. doi: 10.1080/15427951.2009.10129177. |
[48] | S. Li and C. C. Mi, Wireless power transfer for electric vehicle applications, IEEE journal of emerging and selected topics in power electronics, 3 (2015), 4-17. |
[49] | Z. Li, M. Chowdhury, P. Bhavsar and Y. He, Optimizing the performance of vehicle-to-grid (v2g) enabled battery electric vehicles through a smart charge scheduling model, International Journal of Automotive Technology, 16 (2015), 827-837. doi: 10.1007/s12239-015-0085-3. |
[50] | Z. Li, K. Dey, M. Chowdhury and P. Bhavsar, Connectivity supported dynamic routing of electric vehicles in an inductively coupled power transfer environment, IET Intelligent Transport Systems, 10 (2016), 370. doi: 10.1049/iet-its.2015.0154. |
[51] | S. Lukic and Z. Pantic, Cutting the cord: Static and dynamic inductive wireless charging of electric vehicles, IEEE Electrification Magazine, 1 (2013), 57-64. doi: 10.1109/MELE.2013.2273228. |
[52] | S. Mohrehkesh and T. Nadeem, Toward a wireless charging for battery electric vehicles at traffic intersections, in 2011 14th International IEEE Conference on Intelligent Transportation Systems (ITSC), IEEE, 2011,113–118. doi: 10.1109/ITSC.2011.6083137. |
[53] | N. Mouhrim, A. E. H. Alaoui and J. Boukachour, Optimal allocation of wireless power transfer system for electric vehicles in a multipath environment, in Logistics Operations Management (GOL), 2016 3rd International Conference on, IEEE, 2016, 1–7. doi: 10.1109/GOL.2016.7731684. |
[54] | M. Newman, Networks: An Introduction, Oxford University Press, Inc., New York, NY, USA, 2010. |
[55] | M. E. Newman, The mathematics of networks, The new palgrave encyclopedia of economics, 2 (2008), 1-12. |
[56] | P. Ning, J. M. Miller, O. C. Onar and C. P. White, A compact wireless charging system for electric vehicles, in Energy Conversion Congress and Exposition (ECCE), 2013 IEEE, IEEE, 2013, 3629–3634. doi: 10.1109/ECCE.2013.6647179. |
[57] | F. Pan, R. Bent, A. Berscheid and D. Izraelevitz, Locating phev exchange stations in v2g, in Smart Grid Communications (SmartGridComm), 2010 First IEEE International Conference on, IEEE, 2010,173–178. doi: 10.1109/SMARTGRID.2010.5622037. |
[58] | C. Panchal, S. Stegen and J. Lu, Review of static and dynamic wireless electric vehicle charging system, Engineering Science and Technology, an International Journal, 21 (2018), 922-937. doi: 10.1016/j.jestch.2018.06.015. |
[59] | C. Qiu, K. Chau, C. Liu and C. Chan, Overview of wireless power transfer for electric vehicle charging, in Electric Vehicle Symposium and Exhibition (EVS27), 2013 World, IEEE, 2013, 1–9. |
[60] | R. Riemann, D. Z. Wang and F. Busch, Optimal location of wireless charging facilities for electric vehicles: flow-capturing location model with stochastic user equilibrium, Transportation Research Part C: Emerging Technologies, 58 (2015), 1-12. |
[61] | A. Sarker, C. Qiu, H. Shen, A. Gil, J. Taiber, M. Chowdhury, J. Martin, M. Devine and A. Rindos, An efficient wireless power transfer system to balance the state of charge of electric vehicles, in Parallel Processing (ICPP), 2016 45th International Conference on, IEEE, 2016,324–333. doi: 10.1109/ICPP.2016.44. |
[62] | C. L. Staudt, M. Hamann, I. Safro, A. Gutfraind and H. Meyerhenke, Generating scaled replicas of real-world complex networks, in International Workshop on Complex Networks and their Applications, Springer, 2016, 17–28. doi: 10.1007/978-3-319-50901-3_2. |
[63] | K. D. Stetzel, L. L. Aldrich, M. S. Trimboli and G. L. Plett, Electrochemical state and internal variables estimation using a reduced-order physics-based model of a lithium-ion cell and an extended kalman filter, Journal of Power Sources, 278 (2015), 490-505. doi: 10.1016/j.jpowsour.2014.11.135. |
[64] | F. Sun, R. Xiong and H. He, A systematic state-of-charge estimation framework for multi-cell battery pack in electric vehicles using bias correction technique, Applied Energy, 162 (2016), 1399-1409. doi: 10.1016/j.apenergy.2014.12.021. |
[65] | C. Upchurch, M. Kuby and S. Lim, A model for location of capacitated alternative-fuel stations, Geographical Analysis, 41 (2009), 85-106. doi: 10.1111/j.1538-4632.2009.00744.x. |
[66] | US, Fuel economy, http://fueleconomy.gov/, 2017, Accessed: 03-29-2017. |
[67] | H. Ushijima-Mwesigwa, Z. Khan, M. A. Chowdhury and I. Safro, Centralities for networks with consumable resources, Network Science, 7 (2019), 376-401. doi: 10.1017/nws.2019.7. |
[68] | H. M. Ushijima-Mwesigwa, Models for networks with consumable resources: Applications to smart cities., |
[69] | D. Vilathgamuwa and J. Sampath, Wireless power transfer for electric vehicles, present and future trends, in Plug in Electric Vehicles in Smart Grids, Springer, 2015, 33–60. doi: 10.1007/978-981-287-299-9_2. |
[70] | T. Wang, B. Yang, C. Chen and X. Guan, Wireless charging lane deployment in urban areas considering traffic light and regional energy supply-demand balance, in 2019 IEEE 89th Vehicular Technology Conference (VTC2019-Spring), IEEE, 2019, 1–5. doi: 10.1109/VTCSpring.2019.8746492. |
[71] | W. Wang, D. Wang, X. Wang, T. Li, R. Ahmed, S. Habibi and A. Emadi, Comparison of kalman filter-based state of charge estimation strategies for li-ion batteries, in Transportation Electrification Conference and Expo (ITEC), 2016 IEEE, IEEE, 2016, 1–6. |
[72] | Y.-W. Wang, Locating flow-recharging stations at tourist destinations to serve recreational travelers, International Journal of Sustainable Transportation, 5 (2011), 153-171. doi: 10.1080/15568311003717199. |
[73] | Y.-W. Wang and C.-C. Lin, Locating road-vehicle refueling stations, Transportation Research Part E: Logistics and Transportation Review, 45 (2009), 821-829. doi: 10.1016/j.tre.2009.03.002. |
[74] | Y.-W. Wang and C.-C. Lin, Locating multiple types of recharging stations for battery-powered electric vehicle transport, Transportation Research Part E: Logistics and Transportation Review, 58 (2013), 76-87. doi: 10.1016/j.tre.2013.07.003. |
[75] | Y.-W. Wang and C.-R. Wang, Locating passenger vehicle refueling stations, Transportation Research Part E: Logistics and Transportation Review, 46 (2010), 791-801. doi: 10.1016/j.tre.2009.12.001. |
[76] | N. Watrin, B. Blunier and A. Miraoui, Review of adaptive systems for lithium batteries state-of-charge and state-of-health estimation, in Transportation Electrification Conference and Expo (ITEC), 2012 IEEE, IEEE, 2012, 1–6. |
[77] | S. Winter, Modeling costs of turns in route planning, GeoInformatica, 6 (2002), 345-361. doi: 10.1023/A:1020853410145. |
[78] | L. Zamparini and A. Reggiani, The value of travel time in passenger and freight transport: An overview, in Policy Analysis of Transport Networks, Routledge, 2016,161–178. |
[79] | C. Zhang, K. Li, L. Pei and C. Zhu, An integrated approach for real-time model-based state-of-charge estimation of lithium-ion batteries, Journal of Power Sources, 283 (2015), 24-36. doi: 10.1016/j.jpowsour.2015.02.099. |
[80] | S. Zhang, Z. Qian, J. Wu, F. Kong and S. Lu, Wireless charger placement and power allocation for maximizing charging quality, IEEE Transactions on Mobile Computing, 17 (2018), 1483-1496. doi: 10.1109/TMC.2017.2771425. |
Example of
Optimal solution with a four unit installation budget. The thick ends of the edges are used to indicate the direction of the edge. Taking
Directed toy graphs of 26 and 110 vertices used for problems 1 and 2, respectively. The bold end points on the edges of (a) represent edge directions. The graphs are subgraphs of the California road network taken from the dataset SNAP in [47]
Comparison of the different methods. The minimum number of WCL installation needed to eliminate all infeasible routes is
Figures (a) to (f) are plots showing the number of routes ending with final
Road segment graphs from real geospatial data: a node, drawn in blue, represents a road segment. Two road segments
Histograms showing the number of infeasible routes for different values of
The number of routes ending with final
Each boxplot depicts the average final
Using Betweenness Centrality Heuristic to find an Initial Solution