IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v252y2016i3p995-1018.html
   My bibliography  Save this article

The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations

Author

Listed:
  • Hiermann, Gerhard
  • Puchinger, Jakob
  • Ropke, Stefan
  • Hartl, Richard F.

Abstract

Due to new regulations and further technological progress in the field of electric vehicles, the research community faces the new challenge of incorporating the electric energy based restrictions into vehicle routing problems. One of these restrictions is the limited battery capacity which makes detours to recharging stations necessary, thus requiring efficient tour planning mechanisms in order to sustain the competitiveness of electric vehicles compared to conventional vehicles. We introduce the Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations (E-FSMFTW) to model decisions to be made with regards to fleet composition and the actual vehicle routes including the choice of recharging times and locations. The available vehicle types differ in their transport capacity, battery size and acquisition cost. Furthermore, we consider time windows at customer locations, which is a common and important constraint in real-world routing and planning problems. We solve this problem by means of branch-and-price as well as proposing a hybrid heuristic, which combines an Adaptive Large Neighbourhood Search with an embedded local search and labeling procedure for intensification. By solving a newly created set of benchmark instances for the E-FSMFTW and the existing single vehicle type benchmark using an exact method as well, we show the effectiveness of the proposed approach.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:252:y:2016:i:3:p:995-1018
    DOI: 10.1016/j.ejor.2016.01.038
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221716000837
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2016.01.038?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. David Pisinger & Stefan Ropke, 2010. "Large Neighborhood Search," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, chapter 0, pages 399-419, Springer.
    2. F-H Liu & S-Y Shen, 1999. "The fleet size and mix vehicle routing problem with time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 50(7), pages 721-732, July.
    3. 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.
    4. Roberto Baldacci & Enrico Bartolini & Aristide Mingozzi & Roberto Roberti, 2010. "An exact solution framework for a broad class of vehicle routing problems," Computational Management Science, Springer, vol. 7(3), pages 229-268, July.
    5. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    6. Bektas, Tolga & Laporte, Gilbert, 2011. "The Pollution-Routing Problem," Transportation Research Part B: Methodological, Elsevier, vol. 45(8), pages 1232-1250, September.
    7. Mauro Dell'Amico & Michele Monaci & Corrado Pagani & Daniele Vigo, 2007. "Heuristic Approaches for the Fleet Size and Mix Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 41(4), pages 516-526, November.
    8. Koç, Çağrı & Bektaş, Tolga & Jabali, Ola & Laporte, Gilbert, 2014. "The fleet size and mix pollution-routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 70(C), pages 239-254.
    9. 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.
    10. Christos D. Tarantilis & Emmanouil E. Zachariadis & Chris T. Kiranoudis, 2008. "A Hybrid Guided Local Search for the Vehicle-Routing Problem with Intermediate Replenishment Facilities," INFORMS Journal on Computing, INFORMS, vol. 20(1), pages 154-168, February.
    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. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms," Transportation Science, INFORMS, vol. 39(1), pages 104-118, February.
    13. Guy Desaulniers & François Lessard & Ahmed Hadjar, 2008. "Tabu Search, Partial Elementarity, and Generalized k -Path Inequalities for the Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 42(3), pages 387-404, August.
    14. W Dullaert & G K Janssens & K Sörensen & B Vernimmen, 2002. "New heuristics for the Fleet Size and Mix Vehicle Routing Problem with Time Windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(11), pages 1232-1238, November.
    15. 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.
    16. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part II: Metaheuristics," Transportation Science, INFORMS, vol. 39(1), pages 119-139, February.
    17. Abdelkader Sbihi & Richard Eglese, 2010. "Combinatorial optimization and Green Logistics," Annals of Operations Research, Springer, vol. 175(1), pages 159-175, March.
    18. Villeneuve, Daniel & Desaulniers, Guy, 2005. "The shortest path problem with forbidden paths," European Journal of Operational Research, Elsevier, vol. 165(1), pages 97-107, August.
    19. Crevier, Benoit & Cordeau, Jean-Francois & Laporte, Gilbert, 2007. "The multi-depot vehicle routing problem with inter-depot routes," European Journal of Operational Research, Elsevier, vol. 176(2), pages 756-773, January.
    20. G. Clarke & J. W. Wright, 1964. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, INFORMS, vol. 12(4), pages 568-581, August.
    21. Dekker, Rommert & Bloemhof, Jacqueline & Mallidis, Ioannis, 2012. "Operations Research for green logistics – An overview of aspects, issues, contributions and challenges," European Journal of Operational Research, Elsevier, vol. 219(3), pages 671-679.
    22. Stefan Ropke & Jean-François Cordeau, 2009. "Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 43(3), pages 267-286, August.
    23. Gerhard Hiermann & Matthias Prandtstetter & Andrea Rendl & Jakob Puchinger & Günther Raidl, 2015. "Metaheuristics for solving a multimodal home-healthcare scheduling problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 23(1), pages 89-113, March.
    24. Stefan Irnich & Daniel Villeneuve, 2006. "The Shortest-Path Problem with Resource Constraints and k -Cycle Elimination for k (ge) 3," INFORMS Journal on Computing, INFORMS, vol. 18(3), pages 391-406, August.
    25. 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.
    26. 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.
    27. Stefan Irnich & Guy Desaulniers, 2005. "Shortest Path Problems with Resource Constraints," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 33-65, Springer.
    28. Schneider, M. & Sand, B. & Stenger, A., 2013. "A Note on the Time Travel Approach for Handling Time Windows in Vehicle Routing Problems," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 62373, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    29. 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).
    30. 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.
    31. Olli Bräysy & Wout Dullaert & Geir Hasle & David Mester & Michel Gendreau, 2008. "An Effective Multirestart Deterministic Annealing Metaheuristic for the Fleet Size and Mix Vehicle-Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 42(3), pages 371-386, August.
    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. 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.
    2. 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).
    3. 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).
    4. Hiermann, Gerhard & Hartl, Richard F. & Puchinger, Jakob & Vidal, Thibaut, 2019. "Routing a mix of conventional, plug-in hybrid, and electric vehicles," European Journal of Operational Research, Elsevier, vol. 272(1), pages 235-248.
    5. 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.
    6. 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.
    7. 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.
    8. Bektaş, Tolga & Ehmke, Jan Fabian & Psaraftis, Harilaos N. & Puchinger, Jakob, 2019. "The role of operational research in green freight transportation," European Journal of Operational Research, Elsevier, vol. 274(3), pages 807-823.
    9. 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.
    10. Maximilian Schiffer & Grit Walther, 2018. "An Adaptive Large Neighborhood Search for the Location-routing Problem with Intra-route Facilities," Transportation Science, INFORMS, vol. 52(2), pages 331-352, March.
    11. 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.
    12. 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.
    13. 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).
    14. Shuai Zhang & Yuvraj Gajpal & S. S. Appadoo, 2018. "A meta-heuristic for capacitated green vehicle routing problem," Annals of Operations Research, Springer, vol. 269(1), pages 753-771, October.
    15. Koyuncu, Işıl & Yavuz, Mesut, 2019. "Duplicating nodes or arcs in green vehicle routing: A computational comparison of two formulations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 122(C), pages 605-623.
    16. Markov, Iliya & Varone, Sacha & Bierlaire, Michel, 2016. "Integrating a heterogeneous fixed fleet and a flexible assignment of destination depots in the waste collection VRP with intermediate facilities," Transportation Research Part B: Methodological, Elsevier, vol. 84(C), pages 256-273.
    17. Jose Carlos Molina & Ignacio Eguia & Jesus Racero, 2019. "Reducing pollutant emissions in a waste collection vehicle routing problem using a variable neighborhood tabu search algorithm: a case study," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 27(2), pages 253-287, July.
    18. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    19. Arslan, Okan & Yıldız, Barış & Karaşan, Oya Ekin, 2015. "Minimum cost path problem for Plug-in Hybrid Electric Vehicles," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 80(C), pages 123-141.
    20. 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.

    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:ejores:v:252:y:2016:i:3:p:995-1018. 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/locate/eor .

    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.