Michelle Dunbar
A genetic column generation algorithm for sustainable spare part delivery: Application to the Sydney DropPoint Network
Dunbar, Michelle; Belieres, Simon; Shukla, Nagesh; Amirghasemi, Mehrdad; Perez, Pascal; Mishra, Nishikant
Authors
Simon Belieres
Nagesh Shukla
Mehrdad Amirghasemi
Pascal Perez
Professor Nishikant Mishra Nishikant.Mishra@hull.ac.uk
Professor/ Head of Management Systems Subject Group
Abstract
Modern-day logistics companies require increasingly shorter lead-times in order to cater for the increasing popularity of on-demand services. There is consequently an urgent need for fast scheduling algorithms to provide high quality, real-time implementable solutions. In this work we model a spare part delivery problem for an on-demand logistics company, as a variant of vehicle routing problem. For large delivery networks, the optimisation solution technique of column generation has been employed successfully in a variety of vehicle routing settings and is often used in combination with exact methods for solving problems with a large number of variables. Challenges may arise when the pricing subproblem is difficult to solve in a realistic period due to complex constraints or a large number of variables. The problem may become intractable when the network structure varies daily or is known with less certainty over longer period. In such instances, a high quality heuristic solution may be more preferable than an exact solution with excessive run time. We propose an improved version of column generation approach integrating an efficient genetic algorithm to obtain fast and high-quality solutions for a sustainable spare parts delivery problem. More specifically, we propose to retain the traditional column generation iterative framework, with master problem solved exactly, but with pricing subproblem solved using a metaheuristic. Computational results on a real dataset indicate that this approach yields improved solutions compared to the current best-case business-as-usual costs. It also substantially decreases the computational time; allowing for high-quality, tractable solutions to be obtained in few minutes. We propose to strike a balance between the practical and efficient solution aspects of metaheuristic algorithms, and the exact decomposition and iterative aspect of the column generation solution technique.
Citation
Dunbar, M., Belieres, S., Shukla, N., Amirghasemi, M., Perez, P., & Mishra, N. (2018). A genetic column generation algorithm for sustainable spare part delivery: Application to the Sydney DropPoint Network. Annals of Operations Research, 1-19. https://doi.org/10.1007/s10479-018-2911-2
Journal Article Type | Article |
---|---|
Acceptance Date | May 23, 2018 |
Online Publication Date | Jun 1, 2018 |
Publication Date | Jun 1, 2018 |
Deposit Date | Aug 8, 2018 |
Publicly Available Date | Jun 2, 2019 |
Print ISSN | 0254-5330 |
Publisher | Springer Verlag |
Peer Reviewed | Peer Reviewed |
Pages | 1-19 |
DOI | https://doi.org/10.1007/s10479-018-2911-2 |
Keywords | Spare parts delivery; Logistics; Optimisation; Metaheuristics |
Public URL | https://hull-repository.worktribe.com/output/971832 |
Publisher URL | https://link.springer.com/article/10.1007%2Fs10479-018-2911-2 |
Contract Date | Aug 8, 2018 |
Files
Article
(239 Kb)
PDF
Copyright Statement
©2018 The authors
You might also like
The role of fairness in multi-tier sustainable supply chains
(2021)
Journal Article
Exploring the role of social capital mechanisms in cooperative resilience
(2022)
Journal Article
Downloadable Citations
About Repository@Hull
Administrator e-mail: repository@hull.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search