New Optimization Models and Algorithms for Logistics and Delivery Problems

Abstract

Optimization is essential to logistics and delivery problems. It has been widely used to solve classical transportation problems. However, as technology improves and the demand increases, we face an increasing number of challenging and complex problems. In this dissertation, we propose new models and develop new efficient algorithms for emerging delivery problems. The first problem we study is the speed optimization problem, where a sequence of nodes is visited in order within prescribed time windows. It is a fundamental operational problem initially studied for tramp speed decisions. In this thesis, we study this problem regarding vessel and vehicle speed decisions. Given a sequence of nodes over a path, we aim to solve for the optimal speed between each pair of consecutive nodes to minimize total cost while respecting the time-window constraint at each node and speed limits over each arc. We develop an efficient and exact algorithm that is able to solve instances of 1000 nodes in less than a second. The algorithm is 20 to 100 times faster than a general convex optimization solver on test instances and requires much less memory. The solutions found at intermediate steps of our algorithm also provide some insights to ship planners on how to balance the operating cost and service quality. The second problem is the on-demand delivery problem with customer choice. Nowadays, an increasing number of delivery firms and retailers provide same-day delivery service in large metropolitan areas. In general, delivery firms offer some available delivery time windows and corresponding delivery fees to customers. In the meantime, a fleet of vehicles is dispatched to make delivery. We develop a policy based on value function approximation (VFA) to determine delivery fees and provide feasible vehicle routes jointly in real-time. After that, we show how VFA-based future anticipation improves the total profit and increases the number of served customers.