A multi-start route improving matheuristic for the production routeing problem

Abstract

This paper considers the multi-vehicle production routeing problem with a maximum-level replenishment policy. This is a well-established problem within vendor managed inventory where production, inventory and routeing decisions are made simultaneously. We present a novel method to solve the problem that outperforms existing methods both in terms of solution gaps and the number of best-known solutions. The proposed matheuristic is tested on three different sets of benchmark instances consisting of 1218 instances and finds or improves the best-known solution for 632 of them. For the remaining instances, the matheuristic is less than 2.5% from the best-known solutions. The method is particularly proficient on large instances and is also efficient for the inventory routeing problem. The success of the method is largely due to its improvement phase where a novel path-flow-inspired mathematical model is introduced. Here, a route set obtained from the current solution is used and retailers can be simultaneously inserted and removed from a route, making the method flexible even when a small route set is used. In addition, we introduce a new production subproblem that approximates the costs of using a vehicle instead of approximating the costs of visiting a retailer, making it very fast to solve.

Keywords:

• Transportation
• production routeing
• matheuristic
• inventory routeing
• heuristic

Acknowledgments

We would also like to thank the four anonymous referees for their constructive comments and suggestions, which helped improve the quality of the paper. In addition, we would also like to thank our collaborators in the AXIOM project for their valuable feedback. The contents of this paper reflect the views of the last author and not necessarily the views of Kinaxis Inc. or its affiliates.

Data availability statement

The data that support the findings of this study are openly available at http://axiomresearchproject.com/publications/.

Disclosure statement

No potential conflict of interest was reported by the authors.

Correction Statement

This article has been corrected with minor changes. These changes do not impact the academic content of the article.

Additional information

Funding

We would like to thank the Research Council of Norway for funding the research.

Notes on contributors

Simen T. Vadseth

Simen T. Vadseth holds an engineering degree in Industrial Economics and Technology Management from the Norwegian University of Science and Technology (NTNU). He is currently doing a Ph.D. at the same university where his thesis focuses on solution methods for hard combinatorial optimisation problems. Simen is also employed at St. Olav's University Hospital in Trondheim, Norway where he is involved with health logistics and optimisation.

Henrik Andersson

Henrik Andersson is a Professor of optimisation at Norwegian University of Science and Technology. He received an engineering degree in Industrial Engineering and Management from Linkping University and holds a Ph.D. in Infra Informatics from the same university. His primary research interest concerns the development of relevant discrete optimisation models and methods within transportation and healthcare logistics.

Magnus Stålhane

Magnus Stålhane is a Professor of Operations Research at the Norwegian University of Science and Technology (NTNU). He earned his MSc in Industrial Economics and Technology Management in 2008, and his PhD on Optimization of maritime routeing and scheduling problems with complicating inter-route constraints in 2013, both from NTNU. Stlhane has mainly been working on optimisation problems related to vehicle routeing and scheduling problems, but has also published several papers on applications of operations research in the offshore wind industry. Masoud Chitsaz

Masoud Chitsaz

Masoud Chitsaz is a Technical Thought Leader at Kinaxis, a global supply chain planning software company based in Canada. Masoud applies analytics to improve business decisions and operations. He has over 20 years of experience in supply chain and operations planning both in the industry and academia. Prior to immigrating to Canada, he co-founded a successful consulting company where he worked with a diverse range of public and private clients in retail, transportation, supply chain, steel production, auto manufacturing, infrastructure, and real estate. Masoud is also a council member of the Canadian Operations Research Society (CORS), and a mentor for supply chain startups at Next AI. He has a master's degree in Transportation, an MBA from Sharif University of Technology, and a PhD in Operations Management from HEC Montreal with the school's best thesis award. He has published papers in top-tier journals in operations management and supply chain.