Modeling and Optimization of Truck and Robot Routing without Robot-Depots

With the continuous growth of online commerce, managing last-mile deliveries has become increasingly complex, leading to higher costs and longer delivery times. New technologies have made it possible to use autonomous wheeled robots to support trucks, allowing for multiple deliveries to be carried out simultaneously. This thesis presents and analyzes an innovative strategy that combines trucks and robots to make the delivery process more efficient. Unlike other approaches, no depots are used for renting robots; instead, it is assumed that the robots are owned by the delivery companies, making the system less dependent on external factors and therefore easier to implement. The solution approach uses column generation and heuristic methods to improve operational efficiency. The results show that as the number of customers to be served increases, this strategy becomes more effective compared to traditional delivery methods, with cost savings that in some cases exceed 20%. The developed method generally outperforms traditional delivery methods, especially when a large number of deliveries with tight or closely overlapping time windows need to be completed.