{"title":"Vehicle Routing Problem with Mixed Fleet of Conventional and Heterogenous Electric Vehicles and Time Dependent Charging Costs","authors":"Ons Sassi, Wahiba Ramdane Cherif-Khettaf, Ammar Oulamara","volume":99,"journal":"International Journal of Mathematical and Computational Sciences","pagesStart":171,"pagesEnd":182,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/10000760","abstract":"
In this paper, we consider the vehicle routing problem
\r\nwith mixed fleet of conventional and heterogenous electric vehicles
\r\nand time dependent charging costs, denoted VRP-HFCC, in which
\r\na set of geographically scattered customers have to be served by a
\r\nmixed fleet of vehicles composed of a heterogenous fleet of Electric
\r\nVehicles (EVs), having different battery capacities and operating
\r\ncosts, and Conventional Vehicles (CVs). We include the possibility
\r\nof charging EVs in the available charging stations during the routes
\r\nin order to serve all customers. Each charging station offers charging
\r\nservice with a known technology of chargers and time dependent
\r\ncharging costs. Charging stations are also subject to operating time
\r\nwindows constraints. EVs are not necessarily compatible with all
\r\navailable charging technologies and a partial charging is allowed.
\r\nIntermittent charging at the depot is also allowed provided that
\r\nconstraints related to the electricity grid are satisfied.
\r\nThe objective is to minimize the number of employed vehicles and
\r\nthen minimize the total travel and charging costs.
\r\nIn this study, we present a Mixed Integer Programming Model and
\r\ndevelop a Charging Routing Heuristic and a Local Search Heuristic
\r\nbased on the Inject-Eject routine with different insertion methods. All
\r\nheuristics are tested on real data instances.<\/p>\r\n","references":"[1] K. Aissat and A. Oulamara, \u201cA posteriori approach of real-time rideshar-\r\ning problem with intermediate locations,\u201d in proceedings of ICORES\r\n2015, 2015.\r\n[2] O. Sassi and A. Oulamara, \u201cSimultaneous electric vehicles scheduling\r\nand optimal charging in the business context: Case study.\u201d IET, 2014.\r\n[3] O. Sassi and Oulamara, \u201cJoint scheduling and optimal charging of elec-\r\ntric vehicles problem,\u201d in Computational Science and Its Applications\u2013\r\nICCSA 2014. Springer, 2014, pp. 76\u201391.\r\n[4] S. Pelletier, O. Jabali, and G. Laporte, \u201cGoods distribution with electric\r\nvehicles: Review and research perspectives,\u201d 2014.\r\n[5] M. Ramezani, M. Graf, and H. Vogt, \u201cA simulation environment for\r\nsmart charging of electric vehicles using a multi-objective evolutionary\r\nalgorithm,\u201d in Information and Communication on Technology for the\r\nFight against Global Warming, vol. ICT-GLOW 2011, LNCS 6868,\r\n2011, p. pp. 5663.\r\n[6] J. Lee, G. Park, H. Kwak, and H. Jeon, \u201cDesign of an energy con-\r\nsumption scheduler based on genetic algorithms in the smart grid,\u201d in\r\nComputational Collective Intelligence. Technologies and Applications,\r\nvol. ICCCI 2011, Part I, LNCS 6922, 2011, p. 438447.\r\n[7] J. Kang, S. J. Duncan, and D. N. Mavris, \u201cReal-time scheduling tech-\r\nniques for electric vehicle charging in support of frequency regulation,\u201d\r\nProcedia Computer Science, vol. 16, pp. 767 \u2013775, 2013.\r\n[8] P. Toth and D. Vigo, The vehicle routing problem. Siam, 2001.\r\n[9] C. B. e. P. W.Ramdane cherif, M. Haj Rachid, \u201cNew notation and\r\nclassification scheme for vehicle routing problems,\u201d RAIRO, vol. DOI\r\n10.1051\/ro\/2014030, p. To appear, 2014.\r\n[10] A. Artmeier, J. Haselmayr, M. Leucker, and M. Sachenbacher, \u201cThe\r\noptimal routing problem in the context of battery-powered electric\r\nvehicles,\u201d in Workshop CROCS at CPAIOR-10, 2nd International Work-\r\nshop on Constraint Reasoning and Optimization for Computational\r\nSustainability, 2010.\r\n[11] S. Erdogan and E. Miller-Hooks, \u201cA green vehicle routing problem,\u201d\r\nTransport. Res., vol. Part E 48, pp. 100\u2013114, 2012. [12] C. Lin, K. Choy, G. Ho, S. Chung, and H. Lam, \u201cSurvey of green vehicle\r\nrouting problem: Past and future trends,\u201d Expert. Syst. Appl., vol. 41,\r\npp. 1118\u20131138, 2014.\r\n[13] M. Schneider, A. Stenger, and D. Goeke, \u201cThe electric vehicle routing\r\nproblem with time windows and recharging stations,\u201d University of\r\nKaiserslautern, Germany, Tech. Rep., 2012.\r\n[14] D. Goeke, M. Schneider, and D. S. E. A. Professorship, \u201cRouting a\r\nmixed fleet of electric and conventional vehicles,\u201d Darmstadt Technical\r\nUniversity, Department of Business Administration, Economics and\r\nLaw, Institute for Business Studies (BWL), Tech. Rep., 2014.\r\n[15] G. Hiermann, J. Puchinger, and R. F. Hartl, \u201cThe electric fleet size\r\nand mix vehicle routing problem with time windows and recharging\r\nstations,\u201d Working Paper. Accessed July 17, 2014. URL: h ttp:\/\/prolog.\r\nunivie. ac. at\/research\/publications\/downloads\/Hie 2014 638. pdf,\r\nTech. Rep., 2014.\r\n[16] A\u00b4 . Felipe, M. T. Ortun\u02dco, G. Righini, and G. Tirado, \u201cA heuristic ap-\r\nproach for the green vehicle routing problem with multiple technologies\r\nand partial recharges,\u201d Transportation Research Part E: Logistics and\r\nTransportation Review, vol. 71, pp. 111\u2013128, 2014.\r\n[17] S. Bashash, S. J. Moura, J. C. Forman, and H. K. Fathy, \u201cPlug-in hybrid\r\nelectric vehicle charge pattern optimization for energy cost and battery\r\nlongevity,\u201d Journal of Power Sources, vol. 196, pp. 541\u2013549, 2010.\r\n[18] A. Millner, \u201cModeling lithium ion battery degradation in electric vehi-\r\ncles,\u201d in Innovative Technologies for an Efficient and Reliable Electricity\r\nSupply (CITRES), 2010 IEEE Conference on. IEEE, 2010, pp. 349\u2013356.\r\n[19] R. Hassin and A. Keinan, \u201cGreedy heuristics with regret, with applica-\r\ntion to the cheapest insertion algorithm for the tsp,\u201d Operations Research\r\nLetters, vol. 36, no. 2, pp. 243\u2013246, 2008.\r\n[20] M. Dell\u2019Amico, M. Monaci, C. Pagani, and D. Vigo, \u201cHeuristic ap-\r\nproaches for the fleet size and mix vehicle routing problem with time\r\nwindows,\u201d Transportation Science, vol. 41, no. 4, pp. 516\u2013526, 2007.","publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 99, 2015"}