Scientific Program > Talks by Speaker > Jagtenberg Caroline

Matheuristics for the 2019 VeRoLog Solver Challenge: MIPs and Bits
Caroline Jagtenberg  1, *@  , Andrea Raith  1@  , Michael Sundvick  1@  , Kevin Shen  1@  , Andrew Mason  1@  , Oliver Maclaren  1@  
1 : University of Auckland  (UoA)  -  Website
70 Symonds St Auckland 1010 New Zealand -  New Zealand
* : Corresponding author

We decompose the 2019 VeRoLog Solver Challenge problem into two parts: trucks and technicians. These are effectively two dependent VRPs. A feasible solution is obtained by first solving the more challenging technician problem and then using this solution as a constraint on the time windows for the truck problem. The technician problem has two main difficulties: there is no central depot, and there are rostering constraints. We use a heuristic to construct several feasible solutions for the technician problem. We combine these solutions, using all their routes as input for a generalized Set Covering Problem (SCP), solved using Gurobi's Mixed Integer Program (MIP) solver. We then take all routes in the solution of this SCP, and generate a neighbourhood of these promising routes. Rather than sequentially evaluating these neighbouring routes in a heuristic manner, we add these routes as columns to the MIP, which is solved again iteratively. We are thereby exploring the neighborhood of our solution in an exact way. The obtained set of technician routes are then heuristically assigned to days (without guarantee that a feasible solution can be obtained). To increase the likelihood of finding a feasible assignment, we add constraints limiting the total number of days each technician can work. The truck problem is solved similarly: we generate initial solutions using a sequential savings algorithm and use these as input for a SCP model followed by columnwise neighborhood search. Finally, we combine truck routes to reduce the number of trucks needed, using a bin packing algorithm. 

Online user: 1 RSS Feed