Integrated location and routing problems: Models, algorithms and applications
The study of integrated location and routing problems is fundamental for developing efficient designs of transportation networks in logistic applications. In this dissertation, we address two alternative drone-assisted logistic operations in which the decisions of (1) what locations in the network need to be visited? and (2) in what order? are taken simultaneously. In the first problem, we consider an unmanned surface vehicle (USV) that needs to visit a subset of the given locations in order to cover all locations not visited, at the minimum total travel time. It is assumed that the USV is loaded with a scanning device that can cover a specified range around it. We propose to model this problem with a variant of the Shortest Covering Path Problem in which the USV can cover while in-transit, and develop a column generation-based heuristic by reformulating the mixed-integer linear model using Dantzig-Wolfe decomposition. An extensive computational evaluation shows that our heuristic outperforms CPLEX on the most challenging instances, in both solution quality and required CPU time. In the second problem, we consider an application in lastmile delivery of parcels in which an unmanned aerial vehicle (UAV) is used in coordination with a delivery truck to deliver packages to a set of clients. It is assumed that the UAV is launched from the truck to deliver a parcel and then meets the truck again in a rendezvous location. It is allowed for the truck to visit other clients while the drone is flying, however, the UAV has a limited time on air since it is battery powered. The objective is to determine a coordinated tour for the truck and the UAV, such that all the clients are served at the minimum total completion time of the route. We propose a mixed-integer formulation for this problem, and a coverage-based decomposition heuristic. Computational experiments are conducted to test the performance of our heuristic. The results suggest that our approach is suitable to be used in practical applications with large-scale instances, since it is able to produce solutions of good quality in very short times when compared to a dynamic programming approach from the academic literature.