When routing money collection additionally to the total collecting time minimization, avoiding robberies is also a major concern and so the tours cannot somehow be anticipated. This problem is faced by a Portuguese company when the safes of the parking meters need to be collected.
The safes are spread over the streets so Arc Routing is a natural approach. Although some studies for node routing problem exist, references on arc routing regarding the safety issue could not be found. We called this new problem Dissimilar Arc Routing Problem (DARP).
DARP is defined on a mixed graph. Edges represent narrow two way streets that may be served by only one traversal. Arcs are large two way streets that need to be served each direction, or one way streets. The nodes are street crossings, dead-end streets and a depot, where every tour must start and end. The links that represent streets with safes to be collected are named as tasks. Services should be performed on a daily basis and a planning time horizon of five working days is on focus. The problem aims at finding a set of dissimilar tours, one tour for each day, which minimizes the total time.
To impose dissimilarity, tours are divided into periods, and it is avoided that a same task is scheduled for the same period in different tours. We present a mixed integer programming formulation and a matheuristic. Computational experiments are reported.
Keywords: Arc Routing; Dissimilar Arc Routing; Integer Programming Formulation; Matheuristics.
| Subject : | : | Abstracts |
| Topics | : | Heuristics |
| PDF version | : |  PDF version |
