A decomposition heuristic for a rich production routing problem

Author(s)

Miranda, Pedro L. ^[1] ; Cordeau, Jean-Francois ^{[2, 3]} ; Ferreira, Deisemera ^[4] ; Jans, Raf ^{[2, 3]} ; Morabito, Reinaldo ^[1]

Affiliation

^[1] Univ Fed Sao Carlos, Dept Prod Engn, Rodovia Washington Luis Km 235, BR-13565905 Sao Carlos, SP - Brazil

^[2] HEC Montreal, 3000 Chemin Cote St Catherine, Montreal, PQ H3T 2A7 - Canada

^[3] CIRRELT, 3000 Chemin Cote St Catherine, Montreal, PQ H3T 2A7 - Canada

^[4] Univ Fed Sao Carlos, Dept Phys Chem & Math, Rodovia Joao Leme dos Santos Km 110, BR-18052780 Sorocaba, SP - Brazil

• Document type: Journal article
• Source: Computers & Operations Research; v. 98, p. 211-230, OCT 2018.
• Web of Science Citations: 2

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. (C) 2018 Elsevier Ltd. All rights reserved. (AU)

• FAPESP's process: 14/10565-8 - Mathematical models and solutions method for the integrated lot-sizing, scheduling and distribution problem with split delivery
• Grantee: Pedro Luis Miranda Lugo
• Support Opportunities: Scholarships in Brazil - Doctorate
• FAPESP's process: 15/24916-0 - Solution methods for an integrated lot-scheduling and routing problem in furniture industry
• Grantee: Pedro Luis Miranda Lugo
• Support Opportunities: Scholarships abroad - Research Internship - Doctorate