A mathematical model for the electric vehicle routing with time windows considering queuing system at charging stations and alternative paths

Document Type : Research Paper

Authors

Department of Industrial Engineering, K.N. Toosi University of Technology, Tehran, Iran

Abstract

Due to many damages that human activities have imposed on the environment, authorities, manufacturers, and industry owners have taken into account the development of supply chain more than ever. One of the most influential and essential human activities in the supply chain are transportation which green vehicles such as electric vehicles (EVs) are expected to generate higher economic and environmental impact. To this end, designing efficient routing scheme for the fleet of EVs is significant. A remarkable issue about EVs is their need to stations for charging their battery. Due to the existence of time limitations, more attention should be paid to time spent at the charging station, so considering the queuing system at charging stations makes more precise time calculations.  Furthermore, multi-graphs are more consistent with the characteristics of the transportation network. Hence, we consider alternative paths including two criterion cost and energy consumption in the network. First, we develop a mixed integer linear programming for the electric vehicle routing problem on a multi-graph with the queue in charging stations to minimize the traveling and charging costs. Since the proposed problem is NP-hard in a strong sense, we provide a simulated annealing algorithm to search the solution space efficiently and explore a large neighborhood within short computational time.  The efficiency of the model is investigated with numerical and illustrative examples. Then the sensitivity analysis is performed on the proposed model to indicate the importance of the queuing system and the impact of battery capacity on the penetration of EVs.

Keywords

Main Subjects

References

Afifi, S., Dang, D. C., and Moukrim, A. (2013).A simulated annealing algorithm for the vehicle routing problem with time windows and synchronization constraints. Proc., Learning and Intelligent Optimization Conf. LION7, Springer, Berlin, 1–6.
Agrawal, Sh., Zheng, H., Peeta, S., Kumar, A. (2016). Routing aspects of electric vehicle drivers and their effects on network performance. Transportation Research Part D, 46, 246-266.
Bent, R., & Hentenryck, P. V. (2004). A two-stage hybrid local search for the vehicle routing problem with time windows. Transportation Science, 38, 515–530.
Breedam, A. V. (1995). Improvement heuristics for the vehicle routing problem based on simulated annealing. European Journal of Operational Research, 86,480–490.
Bruglieri, M., Mancini, S., Pezzella, F., Pisacane, O., Suraci, S. (2017). A three-phase matheuristic for the time-effective electric vehicle routing problem with partial recharges. Electronic Notes in Discrete Mathematics, 58, 95-102.
Bruglieria, M., Pezzella, F., Pisacanec, O., Suraci, S. (2015). A Variable Neighborhood Search Branching for the Electric Vehicle Routing Problem with Time Windows. Electronic Notes in Discrete Mathematics, 47(15), 221-228.
Cerny, V. (1985). Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm. Journal of Optimization Theory and Applications, 45(1), 41-51.
Chiang, W. C., & Russell, R. A. (1996). Simulated annealing metaheuristics for the vehicle routing problem with time windows.Annals of Operations Research, 63,3–27.
Felipe, A., Ortuno, M.T., Righini, G., Tirado, G. (2014). A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges. Transportation Research Part E, 71, 111-128.
Garaix, T., Artigues, C., Feillet, D., Josselin, D. (2010). Vehicle routing problems with alternative paths: An application to on-demand transportation. European Journal of Operation Research, 204, 62-75.
Hiermann, G., Puchinger, J., Ropke, S., F.Hartl, R. (2016). The electric fleet size and mix vehicle routing problem with time windows and recharging stations. European Journal of Operational Research, 252, 995-1018.
Hof, J., Schneider, M., Goeke, D. (2017). Solving the battery swap station location-routing problem with capacitated electric vehicles using an AVNS algorithm for vehicle-routing problems with intermediate stops. Transportation Research Part B, 97, 102-112.
Huang, Y., Zhao, L., Woensel, T.V., Gross, J. (2017).Time-dependent vehicle routing problem with path flexibility. Transportation Research Part B, 95, 169-195.
Johnson, D. S., Aragon, C. R., McGeoch, L. A., & Schevon, C. (1989). Optimization by simulated annealing: An experimental evaluation: Part I, graph partitioning. Operations Research, 37, 865–892.
Kassam, S., Chen, M. (2013). Solving reverse logistics vehicle routing problem with time windows. The International Journal of Advanced Manufacturing Technology, 68, 57-68.
Keskin, M., Catay, B. (2016). Partial recharge strategies for the electric vehicle routing problem with time windows. Transportation Research Part C, 65, 111-127.
Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P. (1983). Optimization by Simulated Annealing. Science, New Series, 220(4598), 671-680.
Li, Sh., H, Y., J.Mason, S. (2016). A multi-period optimization model for the deployment of public electric vehicle charging stations on network. Transportation Research Part C, 65, 128-143.
Li-ying, W., Yuan-bin, S. (2015). Multiple charging station Location-Routing Problem with time window of electric vehicle. Journal of Engineering Science and Technology Review, 8(5), 190-201.
Osman, I. H. (1993). Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 41, 421–451.
Pelletier, S., Jabali, O., Laporte, G. (2016). Goods Distribution with Electric Vehicles: Review. Vol. 50, No. 1, 3-22.
Penna, P., Afsar, H.M., Prins, Ch. (2016). A hybrid iterative local search algorithm for the electric fleet size and mix vehicle routing problem with time windows and recharging stations. IFAC-PaperOnLine, 49-12, 955-960.
Qiu, G., Liu, W., Zhang, J. (2013). Equipment Optimization Method of Electric Vehicle Fast Charging Station Based on Queuing Theory. Applied Mechanics and Materials, Vols. 291-294, 872-877.
Roberti, R., Wen, M. (2016). The electric traveling salesman problem with time windows. Transportation Research Part E, 89, 32-52.
S.W. Lai, D., Caliskan Demirag, O., M.Y. Leung, J. (2016). A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph. Transportation Research Part E, 86, 32-52.
Said, D., Cherkaoui, S., Khoukhi, L. (2013). Queuing Model for EVs Charging at public supply stations. International Wireless Communications and Mobile Computing Conference (IWCMC), 9.
Schneider, M., Stenger, A., Goeke, D. (2014). The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations. Transportation Science, 1-21.
Setak, M., Habibi, M., Karimi, H., Abedzadeh, M. (2015). A time-dependent vehicle routing problem in multigraph with FIFO property. Journal of Manufacturing systems, 35, 37-45.
Setak, M., Shakeri, Z., Patoghi, A. (2017). A time dependent pollution routing problem in multi-graph. Internathional Journal of Engineering, Vol. 30, No. 2, 234-242.
Sweda, T.M., Dolinskaya, I.S., Klabjan, D. (2017). Adaptive Routing and Recharging Policies for Electric Vehicles. Transportation science, 1-23.
Tavakkoli-Moghaddam, R., Gazanfari, M., Alinaghian, M., Salamatnakhsh, A., Norouzi, N. (2011). A new mathematical model for a competitive vehicle routing problems with time windows solved by simulated annealing. Journal of Manufacturing Systems, 30, 83–92.
Tavakkoli-Moghaddam, R., Safaei, N., & Gholipour, Y. (2006). A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length. Applied Mathematics and Computation, 176, 445–454.
Tikani, H., Setak, M. (2018). Efficient solution algorithms for a time-critical reliable transportation problem in multigraph networks with FIFO property. Applied Soft Computing, 74, 504-528.
Tikani, H., Setak, M. (2019). Ambulance routing in disaster response scenario considering different types of ambulances and semi soft time windows. Journal of Industrial and Systems Engineering 12.1.
Vincent, F., Yu, A.A.N., Redi, P., Hidayat, Y.A., Wibowo, O.J. (2017). A simulated annealing heuristic for the hybrid vehicle routing problem. Applied Soft computing, 53, 119-132.
Wang, Y., Bi, J., Guan, W., Zhao, X. (2017). Optimising route choices for the traveling and charging of battery electric vehicles by considering multiple objectives. Transportation Research Part D.
Wang, Y., Haung, Y., Xu, J., Barclay, N. (2017). Optimal recharging scheduling for urban electric buses: A case study in Davis. Transportation Research Part E, 100, 115-132.
Xiao, Y., Zhao, Q., Kaku, I., Xu, Y. (2012). Development of a fuel consumption optimization model for the capacitated vehicle routing problem. Computers & Operations Research, 39, 1419-1431.
Yang, H., Yang, S., Xu, Y., Cao, E., Lai, M., Dong, Zh. (2015). Electric vehicle route optimization considering time-of-use electricity price by learnable partheno-genetic algorithm. IEEE Transactions on smart grid, VOL. 6, NO. 2, 657-666.
Yang, J., Dong, J., Hu, L.. (2017). A data-driven optimization-based approach for siting and sizing of electric taxi charging stations. Transportation Research Part C, 77, 462-477.
Yang, J., Sun, H. (2015). Battery swap station location-routing problem with capacitated electric vehicles. Computer and operation science, Vol. 55, 217-232.
Yang, Sh., Cheng, W., Hsu, Y., Guan, Ch., Lin, Y. (2014). Charge scheduling of electric vehicles in highways. Mathematical and computer modeling, 57, 2873-2882.
Yang, T., Peters, B. A., & Tu, M. (2005). Layout design for flexible manufacturing systems considering single-loop directional flow patterns. European Journal of Operational Research, 164, 440–455.
Journal of Industrial and Systems Engineering
Volume 12, Issue 1 - Serial Number 1
January 2019
Pages 284-306

Files

History

  • Receive Date: 12 September 2018
  • Revise Date: 23 November 2018
  • Accept Date: 17 January 2019

Share

How to cite

Statistics