Variable neighborhood search algorithms for solving electric vehicle routing problems

The world has agreed to limit the effects of climate change by implementing the Paris Agreement. This requires fundamental and significant changes in the transportation sector, which is among the most carbon-intensive sectors of the global economy. As oil is by far the dominant energy source in the sector, vehicle electrification will play a crucial role in decarbonization. In addition to reducing greenhouse gas emissions, air and noise pollution will also be diminished, contributing to the prevention of related health problems. For logistics companies, electrifying vehicle fleets implies substantial savings in logistics costs through the use of electrical energy produced from renewable sources, as opposed to high and fluctuating fossil fuel prices. Several challenges must be overcome to promote widespread use of electric vehicles (EVs) in logistics activities. The limited energy capacity of EV batteries negatively impacts driving range, while long charging times adversely affect waiting times at charging stations (CSs). For logistics companies with EV fleets, vehicle routing must be designed to meet customers' service demands in terms of both quantity and time. Within the scope of this thesis, the objective is to effectively solve Electric Vehicle Routing Problem (EVRP) derivatives for routing the EV fleets of companies. In addition to EVRP, three EVRP derivatives incorporating time window and simultaneous pickup and delivery constraints, both together and separately, have been mathematically modeled. Exact solutions for small-sized problems have been found, while heuristic solution methods centered on the Variable Neighborhood Search (VNS) algorithm have been proposed for larger problems. Besides the local search operators utilized in the literature, problemspecific VNS operators have been developed. As a result of experimental studies, it has been observed that two versions of the Reduced VNS, one of the proposed heuristic solution methods, featuring the pipe and cyclic neighborhood change step, are the most effective algorithms for solving the problems. It has been noted that the solution improvement rates of VNS operators vary according to problem type, and better solutions can be reached in less time by excluding operators with low performance. KEYWORDS: Electric vehicle routing problem, variable neighborhood search algorithm, heuristic solution approach, exact solution approach