An Adaptive Large Variable Neighborhood Search for a Combined Vehicle Routing and Scheduling Problem
Benjamin Graf  1@  
1 : Osnabrück University  (UOS)

The problem posed in the VeRoLog Solver Challenge 2019 requires the routing and scheduling of trucks and technicians to satisfy a given set of item deliveries and subsequent installations. At the core of the proposed solution method is a Variable Neighborhood Search (VNS) applying well-known operators such as 2-opt, Or-opt, inter-route relocate and inter-route exchange. All operators are either tailored towards the improvement of the truck or the technician tours. To escape local optima the VNS is embedded in an Adaptive Large Neighborhood Search (ALNS) combining multiple removal and insertion operators. Optimizing routes and schedules of trucks and technicians may be conflicting goals, due to the broad objective function, the scheduling constraints on technicians and the time window constraints on deliveries. Therefore, trucks and technicians are improved in two different modes, either respecting or ignoring their counterpart technicians and trucks respectively. In conjunction with a rather tight time limit it is required to focus on those aspects of a given problem instance that yield the largest improvements. To achieve that, the procedures and operators are organized in a dynamically weighted tree that guides the search process. In addition, certain sub-problems, e.g. the scheduling of technicians, the minimization of trucks and the distribution of truck tours over the trucks are achieved by embedded bin-packing and matching procedures.

Online user: 1 RSS Feed