A decomposition heuristic for a rich production routing problem. (October 2018)

• Record Type: Journal Article
• Authors: Miranda, Pedro L.; Cordeau, Jean-François; Ferreira, Deisemera; Jans, Raf; Morabito, Reinaldo
• Is Part Of: Computers & operations research. Volume 98(2018)
• Page Start: 211
• Page End: 230
• Publication Date: 2018-10
• Subjects: Production routing problem -- Integrated production and distribution planning -- Decomposition heuristic -- Lot-sizing; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2018.05.004
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We study a rich production routing problem arising in the context of a make-to-order company. We propose a decomposition heuristic to solve the problem. The heuristic decomposes the problem into two subproblems that are solved iteratively. Computational results indicate that our heuristic clearly outperforms a general-purpose commercial solver. Abstract: 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.