IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v118y2018icp392-420.html
   My bibliography  Save this article

The dial-a-ride problem with electric vehicles and battery swapping stations

Author

Listed:
  • Masmoudi, Mohamed Amine
  • Hosny, Manar
  • Demir, Emrah
  • Genikomsakis, Konstantinos N.
  • Cheikhrouhou, Naoufel

Abstract

The Dial-a-Ride Problem (DARP) consists of designing vehicle routes and schedules for customers with special needs and/or disabilities. The DARP with Electric Vehicles and battery swapping stations (DARP-EV) concerns scheduling a fleet of EVs to serve a set of pre-specified transport requests during a certain planning horizon. In addition, EVs can be recharged by swapping their batteries with charged ones from any battery-swap stations. We propose three enhanced Evolutionary Variable Neighborhood Search (EVO-VNS) algorithms to solve the DARP-EV. Extensive computational experiments highlight the relevance of the problem and confirm the efficiency of the proposed EVO-VNS algorithms in producing high quality solutions.

Suggested Citation

  • Masmoudi, Mohamed Amine & Hosny, Manar & Demir, Emrah & Genikomsakis, Konstantinos N. & Cheikhrouhou, Naoufel, 2018. "The dial-a-ride problem with electric vehicles and battery swapping stations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 392-420.
    • Handle: RePEc:eee:transe:v:118:y:2018:i:c:p:392-420
    DOI: 10.1016/j.tre.2018.08.005
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554517310086
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2018.08.005?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Jeongyong Kim & Inho Song & Woongchul Choi, 2015. "An Electric Bus with a Battery Exchange System," Energies, MDPI, vol. 8(7), pages 1-14, July.
    2. Stefan Ropke & David Pisinger, 2006. "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 40(4), pages 455-472, November.
    3. Ho-Yin Mak & Ying Rong & Zuo-Jun Max Shen, 2013. "Infrastructure Planning for Electric Vehicles with Battery Swapping," Management Science, INFORMS, vol. 59(7), pages 1557-1575, July.
    4. Tolga Bektaş & Emrah Demir & Gilbert Laporte, 2016. "Green Vehicle Routing," International Series in Operations Research & Management Science, in: Harilaos N. Psaraftis (ed.), Green Transportation Logistics, edition 127, chapter 0, pages 243-265, Springer.
    5. He, Fang & Wu, Di & Yin, Yafeng & Guan, Yongpei, 2013. "Optimal deployment of public charging stations for plug-in hybrid electric vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 47(C), pages 87-101.
    6. Briseida Sarasola & Karl Doerner & Verena Schmid & Enrique Alba, 2016. "Variable neighborhood search for the stochastic and dynamic vehicle routing problem," Annals of Operations Research, Springer, vol. 236(2), pages 425-461, January.
    7. R M Jorgensen & J Larsen & K B Bergvinsdottir, 2007. "Solving the Dial-a-Ride problem using genetic algorithms," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(10), pages 1321-1331, October.
    8. Bektas, Tolga & Laporte, Gilbert, 2011. "The Pollution-Routing Problem," Transportation Research Part B: Methodological, Elsevier, vol. 45(8), pages 1232-1250, September.
    9. Gonzales, Eric J., 2016. "Demand responsive transit systems with time-dependent demand: User equilibrium, system optimum, and management strategyAuthor-Name: Amirgholy, Mahyar," Transportation Research Part B: Methodological, Elsevier, vol. 92(PB), pages 234-252.
    10. Kalayci, Can B. & Kulak, Osman & Günther, Hans-Otto, 2015. "A perturbation based variable neighborhood search heuristic for solving the Vehicle Routing Problem with Simultaneous Pickup and Delivery with Time LimitAuthor-Name: Polat, Olcay," European Journal of Operational Research, Elsevier, vol. 242(2), pages 369-382.
    11. Cordeau, Jean-François & Laporte, Gilbert, 2003. "A tabu search heuristic for the static multi-vehicle dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 37(6), pages 579-594, July.
    12. Liu, Haoxiang & Wang, David Z.W., 2017. "Locating multiple types of charging facilities for battery electric vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 30-55.
    13. Mladenović, Nenad & Urošević, Dragan & Hanafi, Saı¨d & Ilić, Aleksandar, 2012. "A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem," European Journal of Operational Research, Elsevier, vol. 220(1), pages 270-285.
    14. Xiang, Zhihai & Chu, Chengbin & Chen, Haoxun, 2006. "A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints," European Journal of Operational Research, Elsevier, vol. 174(2), pages 1117-1139, October.
    15. Potvin, Jean-Yves & Rousseau, Jean-Marc, 1993. "A parallel route building algorithm for the vehicle routing and scheduling problem with time windows," European Journal of Operational Research, Elsevier, vol. 66(3), pages 331-340, May.
    16. Boyacı, Burak & Zografos, Konstantinos G. & Geroliminis, Nikolas, 2017. "An integrated optimization-simulation framework for vehicle and personnel relocations of electric carsharing systems with reservations," Transportation Research Part B: Methodological, Elsevier, vol. 95(C), pages 214-237.
    17. Goeke, D. & Schneider, M., 2015. "Routing a Mixed Fleet of Electric and Conventional Vehicles," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 65939, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    18. Schiffer, Maximilian & Walther, Grit, 2017. "The electric location routing problem with time windows and partial recharging," European Journal of Operational Research, Elsevier, vol. 260(3), pages 995-1013.
    19. Detti, Paolo & Papalini, Francesco & Lara, Garazi Zabalo Manrique de, 2017. "A multi-depot dial-a-ride problem with heterogeneous vehicles and compatibility constraints in healthcare," Omega, Elsevier, vol. 70(C), pages 1-14.
    20. Erdoğan, Sevgi & Miller-Hooks, Elise, 2012. "A Green Vehicle Routing Problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 100-114.
    21. Wang, Ying-Wei & Lin, Chuah-Chih, 2013. "Locating multiple types of recharging stations for battery-powered electric vehicle transport," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 58(C), pages 76-87.
    22. Braekers, Kris & Kovacs, Attila A., 2016. "A multi-period dial-a-ride problem with driver consistency," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 355-377.
    23. Guy Desaulniers & Fausto Errico & Stefan Irnich & Michael Schneider, 2016. "Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows," Operations Research, INFORMS, vol. 64(6), pages 1388-1405, December.
    24. Sayarshad, Hamid R. & Chow, Joseph Y.J., 2015. "A scalable non-myopic dynamic dial-a-ride and pricing problem," Transportation Research Part B: Methodological, Elsevier, vol. 81(P2), pages 539-554.
    25. Martínez-Lao, Juan & Montoya, Francisco G. & Montoya, Maria G. & Manzano-Agugliaro, Francisco, 2017. "Electric vehicles in Spain: An overview of charging systems," Renewable and Sustainable Energy Reviews, Elsevier, vol. 77(C), pages 970-983.
    26. Mahmoud, Moataz & Garnett, Ryan & Ferguson, Mark & Kanaroglou, Pavlos, 2016. "Electric buses: A review of alternative powertrains," Renewable and Sustainable Energy Reviews, Elsevier, vol. 62(C), pages 673-684.
    27. Briseida Sarasola & Karl F. Doerner & Verena Schmid & Enrique Alba, 2016. "Variable neighborhood search for the stochastic and dynamic vehicle routing problem," Annals of Operations Research, Springer, vol. 236(2), pages 425-461, January.
    28. Jean-François Cordeau & Gilbert Laporte, 2007. "The dial-a-ride problem: models and algorithms," Annals of Operations Research, Springer, vol. 153(1), pages 29-46, September.
    29. Yves Molenbruch & Kris Braekers & An Caris, 2017. "Typology and literature review for dial-a-ride problems," Annals of Operations Research, Springer, vol. 259(1), pages 295-325, December.
    30. Zhang, Zhenzhen & Liu, Mengyang & Lim, Andrew, 2015. "A memetic algorithm for the patient transportation problem," Omega, Elsevier, vol. 54(C), pages 60-71.
    31. Demir, Emrah & Huang, Yuan & Scholts, Sebastiaan & Van Woensel, Tom, 2015. "A selected review on the negative externalities of the freight transportation: Modeling and pricing," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 77(C), pages 95-114.
    32. Sujie Shao & Shaoyong Guo & Xuesong Qiu, 2017. "A Mobile Battery Swapping Service for Electric Vehicles Based on a Battery Swapping Van," Energies, MDPI, vol. 10(10), pages 1-21, October.
    33. Carrizosa, Emilio & Mladenović, Nenad & Todosijević, Raca, 2013. "Variable neighborhood search for minimum sum-of-squares clustering on networks," European Journal of Operational Research, Elsevier, vol. 230(2), pages 356-363.
    34. Schilde, M. & Doerner, K.F. & Hartl, R.F., 2014. "Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem," European Journal of Operational Research, Elsevier, vol. 238(1), pages 18-30.
    35. Hemmelmayr, Vera C. & Doerner, Karl F. & Hartl, Richard F., 2009. "A variable neighborhood search heuristic for periodic routing problems," European Journal of Operational Research, Elsevier, vol. 195(3), pages 791-802, June.
    36. Hof, Julian & Schneider, Michael & Goeke, Dominik, 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: Methodological, Elsevier, vol. 97(C), pages 102-112.
    37. Demir, Emrah & Bektaş, Tolga & Laporte, Gilbert, 2012. "An adaptive large neighborhood search heuristic for the Pollution-Routing Problem," European Journal of Operational Research, Elsevier, vol. 223(2), pages 346-359.
    38. Liu, Mengyang & Luo, Zhixing & Lim, Andrew, 2015. "A branch-and-cut algorithm for a realistic dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 267-288.
    39. Goeke, Dominik & Schneider, Michael, 2015. "Routing a mixed fleet of electric and conventional vehicles," European Journal of Operational Research, Elsevier, vol. 245(1), pages 81-99.
    40. Xu, Min & Meng, Qiang & Liu, Kai & Yamamoto, Toshiyuki, 2017. "Joint charging mode and location choice model for battery electric vehicle users," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 68-86.
    41. Michael Schneider & Andreas Stenger & Dominik Goeke, 2014. "The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations," Transportation Science, INFORMS, vol. 48(4), pages 500-520, November.
    42. Nie, Yu (Marco) & Ghamami, Mehrnaz, 2013. "A corridor-centric approach to planning electric vehicle charging infrastructure," Transportation Research Part B: Methodological, Elsevier, vol. 57(C), pages 172-190.
    43. Todosijević, Raca & Benmansour, Rachid & Hanafi, Saïd & Mladenović, Nenad & Artiba, Abdelhakim, 2016. "Nested general variable neighborhood search for the periodic maintenance problem," European Journal of Operational Research, Elsevier, vol. 252(2), pages 385-396.
    44. Masmoudi, Mohamed Amine & Hosny, Manar & Braekers, Kris & Dammak, Abdelaziz, 2016. "Three effective metaheuristics to solve the multi-depot multi-trip heterogeneous dial-a-ride problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 96(C), pages 60-80.
    45. Pelletier, Samuel & Jabali, Ola & Laporte, Gilbert & Veneroni, Marco, 2017. "Battery degradation and behaviour for electric vehicles: Review and numerical analyses of several models," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 158-187.
    46. Adler, Jonathan D. & Mirchandani, Pitu B., 2014. "Online routing and battery reservations for electric vehicles with swappable batteries," Transportation Research Part B: Methodological, Elsevier, vol. 70(C), pages 285-302.
    47. Roberti, R. & Wen, M., 2016. "The Electric Traveling Salesman Problem with Time Windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 89(C), pages 32-52.
    48. Guan, Jian & Lin, Geng, 2016. "Hybridizing variable neighborhood search with ant colony optimization for solving the single row facility layout problem," European Journal of Operational Research, Elsevier, vol. 248(3), pages 899-909.
    49. Felipe, Ángel & Ortuño, M. Teresa & Righini, Giovanni & Tirado, Gregorio, 2014. "A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 71(C), pages 111-128.
    50. Liao, Chung-Shou & Lu, Shang-Hung & Shen, Zuo-Jun Max, 2016. "The electric vehicle touring problem," Transportation Research Part B: Methodological, Elsevier, vol. 86(C), pages 163-180.
    51. Zhou, Boya & Wu, Ye & Zhou, Bin & Wang, Renjie & Ke, Wenwei & Zhang, Shaojun & Hao, Jiming, 2016. "Real-world performance of battery electric buses and their life-cycle benefits with respect to energy consumption and carbon dioxide emissions," Energy, Elsevier, vol. 96(C), pages 603-613.
    52. Hiermann, Gerhard & Puchinger, Jakob & Ropke, Stefan & Hartl, Richard F., 2016. "The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations," European Journal of Operational Research, Elsevier, vol. 252(3), pages 995-1018.
    53. Braekers, Kris & Caris, An & Janssens, Gerrit K., 2014. "Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots," Transportation Research Part B: Methodological, Elsevier, vol. 67(C), pages 166-186.
    54. Montoya, Alejandro & Guéret, Christelle & Mendoza, Jorge E. & Villegas, Juan G., 2017. "The electric vehicle routing problem with nonlinear charging function," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 87-110.
    55. Wei, Lijun & Zhang, Zhenzhen & Zhang, Defu & Lim, Andrew, 2015. "A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 243(3), pages 798-814.
    56. Schneider, M. & Stenger, A. & Goeke, D., 2014. "The Electric Vehicle Routing Problem with Time Windows and Recharging Stations," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 62382, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    57. J-F Cordeau & G Laporte & A Mercier, 2001. "A unified tabu search heuristic for vehicle routing problems with time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(8), pages 928-936, August.
    58. Martin W. P. Savelsbergh, 1992. "The Vehicle Routing Problem with Time Windows: Minimizing Route Duration," INFORMS Journal on Computing, INFORMS, vol. 4(2), pages 146-154, May.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Asghari, Mohammad & Mirzapour Al-e-hashem, S. Mohammad J., 2021. "Green vehicle routing problem: A state-of-the-art review," International Journal of Production Economics, Elsevier, vol. 231(C).
    2. Mohammad Asghari & Seyed Mohammad Javad Mirzapour Al-E-Hashem, 2021. "Green vehicle routing problem: A state-of-the-art review," Post-Print hal-03182944, HAL.
    3. Raeesi, Ramin & Zografos, Konstantinos G., 2020. "The electric vehicle routing problem with time windows and synchronised mobile battery swapping," Transportation Research Part B: Methodological, Elsevier, vol. 140(C), pages 101-129.
    4. Shen, Zuo-Jun Max & Feng, Bo & Mao, Chao & Ran, Lun, 2019. "Optimization models for electric vehicle service operations: A literature review," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 462-477.
    5. Sadati, Mir Ehsan Hesam & Çatay, Bülent, 2021. "A hybrid variable neighborhood search approach for the multi-depot green vehicle routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    6. Bongiovanni, Claudia & Kaspi, Mor & Geroliminis, Nikolas, 2019. "The electric autonomous dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 122(C), pages 436-456.
    7. Xiao, Yiyong & Zhang, Yue & Kaku, Ikou & Kang, Rui & Pan, Xing, 2021. "Electric vehicle routing problem: A systematic review and a new comprehensive model with nonlinear energy recharging and consumption," Renewable and Sustainable Energy Reviews, Elsevier, vol. 151(C).
    8. Schiffer, Maximilian & Schneider, Michael & Laporte, Gilbert, 2018. "Designing sustainable mid-haul logistics networks with intra-route multi-resource facilities," European Journal of Operational Research, Elsevier, vol. 265(2), pages 517-532.
    9. Raeesi, Ramin & Zografos, Konstantinos G., 2022. "Coordinated routing of electric commercial vehicles with intra-route recharging and en-route battery swapping," European Journal of Operational Research, Elsevier, vol. 301(1), pages 82-109.
    10. Goeke, Dominik & Schneider, Michael, 2015. "Routing a mixed fleet of electric and conventional vehicles," European Journal of Operational Research, Elsevier, vol. 245(1), pages 81-99.
    11. Goeke, D. & Schneider, M., 2015. "Routing a Mixed Fleet of Electric and Conventional Vehicles," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 65939, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    12. Schiffer, Maximilian & Walther, Grit, 2018. "Strategic planning of electric logistics fleet networks: A robust location-routing approach," Omega, Elsevier, vol. 80(C), pages 31-42.
    13. Ho, Sin C. & Szeto, W.Y. & Kuo, Yong-Hong & Leung, Janny M.Y. & Petering, Matthew & Tou, Terence W.H., 2018. "A survey of dial-a-ride problems: Literature review and recent developments," Transportation Research Part B: Methodological, Elsevier, vol. 111(C), pages 395-421.
    14. Zhang, Shuai & Gajpal, Yuvraj & Appadoo, S.S. & Abdulkader, M.M.S., 2018. "Electric vehicle routing problem with recharging stations for minimizing energy consumption," International Journal of Production Economics, Elsevier, vol. 203(C), pages 404-413.
    15. Goeke, Dominik, 2019. "Granular tabu search for the pickup and delivery problem with time windows and electric vehicles," European Journal of Operational Research, Elsevier, vol. 278(3), pages 821-836.
    16. Li, Lu & Lo, Hong K. & Huang, Wei & Xiao, Feng, 2021. "Mixed bus fleet location-routing-scheduling under range uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 146(C), pages 155-179.
    17. Mohamed Amine Masmoudi & Manar Hosny & Emrah Demir & Erwin Pesch, 2020. "Hybrid adaptive large neighborhood search algorithm for the mixed fleet heterogeneous dial-a-ride problem," Journal of Heuristics, Springer, vol. 26(1), pages 83-118, February.
    18. Montoya, Alejandro & Guéret, Christelle & Mendoza, Jorge E. & Villegas, Juan G., 2017. "The electric vehicle routing problem with nonlinear charging function," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 87-110.
    19. Malladi, Satya S. & Christensen, Jonas M. & Ramírez, David & Larsen, Allan & Pacino, Dario, 2022. "Stochastic fleet mix optimization: Evaluating electromobility in urban logistics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    20. Su, Yue & Dupin, Nicolas & Puchinger, Jakob, 2023. "A deterministic annealing local search for the electric autonomous dial-a-ride problem," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1091-1111.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transe:v:118:y:2018:i:c:p:392-420. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.