Partial recharge strategies for the electric vehicle routing problem with time windows

The Electric Vehicle Routing Problem with Time Windows (EVRPTW) is an extension to the well-known Vehicle Routing Problem with Time Windows (VRPTW) where the fleet consists of electric vehicles (EVs). Since EVs have limited driving range due to their battery capacities they may need to visit recharging stations while servicing the customers along their route. The recharging may take place at any battery level and after the recharging the battery is assumed to be full. In this paper, the authors relax the full recharge restriction and allow partial recharging (EVRPTW-PR), which is more practical in the real world due to shorter recharging duration. The authors formulate this problem as a 0–1 mixed integer linear program and develop an Adaptive Large Neighborhood Search (ALNS) algorithm to solve it efficiently. The authors apply several removal and insertion mechanisms by selecting them dynamically and adaptively based on their past performances, including new mechanisms specifically designed for EVRPTW and EVRPTW-PR. These new mechanisms include the removal of the stations independently or along with the preceding or succeeding customers and the insertion of the stations with determining the charge amount based on the recharging decisions. The authors test the performance of ALNS by using benchmark instances from the recent literature. The computational results show that the proposed method is effective in finding high quality solutions and the partial recharging option may significantly improve the routing decisions.

• Record URL:
  https://doi.org/10.1016/j.trc.2016.01.013
• Record URL:
  http://www.sciencedirect.com/science/article/pii/S0968090X16000322
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/0968090X
• Supplemental Notes:
  • Abstract reprinted with permission of Elsevier.
• Authors:
  • Keskin, Merve
  • Çatay, Bülent
• Publication Date: 2016-4

Language

• English

Media Info

• Media Type: Web
• Features: Appendices; Figures; References; Tables;
• Pagination: pp 111-127
• Serial:
  • Transportation Research Part C: Emerging Technologies
  • Volume: 65
  • Publisher: Elsevier
  • ISSN: 0968-090X
  • Serial URL: http://www.sciencedirect.com/science/journal/0968090X

Subject/Index Terms

• TRT Terms: Electric vehicle charging; Electric vehicles; Integer programming; Optimization; Routing; Time windows
• Uncontrolled Terms: Metaheuristics; Vehicle routing problem
• Subject Areas: Energy; Highways; Planning and Forecasting; Vehicles and Equipment;

Filing Info

• Accession Number: 01597646
• Record Type: Publication
• Files: TRIS
• Created Date: Apr 28 2016 2:43PM