Snow removal is a perennial problem in northern countries where snowfall is not predictable and the snow removal process may be different from year to year. The study is of the snow removal process in Swedish urban areas which may be similar to experiences in other countries. A city is divided in to areas serviced by contractors. The optimization is confined to an area only as contractors may not cooperate with each other. The street network in an area is manageable. Consider the case of snow removal after the snowfall so that once cleared, the street is without snow for the rest of the period. Though this problem has been considered by the authors in a previous work, it is difficult to solve it exactly. Consider a single vehicle that is used in a sub-area and the driver should cover all that area totally without any interactions among drivers of different sub-areas. The problem is that of a vehicle tour. If the streets are undirected, the problem is same as the Chinese postman problem that can be easily solved. If the roads are directed, then the problem is that of a directed Chinese postman and can be solved easily. If some streets are one way, and others are not it, is a mixed Chinese postman problem. If some roads need not have be cleared, then it is a Chinese rural postman problem. All of them are NP-hard and for the undirected rural postman problem, there are efficient heuristics available.
展开▼
