{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T02:59:54Z","timestamp":1771469994884,"version":"3.50.1"},"reference-count":39,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2019,2,20]],"date-time":"2019-02-20T00:00:00Z","timestamp":1550620800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["71801058"],"award-info":[{"award-number":["71801058"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004607","name":"Guangxi Natural Science Foundation","doi-asserted-by":"publisher","award":["2018JJB110017"],"award-info":[{"award-number":["2018JJB110017"]}],"id":[{"id":"10.13039\/501100004607","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>To develop a non-polluting and sustainable city, urban administrators encourage logistics companies to use electric vehicles instead of conventional (i.e., fuel-based) vehicles for transportation services. However, electric energy-based limitations pose a new challenge in designing reasonable visiting routes that are essential for the daily operations of companies. Therefore, this paper investigates a real-world electric vehicle routing problem (VRP) raised by a logistics company. The problem combines the features of the capacitated VRP, the VRP with time windows, the heterogeneous fleet VRP, the multi-trip VRP, and the electric VRP with charging stations. To solve such a complicated problem, a heuristic approach based on the adaptive large neighborhood search (ALNS) and integer programming is proposed in this paper. Specifically, a charging station adjustment heuristic and a departure time adjustment heuristic are devised to decrease the total operational cost. Furthermore, the best solution obtained by the ALNS is improved by integer programming. Twenty instances generated from real-world data were used to validate the effectiveness of the proposed algorithm. The results demonstrate that using our algorithm can save 7.52% of operational cost.<\/jats:p>","DOI":"10.3390\/a12020045","type":"journal-article","created":{"date-parts":[[2019,2,20]],"date-time":"2019-02-20T11:45:39Z","timestamp":1550663139000},"page":"45","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":51,"title":["A Heuristic Approach for a Real-World Electric Vehicle Routing Problem"],"prefix":"10.3390","volume":"12","author":[{"given":"Mengting","family":"Zhao","sequence":"first","affiliation":[{"name":"School of Automobile and Traffic Engineering, Wuhan University of Science and Technology, Wuhan 430065, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1020-6259","authenticated-orcid":false,"given":"Yuwei","family":"Lu","sequence":"additional","affiliation":[{"name":"School of Mechanical Engineering, Guangxi University of Science and Technology, Liuzhou 545006, China"}]}],"member":"1968","published-online":{"date-parts":[[2019,2,20]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1016\/S0166-218X(01)00351-1","article-title":"Models, Relaxations and Exact Approaches for the Capacitated Vehicle Routing Problem","volume":"123","author":"Toth","year":"2002","journal-title":"Discrete. Appl. Math."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1287\/trsc.1030.0056","article-title":"Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms","volume":"39","author":"Braysy","year":"2005","journal-title":"Transp. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1287\/trsc.1030.0057","article-title":"Vehicle Routing Problem with Time Windows, Part II: Metaheuristics","volume":"39","author":"Braysy","year":"2005","journal-title":"Transp. Sci."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1287\/trsc.1070.0190","article-title":"Heuristic Approaches for the Fleet Size and Mix Vehicle Routing Problem with Time Windows","volume":"41","author":"Monaci","year":"2007","journal-title":"Transp. Sci."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"676","DOI":"10.1287\/trsc.2015.0608","article-title":"The Multi-Trip Vehicle Routing Problem with Time Windows and Release Dates","volume":"50","author":"Cattaruzza","year":"2016","journal-title":"Transp. Sci."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"995","DOI":"10.1016\/j.ejor.2016.01.038","article-title":"The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations","volume":"252","author":"Hiermann","year":"2016","journal-title":"Eur. J. Oper. Res."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Arnau, Q., Juan, A.A., and Serra, I. (2018). On the Use of Learnheuristics in Vehicle Routing Optimization Problems with Dynamic Inputs. Algorithms, 11.","DOI":"10.3390\/a11120208"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Cassettari, L., Demartini, M., Mosca, R., Revetria, R., and Tonelli, F. (2018). A Multi-Stage Algorithm for a Capacitated Vehicle Routing Problem with Time Constraints. Algorithms, 11.","DOI":"10.3390\/a11050069"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Chen, S., Chen, R., and Gao, J. (2017). A Monarch Butterfly Optimization for the Dynamic Vehicle Routing Problem. Algorithms, 10.","DOI":"10.3390\/a10030107"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1287\/trsc.2015.0646","article-title":"Goods Distribution with Electric Vehicles: Review and Research Perspectives","volume":"50","author":"Pelletier","year":"2016","journal-title":"Transp. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1287\/trsc.2013.0490","article-title":"The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations","volume":"48","author":"Schneider","year":"2014","journal-title":"Transp. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/j.tre.2014.09.003","article-title":"A Heuristic Approach for the Green Vehicle Routing Problem with Multiple Technologies and Partial Recharges","volume":"71","author":"Felipe","year":"2014","journal-title":"Transport. Res. E-Log."},{"key":"ref_13","first-page":"57","article-title":"Iterated Tabu Search for the Mix Fleet Vehicle Routing Problem with Heterogenous Electric Vehicles","volume":"359","author":"Sassi","year":"2015","journal-title":"Model. Comput. Optim. Inf. Syst. Manag. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/j.cor.2014.07.003","article-title":"Battery Swap Station Location-Routing Problem with Capacitated Electric Vehicles","volume":"55","author":"Yang","year":"2015","journal-title":"Comput. Oper. Res."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/j.cor.2016.06.013","article-title":"An Adaptive Large Neighborhood Search Heuristic for the Electric Vehicle Scheduling Problem","volume":"76","author":"Wen","year":"2016","journal-title":"Comput. Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/j.trc.2016.01.013","article-title":"Partial Recharge Strategies for the Electric Vehicle Routing Problem with Time Windows","volume":"65","author":"Keskin","year":"2016","journal-title":"Transport. Res. C-Emer."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1388","DOI":"10.1287\/opre.2016.1535","article-title":"Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows","volume":"64","author":"Desaulniers","year":"2016","journal-title":"Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.trb.2017.02.004","article-title":"The Electric Vehicle Routing Problem with Nonlinear Charging Function","volume":"103","author":"Montoya","year":"2017","journal-title":"Transport. Res. B-Meth."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"995","DOI":"10.1016\/j.ejor.2017.01.011","article-title":"The Electric Location Routing Problem with Time Windows and Partial Recharging","volume":"260","author":"Schiffer","year":"2017","journal-title":"Eur. J. Oper. Res."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1016\/j.trb.2016.11.009","article-title":"Solving the Battery Swap Station Location-Routing Problem with Capacitated Electric Vehicles Using an AVNS Algorithm for Vehicle-Routing Problems with Intermediate Stops","volume":"97","author":"Hof","year":"2017","journal-title":"Transport. Res. B-Meth."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1016\/j.ijpe.2018.07.016","article-title":"Electric Vehicle Routing Problem with Recharging Stations for Minimizing Energy Consumption","volume":"203","author":"Zhang","year":"2018","journal-title":"Int. J. Prod. Econ."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/j.cor.2018.07.012","article-title":"The Green Mixed Fleet Vehicle Routing Problem with Partial Battery Recharging and Time Windows","volume":"101","author":"Macrina","year":"2019","journal-title":"Comput. Oper. Res."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/j.cor.2018.12.013","article-title":"Improved Formulations and Algorithmic Components for the Electric Vehicle Routing Problem with Nonlinear Charging Functions","volume":"104","author":"Froger","year":"2019","journal-title":"Comput. Oper. Res."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/j.tre.2011.08.001","article-title":"A Green Vehicle Routing Problem","volume":"48","year":"2012","journal-title":"Transport. Res. E-Log."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1287\/trsc.1050.0135","article-title":"An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows","volume":"40","author":"Ropke","year":"2006","journal-title":"Transp. Sci."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1016\/j.ejor.2012.06.044","article-title":"An Adaptive Large Neighborhood Search Heuristic for the Pollution-Routing Problem","volume":"223","author":"Demir","year":"2012","journal-title":"Eur. J. Oper. Res."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/j.tre.2015.11.004","article-title":"Adaptive Large Neighborhood Search Heuristics for the Vehicle Routing Problem with Stochastic Demands and Weight-Related Cost","volume":"85","author":"Luo","year":"2016","journal-title":"Transport. Res. E-Log."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"728","DOI":"10.1016\/j.cor.2011.05.005","article-title":"An Adaptive Large Neighborhood Search Heuristic for the Cumulative Capacitated Vehicle Routing Problem","volume":"39","author":"Ribeiro","year":"2012","journal-title":"Comput. Oper. Res."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"3215","DOI":"10.1016\/j.cor.2012.04.007","article-title":"An Adaptive Large Neighborhood Search Heuristic for Two-Echelon Vehicle Routing Problems Arising in City Logistics","volume":"39","author":"Hemmelmayr","year":"2012","journal-title":"Comput. Oper. Res."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1287\/trsc.1120.0432","article-title":"An Adaptive Large Neighborhood Search for the Pickup and Delivery Problem with Transfers","volume":"47","author":"Masson","year":"2013","journal-title":"Transp. Sci."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"972","DOI":"10.1016\/j.ejor.2016.11.026","article-title":"A Metaheuristic for the Time-Dependent Pollution-Routing Problem","volume":"259","author":"Franceschetti","year":"2017","journal-title":"Eur. J. Oper. Res."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/j.ejor.2016.03.040","article-title":"An Adaptive Large Neighborhood Search for the Two-Echelon Multiple-Trip Vehicle Routing Problem with Satellite Synchronization","volume":"254","author":"Grangier","year":"2016","journal-title":"Eur. J. Oper. Res."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1016\/j.trb.2016.11.003","article-title":"A Hybrid Large Neighborhood Search for the Static Multi-Vehicle Bike-Repositioning Problem","volume":"95","author":"Ho","year":"2017","journal-title":"Transport. Res. B-Meth."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1007\/s10951-011-0246-9","article-title":"Adaptive Large Neighborhood Search for Service Technician Routing and Scheduling Problems","volume":"15","author":"Kovacs","year":"2012","journal-title":"J. Sched."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1007\/s10732-014-9262-1","article-title":"Efficient Heuristics for the Workover Rig Routing Problem with a Heterogeneous Fleet and a Finite Horizon","volume":"20","author":"Ribeiro","year":"2014","journal-title":"J. Heuristics"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1007\/BF02022044","article-title":"Local Search in Routing Problems with Time Windows","volume":"4","author":"Savelsbergh","year":"1985","journal-title":"Ann. Oper. Res."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/j.trc.2015.09.009","article-title":"A Multi-Space Sampling Heuristic for the Green Vehicle Routing Problem","volume":"70","author":"Montoya","year":"2016","journal-title":"Transport. Res. C-Emer."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1016\/j.cor.2012.07.018","article-title":"A Hybrid Genetic Algorithm with Adaptive Diversity Management for a Large Class of Vehicle Routing Problems with Time-Windows","volume":"40","author":"Vidal","year":"2013","journal-title":"Comput. Oper. Res."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1016\/j.ejor.2008.07.022","article-title":"A Variable Neighborhood-Based Heuristic for the Heterogeneous Fleet Vehicle Routing Problem","volume":"197","author":"Imran","year":"2009","journal-title":"Eur. J. Oper. Res."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/2\/45\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:33:35Z","timestamp":1760186015000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/2\/45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,20]]},"references-count":39,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2019,2]]}},"alternative-id":["a12020045"],"URL":"https:\/\/doi.org\/10.3390\/a12020045","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,20]]}}}