Collaborative routing aided by drones in last-mile delivery (LMD) has been an extensively studied topic in recent years. In this article, a new optimization problem for collaborative routing with a truck and a fleet of drones in LMD is introduced. The problem proposes a new strategy to coordinate a truck and a fleet of drones to serve a given set of customers. The plan is based on identifying the locations where the truck can park and where the drones fly to serve the customers. A procedure to locate these parking lots conveniently is given. For the transportation network, which includes these points, a mixed linear integer programming formulation is provided, which aims to minimize the makespan of serving all the customers. Computational experiments on a set of problem instances were conducted to analyze the model solutions' characteristics and find their computational limits. The experiments showed that the proposed model could significantly improve the results obtained when only the truck delivers. Additionally, we propose a GRASP metaheuristic to solve instances of greater size. Its computational performance was studied when applied to a set of instances with different characteristics. The paper discusses some insights obtained from the computational experimentation and presents future research directions.

Uncertainty in optimization is not a new ingredient. Diverse models considering uncertainty have been developed over the last 40 years. In our paper we essentially discuss a particular uncertainty model associated with combinatorial optimization problems, developed in the 90's and broadly studied in the past years. This approach named minmax regret (in particular our emphasis is on the robust deviation criteria) is different from the classical approach for handling uncertainty, stochastic approach, where uncertainty is modeled by assumed probability distributions over the space of all possible scenarios and the objective is to find a solution with good probabilistic performance. In the minmax regret (MMR) approach, the set of all possible scenarios is described deterministically, and the search is for a solution that performs reasonably well for all scenarios, i.e., that has the best worst-case performance. In this paper we discuss the computational complexity of some classic combinatorial optimization problems using MMR approach, analyze the design of several algorithms for these problems, suggest the study of some specific research problems in this attractive area, and also discuss some applications using this model.