Human solution strategies for the vehicle routing problem: Experimental findings and a choice-based theory

Abstract The vehicle routing problem is one of the classical problems in transportation science. Many algorithms have been proposed over the last decades, but the problem is still hard to solve, even for computers. We conduct a laboratory experiment to identify human solution strategies for the vehicle routing problem. Using a newly introduced discrete choice model, we show that humans tend to follow local-to-global problem-solving strategies, which involves a distinction between a first construction and a second improvement phase. When comparing the human performance with the optimal solution and classical heuristics (nearest neighbor, savings, and sweep), we see that participants typically perform better than the worst heuristic and worse than the best heuristic. Also, the combination of clustering and routing in the vehicle routing problem complicates finding good solutions compared to the traveling salesman problem, where particularly poor clustering leads to poor solutions. Especially participants with lower cognitive reflection test scores fail to identify good clusters and tend to use clusters that make the routing problem of a cluster easier. Moreover, only participants with a high cognitive reflection test score were able to improve solutions by using feedback on the current tour length. The other group even disimproved. Lastly, using the feedback option too often leads to a decline in performance which implies an overreaction of corrections made to an existing solution.