In this dissertation, I study a relatively novel variant form of traveling salesman problem (TSP), i.e. traveling salesman problem with time windows and a drone (TSPTWD) or multiple drones (TSPTWmD) with intermediate points. Mathematical models and metaheuristics were successfully developed, and numerical experiments showed promising savings of delivery time versus conventional modes.

The first essay (Chapter 2) is an extension of one of the earliest studies of this topic which established a traveling salesman model of a truck and a drone. That model only allows the drone to be operated on customers’ sites. I developed a new model to solve a novel variant of TSP, i.e. traveling salesman problem with time windows and a drone (TSPTWD) which can be operated on customers’ sites and intermediate points. Computational experiments have been implemented to test my new model. The results of small size problems (less than seven customers) showed that my new model can save delivery time as large as 42.8% than the traditional pure truck TSP model. Comparing with the existing model of a truck and a drone operated only on customers’ sites, my new model further increased the saving as large as 2.85%. And that saving could be even larger if I implement my model on larger size problems (with more customers).

Due to the NP-hardness, only small size problems (less than seven customers) can be solved exactly in a practical period (less than one hour). Some LP heuristics can provide relatively good solutions within a shorter time. But that computing time will also increase too large with growing problem size. Then I developed other heuristics or metaheuristics to solve large size problems within an acceptable period in the second essay.

In the second essay (Chapter 3) I developed multiple heuristics and metaheuristics to solve TSPTWD problems with as many as 100 customers which are likely the size of problems in the real world. At first, the problem of poor-quality solutions had been met and a series of improvement strategies were initiated. Those strategies were developed based on the specific nature of this novel problem TSPTWD. When those strategies were implemented the metaheuristics generated solutions with much higher quality.

Numerical experiments were designed and implemented to test the developed metaheuristics and the impact of factors. The results showed that the algorithm SA_01 outperformed SA_02 and the naïve method of TSPTWD. My model can save as large as 26% of the delivery time than the traditional pure truck TSP. The idea of my research to provide intermediate points on arcs did generate more delivery time savings than only operating the drone on customers’ sites. That improvement could be as large as 4%. The results also showed that lower customer density provides more opportunities for delivery time saving.

In the third essay (Chapter 4) I developed a new mathematical model of traveling salesman problem with time windows and multiple drones (TSPTWmD) which can be operated on customers’ sites and intermediate points and two metaheuristics, i.e. simulated annealing 02, 03 (SA_02, SA_03) to solve TSPTWmD problems as large as 100 customers which is similar to the size of problems in the real world.

The improvement strategies of essay 2 were implemented and multiple drones were incorporated into the new metaheuristics. Computational experiments were designed and implemented to test the developed metaheuristics and the impact of factors. The results showed that algorithm SA_03 outperformed SA_02 and it is even better than SA_01. The delivery time saving can be as large as 32.1% comparing with the traditional pure truck TSP. The idea of my research to provide multiple drones did generate more delivery time savings than only using one drone. The results show that the delivery time could be further reduced as large as more than 5%. The impact of factors is similar as demonstrated in Chapter 3 that lower customer density provides more opportunities for delivery time saving.