| Abstract | 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 CO2/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 emission, 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 the 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 the EVRP problem. 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 of the first part of the thesis, 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 EVs, which are usually caused by congestion. In the last part, the adapted delivery problem of a Croatian company was modeled as EVRP problem 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. |
| Abstract (croatian) | Glavni cilj istraživanja ove disertacije je: (i) razviti hibridnu metodu adaptivnoga pretraživanja velikog susjedstva za rješavanje različitih inačica postojećih EVRP problema i (ii) predložiti novi model vremenski ovisnog usmjeravanja električnih vozila te na njemu primijeniti razvijenu metodu. U sklopu disertacije ostvarena su sljedeća tri izvorna znanstvena doprinosa: razvoj hibridne ALNS metode za rješavanje postojećih inačica problema usmjeravanja električnih vozila; razvoj modela vremenski ovisnog usmjeravanja električnih vozila s vremenskim prozorima i pripadnog mješovitog cjelobrojnog programa; rješavanje razvijenog modela problema vremenski ovisnog usmjeravanja električnih vozila s vremenskim prozorima prilagođenom hibridnom ALNS metodom. Kroz postignute rezultate može se zaključiti kako je predložena HALNS metoda sposobna učinkovito riješiti različite postojeće inačice EVRP problema, prema različitim kriterijima minimizacije. Na skoro svim testiranim testnim problemima, metoda je pronašla nekoliko, do sada neobjavljenih, najbolje ostvarenih rezultata, čime se najbolje ukazuje na učinkovito rješavanje EVRP problema. Istovremeno predložena metoda ima vrijeme izvršavanja kraće od većine drugih metoda primijenjenih za rješavanje EVRP problema. Razvijeni novi problem vremenski ovisnog EVRP-a nastoji uzeti u obzir vremenski promjenjivo stanje prometne mreže, i kao rezultat izbjegavati kretanje vozila po zagušenim prometnicama, te ako postoji koristiti vremenski brži put. Na taj način može se uštedjeti na vremenu putovanja, na uštrb povećanja prijeđene udaljenosti. Za rješavanje problema predložena HALNS metoda modificirana je s dijelovima za izračun vremenski ovisnog vremena putovanja. Rezultati na srodnim problemima ukazuju da se predložena metoda može primijeniti za rješavanje vremenski ovisnog VRP problema. Ostvareni rezultati disertacije pokazuju veliki potencijal za provođenje daljnjeg istraživanja u području usmjeravanja električnih vozila. |
