Task allocation—computing the logistics of snow-plowing

In winter, snowfall can rapidly disrupt daily life and impact on Japan's economy. Snowplowing is a considerable annual expense, and methods for co-ordinating plowing activity are needed to ensure an efficient, cost-effective service. Clever computer models are needed to manage such complex activities, which involve many agents and interactions.

Now, Satoshi Takahashi at the University of Electro-Communications, and Tokuro Matsuo at the Advanced Institute for Industrial Technology in Tokyo have devised a computational method that combines task allocation and scheduling of individual snow-plows to maximize efficiency.

The researchers aimed to identify the best routes for multiple snow-plows to take without replicating route paths, meaning their computer model had to allocate and schedule tasks simultaneously. They considered various routes in the city of Yonezawa as a series of graphical plots; this gave each snow-plow 'agent' a set of potential arcs, or routes, to follow.

Takahashi and Matsuo then devised an algorithm for task allocation, followed by an agent simulation to determine the best-fit arcs for each plow at any given time. Their method calculates directed paths that minimize inefficient movement for each snow-plow, with the option of setting a maximum time limit for a task. Throughout the process, the progress of other snowploughs is monitored so that individual routes can be changed instantaneously.

The researchers found that a higher number of snow-plows does not equal faster, more efficient clearance. There are an optimum number of operating snow-plows needed depending on each snowfall scenario. The model could help direct the country's snow-plow network in future.