Experimental Designs for Optimizing Last-Mile Delivery

Companies like Amazon and UPS are heavily invested in last-mile delivery problems. Optimizing last-delivery operations not only creates tremendous cost savings for these companies but also generate broader societal and environmental benefits in terms of better delivery service and reduced air pollutants and greenhouse gas emissions. Last-mile delivery is readily formulated as the Travelling Salesman Problem (TSP), where a salesperson must visit several cities and return to the origin with the least cost. A solution to this problem is a Hamiltonian circuit in an undirected graph. Many methods exist for solving the TSP, but they often assume the travel costs are fixed. In practice, travel costs between delivery zones are random quantities, as they are subject to variation from traffic, weather, and other factors. Innovations such as truck-drone last-mile delivery creates even more uncertainties due to scarce data. A Bayesian D-optimal experimental design in conjunction with a regression model are proposed to estimate these unknown travel costs, and subsequently search for a highly efficient solution to the TSP. This framework can naturally be extended to incorporate the use of drones and any other emerging technology that has use in last-mile delivery.