Premium
Dissimilar arc routing problems
Author(s) -
Constantino Miguel,
Mourão M. Cândida,
Pinto Leonor S.
Publication year - 2017
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21763
Subject(s) - arc routing , routing (electronic design automation) , solver , integer programming , computer science , operations research , vehicle routing problem , mathematical optimization , point (geometry) , linear programming , integer (computer science) , arc (geometry) , computer network , mathematics , algorithm , geometry , programming language
Money collection presents particular problems in terms of effective vehicle routing. Planning the collection or distribution of money for ATMs or parking meters gives rise to two problems: while the total collecting time should be minimized, tours on successive days should be different to prevent robberies. The combination of these two problems is named as the Dissimilar Routing Problem. When the safes to be collected are located along the streets, it corresponds to an arc routing problem, which we call D A R P , and when the money is from ATMs, it corresponds to a vehicle routing problem, usually referred to as the peripatetic routing problem. The former problem arises in a Portuguese company in charge of street parking in Lisbon. The firm needs to define tours to collect safes from parking meters, minimizing the total collecting time. To avoid robberies these tours cannot be repeated or somehow anticipated. For this new problem, we present a mixed integer linear programming (MILP) model and develop a matheuristic. Preliminary experiments are provided with data that mimic the real confidential data. Results point to a good performance of the matheuristic, while the smaller instances can be solved to optimality with the MILP model and a commercial solver. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(3), 233–245 2017