engleski

Solving the Electric Vehicle Routing Problem Using a Hybrid Adaptive Large Neighborhood Search Method

In order to perform a high-quality and on-time delivery in logistic systems, it is necessary to efficiently manage a delivery fleet. Nowadays, due to the new policies and regulations related to greenhouse gas emission in the transport sector, logistic companies are paying higher penalties for each emission gram of CO_2/km. With Electric Vehicle (EV) market penetration, many companies have started to evaluate the integration of EVs in their fleet, as EVs do not have local greenhouse gas emissions, produce minimal noise, and are independent of the fluctuating oil price. Well- researched Vehicle Routing Problem (VRP) is extended to the Electric Vehicle Routing Problem (EVRP), which takes into account specific characteristics of EVs. EVRP aims to determine a set of least-cost electric vehicle delivery routes from a depot to a set of geographically scattered customers, subject to side constraints. As VRP is an NP-hard problem, the EVRP is also an NP-hard problem, which incurs the use of heuristic and metaheuristic procedures to solve the problem. Over the years, various heuristic procedures were applied to solve the VRP problem. In the last several years, these procedures were modified for application on the EVRP problem. In the literature, for each problem variant of the EVRP, i.e., time windows, partial recharging, full recharge, different charging stations, etc., a specifically designed metaheuristic procedure is proposed. The main objective of this thesis is to develop a Hybrid Adaptive Large Neighborhood Search (HALNS) method for solving different variants of the EVRP problem. The proposed method includes a local search for improving the solution and exact procedure for optimal Charging Station (CS) placement. In the first part of the thesis, the proposed hybrid method was implemented and compared to the non-hybrid method used for solving EVRP. Also, the advantages of the metaheuristic methods were highlighted in comparison to the exact method for solving the problem defined as a mixed integer linear program. The developed hybrid method was applied to solve different EVRP variants. In the end, the results were analyzed and compared to the so-far best-known solutions. In the second part, the new time-dependent EVRP problem with time windows and charging time dependent on the state-of-charge was presented. The problem considers temporal changes in the traffic network while routing BEVs, which are usually caused by congestion. In the last part, the adapted delivery problem of a Croatian company was modeled as EVRP and solved by the HALNS method. Instead of using conventional vehicles, the fleet of EVs with equal vehicle characteristics (load and battery capacity) was considered.

electric vehicles ; electric vehicle routing problem ; hybrid metaheuristic ; heuristics ; exact procedures ; dynamic programming ; time-dependent routing ; logistic

nije evidentirano