Last mile delivery routing problem using autonomous electric vehicles

Official URL: https://risc01.sabanciuniv.edu/record=b3077860_(Table of contents)

Distribution management is one of the important elements of the supply chain or logistic system due to its large contribution to the total cost of the system. One of the growing industries in distribution management is using autonomous electric vehicles for last mile delivery. Applying autonomous delivery vehicles (ADV) to deliver the products has many applications in grocery shopping, logistics, food delivery, etc. In the real-world situations for ADV, a subset of delivery sites (customers) is visited directly; however, the remaining customers must be covered by (assigned to) the delivery sites en-route with which their distance is within the maximum walking distance. Accordingly, the present thesis studies a last-mile delivery routing using ADV which is a covering-routing problem (or median-routing problem) satisfying the load capacity, route distance/duration, and customer’s walking distance constraints. The addressed problem is called Covering Electric Vehicle Routing problem (CE-VRP). Two mathematical models are proposed for CE-VRP: one with the assignment cost as the objective function, and the other with the assignment distance as a constraint. The proposed models are developed according to efficient mathematical models proposed for handling the constraints of the maximum route distance/duration in the literature with the polynomial number of constraints and decision variables. Due to the NP-hardness of the CE-VRP, a new two-phase heuristic consisting of selecting the delivery sites and customers assignment (first phase), and routing the vehicles visiting the delivery sites (second phase) is proposed to solve iv the large-sized instances. Also, several efficient repair and improvement operators are proposed in the first phase, and a hybrid Variable Neighbourhood search with Simulated Annealing (VNS-SA) metaheuristic is designed to find the high-quality routes by diversifying and intensifying the solution space in the second phase. The computational results show the efficiency of the proposed method in solving the various-sized instances of CE-VRP and other covering-routing problems. Finally, concluding remarks and suggestions for future studies are stated.