An exact algorithm for the electric-vehicle routing problem with nonlinear charging time

References

• Augerat, P., Belenguer, J. M., Benavent, E., Corberan, A., Naddef, D., & Rinaldi, G. (1998). Computational results with a branch-and-cut code for the capacitated vehicle routing problem. (Tech. Rep. No. 495). Istituto Di Analisi Dei Sistemi Ed Informatica.
   Google Scholar
• Avci, B., Girotra, K., & Netessine, S. (2015). Electric vehicles with a battery switching station: Adoption and environmental impact. Management Science, 61(4), 772–794. doi:10.1287/mnsc.2014.1916
   Web of Science ®Google Scholar
• Bard, J. F., Huang, L., Dror, M., & Jaillet, P. (1998). A branch and cut algorithm for the VRP with satellite facilities. IIE Transactions, 30(9), 821–834. doi:10.1080/07408179808966528
   Web of Science ®Google Scholar
• Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998). Branch-and-price: Column generation for solving huge integer programs. Operations Research, 46(3), 316–329. doi:10.1287/opre.46.3.316
   Web of Science ®Google Scholar
• Belotti, P., Lee, J., Liberti, L., Margot, F., & Waechter, A. (2009). Branching and bounds tightening techniques for non-convex MINLP. Optimization Methods and Software, 24(4–5), 597–634. doi:10.1080/10556780903087124
   Web of Science ®Google Scholar
• Bertsimas, D., & Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53. doi:10.1287/opre.1030.0065
   Web of Science ®Google Scholar
• Braekers, K., Ramaekers, K., & Van Nieuwenhuyse, I. (2016). The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 99, 300–313. doi:10.1016/j.cie.2015.12.007
   Web of Science ®Google Scholar
• Brumbaugh-Smith, J., & Shier, D. (1989). An empirical investigation of some bicriterion shortest path algorithms. European Journal of Operational Research, 43(2), 216–224. doi:10.1016/0377-2217(89)90215-4
   Web of Science ®Google Scholar
• Bullnheimer, B., Hartl, R. F., & Strauss, C. (1999). An improved ant system algorithm for thevehicle routing problem. Annals of Operations Research, 89, 319–328. doi:10.1023/A:1018940026670
   Web of Science ®Google Scholar
• Campbell, J. F. (1996). Hub Location and the p-Hub median problem. Operations Research, 44(6), 923–935. doi:10.1287/opre.44.6.923
   Web of Science ®Google Scholar
• Capar, I., & Kuby, M. (2012). An efficient formulation of the flow refueling location model for alternative-fuel stations. IIE Transactions, 44(8), 622–636. doi:10.1080/0740817X.2011.635175
   Web of Science ®Google Scholar
• Chabrier, A. (2006). Vehicle routing problem with elementary shortest path based column generation. Computers & Operations Research, 33(10), 2972–2990. doi:10.1016/j.cor.2005.02.029
   Web of Science ®Google Scholar
• Chung, S. H., & Kwon, C. (2015). Multi-period planning for electric car charging station locations: A case of Korean Expressways. European Journal of Operational Research, 242(2), 677–687. doi:10.1016/j.ejor.2014.10.029
   Web of Science ®Google Scholar
• Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568–581. doi:10.1287/opre.12.4.568
   Web of Science ®Google Scholar
• Conrad, R. G., & Figliozzi, M. A. (2011). The recharging vehicle routing problem. In IIE Annual Conference Proceedings.
   Google Scholar
• Cordeau, J.-F., Gendreau, M., Laporte, G., Potvin, J.-Y., & Semet, F. (2002). A guide to vehicle routing heuristics. Journal of the Operational Research Society, 53 (5), 512–522. doi:10.1057/palgrave.jors.2601319
   Web of Science ®Google Scholar
• Crevier, B., Cordeau, J.-F., & Laporte, G. (2007). The multi-depot vehicle routing problem with inter-depot routes. European Journal of Operational Research, 176(2), 756–773. doi:10.1016/j.ejor.2005.08.015
   Web of Science ®Google Scholar
• Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80–91. doi:10.1287/mnsc.6.1.80
   Web of Science ®Google Scholar
• Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8(1), 101–111. doi:10.1287/opre.8.1.101
   Web of Science ®Google Scholar
• Desaulniers, G., Errico, F., Irnich, S., & Schneider, M. (2016). Exact algorithms for electric vehicle-routing problems with time windows. Operations Research, 64(6), 1388–1405. doi:10.1287/opre.2016.1535
   Web of Science ®Google Scholar
• Desrochers, M., Desrosiers, J., & Solomon, M. (1992). A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 40(2), 342–354. doi:10.1287/opre.40.2.342
   Web of Science ®Google Scholar
• Drezner, Z., & Hamacher, H. W. (1995). Facility location. New York, NY: Springer-Verlag.
   Google Scholar
• Egbue, O., & Long, S. (2012). Barriers to widespread adoption of electric vehicles: An analysis of consumer attitudes and perceptions. Energy Policy, 48, 717–729. doi:10.1016/j.enpol.2012.06.009
   Web of Science ®Google Scholar
• Erdoğan, S., & Miller-Hooks, E. (2012). A green vehicle routing problem. Transportation Research Part E: Logistics and Transportation Review, 48(1), 100–114. doi:10.1016/j.tre.2011.08.001
   Web of Science ®Google Scholar
• Feillet, D., Dejax, P., Gendreau, M., & Gueguen, C. (2004). An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks, 44(3), 216–229. doi:10.1002/net.20033
   Web of Science ®Google Scholar
• Frade, I., Ribeiro, A., Gonçalves, G., & Antunes, A. (2011). Optimal location of charging stations for electric vehicles in a neighborhood in Lisbon, Portugal. Transportation Research Record: Journal of the Transportation Research Board, 2252 (1), 91–98. doi:10.3141/2252-12
   Web of Science ®Google Scholar
• Franke, T., Neumann, I., Bühler, F., Cocron, P., & Krems, J. F. (2012). Experiencing range in an electric vehicle: Understanding psychological barriers. Applied Psychology, 61(3), 368–391. doi:10.1111/j.1464-0597.2011.00474.x
   Web of Science ®Google Scholar
• Froger, A., Mendoza, J. E., Jabali, O., & Laporte, G. (2019). Improved formulations and algorithmic components for the electric vehicle routing problem with nonlinear charging functions. Computers & Operations Research, 104, 256–294. doi:10.1016/j.cor.2018.12.013
   Web of Science ®Google Scholar
• Gao, L., Liu, S., & Dougal, R. A. (2002). Dynamic lithium-ion battery model for system simulation. IEEE Transactions on Components and Packaging Technologies, 25(3), 495–505. doi:10.1109/TCAPT.2002.803653
   Web of Science ®Google Scholar
• Gao, Y., Zhang, C., Liu, Q., Jiang, Y., Ma, W., & Mu, Y. (2014). An optimal charging strategy of lithium-ion batteries based on polarization and temperature rise. In 2014 IEEE Conference and Expo Transportation Electrification Asia-Pacific (ITEC Asia-Pacific), 1–6 Aug. IEEE.
   Google Scholar
• Gendreau, M., Hertz, A., & Laporte, G. (1994). A tabu search heuristic for the vehicle routing problem. Management Science, 40(10), 1276–1290. doi:10.1287/mnsc.40.10.1276
   Web of Science ®Google Scholar
• Gendreau, M., Jabali, O., & Rei, W. (2016). 50th anniversary invited article—Future research directions in stochastic vehicle routing. Transportation Science, 50(4), 1163–1173. doi:10.1287/trsc.2016.0709
   Web of Science ®Google Scholar
• Gendreau, M., Laporte, G., & Séguin, R. (1995). An exact algorithm for the vehicle routing problem with stochastic demands and customers. Transportation Science, 29(2), 143–155. doi:10.1287/trsc.29.2.143
   Web of Science ®Google Scholar
• Gendreau, M., Laporte, G., & Séguin, R. (1996). Stochastic vehicle routing. European Journal of Operational Research, 88(1), 3–12. doi:10.1016/0377-2217(95)00050-X
   Web of Science ®Google Scholar
• Ghaziri, H. (1996). Supervision in the self-organizing feature map: Application to the vehicle routing problem. In Meta-heuristics (pp. 651–660). Boston, MA: Springer.
   Google Scholar
• Gianessi, P., Ceselli, A., Létocart, L., & Calvo, R. W. (2016). A branch & price & cut algorithm for the vehicle routing problem with intermediate replenishment facilities. Electronic Notes in Discrete Mathematics, 55, 93–96.
   Google Scholar
• Gillett, B. E., & Miller, L. R. (1974). A heuristic algorithm for the vehicle-dispatch problem. Operations Research, 22(2), 340–349. doi:10.1287/opre.22.2.340
   Web of Science ®Google Scholar
• Golden, B. L., Raghavan, S., & Wasil, E. A. (2008). The vehicle routing problem: latest advances and new challenges. (Vol. 43). New York, NY: Springer Science & Business Media.
   Google Scholar
• Han, J., Lee, C., & Park, S. (2014). A Robust scenario approach for the vehicle routing problem with uncertain travel times. Transportation Science, 48(3), 373–390. doi:10.1287/trsc.2013.0476
   Web of Science ®Google Scholar
• Hannan, M. A., Hoque, M. M., Hussain, A., Yusof, Y., & Ker, P. J. (2018). State-of-the-art and energy management system of lithium-ion batteries in electric vehicle applications: Issues and recommendations. IEEE Access., 6, 19362–19378. doi:10.1109/ACCESS.2018.2817655
   Web of Science ®Google Scholar
• Hoke, A., Brissette, A., Maksimović, D., Pratt, A., & Smith, K. (2011). Electric vehicle charge optimization including effects of lithium-ion battery degradation. In 2011 IEEE Vehicle Power and Propulsion Conference (pp. 1–8). IEEE.
   Google Scholar
• Ichoua, S., Gendreau, M., & Potvin, J.-Y. (2003). Vehicle dispatching with time-dependent travel times. European Journal of Operational Research, 144(2), 379–396. doi:10.1016/S0377-2217(02)00147-9
   Web of Science ®Google Scholar
• Ikeya, T., Sawada, N., Murakami, J-I., Kobayashi, K., Hattori, M., Murotani, N., … Ishihara, K. (2002). Multi-step constant-current charging method for an electric vehicle nickel/metal hydride battery with high-energy efficiency and long cycle life. Journal of Power Sources, 105(1), 6–12. doi:10.1016/S0378-7753(01)00907-7
   Web of Science ®Google Scholar
• International Energy Agency. (2016). Global EV Outlook 2016 (Tech. Rep.).
   Google Scholar
• Irnich, S., & Desaulniers, G. (2006). Shortest path problems with resource constraints. In Column generarion. Boston, MA: Springer.
   Google Scholar
• Jung, J., Chow, J. Y. J., Jayakrishnan, R., & Park, J. Y. (2014). Stochastic dynamic itinerary interception refueling location problem with queue delay for electric taxi charging stations. Transportation Research Part C: Emerging Technologies, 40, 123–142. doi:10.1016/j.trc.2014.01.008
   Web of Science ®Google Scholar
• Jung, J., Jayakrishnan, R., & Choi, K. (2015). A dually sustainable urban mobility option: shared-taxi operations with electric vehicles. International Journal of Sustainable Transportation, 11(8), 567–581. doi:10.1080/15568318.2015.1092057
   Web of Science ®Google Scholar
• Keskin, M., & Çatay, B. (2016). Partial recharge strategies for the electric vehicle routing problem with time windows. Transportation Research Part C: Emerging Technologies, 65, 111–127. doi:10.1016/j.trc.2016.01.013
   Web of Science ®Google Scholar
• Kim, J.-G., & Kuby, M. (2012). The deviation-flow refueling location model for optimizing a network of refueling stations. International Journal of Hydrogen Energy, 37(6), 5406–5420. doi:10.1016/j.ijhydene.2011.08.108
   Web of Science ®Google Scholar
• Koç, Ç., Jabali, O., Mendoza, J. E., & Laporte, G. (2019). The electric vehicle routing problem with shared charging stations. International Transactions in Operational Research, 26(4), 1211–1243. doi:10.1111/itor.12620
   Web of Science ®Google Scholar
• Kuby, M., & Lim, S. (2005). The flow-refueling location problem for alternative-fuel vehicles. Socio-Economic Planning Sciences, 39(2), 125–145. doi:10.1016/j.seps.2004.03.001
   Google Scholar
• Kuby, M., Lines, L., Schultz, R., Xie, Z., Kim, J.-G., & Lim, S. (2009). Optimization of hydrogen stations in Florida using the flow-refueling location model. International Journal of Hydrogen Energy, 34(15), 6045–6064. doi:10.1016/j.ijhydene.2009.05.050
   Web of Science ®Google Scholar
• Kullman, N., Goodson, J., & Mendoza, J. E. (2019). Electric vehicle routing with public charging stations. hal-01928730.
   Google Scholar
• Kumar, S. N., & Panneerselvam, R. (2012). A survey on the vehicle routing problem and its variants. Intelligent Information Management, 04(03), 66–74. doi:10.4236/iim.2012.43010
   Google Scholar
• Lam, S. K., Pitrou, A., & Seibert, S. (2015). Numba: A llvm-based python jit compile. In Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC.
   Google Scholar
• Laporte, G., & Louveaux, F. V. (1993). The integer L-shaped method for stochastic integer programs with complete recourse. Operations Research Letters, 13(3), 133–142. doi:10.1016/0167-6377(93)90002-X
   Web of Science ®Google Scholar
• Laporte, G., Louveaux, F. V., & Van Hamme, L. (2002). An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic demands. Operations Research, 50(3), 415–423. doi:10.1287/opre.50.3.415.7751
   Web of Science ®Google Scholar
• Lee, C., & Han, J. (2017). Benders-and-Price approach for electric vehicle charging station location problem under probabilistic travel range. Transportation Research Part B: Methodological, 106, 130–152. doi:10.1016/j.trb.2017.10.011
   Web of Science ®Google Scholar
• Lee, C., Lee, K., & Park, S. (2012). Robust vehicle routing problem with deadlines and travel time/demand uncertainty. Journal of the Operational Research Society, 63(9), 1294–1306. doi:10.1057/jors.2011.136
   Web of Science ®Google Scholar
• Lei, C., Lin, W.-H., & Miao, L. (2014). A multicut L-shaped based algorithm to solve a stochastic programming model for the mobile facility routing and scheduling problem. European Journal of Operational Research, 238(3), 699–710. doi:10.1016/j.ejor.2014.04.024
   Web of Science ®Google Scholar
• Lin, C., Choy, K. L., Ho, G. T., Chung, S. H., & Lam, H. Y. (2014). Survey of green vehicle routing problem: Past and future trends. Expert Systems with Applications, 41(4), 1118–1138. doi:10.1016/j.eswa.2013.07.107
   Web of Science ®Google Scholar
• Lin, J., Zhou, W., & Wolfson, O. (2016). Electric vehicle routing problem. Transportation Research Procedia, 12, 508–521. doi:10.1016/j.trpro.2016.02.007
   Google Scholar
• Lopes, J. A. P., Soares, F. J., & Almeida, P. M. R. (2011). Integration of electric vehicles in the electric power system. Proceedings of the IEEE, 99(1), 168–183. doi:10.1109/JPROC.2010.2066250
   Web of Science ®Google Scholar
• Lu, L., Han, X., Li, J., Hua, J., & Ouyang, M. (2013). A review on the key issues for lithium-ion battery management in electric vehicles. Journal of Power Sources, 226, 272–288. doi:10.1016/j.jpowsour.2012.10.060
   Web of Science ®Google Scholar
• Lübbecke, M. E., & Desrosiers, J. (2005). Selected topics in column generation. Operations Research, 53(6), 1007–1023. doi:10.1287/opre.1050.0234
   Web of Science ®Google Scholar
• Mak, H.-Y., Rong, Y., & Shen, Z.-J. M. (2013). Infrastructure planning for electric vehicles with battery swapping. Management Science, 59(7), 1557–1575. doi:10.1287/mnsc.1120.1672
   Web of Science ®Google Scholar
• Malandraki, C., & Daskin, M. S. (1992). Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms. Transportation Science, 26(3), 185–200. doi:10.1287/trsc.26.3.185
   Web of Science ®Google Scholar
• Miller, C. E., Tucker, A. W., & Zemlin, R. A. (1960). Integer programming formulation of traveling salesman problems. Journal of the ACM, 7(4), 326–329. doi:10.1145/321043.321046
   Web of Science ®Google Scholar
• Montoya, A., Guéret, C., Mendoza, J. E., & Villegas, J. G. (2017). The electric vehicle routing problem with nonlinear charging function. Transportation Research Part B: Methodological, 103, 1–24. doi:10.1016/j.trb.2017.02.004
   Web of Science ®Google Scholar
• Muter, I., Cordeau, J.-F., & Laporte, G. (2014). A branch-and-price algorithm for the multidepot vehicle routing problem with interdepot routes. Transportation Science, 48(3), 425–441. doi:10.1287/trsc.2013.0489
   Web of Science ®Google Scholar
• Notten, P. H., Het Veld, J. O., & Van Beek, J. (2005). Boostcharging Li-ion batteries: A challenging new charging concept. Journal of Power Sources, 145(1), 89–94. doi:10.1016/j.jpowsour.2004.12.038
   Web of Science ®Google Scholar
• Ordóñez, F. (2010). Robust vehicle routing. In Risk and optimization in an uncertain world (pp. 153–178). Catonsville, MD: INFORMS.
   Google Scholar
• Osman, I. H. (1993). Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 41(4), 421–451. doi:10.1007/BF02023004
   Google Scholar
• Parragh, S. N., Doerner, K. F., & Hartl, R. F. (2008). A survey on pickup and delivery problems. Journal Für Betriebswirtschaft, 58(1), 21–51. doi:10.1007/s11301-008-0036-4
   Google Scholar
• Rei, W., Gendreau, M., & Soriano, P. (2010). A hybrid Monte Carlo local branching algorithm for the single vehicle routing problem with stochastic demands. Transportation Science, 44(1), 136–146. doi:10.1287/trsc.1090.0295
   Web of Science ®Google Scholar
• Russell, R. A. (1977). Technical notean effective heuristic for the m-tour traveling salesman problem with some side conditions. Operations Research, 25(3), 517–524. doi:10.1287/opre.25.3.517
   Web of Science ®Google Scholar
• Sahinidis, N. V. (1996). Baron: A general purpose global optimization software package. Journal of Global Optimization, 8(2), 201–205. doi:10.1007/BF00138693
   Web of Science ®Google Scholar
• Said, D., Cherkaoui, S., & Khoukhi, L. (2013). Queuing model for EVs charging at public supply stations. In 2013 9th International Wireless Communications and Mobile Computing Conference (IWCMC 2013) (pp. 65–70). IEEE. doi:10.1109/IWCMC.2013.6583536
   Google Scholar
• Sarker, M. R., Pandzic, H., & Ortega-Vazquez, M. A. (2015). Optimal operation and services scheduling for an electric vehicle battery swapping station. IEEE Transactions on Power Systems, 30(2), 901–910. doi:10.1109/TPWRS.2014.2331560
   Web of Science ®Google Scholar
• Savelsbergh, M. W., & Sol, M. (1995). The general pickup and delivery problem. Transportation Science, 29(1), 17–29. doi:10.1287/trsc.29.1.17
   Web of Science ®Google Scholar
• Schneider, M., Stenger, A., & Goeke, D. (2014). The electric vehicle-routing problem with time windows and recharging stations. Transportation Science, 48(4), 500–520. doi:10.1287/trsc.2013.0490
   Web of Science ®Google Scholar
• Schücking, M., Jochem, P., Fichtner, W., Wollersheim, O., & Stella, K. (2017). Charging strategies for economic operations of electric vehicles in commercial applications. Transportation Research Part D: Transport and Environment, 51(91599), 173–189. doi:10.1016/j.trd.2016.11.032
   Web of Science ®Google Scholar
• Solano-Charris, E., Prins, C., & Santos, A. C. (2015). Local search based metaheuristics for the robust vehicle routing problem with discrete scenarios. Applied Soft Computing, 32, 518–531. doi:10.1016/j.asoc.2015.03.058
   Web of Science ®Google Scholar
• Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2), 254–265. doi:10.1287/opre.35.2.254
   Web of Science ®Google Scholar
• Sungur, I., Ordónez, F., & Dessouky, M. (2008). A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty. IIE Transactions, 40(5), 509–523. doi:10.1080/07408170701745378
   Web of Science ®Google Scholar
• Taccari, L. (2016). Integer programming formulations for the elementary shortest path problem. European Journal of Operational Research, 252(1), 122–130. doi:10.1016/j.ejor.2016.01.003
   Web of Science ®Google Scholar
• Tarantilis, C. D., Zachariadis, E. E., & Kiranoudis, C. T. (2008). A hybrid guided local search for the vehicle-routing problem with intermediate replenishment facilities. INFORMS Journal on Computing, 20(1), 154–168. doi:10.1287/ijoc.1070.0230
   Web of Science ®Google Scholar
• Toregas, C., Swain, R., ReVelle, C., & Bergman, L. (1971). The location of emergency service facilities. Operations Research, 19(6), 1363–1373. doi:10.1287/opre.19.6.1363
   Web of Science ®Google Scholar
• Toth, P., & Vigo, D. (2014). Vehicle routing: problems, methods, and applications. Philadelphia, PA: SIAM.
   Google Scholar
• Tremblay, O. (2015). Experimental validation of a battery dynamic model for EV applications. World Electric Vehicle Journal, 24 (3), 289–298. doi:10.3390/wevj3020289
   Google Scholar
• van Breedam, A. (1996). An analysis of the effect of local improvement operators in genetic algorithms and simulated annealing for the vehicle routing problem. Belgium: RUCA.
   Google Scholar
• Wang, Y.-W., & Lin, C.-C. (2009). Locating road-vehicle refueling stations. Transportation Research Part E: Logistics and Transportation Review, 45(5), 821–829. doi:10.1016/j.tre.2009.03.002
   Web of Science ®Google Scholar
• Wang, Y.-W., & Lin, C.-C. (2013). Locating multiple types of recharging stations for battery-powered electric vehicle transport. Transportation Research Part E: Logistics and Transportation Review, 58, 76–87. doi:10.1016/j.tre.2013.07.003
   Web of Science ®Google Scholar