New algorithms for two logistics optimization problems

Abstract

Logistics optimization plays a critical role for modern companies in minimizing their costs to gain competitive advantage. In this thesis we study two logistics optimization problems, with one to determine an optimal route for a vehicle, which is a problem at operational level, and with the other to jointly decide on facility locations and network connections, which is a problem at both strategic and tactic level. Both of the two problems aim to minimize the total operational cost and have wide applications in transportation industry. For the first problem, its solution can help shipping carriers using a barge to reposition empty containers in a tree-shaped water system. For the second problem, its solution can be used to help transportation companies to construct plans of facility locations combined with vehicle routing or cargo shipping. Since both of the two problems are NP-hard, i.e., there unlikely exists any polynomial time algorithms that can solve them to optimality, it is of great interest to develop efficient or improved approximation algorithms that can produce near-optimal solutions in affordable running time for these two problems. This thesis comprises two essays and presents newly developed algorithms for these two logistics optimization problems. The problem studied in the first essay is named the Capacitated Traveling Salesman Problem with Pickup and Delivery on a Tree, and it aims to determine the best route for a vehicle with a finite capacity to transport amounts of a product from pickup points to delivery points on a tree-shaped network, such that the total travel distance of the vehicle is minimized. This problem has several applications in transportation industry and is well-known to be strongly NP-hard. We therefore develop a 2-approximation algorithm that is a significant improvement over the best constant approximation ratio of 5 derived from existing literature. Computational results show that the proposed algorithm also achieves good average performance, with a much shorter running time and better quality solution, over randomly generated instances. The problem studied in the second essay is named the k-median Steiner Forest Problem that jointly optimizes the opening of at most k facility locations and their connections to the client locations, so that each client is connected by a path to an open facility, with the total connection cost minimized. The problem has wide applications in the transportation and telecommunication industries, but is known to be strongly NP-hard. In the literature, only a 2-approximation algorithm is available, it being based on a Lagrangian relaxation of the problem and using a sophisticated primal-dual schema. Therefore, we develop an improved approximation algorithm using a simple transformation from an optimal solution of a minimum spanning tree problem. Compared with the existing algorithm, our new algorithm not only achieves a better approximation ratio that is easier to be proved, but also guarantees to produce solutions of equal or better quality-up to 50% improvement in some cases. Additionally, for two non-trivial special cases, where either every location contains a client, or all the locations are in a tree-shaped network, we have developed, for the first time in the literature, new algorithms that can solve the problem to optimality in polynomial time.