A Vehicle Routing Problem with Movement Synchronization of Drones, Sidewalk Robots, or Foot-Walkers

Puyuan Deng, MASc thesis, Civil Engineering, 2018
Professor Matthew J. Roorda, Supervisor


Express courier companies are experiencing congestion with their parcel deliveries particularly in dense urban areas due to high customer demand, limited road space and scarce parking supply. Accordingly, various companies are investing and exploring solutions to alleviate this congestion. One potential solution is to use autonomous technologies such as drones or sidewalk robots to assist with the delivery of parcel packages. In order to assess the implications of incorporating such technologies, an optimization model to the vehicle routing problem with movement synchronization is required.

This study proposes an exact formulation of the problem with a metaheuristic approach to solve large instances of the VRPMS to compare the cost benefit of incorporating the drone, the sidewalk robot, and the foot-walker. The foot-walker is the traditional option that express courier companies use during peak seasons to help with the surges in parcel delivery.

Comparison between different technologies
Figure 1: Route cost comparison between different technologies assisting the truck only delivery scheme.

As can be seen in Figure 1, given the assumptions made for the attributes of each technology, the foot-walker generated the largest savings followed by the sidewalk robot and then the drone. It is important to note that this result is heavily dependent on the assumptions made by the author from the most recent speculations of the capabilities of the drone and the sidewalk robot. As these technologies continue to mature and grow in the commercial market, there could be drastic changes to the results.

Access via Tspace / U of T Libraries: Abstract and full thesis “A Vehicle Routing Problem with Movement Synchronization of Drones, Sidewalk Robots, or Foot-Walkers.”

Supervisor contact information

Professor Matthew J. Roorda
Tel: 416-978-5976