Optimizing Drones For Last-Mile Delivery: The Traveling Salesman Problem

Today’s increasingly competitive landscape of eCommerce and omni-channel delivery execution has emerged a model known as “the traveling salesman problem” – referring to the use of multiple drones in commercial last-mile operations.

Even though the use of drones was initially mainly in the aircraft and military operations, drones are entering more and more pores of our society. However, not every application is by all means perfect.

Drones and the “Traveling Salesman Problem”

A thesis written by Justin J. Yoon at the Massachusetts Institute of Technology explores the feasibility of deploying drones to the last mile, modeling the cost of serving customers with one truck and multiple drones in the context of the traveling salesman problem.

Meanwhile, a definition of the “traveling salesman problem” is:

“Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?”

This theory of computational complexity concerns many industries and is often the main subject for developing algorithms to increase the efficacy. Formulated in 1930, it is one of the most intensively studied problems in optimization.

In the thesis, the author constructs a model with mixed integer linear programming (MILP) optimization and assessed with a sensitivity analysis of several parameters, finding significant cost savings of over 30% in terms of the TSP on the base case and 55% in the best scenario.

Companies Need to Identify Pivotal Opportunities to Gain a Competitive Edge

Inspired by his advisors, the author outlines his market scope, predicting the the cost of the global parcel delivery market is estimated to approx. $82 billion US dollars, with all percent being generated in China, Germany and the United States. (Joerss et al., 2016)

The author also outlines that given the vast and growing use of the parcel delivery market, it is crucial for companies to identify pivotal opportunities and gain a competitive edge. As written in the thesis:

“The rapid expansion and establishment of e-commerce by companies like Amazon are primary drivers and leading indicators for this growth. In 2015, consumers worldwide spent 1.7 trillion dollars on ecommerce; this amount is projected to double to 3.5 trillion by 2019 (Lindner, 2015). This increased demand on online retail consumption has shifted the market landscape from one that has been previously B2B-dominated to one in which B2C drives over 50 percent of global volume. To capitalize on this shift, it is important for companies to understand that over half of global parcel delivery costs are primarily incurred in the last mile (Joerss et al., 2016). ”

The increasing congestion and density of urban populations requires companies to innovate and fight through traffic and idling more often – a challenge from which drones are wholly exempt, according to the author.

Drones are Favorable Over Trucks Because of Their High-Speed and Efficiency

Drones are favorable over trucks for their ability to maintain high speeds in the face of congested roads, but also have a couple of downsides – mainly linked to the lack of regulation and the several physical constraints.

The two crucial limitations of drones are their limited payload capacity (5 pounds) and range of approximately 10 miles, assuming a speed of 50 miles per hour. To overcome the constraints, the author cites Murray and Chu (2015) and their plan in which a single drone is attached to a truck and dispatched en-route to serve customers.

The thesis also formulates a mathematical model, defining its various components and outlining an entire plan of how a model of this could work, deploying multiple drones and including all the operating fuel and labor costs.

Future Research on the Subject

As a last note, the author also outlines his future research that would be interesting to explore in terms of impact of drone usage in TSP. He outlines several notable topics, including:

“One is the trade off between truck capacity and number of drones available per tour. Optimization of this decision can potentially define an industry standard on how any drones that each delivery truck should carry. Another interesting topic of future research is the feasibility of each drone being able to carry more than one package and serve more than one customer at a time. Once this is determined to be feasible, the upside to 45 drone development and usage in the last-mile can be explosive. Finally, future optimizations and models should work to include the capability of drones to launch and rendezvous with the truck at a point other than a network node.”

The author of the thesis concludes that “disruption is imminent” for a model like this to be properly put into action – and yield immense cost savings over TSP compared to the truck-only use and delivery.

Citation: “The traveling salesman problem with multiple drones : an optimization model for last-mile delivery”, Yoon, Justin J, URI: http://hdl.handle.net/1721.1/117930 | Massachusetts Institute of Technology. Supply Chain Management Program | https://dspace.mit.edu/bitstream/handle/1721.1/117930/1051223610-MIT.pdf?sequence=1