Based on the most recent literature dealing with consistency, security aspects and surveillance tasks with respect to vehicle routing problems, we provide a formulation, a definition and a way to measure inconsistency as well as a suitable meta- and mathheuristic that is able to solve the problem given the restrictions from a real world application. As suitable characteristics for diversification in terms of inconsistency we present two possibilities: time of service and route diversity. Those two were selected since those are suitable for a wide range of problems. Time inconsistency is a necessary in patrol problems while route inconsistency is important in cash in transit problems.
One important restriction needs to be considered for the solution; the companies cannot control the actual routing drivers use to visit all stops, only the clustering and the time window realization can be controlled. Taking this information into account the clustering had to be used to ensure the route inconsistency and diversity. A two-stage solution process consisting of clustering and routing operations is applied (exact ones as well as heuristic ones). The models and heuristics performance were tested on classic instances for the vehicle routing problem as well as real-world instances from an Austrian security service provider.
With the method at hand we are able to generate good quality solutions for the Solomon instances as well as for the two newly created case studies.
| Subject : | : | Abstracts |
| Topics | : | Meta-heuristics |
| Topics | : | Real-Life VRPs |
| PDF version | : |  PDF version |
