Simon Belieres, Pascal Perez, Mehrdad Amirghasemi, Nishikant Mishra, Michelle Dunbar, Nagesh Shukla, The University of Sydney, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Schol of Computer Science and IT, University of Nottingham, UK (UON), Hull University Business School (HUBS), University of Hull [United Kingdom], Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), and Université Fédérale Toulouse Midi-Pyrénées
© 2018 Springer Science+Business Media, LLC, part of Springer Nature 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.