The simultaneous rapidly increasing demand for home delivery of goods and on-demand expectancy of customers over the past years leaves a tough challenge for the logistical branch. They have to keep up with this increasing demand and simultaneously they are obliged to satisfy consumer service level demands to preserve their customers. On the other hand, as economic goals drive these businesses, they are prompted to operate cost-effectively. As a result, the fleet, deployed to execute the last-mile delivery, should meet both the requirement of cost-efficiency as well as the requirement for meeting consumer service level demands. This raises the question of how to efficiently design a fleet for last-mile on-demand logistics. For a fleet to be able to operate cost-efficiently, the fleet design decisions are required to take both fixed and variable costs into account. As such, the fleet design decisions need to include the consideration of the size of the fleet as well as the distance the vehicles travel on daily basis. Therefore, the goal of this thesis is to develop a novel method for fleet design for last-mile on-demand logistics. This work contributes by being the first to investigate methods for doing fleet design specifically for last-mile on-demand logistics considering multiple depots and variable pick-up locations. The purpose of the method is to determine the operational plans of the individual vehicles, the number of vehicles needed throughout a certain time period, the pick-up locations for all orders and the total distance travelled by the full fleet of vehicles. The proposed method builds upon established fleet design methods for ride-sharing taxi problems. The optimization method is adapted for last-mile on-demand logistics, yielding the required number of vehicles and their individual operational plans. The input of the system is a set of trips, which represent a path of a single vehicle to deliver one or multiple orders from a depot. Connecting two trips, which is called chaining, has the benefit of reducing the number of vehicles used, as chained trips are served by a single vehicle. Additionally, from multiple available depots where orders can be picked up, the method determines the best depot per order. This part of the method is called depot re-assignment. Furthermore, the fleet design problem is modelled as a multi-objective optimisation problem to find the trade-off between fleet size and the total distance the vehicles travel. Three different modelled datasets, each containing 10.000 order requests in the city centre of Amsterdam, are used to prove the value of the given method. A comparison between the method with and without depot re-assignment is made, to prove the value of the given addition of depot re-assignment. It is proven that depot re-assignment is valuable as it decreases or retains the fleet size for all test cases. The experiments conducted show that a significant decrease of the required fleet size can be established by a minor increase in total travelled distance. Furthermore, the optimal trade-off between the fleet size and the total distance travelled can be determined for a specific operation with the knowledge of operational costs for that operation.