A genetic column generation algorithm for sustainable spare part delivery: application to the Sydney DropPoint network

Michelle Dunbar, Simon Belieres, Nagesh Shukla (), Mehrdad Amirghasemi, Pascal Perez and Nishikant Mishra
Additional contact information
Michelle Dunbar: University of Sydney
Simon Belieres: l’Institut National des Sciences Appliquées de Toulouse (INSA)
Nagesh Shukla: University of Technology Sydney
Mehrdad Amirghasemi: University of Wollongong
Pascal Perez: University of Wollongong
Nishikant Mishra: University of Hull

Annals of Operations Research, 2020, vol. 290, issue 1, No 41, 923-941

Abstract: 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.

Keywords: Spare parts delivery; Logistics; Optimisation; Metaheuristics (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-018-2911-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:290:y:2020:i:1:d:10.1007_s10479-018-2911-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-018-2911-2

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().