A shortest path-based algorithm for the inventory routing problem of waste vegetable oil collection

Abstract

We consider an inventory routing problem over a time horizon in which wasted vegetable oil has to be collected from source points periodically. These source points have different accumulation rates and limited storage capacities that must not be exceeded. Collected waste is then processed and used as raw material for producing high-quality grease, oils and tallows. The decision problem is to determine for each day which source points to visit as well as the routes of the vehicles operating, such that cost-effectiveness is maximised. In this paper, we tackle this problem with two different but complementary approaches. First, we develop integer programming techniques to solve a relaxed version of the problem, without routing constraints. Then, we propose a constructive heuristic based on the shortest path and split procedures. Performances are compared with the actual company’s solution; numerical tests performed on real-world data with up to 3000 customers served on a 30 day time horizon show that our algorithms are able to increase cost-effectiveness by up to 20%.

Keywords:

• Reverse logistics
• inventory routing
• waste vegetable oil
• integer programming
• heuristics

Acknowledgements

Work in this paper was carried out with financial support from the National Sciences and Engineering Research Council of Canada, through an Engage grant, and with supportfrom the Department of Mathematics and Industrial Engineering of Polytechnique Montréal, for which the first author is thankful. Authors would also like to thank the company for their involvement in the project.

Notes

No potential conflict of interest was reported by the authors.