A decomposition heuristic for a rich production routing problem

We propose a decomposition heuristic to solve a rich production routing problem arising in the context of a make-to-order company. The problem is motivated by the operations of a Brazilian furniture manufacturer and considers several important features, such as multiple products, sequence-dependent setup times, a heterogeneous fleet of vehicles, routes extending over one or more periods, multiple time windows and customer deadlines, among others. An integrated mathematical model is presented and is used as a basis to develop the heuristic, which solves the problem by decomposing it in two parts that are solved iteratively. The first subproblem focuses on the production planning and customer assignment decisions, and uses an approximation for the routing costs and travel times. The second subproblem makes the routing decisions, which are further improved by a local search algorithm. The solution of the second subproblem is then used to update the approximation of the routing costs and travel times in the first subproblem. We use a large set of random instances to benchmark our heuristic against a general-purpose solver. Numerical results show that our method provides, in shorter computing times, solutions of similar quality as those obtained by the solver for instances with up to 15 customers. For larger instances, with 20 to 50 customers, the heuristic clearly outperforms the solver, which in most cases cannot find any solution after 24 h of computing time.