Skip to main content
SpringerLink
Log in

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

  • S.I.: SOME
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  • Aggarwal, C. C., Orlin, J. B., & Tai, R. P. (1997). Optimized crossover for the independent set problem. Operations Research, 45(2), 226–234.

    Article  Google Scholar 

  • Ahuja, R., Orlin, J., & Tiwari, A. (2000). A greedy genetic algorithm for the quadratic assignment problem. Computers & Operations Research, 27(10), 917–934.

    Article  Google Scholar 

  • Alvelos, F., de Sousa, A., & Santos, D. (2013). Combining column generation and metaheuristics. In E.-G. Talbi (Ed.), Hybrid metaheuristics. Studies in computational intelligence (Vol. 434, pp. 285–334). Berlin: Springer.

    Chapter  Google Scholar 

  • Amirghasemi, M., & Zamani, R. (2015). An effective asexual genetic algorithm for solving the job shop scheduling problem. Computers & Industrial Engineering, 83, 123–138.

    Article  Google Scholar 

  • Amirghasemi, M., & Zamani, R. (2017). An effective evolutionary hybrid for solving the permutation flowshop scheduling problem. Evolutionary Computation, 25(1), 87–111. https://doi.org/10.1162/EVCO_a_00162.

    Article  Google Scholar 

  • Baker, B. M., & Ayechew, M. (2003). A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 30(5), 787–800.

    Article  Google Scholar 

  • Baldacci, R., Bartolini, E., & Mingozzi, A. (2011). An exact algorithm for the pickup and delivery problem with time windows. Operations Research, 59(2), 414–426.

    Article  Google Scholar 

  • Beasley, J. E. (1990). Or-library: Distributing test problems by electronic mail. The Journal of the Operational Research Society, 41(11), 1069–1072.

    Article  Google Scholar 

  • Beck, J. C., Prosser, P., & Selensky, E. (2002). On the reformulation of vehicle routing problems and scheduling problems. In S. Koenig & R. C. Holte (Eds.), Abstraction, reformulation, and approximation (pp. 282–289). Berlin: Springer.

    Chapter  Google Scholar 

  • Beheshti, A. K., & Hejazi, S. R. (2015). A novel hybrid column generation-metaheuristic approach for the vehicle routing problem with general soft time window. Information Sciences, 316, 598–615. nature-Inspired Algorithms for Large Scale Global Optimization.

    Article  Google Scholar 

  • Bierwirth, C., Mattfeld, D., & Kopfer, H. (1996). On permutation representations for scheduling problems. In H. M. Voigt, W. Ebeling, I. Rechenberg, & H. P. Schwefel (Eds.), Parallel problem solving from nature—PPSN IV (pp. 310–318). Berlin: Springer.

    Chapter  Google Scholar 

  • Borndörfer, R., Grötschel, M., Klostermeier, D., & Küttner, C. (1999). Telebus Berlin: Vehicle Scheduling in a dial-a-ride system. In N. H. M. Wilson (Ed.), Proceedings of the 7th international workshop on computer-aided transit scheduling. Lecture notes in economics and mathematical systems (pp. 391–422). Berlin: Springer.

    Chapter  Google Scholar 

  • Bräysy, O., & Gendreau, M. (2005). Vehicle routing problem with time windows, part I: Route construction and local search algorithms. Transportation Science, 39(1), 104–118.

    Article  Google Scholar 

  • Clerc, M., & Kennedy, J. (2002). The particle swarm-explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary computation, 6(1), 58–73.

    Article  Google Scholar 

  • Cordeau, J.-F., & Laporte, G. (2007). The dial-a-ride problem: Models and algorithms. Annals of Operations Research, 153, 29–46.

    Article  Google Scholar 

  • Davis, L. (1985). Job shop scheduling with genetic algorithms. In J. Grefenstette (Ed.), Proceedings of the first international conference on genetic algorithms (pp. 136–140). Hillsdale, NJ: Lawrence Erlbaum Associates.

    Google Scholar 

  • De Jong, K. A. (2006). Evolutionary computation: A unified approach. Cambridge: MIT Press.

    Google Scholar 

  • Desaulniers, G., Erdmann, A., Solomon, M. M., & Soumis, F. (2002). The VRP with pickup and delivery. The vehicle routing problem (pp. 225–242). Philadelphia: SIAM Monographs on Discrete Mathematics and Applications.

    Book  Google Scholar 

  • Desrosiers, J., Dumas, Y., Solomon, M. M., & Soumis, F. (1995). Time constrained routing and scheduling. Volume 8 of network routing, handbooks in operations research and management science (pp. 35–139). Amsterdam: Elsevier Science.

    Google Scholar 

  • Djerid, L., Portmann, M., & Villon, P. (1996). Performance analysis of permutation cross-over genetic operators. Journal of Decision Systems, 4(1/2), 157–177.

    Article  Google Scholar 

  • Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53–66.

    Article  Google Scholar 

  • Eiben, A., & Schippers, C. (1998). On evolutionary exploration and exploitation. Fundamenta Informaticae, 35(1), 35–50.

    Article  Google Scholar 

  • Elluru, S., Gupta, H., Kaur, H., & Singh, S.P. (2017). Proactive and reactive models for disaster resilient supply chain. Annals of Operations Research. https://doi.org/10.1007/s10479-017-2681-2.

  • Espinoza, D., Garcia, R., Goycoolea, M., Nemhauser, G. L., & Savelsbergh, M. W. P. (2008). Per-seat, on-demand air transportation part I: Problem description and an integer multicommodity flow model. Transportation Science, 42(3), 263–278.

    Article  Google Scholar 

  • Falkenauer, E., & Bouffouix, S. (1991). A genetic algorithm for job shop. In Proceedings. IEEE International conference on robotics and automation, 1991(Vol. 1, pp. 824–829).

  • Fox, B., & McMahon, M. (1991). Genetic operators for sequencing problems. Foundations of Genetic Algorithms, 1, 284–300.

    Google Scholar 

  • Gao, L., Zhang, G., Zhang, L., & Li, X. (2011). An efficient memetic algorithm for solving the job shop scheduling problem. Computers & Industrial Engineering, 60(4), 699–705.

    Article  Google Scholar 

  • Goldberg, D., & Lingle, R. (1985). Alleles, loci and the traveling salesman problem. In Proceedings of the 1st international conference on genetic algorithms (pp. 154–159). Hillsdale, NJ: L. Erlbaum Associates Inc.

  • Holland, J. H. (1975). Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence. Ann Arbor: University of Michigan Press.

    Google Scholar 

  • Iyer, S., & Saxena, B. (2004). Improved genetic algorithm for the permutation flowshop scheduling problem. Computers & Operations Research, 31(4), 593–606.

    Article  Google Scholar 

  • Kaur, H., & Singh, S. P. (2016). Sustainable procurement and logistics for disaster resilient supply chain. Annals of Operations Research. https://doi.org/10.1007/s10479-016-2374-2.

  • Kaur, H., & Singh, S. P. (2017). Flexible dynamic sustainable procurement model. Annals of Operations Research. https://doi.org/10.1007/s10479-017-2434-2.

  • Moscato, P. (1989). On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. In Caltech concurrent computation program, C3P Report 826, 1989.

  • Pacquette, J., Cordeau, J.-F., Laporte, G., & Pascoal, M. M. B. (2013). Combining multicriteria analysis and tabu search for dial-a-ride problems. Transportation Research Part B: Methodological, 52, 1–16.

    Article  Google Scholar 

  • Parragh, S. (2011). Introducing heterogeneous users and vehicles into models and algorithms for the dial-a-ride problem. Transportation Research Part C, 19, 912–930.

    Article  Google Scholar 

  • Poon, P., & Carter, J. (1995). Genetic algorithm crossover operators for ordering applications. Computers & Operations Research, 22(1), 135–147.

    Article  Google Scholar 

  • Potvin, J.-Y., & Bengio, S. (1996). The vehicle routing problem with time windows part II: Genetic search. INFORMS Journal on Computing, 8(2), 165–172.

    Article  Google Scholar 

  • Reeves, C., & Yamada, T. (1998). Genetic algorithms, path relinking, and the flowshop sequencing problem. Evolutionary Computation, 6(1), 45–60.

    Article  Google Scholar 

  • Rochat, Y., & Taillard, r. (1995). Probabilistic diversification and intensification in local search for vehicle routing. Journal of Heuristics, 1(1), 147–167. https://doi.org/10.1007/BF02430370.

    Article  Google Scholar 

  • Ropke, S., Cordeau, J.-F., & Laporte, G. (2007). Models and branch-and-cut algorithms for pick up and delivery problems with time windows. Networks, 49(4), 258–272.

    Article  Google Scholar 

  • Shukla, N., Choudhary, A., Prakash, P., Fernandes, K., & Tiwari, M. (2013a). Algorithm portfolios for logistics optimization considering stochastic demands and mobility allowance. International Journal of Production Economics, 141(1), 146–166.

    Article  Google Scholar 

  • Shukla, N., Dashora, Y., Tiwari, M. K., Chan, F. T. S., & Wong, T. C. (2008). Introducing algorithm portfolios to a class of vehicle routing and scheduling problem. In Proceedings of The 2nd international conference on operations and supply chain management (pp. 1–10).

  • Shukla, N., & Kiridena, S. (2016). A fuzzy rough sets-based multi-agent analytics framework for dynamic supply chain configuration. International Journal of Production Research, 54(23), 6984–6996. https://doi.org/10.1080/00207543.2016.1151567.

    Article  Google Scholar 

  • Shukla, N., Tiwari, M., & Ceglarek, D. (2013b). Genetic-algorithms-based algorithm portfolio for inventory routing problem with stochastic demand. International Journal of Production Research, 51(1), 118–137.

    Article  Google Scholar 

  • Solomon, M. (1983). Vehicle routing and scheduling with time window constraints: Models and algorithms. Ph.D. thesis, Dept. of Decision Sciences, University of Pennsylvania.

  • Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2), 254–265.

    Article  Google Scholar 

  • Starkweather, T., Mcdaniel, S., Whitley, D., & Mathias, K. (1991). A comparison of genetic sequencing operators. In Proceedings of the fourth international conference on genetic algorithms (pp. 69–76). Morgan Kaufmann.

  • Syswerda, G. (1991). Schedule optimization using genetic algorithms. In L. Davis (Ed.), Handbook of genetic algorithms (pp. 332–349). New York: Van Norstrand Reinhold.

    Google Scholar 

  • Toth, P., & Vigo, D. (1997). Heuristic algorithms for the handicapped persons transportation problem. Transportation Science, 31(1), 60–71.

    Article  Google Scholar 

  • Wang, H., Lee, D.-H., & Cheu, R. (2009). PDPTW based taxi dispatch modeling for booking service. In Proceedings of the 5th international conference on natural computation. ICNC’09 (pp. 242–247). Piscataway, NJ: IEEE Press.

  • Whitley, L., Starkweather, T., & Fuquay, D. (1989). Scheduling problems and traveling salesmen: The genetic edge recombination operator. In Proceedings of the 3rd international conference on genetic algorithms (pp. 133–140). San Francisco, CA: Morgan Kaufmann Publishers Inc.

Download references

Acknowledgements

The authors thank DropPoint Australia Pty. Ltd for their collaboration and support.

Author information

Authors and Affiliations

  1. ACRF Image-X Institute, Sydney Medical School, University of Sydney, Sydney, 2006, Australia

    Michelle Dunbar

  2. l’Institut National des Sciences Appliquées de Toulouse (INSA), 31077, Toulouse Cedex 4, France

    Simon Belieres

  3. School of Systems, Management and Leadership, University of Technology Sydney, Sydney, 2007, Australia

    Nagesh Shukla

  4. SMART Infrastructure Facility, University of Wollongong, Wollongong, 2522, Australia

    Mehrdad Amirghasemi & Pascal Perez

  5. Hull University Business School, University of Hull, Hull, UK

    Nishikant Mishra

Authors
  1. Michelle Dunbar
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Simon Belieres
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Nagesh Shukla
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Mehrdad Amirghasemi
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Pascal Perez
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Nishikant Mishra
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Nagesh Shukla.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Dunbar, M., Belieres, S., Shukla, N. et al. A genetic column generation algorithm for sustainable spare part delivery: application to the Sydney DropPoint network. Ann Oper Res 290, 923–941 (2020). https://doi.org/10.1007/s10479-018-2911-2

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-018-2911-2

Keywords

Search

Navigation